الانتقال إلى المحتوى
العودة إلى نتائج البحث

التحسين المعزز بالمستعمرات النملية متعدد الأهداف (MOACO)

قدّمه
Gambardella, Taillard & Agazzi; Dorigo & Stützle
السنة
1999
النوع
Population-based metaheuristic
العائلة
Simulation / optimization

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

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

الفكرة الحدسية وراء الطريقة

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

التاريخ

تم تقديم التحسين المعزز بالمستعمرات النملية بواسطة ماركو دوريغو في أطروحته للدكتوراه عام 1992 وتمت صياغته رسميًا مع مانزيوزو وكولورني. ظهرت امتدادات الأهداف المتعددة في أواخر التسعينيات؛ أظهر MACS-VRPTW لـ Gambardella و Taillard و Agazzi (1999) مستعمرات نمل متعددة تستهدف أهدافًا مختلفة. قامت أطر العمل اللاحقة من قبل Doerner و Hartl وآخرين بتشكيل MOACO كفئة، وقدم كتاب دوريغو وشتوتزل عام 2004 المعالجة الخوارزمية القياسية. لا يزال MOACO مجالًا نشطًا للبحث مع تطبيقات في توجيه الشبكات، والمعلوماتية الحيوية، واللوجستيات المستدامة.

متى تُستخدم

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

الحدود والاعتبارات

  • يتطلب ضبطًا دقيقًا للعديد من المعلمات الفائقة (α، β، ρ، حجم المستعمرة، سعة الأرشيف)، ويمكن أن يكون الحساسية لهذه الإعدادات عالية.
  • التقارب أبطأ من الحلول الدقيقة للمشاكل الصغيرة المنظمة جيدًا حيث تكون طرق البرمجة الصحيحة أو الديناميكية قابلة للتطبيق.
  • جودة التقريب وتنوع جبهة باريتو غير مضمونة؛ تختلف النتائج عبر التشغيلات بسبب البناء العشوائي.
  • يصعب التوسع إلى مساحات أهداف عالية الأبعاد (> 3 أهداف) وقد يتطلب استراتيجيات تفكيك متخصصة.
  • لا يوجد دليل على التقارب لحالات المشكلة العشوائية؛ الضمانات النظرية محدودة مقارنة بالبرمجة الرياضية.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

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

2

تبني كل نملة حلاً كاملاً خطوة بخطوة عن طريق اختيار مكونات الحل احتماليًا. يستخدم احتمال الانتقال قوة الفيرومون τ والرغبة الاستدلالية η مرفوعة إلى أسس ضبط α و β. تقوم متغيرات MOACO المختلفة بتعيين مصفوفات الفيرومونات لكل هدف أو تستخدم أوزانًا قياسية تتغير عبر النمل.

الصيغة
p_{ij}^k = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}]^\alpha \cdot [\eta_{il}]^\beta}
3

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

4

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

5

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

الصيغة
\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \sum_{k: s^k \in \mathcal{A}} \Delta\tau_{ij}^k
6

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

الأخطاء الشائعة

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

الأسئلة الشائعة

كيف يختلف MOACO عن تشغيل ACO أحادي الهدف عدة مرات مع مجموعات أوزان مختلفة؟

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

أي متغير MOACO يجب أن أستخدم لمشكلة جديدة؟

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

كم عدد النمل والتكرارات المطلوبة عادة؟

لا توجد إجابة عالمية، ولكن تكوين بدء شائع هو 20-100 نملة لكل مستعمرة و 500-2000 تكرار للمشاكل التوافقية متوسطة الحجم. تتطلب مساحات الحلول الأكبر والأهداف الأكثر عددًا تكرارات أكثر. قم دائمًا بإجراء تكرارات مستقلة متعددة وقم بالإبلاغ عن مؤشرات الحجم الفائق أو مؤشر المسافة العامة (IGD) في المتوسط على البذور.

هل يمكن لـ MOACO التعامل مع مشاكل التحسين المستمرة؟

تم تصميم ACO القياسي للمساحات المنفصلة. توجد متغيرات MOACO المستمرة (مثل تلك القائمة على ACOR) ولكنها تتفوق عليها عمومًا NSGA-II أو MOEA/D في المشاكل المستمرة. احتفظ بـ MOACO للمشاكل التوافقية أو المختلطة الصحيحة حيث يوفر بناؤها القائم على الرسم البياني ميزة طبيعية.

كيف يجب تعيين حجم أرشيف باريتو؟

يحد حجم الأرشيف من عدد الحلول النخبة المستخدمة لإيداع الفيرومون. الأرشيف الصغير جدًا يفقد التنوع؛ الكبير جدًا يبطئ تعزيز الفيرومون. تتراوح القيم النموذجية من 10 إلى 100 حل؛ استخدم استراتيجية مسافة الازدحام أو القائمة على الشبكة للحفاظ على أرشيف منتشر جيدًا بغض النظر عن الحجم.

طرق ذات صلة

المصادر

  1. Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, & F. Glover (Eds.), New Ideas in Optimization (pp. 63–76). McGraw-Hill.

    افتح مرجع المنشور
    تم النسخ.
  2. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.

    ردمك: 9780262042192
    تم النسخ.