المعلوماتية > برمجيات
خوارزمية خلية النحل ABC
خوارزمية النحل خوارزمية مستوحاة من السلوك الذكي للنحل في بحثه عن الطعام. من المعلوم أن عاملات النحل عندما يجدن الطعام في رحلة البحث فإنهن يعدن للخلية بعيّنة منه ويخبرن بقية العاملات عن مكان الطعام واتجاهه عن طريق تأدية رقصة اهتزازية في اتجاه محدد وبعدد مرات محدد للإشارة إلى مكان الطعام.
خوارزمية خلية النحل الصنعية Artificial Bee Colony أو ABC اختصارًا هي خوارزمية عرَّفها البروفيسور درويش قره بوغا Derviş Karaboğa عام 2005 مستوحاة من السلوك الذكي لنحل العسل.
في الطبيعة تبحث بضع نحلات عاملات من الخلية عن مصادر غذاء في بستان من الأزهار مثلًا، وعندما تجد النحلة مصدر غذاء، تعود إلى الخلية لإخبار بقية النحل عن المصدر وذلك بتأدية بعض الحركات التي تدعى رقصات النحل، وتخبر عن موقع الغذاء واتجاهه وكميته وجودته عن طريق تلك الرقصات.
تصنف هذه الخوارزمية ضمن الخوارزميات السربية البسيطة مثل خوارزمية أسراب الطيور (هنا) وخوارزمية التطور التفاضلي Differential Evolution (DE) Algorithm، لأنها لا تستخدم سوى معاملات (بارامترات) التحكم الشائعة مثل حجم الخلية وعدد الدورات الأقصى.
يستفاد من هذه الخوارزمية في حل مسائل الأمثلية Optimization Problems؛ أي المسائل التي تتطلب التوصل إلى الحل الأمثل من مجموعة حلول مطروحة، مثل مسألة البائع الجوال الذي يجب عليه التنقل بين عدة مدن باستهلاك أقل ما يمكن من الوقود أو دون أن يمر من مدينة أكثر من مرة واحدة مثلًا.
خطوات الخوارزمية
تعد هذه الخوارزمية أداة أمثلية Optimization Tool تؤمن إجرائية بحث قائم على الجمهرة Population-Based Search، إذ تتفرق النحلات لتبحث كل منها عن مصادر الطعام وتعثر على مصدر رحيق وافر مقارنة بالمصادر الأخرى في رقعة بحثها، ثم يُحدد مصدر الرحيق الأوفر بين المصادر الوافرة جميعًا، وهذا بالضبط ما تتطلبه مسائل الأمثلية (الأفضلية).
في نظام ABC؛ يصنف النحل إلى عامل ومراقب ومستكشف، ويتنقل النحل العامل في مساحة بحث متعددة الأبعاد كلٌّ في اتجاه، ويختار بعض النحل العامل والمراقب مصادر الطعام اعتمادًا على:
- تجربتهم
- والأفراد المجاورين لهم في أثناء البحث
- وتغير أوضاعهم في أثناء مراحل عمل الخوارزمية.
يطير بعض أفراد النحل المستكشف للبحث عن مصادر جديدة عشوائيًّا، أما أفراد النحل العامل فيبحثون عن مصادر الغذاء استنادًا إلى تجارب سابقة، فإن توصلوا إلى كمية رحيق في المصدر الجديد أكبر من الكمية في المصدر المخزن في ذاكرتهم سابقًا؛ يُحفظ المصدر الجديد ويُنسى السابق.
وهكذا تجمع خوارزمية ABC بين طرائق البحث المحلية التي يؤديها النحل العامل والمراقب وطرائق البحث العامة التي يؤديها النحل المستكشف؛ محققة بذلك توازنًا بين اكتشاف Exploration مصادر جديدة واستثمار Exploitation مصادر معروفة.
برمجة الخوارزمية حاسوبيًّا
تتألف هذه الخوارزمية من الخطوات الآتية:
الخطوة الأولى: تبدأ هذه الخوارزمية بوضع n نحلة كشفية في مساحة بحث محددة s.
الخطوة الثانية: تقيم النحلات مدى ملاءمة المواقع التي زارتها، ثم تُعد نتائج هذه التقييمات قيمًا أولية للتدريب مع بيانات الموقع الأخرى، وتُكرر هذه العملية عددًا من المرات، ثم تُخزن قيم الملاءمة الناتجة عن النحلات - وهي n قيمة - في مصفوفة بترتيب تنازلي.
الخطوة الثالثة: تنتقي النحلات الكشفية جميعها m موقعًا من عناصر مصفوفة الملاءمة متخذاتٍ القرار اتخاذًا جمعيًّا، ثم يُختار e موقعًا من المجموعة m على كامل مساحة البحث s.
الخطوة الرابعة: تُختار مساحة بحث مجاورة للمواقع الأشد ملاءمة لعل النحل يجد مواقع أخرى أفضل من الحالية، فإن تحقق ذلك حُدثت بيانات المصفوفة، وإلا بقيت عناصر المصفوفة على حالها.
الخطوة الخامسة: بعد مرحلة اختيار المواقع المجاورة يعيد النحل تقييم ملاءمة تلك المواقع.
الخطوة السادسة: تُختار النحلات الأفضل في كل موقع لتكوين جيل الجمهرة اللاحق. هذه الخطوة غير موجودة في الطبيعة، لكن وُضعت في الخوارزمية الحاسوبية لتقليص عدد المواقع التي يجب اكتشافها في الدورة اللاحقة.
الخطوة السابعة: تُهيأ الجمهرة الجديدة ببيانات المواقع الأفضل التي توصل إليها النحل الكشاف في التكرار الأول للخوارزمية.
الخطوة الثامنة: تُكرّر الخطوات (من 2 إلى 7) لحين الوصول إلى شرط التوقف (قد يخدد عدد التكرارات مسبقًّا أو يُحدّد عدد مواقع معينة نرغب في الحصول عليها)
ختامًا، ونظرًا إلى استقرار هذه الخوارزمية وتقاربها السريع ومرونتها العالية ومعاملات التحكم القليلة؛ تُستخدم خوارزمية النحل الصنعية في تطبيقات كثيرة في العالم الحقيقي.
وبغرض تحسين كفاءة هذه الخوارزمية في التطبيقات؛ تُدمج مع الخوارزميات الجينية Genetic Algorithms.
المصادر: