التحسين بالزخم الجسيمي متعدد الأهداف (MOPSO)
- قدّمه
- Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S.
- السنة
- 2004
- النوع
- Population-based swarm metaheuristic
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
التحسين بالزخم الجسيمي متعدد الأهداف (MOPSO) هو استراتيجية فوق-استدلالية (metaheuristic) مستوحاة من ذكاء الأسراب، توسع نطاق التحسين بالزخم الجسيمي الأصلي (PSO) للتعامل مع دوال هدف متعددة ومتعارضة في وقت واحد. تحتفظ بأرشيف خارجي لباريتو وتستخدم الاختيار القائم على الهيمنة لتوجيه مجموعة من الحلول المرشحة نحو جبهة باريتو الحقيقية دون الحاجة إلى معلومات تفضيلية مسبقة.
الفكرة الحدسية وراء الطريقة
تخيل سربًا من الطيور يبحث جماعيًا عن الطعام في منظر طبيعي به تلال متعددة بارتفاعات مختلفة لا يمكن تسلقها جميعًا مرة واحدة — غالبًا ما يعني اكتساب الارتفاع على تل خسارة الأرض على تل آخر. يطلق MOPSO سربًا من الجسيمات عبر فضاء المقايضات متعدد الأبعاد هذا. يتذكر كل جسيم أفضل موضع غير مهيمن خاص به ويتعلم من أرشيف خارجي لأفضل الحلول العالمية غير المهيمنة التي تم العثور عليها حتى الآن. من خلال مزج الذاكرة الشخصية، والتعلم الاجتماعي، والعشوائية المتحكم بها، يقوم السرب تدريجيًا برسم جبهة باريتو الكاملة، وكشف الطيف الكامل للمقايضات الفعالة بدلاً من حل وسط واحد.
التاريخ
تم تقديم التحسين بالزخم الجسيمي بواسطة كينيدي وإيبرهارت في عام 1995، مستوحى من السلوك الاجتماعي لتجمعات الطيور. تم اقتراح أول امتداد واسع النطاق متعدد الأهداف، MOPSO، بواسطة كويلو كويلو، بوليدو، وليتشوجا في عام 2004، والذي قدم أرشيف باريتو خارجي واختيار قائد قائم على المكعب الفائق. قامت المتغيرات اللاحقة — بما في ذلك OMOPSO، و dMOPSO، و SMPSO — بتحسين إدارة الأرشيف، والمعلمات التكيفية، ومعالجة القيود، مما رسخ MOPSO كخوارزمية رئيسية لتقريب جبهة باريتو جنبًا إلى جنب مع NSGA-II.
متى تُستخدم
استخدم MOPSO عندما تواجه مشكلة تحسين مستمرة مع هدفين أو أكثر متعارضين وتحتاج إلى تقريب جبهة باريتو الكاملة بدلاً من حل واحد. يتفوق في التصميم الهندسي، وسلسلة التوريد، وأنظمة الطاقة، وضبط المعلمات الفائقة حيث تكون تقييمات الأهداف مكلفة بشكل معتدل وفضاء القرار مستمر. فضل NSGA-II أو NSGA-III للمشاكل التوافقية أو المختلطة الأعداد الصحيحة، وفضل طرق الأهداف المتعددة القائمة على التدرج عندما تكون الأهداف سلسة وقابلة للاشتقاق. لا تستخدم MOPSO عندما يتجاوز عدد الأهداف خمسة إلى سبعة — تتطلب مشاكل الأهداف المتعددة خوارزميات متخصصة للأهداف المتعددة (مثل NSGA-III، MOEA/D). تجنبها أيضًا عندما يكون كل تقييم دالة مكلفًا للغاية (أقل من 100 تقييم متاح) — الطرق المدعومة بالبدائل مفضلة في هذا النظام.
الحدود والاعتبارات
- الأداء حساس لوزن القصور الذاتي (w) ومعاملات التسارع (c1، c2)؛ تؤدي المعلمات غير المضبوطة بشكل جيد إلى التقارب المبكر أو الانجراف المفرط.
- تضيف إدارة الأرشيف واختيار القادة معلمات فائقة إضافية (حجم الأرشيف، مقياس التجمّع) تعتمد على المشكلة.
- ضمانات التقارب والتنوع هي استدلالية، وليست رياضية — قد تفوت جبهة باريتو التقريبية مناطق من الجبهة الحقيقية.
- يعاني مع أكثر من خمسة إلى سبعة أهداف بسبب لعنة الأبعاد في الاختيار القائم على الهيمنة.
- غير قابل للتطبيق مباشرة على فضاءات البحث المنفصلة أو التوافقية بدون ترميز خاص بالمشكلة وتكييفات لتحديد سرعة الانحراف.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يقرب بشكل طبيعي جبهة باريتو الكاملة في تشغيل واحد، مما يوفر لصانعي القرار مجموعة غنية من حلول المقايضة الفعالة.
- لا يتطلب معلومات التدرج، مما يجعله قابلاً للتطبيق على دوال الهدف غير القابلة للاشتقاق، أو المشوشة، أو الصندوق الأسود.
- آلية تحديث السرعة والموضع البسيطة خفيفة حسابيًا وسهلة التنفيذ بالتوازي.
- يحافظ أرشيف باريتو الخارجي على أفضل الحلول التي تم العثور عليها طوال البحث، مما يمنع فقدان نقاط غير مهيمنة عالية الجودة.
- يوفر الإطار المرن معالجة القيود، والتحكم التكيفي في المعلمات، والتهجين مع البحث المحلي.
التطبيقات
- التصميم الهندسي متعدد الأهداف: تقليل الوزن والتكلفة والإجهاد بشكل متزامن في المكونات الهيكلية والميكانيكية.
- أنظمة الطاقة: مقايضات باريتو المثلى بين التكلفة والموثوقية والانبعاثات في جدولة شبكات الطاقة وتخطيط الطاقة المتجددة.
- إدارة سلسلة التوريد: التحسين المشترك لمستوى الخدمة وتكلفة المخزون ووقت التسليم عبر شبكات متعددة المستويات.
- ضبط المعلمات الفائقة للتعلم الآلي: موازنة دقة النموذج مقابل وقت الاستدلال أو بصمة الذاكرة.
- إدارة موارد المياه: تحسين سياسات إطلاق الخزانات للأهداف المتنافسة لتوليد الطاقة والتحكم في الفيضانات وتدفق النظام البيئي.
- تحسين المحفظة: تقريب جبهة الكفاءة للعائد المتوقع مقابل المخاطر لتخصيص الأصول المالية.
كيف يعمل
كيف يعمل
إنشاء مجموعة من N جسيمات بمواقع وسرعات عشوائية في فضاء القرار. تقييم جميع دوال الهدف لكل جسيم وتعبئة أرشيف باريتو الخارجي بجميع الحلول الأولية غير المهيمنة. تعيين أفضل موضع شخصي (pbest) لكل جسيم مساويًا لموقعه الابتدائي.
حساب جميع قيم دوال الهدف لكل جسيم في السرب الحالي. تطبيق مقارنات الهيمنة: الحل x يهيمن على الحل y إذا كان x ليس أسوأ في جميع الأهداف وأفضل بشكل صارم في هدف واحد على الأقل. تحديث أفضل موضع شخصي (pbest) لكل جسيم إذا كان الموضع الجديد يهيمن على أفضل موضع شخصي مخزن، أو غير مهيمن بالنسبة له.
إدراج جميع الحلول الجديدة غير المهيمنة في الأرشيف الخارجي. إزالة أي أعضاء في الأرشيف أصبحوا الآن مهيمنين من قبل الوافدين الجدد. إذا تجاوز الأرشيف حد سعته، قم بتطبيق استراتيجية تقليم قائمة على الكثافة (مثل، تجمّع المكعب الفائق أو مسافة الجار الأقرب) للحفاظ على التنوع عبر تقريب جبهة باريتو.
لكل جسيم، اختر قائدًا عالميًا أفضل (gbest) من الأرشيف الخارجي. عادةً ما يتم اختيار القائد من مناطق الأرشيف الأقل ازدحامًا باستخدام آلية دورة أو عجلة دوارة بناءً على مسافة التجمّع، مما يضمن انجذاب السرب نحو أجزاء جبهة باريتو غير المستكشفة بدلاً من التقارب المبكر إلى منطقة واحدة.
تحديث السرعة والموضع لكل جسيم باستخدام قاعدة تحديث PSO: v = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x)، حيث w هو وزن القصور الذاتي الذي يتحكم في توازن الاستكشاف/الاستغلال، c1 و c2 هما معاملات التسارع المعرفي والاجتماعي، و r1، r2 هما أرقام عشوائية منتظمة. تطبيق معالجة الحدود للحفاظ على الجسيمات في فضاء القرار الممكن.
الصيغة
v_{id}^{t+1} = w v_{id}^t + c_1 r_1 (pbest_{id} - x_{id}^t) + c_2 r_2 (gbest_d - x_{id}^t)كرر التقييم–التحديث–الأرشفة–اختيار القادة–تحريك الجسيمات حتى يتم استيفاء معيار التوقف (الحد الأقصى للتكرارات، الحد الأقصى لتقييمات الدوال، أو ركود جبهة باريتو). أعد الأرشيف الخارجي النهائي كمجموعة باريتو المثلى التقريبية، والتي يقوم صانع القرار بعد ذلك بفحصها لاختيار حل مقايضة مفضل.
الأخطاء الشائعة
- يؤدي تعيين سعة الأرشيف صغيرة جدًا إلى تقليم عدواني يدمر تنوع جبهة باريتو؛ والكبير جدًا يبطئ اختيار القائد ويزيد من تكلفة الذاكرة.
- يؤدي استخدام قائد عالمي أفضل واحد للسرب بأكمله إلى التقارب المبكر؛ استخدم دائمًا آلية اختيار قائد واعية بالتنوع (مثل، دورة مسافة التجمّع).
- إهمال معالجة الحدود يسمح للجسيمات بالهروب من المنطقة الممكنة، مما ينتج حلولاً غير ممكنة تلوث الأرشيف.
- الإبلاغ فقط عن الأرشيف النهائي بدون مقاييس التقارب والتنوع (مثل، مؤشر الحجم الفائق، المسافة الجيلية) يجعل من المستحيل مقارنة النتائج عبر التشغيلات أو الطرق.
- معاملة MOPSO كمحسن صندوق أسود دون التحقق من أن أهداف المشكلة متعارضة بالفعل — إذا كانت الأهداف متوافقة، فإن PSO أحادي الهدف القياسي أو الانحدار المتدرج كافٍ.
الأسئلة الشائعة
كيف يختلف MOPSO عن NSGA-II؟
كلاهما يقرب جبهة باريتو باستخدام مجموعة من الحلول والاختيار القائم على الهيمنة، لكنهما يختلفان في الآليات. يستخدم NSGA-II عوامل التقاطع والطفرة على مجموعة مدمجة من الآباء والأبناء مع فرز مسافة التجمّع. يستخدم MOPSO حركة الجسيمات القائمة على السرعة الموجهة بواسطة قادة شخصيين وقادة قائمين على الأرشيف. عادةً ما يكون MOPSO أسرع لكل تكرار في المساحات المستمرة؛ NSGA-II أكثر ملاءمة بطبيعته للمشاكل التوافقية والتبديلية.
ما حجم الأرشيف الذي يجب أن أستخدمه؟
الحجم الافتراضي الشائع هو 100-200 حل لمشاكل الهدفين أو الثلاثة. تحسن الأرشيفات الأكبر تغطية جبهة باريتو ولكنها تبطئ اختيار القائد. بالنسبة للمشاكل ذات أربعة أهداف أو أكثر، يجب أن يتناسب حجم الأرشيف مع التعقيد المتوقع لجبهة باريتو؛ يمكن أن تساعد مخططات إدارة الأرشيف التكيفية.
هل يمكن لـ MOPSO التعامل مع القيود؟
نعم، من خلال دوال العقوبة، وقواعد الإمكانية (تفضيل الحلول الممكنة على غير الممكنة في مقارنات الهيمنة)، أو عوامل الإصلاح. تتضمن الصيغة الأصلية لكويلو كويلو آلية بسيطة لمعالجة القيود تعتمد على دورات الإمكانية.
كم عدد دوال الهدف التي يمكن لـ MOPSO التعامل معها بفعالية؟
يعمل MOPSO بشكل جيد لهدفين إلى أربعة أهداف. بعد خمسة إلى سبعة أهداف، تضعف ضغوط الهيمنة بشكل كبير — تصبح جميع الحلول تقريبًا غير مهيمنة بشكل متبادل — وتتفوق محسنات الأهداف المتعددة المتخصصة (NSGA-III، MOEA/D، أو الطرق القائمة على التحلل) على MOPSO القياسي.
ما هي المقاييس التي يجب أن أستخدمها لتقييم نتائج MOPSO؟
أبلغ عن مؤشر الحجم الفائق (يقيس حجم فضاء الهدف الذي تهيمن عليه الجبهة التقريبية — الأعلى أفضل)، والمسافة الجيلية (القرب من جبهة باريتو مرجعية)، ومقاييس الانتشار أو دلتا (انتظام التوزيع). يلزم إجراء تشغيلات مستقلة متعددة مع مقارنات إحصائية للتوثيق الموثوق.
طرق ذات صلة
المصادر
Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256–279.
افتح مرجع DOIتم النسخ.Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks (ICNN), Perth, Australia, 4, 1942–1948.
افتح مرجع DOIتم النسخ.