البحث المحلي

البحث المحلي (local search) عائلة الإرشاديات التحسينية التي تبدأ بحل أولي وتبحث في كل تكرار عن جار أفضل ضمن مجموعة تغييرات صغيرة تسمى الجوار. بدأت الدراسات المنهجية على TSP بـ 2-opt لـ Croes (1958) و3-opt لـ Lin (1965)، وبلغت ذروتها بخوارزمية k-opt متغيرة العمق لـ Lin وKernighan (1973) — Lin-Kernighan ومشتقاته متغيرة العمق (Helsgaun 2000) قدمت لعقود أفضل أداء تجريبي على TSP. يتألف البحث المحلي من تعريف للجوار (مثلاً تبديل حافتين في TSP، تبديل مهمتين في الجدولة، relocate / swap / 2-opt* في VRP)، وقاعدة تقييم للحركة (التحسين الأول، أفضل تحسين، أقل تدهور)، ومعيار إيقاف. يتقارب البحث المحلي دائماً إلى **أمثل محلي** — نقطة لا يمكن تحسينها داخل الجوار — لكنه لا يضمن أمثلية عامة. للهروب من الأمثل المحلي طُوّرت الميتا-إرشاديات: tabu search (Glover 1989)، simulated annealing (Kirkpatrick 1983)، VNS (Mladenović وHansen 1997)، iterated local search (Lourenço وMartin وStützle 2003). يقدم البحث المحلي ميزة سرعة هائلة: على TSP من 10.000 مدينة، تشغيل مشتق من Lin-Kernighan يصل إلى 0.5% من الحل الدقيق في ثوان على عتاد حديث. Aarts وLenstra (1997) *Local Search in Combinatorial Optimization* مرجع رئيسي.