خوارزمية مستعمرة النمل (ACO)
المعلوماتية >>>> برمجيات
Image: https://biology.stackexchange.com/questions/56654/how-do-ants-follow-each-other
أجرى "دينيو بورغ- Deneubourg" وآخرون تجربةً تعرف باسم "تجربة الجسر المزدوج Double Bridge Experiment"؛ إذ رُبِطت مستعمرة النمل بمصدر غذائي بواسطة جسرين متساويي الطول. في البداية، استكشف النمل محيط المستعمرة وسار باتجاهات عشوائية حتى وصل في النهاية إلى مصدر الغذاء؛ إذ يودع النمل الفرمون على الأرض على طول الطريق التي سلكتها بين مصدر الغذاء والمستعمرة. وفي أثناء البحث، اختار النمل أحد الجسرين عشوائيًّا، وعلى الرغم من أنّ الجسرين متساويي الطول؛ سوف يكون تركيز الفيرومون على الجسرين مختلفًا -ولو قليلًا- بسبب التقلبات العشوائية (random fluctuations)، وسيجلب ذلك مزيدًا من النمل إلى هذا الجسر، الذي بدوره سيسبب ظهور كمية أكبر من الفيرومون.
في النهاية سيصبح هذا الجسر أكثر جاذبية بسبب كمية الفرمون العالية مقارنةً بالجسر الآخر، ومع مرور الزمن ستستعمل المستعمرة بأكملها هذا الجسر للوصول إلى الغذاء (2).
خوارزمية مستعمرة النمل لحساب الأمثليات (ACO)
تعد خوارزمية ACO جزءًا من *الخوارزميات التجريبية (Metaheuristic algorithms)؛ إذ يمكن استخدامها لإيجاد حلول تقريبية لمشاكل الأمثلية التوافقية (combinatorial optimization problems)، وتعد من مناهج الذكاء الحسابي التي استخدمها الدكتور Marco Dorigo أولَ مرة بالتعاون مع Alberto Colorni و(Vittorio Maniezzo (1.
في ACO، تبحث مجموعة من الوكلاء تسمى النمل الاصطناعي (artificial ants) عن حلول جيدة لمشكلة أمثليات معينة. في البداية؛ تحوَّل المشكلة إلى مسألة العثور على أفضل مسار في مخطط بياني موزون (weighted graph) يحوي عُقدًا (nodes) وخطوطًا (edges). يبني النمل الحلول تراكميًّا من خلال الانتقال على المخطط البياني؛ إذ يبدأ النمل من نقطة البداية (المستعمرة)، ويحاول على نحو متكرر بناءَ حل كامل (الوصول من المستعمرة إلى مصدر الغذاء)، ويتضمن الحل مجموعةَ الخطوط (أو العقد حسب نوع المسألة) التي سيمر عليها النمل في طريقه إلى مصدر الغذاء؛ إذ تتحرك كل نملة (تخطو خطوة واحدة) من عقدة A إلى عقدة أخرى B بحيث تجعل الحل الجزئي أكثر اكتمالًا (المقصود هنا الاقتراب من مصدر الغذاء)، وتُختار العقدة التالية B على نحو احتمالي، وتنحاز القاعدة الاحتمالية هنا إلى قيم الفرمون والمعلومات الإرشادية (heuristic information) المرتبطة بالخط بين العقدتين A وB، فكلما ارتفعت قيمة الفرومون والقيمة الإرشادية المرتبطة بالخط؛ زادت احتمالية انتقال النملة إلى هذه العقدة B مرورًا بهذا الخط. علمًا أنّ كل نملة تحتفظ بالمسار الذي سارت عليه، وتُختار الخطوط في الخطوات اللاحقة بحيث لا تؤدي إلى عقد زِيرَت من قبل.
كذلك تجري الخوارزمية عملياتٍ حسابية متزامنة لمجموعة العملاء الذين يتحركون على نحو غير متزامن (مستعمرة من النمل) عبر العقد، وتُحدَّث معلومات الفرمون للخطوط في نهاية كل تكرار، وذلك عندما تكمل جميع النملات حلولها؛ إذ يُزاد مستوى الفرمون المرتبط بمكونات الحلول (solution components) (وهي الخطوط التي تشكل جزءًا من الحل) بناءً على إذا ما كان الحل "جيدًا"، أو إنقاصها في حالة كان الحل "سيئًا" (1).
في التكرارات اللاحقة، تتعلق الحركة المستقبلية للنملات بجودة الحلول التي حُصِل عليها. ويُتّخذ قرار الانتقال من عقدة إلى عقدة أخرى محليًّا وعشوائيًّا بالاعتماد على معلمتين (parameters) تسمّيان: الأثر (trail)، والجاذبية (attractiveness).
وبالمحصلة، إنّ معلومات الفرمون الموجودة على الخطوط -والتي تُعدَّل في كل تكرار- ستؤدي دورًا مهمًّا في توجيه البحث الذي سيجريه النمل مستقبلًا، وتستمر الخوارزمية بالعمل على نحو متكرر حتى يُستوفى معيار الإنهاء (1,3).
تحتوي خوارزمية ACO على إجرائين مهمّين أيضًا، وهما (1):
بعض تطبيقات خوارزمية ACO
هوامش:
* الخوارزميات التجريبية: هي خوارزميات تبني الحل تراكميًّا بإحدى الطريقتين (1):
المصادر:
2. Deneubourg J, Aron S, Goss S, Pasteels J. The self-organizing exploratory pattern of the argentine ant | SpringerLink [Internet]. 1990 [cited 2020 Jun 24]. Available from: هنا;
3. Dorigo M. Ant colony optimization | Scholarpedia [Internet]. 2007 [cited 2020 Jun 24]. Available from: هنا
4. Gambardella L, Dorigo M. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem | INFORMS Journal on Computing [Internet]. Pubsonline.informs.org. 2000 [cited 24 June 2020]. Available from: هنا
5. Bullnheimer B, Hartl R, Strauss C. Applying the ANT System to the Vehicle Routing Problem | SpringerLink [Internet]. 1999 [cited 24 June 2020]. Available from: هنا
