البحث المحلي المتكرر

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
يؤدي البحث المحلي المتكرر إلى استبعاد حل من الحل الأمثل المحلي

البحث المحلي المتكرر [ 1 ] [ 2 ] ( ILS ) هو مصطلح في الرياضيات التطبيقية وعلوم الكمبيوتر يحدد تعديلًا لطرق البحث المحلي أو تسلق التل لحل مشاكل التحسين المنفصلة .

قد تتعثر طرق البحث المحلية في الحد الأدنى المحلي ، حيث لا تتوفر جيران محسّنون.

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

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

تعتمد خوارزمية البحث المحلي المتكرر على بناء سلسلة من الحلول المثلى محليًا من خلال:

  1. إخلال بالحد الأدنى المحلي الحالي؛
  2. تطبيق البحث المحلي بعد البدء من الحل المعدل.

يجب أن تكون قوة الاضطراب كافية لتوجيه المسار إلى حوض جذب مختلف يؤدي إلى حل أمثل محلي مختلف .

خوارزمية الاضطراب

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

  1. ضعيف جدًا: العودة إلى نفس الحد الأدنى المحلي
  2. قوي جدًا: إعادة تشغيل عشوائية

اضطراب المعيار

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

الاضطراب التكيفي

بما أنه لا توجد دالة مسبقة تحدد القيمة الأنسب لاضطراب معين، فإن أفضل معيار هو جعله قابلاً للتكيف. على سبيل المثال، اقترح باتيتي وبروتاسي [ 3 ] خوارزمية بحث تفاعلية لمسألة MAX-SAT تتناسب تمامًا مع إطار عمل ILS. يطبقان مخطط اضطراب "موجه" باستخدام خوارزمية بحث محظور ، وبعد كل اضطراب، يطبقان خوارزمية هبوط محلي قياسية. طريقة أخرى لتكييف الاضطراب هي تغيير قوته بشكل حتمي أثناء البحث.

تحسين الاضطراب

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

التطبيقات

تم تطبيق هذه الطريقة على العديد من مشاكل التحسين التوافقي بما في ذلك مشاكل جدولة ورش العمل ، [ 4 ] [ 5 ] مشاكل تدفق العمل، [ 6 ] مشاكل توجيه المركبات [ 7 ] بالإضافة إلى العديد من المشاكل الأخرى.

مراجع

  1. ↑ لورينكو، إتش آر؛ مارتن، أو؛ ستوتزل، تي. (2010). "البحث المحلي المتكرر: الإطار والتطبيقات". دليل الميتاهيورستيك . دار نشر كلوير الأكاديمية، السلسلة الدولية في بحوث العمليات وعلوم الإدارة. المجلد  146 (  الطبعة الثانية). الصفحات 363-397 . CiteSeerX 10.1.1.187.2089 . doi : 10.1007/978-1-4419-1665-5_12 . ISBN   978-1-4419-1663-1.
  2. ↑ لورينكو، إتش آر؛ مارتن، أو؛ ستوتزل، تي. (2003). "البحث المحلي المتكرر" . دليل الميتاهيورستيك . السلسلة الدولية في بحوث العمليات وعلوم الإدارة. المجلد 57. دار نشر كلوير الأكاديمية. الصفحات 321-353 .  
  3. ↑ باتيتي، روبرتو؛ بروتاسي، ماركو (1997-01-01). "البحث التفاعلي، خوارزمية استدلالية حساسة للتاريخ لمسألة MAX-SAT" . مجلة ACM للخوارزميات التجريبية . 2 : 2–es. doi : 10.1145/264216.264220 . ISSN 1084-6654 . 
  4. ↑ لورينكو، إتش آر؛ زويجنبرغ، إم. (1996). "دمج التحسين ذي الخطوة الكبيرة مع البحث المحظور: تطبيق على مشكلة جدولة ورش العمل". الخوارزميات فوق الحدسية: النظرية والتطبيقات . دار نشر كلوير الأكاديمية. سبرينغر. ص 219-236 . doi : 10.1007/978-1-4613-1361-8_14 . ISBN  9780792397007.
  5. ↑ لورينكو، إتش آر (1995). "جدولة ورش العمل: دراسة حسابية لطرق البحث المحلي والتحسين بخطوات كبيرة". المجلة الأوروبية لبحوث العمليات . 83 (2): 347-364 . doi : 10.1016/0377-2217(95)00012-F .
  6. ↑ خوان، أ.أ.؛ لورينكو، هـ.؛ ماتيو، م.؛ لو، ر.؛ كاستيلا، ك. (2013). "استخدام البحث المحلي المتكرر لحل مشكلة تدفق الإنتاج: قضايا المعلمات والعشوائية والتوازي" . المعاملات الدولية في بحوث العمليات . مؤرشف من الأصل في 2012-12-02 . تم الاسترجاع في 2013-05-20 .
  7. ↑ بينا، بوكا إتش في؛ ساتوري أوشي، إل؛ سوبرامانيان، أ. (2013). "خوارزمية بحث محلي متكررة لمسألة توجيه مركبات الأسطول غير المتجانس". مجلة الخوارزميات . 19 (2): 201-232 . doi : 10.1007/s10732-011-9186-y .

[ 1 ]