الانتقال إلى المحتوى
العودة إلى نتائج البحث

Stochastic NSGA-II — التحسين التطوري متعدد الأهداف في ظل عدم اليقين

قدّمه
Deb, K. et al. (NSGA-II base); Hughes, E. J. and subsequent researchers for stochastic extensions
السنة
2001–2002
النوع
Evolutionary multi-objective optimization under uncertainty
العائلة
Simulation / optimization

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

يمتد Stochastic NSGA-II ليُعالج الخوارزمية التطورية NSGA-II للتعامل مع دوال الهدف التي تكون مشوشة أو غير مؤكدة أو احتمالية. من خلال حساب المتوسط أو أخذ عينات من الأهداف العشوائية عبر تقييمات متعددة، فإنه يحدد الحلول المثلى لباريتو التي تكون قوية ضد عدم اليقين، مما يجعلها مناسبة لمشاكل تصميم الهندسة، وتحسين سلسلة التوريد، وتحسين السياسات حيث تهم التقلبات الواقعية.

الفكرة الحدسية وراء الطريقة

تُعد NSGA-II واحدة من أكثر الخوارزميات فعالية للعثور على مجموعة متنوعة من حلول المقايضة المثلى لباريتو في المشاكل متعددة الأهداف. ومع ذلك، يفترض الإصدار القياسي تقييمات هدف حتمية. في الممارسة العملية، غالبًا ما تُرجع المحاكاة والتجارب والأنظمة الحقيقية مخرجات مشوشة. يعالج Stochastic NSGA-II هذا عن طريق إعادة أخذ العينات أو التقدير الإحصائي للياقة الحقيقية لكل حل، ثم تطبيق الفرز السريع غير المهيمن وخوارزمية المسافة المزدحمة الخاصة بـ NSGA-II للتنقل في واجهة باريتو بشكل موثوق على الرغم من الضوضاء. تكمن الفكرة الرئيسية في أن ترتيب الحلول حسب الأداء المتوقع - أو حسب احتمالية هيمنتها - يستعيد بنية باريتو الصحيحة حتى عندما تكون التقييمات الفردية غير موثوقة.

التاريخ

تم تقديم NSGA-II بواسطة Deb وآخرون في عام 2002 كخوارزمية جينية سريعة ونخبوية متعددة الأهداف وسرعان ما أصبحت معيارًا قياسيًا. ظهرت امتدادات عشوائية بعد فترة وجيزة، مدفوعة بمجتمعات تحسين الهندسة التي تحتاج إلى التعامل مع ضوضاء المحاكاة. قام Hughes (2001) بتشكيل ترتيب الأهداف المتعددة في ظل عدم اليقين. منذ منتصف العقد الأول من القرن الحادي والعشرين، ظهرت العديد من المتغيرات التي تغطي أخذ العينات التكيفي، واحتمالية الهيمنة، وتحسين الحجم الفائق المتوقع في ظل الضوضاء.

متى تُستخدم

استخدم Stochastic NSGA-II عندما تواجه مشكلة تحسين متعددة الأهداف حيث يتم تقييم الأهداف عبر المحاكاة أو التجربة أو المستشعرات المشوشة وتحتاج إلى حلول تظل جيدة عبر نطاق عدم اليقين - وليس فقط في المتوسط. وهي مناسبة بشكل خاص لتصميم الهندسة في ظل تفاوتات التصنيع، وتحسين سلسلة التوريد مع عدم يقين الطلب، ونماذج البيئة أو السياسات ذات المدخلات العشوائية. لا تستخدمها عندما تكون الأهداف حتمية ورخيصة التقييم (يكفي استخدام NSGA-II القياسي)، وعندما يكون عدد التكرارات اللازمة للتقدير الموثوق يجعل الميزانية الإجمالية غير عملية، أو عندما تكون المشكلة أحادية الهدف (استخدم خوارزميات EA أحادية الهدف العشوائية بدلاً من ذلك). تجنبها عندما يكون توزيع الضوضاء غير مستقر للغاية أو منظم بطرق تنتهك افتراض أخذ العينات المستقلة والمتطابقة التوزيع (i.i.d.).

الحدود والاعتبارات

  • تتزايد التكلفة الحسابية مع عدد التكرارات r لكل تقييم، مضروبة في حجم المجموعة والأجيال - يمكن أن تصبح باهظة الثمن للمحاكاة المكلفة.
  • اختيار العدد الصحيح من التكرارات r أمر غير تافه: القليل جدًا يؤدي إلى أخطاء في الترتيب، والكثير جدًا يهدر الميزانية.
  • لا توجد ضمانات تقارب رسمية لواجهة باريتو العشوائية الحقيقية؛ تعتمد الجودة على الميزانية ومستوى الضوضاء.
  • تتجاهل مقارنات الهيمنة باستخدام المتوسطات المقدرة عدم اليقين في التقدير، مما قد يسبب خطأ في الترتيب في ظل الضوضاء العالية.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • ترث قدرة NSGA-II القوية على اكتشاف واجهة باريتو والحفاظ على التنوع من خلال الفرز غير المهيمن والمسافة المزدحمة.
  • تأخذ في الاعتبار بشكل صريح ضوضاء دالة الهدف، مما ينتج عنه حلول قوية وموثوقة في التطبيق الواقعي.
  • إطار عمل مرن - يمكن أن يستخدم التقدير العشوائي المتوسط، أو المتانة المستندة إلى الكميات، أو احتمالية الهيمنة دون تغيير الخوارزمية الأساسية.
  • قابلة للتطبيق على نماذج المحاكاة الصندوق الأسود حيث تكون معلومات التدرج غير متاحة.
  • تنتج واجهة باريتو كاملة بدلاً من حل واحد، مما يمنح صانعي القرار خيارات مقايضة واضحة.

التطبيقات

  • التصميم الهندسي القوي: تحسين المكونات الهيكلية أو الميكانيكية في ظل تفاوتات التصنيع وتقلبات الأحمال.
  • تصميم شبكة سلسلة التوريد: تقليل التكلفة ووقت التسليم عندما تكون كميات الطلب والإمداد عشوائية.
  • نمذجة السياسات البيئية: إيجاد استراتيجيات مثلى لباريتو لخفض الانبعاثات عندما تحتوي نماذج التأثير المناخي على معلمات غير مؤكدة.
  • تحسين المحفظة: موازنة العائد المتوقع والمخاطر عندما تتبع عوائد الأصول عمليات عشوائية.
  • تخصيص موارد الرعاية الصحية: تحسين التكاليف ونتائج المرضى في ظل معدلات وصول المرضى غير المؤكدة وفعالية العلاج.
  • تخطيط أنظمة الطاقة: تحديد حجم تركيبات الطاقة المتجددة في ظل ملفات تعريف توليد الرياح والطاقة الشمسية العشوائية.

كيف يعمل

كيف يعمل

1

تحديد مشكلة التحسين متعدد الأهداف مع k دوال هدف عشوائية f_1(x,xi)، ...، f_k(x,xi)، حيث تمثل xi المعلمات العشوائية المسحوبة من توزيع معروف أو مقدر. تحديد حدود متغيرات القرار، والقيود، وعدد التقييمات المتكررة (التكرارات) r المستخدمة لتقدير القيمة المتوقعة لكل هدف.

2

تهيئة مجموعة من N حلول مرشحة عشوائيًا ضمن فضاء القرار الممكن. لكل فرد، قم بتخصيص متجه تقدير للياقة بطول k، تم تهيئته إلى الصفر. قم بتعيين عداد الأجيال g = 0 وتحديد معايير التوقف (الحد الأقصى للأجيال G_max أو تحمل التقارب).

3

لكل فرد x_i في المجموعة، قم بتقييم كل هدف f_j(x_i, xi) بالضبط r مرة عن طريق أخذ عينات xi من توزيعه (أو تشغيل r تكرار للمحاكاة). قم بتقدير الهدف الحقيقي كمتوسط العينة: f_j_hat(x_i) = (1/r) * sum_{l=1}^{r} f_j(x_i, xi_l). اختياريًا، قم بحساب الأخطاء المعيارية لإعلام استراتيجيات أخذ العينات التكيفية.

4

تطبيق الفرز السريع غير المهيمن على متجهات الأهداف المقدرة. الحل x_a يهيمن على x_b إذا كان f_j_hat(x_a) <= f_j_hat(x_b) لجميع j وأقل بشكل صارم لواحد على الأقل j. قم بتعيين كل حل إلى رتبة واجهة باريتو F_1، F_2، ... حيث تحتوي F_1 على الحلول غير المهيمنة من قبل أي حل آخر.

5

اختيار الآباء باستخدام اختيار البطولة الثنائية بناءً على رتبة باريتو والمسافة المزدحمة (للحفاظ على التنوع). تطبيق العوامل الوراثية - التقاطع الثنائي المحاكى (SBX) والطفرة متعددة الحدود - لتوليد مجموعة من النسل Q بحجم N. دمج مجموعتي الآباء والنسل (حجم 2N)، وإعادة تقييم الأهداف العشوائية، وإعادة الفرز، واختيار أفضل N حلول حسب الرتبة ثم المسافة المزدحمة.

6

زيادة g. إذا كان g < G_max ولم تستقر واجهة باريتو، كرر من خطوة التقييم العشوائي. بخلاف ذلك، قم بإرجاع واجهة باريتو النهائية F_1 كمجموعة من الحلول القوية غير المهيمنة. قم بالإبلاغ عن واجهة باريتو التقريبية في فضاء الهدف لاختيار صانع القرار.

الأخطاء الشائعة

  • استخدام تكرار واحد (r=1) لكل فرد يعامل الضوضاء كإشارة، مما يؤدي إلى واجهات باريتو غير مستقرة للغاية عبر التشغيلات - استخدم دائمًا r >= 3 كحد أدنى وتحقق من التقارب.
  • تجاهل تباين الأهداف العشوائية قد يؤدي إلى اختيار حلول تبدو جيدة في المتوسط ولكنها تؤدي أداءً سيئًا في سيناريوهات الذيل - ضع في اعتبارك صياغات الأهداف الكمية أو أسوأ الحالات عندما تكون مخاطر الذيل مهمة.
  • تطبيق الطريقة دون التحقق مما إذا كانت الضوضاء مستقرة: إذا تغيرت خصائص الضوضاء مع قيم متغير القرار، فإن أخذ العينات التكيفي أو النماذج غير المتجانسة ضرورية.
  • معاملة واجهة باريتو الناتجة كقرار نهائي دون تقييم المتانة خارج العينة - قم دائمًا بالتحقق من الحلول الموصى بها باستخدام تشغيلات محاكاة خارج العينة.

الأسئلة الشائعة

كم عدد التكرارات r التي يجب أن أستخدمها لكل تقييم فردي؟

نقطة انطلاق شائعة هي r = 5-30، اعتمادًا على معامل الاختلاف للهدف. استراتيجيات التكيف التي تخصص المزيد من التكرارات للحلول النخبوية أو تستخدم أخذ العينات المتسلسل حتى يتم تلبية معيار الثقة تكون أكثر كفاءة. بالنسبة للمحاكاة المكلفة، غالبًا ما يكون r = 3-5 مع مجموعة كبيرة حلاً وسطًا عمليًا.

كيف يختلف Stochastic NSGA-II عن NSGA-II القياسي؟

الاختلاف الهيكلي الوحيد هو في تقييم الهدف: يقوم NSGA-II القياسي بتقييم f(x) مرة واحدة ويفترض أن النتيجة دقيقة، بينما يقوم Stochastic NSGA-II بتقييم f(x, xi) r مرة ويستخدم متوسط العينة (أو إحصائية متانة أخرى) كهدف فعال. تظل جميع آليات الفرز والاختيار والعوامل الوراثية متطابقة.

هل يمكنني استخدام Stochastic NSGA-II مع احتمالية الهيمنة بدلاً من الأهداف المتوسطة؟

نعم. تستبدل أساليب احتمالية الهيمنة مقارنات الهيمنة الحتمية باحتمالات الهيمنة العشوائية، وهو أمر أكثر مبدأً في ظل الضوضاء العالية. يتطلب هذا عينات أكثر لكل مقارنة ولكنه ينتج ترتيبات أكثر موثوقية عندما تكون الضوضاء كبيرة مقارنة بفروق الأهداف.

ماذا لو كانت محاكاتي مكلفة للغاية بالنسبة للتكرارات المتعددة؟

ضع في اعتبارك أساليب مساعدة بديلة: قم ببناء نموذج رياضي (metamodel) باستخدام عملية غاوسية أو شبكة عصبية لدالة الهدف، واستخدمه لتقدير المتوسط والتباين بتكلفة زهيدة، وطبق معايير التحسين المتوقع أو احتمالية التحسين بدلاً من التقييمات المباشرة المتكررة.

هل يضمن Stochastic NSGA-II العثور على واجهة باريتو العشوائية الحقيقية؟

لا. مثل جميع الخوارزميات التطورية، فهي طريقة استدلالية لا تضمن التقارب في وقت محدود إلى الواجهة الحقيقية. إرشادات عملية: قم بإجراء تجارب مستقلة متعددة، وقارن الواجهات الناتجة باستخدام مؤشرات الحجم الفائق، وزد حجم المجموعة أو عدد الأجيال إذا اختلفت الواجهات بشكل كبير عبر التشغيلات.

طرق ذات صلة

المصادر

  1. 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
    تم النسخ.
  2. Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001), Lecture Notes in Computer Science, vol. 1993, pp. 329–343. Springer.

    افتح مرجع DOI
    تم النسخ.