البحث التابو متعدد الأهداف (MOTS) — خوارزمية فوق استدلالية للحلول المثلى باريتو
- قدّمه
- Hansen, M. P.; building on Glover (1989) Tabu Search
- السنة
- 1997
- النوع
- Metaheuristic multi-objective optimization
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
البحث التابو متعدد الأهداف (MOTS) هي خوارزمية فوق استدلالية توسع إطار البحث التابو الكلاسيكي لتحسين وظيفتين أو أكثر من وظائف الأهداف المتعارضة بشكل متزامن. بدلاً من حل أمثل واحد، تسعى إلى تقريب واجهة باريتو — مجموعة الحلول التي لا يمكن تحسين أي هدف فيها دون تدهور هدف آخر — مما يجعلها مناسبة لمشاكل التحسين التوافقي والمستمر المعقدة في الهندسة واللوجستيات وأبحاث العمليات.
الفكرة الحدسية وراء الطريقة
تخيل استكشاف منظر طبيعي وعر به العديد من التلال والوديان، ولكن لديك خرائط متعددة تعرض تضاريس مختلفة (واحدة لكل هدف) تتعارض مع بعضها البعض. تتنقل خوارزمية MOTS في هذه المساحة عن طريق الانتقال إلى الحلول المجاورة، والاحتفاظ بقائمة ذاكرة قصيرة المدى (قائمة التابو) من المواقع التي تمت زيارتها مؤخرًا لتجنب الدوران، والاحتفاظ بأرشيف للحلول غير المهيمنة التي تم العثور عليها حتى الآن. بشكل دوري، تدفع التنويعات الاستراتيجية البحث إلى مناطق غير مستكشفة من واجهة باريتو، مما يوازن بين استغلال المناطق الواعدة والاستكشاف العالمي.
التاريخ
يوسع البحث التابو متعدد الأهداف البحث التابو أحادي الهدف الذي قدمه فريد جلوفر في عام 1989. تم تقديم أول صياغة منهجية لـ MOTS — بما في ذلك أرشيف باريتو ومعايير الطموح متعددة الأهداف — بواسطة M. P. Hansen في مؤتمر MCDM لعام 1997. قامت الأعمال اللاحقة التي قام بها Gandibleux و Teghem وآخرون بتشكيل متغيرات لمشاكل التوافق، ومنذ ذلك الحين تم تطبيق MOTS على مشاكل الجدولة واللوجستيات وتصميم الهندسة كبديل تنافسي للخوارزميات التطورية متعددة الأهداف.
متى تُستخدم
استخدم خوارزمية MOTS عندما تواجه مشكلة تحسين توافقي أو مختلط الأعداد الصحيحة مع هدفين أو أكثر متعارضين (على سبيل المثال، التكلفة مقابل الجودة، الوقت مقابل المخاطر) وتكون الطرق الدقيقة غير قابلة للحساب. تتفوق في مشاكل الجدولة، وتوجيه المركبات، وتصميم الشبكات، واختيار المحافظ حيث يكون فضاء البحث كبيرًا جدًا للإحصاء الشامل. فضل خوارزمية MOTS على البحث العشوائي البحت عندما يكون هيكل الجوار ذا مغزى ويمكن تعريف عوامل الحركة بوضوح. لا تستخدم خوارزمية MOTS عندما: يكون للمشكلة هدف واحد (يكفي البحث التابو البسيط)؛ عندما يمكن إحصاء واجهة باريتو بدقة؛ عندما تكون معلومات التدرج متاحة والمشهد محدب (استخدم البرمجة الرياضية بدلاً من ذلك)؛ أو عندما تتطلب القرارات في الوقت الفعلي مخرجات حتمية وقابلة للتكرار بدون تباين عشوائي.
الحدود والاعتبارات
- يعتمد الأداء بشكل كبير على طول قائمة التابو، وتعريف الجوار، واستراتيجية التنويع — مما يتطلب ضبطًا دقيقًا للمعلمات.
- لا يوجد ضمان للتقارب إلى واجهة باريتو الحقيقية؛ تعتمد جودة الحل على طول التشغيل وهيكل المشكلة.
- مكلفة حسابيًا لكل تكرار عندما تكون الأحياء كبيرة أو تكون تقييمات الأهداف مكلفة.
- يمكن أن تصبح صيانة وتحديث أرشيف باريتو مكلفة مع زيادة عدد الأهداف وحجم الأرشيف.
- التنفيذ المتوازي ليس بالأمر السهل نظرًا للطبيعة المتسلسلة القائمة على الذاكرة لآلية التابو.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تتجنب إعادة زيارة الحلول الأخيرة عبر قائمة التابو، مما يقلل من خطر الدوران في المناظر الطبيعية المعقدة.
- تسمح معايير الطموح بتجاوز قيود التابو عندما يؤدي الانتقال إلى تحسين استثنائي، مما يوازن بين الذاكرة والمرونة.
- لا تتطلب معلومات التدرج، مما يجعلها قابلة للتطبيق على وظائف الأهداف غير القابلة للتفاضل، أو المنفصلة، أو الصندوق الأسود.
- تنتج تقريبًا لواجهة باريتو بأكملها في تشغيل واحد، مما يدعم اتخاذ القرارات متعددة المعايير.
- يسمح تصميم الجوار وعوامل الحركة المرنة بالتخصيص الخاص بالمشكلة.
- تمكن آليات التنويع من الهروب من التحسينات المحلية وتغطية أفضل لواجهة باريتو.
التطبيقات
- توجيه المركبات متعدد الأهداف وجدولة اللوجستيات (تقليل التكلفة ووقت التسليم بشكل متزامن)
- جدولة المشاريع ثنائية الأهداف: تقليل وقت الانتهاء وتكلفة الموارد في ظل قيود الأسبقية
- تحسين المحفظة: موازنة العائد المتوقع مقابل المخاطر عبر فئات الأصول المتعددة
- تصميم الشبكة: تقليل تكلفة التركيب مع زيادة الموثوقية أو الإنتاجية
- تخطيط عمليات التصنيع: تحسين وقت الدورة، واستخدام الطاقة، ومقاييس الجودة بشكل مشترك
- الإدارة البيئية: موازنة الناتج الاقتصادي مقابل التلوث أو التأثير البيئي
كيف يعمل
كيف يعمل
تهيئة البحث بحل واحد أو أكثر من الحلول الابتدائية (تم إنشاؤها عشوائيًا أو بناؤها استدلاليًا). تعيين قائمة تابو فارغة بطول ثابت L وتهيئة أرشيف باريتو بالحلول غير المهيمنة من السكان الابتدائية.
إنشاء الجوار N(s) للحل الحالي s عن طريق تطبيق عوامل الحركة (التبديلات، الإدراجات، الاضطرابات). تقييم جميع الحلول المجاورة على كل وظيفة هدف لتحديد المرشحين للتقدم.
تطبيق مرشح التابو: استبعاد الجيران الذين تظهر حركاتهم المحددة في قائمة التابو ما لم يستوفوا معيار الطموح — عادةً ما يكون الجار يهيمن على جميع أعضاء الأرشيف الحاليين أو يحسن القيمة المعروفة الأفضل في هدف واحد على الأقل. هذا يمنع الدوران ويجبر على الاستكشاف.
اختيار أفضل جار غير تابو (أو الفائز بمعيار الطموح) كحل حالي تالٍ. تحديث أرشيف باريتو بإضافة الحل الجديد إذا كان غير مهيمن؛ إزالة أي أعضاء أرشيف يهيمن عليها الإدخال الجديد.
تطبيق استراتيجيات التنويع عندما يتعثر البحث: ذاكرة التردد طويلة المدى تحدد المناطق التي تمت زيارتها نادرًا؛ إعادة التشغيل من حلول الأرشيف النخبة أو الحلول المضطربة عشوائيًا لتوسيع تغطية واجهة باريتو.
تكرار خطوات الجوار والمرشح والأرشيف حتى يتم استيفاء معيار التوقف — عادةً ما يكون الحد الأقصى لعدد التكرارات، أو تقييمات الوظائف، أو وقت وحدة المعالجة المركزية المنقضي. إرجاع أرشيف باريتو باعتباره الواجهة المثلى باريتو التقريبية.
الأخطاء الشائعة
- يؤدي تعيين قائمة التابو قصيرة جدًا إلى الدوران؛ تعيينها طويلة جدًا يقيد البحث بشكل مفرط ويفقد الحلول الجيدة — المعايرة التجريبية ضرورية.
- يؤدي إهمال التنويع إلى التقارب المبكر في منطقة واحدة من واجهة باريتو، مما ينتج عنه تقريب ضعيف.
- يؤدي تطبيق خوارزمية MOTS مع أكثر من ثلاثة أهداف إلى تدهور الأداء لأن إدارة الأرشيف والحفاظ على التنوع يصبحان مرهقين حسابيًا؛ يجب النظر في الطرق القائمة على التحلل للمشاكل متعددة الأهداف.
- يحد استخدام عوامل الحركة العامة دون تصميم خاص بالمشكلة بشكل كبير من جودة الحل مقارنة بالتطبيقات المصممة خصيصًا.
- يمكن أن يؤدي الإبلاغ عن الأرشيف النهائي فقط دون فحص تاريخ التقارب إلى إخفاء الركود المبكر.
الأسئلة الشائعة
كيف تتعامل خوارزمية MOTS مع قائمة التابو عندما تكون هناك أهداف متعددة؟
تقوم قائمة التابو بتخزين الحركات (وليس الحلول)، لذا فهي تعمل بنفس الطريقة كما في البحث التابو أحادي الهدف. الفرق الرئيسي هو أن الاختيار بين الجيران غير التابو يستخدم هيمنة الأهداف المتعددة أو وظيفة قياسية، ويتم إعادة تعريف معيار الطموح للسماح بحركة تابو إذا كان الحل الناتج غير مهيمن من قبل جميع أعضاء الأرشيف الحاليين.
ما هو أرشيف باريتو وكم يجب أن يكون حجمه؟
يخزن أرشيف باريتو جميع الحلول غير المهيمنة التي تم العثور عليها أثناء البحث. عادة ما يكون حجمه الأقصى محدودًا (على سبيل المثال، 100-500 حل) للحفاظ على تكلفة الذاكرة والتحديث قابلة للإدارة. عندما يمتلئ الأرشيف، تقوم تقليم المسافة المزدحمة أو التقليم المستند إلى الشبكة بإزالة الحلول من المناطق المزدحمة بشكل مفرط للحفاظ على التنوع.
كيف تقارن خوارزمية MOTS بـ NSGA-II للمشاكل متعددة الأهداف؟
تستخدم NSGA-II نهجًا تطوريًا قائمًا على السكان مع التزاوج والطفرات، مما يجعلها أفضل في الاستكشاف العالمي في وقت مبكر من البحث. تعتمد خوارزمية MOTS على حركات الجوار والذاكرة، والتي غالبًا ما تعطي جودة بحث محلية أدق. في الممارسة العملية، تميل خوارزمية MOTS إلى التفوق في المشاكل التوافقية ذات هيكل الجوار القوي، بينما تستخدم NSGA-II على نطاق أوسع للمشاكل المستمرة.
كم عدد التكرارات المطلوبة عادة؟
لا توجد قاعدة عالمية. الممارسة الشائعة هي تخصيص تقييمات الوظائف بدلاً من التكرارات — عادةً 10,000 إلى 100,000 تقييم اعتمادًا على حجم المشكلة — وتشغيل عمليات بدء مستقلة متعددة لتقييم جودة الحل واستقرار واجهة باريتو.
هل يمكن لـ MOTS التعامل مع أكثر من هدفين؟
نعم، ولكن الفعالية تتدهور مع نمو عدد الأهداف إلى ما بعد ثلاثة (لعنة الأبعاد في فضاء الأهداف). بالنسبة لأربعة أهداف أو أكثر، ينفجر حجم الأرشيف ويصبح الحفاظ على التنوع صعبًا؛ غالبًا ما يُفضل استخدام الأساليب القائمة على التحلل أو المؤشرات.
طرق ذات صلة
المصادر
Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.
افتح مرجع المنشورتم النسخ.Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
افتح مرجع DOIتم النسخ.