تحسين مستعمرة النمل — التحسين التوافقي القائم على السرب
- السنة
- 1992 (foundational thesis); 1997 (Ant Colony System formalization)
- النوع
- Metaheuristic — swarm intelligence
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تحسين مستعمرة النمل (ACO) هو خوارزمية استدلالية فائقة قدمها ماركو دوريغو وزملاؤه في أوائل التسعينيات لحل مشاكل التحسين التوافقي عن طريق محاكاة سلوك البحث الجماعي للنمل. يضع النمل الحقيقي مسارات الفيرومونات على المسارات ويتبع المسارات الأقوى بشكل تفضيلي؛ يحول ACO آلية التغذية الراجعة الإيجابية هذه إلى إجراء بحث يجد حلولاً عالية الجودة للمشاكل ذات الهيكل البياني مثل مشكلة البائع المتجول، وتوجيه المركبات، والجدولة.
الفكرة الحدسية وراء الطريقة
تخيل مستعمرة من النمل تتجول في خريطة بحثًا عن أقصر طريق بين مصادر الغذاء. يتم اجتياز المسارات القصيرة بشكل متكرر وتتلقى المزيد من رواسب الفيرومونات، مما يجعلها أكثر جاذبية للنمل اللاحق. على مدار تكرارات عديدة، يركز هذا التعزيز حركة المرور على أفضل المسارات بينما يمنع التبخر المستعمرة من التركيز على مسار واحد مبكرًا جدًا. ينسخ ACO هذه الحلقة — يقوم عدد من النمل الاصطناعي ببناء حلول مرشحة، وتودع الحلول الجيدة الفيرومونات، ويقوم التبخر تدريجيًا بمسح ذاكرة المسارات القديمة والأقل جودة حتى تتقارب المستعمرة على حل عالي الجودة.
التاريخ
تم تقديم إطار عمل تحسين مستعمرة النمل بواسطة ماركو دوريغو في أطروحته للدكتوراه عام 1992، مستفيدًا من ملاحظات حول كيفية إيجاد مستعمرات النمل الحقيقية لأقصر المسارات عبر اتصالات الفيرومون الستيجمرجية. تم نشر أول خوارزمية ملموسة، نظام النمل (AS)، مع مانزيوز وكولورني في عام 1996. في عام 1997، نشر دوريغو وجامبارديلا نظام مستعمرة النمل (ACS)، الذي قدم تحديثات فيرومون محلية وقاعدة استغلال أكثر عدوانية، مما حسن الأداء بشكل كبير على مشكلة البائع المتجول. وحدت دراسة دوريغو وشتوتزله عام 2004 الصادرة عن مطبعة MIT إطار عمل ACO وأسستها كفرع رئيسي من ذكاء السرب. تم توسيع ACO منذ ذلك الحين لتشمل المجالات المستمرة (ACOR)، والمشاكل متعددة الأهداف (MOACO)، والرسوم البيانية الديناميكية.
متى تُستخدم
ACO مناسب لمشاكل التحسين التوافقي التي يمكن التعبير عنها كمهمة إيجاد مسار أو مهمة تعيين على رسم بياني — تشمل الأمثلة الكلاسيكية مشكلة البائع المتجول، وتوجيه المركبات، وجدولة ورشة العمل، وتوجيه الشبكة. يقبل متغيرات القرار المستمرة والفئوية عندما يتم تشفير المشكلة بشكل مناسب. لا يلزم افتراض الطبيعية ولا يوجد حد أدنى لحجم العينة؛ المدخلات ذات الصلة هي هيكل رسم بياني محدد جيدًا وميزانية تكرار كافية (عادةً عدة مئات إلى بضعة آلاف من التكرارات). ACO تنافسي بشكل خاص عندما تتوفر استدلالات المجال لتوجيه النمل. إذا كان يمكن تحمل أقل من حوالي 100-200 تكرار، فإن البحث المحظور هو بديل مفضل.
الحدود والاعتبارات
- يتطلب ميزانية تكرار كافية؛ مع عدد قليل جدًا من التكرارات تكون مسارات الفيرومون غير موثوقة وتتدهور جودة الحل.
- يجب ضبط ثلاث معلمات رئيسية — α و β و ρ؛ يمكن أن تتسبب القيم المختارة بشكل سيء في التقارب المبكر أو الركود.
- يمكن أن يكون التقارب بطيئًا على الرسوم البيانية الكبيرة جدًا لأن إشارة الفيرومون تتخفف عبر العديد من الحواف.
- غير مناسب بشكل طبيعي لمشاكل التحسين المستمر بدون تشفير رسم بياني.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يعالج مساحات البحث التوافقي الكبيرة والمتقطعة التي لا يمكن حلها بالطرق الدقيقة.
- يسمح البحث القائم على السكان بالتوازي الضمني — يتم استكشاف حلول مرشحة متعددة في وقت واحد.
- يمكن حقن معرفة المجال (الاستدلال η) مباشرة في قاعدة الانتقال لتسريع التقارب.
- تركز آلية الفيرومون ذات التغذية الراجعة الإيجابية بشكل طبيعي البحث على المناطق الواعدة بمرور الوقت.
- قوي ضد إعادة هيكلة المشكلة: إضافة أو إزالة عقد/حواف الرسم البياني لا تتطلب إعادة اشتقاق الخوارزمية.
التطبيقات
- مشكلة البائع المتجول (TSP) وتوجيه المركبات — إيجاد جولات بأقل تكلفة عبر المدن أو نقاط التسليم.
- جدولة ورشة العمل والورشة المفتوحة — تعيين العمليات للآلات لتقليل وقت الإنجاز أو التأخير.
- توجيه الشبكة في الاتصالات — التكيف الديناميكي لمسارات الحزم لتقليل الازدحام.
- تحسين سلسلة التوريد والخدمات اللوجستية — تعيين المستودعات، وتسلسل تسليم الميل الأخير.
- التصميم الهندسي — مشاكل اختيار المعلمات وتخطيط المكونات المشفرة كمساحات بحث متقطعة.
كيف يعمل
كيف يعمل
تُشفر مشكلة التحسين كرسم بياني: تمثل العقد نقاط القرار (مثل المدن، المهام، العمليات) وتحمل الحواف وزنين — مستوى فيرومون τ يتم تحديثه كل تكرار وقيمة استدلالية η مشتقة من معرفة المجال (مثل مقلوب المسافة). هذا الرسم البياني هو البيئة المشتركة التي يتواصل من خلالها جميع النمل بشكل غير مباشر.
يقوم كل نملة اصطناعية ببناء حل كامل عن طريق اجتياز الرسم البياني. عند كل عقدة، تختار احتماليًا الحافة التالية وفقًا لقاعدة انتقال توازن بين مستوى الفيرومون (مرفوع إلى α) والجاذبية الاستدلالية (مرفوعة إلى β). يفضل α الأعلى استغلال المسارات الجيدة المعروفة؛ يزيد β الأعلى الاعتماد على المعرفة الخاصة بالمشكلة. النتيجة هي مجموعة من الحلول المرشحة المنتجة بالتوازي في كل تكرار.
بعد أن تكمل جميع النمل جولاتهم، يتم تعديل مستويات الفيرومون في خطوتين. أولاً، يقلل التبخر من فيرومون كل حافة بعامل (1 − ρ)، مما يمنع التراكم غير المحدود ويمنع البحث من الانغلاق المبكر. ثانيًا، تودع النمل الفيرومونات على الحواف التي استخدمتها؛ تودع الحلول الأفضل المزيد، مما يعزز المسارات الأقصر أو الأعلى جودة. يضيف متغير نظام مستعمرة النمل (ACS) أيضًا تحديثًا محليًا للفيرومون أثناء البناء لتنويع البحث.
تتكرر الإجراءات حتى يتم استيفاء معيار التوقف — عادةً ما يكون الحد الأقصى لعدد التكرارات أو عتبة الركود (لا يوجد تحسن على مدار عدد محدد من التكرارات). يتم إرجاع أفضل حل تم العثور عليه عبر جميع التكرارات. إذا كانت ميزانية التكرار صغيرة جدًا، فقد لا تشكل المستعمرة مسارات فيرومون موثوقة ويتدهور الحل إلى بحث عشوائي تقريبًا؛ يوصى بالرجوع إلى البحث المحظور في هذه الحالة.
الأخطاء الشائعة
- تشغيل عدد قليل جدًا من التكرارات (قاعدة عامة هي مئات على الأقل) — لا تشكل المستعمرة مسارات فيرومون مستقرة أبدًا، مما ينتج حلولًا عشوائية تقريبًا؛ قم بالتبديل إلى البحث المحظور إذا كانت الميزانية ضيقة جدًا.
- ضبط معدل التبخر ρ منخفضًا جدًا — يتراكم الفيرومون القديم، وتركز المستعمرة على مسار دون المستوى الأمثل مبكرًا، وينهار التنوع؛ قم بزيادة ρ أو استخدم آلية إعادة تعيين الفيرومون.
- تجاهل المعلومات الاستدلالية (β = 0) — تصبح الخوارزمية مدفوعة بالفيرومون بشكل بحت، وهو أمر بطيء وغير موثوق به في البداية عندما تكون المسارات غير مطلعة.
- تطبيق ACO على مشاكل مستمرة بدون تشفير رسم بياني مناسب — تعتمد قاعدة انتقال الاحتمالات على رسم بياني متقطع؛ يؤدي تعيين المتغيرات ذات القيم الحقيقية مباشرة بدون تقطيع أو متغير ACO مناسب (مثل ACOR) إلى نتائج سيئة.
- الفشل في تتبع أفضل حل عالمي عبر جميع التكرارات — تحديثات الفيرومون بناءً على أفضل نملة في التكرار الحالي فقط تفقد الأفضل الذي تم العثور عليه بشكل عام.
الأسئلة الشائعة
كيف يختلف ACO عن الخوارزميات الجينية؟
كلاهما استدلالات فائقة قائمة على السكان، لكنهما يختلفان في كيفية تطور الحلول. تحتفظ الخوارزميات الجينية بمجموعة من الحلول الكاملة وتستخدم عوامل التقاطع والطفرة لإنشاء ذرية. يحتفظ ACO بمصفوفة فيرومون — ذاكرة مشتركة — ويبني كل نملة حلًا جديدًا من الصفر بتوجيه من تلك الذاكرة. يعتبر ACO بشكل عام أكثر طبيعية لمشاكل إيجاد المسارات والتسلسل، بينما تنطبق الخوارزميات الجينية على نطاق واسع على التحسين ذي الترميز الحقيقي والثنائي.
ما هي القيم التي يجب أن أستخدمها لـ α و β و ρ؟
تشير المعايير القياسية على TSP إلى أن α ≈ 1، و β ≈ 2-5، و ρ ≈ 0.02-0.1 كنقاط انطلاق معقولة (Dorigo & Stützle, 2004). يزيد β الأعلى من التأثير الاستدلالي (مفيد عندما تكون معرفة المجال موثوقة)؛ يزيد ρ الأعلى من التبخر والتنوع ولكنه قد يبطئ التقارب. هذه المعلمات تعتمد على المشكلة ويجب ضبطها بشكل منهجي، على سبيل المثال باستخدام بحث شبكي صغير أو تحسين بايزي.
هل يمكن لـ ACO حل مشاكل التحسين المستمر؟
تم تصميم ACO القياسي لمساحات البحث المتقطعة ذات الهيكل البياني. يمكن معالجة المشاكل المستمرة باستخدام ACOR (تحسين مستعمرة النمل للمجالات المستمرة)، والذي يستبدل مصفوفة الفيرومون بأرشيف حل ودالة كثافة احتمالية. بالنسبة للمشاكل المستمرة البحتة بدون تشفير رسم بياني طبيعي، قد تكون البدائل مثل تحسين سرب الجسيمات أو التطور التفاضلي أبسط في التطبيق.
كم عدد النمل والتكرارات المطلوبة عادةً؟
لا توجد إجابة عالمية، ولكن نقطة انطلاق عملية هي تعيين عدد النمل مساويًا لعدد العقد في الرسم البياني وتشغيله لعدة مئات من التكرارات. يمكن أن يؤدي اكتشاف الركود — التوقف عندما لم يتحسن أفضل حل لعدد ثابت من التكرارات — إلى توفير الحسابات. إذا تم فرض ميزانية صارمة أقل من حوالي 100-200 تكرار، فمن غير المرجح أن ينتج ACO نتائج موثوقة؛ البحث المحظور هو خيار أفضل في هذا النظام.
طرق ذات صلة
المصادر
Dorigo, M. & Gambardella, L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
افتح مرجع DOIتم النسخ.Dorigo, M. & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
ردمك: 9780262042192تم النسخ.