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

البحث المحظور — استدلال فوقي للبحث المحلي

قدّمه
Fred Glover
السنة
1989
النوع
Local-search metaheuristic

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

حجم الخط

ماذا تفعل؟

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

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

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

التاريخ

تم تقديم البحث المحظور بواسطة فريد جلوفر في ورقة بحثية بارزة عام 1989 في مجلة ORSA Journal on Computing، حيث تم تقديمه كاستراتيجية لتوجيه البحث المحلي من خلال استغلال ذاكرة التحركات السابقة. تم توحيد الأفكار الأساسية وتوسيعها في كتاب جلوفر ولاجونا عام 1997 من سبرينغر، والذي أسس قائمة الحظر قصيرة المدى القياسية، ومعايير الطموح، واستراتيجيات التنويع والتركيز طويلة المدى التي لا تزال مركزية للطريقة اليوم. منذ تقديمه، تم تطبيق البحث المحظور على نطاق واسع في بحوث العمليات، والجدولة، واللوجستيات، والتصميم التوافقي، ولا يزال يعتبر استدلالًا فوقيًا معياريًا جنبًا إلى جنب مع التلدين المحاكى والخوارزميات الجينية.

متى تُستخدم

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

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

  • الأداء حساس لتعريف الجوار ومدة الحظر؛ يمكن أن تؤدي الخيارات السيئة إلى حبس البحث أو جعله يتكرر على الرغم من آلية الحظر.
  • يتطلب ميزانية تكرار دنيا — عادةً أكثر من 1000 تكرار — لاستكشاف الجوار بشكل كافٍ؛ مع عدد قليل جدًا من التكرارات، لا تكون النتائج أفضل من البحث المحلي البسيط.
  • تقوم القائمة المحظورة بتخزين سمات التحرك بدلاً من الحلول الكاملة، لذا فإن معيار الطموح مطلوب لمنع حظر التحركات الجيدة حقًا عن طريق الخطأ.
  • على عكس الحلول الدقيقة، لا يقدم البحث المحظور ضمانًا للأمثلية ويمكن أن تختلف جودة النتيجة عبر التشغيلات إذا كان الحل الأولي أو الجوار عشوائيًا.

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

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

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

2

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

3

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

4

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

5

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

6

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

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

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

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

كيف يختلف البحث المحظور عن التلدين المحاكى؟

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

ما هي مدة القائمة المحظورة؟

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

هل يضمن البحث المحظور إيجاد الأمثل العالمي؟

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

ما هو معيار الطموح ولماذا هو ضروري؟

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

طرق ذات صلة

المصادر

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    افتح مرجع المنشور
    تم النسخ.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

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