التحسين التطوري متعدد الأهداف الموجه بالمحاكاة NSGA-II المعتمد على الوكيل
- قدّمه
- Deb et al. (NSGA-II, 2002); integrated with agent-based modeling frameworks in the 2000s–2010s
- السنة
- 2000s–2010s
- النوع
- Simulation-embedded evolutionary multi-objective optimizer
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
يُضمِّن خوارزمية NSGA-II التطورية داخل حلقة محاكاة معتمدة على الوكيل بحيث يتم تحديد القيم الهدفية لكل حل مرشح عن طريق تشغيل محاكاة وكيل كاملة بدلاً من تقييم دالة مغلقة الشكل. يُمكِّن هذا الاقتران من التحسين متعدد الأهداف للأنظمة التي تنشأ أدائها من التفاعلات على المستوى الجزئي للوكلاء المستقلين بدلاً من المعادلات القابلة للمعالجة تحليليًا.
الفكرة الحدسية وراء الطريقة
تستعلم NSGA-II القياسية عن صيغة رياضية لتقييم كل حل بناءً على أهداف متعددة. عندما يكون سلوك النظام معقدًا جدًا أو ناشئًا بحيث لا يمكن التعبير عنه بصيغة - فكر في الأوبئة أو شبكات المرور أو سلاسل التوريد ذات الجهات الفاعلة المتكيفة - فإنك تستبدل هذه الصيغة بمحاكاة معتمدة على الوكيل. يشفّر كل حل مرشح معلمات السياسة أو قواعد الوكيل؛ يتم تشغيل المحاكاة إلى الأمام، ويتم قياس النتائج المجمعة كقيم هدفية، ثم تبني عملية الفرز غير المهيمنة واختيار المسافة المزدحمة الخاصة بـ NSGA-II واجهة باريتو متنوعة من حلول المقايضة. النتيجة هي مجموعة من تكوينات المعلمات التي تكون فعالة بشكل باريتو بشكل متزامن عبر جميع الأهداف المسماة، حتى عندما تنشأ هذه الأهداف من ديناميكيات تكيفية معقدة.
التاريخ
تم تقديم NSGA-II بواسطة كاليانموي ديب وزملائه في IIT كانبور في عام 2002 كخوارزمية جينية سريعة ونخبوية متعددة الأهداف، وسرعان ما أصبحت واحدة من أكثر الخوارزميات استشهادًا في الحوسبة التطورية. نما النمذجة المعتمدة على الوكيل كنموذج حسابي خلال التسعينيات بمنصات مثل Swarm و NetLogo و Repast. ظهر اقتران NSGA-II مع عمليات المحاكاة المعتمدة على الوكيل في العقدين الأول والثاني من القرن الحادي والعشرين حيث سعى الباحثون في التخطيط الحضري وعلم البيئة وعلم الأوبئة وإدارة سلسلة التوريد إلى تحسين السياسات في الأنظمة المعقدة للغاية بالنسبة للصياغة التحليلية.
متى تُستخدم
استخدم NSGA-II المعتمد على الوكيل عندما يجب تحسين هدفين أو أكثر متعارضين في وقت واحد وتنشأ هذه الأهداف من تفاعلات الوكيل بدلاً من الدوال المغلقة الشكل - على سبيل المثال، موازنة تكلفة احتواء الوباء والنشاط الاقتصادي في نموذج سكاني، أو تقليل تكلفة سلسلة التوريد مع زيادة متانة شبكة من الموردين المتكيفين. إنه مناسب عندما تكون العشوائية متأصلة في النظام ويجب حساب متوسطها عبر التكرارات. لا تستخدمه عندما تكون هناك دالة هدف تحليلية سريعة (NSGA-II العادي كافٍ وأرخص بكثير)، أو عندما يكون هدف واحد فقط ذا صلة، أو عندما تكون المحاكاة المعتمدة على الوكيل باهظة الثمن للغاية لكل تشغيل بحيث تجعل حتى مجموعة صغيرة من الأفراد التكلفة الحسابية الإجمالية غير ممكنة، أو عندما تكون هناك حاجة إلى أكثر من ثلاثة أو أربعة أهداف (فضل متغيرات NSGA-III أو MOEA/D بدلاً من ذلك).
الحدود والاعتبارات
- مكلف حسابيًا للغاية: يتطلب كل جيل N × R تشغيل محاكاة، حيث قد يكون R تكرارًا لكل فرد كبيرًا؛ يمكن أن يكون وقت الساعة الإجمالي باهظًا.
- يتدهور الأداء مع وجود أكثر من ثلاثة أو أربعة أهداف، لأن الفرز غير المهيمن يفقد قوة التمييز وتصبح المسافة المزدحمة غير موثوقة في فضاء الأهداف عالي الأبعاد.
- تعتمد النتائج على دقة نموذج المحاكاة؛ قواعد الوكيل غير الواقعية أو المعلمات غير المعايرة بشكل جيد تنتج واجهات باريتو مضللة بغض النظر عن جودة التحسين.
- يمكن أن تفسد العشوائية في تقييم لياقة المحاكاة مقارنات الهيمنة إذا كان عدد التكرارات R صغيرًا جدًا، مما يؤدي إلى ترتيب باريتو غير صحيح.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يتعامل مع مناظر الأهداف الناشئة، والتابعة للمسار، والعشوائية التي لا يمكن التعبير عنها تحليليًا، مما يجعله قابلاً للتطبيق على الأنظمة التكيفية المعقدة.
- ينتج واجهة باريتو كاملة في تشغيل تحسين واحد، مما يمنح صانعي القرار رؤية واضحة للمقايضات دون الحاجة إلى أوزان تفضيل مسبقة.
- تضمن آلية النخبوية في NSGA-II عدم التخلص من الحلول غير المهيمنة عالية الجودة عبر الأجيال.
- يسمح حساب متوسط التكرارات داخل كل تقييم لياقة بدنية للطريقة بالتعامل مع ضوضاء المحاكاة العشوائية بطريقة مبدئية.
- متوافق مع أي منصة محاكاة معتمدة على الوكيل (NetLogo، Repast، AnyLogic، Mesa) من خلال واجهة تغليف موحدة.
التطبيقات
- تصميم التدخلات الوبائية: إيجاد مجموعات باريتو المثلى من تغطية التطعيم وقيود الحركة التي تقلل بشكل مشترك من عبء العدوى والتكلفة الاقتصادية في نموذج وكيل سكاني.
- التخطيط الحضري لاستخدام الأراضي والنقل: تحسين معلمات تقسيم المناطق والاستثمار في البنية التحتية التي تنشأ كازدحام وانبعاثات ونتائج إنصاف من تفاعلات الوكيل للمقيمين والمركبات.
- تصميم شبكة سلسلة التوريد: تحديد تكوينات السياسة التي توازن بين التكلفة ووقت التسليم ومرونة الاضطراب عبر شبكات من الوكلاء الموردين والموزعين المتكيفين.
- إدارة الحصاد البيئي: تحسين قواعد الحصاد لزيادة الإنتاج الاقتصادي إلى أقصى حد مع الحفاظ على التنوع البيولوجي في نموذج نظام بيئي معتمد على الوكيل.
- التحكم في الشبكات الصغيرة للطاقة: المشاركة في تحسين استراتيجيات عروض أسعار وكلاء المستهلكين لتقليل تكلفة الشبكة وانبعاثات الكربون في ظل توليد متجدد عشوائي.
- تحليل سياسات عدم المساواة الاجتماعية: إيجاد مجموعات معلمات التدخل التي تحسن بشكل مشترك إنصاف الدخل وكفاءة سوق العمل في نماذج اقتصادية معتمدة على الوكيل.
كيف يعمل
كيف يعمل
حدد متغيرات القرار (معلمات سلوك الوكيل، أو رافعات السياسة، أو تخصيص الموارد) وأحصِ الأهداف المتعارضة للتحسين (مثل، تقليل التكلفة وزيادة معدل الخدمة). قم ببناء أو معايرة نموذج محاكاة معتمد على الوكيل يقبل متجه متغيرات القرار ويعيد قياسات الأهداف في نهاية كل تشغيل محاكاة. حدد القيود، ومدة المحاكاة، وعدد التكرارات العشوائية لكل تقييم.
قم بتهيئة مجموعة من N متجه حلول مرشحة عن طريق أخذ عينات من فضاء القرار بشكل موحد عشوائيًا أو عبر أخذ عينات من لاتين هايبركيوب. يمثل كل فرد تكوينًا واحدًا لمعلمات الوكيل أو إعدادات السياسة. قم بتعيين المعلمات الفائقة لـ NSGA-II: حجم المجموعة N، احتمالية التقاطع، معدل الطفرة، والحد الأقصى لعدد الأجيال.
لكل فرد في المجموعة الحالية، قم بتشغيل المحاكاة المعتمدة على الوكيل R مرات (تكرارات) وقم بحساب متوسط القيم الهدفية الناتجة لتقليل الضوضاء العشوائية. سجل متوسط المتجه الهدف لكل فرد. تهيمن هذه الخطوة على التكلفة الحسابية: N فرد مضروبًا في R تكرارات مضروبًا في T خطوات زمنية للمحاكاة لكل تقييم.
طبق الفرز السريع غير المهيمن لترتيب جميع الأفراد في واجهات باريتو F1، F2، .... الواجهة F1 تحتوي على الحلول غير المهيمنة من قبل أي حل آخر؛ الواجهة F2 تحتوي على تلك المهيمنة فقط من قبل أعضاء F1، وهكذا. داخل كل واجهة، قم بحساب المسافة المزدحمة - مجموع فجوات الجيران المعيارية على طول كل محور هدف - لقياس مدى عزلة كل حل والحفاظ على التنوع عبر الواجهة.
اختر الآباء عبر المنافسة الثنائية باستخدام عامل المقارنة المزدحم: فضل الفرد في واجهة ذات رقم أقل، مع كسر التعادل لصالح مسافة مزدحمة أكبر. طبق التقاطع الثنائي المحاكى (SBX) والطفرة متعددة الحدود لإنتاج N نسل. ادمج الآباء والنسل في مجمع من 2N فرد، وأعد الفرز، واحتفظ بأفضل N فرد للجيل التالي باستخدام ترتيب الواجهة والمسافة المزدحمة كفاصل للتعادل.
بعد الوصول إلى معيار التوقف (استنفاد ميزانية الجيل أو تأكيد تقارب الحجم الفائق)، أعد الواجهة F1 للمجموعة النهائية كمجموعة باريتو المثلى التقريبية. قم بتصوير سطح المقايضة في فضاء الأهداف وقم بالإبلاغ عن الحجم الفائق أو المسافة الجينية المعكوسة (IGD) كمقاييس جودة مجمعة عبر عدة تشغيلات مستقلة.
الأخطاء الشائعة
- استخدام عدد قليل جدًا من التكرارات لكل فرد (R = 1 أو 2) عندما تكون المحاكاة عشوائية - تقدير لياقة مشوش يسبب خطأ في تصنيف الحلول في خطوة الفرز المهيمن وتفسد واجهة باريتو.
- تعيين حجم المجموعة N أصغر من تعقيد واجهة باريتو المتوقعة، مما يجبر الخوارزمية على التخلص من مناطق كاملة من فضاء المقايضة وإعادة واجهة مجزأة.
- تطبيق هذه الطريقة على أربعة أهداف أو أكثر دون التبديل إلى NSGA-III أو MOEA/D، مما يتسبب في تجمع معظم الأفراد في الواجهة F1 ويجعل الاختيار عشوائيًا تقريبًا.
- خلط معايرة نموذج الوكيل والتحسين: يجب معايرة المحاكاة على البيانات المرصودة قبل بدء التحسين - تحسين نموذج غير معاير ينتج واجهات باريتو بدون صلاحية في العالم الحقيقي.
- إهمال الحوسبة المتوازية: نظرًا لأن كل تشغيل محاكاة مستقل، فإن NSGA-II المعتمد على الوكيل قابل للتوازي بشكل كبير؛ تشغيله أحادي الخيط يهدر الأجهزة المتاحة ويجعل أوقات التشغيل طويلة بشكل غير ضروري.
الأسئلة الشائعة
كيف يختلف NSGA-II المعتمد على الوكيل عن NSGA-II العادي؟
يقوم NSGA-II العادي بتقييم كل حل عن طريق استدعاء دالة تحليلية، وهو أمر سريع. يستبدل NSGA-II المعتمد على الوكيل استدعاء الدالة هذا بتشغيل محاكاة وكيل كاملة، مما يتيح التحسين على الأهداف الناشئة والتابعة للمسار، ولكن بتكلفة حسابية أعلى بكثير لكل تقييم.
كم عدد التكرارات التي يجب أن أجريها لكل تقييم فردي؟
ما يكفي بحيث ينخفض معامل التباين لكل هدف عبر التكرارات إلى ما دون حوالي 5-10٪. ابدأ بـ R = 10 وزد حتى تستقر تقديرات الأهداف. بالنسبة للنماذج العشوائية للغاية، قد تحتاج إلى R = 30 إلى 50، مما يضاعف التكلفة وفقًا لذلك.
كيف يمكنني جعل NSGA-II المعتمد على الوكيل مجديًا حسابيًا؟
قم بالتوازي عبر نوى وحدة المعالجة المركزية أو مجموعة - تشغيلات محاكاة كل فرد مستقلة وقابلة للتوازي بشكل تافه. استخدم نماذج بديلة (عمليات غاوسية أو شبكات عصبية) لتقريب اللياقة البدنية للفحص المسبق الرخيص، مع الاحتفاظ بتقييمات المحاكاة الكاملة للمرشحين الواعدين.
ماذا لو كان لدي أربعة أهداف أو أكثر؟
قم بالتبديل إلى متغير معتمد على الوكيل من NSGA-III أو MOEA/D. يستخدم NSGA-III الاختيار المستند إلى نقاط مرجعية بدلاً من المسافة المزدحمة، مما يحافظ على التنوع بفعالية في أربعة أهداف أو أكثر. يقوم MOEA/D بتفكيك المشكلة إلى مشاكل فرعية قياسية ويتوسع بشكل أفضل في إعدادات الأهداف المتعددة.
كيف أتحقق من أن واجهة باريتو موثوقة؟
قم بتشغيل 10 تشغيلات تحسين مستقلة على الأقل باستخدام بذور عشوائية مختلفة وقم بحساب الحجم الفائق أو IGD لكل منها. أبلغ عن الوسيط والمدى الرباعي عبر التشغيلات. يشير الحجم الفائق المتسق عبر التشغيلات إلى أن المُحسِّن قد تقارب بشكل موثوق من نفس واجهة باريتو التقريبية.
طرق ذات صلة
المصادر
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تم النسخ.Macal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.
افتح مرجع DOIتم النسخ.