خوارزمية التصنيف غير المهيمن ثنائية الترتيب الثانية (NSGA-II)
- السنة
- 2002
- النوع
- Evolutionary multi-objective optimisation algorithm
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تُعد خوارزمية التصنيف غير المهيمن ثنائية الترتيب الثانية (NSGA-II) الخوارزمية المرجعية القياسية للتحسين التطوري متعدد الأهداف، والتي قدمها ديب وبراتاب وأغاروال ومياريفان في عام 2002. بدلاً من دمج أهداف متعددة متعارضة في درجة واحدة، تقوم بتطوير مجموعة من الحلول المرشحة عبر الأجيال وتعيد مجموعة من الحلول المثلى للمقايضة - جبهة باريتو - باستخدام التصنيف السريع غير المهيمن ومقياس المسافة المزدحمة للحفاظ على التنوع.
الفكرة الحدسية وراء الطريقة
تخيل أنك تريد تصميم منتج يكون في الوقت نفسه رخيصًا ومتينًا قدر الإمكان. الرخص عادة ما يعني متانة أقل، لذلك لا يوجد حل واحد مثالي - بل هناك عائلة من الحلول الوسط المعقولة. تعمل خوارزمية NSGA-II مثل مجموعة من التصميمات المتنافسة: في كل جيل، يتم القضاء على التصميمات الأضعف التي تهيمن عليها تصميمات أخرى في كل هدف، ويتم نشر الناجين لتغطية النطاق الكامل للمقايضات بدلاً من التكتل حول زاوية واحدة. بعد عدد كافٍ من الأجيال، تترك بقائمة غنية من الخيارات - جبهة باريتو - تختار منها التوازن الذي يناسب أولوياتك.
التاريخ
نُشرت خوارزمية NSGA-II بواسطة كاليانموي ديب وزملائه في المعهد الهندي للتكنولوجيا في كانبور عام 2002 كخليفة مصحح ومحسن بشكل كبير لـ NSGA الأصلية (Srinivas & Deb, 1994). كانت الابتكارات الرئيسية هي إجراء تصنيف سريع غير مهيمن بتعقيد O(MN²)، وعامل مسافة مزدحمة صريح للحفاظ على تنوع الحلول دون معلمة مشاركة، وآلية اختيار نخبوية. أصبحت ورقة IEEE Transactions on Evolutionary Computation لعام 2002 واحدة من أكثر الأعمال استشهادًا في الحوسبة التطورية وأرست NSGA-II كمعيار فعلي للخوارزميات التطورية متعددة الأهداف. امتدت الإصدارات اللاحقة - NSGA-III (2014) وغيرها - الإطار إلى مشاكل متعددة الأهداف.
متى تُستخدم
تنطبق خوارزمية NSGA-II كلما كانت المشكلة تحتوي على دالتين أو أكثر من دوال الهدف المتعارضة التي لا يمكن دمجها في معيار واحد دون فقدان للمعلومات. يمكن أن تكون متغيرات القرار مستمرة أو ثنائية أو فئوية، ولا يلزم وجود افتراضات توزيعية على مشهد الأهداف. تناسب الخوارزمية التصميم الهندسي، وتخصيص الموارد، والجدولة، ومشاكل المحافظ حيث تكون مجموعة من الحلول الوسط أكثر فائدة من حل أمثل واحد. يلزم عدد كافٍ من الأجيال (عادة عدة مئات أو أكثر) لتحقيق تغطية جيدة للجبهة؛ يعد تشغيل عدد قليل جدًا من الأجيال هو وضع الفشل الرئيسي.
الحدود والاعتبارات
- يتدهور الأداء مع زيادة عدد الأهداف عن ثلاثة أو أربعة - تصبح المسافة المزدحمة مقياسًا ضعيفًا للتنوع في الأبعاد العالية.
- يتطلب ضبطًا دقيقًا لحجم المجموعة وعدد الأجيال؛ عدد قليل جدًا من الأجيال يمنع تغطية الجبهة الكافية.
- يجعل تقييم دوال الهدف التي تتضمن عمليات محاكاة مكلفة الخوارزمية مكلفة حسابيًا.
- النتائج عشوائية: يمكن أن تؤدي بذور عشوائية مختلفة إلى جبهات باريتو مختلفة، لذا يوصى بتشغيلات متعددة ومقارنة إحصائية (مثل الحجم الفائق).
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تنتج مجموعة متنوعة من الحلول المثلى للمقايضة في تشغيل واحد، مما يتجنب الحاجة إلى تكرار التحسين بأوزان مختلفة.
- يعمل التصنيف السريع غير المهيمن في وقت O(MN²) (M أهداف، N حجم المجموعة)، مما يجعله قابلاً للتطبيق للأحجام المعتدلة للمشكلات.
- يضمن الاختيار النخبوية عدم التخلص من الحلول الجيدة التي تم العثور عليها مبكرًا.
- قابلة للتطبيق على متغيرات القرار المستمرة والثنائية والفئوية دون افتراضات توزيعية.
- تم التحقق منها على نطاق واسع عبر مجالات الهندسة وبحوث العمليات والعلوم الحاسوبية.
التطبيقات
- التصميم الهندسي: تقليل الوزن وزيادة القوة الهيكلية في المكونات الميكانيكية في وقت واحد.
- الأنظمة البيئية والطاقة: موازنة التكلفة والانبعاثات والموثوقية في تخطيط شبكات الطاقة أو الطاقة المتجددة.
- الرعاية الصحية وبحوث العمليات: الجدولة التي تحسن وقت انتظار المريض واستخدام الموارد والتكلفة في وقت واحد.
- تحسين المحافظ في التمويل واختيار المشاريع في الأعمال: المقايضة بين العائد والمخاطر والسيولة.
- ضبط المعلمات الفائقة في التعلم الآلي: تحسين الدقة مقابل تعقيد النموذج أو وقت الاستدلال.
كيف يعمل
كيف يعمل
يتم إنشاء مجموعة من الحلول المرشحة عن طريق أخذ عينات عشوائية من متغيرات القرار (أو عن طريق التصميم) ضمن حدودها. يتم تعيين حجم المجموعة ليكون كبيرًا بما يكفي لضمان التنوع عبر مساحة الأهداف منذ البداية.
يتم فك تشفير كل حل مرشح إلى قيم متغيرات القرار وتقييم كل دالة هدف. تكون النتيجة متجهًا من درجات الأهداف لكل فرد. غالبًا ما تكون هذه الخطوة هي عنق الزجاجة الحسابي عندما تتضمن الأهداف عمليات محاكاة أو نماذج مكلفة.
يتم ترتيب الحلول عن طريق التصنيف غير المهيمن: يحتوي الجبهة الأولى على جميع الحلول التي لا يهيمن عليها أي حل آخر في كل هدف؛ يحتوي الجبهة الثانية على الحلول التي تهيمن عليها فقط تلك الموجودة في الجبهة الأولى؛ وهكذا. ضمن كل جبهة، يتم حساب درجة المسافة المزدحمة لقياس مدى عزلة الحل عن جيرانه - المسافة المزدحمة الأعلى تعني أن الحل يحتل منطقة أقل ازدحامًا من الجبهة.
تدمج استراتيجية الاختيار النخبوية المجموعة الحالية مع النسل وتحتفظ بأفضل N فردًا، وتملأ الجبهات بالترتيب وتستخدم المسافة المزدحمة لكسر التعادل داخل آخر جبهة مقبولة. هذا يضمن عدم فقدان الحلول الجيدة التي تم العثور عليها في الأجيال السابقة أبدًا.
يتكاثر الأفراد المختارون من خلال العوامل الوراثية - الاختيار الثنائي بالبطولة، والتقاطع الثنائي المحاكى (SBX)، والطفرة متعددة الحدود - مما ينتج عنه مجموعة نسل جديدة. تحافظ هذه العوامل على التنوع الهادف مع استكشاف محيط الحلول الواعدة.
تتكرر خطوات التقييم والتطوير لعدد محدد من الأجيال. يتم الحكم على التقارب عن طريق الفحص البصري لجبهة باريتو أو عن طريق تتبع مؤشر الحجم الفائق. الناتج النهائي هو مجموعة الحلول غير المهيمنة التي تقارب جبهة باريتو الحقيقية.
الأخطاء الشائعة
- عادةً ما يؤدي تشغيل أقل من عدة مئات من الأجيال إلى جبهة باريتو غير مكتملة؛ إذا كانت الميزانية الحسابية ضيقة، ففكر في التحسين أحادي الهدف الموزون بدلاً من ذلك.
- معالجة مشكلة ذات هدف واحد كمشكلة متعددة الأهداف أمر غير ضروري - استخدم محسّنًا أحادي الهدف.
- يؤدي إهمال تعيين حدود معقولة للمتغيرات إلى مجموعات لا تصل أبدًا إلى مناطق مجدية أو ذات معنى في مساحة البحث.
- الإبلاغ عن حل واحد فقط من جبهة باريتو دون الكشف عن الجبهة الكاملة يخفي هيكل المقايضة الذي تم تصميم NSGA-II للكشف عنه.
الأسئلة الشائعة
كم عدد الأجيال التي تحتاجها خوارزمية NSGA-II؟
لا توجد قاعدة عالمية، ولكن تشغيل أقل من بضع مئات من الأجيال ينتج عادةً جبهة باريتو غير مكتملة. النهج العملي هو رسم مؤشر الحجم الفائق عبر الأجيال والتوقف عندما يستقر. إذا كانت الميزانية الحسابية تمنع ذلك، فإن محسّنًا أحادي الهدف موزونًا هو بديل أكثر أمانًا.
ما هي جبهة باريتو؟
جبهة باريتو هي مجموعة الحلول التي لا يمكن فيها تحقيق أي تحسين في هدف واحد دون تدهور هدف واحد على الأقل. تقارب خوارزمية NSGA-II هذه الجبهة، مما يمنحك قائمة كاملة من الحلول الوسط المتوازنة بدلاً من إجابة واحدة.
هل يمكن لـ NSGA-II التعامل مع أكثر من هدفين؟
نعم، ولكن المسافة المزدحمة - آلية التنوع - تصبح أقل فعالية مع تجاوز عدد الأهداف ثلاثة أو أربعة (نظام 'الأهداف المتعددة'). بالنسبة للمشاكل التي تحتوي على خمسة أهداف أو أكثر، يُفضل عمومًا استخدام NSGA-III أو الخوارزميات القائمة على التحلل مثل MOEA/D.
هل خوارزمية NSGA-II حتمية؟
لا. تتضمن العوامل الوراثية والمجموعة الأولية العشوائية، لذلك يمكن أن تؤدي التشغيلات المختلفة ببذور عشوائية مختلفة إلى تقريبات مختلفة لجبهة باريتو. أفضل ممارسة هي تشغيل الخوارزمية عدة مرات ومقارنة جودة الجبهة باستخدام مؤشر الحجم الفائق.
طرق ذات صلة
المصادر
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تم النسخ.Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.
افتح مرجع DOIتم النسخ.