قوة النمل وخوارزميات مستعمرة النمل

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

إن هذه القدرة كانت صاعقة كفاية لحث علماء الحاسوب في التسعينات للتفكير بمحاكاة سلوك النمل في برامج الحاسوب المصممة لحل المشاكل المعقدة.

في وقتنا الحالي، تستخدم خوارزميات مستعمرة النمل ant colony optimisation algorithms – ACOs بكثرة لحل المشاكل التي تحتوي على عدة عناصر تحتاج للدمج بالطريقة المثلى. سواء كانت المشكلة اختيار طرق التوصيل لأسطول من الشاحنات أو جدولة مواعيد الأطباء في مستشفى.

كيف يقوم النمل بذلك؟

يتواصل النمل باستخدام مواد كيميائية تدعى الفيرمونات (pheromones). يقول ماركو دوريغو ( Marco Dorigo) من جامعة بروكسل الحرة (Université Libre de Bruxelles)، والذي اخترع خوارزميات مستعمرة النمل في أطروحة الدكتوراة وشارك في تأليف كتاب مهم ومؤثر عن هذا الموضوع:

“عندما يتحرك النمل، يترك وراءه فيرمونات على الأرض. وإذا شعر بوجود طريق مسبق يحتوي عليهم، فهنالك احتمالية أعلى لتتبعهم الطريق القديم على سلوكهم اتجاهًا جديدًا.”

إذا فضّل ما يكفي من النمل طريقًا معينًا، تنشأ حلقة تغذية راجعة: ستجذب الفيرمونات المتروكة المزيد من النمل إلى الطريق، والذي بدوره سيرفع تركيز الفيرمونات الموجودة، مما سيجذب المزيد من النمل ثانية، وهكذا دواليك.

في تجربة مثيرة للاهتمام، أظهر علماء البيولوجيا أن هذه الآلية  قادرة وحدها على جعل النمل كجماعة يجدون الطريق الأقصر بين العش والطعام. في عام 1990، قدم جان لويس دينوبورج (Jean-Louis Deneubourg) وزملاؤه طريقين للنمل يصلان بين عشهم ومنطقة لم يكتشفوها مسبقًا تحتوي على الطعام. في إحدى التجارب كان أحد الطريقين أطول بمرتين من الآخر، وقد اختار النمل الطريق الأقصر في نهاية المطاف دائمًا.

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

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

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

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

كل هذا يعد مثالًا على ما يسمى “التنسيق الوصمي” (stigmergy) حيث يترك الأفراد (في هذه الحالة النمل) علامات في البيئة تقود أفعال الأفراد الآخرين. بالتالي، تنشأ حلقة تغذية راجعة تتسبب في ظهور سلوك يبدو متناسق ومنهجي (اختيار طريق سريع في مثال النمل).

لماذا يقوم البشر بذلك؟

يقول دوريغو:

“يحل النمل مسألة أمثلية (optimisation problem) في تجربة دوينبورغ. بالنسبة للإنسان، مسألة الأمثلية هذه بسيطة؛ لأننا عندما نختار بين طريقين نعرف فورًا الأقصر. ولكن هناك العديد من المشاكل الأخرى على أرض الواقع يمكن تمثيلها كمسائل استمثال توافقي (combinatorial optimisation problems).”

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

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

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

كيف تنجز الحواسيب هذا العمل؟

تقبع خلف أمثلية مستعمرات النمل فكرة بناء خوارزميات تقلد سلوك النمل لتجد أفضل الحلول المتاحة  لكل مشكلة. عندما تكون لديك مشكلة واقعية، تبدأ بترجمتها إلى مسألة أمثلية على شكل شبكة. يمكن تمثيل الشبكات بسهولة على الكمبيوتر، وكذلك النمل الافتراضي والمسمى “عملاء” (agents)، الذين يتحركون فيها. أما مكان الفرمونات فيعبر عنه باستخدام “فرمونات افتراضية” وهي رقم  موجود على كل رابط في الشبكة: كلما ارتفع الرقم، يعني هذا المزيد من الفيرمونات.

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

يشرح دوريغو:

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

باستعمال هذه الفكرة، دوريغو، و جياني دي كارو (Gianni Di Caro) ولوكا غامبارديلا (Luca Gambardella) طوروا ليس خوارزمية لحل مسألة معينة فحسب، إنما عقلية (framework) يمكن تطبيقها على أي مسألة استمثال توافقي.

هل يقوم الحاسوب بهذا العمل جيدًا؟

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

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

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

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

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

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

المصدر