خوارزمية النحل

📅 آخر تحديث: ٢٢ يوليو ٢٠٢٦
✍️ نُشر في: ٢٢ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
تحاكي خوارزمية النحل سلوك البحث عن الطعام لدى نحل العسل.

في علوم الحاسوب وبحوث العمليات ، تُعدّ خوارزمية النحل خوارزمية بحث قائمة على السكان، طُوّرت بواسطة فام وغنبارزاده وآخرين عام 2005. [ 1 ] تُحاكي هذه الخوارزمية سلوك البحث عن الغذاء لدى خلايا نحل العسل. في نسختها الأساسية، تُجري الخوارزمية نوعًا من البحث في الجوار مُدمجًا مع البحث الشامل، ويمكن استخدامها في كلٍّ من التحسين التوافقي والتحسين المستمر . الشرط الوحيد لتطبيق خوارزمية النحل هو تحديد مقياس للمسافة بين الحلول. وقد أُثبتت فعالية خوارزمية النحل وقدراتها المحددة في عدد من الدراسات. [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ]

استعارة

تستطيع خلية نحل العسل أن تمتد لمسافات طويلة (أكثر من 14  كم) [ 7 ] وفي اتجاهات متعددة في آن واحد لجمع الرحيق أو حبوب اللقاح من مصادر غذائية متنوعة (بقع الزهور). ويقوم جزء صغير من الخلية بالبحث باستمرار في البيئة المحيطة عن بقع زهور جديدة. تتحرك هذه النحلات الكشافة عشوائيًا في المنطقة المحيطة بالخلية، لتقييم جدوى (صافي إنتاج الطاقة) مصادر الغذاء التي تصادفها. [ 7 ] وعند عودتها إلى الخلية، تضع النحلات الكشافة الغذاء الذي جمعته. أما النحلات التي عثرت على مصدر غذاء ذي جدوى عالية، فتتجه إلى منطقة في الخلية تُسمى "ساحة الرقص"، وتؤدي طقوسًا تُعرف برقصة الاهتزاز . [ 8 ] ومن خلال رقصة الاهتزاز، تُبلغ النحلة الكشافة النحلات الأخرى بموقع اكتشافها، فتنضم إلى استغلال بقعة الزهور. وبما أن طول الرقصة يتناسب مع تقييم النحلة الكشافة لمصدر الغذاء، يتم تجنيد المزيد من النحلات الباحثة عن الطعام لجمع أفضل بقع الزهور. بعد الرقص، يعود النحل الكشاف إلى مصدر الغذاء الذي اكتشفه لجمع المزيد. وطالما تم تقييم مصادر الغذاء الغنية على أنها مربحة، فإن النحل الكشاف سيعلن عنها عند عودته إلى الخلية. وقد يقوم النحل الباحث عن الطعام الذي تم تجنيده برقصة اهتزازية أيضًا، مما يزيد من التجنيد في مناطق الأزهار الغنية بالعناصر الغذائية. وبفضل هذه العملية التحفيزية الذاتية، تستطيع خلية النحل تحويل تركيز جهود البحث عن الطعام بسرعة إلى مناطق الأزهار الأكثر ربحية. [ 7 ]

الخوارزمية

تحاكي خوارزمية النحل [ 2 ] [ 9 ] استراتيجية البحث عن الغذاء لدى نحل العسل لإيجاد الحل الأمثل لمسألة التحسين. يُنظر إلى كل حل مرشح على أنه مصدر غذاء (زهرة)، ويُستخدم مجتمع (مستعمرة) من n من النحلات للبحث في فضاء الحلول. في كل مرة تزور فيها نحلة اصطناعية زهرة (تهبط على حل)، فإنها تُقيّم جدواه (كفاءته).

تتألف خوارزمية النحل من إجراء تهيئة ودورة بحث رئيسية تُكرر لعدد T من المرات، أو حتى يتم العثور على حل ذي جودة مقبولة. تتكون كل دورة بحث من خمسة إجراءات: التوظيف، والبحث المحلي، وتقليص الجوار، والتخلي عن الموقع، والبحث الشامل.

الشفرة الزائفة لخوارزمية النحل القياسية [ 2 ] 1 لـ i = 1، ...، ns أنا الكشفية [i] = التهيئة_الكشافة () ii flower_patch[i] = Initialise_flower_patch(scout[i]) 2. كرر حتى يصبح شرط_الإيقاف = صحيح التوظيف ii لـ i = 1، ...، na 1 flower_patch[i] = Local_search(flower_patch[i]) 2 flower_patch[i] = Site_abandonment(flower_patch[i]) 3 flower_patch[i] = Neighbourhood_shrinking(flower_patch[i]) iii لكل i = nb، ...، ns 1 flower_patch[i] = Global_search(flower_patch[i])}

في روتين التهيئة، يتم وضع ns من النحل الكشاف عشوائيًا في فضاء البحث، ويقوم بتقييم مدى ملاءمة الحلول التي يهبط عليها. لكل حل، يتم تحديد منطقة مجاورة (تسمى رقعة الزهور).

في عملية التجنيد، يقوم الكشافة الذين زاروا أفضل المواقع ( nb ≤ ns ) بتجنيد الباحثين عن الطعام للبحث في المناطق المحيطة بأفضل المواقع. يقوم الكشافة الذين عثروا على أفضل المواقع ( ne ≤ nb ) بتجنيد nre من الباحثين عن الطعام، بينما يقوم الكشافة الآخرون (nb - ne) بتجنيد nrb ≤ nre من الباحثين عن الطعام. وبالتالي، يعتمد عدد الباحثين عن الطعام المجندين على ربحية مصدر الغذاء.

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

كما هو الحال في مستعمرات النحل البيولوجية، [ 7 ] يقوم عدد قليل من النحل الكشاف باستكشاف فضاء الحلول بحثًا عن مناطق جديدة ذات كفاءة عالية (بحث شامل). وتعيد عملية البحث الشامل تهيئة آخر ns - nb من رقع الزهور بحلول مُولّدة عشوائيًا.

في نهاية دورة بحث واحدة، يتألف مجتمع النحل الكشاف من ns نحلة كشافة: nr نحلة كشافة ناتجة عن إجراء البحث المحلي (قد يكون بعضها قد أُعيد تهيئته بواسطة إجراء هجر الموقع)، و ns - nb نحلة كشافة ناتجة عن إجراء البحث العالمي. إجمالي حجم مستعمرة النحل الاصطناعية هو n = ne • nre + ( nb - ne ) • nrb + ns نحلة (نحلات البحث عن الطعام في المواقع النخبوية + نحلات البحث عن الطعام المتبقية في أفضل المواقع + النحل الكشاف).

المتغيرات

بالإضافة إلى خوارزمية النحل الأساسية، [ 9 ] توجد عدة نسخ محسّنة أو هجينة منها، يركز كل منها على معالجة بعض أوجه القصور في الخوارزمية الأساسية. تشمل هذه النسخ (على سبيل المثال لا الحصر) خوارزمية النحل الضبابية أو المحسّنة (EBA)، [ 10 ] وخوارزمية النحل المجمعة (GBA)، [ 5 ] وخوارزمية النحل المعدلة الهجينة (MBA)، [ 11 ] وما إلى ذلك. فيما يلي كود MATLAB الزائف لخوارزمية النحل المجمعة (GBA) [ 5 ] .

دالة GBA %% تعيين معلمات المسألة maxIteration = ..; % عدد التكرارات (مثلاً 1000-5000) maxParameters = ..; % عدد متغيرات الإدخال min = [..] ; % مصفوفة بحجم maxParameters لتحديد القيمة الدنيا لكل مُدخل max = [..] ; % مصفوفة بحجم maxParameters لتحديد القيمة القصوى لكل مُدخل%% ضبط معلمات خوارزمية النحل المُجمّع (GBA) R_ngh = ..; % نصف قطر رقعة البحث عن النحل في المجموعة الأولى (مثال: 0.001 - 1) n = ..; % عدد النحل الكشاف (مثال: 4-30) nGroups = ..; % عدد المجموعات، باستثناء المجموعة العشوائية%% إعدادات المعلمات التلقائية لخوارزمية GBA k = 3 * n / (( nGroups + 1 ) ^ 3 - 1 ); % معلمة GBA لتعيين عدد النحل الكشاف في كل مجموعة groups = zeros ( 1 , nGroups ) ; % مصفوفة لحفظ عدد النحل الكشاف لكل مجموعة recruited_bees = zeros ( 1 , nGroups ); % مصفوفة لحفظ عدد النحل المجند لكل مجموعة a = ((( max - min ) ./ 2 ) - R_ngh ) ./ ( nGroups ^ 2 - 1 ); % معلمة GBA لتعيين أنصاف أقطار الجوار b = R_ngh - a ; % معلمة GBA لتعيين أنصاف أقطار الجوار for i = 1 : nGroups % لكل مجموعة groups ( i ) = floor ( k * i ^ 2 ) ; % تحديد عدد النحل الكشاف في كل مجموعة if groups ( i ) == 0 groups ( i ) = 1 ; يجب أن يكون هناك نحلة كشافة واحدة على الأقل لكل مجموعة . نحدد عدد النحل المجند لكل مجموعة . نحدد نصف قطر رقعة البحث لكل مجموعة . نخصص النحل المتبقي ( إن وجد ) للبحث العشوائي . نتأكد من أن النتيجة ليست سالبة .​​​​%% تهيئة مصفوفة السكان population = zeros ( n , maxParameters + 1 ); % مجموعة من n نحلة تتضمن جميع متغيرات الإدخال ولياقتها for i = 1 : n population ( i , 1 : maxParameters ) = generate_random_solution ( maxParameters , min , max ); % تهيئة عشوائية لمتغيرات maxParameters بين max و min population ( i , maxParameters + 1 ) = evalulate_fitness ( population ( i , :)); % تقييم لياقة كل حل وحفظه في الفهرس الأخير من مصفوفة السكان endsorted_population = sortrows ( population ); % فرز السكان بناءً على لياقتهم البدنية%% تكرارات خوارزمية النحل المُجمّع for i = 1 : maxIteration % الحلقة الرئيسية لخوارزمية النحل المُجمّع beeIndex = 0 ; % تتبع جميع النحل (أي، الرقع) for g = 1 : nGroups % لكل مجموعة من النحل الكشاف for j = 1 : groups ( g ) % استغلال كل رقعة داخل كل مجموعة beeIndex = beeIndex + 1 ; % زيادة العداد لكل رقعة for i = 1 : recruited_bees ( g ) % لكل نحلة مُجنّدة من المجموعة solution = bee_waggle_dance ( sorted_population ( beeIndex , 1 : maxParameters ), ngh ( g )); % البحث في الجوار حول الرقعة/الحل المُختار ضمن نصف قطر ngh fit = evaluate_fitness ( solution ); % تقييم مدى ملاءمة الحل الذي تم العثور عليه مؤخرًا إذا كانت الملاءمة < sorted_population ( beeIndex , maxParameters + 1 ) % مسألة تصغير: إذا عثر النحل المُستَقبِل على موقع/رقعة/حل أفضل، فإن sorted_population ( beeIndex , 1 : maxParameters + 1 ) = [ solution ( 1 : maxParameters ), fit ]; % نسخ الحل الجديد وملاءمته إلى مصفوفة السكان المُرتّبة end end end endfor i = 1 : group_random % بالنسبة للنحل العشوائي المتبقي beeIndex = beeIndex + 1 ; solution ( beeIndex , 1 : maxParameters )= generate_random_solution ( maxParameters , min , max ); % توليد حل عشوائي جديد عند الفهرس beeIndex solution ( beeIndex , maxParameters + 1 )= evaluate_fitness ( solution ); % تقييم لياقته sorted_population ( beeIndex ,:) = [ solution ( 1 : maxParameters ), fit ]; % نسخ الحل العشوائي الجديد ولياقته إلى مصفوفة السكان المرتبة endsorted_population = sortrows ( sorted_population ); % فرز السكان بناءً على لياقتهم Best_solution_sofar = sorted_population ( 1 ,:);عرض ( 'الأفضل:' ); عرض ( أفضل_حل_حتى_الآن ); % عرض أفضل حل للتكرار الحالي نهاية % نهاية الحلقة الرئيسية لـ GBA نهاية % نهاية الدالة الرئيسية%% دالة رقصة النحلة المتذبذبة function new_solution = bee_waggle_dance ( solution, ngh, maxParameters ) new_solution ( 1 : maxParameters ) = ( solution - ngh ) + ( 2 * ngh .* rand ( 1 , maxParameters )); end

انظر أيضاً

مراجع

  1. ↑ فام دي تي، غانبارزاده أ، كوتش إي، أوتري إس، رحيم إس وزيدي إم. خوارزمية النحل. مذكرة فنية، مركز هندسة التصنيع، جامعة كارديف، المملكة المتحدة، 2005.
  2. 1 2 3 Pham, DT, Castellani, M. (2009), The Bees Algorim – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems . Proc. ImechE, Part C, 223(12), 2919-2938.
  3. ↑ Pham, DT and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Continuous Optimisation Algorithms , Soft Computing, 1-33.
  4. ↑ Pham, DT and Castellani, M. (2015), A comparison study of the bees algorithm as a tool for function optimisation , Cogent Engineering 2(1), 1091540.
  5. 1 2 3 نسرينبور، إتش آر، ماسا بافاني، أ.، تشنهلاب، م.، (2017)، خوارزمية النحل المجمعة: نسخة مجمعة من خوارزمية النحل ، الحواسيب 2017، 6(1)، 5؛ ( doi : 10.3390/computers6010005 )
  6. ↑ بارونتي، لوكا وكاستيلاني، ماركو وفام، د. (2020)، تحليل آليات البحث في خوارزمية النحل. ، الحوسبة السربية والتطورية. 59. 100746. 10.1016/j.swevo.2020.100746
  7. 1 2 3 4 تيريشكو ف.، لونجاروف أ.، (2005) اتخاذ القرارات الجماعية في ديناميكيات البحث عن الطعام لدى نحل العسل. مؤرشف في 2014-02-01 على موقع Wayback Machine . مجلة الحوسبة ونظم المعلومات، 9(3)، 1-7.
  8. ↑ فون فريش، ك. (1967) لغة الرقص وتوجه النحل. مطبعة جامعة هارفارد، كامبريدج، ماساتشوستس.
  9. 1 2 Pham DT, Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., The Bees Algorithm, A Novel Tool for Complex Optimisation Problems , Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier, pp. 454-459, 2006.
  10. ↑ فام دي تي، حاج درويش أ.، (2008)، أ. الاختيار الضبابي لمواقع البحث المحلية في خوارزمية النحل . وقائع مؤتمر آلات وأنظمة الإنتاج المبتكرة (IPROMS 2008)
  11. ↑ فام كيو تي، فام دي تي، كاستيلاني إم، خوارزمية النحل المعدلة وطريقة إحصائية لضبط معاييرها. وقائع مؤسسة المهندسين الميكانيكيين (ImechE)، الجزء الأول: مجلة هندسة النظم والتحكم، 2011 ( doi : 10.1177/0959651811422759 )