خوارزمية مستعمرة النمل (ACO)

تعود فكرة خوارزمية مستعمرة النمل لحساب الأمثليات (Ant    Colony    Optimization (ACO  إلى طريقة الوصول إلى المصدر الغذائي التي تستخدمها بعض أنواع النمل؛ إذ يضع النمل مادةً تسمى "فرمون- pheromone" على الأرض من أجل تحديد المسار الأفضل الذي يجب أن يتبعه الآخرون. يدرك النمل وجود آثار الفرمون في عدة اتجاهات فيتّبع المسارات التي تحوي تركيزًا أعلى منه، ويتمكن النمل بفضل هذه التقنية من نقل الطعام إلى مستعمرته بطريقة فعالة (المقصود هنا أن الخط الذي يسير عليه النمل هو أقصر مسار بين مصدر الغذاء والمستعمرة) (1).

أجرى "دينيو بورغ- 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):

• تلاشي الأثر (trail evaporation) أو النسيان: تقل قيمة الأثر بمرور الوقت، وبالتالي تُحذَف أو تُنسَى الخطوط التي لم يعد يختارها النمل في أثناء مسيرته.
• الإجراءات الخفية (daemon actions): وتستخدم لتنفيذ بعض الإجراءات المركزية التي لا يمكن أن ينفّذها النمل فرديًّا؛ مثل استدعاء إجراء الأمثلية المحلي، أو تحديث المعلومات العامة التي تسهم بتحديد ما إذا كان من الممكن أن تُحيّز عملية البحث من منظور عام.

بعض تطبيقات خوارزمية ACO

1. مشكلة الترتيب التسلسلي (Sequential ordering problem):  مثل مسألة البائع الجوال المتماثلة (symmetric) -الذهاب والإياب على الطريق نفسها لهما التكلفة نفسها- وغير المتماثلة (asymmetric) -قد تختلف تكلفة الذهاب عن تكلفة الإياب للطريق نفسها-، فالمطلوب هو أداء جولة مغلقة تشتمل على الحد الأدنى من التكلفة لزيارة كل مدينة مرة واحدة  (4).
2. مشكلة توجيه المركبات (Vehicle routing problems): حيث تخدّم مجموعة من المركبات الموجودة في مستودع ما مجموعةً من العملاء قبل العودة ثانيةً إلى المستودع، والمطلوب هو تقليل عدد المركبات المستخدمة والمسافة الإجمالية التي تقطعها المركبات؛ إذ تشمل المسألة مجموعةً من القيود؛ مثل سعة المركبة، وازدحام الشوارع الذي يؤثر في زمن المرور بالشارع، والحد الأقصى لطول الجولة، وغيرها من القيود (5).

هوامش:

* الخوارزميات التجريبية: هي خوارزميات تبني الحل تراكميًّا بإحدى الطريقتين (1):

• تبدأ من العدم (null solution) وتضيف العناصر حتى الحصول على حل جيد كامل.
• تبدأ بحل كامل وتعدّل العناصر تكراريًّا للحصول على حل أفضل.

المصادر: