المعلوماتية > برمجيات
خوارزميَّةُ أسراب الطُّيور PSO
اكتُشِفت خوارزمية أسراب الطيور-أو كما تعرف بـ (Particle swarm optimization (PSO- عام 1995 على يد عالم النفس والاجتماع (جيمس كيندي) والمهندس الكهربائي (راسل إيبرهارت). تقومُ فكرة الخوارزمية على مجموعةٍ من العناصر تُسمى بـ"السرب"، وتنتشر عشوائيًّا في منطقةٍ محدودة بهدف البحث عن الحل الأمثل داخل هذه المنطقة.
تعودُ خلفية هذه الخوارزمية إلى مصطلح "الحياة الصنعية" Artificial life -أو باختصار Alife-، والذي يعود إلى أوائل القرن العشرين؛ إذ يصف هذا المصطلح الأبحاثَ التي تدرس نُظمًا من صنع الإنسان وتملك خصائص الحياة الأساسية؛ مثل نمذجة حركة الطيور أو النمل في بناء المستعمرات.
يتفرَّع عن هذا المصطلح فرعان أساسيان:
- الدراسات المهتمة بتقنيات الحوسبة والمساعدة في نمذجة الظواهر البيولوجية.
- الدراسات المهتمة بالظواهر البيولوجية وكيفية توظيفها الصحيح في حل المشكلات الحاسوبية؛ مثل الخوارزميات الجينية والشبكات العصبونية الصنعية.
- تصنَّفُ خوارزمية (أسراب الطيور) ضمن الفرع الثاني، ولكن باختلافٍ بسيطٍ عن الخوارزميات الجينية؛ إذ تناقش الخوارزمية نمطًا آخر من النظم البيولوجية، وهي نظمٌ تعتمد على السلوك التعاوني للأفراد في أثناء تفاعلهم مع بيئتهم ومع بعضهم.
ما هي خوارزمية (أسراب الطيور)؟ وكيف تنَفَّذُ في الفضاء البرمجي؟
لشرح الفكرة سنطرح المثال الآتي:
لدينا سربٌ من الطيور ينتشر في منطقةٍ محددةٍ بغرض البحث عن طعام، وينتشر الطعام في هذه المنطقة عشوائيًّا، بالإضافة إلى أنَّ الطيور لا تعلم مواضع الطعام على نحوٍ واضح؛ فما هي الطريقة المُثلى للبحث عن الطعام؟
الطريقة المثلى هي بانتشار الطيور كافة في المنطقة، مع إخبار الطيور في كل مرة بعضها للبعض عن مواضع الطعام.
شكل توضيحي (1) طريقة عمل الخوارزمية
كما نرى في الصورة أعلاه؛ فالعناصر تبدأ رحلة البحث من مناطقَ عشوائيةً، ومع كل إعادةٍ تقترب العناصر من الحل الأمثل والأكثر دقة (المنطقة الممتلئة بالطعام).
هذا ما تفعله الخوارزمية تمامًا؛ إذ يُدعى كلّ طيرٍ داخل الخوارزمية بـ العنصر -أو particl-، ويمتلك كل عنصرٍ قيمةً ملائمةً -أو fitness value-، وتدلُّ هذه القيمة على مدى ملائمة حل هذا العنصر بالمقارنة مع باقي العناصر؛ إذ تجري هذه العملية بمساعدة تابعٍ يُسمّى تابع الملائمة fitness function.
تمتلك العناصر سرعاتٍ تقودها في رحلة بحثها عن الطعام أيضًا.
تعالَجُ المعلومات عن طريق الاستعانة ببعض المتغيرات المهمة وهي:
أفضل قيمةٍ ملائمةٍ سجَّلها العنصر وتُرمز بـ pbest، بالإضافة إلى أفضل قيمةٍ ملائمةٍ مُسجلةٍ ضمن السرب gbest، وأخيرًا قيمةُ أفضلِ تموضعٍ محليٍّ لعنصر بالمقارنة مع العناصر المجاورة محليًا lbest.
بعد معرفة قيم هذه العناصر، تُغير العناصر من سرعتها وتموضعها في كل تكرارٍ بمساعدة المعادلتين الآتيتين:
إذ تمثِّل سرعة العنصر، و c معاملات التسارع، و present تموضع العنصر الحالي.
ونرى أنَّ المعادلة الأولى تحسُب سرعة العنصر بالاعتماد على عدة عوامل:
السرعة اللحظية في التكرار السابق
أما المعادلة الثانية؛ تمكننا من حساب موضع العنصر الجديد بالاعتماد على سرعته وتموضعه السابقين.
خوارزمية (أسراب الطيور) بخطوات بسيطة:
يمكننا اختصار عمل الخوارزمية إلى ثلاث خطواتٍ رئيسة:
- حساب قيمة الملائمة لكل عنصر وقيمة الملائمة العامة.
- تحديث قيم الملائمة.
- تحديث السرعة والموضع لكل عنصر.
في الصورة أدناه نرى المخطط الهيكلي للخوارزمية:
في البداية؛ تُعرَّفُ جميع العناصر وتعطى قيمًا ابتدائية، ثمَّ تُحسب قيم الملائمة لكل عنصر، بعد ذلك يناقَشُ الشرط الآتي:"هل قيمةُ الملائمة الحالية أفضل من السابقة؟"
في حال كانت قيمة الملائمة أفضلُ من القيمة السابقة؛ نحدِّثُ القيمةَ القديمة إلى القيمة الحديثة، وأما في حال كانت القيمة القديمة أفضل من الحديثة؛ فنبقي على القيمة القديمة. ثم نضع قيمةَ ملائمةِ العنصر الجديدة مكان قيمة الملائمة الكلية للسرب، ثم نحسب سرعة العنصر ونناقش إذا ما كان العنصر قد وصل إلى الحل المثالي أم لا، في حال الوصول تنتهي الخوارزمية، أما في حال عدم الوصول فتكرر الخوارزمية نفسها من مرحلة حساب قيمة الملائمة الجديدة.
بعد التعرف إلى سير الخوارزمية؛ يمكننا القول أن هذه الخوارزمية بسيطة وسهلة البرمجة والتطبيق.
ما الفرق بين خوارزمية (أسراب الطيور) والخوارزميات الجينية؟
كما ذكرنا سابقًا؛ إنَّ خوارزمية الأسراب والخوارزميات الجينية GAs تنحدر من سلالة الخوارزميات التطورية؛ إذ تمتلك الخوارزميتان بعض نقاط التشابه، مثل توليد تجمعات عشوائيةٍ وحساب قيمة الملائمة. وتحدَّثُ الخوارزميتين وفقًا لتقنياتٍ عشوائية؛ بينما توجد بعض نقاط الاختلاف؛ إذ أنَّ خوارزمية PSO لا تمتلك معاملات التزاوج والطفرة التي تمتلكها الخوارزميات الجينية.
ثم إنَّ آلية معالجة المعلومات في الخوارزميات الجينية GAs مختلفة كثيرًا؛ إذ تتشارك الـ"كروموزومات" المعلومات مع بعضها؛ مما يؤدي إلى تحرك جميع العناصر على هيئة مجموعةٍ واحدةٍ إلى المنطقة المُثلى. وأمّا في خوارزمية (أسراب الطيور) PSO؛ فإنَّ معامل Ibest يعطي المعلومات المهمة فقط لعناصر السرب، لتكون هذه الخوارزميةُ خوارزميةً ذات اتجاه واحد في مشاركة المعلومات، وتمتلك عناصرَ تسعى دائمًا لتتقارب باتجاه الحل الأفضل سريعًا.
وختامًا؛ يمكننا القول أنَّ هذه الخوارزمية كانت أحدَ أفضلِ الخوارزميات التي استُوحت من السلوكيات الاجتماعية الجماعية المتطورة للكائنات الحية، وذلك لما برهنته من فاعليةٍ وانتشارٍ في تطبيقاتٍ عديدة شملت جوانب الحياة شتَّى؛ مثل الاتصالات ومجال الطب الحيوي والتحكم.
المصادر:
1-هنا
2-هنا
3-هنا
4-هنا