تحسين السرب الجسيمي (PSO)
- السنة
- 1995
- النوع
- Population-based metaheuristic / swarm intelligence
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تحسين السرب الجسيمي (PSO) هو خوارزمية استدلالية فائقة قائمة على السكان قدمها كينيدي وإيبرهارت في عام 1995، مستوحاة من الحركة الجماعية لأسراب الطيور ومدارس الأسماك. كل حل مرشح - يسمى جسيمًا - يتحرك عبر مساحة البحث عن طريق تحديث سرعته وموضعه بناءً على أفضل تجاربه الخاصة وأفضل تجارب السرب بأكمله، مما يتيح تقاربًا سريعًا عبر مشاكل التحسين المستمر.
الفكرة الحدسية وراء الطريقة
تخيل سربًا من الطيور يبحث في حقل واسع عن أغنى مصدر للغذاء. لا يمتلك أي طائر خريطة، لكن كل واحد يتذكر أفضل بقعة زارها شخصيًا ويدرك أفضل بقعة وجدتها أي طائر قريب. كل طائر يوجه رحلته جزئيًا نحو أفضل موقع يتذكره بنفسه وجزئيًا نحو أفضل موقع للسرب بشكل جماعي، ويضبط سرعته وفقًا لذلك. عبر العديد من هذه التعديلات، يتقارب السرب بأكمله نحو المنطقة الأكثر ثراءً. يعمل تحسين السرب الجسيمي بنفس الطريقة تمامًا: كل جسيم هو حل مرشح، وموقعه هو الحل نفسه، ويتجمع السرب بشكل جماعي نحو الأمثل عن طريق تجميع الذاكرة الفردية والاجتماعية.
التاريخ
قدم جيمس كينيدي ورسل إيبرهارت تحسين السرب الجسيمي في المؤتمر الدولي للشبكات العصبية IEEE عام 1995، مستفيدين مباشرة من نماذج المحاكاة للسلوك الاجتماعي في أسراب الطيور ومدارس الأسماك. أسست الورقة الأساسية لعام 1995 معادلات تحديث السرعة والموضع التي لا تزال مركزية للخوارزمية. في عام 1998، قدم شي وإيبرهارت معلمة وزن القصور الذاتي في تحديث السرعة، مما حسن بشكل كبير التحكم في التقارب وأصبح التعديل القياسي الذي اعتمدته الأبحاث اللاحقة. اكتسب تحسين السرب الجسيمي زخمًا بسرعة كبديل عملي للخوارزميات الجينية للتحسين المستمر، نظرًا لبساطته وسرعة تقاربه التنافسية، وقد تم تطبيقه منذ ذلك الحين في مجالات الهندسة، وضبط المعلمات الفائقة للتعلم الآلي، ومعالجة الإشارات، والنمذجة العلمية.
متى تُستخدم
يصلح تحسين السرب الجسيمي لمشاكل التحسين المستمر حيث يمكن تقييم دالة اللياقة عند أي نقطة في مساحة البحث ولكن قد تكون غير قابلة للاشتقاق، أو متعددة الأنماط، أو مكلفة حسابيًا تحليليًا. لا يتطلب افتراض الطبيعية ولا الحد الأدنى لحجم العينة، مما يجعله قابلاً للتطبيق عبر المجالات. تعمل الطريقة بشكل أفضل عندما تكون حدود مساحة البحث معروفة مسبقًا، وعندما يتم ضبط وزن القصور الذاتي ومعاملات التسارع بعناية، وعند تخصيص عدد كافٍ من التكرارات. إذا كان عدد التكرارات منخفضًا جدًا (أقل من بضع مئات في المشاكل غير التافهة)، فمن المحتمل حدوث تقارب مبكر وقد يكون التحسين البايزي بديلاً أكثر أمانًا.
الحدود والاعتبارات
- مصمم لمساحات البحث المستمر؛ غير قابل للتطبيق مباشرة على المشاكل المنفصلة أو التوافقية بدون تعديل.
- التقارب المبكر هو خطر معروف: قد يتجمع السرب حول حد أمثل محلي إذا تم اختيار وزن القصور الذاتي والمعاملات بشكل سيء.
- تعتمد سرعة التقارب وجودة الحل على اختيار وزن القصور الذاتي ومعاملات التسارع.
- لا يوجد ضمان نظري للعثور على الحد الأمثل العالمي في عدد محدود من التكرارات.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تقارب سريع في مساحات البحث المستمر مقارنة بالعديد من الطرق القائمة على السكان.
- عدد قليل جدًا من المعلمات لضبطها - بشكل أساسي وزن القصور الذاتي ومعاملين للتسارع.
- لا يتطلب معلومات التدرج أو المشتقة، مما يجعله قابلاً للتطبيق على دوال اللياقة غير القابلة للاشتقاق والصندوق الأسود.
- يتوسع بشكل طبيعي للمشاكل المستمرة عالية الأبعاد.
- بسيط من الناحية المفاهيمية وسهل التنفيذ.
التطبيقات
- ضبط المعلمات الفائقة لنماذج التعلم الآلي عبر مساحات المعلمات المستمرة.
- تحسين التصميم الهندسي - تصميم الهياكل، والديناميكا الهوائية، والأنظمة الكهربائية.
- تدريب أوزان الشبكات العصبية والبحث عن البنية.
- معالجة الإشارات وتصميم الهوائيات.
- التفويض الاقتصادي وتحسين أنظمة الطاقة.
- تقدير المعلمات في النماذج العلمية ونماذج المحاكاة.
كيف يعمل
كيف يعمل
يتم وضع سرب من الجسيمات في مواضع عشوائية داخل مساحة البحث المحددة، ويتم تعيين سرعة أولية عشوائية لكل جسيم. يسجل كل جسيم أيضًا أفضل موضع شخصي له - أفضل حل واجهه حتى الآن - ويتتبع السرب أفضل موضع عالمي وجده أي جسيم. يتم تعيين وزن القصور الذاتي، ومعامل الإدراك، ومعامل الاجتماعية قبل بدء التشغيل، حيث أن توازنهما يحكم مباشرة ما إذا كان السرب يستكشف على نطاق واسع أو يستغل المناطق الجيدة المعروفة.
يتم حساب دالة اللياقة لكل جسيم في موضعه الحالي. هذه هي الخطوة الوحيدة الخاصة بالمشكلة: لا يفرض تحسين السرب الجسيمي أي قيود على شكل دالة اللياقة بخلاف شرط إمكانية تقييمها عند أي نقطة في مساحة البحث المستمر. يتم تحديث أفضل موضع شخصي لكل جسيم وأفضل موضع عالمي للسرب كلما أدى موضع جديد إلى قيمة لياقة أفضل.
يتم تحديث سرعة كل جسيم باستخدام ثلاثة مكونات: حد القصور الذاتي (السرعة السابقة المُقاسة، مما يعزز الزخم)، حد الإدراك (الجاذبية نحو أفضل موضع شخصي للجسيم)، وحد الاجتماعية (الجاذبية نحو أفضل موضع عالمي للسرب). يتم بعد ذلك حساب الموضع الجديد عن طريق إضافة السرعة المحدثة إلى الموضع الحالي. يتحكم وزن القصور الذاتي في المقايضة بين الاستكشاف والاستغلال: قيمة أعلى تفضل الاستكشاف الواسع بينما قيمة أقل تعزز الاستغلال الدقيق للمناطق الجيدة المعروفة.
تُكرر خطوات التقييم والتحديث لعدد محدد من التكرارات. يضيق السرب تدريجيًا بحثه حول المنطقة الواعدة. ينتهي التشغيل عند الوصول إلى حد التكرار، وعند هذه النقطة يتم الإبلاغ عن أفضل موضع عالمي كحل. يلزم عدد كافٍ من التكرارات - عادةً مئات إلى ألف تكرار على الأقل للمشاكل غير التافهة - للسماح للسرب بالتقارب؛ التوقف المبكر جدًا يخاطر بإرجاع نتيجة دون المستوى الأمثل.
الأخطاء الشائعة
- تشغيل عدد قليل جدًا من التكرارات - في المشاكل غير التافهة، تمنع التكرارات غير الكافية السرب من التقارب؛ يفضل التحسين البايزي عندما تكون ميزانية الحساب ضيقة جدًا.
- اختيار وزن قصور ذاتي مرتفع جدًا يبقي الجسيمات تستكشف إلى أجل غير مسمى ويؤخر التقارب؛ منخفض جدًا يسبب تكتلًا مبكرًا حول حد أمثل محلي.
- تجاهل حدود مساحة البحث - الجسيمات التي تنجرف خارج الحدود المقصودة تستكشف مناطق غير ذات صلة وتشوه أفضل موضع عالمي.
- معاملة تحسين السرب الجسيمي على أنها مناسبة للمشاكل المنفصلة أو التوافقية دون تكييف - تفترض معادلات تحديث السرعة والموضع القياسية مساحة مستمرة.
- يتم اكتشاف التقارب المبكر بشكل غير صحيح إذا لم يتم مراقبة تقدم اللياقة عبر التكرارات؛ تتبع دائمًا لياقة أفضل موضع عالمي مقابل عدد التكرارات.
الأسئلة الشائعة
كيف يختلف تحسين السرب الجسيمي عن الخوارزمية الجينية؟
كلاهما استدلالات فائقة قائمة على السكان للتحسين، لكنهما يختلفان في الآلية. تطور الخوارزمية الجينية مجموعة من خلال عوامل الاختيار، والتقاطع، والطفرة المستوحاة من التطور البيولوجي. بدلاً من ذلك، يحرك تحسين السرب الجسيمي الجسيمات عبر مساحة مستمرة عن طريق تحديث السرعات بناءً على الذاكرة الشخصية والاجتماعية - لا يوجد تقاطع أو طفرة. عادةً ما يحتوي تحسين السرب الجسيمي على معلمات أقل لضبطها وغالبًا ما يتقارب بشكل أسرع في المشاكل المستمرة، بينما يمكن تكييف الخوارزميات الجينية بشكل طبيعي أكثر للمساحات المنفصلة أو التوافقية.
ما هي المعلمات الرئيسية وكيف ينبغي ضبطها؟
المعلمات الأساسية الثلاثة هي وزن القصور الذاتي (w)، الذي يتحكم في مقدار السرعة السابقة التي يتم الاحتفاظ بها؛ معامل الإدراك (c1)، الذي يقيس الجاذبية نحو أفضل موضع شخصي للجسيم؛ ومعامل الاجتماعية (c2)، الذي يقيس الجاذبية نحو أفضل موضع عالمي. نقطة انطلاق شائعة من الأدبيات هي w حوالي 0.7-0.9، و c1 و c2 حوالي 1.5-2.0. غالبًا ما يتم تقليل وزن القصور الذاتي خطيًا عبر التكرارات لنقل السرب من الاستكشاف في البداية نحو الاستغلال لاحقًا.
هل يمكن لتحسين السرب الجسيمي التعامل مع المشاكل المنفصلة أو التوافقية؟
تم تعريف تحسين السرب الجسيمي القياسي لمساحات البحث المستمر ويطبق تحديثات السرعة والموضع التي تفترض إحداثيات ذات قيم حقيقية. توجد متغيرات منفصلة أو توافقية - مثل تحسين السرب الجسيمي الثنائي - ولكن هذه تتطلب تعديلات غير تافهة لمعادلات التحديث. بالنسبة للمشاكل التوافقية البحتة مثل التوجيه أو الجدولة، غالبًا ما يكون تحسين مستعمرة النمل هو الخيار الأكثر طبيعية.
كيف أعرف إذا كان السرب قد تقارب مبكرًا؟
تتبع قيمة لياقة أفضل موضع عالمي عبر التكرارات. إذا استوى المنحنى قبل نفاد ميزانية التكرار بوقت طويل ولم يكن الحل المبلغ عنه مرضيًا، فمن المحتمل أن يكون التقارب المبكر قد حدث. تشمل العلاجات الشائعة زيادة وزن القصور الذاتي، أو إعادة تشغيل السرب من مواضع عشوائية جديدة، أو زيادة حجم السرب. إذا لم تسمح ميزانية الحساب بمزيد من التكرارات، فقد يكون التحسين البايزي بديلاً أكثر كفاءة.
طرق ذات صلة
المصادر
Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.
افتح مرجع DOIتم النسخ.Shi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).
افتح مرجع المنشورتم النسخ.