التطور التفاضلي — محسن احتمالي عالمي
- قدّمه
- Rainer Storn & Kenneth Price
- السنة
- 1997
- النوع
- Population-based stochastic metaheuristic
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
التطور التفاضلي (DE)، الذي قدمه راينر ستورن وكينيث برايس في عام 1997، هو خوارزمية تحسين احتمالية قائمة على السكان مصممة للمساحات البارامترية المستمرة. يقوم بتوليد حلول مرشحة عن طريق دمج فروق المتجهات بين أعضاء السكان الحاليين، مما يجعله بديلاً قوياً وقليل المعلمات للخوارزميات الجينية وتحسين أسراب الجسيمات عندما تكون مساحة البحث غير محدبة، أو متعددة القيم، أو غير مناسبة للطرق المعتمدة على التدرج.
الفكرة الحدسية وراء الطريقة
تخيل مجموعة من المستكشفين منتشرين عبر منظر طبيعي غير معروف يبحثون عن أدنى وادٍ. في كل خطوة، يراقب كل مستكشف ثلاثة زملاء تم اختيارهم عشوائياً، ويتحرك في الاتجاه الذي يقترحه الفرق بين اثنين منهم مضروباً في عامل حجم الخطوة، ثم يقرر ما إذا كان الموضع الجديد أو القديم هو تضاريس أفضل. على مدار جولات عديدة، تتجمع المجموعة بأكملها تدريجياً حول أعمق وادٍ وجدته بشكل جماعي. يعمل التطور التفاضلي بنفس الطريقة بالضبط: "الفرق" بين متجهين للسكان يعمل كاتجاه بحث، وعامل القياس F يتحكم في مدى جرأة كل خطوة.
التاريخ
تم تقديم التطور التفاضلي بواسطة راينر ستورن وكينيث برايس في ورقتهما البحثية الرائدة عام 1997 في مجلة تحسين الأداء العالمي. نشأت الخوارزمية من عمل برايس السابق على التلدين الجيني وتجارب ستورن على تقاطع النقطة العائمة. أثبت المتغير الأصلي، الذي يسمى الآن DE/best/1/bin، أنه تنافسي مع استراتيجيات التطور والخوارزميات الجينية المعاصرة وغالباً ما يتفوق عليها في المعايير القياسية. قامت مراجعة شاملة من قبل داس، موليك، وسوغانثان (2016) بتصنيف أكثر من عقدين من المتغيرات والمخططات التكيفية والتطبيقات، مما رسخ DE كواحدة من الطرق الأساسية في أدبيات الأساليب فوق الإحصائية.
متى تُستخدم
التطور التفاضلي مناسب عندما تكون الدالة الهدف مستمرة، وربما غير قابلة للاشتقاق أو متعددة القيم، وتكون حدود البحث لجميع المعلمات معروفة مسبقاً. لا تتطلب معلومات التدرج ولا افتراضات طبيعية، لذا فهي مناسبة للتصميم الهندسي، وضبط المعلمات الفائقة، ومعايرة نماذج المحاكاة، وأي مهمة تحسين للصندوق الأسود. حجم السكان الذي يبلغ حوالي 10 أضعاف عدد المعلمات هو نقطة انطلاق شائعة. لا ينبغي تطبيق DE على مشاكل منفصلة أو توافقية بحتة؛ كما أنها تحتاج إلى 1000 تكرار على الأقل للتقارب بشكل موثوق — إذا كانت ميزانية تقييم الدالة ضيقة جداً، فإن التحسين البايزي هو بديل أكثر كفاءة من حيث العينات.
الحدود والاعتبارات
- يمكن أن يكون التقارب بطيئاً إذا كان عدد التكرارات غير كافٍ؛ غالباً ما يؤدي أقل من 1000 جيل إلى نتيجة دون المستوى الأمثل.
- أداء حساس لاختيار F و CR — يمكن أن تؤدي المعلمات غير المضبوطة بشكل جيد إلى تقارب مبكر أو تقدم بطيء بشكل مفرط.
- غير مصممة لمساحات البحث المنفصلة أو التوافقية البحتة؛ توجد امتدادات منفصلة ولكنها أقل شيوعاً.
- تتطلب كل تكرار تقييم الدالة الهدف NP مرة، والتي يمكن أن تكون مكلفة عندما يكون كل تقييم مكلفاً حسابياً.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- لا تتطلب معلومات التدرج — تعمل مع أي دالة هدف للصندوق الأسود، بما في ذلك الدوال غير القابلة للاشتقاق والمشوشة.
- عدد قليل جداً من معلمات التحكم (F، CR، NP) مقارنة بقوة البحث الخاصة بها، مما يجعلها سهلة التكوين نسبياً.
- تتعامل بشكل طبيعي مع المناظر الطبيعية متعددة القيم حيث تتقارب المحسنات المعتمدة على التدرج إلى القيم المثلى المحلية.
- يمكن موازاة تقييمات السكان بشكل مستقل ومباشر، مما يقلل من وقت الساعة الحائطية على الأنظمة متعددة النوى.
- تنافسية مع الخوارزميات الجينية وتحسين أسراب الجسيمات على العديد من المعايير مع استخدام قاعدة تحديث أبسط.
التطبيقات
- معايرة نماذج المحاكاة ونماذج الوكلاء التي تكون دوالها الهدف غير تحليلية.
- تحسين المعلمات الفائقة لخطوط أنابيب التعلم الآلي عندما تكون مساحة البحث مستمرة ومحدودة.
- مشاكل التصميم الهندسي مثل تصميم الهوائيات، والتحسين الهيكلي، وضبط المتحكمات.
- تدريب الشبكات العصبية وتكييف النماذج غير الخطية في الهندسة والعلوم الطبيعية.
- تحسين أوزان المحفظة وتقدير المعلمات في نماذج السلاسل الزمنية المالية.
كيف يعمل
كيف يعمل
يتم رسم مجموعة من NP متجهات حلول مرشحة بشكل موحد وعشوائي ضمن حدود البحث المحددة مسبقاً لكل معلمة. يجب على المستخدم تحديد حدود البحث قبل بدء الخوارزمية؛ لا يمكن لـ DE استنتاج هذه الحدود من المشكلة. تغطي مجموعة أولية جيدة المساحة الممكنة بالكامل حتى لا تفوت الخوارزمية المناطق الواعدة في البداية.
لكل متجه هدف في السكان، يتم اختيار ثلاثة متجهات مميزة عشوائياً. يتم تشكيل متجه متحور عن طريق إضافة الفرق المقاس لاثنين منهم إلى الثالث: v = x_r1 + F*(x_r2 - x_r3)، حيث F هو عامل القياس (عادةً 0.4–1.0). هذه الخطوة المعتمدة على الفرق هي ما يميز DE عن الخوارزميات التطورية الأخرى ويمنحها معلومات اتجاهية ذاتية التكيف دون الحاجة إلى حساب التدرج.
يتم بناء متجه تجريبي عن طريق خلط المتجه المتحور والمتجه الهدف الأصلي عنصراً بعنصر. يتم أخذ كل عنصر من المتجه المتحور باحتمالية CR (معدل التقاطع، عادةً 0.5–1.0) ومن المتجه الهدف بخلاف ذلك؛ يتم أخذ عنصر واحد على الأقل دائماً من المتجه المتحور. تتحكم هذه الخطوة في التوازن بين الاستكشاف والاستغلال: معدل CR مرتفع يفضل المتجه المتحور، ومعدل CR منخفض يحافظ على المزيد من الحل الحالي.
يتم تقييم المتجه التجريبي على الدالة الهدف ومقارنته بالمتجه الهدف. إذا حقق المتجه التجريبي قيمة هدف مساوية أو أفضل، فإنه يحل محل المتجه الهدف في الجيل التالي؛ وإلا يتم الاحتفاظ بالمتجه الهدف دون تغيير. هذا الاختيار الجشع واحد لواحد يمنع السكان من التدهور ويضمن تحسناً رتيباً لأفضل حل تم العثور عليه.
تتكرر الطفرة والتقاطع والاختيار لعدد كافٍ من الأجيال (عادةً 1000 أو أكثر) حتى يتم استيفاء معيار التقارب — على سبيل المثال، انخفض التغيير في أفضل قيمة هدف عن عتبة التسامح، أو تم الوصول إلى الحد الأقصى لعدد التكرارات. أفضل متجه في السكان النهائي هو حل الخوارزمية.
الأخطاء الشائعة
- يعد تشغيل DE بعدد قليل جداً من التكرارات (أقل من ~1000) الخطأ الأكثر شيوعاً — لم تحصل الخوارزمية على أجيال كافية للتقارب، ويجب التعامل مع النتيجة على أنها أولية؛ انتقل إلى التحسين البايزي إذا كانت ميزانية التقييم ضيقة.
- ضبط عامل القياس F منخفضاً جداً يؤدي إلى انهيار التنوع مبكراً؛ ضبطه مرتفعاً جداً يمنع التقارب. ابدأ بـ F في [0.4، 1.0] وقم بالضبط تجريبياً.
- يعد إغفال حدود البحث أو تحديدها بشكل خاطئ خطأً فادحاً — يستخدم DE الحدود لتهيئة السكان وسينتج نتائج غير ذات معنى إذا كانت الحدود ضيقة جداً أو غائبة.
- يعد التعامل مع DE كتشغيل لمرة واحدة محفوفاً بالمخاطر في المناظر الطبيعية متعددة القيم — قم بإجراء العديد من التجارب المستقلة من بذور عشوائية مختلفة وقم بالإبلاغ عن أفضل حل تم العثور عليه عبر التشغيلات.
الأسئلة الشائعة
كيف أختار عامل القياس F ومعدل التقاطع CR؟
الافتراضات الافتراضية الأكثر شيوعاً هي F = 0.8 و CR = 0.9 لاستراتيجية DE/best/1/bin. في الممارسة العملية، يتحكم F في حجم الخطوة — القيم حول 0.4–1.0 نموذجية — ويتحكم CR في مقدار استبدال المتجه المتحور للمتجه الهدف. إذا تقاربت المجموعة بسرعة كبيرة، قم بزيادة F أو خفض CR. تقوم متغيرات DE التكيفية (jDE، JADE) بضبط هذه المعلمات تلقائياً أثناء التشغيل، وهو خيار معقول عندما يكون الضبط اليدوي غير عملي.
كم عدد الأجيال المطلوبة؟
كقاعدة عامة، يوصى بما لا يقل عن 1000 جيل. بالنسبة للمشاكل عالية الأبعاد (العديد من المعلمات) أو المناظر الطبيعية المعقدة، قد تكون هناك حاجة إلى مزيد من التكرارات. راقب قيمة الهدف لأفضل حل عبر الأجيال: إذا لم تتغير لعدة مئات من التكرارات، فمن المحتمل أن DE قد تقاربت — أو ركدت، وفي هذه الحالة يُنصح بإعادة التشغيل ببذرة عشوائية جديدة.
كيف يقارن DE بالخوارزميات الجينية وتحسين أسراب الجسيمات؟
كلها أساليب فوق إحصائية قائمة على السكان للتحسين المستمر. يستخدم DE عادةً معلمات تحكم أقل من GAs ولديه قاعدة تحديث أبسط وحتمية مقارنة بـ PSO. على العديد من المعايير القياسية، يكون DE تنافسياً مع كليهما أو يتفوق عليهما، ولكن الأداء يعتمد على المشكلة. غالباً ما يأتي الاختيار إلى الألفة والتطبيقات المتاحة بدلاً من التصنيف الشامل.
هل يمكن لـ DE التعامل مع المعلمات الصحيحة أو الفئوية؟
تم تصميم DE للمساحات المستمرة. يمكن استيعاب المعلمات الصحيحة عن طريق تقريب الحل المستمر إلى أقرب عدد صحيح بعد كل تحديث، ولكن هذا تقريب. المشاكل الفئوية أو التوافقية البحتة — مثل الجدولة أو التوجيه — تخدمها بشكل أفضل الطرق المصممة للمساحات المنفصلة، مثل تحسين مستعمرة النمل أو البحث المحرم.
طرق ذات صلة
المصادر
Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.
افتح مرجع DOIتم النسخ.Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.
افتح مرجع DOIتم النسخ.