Yerel Arama

Yerel arama (local search), bir başlangıç çözümünden başlayıp her iterasyonda komşuluk olarak tanımlanmış küçük değişiklik kümesi içinde daha iyi bir komşu ararak iyileştirmeye çalışan iyileştirici sezgisel ailesidir. Yöntemin TSP üzerindeki ilk sistematik tartışmaları Croes (1958) 2-opt ve Lin (1965) 3-opt ile başlamış, Lin ve Kernighan (1973) değişken-derinlikli k-opt algoritmasıyla zirvesine ulaşmıştır — Lin-Kernighan ve onun değişken-derinlik türevleri (Helsgaun 2000) onlarca yıl boyunca TSP için en iyi ampirik performansı vermiştir. Yerel arama bir komşuluk tanımı (örneğin TSP'de iki kenar takası, scheduling'de iki iş yer değişimi, VRP'de relocate / swap / 2-opt*), bir hareket değerlendirme kuralı (ilk-iyi, en-iyi, en kötü-azalan) ve durma kriterinden oluşur. Yerel arama her zaman bir **yerel optimuma** yakınsar — komşuluk yapısı içinde iyileştirilemez nokta — ancak global optimum garantisi yoktur. Yerel optimumdan kaçınma için metasezgiseller geliştirilmiştir: tabu search (Glover 1989), simulated annealing (Kirkpatrick 1983), VNS (Mladenović ve Hansen 1997), iterated local search (Lourenço, Martin ve Stützle 2003). Yerel aramanın hız avantajı çok büyüktür: 10.000 noktalı TSP için bir Lin-Kernighan-türevi koşu modern hesaplayıcıda saniyeler içinde tam çözümün %0.5'i içinde sonuç verir. Aarts ve Lenstra (1997) *Local Search in Combinatorial Optimization* referans cilttir.