خوارزمية مجتمع النحل الاصطناعي

في مجالي علم الحاسوب وبحوث العمليات، خوارزمية مجتمع النحل (Artificial bee colony algorithm، اختصارا: ABC)، هي خوارزمية استمثالية تعتمد على نموذج ذكاء سلوك سرب النحل في البحث عن الطعام. فمن المعلوم أن النحل عندما يجد الطعام خلال رحلة البحث فإنه يعود للخلية بعيّنة منه ليخبر بقية النحل العاملة عن مكان الطعام واتجاهه من خلال قيام النحلة برقصة اهتزازية في اتجاه معين وبعدد مرات معينة للإشارة إلى مكان وجود الطعام. اقترحها كارابوغا عام 2005.^[1]

كذلك تُسمى بخوارزمية التعلم لأنها الأكثر سرعة في عملية التعلم والتي تميزت بإيجاد الحل الأمثل للعديد من التطبيقات، مثل التعرف على بصمة الاصبع والوصول إلى أقصر طريق (مسألة البائع المتجول).

لمحة عامة

يتكون مجتمع النحل من ثلاث مجموعات: العاملات، المتفرجات، والكشافة. ويفترض أن هناك عاملة واحدة لكل مصدر طعام، يعني أن عدد العاملات يساوي عدد مصادر الطعام حول الخلية.

تذهب العاملات إلى مصادر الطعام ثم ترجع وترقص في الخلية، وهنا يأتي دور المتفرجات، حيث تشاهد رقصات العاملات وتختار مصدر الطعام المناسب حسب الرقصات. أما العاملات اللاتي هُجرت (استُثنِيت) أماكن طعامهن فتصبح كشافة وتبدأ البحث عن مصادر جديدة للطعام.

الخطوات الأساسية

• البحث عن المصادر الغذائية الأولية لجميع النحل العاملات.
• كل نحلة عاملة تذهب إلى مصدر الغذاء الموجود في ذاكرتها وتحدد مصدر مجاور له وتقيّم مقدار الرحيق الموجود ثم ترجع لترقص في الخلية.
• كل نحلة متفرجة تشاهد الرقصات وتختار مصدر الغذاء بالاعتماد على الرقصات ثم تذهب للمكان وتقيّم مقدار الرحيق وجودته.
• يتم تحديد مصدر الغذاء المهجور واستبداله بمصدر جديد يكتشف من خلال الكشافة.

• أما أفضل المصادر البعيدة فيتم تسجيلها.

تعتمد هذه الخوارزمية على عدد النحلات في المجتمع ومكان الغذاء يمثل حل محتمل للمسألة  وكمية الرحيق يتطابق مع جودة الحل، ويمثل عدد النحلات العاملات عدد الحلول.

القاعدة وطريقة العمل

تعتمد هذه الخوارزمية على حجم الخلية (عدد النحلات) ، حيث يقسم سرب النحل إلى 50% نحلات عاملات و 50% نحلات كشافة وعدد المتفرجات يساوي 1.كما أن عدد النحلات العاملات يساوي عدد الحلول، حيث ${\displaystyle X_{i}=\{x_{i,1},x_{i,2},\ldots ,x_{i,n}\}}$ متّجه يمثّل الحل رقم ${\displaystyle i}$ في الخلية، ${\displaystyle n}$ مصادر الطعام (وبالتالي عدد النحلات العاملات).

كل نحلة عاملة ${\displaystyle X_{i}}$ تعطي حل ${\displaystyle V_{i}}$ (في خلية النحل يمثل ${\displaystyle X_{i}}$ موقع غذاء) ويُعطى ${\displaystyle V_{i}}$ بالمعادلة: ${\displaystyle V_{i_{k}}=X_{i_{k}}+\Phi _{i_{k}}\times (X_{i_{k}}-X_{j_{k}})}$

حيث ${\displaystyle X_{j}}$ حل يتم اختياره عشوائياً بشرط ${\displaystyle i\neq j}$، كذلك ${\displaystyle k\in \{1,2,\ldots ,n\}}$ مُحدد للبعد يتم اختياره عشوائياً، وعدد عشوائي ${\displaystyle \Phi _{i_{k}}}$ ضمن الفترة ${\displaystyle [-1,1]}$.

بعد تحديد اماكن الغذاء ${\displaystyle V_{i}}$ يتم مقارنتها معاً، فإذا كان مصدر الغذاء يساوي أو أفضل من القديم فيتم استبداله في الذاكرة، وإلا يبقى المكان القديم في الذاكرة ويتم استبعاد المكان الجديد.

تالياً يتم ايجاد الحل الأمثل وهو الحل الحاصل على أعلى احتمال ${\displaystyle P_{i}}$. بعد انتهاء عملية البحث عن مصادر الغذاء (الحلول) تُشارك النحلات العاملات النحلة المتفرجة المعلومات حول مصدر الغذاء (الحل) ثم تقوم النحلة المتفرجة باختيار الحل الامثل الحاصل على أفضل احتمال بين الحلول المقترحة الأخرى حيث يتم حساب الاحتمال بالمعادلة:

حيث أن ${\displaystyle fit_{i}}$: هي قيمة التناسب للحل ${\displaystyle i}$ ومجموعة باقي الحلول، وتحدد من خلال اقتران يناسب المسألة.

إذن الحل الامثل هو الحل (المصدر) ذو الاحتمال الاعلى، فإذا لم تتحسن قيمة ${\displaystyle X_{j}}$ لمصدر غذاء وفق قيمة معرفة سابقا تسمى النهاية (limit) بعد عدد من الدورات، فسوف يتم استثناء هذا المصدر (الحل).

مقالات ذات صلة

• استمثال عناصر السرب
• ذكاء السرب

مراجع

وصلات خارجية

• Artificial Bee Colony (ABC) Algorithm Homepage, Turkey: Intelligent Systems Research Group, Department of Computer Engineering, Erciyes University, مؤرشف من الأصل في 15 فبراير 2018

موسوعات ذات صلة :

• موسوعة خوارزميات