البحث الجدولي القوي — استدلالي فوقي يعتمد على الجدولة مع متانة ضد عدم اليقين
- قدّمه
- Glover, F. (Tabu Search); robustness extensions by various authors
- السنة
- 1989 (TS); robust variant ~2000s
- النوع
- Metaheuristic with robustness mechanism
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
يمتد البحث الجدولي القوي (RTS) الاستدلالي الفوقي الجدولي الكلاسيكي من خلال تقييم الحلول المرشحة ليس فقط على قيمة هدفها الاسمية ولكن أيضًا على أدائها في ظل عدم اليقين. بدلاً من البحث عن أفضل حل لسيناريو واحد، يبحث RTS عن حلول تؤدي أداءً جيدًا عبر مجموعة من السيناريوهات أو التحقيقات، مقايضة الذروة المثلى بالموثوقية.
الفكرة الحدسية وراء الطريقة
يجد البحث الجدولي الكلاسيكي حلولًا ممتازة من خلال حظر الحركات التي تمت زيارتها مؤخرًا وتوجيه البحث عبر حي. ومع ذلك، في الممارسة العملية، تختلف المدخلات الواقعية - التكاليف، والطلبات، وأوقات السفر. قد يؤدي الحل الذي يبدو مثاليًا في ظل القيم المفترضة إلى أداء ضعيف عندما يختلف الواقع. يدمج البحث الجدولي القوي معيار المتانة مباشرة في دالة التقييم: يتم تقييم كل حل مرشح عبر سيناريوهات متعددة (مُعينة أو مُعدودة)، ويفضل البحث عن الحلول ذات الأداء المستقر ومنخفض التباين. هذا يجعل الحل النهائي مقاومًا لتقلبات المعلمات دون الحاجة إلى إعادة التحسين بعد الواقعة.
التاريخ
تم تقديم البحث الجدولي بواسطة Fred Glover في عامي 1989-1990 كاستدلالي فوقي يعتمد على الذاكرة يتجنب النقاط المثلى المحلية عن طريق حظر الحركات المعكوسة مؤخرًا. ظهرت التوسعات القوية في أواخر التسعينيات والعقد الأول من القرن الحادي والعشرين بالتوازي مع الاهتمام المتزايد بالتحسين القوي؛ قام الباحثون بدمج تقييمات مستندة إلى السيناريو وتقييمات أسوأ الحالات في تقييم حي البحث الجدولي، مما أدى إلى ظهور البحث الجدولي القوي كأداة عملية لمشاكل الهندسة والخدمات اللوجستية في ظل عدم اليقين.
متى تُستخدم
استخدم البحث الجدولي القوي عندما تواجه مشكلة تحسين توافقي أو منفصل حيث تكون معلمات الإدخال الرئيسية غير مؤكدة أو متغيرة - مشاكل التوجيه، أو الجدولة، أو التعيين، أو تصميم الشبكة في ظل عدم اليقين في الطلب أو التكلفة. إنه مناسب بشكل خاص عندما تكون تكلفة إعادة التحسين بعد النشر مرتفعة، أو عندما يجب اعتماد الحلول على أنها موثوقة قبل التنفيذ. تجنب RTS عندما تكون المشكلة حتمية بحتة (يكفي البحث الجدولي الكلاسيكي)، عندما تكون مجموعة عدم اليقين كبيرة جدًا بحيث لا يمكن أخذ عينات منها بشكل قابل للتتبع دون حساب باهظ، أو عندما تكون المشكلة سلسة ومحدبة (ستكون طرق المتانة المستندة إلى التدرج أسرع وأكثر موثوقية).
الحدود والاعتبارات
- يضاعف تقييم المتانة عبر مجموعة سيناريوهات كبيرة التكلفة الحسابية بمقدار |S| لكل تكرار، مما قد يكون باهظًا.
- تعتمد جودة المتانة بشكل كبير على جودة مجموعة السيناريوهات؛ قد يؤدي ضعف تغطية السيناريو إلى التقليل من الثقة الحقيقية.
- تعتبر فترة بقاء الجدولة وحجم الحي معلمات فائقة خاصة بالمشكلة تتطلب ضبطًا.
- لا يضمن الأمثلية العالمية أو شهادة جودة الحل.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يجد حلولًا قوية ضد تباين المدخلات دون الحاجة إلى فحص متانة منفصل بعد الواقعة.
- يرث الأداء التجريبي القوي للبحث الجدولي على مشاكل التوافق الصعبة (الجدولة، VRP، متغيرات TSP).
- معيار متانة مرن: يدعم أهداف الحد الأدنى، والقيمة المتوقعة، والمتوسط والتباين، والأهداف المستندة إلى المئين.
- لا يتطلب تحدب المشكلة أو قابليتها للاشتقاق - قابلة للتطبيق على الأهداف الصندوق الأسود والمنفصلة.
- تمنع آلية الجدولة الوقوع في الحلول المحلية القوية ولكن المتوسطة عالميًا.
التطبيقات
- توجيه المركبات القوي في ظل أوقات سفر أو طلبات عملاء عشوائية
- جدولة ورشة العمل أو خط الإنتاج بأوقات معالجة غير مؤكدة
- تصميم الشبكة وتخطيط السعة في ظل تقلبات الطلب
- تحسين سلسلة التوريد بأوقات تسليم أو تكاليف مورد غير مؤكدة
- تخصيص التردد في الاتصالات في ظل عدم اليقين في التداخل
- تحسين المحفظة بعوائد أصول غير مؤكدة باستخدام قيود توافقية
كيف يعمل
كيف يعمل
تحديد مشكلة التحسين التوافقي أو المستمر، وتحديد المعلمات غير المؤكدة (مثل، الطلبات، التكاليف، أوقات المعالجة)، وتحديد مجموعة سيناريوهات S التي تمثل التحقيقات المعقولة - إما عن طريق أخذ عينات من التوزيعات أو بناء مجموعة عدم يقين منفصلة. تعيين الهدف المتين: تقليل تكلفة أسوأ حالة، أو تقليل التكلفة المتوقعة، أو تقليل مزيج مرجح من المتوسط والتباين.
لكل حل مرشح x يتم مواجهته أثناء البحث، قم بتقييم هدفه f(x, s) في ظل كل سيناريو s في S. احسب مقياس المتانة R(x) - على سبيل المثال، R(x) = max_{s in S} f(x,s) لمتانة الحد الأدنى، أو R(x) = E[f(x,s)] + lambda * Var[f(x,s)] لمتانة المتوسط والتباين. هذا يحل محل التقييم الاسمي الفردي المستخدم في البحث الجدولي الكلاسيكي.
توليد حي N(x) للحل الحالي x عن طريق تطبيق جميع الحركات الممكنة (التبديلات، الإدخالات، الانعكاسات، إلخ). قم بتقييم R(x') لكل جار x'، باستثناء الحركات الموجودة حاليًا في قائمة الجدولة ما لم يتم استيفاء معيار الإلهام. اختر الجار x* ذو أفضل قيمة متانة R(x*).
الانتقال إلى x* وتسجيل عكس الحركة المطبقة في قائمة الجدولة مع فترة بقاء t (عادةً 5-20 تكرارًا). تمنع قائمة الجدولة الدوران وتشجع الاستكشاف. قد تتجاوز معايير الإلهام - مثل قبول حركة جدولة إذا أنتجت أفضل حل قوي عالميًا - تقييد الجدولة.
تحديث أفضل حل قوي معروف إذا تحسن R(x*) عن أفضل حل حالي. استمر في التكرار حتى يتم استيفاء معيار التوقف: الحد الأقصى للتكرارات، أو الوقت المنقضي، أو عدم التحسن خلال عدد محدد من الخطوات. أعد أفضل حل قوي تم العثور عليه مع ملف أدائه الخاص بالسيناريو.
الأخطاء الشائعة
- استخدام عدد قليل جدًا من السيناريوهات يقلل من تقدير عدم اليقين الحقيقي وينتج حلولًا تبدو قوية ولكنها تفشل في الممارسة.
- الخلط بين البحث الجدولي القوي والبحث الجدولي العشوائي: يحسن التحسين القوي التعرض للحالات الأسوأ، بينما يأخذ البحث الجدولي العشوائي عينات لتقريب القيمة المتوقعة - الأهداف والتفسيرات مختلفة.
- تطبيق متانة الحد الأدنى عندما يكون لسيناريو أسوأ حالة احتمال ضئيل يؤدي إلى حلول مفرطة في التحفظ بتكلفة غير ضرورية.
- قد يؤدي تجاهل معايير الإلهام إلى تفويت البحث عن حلول قوية عالميًا تتضمن حركات جدولة.
- ضبط فترة بقاء الجدولة مرتفعة جدًا يخلق تقييدًا مفرطًا؛ منخفض جدًا يسبب دورانًا - كلاهما يقلل من جودة الحل.
الأسئلة الشائعة
كيف يختلف البحث الجدولي القوي عن البحث الجدولي العشوائي؟
يستخدم البحث الجدولي العشوائي عادةً أخذ العينات العشوائية داخل إجراء البحث نفسه (مثل، القبول الاحتمالي أو أخذ عينات الحي العشوائي) لتقريب القيم المتوقعة. يقوم البحث الجدولي القوي بتحسين معيار المتانة بشكل صريح - مثل أداء أسوأ حالة أو متوسط وتباين - الذي يتم تقييمه عبر مجموعة عدم يقين محددة. الهدف في البحث الجدولي القوي هو استقرار الحل عبر السيناريوهات، وليس فقط الأداء المتوقع.
ما حجم مجموعة السيناريوهات S التي يجب أن تكون؟
لا توجد قاعدة عالمية. بالنسبة لمجموعات عدم اليقين المنفصلة، قم بإحصاء جميع السيناريوهات المعقولة إذا كان ذلك ممكنًا. بالنسبة للتوزيعات المستمرة، غالبًا ما توفر 50-500 عينة سيناريوهات تغطية كافية؛ يمكن لتقنيات تقليل التباين مثل أخذ عينات لاتينية فائقة تحسين الكفاءة. يُنصح بتحليل الحساسية على |S| قبل الالتزام بعدد سيناريوهات نهائي.
هل يمكن للبحث الجدولي القوي التعامل مع مشاكل متعددة الأهداف؟
نعم. عند دمجه مع أطر البحث الجدولي متعددة الأهداف، تصبح المتانة هدفًا إضافيًا أو قيدًا. يمكن استكشاف جبهات باريتو للأداء (الاسمي، المتانة)، مما ينتج مجموعة من الحلول التي تقايض المثالية بالموثوقية - مفيدة عندما يتعين على أصحاب المصلحة الاختيار بين الخيارات المتسامحة مع المخاطر والمتحفظة من المخاطر.
ما هو مقياس المتانة الذي يجب أن أختاره؟
الحد الأدنى (أسوأ حالة) مناسب عندما تكون حالات الفشل كارثية ولا يمكن قبول النتائج السيئة ذات الاحتمالية المنخفضة. القيمة المتوقعة تناسب صانعي القرار المحايدين للمخاطر. يوازن المتوسط والتباين بين متوسط الأداء والتباين وهو شائع في تصميم الهندسة. تُستخدم مقاييس القيمة المعرضة للخطر (VaR) أو القيمة المعرضة للخطر المشروطة في التطبيقات المالية واللوجستية حيث تكون ضمانات المئين مهمة.
هل البحث الجدولي القوي مناسب للحالات الكبيرة جدًا؟
يعتمد ذلك على تكلفة تقييم السيناريو. إذا كان كل تقييم f(x,s) رخيصًا (مللي ثانية)، تظل المتانة عبر مئات السيناريوهات قابلة للتتبع حتى للحالات الكبيرة. إذا كان كل تقييم يتطلب محاكاة أو استدعاء حلال مكلف، تصبح ضرورية تقنيات تقليل السيناريو العدوانية أو نماذج البديل. التقييم المتوازي للسيناريوهات عبر الخيوط أو الأجهزة هو تخفيف شائع.
طرق ذات صلة
المصادر
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
افتح مرجع DOIتم النسخ.Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.
افتح مرجع المنشورتم النسخ.