في مجال الحوسبة و البحث العملياتي، أي علم اتخاد القرار، تعتبر خوارزميات النحل من الخوارزميات التحسينية الفريدة والفعالة. هذه الخوارزميات التحسينية المستوحاة من الطبيعة تنتمي إلي مجموعة الخوارزميات التحسينية التي تتبنى في مقاربتها الخوارزمية، لحل المشاكل، مفهوم الساكنة. أي أن جميع الحلول المحتملة التي تم معالجتها تنتمي لجيل واحد من الأجيال على الأقل، على مدار دورات التكرار.
صممت هذه الخوارزميات لمحاكاة أسلوب بحث نحل المستعمرات عن موارد الطعام. أي حقول الأزهار التي تحتوي على الرحيق الذي تتغدى عليه. وليس النحل البري الذي ينفرد بذاته ويعيش مستقلا عن أي تجمع، فلكل طريقته.
تستخدم هذه الخوارزمية في حل المشاكل المستمرة و المشاكل المتقطعة، مثل خوارزميات الساكنة الأخرى. ولتنفيد هذا تقوم ببحث محلي بجوار الحلول المحلية، المكتشفة بواسطة بحث شامل و غير مركز.
يشترط استخدام هذه الخوارزمية القدرة على حساب الفرق بين الحلول، أي المسافة بين نقاط فضاء الحلول المحتملة. وبالطبع بدون الحاجة لحساب أي اشتقاقات أو تدرجات. وفي هذا المقال سنركز على مراجعة ألية بحث نحل المستعمرات عن الرحيق، وكذلك ألية عمل بعض خوارزميات النحل ومتحوراتها.
محتويات المقال :
تعيش نحلات العسل في مستعمرات منظمة. تخزن العاملات منها العسل الذي تنتجه فيها وتتغذى عليه من أجل أن تحيا وتستمر. هذه الحياة التي تقضيها في العمل قائمة على عدد من المتطلبات والتي من أجل تحقيقها تحتاج النحلات للتواصل في ما بينها. فيتم التواصل، كما النمل وعدد من الحيوانات و الحشرات الأخرى، بواسطة الفيرومونات. لكن إضافة لهذه الطريقة التقليدية، تمتاز النحلات باستخدامها للرقص لتحقيق المزيد من التواصل. فباستخدام رقصات محددة تستطيع النحلات أن تمرر فيما بينها معلومات حساسة ومهمة عن اتجاه وقيمة مصدر الطعام. اتجاه الجسم يشير إلي مصدر الطعام، و الصوت الناتج خلال الرقصة يدل على مدى أهمية وقيمة هذا المصدر.
كما هو واضح، فآلية التواصل بالفيرومونات جد مهمة في حياة النحلة وحاسمة في استمرارية المستعمرة. فباستخدام مركب كميائي معين من الفيرومونات يمكن أن تحفز النحلة مجموعتها لرد فعل على هجوم ما. إضافةً، فعند إيجاد النحلة لمصدر رحيق معين، وتعود حاملة إياه، تصدر مجموعة من الفيرومونات كإشارة. ومن ثم تقوم النحلة برقصتها لتحديد المكان والجودة للنحلات المجاورة.
عند تعدد مصادر الرحيق، أثبتت الدراسات أن السلوك المنظم للمستعمرة قادر على توزيع النحلات الجامعة على هذه المصادر بطريقة فعالة. وذلك من أجل جمع أقصى قدر من الرحيق. فكي تستطيع المستعمرة النجاة خلال فصل الشتاء، يتوجب جمع ما لا يقل عن 15 كيلوغرام من العسل أو ما قد يصل إلي 50 كيلوغرام، حسب النوع والمنطقة.
هنا تبرز أهمية قدرة النحل على توزيع أفراده لجمع الرحيق من وجهة نظر تطورية. فإن لم تجمع ما يكفي وتنظم مجهوداتها بالطريقة المثلى، فلن تبقى إلي أن يحل فصل الربيع. وبالتالي، ما يجعل من موضوع أليات عمل مستعمرات النحل هذه بمختلف أنواعها مصدرًا هامًا نستطيع استحضاره ومحاكاته لإيجاد مختلف الطرق لحل ما يوجهنا من مشاكل هندسية وخصوصًا المشاكل التحسينية. وقد تم تصميم عدد كبير من الخوارزميات التحسينية انطلاقًا من مفهوم مستعمرة النحل، وفق هذه الميكانيزمات، وطرق العمل الفريدة والفعالة.
على مدار العقدين الماضيين، بدأت خوارزميات النحل تنبثق كخوارزميات تحسينية واعدة في مجال التحسين. لكن بعد البحث نجد أنه من الصعب تحديد التاريخ الدقيق لأول صياغة لهذه الخوارزميات. بحيث تم تطويرها من طرف عدد من الباحثين في أبحاث مستقلة، وفي مختلف أنحاء العالم، على مدار السنوات.
لكن انطلاقا من الأدبيات العلمية والأوراق البحثية نجد أن خوارزمية نحل العسل Honeybee Algorithm قد تم تطويرها سنة 2004 على يد كريغ توفي Craig A. Tovey من معهد جورجيا للتكنولوجيا، و سونيل نكراني Sunil Nkarani من جامعة أوكسفورد. وفي أواخر 2004 وبداية 2005 طور عالم الرياضيات والحاسوب شين شي يانغ Xin She Yang من جامعة كامبريدج خوارزمية النحلة الافتراضية Virtual Bee Algorithm، لحل مشاكل التحسين العددية. هذه الخوارزمية قادرة على مواجهة المشاكل المستمرة و المتقطعة.
وفي وقت لاحق من سنة 2005 طور حداد Haddad و أفشار Afshar وزملاءهما خوارزمية تحسين تزاوج نحل العسل Honeybee mating Optimization. والتي استخدمت في تصميم الخزانات والتعنقد clustering. وفي نفس الفترة الزمنية طور كارابوجا D. Karaboga خوارزمية النحل الاصطناعية Artificial Bee Algorithm للتحسين العددي.
يتم توجيه النحل العامل في خوارزمية نحل العسل Honeybee Algorithm نحو عدد من مصادر الطعام. من أجل الحصول على أكبر كمية من الرحيق. عملية التوجيه هذه تقوم على عدد من العوامل، مثل تركيز الرحيق في المنطقة المعنية وكذلك قربها من المستعمرة. وسنجد أن عملية التوجيه هذه مشابهة لعملية توزيع خوادم استضافة الويب allocation of web-hosting servers على الإنترنت. وبالتالي، كان هذا المشكل من أوائل المسائل التي تم حلها بواسطة خوارزميات النحل، وبالضبط خوارزمية نحل العسل.
باعتبار Wi(j) قوة تذبذب رقصة النحلة i خلال خطوة التنفيد j، نجد أنه من الممكن تحديد احتمالية اتباع نحلة معينة للمصدر المشار إليه بعد مشاهدة الرقصة بواسطة عدد من الصيغ وذلك اعتمادًا على المتحور المستعمل، فنجد الصيغة المطبقة في خوارزمية نحل العسل كالتالي:
يمثل العدد الصحيح الطبيعي nf عدد النحلات العاملة الباحثة، و t دورة البحث الحالية. وبالتالي عدد النحلات المراقبة للرقصات هو N-nf أي مجموع النحلات ناقص عدد النحلات غير المتفرغة، بسبب بحثها.
يمكن كذلك تحديد معادلة لاحتمالية الاستكشاف ممثلة بصيغة إحصائية أخرى، فنجد الصيغة الغاوسية الجديدة:
عند عدم رقص أي نحلة نجد:
ما يعني أن النحلات ستبحث عشوائيًا.
في متحورات أخرى، عند تطبيقها لحل المشاكل المتقطعة مثل مشاكل الجدولة، تقوم النحلة الباحثة بأداء رقصة معينة في مدة زمنية محددة τ = γ fp. بحيث تعبر fp عن ربحية أو غنى منطقة الطعام، أي حقل الزهور وتركيز الرحيق بها. بينما γ هي معامل تحجيم للتحكم في الفترة الزمنية للرقصة. بالطبع الربحية مرتبطة بالدالة الهدف.
بالإضافة لهذا، يتم تصنيف كل مسار بطريقة ديناميكية. فنجد أن مسار أكبر عدد من النحلات هو المسار المفضل للخلية. كما أن احتمالية اختيار طريق بين نقطتين في مشكل توجيهي معين يمكن أن تتم وفق الصيغة التالية:
على غرار خوارزميات مستعمرة النمل، فخوارزمية نحل العسل HBA، جد فعالة في التعامل مع مشاكل التحسين المتقطعة مثل مشاكل التوجيه والجدولة. لكن في مواجهة التحسين المستمر، فهي غير مباشرة، وبالتالي في حاجة إلى بعض التعديلات.
طورت خوارزمية النحلة الافتراضية Virtual Bee Algorithm من طرف Xin She Yang سنة 2005 من أجل مواجهة المشاكل المستمرة والمتقطعة. بحيث تتشابه في عدد من خصائصها خوارزمية استمثال عناصر السرب Particle Swarm Optimization أكثر من خوارزميات النحل الأخرى، ويقصد ب”الاستمثال” التحسين. في هذه الخوارزمية تمثل الدالة الهدف قيم الرحيق الافتراضية، بينما الحلول المحتملة هي مواقع غنية، بكميات متفاوتة، بالرحيق. كما أن قوة الرقصة تعتمد فقط على تركيز الرحيق، والذي يمكن اعتباره هنا معاملًا للملائمة fitness للحلول المحتملة.
في مواجهة المشاكل المتقطعة يتم ربط الدالة الهدف، مثل دالة تحديد الطريق الأقصر، مباشرة بربحية عملية استكشاف الرحيق. والتي بدورها ترتبط عملية استكشاف الرحيق، بقوة رقصة النحلة.
انطلاقًا من هذا، نلاحظ وجود تشابه كبير بين هذه الخوارزمية وسابقتها، خوارزمية نحل العسل. لكن رغم وجود هكذا تشابه، إلا أنه عند تدقيق النظر في آلية بحث النحلات، نجد الاختلافات. إذ أنها لا تحتاج للعودة للخلية من أجل إخبار نظيراتها بما اكتشفته، بحيث يمكنها بث محتوى الرقصة عن بعد لجميع النحلات. وبالتالي يصبح الحل الأمثل الحالي معلومًا عند كل نحلة باحثة ومؤثرًا على عملية اتخاد القرار الفردية. فنجد من هذا إختلافًا بنيويًا، لا يجعل منها تختلف عن خوارزمية نحل العسل فحسب، بل وتختلف كذلك عن كل خوارزميات النحل الأخرى.
في هذه الخوارزمية، خوارزمية مستعمرة النحل الاصطناعية Artificial Bee Colony Algorithm، يتم تقسيم نحلات المستعمرة لثلاث أنواع. النحلات العاملة، والنحلات الكشافة، والنحلات المراقبة. فنجد لكل مصدر طعام نحلة عاملة واحدة تبحث محليًا عن الحل المحلي الأمثل. فيما يحاكي عملية استخراج الرحيق والانتقال من زهرة إلي أخرى. كما أن التخلي عن مصدر طعام معين، عند نضوبه أو انخفاض ربحيته، يعني مباشرة تحول نحلته العاملة إلي نحلة كشافة. فتبحث النحلة الكشافة بشكل عشوائي عن مصادر طعام أخرى.
تتشارك النحلات العاملة والنحلات الكشافة معلوماتها مع النحلات المراقبة، والتي تتمركز في الخلية. هذه الأخيرة، فيما بعد، تقرر منطقة بحثها متخذتةً بعين الاعتبار المعلومات التي وصلت إليها. لتصبح هي الأخرى نحلات عاملة وتنضم للفريق.
لكونها خوارزميات ناجحة، يمكن تطبيقها لحل مختلف أنواع المشاكل التحسينية. فنجد خوارزميات النحل حاضرة في كل مجالات التحسين الحوسبي فمن تطبيقاتها نجد:
وتبقى التطبيقات الحالية كثيرة، والأخرى الممكنة لا حصر لها فالبحث لا زال جاريًا، والأفق مفتوح.
مصادر
لا تزال أفكار نيتشه الفلسفية يتردد صداها في المجتمع المعاصر، وتتحدى فهمنا للأخلاق ومكانتها في…
تخيل فريقًا من العلماء الرواد يعملون بلا كلل لكشف أسرار الدماغ البشري. إنهم في سعيهم…
في عالم وسائل التواصل الاجتماعي، تظهر الصيحات وتختفي، لكن بعضها يجعلك تتساءل: ما السبب وراء…
الصداع تجربة إنسانية عالمية، وعلى الرغم من انتشاره إلا أن الأسباب الكامنة وراءه لا تزال…
إن فهم كيف بدأت الحياة وتطورت على الأرض هو السؤال الذي أذهل البشر على مر…
يصادف في شهر أغسطس الذكرى السنوية الثالثة لانسحاب الولايات المتحدة من أفغانستان وعودة طالبان إلى…
View Comments
شكرا لكم.