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

تتطلب مفاهيم جديدة، إذ لم يعد مفهوم "الذكاء" محصورًا في مكان واحد، بل أصبح موجودًا في كل شيء، مهما صغر حجمه. من المعروف أن المفاهيم التي تركز على الإنسان أدت إلى إنتاج أنظمة تكنولوجيا معلومات تتمركز فيها معالجة البيانات ووحدات التحكم وقوة الحساب. وقد شهدت هذه الوحدات المركزية تحسنًا مستمرًا في أدائها، حتى باتت تُضاهي الدماغ البشري. وأصبح نموذج الدماغ هو الرؤية المثالية للحواسيب. ستُغير الشبكات المحيطة من الأشياء الذكية، وجيل جديد من أنظمة المعلومات، عاجلًا أم آجلًا، والذي سيكون أكثر انتشارًا ويعتمد على تقنية النانو، هذا المفهوم تغييرًا جذريًا. فالأجهزة الصغيرة، التي يمكن تشبيهها بالحشرات، لا تمتلك ذكاءً عاليًا في حد ذاتها، بل يمكن تصنيف ذكائها على أنه محدود للغاية. على سبيل المثال، من المستحيل دمج آلة حاسبة عالية الأداء قادرة على حل أي نوع من المسائل الرياضية في شريحة حيوية تُزرع في جسم الإنسان، أو دمجها في علامة ذكية مصممة لتتبع المنتجات التجارية. ومع ذلك، بمجرد ربط هذه الأشياء ببعضها، فإنها تُطور شكلًا من أشكال الذكاء يُمكن مقارنته بمستعمرة من النمل أو النحل. في حالة بعض المشكلات، يمكن أن يكون هذا النوع من الذكاء متفوقًا على التفكير الذي يقوم به نظام مركزي مشابه للدماغ. ^{[ 11 ]}

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

يُعدّ التواصل القائم على الفيرومونات من أكثر طرق التواصل فعاليةً، وهو شائع في الطبيعة. تستخدم الحشرات الاجتماعية، كالنحل والنمل والنمل الأبيض، الفيرومونات للتواصل فيما بينها، وكذلك للتواصل مع أسرابها. ونظرًا لسهولة تطبيقها، تمّ اعتماد الفيرومونات الاصطناعية في أنظمة الروبوتات المتعددة وأنظمة الروبوتات الجماعية. وقد طُبّق التواصل القائم على الفيرومونات بوسائل مختلفة، منها الكيميائية ^{[ 14 ] [ 15 ] [ 16 ]} والفيزيائية (مثل علامات RFID ^{[ 17 ]} والضوء ^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]} والصوت ^{[ 22 ]} ). مع ذلك، لم تتمكن هذه التطبيقات من محاكاة جميع جوانب الفيرومونات كما هي موجودة في الطبيعة.

استُخدم الضوء المُسقط في ورقة بحثية نُشرت عام ٢٠٠٧ في مؤتمر IEEE، من قِبل غارنييه وسيمون وآخرين، كإعداد تجريبي لدراسة التواصل القائم على الفيرومونات مع الروبوتات الصغيرة ذاتية التشغيل. ^{[ ٢٣ ]} وقدّمت دراسة أخرى نظامًا تم فيه تطبيق الفيرومونات عبر شاشة LCD أفقية تتحرك عليها الروبوتات، حيث زُوّدت الروبوتات بمستشعرات ضوئية موجهة للأسفل لتسجيل الأنماط الموجودة أسفلها. ^{[ ٢٤ ] [ ٢٥ ]}

تحتاج كل نملة إلى إيجاد حل للتحرك عبر الرسم البياني. لاختيار الحافة التالية في مسارها، ستأخذ النملة في الاعتبار طول كل حافة متاحة من موقعها الحالي، بالإضافة إلى مستوى الفيرومون المقابل. في كل خطوة من خطوات الخوارزمية، تتحرك كل نملة من حالة${\displaystyle x}$للتصريح${\displaystyle y}$، وهو ما يتوافق مع حل وسيط أكثر اكتمالاً. وبالتالي، كل نملة${\displaystyle k}$يحسب مجموعة${\displaystyle A_{k}(x)}$من التوسعات الممكنة لحالتها الحالية في كل تكرار، وتنتقل إلى واحدة من هذه التوسعات باحتمالية معينة. بالنسبة للنملة${\displaystyle k}$، الاحتمال${\displaystyle p_{xy}^{k}}$الانتقال من ولاية${\displaystyle x}$للتصريح${\displaystyle y}$يعتمد ذلك على مزيج من قيمتين، وهما الجاذبية${\displaystyle \eta _{xy}}$من الخطوة، كما تم حسابها بواسطة بعض الاستدلالات التي تشير إلى الرغبة المسبقة في تلك الخطوة ومستوى التتبع${\displaystyle \tau _{xy}}$يشير مستوى المهارة في تنفيذ هذه الحركة إلى مدى إتقانها في الماضي. أما مستوى المهارة فيُمثل مؤشراً لاحقاً على مدى استصواب هذه الحركة.

بشكل عام، الـ${\displaystyle k}$ينتقل النمل من الولاية${\displaystyle x}$للتصريح${\displaystyle y}$باحتمال

$$$

أين${\displaystyle \tau _{xy}}$هي كمية الفيرومون المودعة للانتقال من الحالة${\displaystyle x}$ل${\displaystyle y}$،${\displaystyle \alpha }$≥ 0 هو مُعامل للتحكم في تأثير${\displaystyle \tau _{xy}}$،${\displaystyle \eta _{xy}}$إن استحسان الانتقال بين الدول هو${\displaystyle xy}$( المعرفة المسبقة ، عادةً)${\displaystyle 1/d_{xy}}$، أين${\displaystyle d}$(المسافة)،${\displaystyle \beta }$≥ 1 هو مُعامل للتحكم في تأثير${\displaystyle \eta _{xy}}$و${\displaystyle \mathrm {allowed} _{x}}$هي مجموعة الوجهات المسموح بها من الولاية${\displaystyle x}$.${\displaystyle \tau _{xz}}$و${\displaystyle \eta _{xz}}$يمثل مستوى المسار وجاذبيته بالنسبة لانتقالات الحالة الأخرى المحتملة.

عادةً ما يتم تحديث مسارات النمل عندما تُكمل جميع النملات حلولها، مما يؤدي إلى زيادة أو تقليل مستوى المسارات بما يتوافق مع التحركات التي كانت جزءًا من حلول "جيدة" أو "سيئة"، على التوالي. مثال على قاعدة تحديث الفيرومون العالمية هو الآن

${\displaystyle \tau _{xy}\leftarrow (1-\rho )\tau _{xy}+\sum _{k}^{m}\Delta \tau _{xy}^{k}}$

أين${\displaystyle \tau _{xy}}$هي كمية الفيرومون المودعة لانتقال الحالة${\displaystyle xy}$،${\displaystyle \rho }$معامل تبخر الفيرومون ،${\displaystyle m}$هو عدد النمل و${\displaystyle \Delta \tau _{xy}^{k}}$كمية الفيرومون التي يتم ترسيبها بواسطة${\displaystyle k}$النملة رقم 1، والتي تُعطى عادةً لمسألة البائع المتجول (مع تحركات تتوافق مع أقواس الرسم البياني) بواسطة

${\displaystyle \Delta \tau _{xy}^{k}={\begin{cases}Q/L_{k}&{\mbox{if ant }}k{\mbox{ uses curve }}xy{\mbox{ in its tour}}\\0&{\mbox{otherwise}}\end{cases}}}$

أين${\displaystyle L_{k}}$تكلفة${\displaystyle k}$جولة النملة (عادةً ما تكون مدتها) و${\displaystyle Q}$ثابت.

يُعد نظام النمل أول خوارزمية لتحسين مستعمرات النمل. وتتوافق هذه الخوارزمية مع تلك المذكورة أعلاه. وقد طوّرها دوريغو. ^{[ 26 ]}

في خوارزمية نظام مستعمرة النمل، تم تعديل نظام النمل الأصلي في ثلاثة جوانب:

1. إن اختيار الحواف منحاز نحو الاستغلال (أي تفضيل احتمال اختيار أقصر الحواف التي تحتوي على كمية كبيرة من الفيرومون)؛
2. أثناء بناء الحل، تقوم النمل بتغيير مستوى الفيرومون للحواف التي تختارها عن طريق تطبيق قاعدة تحديث الفيرومون المحلية؛
3. في نهاية كل تكرار، يُسمح فقط لأفضل نملة بتحديث المسارات من خلال تطبيق قاعدة تحديث الفيرومون العالمية المعدلة. ^{[ 27 ]}

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

تتحكم هذه الخوارزمية في الحد الأقصى والأدنى لكميات الفيرومون على كل مسار. يُسمح فقط لأفضل مسار عالمي أو أفضل مسار في كل تكرار بإضافة الفيرومون إلى مساره. لتجنب توقف خوارزمية البحث، يُحدد نطاق كميات الفيرومون الممكنة على كل مسار ضمن الفترة [τ _max ,τ _min ]. تُهيأ جميع الحواف إلى τ _max لحثّ الخوارزمية على استكشاف المزيد من الحلول. تُعاد تهيئة المسارات إلى τ _max عند الاقتراب من التوقف. ^{[ 28 ]}

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

تم تطوير نظام مستعمرة نمل (ACS) مزود باستراتيجيات تواصل. تم تقسيم النمل الاصطناعي إلى عدة مجموعات. تم اقتراح سبع طرق تواصل لتحديث مستوى الفيرومون بين المجموعات في نظام مستعمرة النمل، وتعمل هذه الطرق على حل مشكلة البائع المتجول. ^{[ 29 ]}

تتمثل آلية ترسب الفيرومونات في خوارزمية COAC في تمكين النمل من البحث عن الحلول بشكل تعاوني وفعال. وباستخدام طريقة التصميم المتعامد، يستطيع النمل في النطاق الممكن استكشاف المناطق التي يختارها بسرعة وكفاءة، مع تعزيز قدرة البحث الشامل ودقته. كما يمكن توسيع نطاق طريقة التصميم المتعامد وطريقة تعديل نصف القطر التكيفي لتشمل خوارزميات تحسين أخرى، مما يوفر مزايا أوسع في حل المشكلات العملية. ^{[ 30 ]}

هي شكل تكراري من نظام النمل، حيث يقسم نطاق البحث بأكمله إلى عدة نطاقات فرعية، ويحل المسألة الهدفية على هذه النطاقات الفرعية. ^{[ 31 ]} تُقارن النتائج من جميع النطاقات الفرعية، ويتم اختيار أفضلها للانتقال إلى المستوى التالي. تُقسّم النطاقات الفرعية الموافقة للنتائج المختارة إلى نطاقات فرعية أخرى، وتُكرر العملية حتى يتم الحصول على مخرج بالدقة المطلوبة. وقد تم اختبار هذه الطريقة على مسائل عكسية جيوفيزيائية غير محددة جيدًا، وأثبتت فعاليتها. ^{[ 32 ]}

• مشكلة الترتيب التسلسلي (SOP) ^{[ 34 ]}
• مشكلة جدولة ورش العمل (JSP) ^{[ 35 ]}
• مشكلة جدولة المتجر المفتوح (OSP) ^{[ 36 ] [ 37 ]}
• مشكلة تدفق التبديل (PFSP) ^{[ 38 ]}
• مشكلة التأخير الكلي لآلة واحدة (SMTTP) ^{[ 39 ]}
• مشكلة التأخير المرجح الإجمالي للآلة الواحدة (SMTWTP) ^{[ 40 ] [ 41 ] [ 42 ]}
• مشكلة جدولة المشاريع ذات الموارد المحدودة (RCPSP) ^{[ 43 ]}
• مشكلة جدولة ورش العمل الجماعية (GSP) ^{[ 44 ]}
• مشكلة التأخير الكلي لآلة واحدة مع أوقات الإعداد المعتمدة على التسلسل (SMTTPDST) ^{[ 45 ]}
• مشكلة جدولة التدفق متعدد المراحل (MFSP) مع أوقات الإعداد / التغيير المعتمدة على التسلسل ^{[ 46 ]}
• مشاكل تخطيط تسلسل التجميع (ASP) ^{[ 47 ]}

• مشكلة توجيه المركبات ذات السعة المحدودة (CVRP) ^{[ 48 ] [ 49 ] [ 50 ]}
• مشكلة توجيه المركبات متعددة المستودعات (MDVRP) ^{[ 51 ]}
• مشكلة توجيه المركبات الدورية (PVRP) ^{[ 52 ]}
• مشكلة توجيه مركبات التوصيل المنقسمة (SDVRP) ^{[ 53 ]}
• مشكلة توجيه المركبات العشوائية (SVRP) ^{[ 54 ]}
• مشكلة توجيه المركبات مع الاستلام والتسليم (VRPPD) ^{[ 55 ] [ 56 ]}
• مشكلة توجيه المركبات مع النوافذ الزمنية (VRPTW) ^{[ 57 ] [ 58 ] [ 59 ] [ 60 ]}
• مشكلة توجيه المركبات المعتمدة على الوقت مع النوافذ الزمنية (TDVRPTW) ^{[ 61 ]}
• مشكلة توجيه المركبات مع النوافذ الزمنية وعمال الخدمة المتعددين (VRPTWMS)

• مشكلة التخصيص التربيعي (QAP) ^{[ 62 ]}
• مشكلة التخصيص المعممة (GAP) ^{[ 63 ] [ 64 ]}
• مشكلة تخصيص التردد (FAP) ^{[ 65 ]}
• مشكلة تخصيص التكرار (RAP) ^{[ 66 ]}

• مشكلة تغطية المجموعة (SCP) ^{[ 67 ] [ 68 ]}
• مشكلة التقسيم (SPP) ^{[ 69 ]}
• مشكلة تقسيم شجرة الرسم البياني المقيدة بالوزن (WCGTPP) ^{[ 70 ]}
• مشكلة الشجرة ذات عدد الكارديناليات الموزونة بالأقواس (AWlCTP) ^{[ 71 ]}
• مشكلة الحقيبة المتعددة (MKP) ^{[ 72 ]}
• الحد الأقصى لمشكلة المجموعة المستقلة (MIS) ^{[ 73 ]}

• يمكن لتقنية تحسين الدوائر باستخدام خوارزمية مستعمرات النمل (ACO) لتحسين  دائرة مكبر الإحساس بتقنية CMOS 45 نانومتر أن تتقارب إلى الحلول المثلى في وقت قصير جدًا. ^{[ 74 ]}
• يمكن أن يؤدي استخدام خوارزمية تحسين مستعمرات النمل (ACO) في توليف الدوائر العكسية إلى تحسين الكفاءة بشكل كبير. ^{[ 75 ]}

لتحسين شكل الهوائيات، يمكن استخدام خوارزميات مستعمرات النمل. على سبيل المثال، يمكن النظر في هوائيات علامات RFID القائمة على خوارزميات مستعمرات النمل (ACO)، ^{[ 77 ]} ومذبذبات ذات حلقة ارتداد وحلقات اهتزازية 10×10 ^{[ 76 ].}

تُستخدم خوارزمية مستعمرة النمل في معالجة الصور للكشف عن حواف الصور وربطها. ^{[ 78 ] [ 79 ]}

• كشف الحواف:

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

فيما يلي الخطوات المتبعة في اكتشاف الحواف باستخدام خوارزمية مستعمرة النمل: ^{[ 80 ] [ 81 ] [ 82 ]}

الخطوة 1: التهيئة. ضعها عشوائياً${\displaystyle K}$النمل في الصورة${\displaystyle I_{M_{1}M_{2}}}$أين${\displaystyle K=(M_{1}*M_{2})^{\tfrac {1}{2}}}$مصفوفة الفيرومون${\displaystyle \tau _{(i,j)}}$يتم تهيئتها بقيمة عشوائية. ويتمثل التحدي الرئيسي في عملية التهيئة في تحديد مصفوفة الاستدلال.

توجد طرق متنوعة لتحديد مصفوفة الاستدلال. في المثال أدناه، تم حساب مصفوفة الاستدلال بناءً على الإحصائيات المحلية: الإحصائيات المحلية عند موضع البكسل.${\displaystyle (i,j)}$.

${\displaystyle \eta _{(i,j)}={\tfrac {1}{Z}}*Vc*I_{(i,j)},}$

أين${\displaystyle I}$هي صورة الحجم${\displaystyle M_{1}*M_{2}}$،

${\displaystyle Z=\sum _{i=1:M_{1}}\sum _{j=1:M_{2}}Vc(I_{i,j})}$

هو عامل توحيد، و

${\displaystyle {\begin{aligned}Vc(I_{i,j})=&f\left(\left\vert I_{(i-2,j-1)}-I_{(i+2,j+1)}\right\vert +\left\vert I_{(i-2,j+1)}-I_{(i+2,j-1)}\right\vert \right.\\&+\left\vert I_{(i-1,j-2)}-I_{(i+1,j+2)}\right\vert +\left\vert I_{(i-1,j-1)}-I_{(i+1,j+1)}\right\vert \\&+\left\vert I_{(i-1,j)}-I_{(i+1,j)}\right\vert +\left\vert I_{(i-1,j+1)}-I_{(i-1,j-1)}\right\vert \\&+\left.\left\vert I_{(i-1,j+2)}-I_{(i-1,j-2)}\right\vert +\left\vert I_{(i,j-1)}-I_{(i,j+1)}\right\vert \right)\end{aligned}}}$

${\displaystyle f(\cdot )}$يمكن حسابها باستخدام الدوال التالية:

${\displaystyle f(x)=\lambda x,\quad {\text{for x ≥ 0; (1)}}}$

${\displaystyle f(x)=\lambda x^{2},\quad {\text{for x ≥ 0; (2)}}}$

${\displaystyle f(x)={\begin{cases}\sin({\frac {\pi x}{2\lambda }}),&{\text{for 0 ≤ x ≤}}\lambda {\text{; (3)}}\\0,&{\text{else}}\end{cases}}}$

${\displaystyle f(x)={\begin{cases}\pi x\sin({\frac {\pi x}{2\lambda }}),&{\text{for 0 ≤ x ≤}}\lambda {\text{; (4)}}\\0,&{\text{else}}\end{cases}}}$

المعلمة${\displaystyle \lambda }$في كل وظيفة من الوظائف المذكورة أعلاه، يتم تعديل الأشكال الخاصة بالوظائف.

الخطوة الثانية: عملية البناء. تعتمد حركة النملة على وحدات بكسل متصلة بأربعة أو ثمانية . ويُعطى احتمال تحرك النملة بمعادلة الاحتمال.${\displaystyle P_{x,y}}$

الخطوتان 3 و5: عملية التحديث. يتم تحديث مصفوفة الفيرومونات مرتين. في الخطوة 3، يتم تحديث أثر النملة (المُعطى بواسطة${\displaystyle \tau _{(x,y)}}$يتم تحديث ) بينما في الخطوة 5 يتم تحديث معدل تبخر المسار والذي يتم تحديده بواسطة:

${\displaystyle \tau _{new}\leftarrow (1-\psi )\tau _{old}+\psi \tau _{0}}$،

أين${\displaystyle \psi }$معامل اضمحلال الفيرومون${\displaystyle 0<\tau <1}$

الخطوة 7: عملية اتخاذ القرار. بمجرد أن تتحرك النملات K مسافة ثابتة L لعدد N من التكرارات، يُعتمد القرار بشأن ما إذا كانت هذه المسافة تمثل حافة أم لا على العتبة T في مصفوفة الفيرومون τ. تُحسب العتبة في المثال أدناه بناءً على طريقة أوتسو .

تم الكشف عن حواف الصورة باستخدام خوارزمية مستعمرة النمل (ACO): تم إنشاء الصور أدناه باستخدام دوال مختلفة معطاة بالمعادلات من (1) إلى (4). ^{[ 83 ]}

• ربط الحواف: ^{[ 84 ]} أثبتت خوارزمية ACO أيضًا فعاليتها في خوارزميات ربط الحواف.

• التنبؤ بالإفلاس ^{[ 85 ]}
• التصنيف ^{[ 35 ]}
• التخطيط الإنتاجي طويل الأجل للمناجم المكشوفة ^{[ 86 ]}
• توجيه الشبكة الموجه بالاتصال ^{[ 87 ]}
• توجيه الشبكة بدون اتصال ^{[ 88 ] [ 89 ]}
• التنقيب عن البيانات ^{[ 35 ] [ 90 ] [ 91 ] [ 92 ]}
• التدفقات النقدية المخصومة في جدولة المشاريع ^{[ 93 ]}
• استرجاع المعلومات الموزعة ^{[ 94 ] [ 95 ]}
• تصميم شبكة الطاقة والكهرباء ^{[ 96 ]}
• مشكلة جدولة سير العمل الشبكي ^{[ 97 ]}
• تصميم الببتيدات المثبطة لتفاعلات البروتين-البروتين ^{[ 98 ]}
• نظام اختبار ذكي ^{[ 99 ]}
• تصميم الدوائر الإلكترونية للطاقة ^{[ 100 ]}
• طي البروتين ^{[ 101 ] [ 102 ] [ 103 ]}
• تحديد النظام ^{[ 104 ] [ 105 ]}