NSGA-II القوي — التحسين متعدد الأهداف في ظل عدم اليقين
- قدّمه
- Kalyanmoy Deb and Himanshu Gupta
- السنة
- 2006
- النوع
- Robust evolutionary multi-objective optimization algorithm
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
يوسع NSGA-II القوي خوارزمية NSGA-II التطورية الكلاسيكية لتأخذ في الاعتبار عدم اليقين البارامتري، مما يجد حلولًا مثلى لباريتو تظل عالية الأداء حتى عندما تنحرف معلمات الإدخال عن قيمها الاسمية. فبدلاً من تحسين قيم الأهداف عند نقطة واحدة، يقوم بتقييم كل حل مرشح عبر نطاق أو توزيع من تحقيق عدم اليقين ويختار المتانة جنبًا إلى جنب مع هيمنة باريتو.
الفكرة الحدسية وراء الطريقة
من الناحية العملية، تواجه التصميمات الهندسية والقرارات السياسية ظروف تشغيل غير مؤكدة: تختلف خصائص المواد، وتختلف توقعات الطلب عن الواقع، وتتقلب الأحمال البيئية. قد يؤدي الحل الذي يبدو أمثل عند القيم الاسمية للمعلمات إلى أداء ضعيف في ظل انحرافات معقولة. يعالج NSGA-II القوي هذا بتقييم كل حل مرشح ليس فقط عند نقطة تصميمه ولكن عبر منطقة مجاورة أو عينة من السيناريوهات غير المؤكدة، ثم يتعامل مع القيمة المتوقعة والتباين (أو الأداء في أسوأ الحالات) لكل هدف كمعايير للاختيار. وبالتالي، توازن الخوارزمية بين خسارة صغيرة في الأداء الاسمي ومكسب كبير في الموثوقية، مما يوفر جبهة باريتو من الحلول التنافسية والمستقرة في ظل عدم اليقين.
التاريخ
نشأ NSGA-II القوي من إطار التحسين متعدد الأهداف القوي الذي صاغه Deb و Gupta في عام 2006، والذين أدخلوا مقاييس متانة صريحة في آلية اختيار NSGA-II. تم نشر خوارزمية NSGA-II الأساسية بواسطة Deb و Pratap و Agarwal و Meyarivan في عام 2002. وقد وسعت الأعمال اللاحقة للباحثين في التصميم الهندسي، وبحوث العمليات، وأنظمة الطاقة الإطار ليشمل المشاكل ذات القيود العشوائية، وأنواع عدم اليقين المختلطة، وتقييم المتانة المدعوم بالبدائل.
متى تُستخدم
استخدم NSGA-II القوي عندما تتضمن مشكلة متعددة الأهداف معلمات غير مؤكدة (خصائص المواد، الطلب، التكاليف، الظروف البيئية) ويجب أن تظل الحلول مقبولة عبر انحرافات معقولة عن القيم الاسمية، وليس فقط عند نقطة تصميم واحدة. إنه مناسب للتصميم الهندسي، وتخطيط سلسلة التوريد في ظل عدم اليقين في الطلب، وتحسين أنظمة الطاقة مع التوليد العشوائي. تجنبه عندما تكون الميزانيات الحسابية ضيقة جدًا، لأن تقييم M عينة عدم يقين لكل فرد لكل جيل يضاعف تكاليف تقييم الدالة بمقدار M. تجنبه أيضًا عندما تكون حالات عدم اليقين ضئيلة نسبيًا مقارنةً بتغير الهدف، أو عندما يكون تقييم دالتين أو ثلاث دوال هدف فقط لكل مرشح ممكنًا — في هذه الحالة يكون NSGA-II القياسي أو الطرق المدعومة بالبدائل أكثر كفاءة.
الحدود والاعتبارات
- تتزايد التكلفة الحسابية مع M (عينات عدم اليقين لكل تقييم)، مما يجعلها مكلفة عندما تكون تقييمات الهدف قائمة على المحاكاة أو تستغرق وقتًا طويلاً.
- يؤثر اختيار مقياس المتانة (المتوسط، التباين، أسوأ الحالات) بشكل كبير على الحلول المفضلة، ولا يوجد خيار صحيح عالميًا.
- يتدهور الأداء لأكثر من ثلاثة أهداف لنفس السبب الذي يتدهور به NSGA-II القياسي — تفقد مسافة الازدحام قوتها التمييزية في فضاء الأهداف عالي الأبعاد.
- يتطلب تقدير المتانة بشكل موثوق M كبيرًا بما فيه الكفاية، ولكن M الصغير يدخل ضوضاء عشوائية يمكن أن تضلل تقريب جبهة باريتو.
- ليس من السهل تطبيقه عندما تكون مجموعة عدم اليقين غير متصلة أو عندما تكون الارتباطات بين المعلمات غير المؤكدة معقدة ويصعب أخذ عينات منها.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- ينتج حلول باريتو المثلى التي تم التحقق منها صراحةً لأداء جيد في ظل عدم اليقين، مما يقلل من مخاطر الحلول التي تتدهور بشكل سيء في الممارسة.
- يرث NSGA-II القوي الفرز السريع غير المهيمن والنخبوية من NSGA-II، مما يضمن عدم التخلص من الحلول غير المهيمنة بقوة عبر الأجيال.
- مرونة في مقياس المتانة: يمكن استبدال القيمة المتوقعة، أو عقوبة التباين، أو أسوأ الحالات، أو القيد الاحتمالي اعتمادًا على تفضيل المخاطر.
- يعمل لكل من مساحات القرار المستمرة والمنفصلة دون تعديل لآلية الاختيار الأساسية.
- يوفر لصناع القرار مجموعة من خيارات المقايضة التي تختلف في كل من التوازن متعدد الأهداف ومستوى المتانة، مما يدعم التعبير المستنير عن التفضيلات.
التطبيقات
- تصميم ديناميكي هوائي قوي يحسن المقايضات بين السحب والرفع في ظل الظروف الجوية المتغيرة
- تصميم شبكة سلسلة التوريد يوازن بين التكلفة ومستوى الخدمة في ظل الطلب العشوائي للعملاء
- تخطيط نظام طاقة قوي مع توليد متجدد غير مؤكد وملفات تعريف الحمل
- تحسين هيكلي متعدد الأهداف يأخذ في الاعتبار تفاوتات التصنيع وتقلب الحمل
- تحسين المحفظة في ظل عدم اليقين في السوق مع مقايضات بين العائد المتوقع والتباين
- إدارة الموارد المائية تحسن التخصيص والموثوقية في ظل سيناريوهات التدفق غير المؤكدة مناخيًا
كيف يعمل
كيف يعمل
قم بإنشاء مجموعة أولية P من N حلول مرشحة ترمّز متجهات متغيرات القرار. حدد نموذج عدم اليقين: حدد المعلمات غير المؤكدة، وتوزيعاتها الاحتمالية أو مجموعات الاضطراب، ومقياس المتانة المراد استخدامه (القيمة المتوقعة، التباين، أسوأ الحالات، أو مزيج مرجح). قم بتقييم جميع الحلول في ظل الظروف الاسمية لتحديد اللياقة الأساسية.
لكل حل مرشح x في المجموعة، اسحب M تحقيقًا لعدم اليقين من توزيعات المعلمات المحددة (أو عدد منطقة مجاورة منظمة). قم بتقييم جميع الدوال الهدف في ظل كل تحقيق وجمع النتائج في تقديرات هدف قوية. التجميع الشائع: استخدم المتوسط كتقدير للمتانة للأداء المتوقع وأضف عقوبة تتناسب مع الانحراف المعياري لمراعاة التباين، بحيث يصبح الهدف القوي f_robust(x) = mean[f(x, xi)] + lambda * std[f(x, xi)].
طبق الفرز السريع غير المهيمن على المجموعة باستخدام تقديرات الهدف القوية بدلاً من القيم الاسمية. عيّن كل حل إلى جبهة غير مهيمنة F1، F2، إلخ. بناءً على هيمنة باريتو للأهداف القوية. الحلول في F1 غير مهيمنة بقوة: لا يوجد حل آخر أفضل في جميع الأهداف القوية في وقت واحد.
ضمن كل جبهة غير مهيمنة، احسب مسافة الازدحام لكل حل على طول كل محور هدف قوي. تحدد مسافة الازدحام مدى عزلة الحل في فضاء الهدف القوي، مما يعزز الانتشار عبر جبهة باريتو القوية. الحلول ذات مسافة الازدحام الكبيرة تشغل مناطق قليلة الكثافة ويتم تفضيلها أثناء الاختيار للحفاظ على التنوع.
طبق اختيار البطولة الثنائي باستخدام عامل المقارنة المزدحم على الجبهات القوية ومسافات الازدحام. أنشئ مجموعة ذرية Q بحجم N عبر عوامل التزاوج (التزاوج الثنائي المحاكى) والطفرة (الطفرة متعددة الحدود). أعد تقييم حلول الذرية باستخدام تقييم المتانة مع M عينة عدم يقين لكل فرد. تهيمن هذه الخطوة على وقت التشغيل عندما تكون M كبيرة.
ادمج المجموعة الأصلية P والذرية Q في مجموعة مجمعة من 2N حلول. أعد الفرز حسب عدم الهيمنة القوية ومسافة الازدحام. اختر أفضل N فرد لتشكيل الجيل التالي، مع الحفاظ على النخبوية. توقف عندما يتم الوصول إلى الحد الأقصى للجيل، أو يتوقف الحجم الفائق، أو يتم استنفاد الميزانية الحسابية. أعد جبهة باريتو القوية النهائية F1.
الأخطاء الشائعة
- يؤدي استخدام عدد قليل جدًا من عينات عدم اليقين لكل تقييم (M أقل من 20-30) إلى إدخال ضوضاء تقييم تشوه ترتيب عدم الهيمنة وتنتج جبهة باريتو قوية غير موثوقة.
- الخلط بين متانة قيم الهدف ومتانة الحلول المثلى: قد يتطلب الحل القوي في فضاء الهدف قيمًا دقيقة لمتغيرات القرار يصعب تنفيذها.
- تطبيق مسافة الازدحام الافتراضية لـ NSGA-II في فضاء الهدف القوي دون التحقق مما إذا كانت الأهداف القوية على مقاييس متناسبة؛ قم بتطبيع الأهداف قبل حساب المسافات.
- تشغيل تكرار واحد والتعامل مع النتيجة على أنها نهائية؛ قم دائمًا بتشغيل تكرارات مستقلة متعددة وقم بالإبلاغ عن إحصائيات الحجم الفائق لمراعاة التباين العشوائي.
- اختيار lambda (وزن عقوبة التباين) بشكل عشوائي دون تحليل الحساسية؛ يرمز lambda المختار ضمنيًا إلى موقف مخاطر يجب أن يكون واضحًا ومبررًا.
الأسئلة الشائعة
كيف يختلف NSGA-II القوي عن NSGA-II القياسي؟
يقوم NSGA-II القياسي بتقييم كل حل مرشح عند قيمه البارامترية الاسمية ويستخدم قيم الهدف هذه لهيمنة باريتو. بينما يقوم NSGA-II القوي بتقييم كل حل عبر M تحقيقًا للمعلمات غير المؤكدة، ويجمع النتائج في تقديرات هدف قوية (مثل المتوسط والتباين)، ويستخدم هذه التقديرات لترتيب الهيمنة. يزيد هذا من التكلفة الحسابية بعامل M ولكنه ينتج حلولًا تظل تنافسية عندما تنحرف المعلمات عن القيم الاسمية.
كم عدد عينات عدم اليقين M التي يجب أن أستخدمها لكل فرد؟
لا توجد قاعدة عالمية. نقطة البداية الشائعة هي M = 30 إلى 50 عينة مونت كارلو إذا كانت تقييمات الهدف رخيصة. بالنسبة للتقييمات المكلفة، قد يكون M = 5 إلى 10 ضروريًا. قم بإجراء دراسة حساسية: زد M حتى تستقر تقديرات الهدف القوية. يحقق أخذ العينات شبه العشوائي (مكعب لاتيني أو سوبول) تغطية أفضل من أخذ العينات العشوائي البحت لنفس M.
هل يمكنني استخدام NSGA-II القوي مع أكثر من ثلاثة أهداف؟
يمكن تطبيق الخوارزمية، لكن الأداء يتدهور لنفس السبب الذي يتدهور به NSGA-II القياسي: تفقد مسافة الازدحام قوتها التمييزية في فضاء الأهداف عالي الأبعاد، وينتهي المطاف بمعظم الحلول على الجبهة الأولى غير المهيمنة. لأربعة أهداف أو أكثر، فكر في نسخة قوية من NSGA-III، والتي تستخدم اختيارًا قائمًا على نقطة مرجعية بدلاً من مسافة الازدحام.
ما هو مقياس المتانة الذي يجب أن أختاره؟
يعتمد الاختيار على موقف المخاطرة. يستهدف التحسين القائم على المتوسط فقط الأداء المتوقع دون معاقبة التقلبات — وهو مناسب للقرارات المتكررة. يعاقب المتوسط بالإضافة إلى التباين عدم الاستقرار ويناسب السياقات التي تتجنب المخاطر. التحسين في أسوأ الحالات (minimax) محافظ للغاية ومناسب فقط عندما يكون تحقيق كارثي واحد غير مقبول. وثق وبرر الاختيار، لأنه يؤثر بشكل كبير على الحلول التي تظهر على جبهة باريتو القوية.
كيف أتحقق من أن الحلول المعادة قوية حقًا؟
بعد انتهاء الخوارزمية، أعد تقييم كل حل من حلول جبهة باريتو بمجموعة جديدة وكبيرة من عينات عدم اليقين (على سبيل المثال، M = 1000) مستقلة عن العينات المستخدمة أثناء التحسين. تحقق مما إذا كانت متوسطات الأهداف وتبايناتها تتطابق مع التقديرات من التشغيل التطوري. تشير التناقضات الكبيرة إلى أن M كان صغيرًا جدًا أثناء التحسين، أو أن نموذج عدم اليقين كان محددًا بشكل خاطئ.
طرق ذات صلة
المصادر
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
افتح مرجع DOIتم النسخ.Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463-494.
افتح مرجع DOIتم النسخ.