Pencarian Lokal Berulang (ILS) adalah istilah dalam matematika terapan dan ilmu komputer yang mendefinisikan modifikasi pencarian lokal atau metode mendaki bukit untuk memecahkan masalah optimasi diskrit.
Metode pencarian lokal bisa macet di minimum lokal, di mana tidak ada tetangga yang lebih baik yang tersedia.
Modifikasi sederhana terdiri dari panggilan iterasi ke rutin pencarian lokal, setiap kali dimulai dari konfigurasi awal yang berbeda. Ini disebut pencarian lokal berulang, dan menyiratkan bahwa pengetahuan yang diperoleh selama fase pencarian lokal sebelumnya tidak digunakan. Pembelajaran menyiratkan bahwa sejarah sebelumnya, misalnya memori tentang minima lokal yang ditemukan sebelumnya, ditambang untuk menghasilkan titik awal yang lebih baik dan lebih baik untuk pencarian lokal.
Asumsi implisitnya adalah distribusi berkerumun dari minima lokal: ketika meminimumkan suatu fungsi, menentukan minima lokal yang baik lebih mudah ketika memulai dari minimum lokal dengan nilai rendah daripada saat memulai dari titik acak. Satu-satunya peringatan adalah untuk menghindari kurungan di baskom atraksi tertentu, sehingga tendangan untuk mengubah peminim lokal menjadi titik awal untuk lari berikutnya harus cukup kuat, tetapi tidak terlalu kuat untuk menghindari kembali ke restart acak tanpa memori.
Pencarian Lokal Berulang didasarkan pada pembuatan urutan solusi optimal lokal dengan:
- mengganggu minimum lokal saat ini;
- menerapkan pencarian lokal setelah memulai dari solusi yang dimodifikasi.
Kekuatan gangguan harus cukup untuk mengarahkan lintasan ke cekungan tarikan yang berbeda yang mengarah ke optimum lokal yang berbeda.
Algoritma Gangguan
Algoritma gangguan untuk ILS bukanlah tugas yang mudah. Tujuan utamanya adalah untuk tidak terjebak dalam minimum lokal yang sama dan untuk mendapatkan properti ini benar, operasi undo dilarang. Meskipun demikian, permutasi yang baik harus mempertimbangkan banyak nilai, karena ada dua jenis permutasi buruk:
- terlalu lemah: kembali ke minimum lokal yang sama
- terlalu kuat: restart acak
Gangguan Tolok Ukur
Prosedurnya terdiri dari memperbaiki sejumlah nilai untuk gangguan sedemikian rupa sehingga nilai-nilai ini signifikan misalnya: pada probabilitas rata-rata dan tidak jarang. Setelah itu, pada saat runtime akan memungkinkan untuk memeriksa plot benchmark untuk mendapatkan ide rata-rata pada instance yang dilewati.
Gangguan Adaptif
Karena tidak ada fungsi apriori yang memberi tahu mana yang merupakan nilai yang paling cocok untuk gangguan tertentu, kriteria terbaik adalah membuatnya adaptif. Misalnya Battiti dan Protasi mengusulkan algoritma pencarian reaktif untuk MAX-SAT yang sangat cocok dengan kerangka kerja ILS. Mereka melakukan skema gangguan "terarah" yang diimplementasikan oleh algoritma pencarian tabu dan setelah setiap gangguan mereka menerapkan algoritma keturunan lokal standar. Cara lain untuk mengadaptasi gangguan adalah dengan mengubah secara deterministik kekuatannya selama pencarian.
Mengoptimalkan Gangguan
Prosedur lain adalah mengoptimalkan sub-bagian dari masalah, dengan mengaktifkan properti not-undo. Jika prosedur ini memungkinkan, semua solusi yang dihasilkan setelah gangguan cenderung sangat baik. Selanjutnya bagian-bagian baru juga dioptimalkan.
Kesimpulan
Metode ini telah diterapkan pada beberapa masalah optimasi kombinatorial termasuk masalah Penjadwalan Job Shop, Masalah Flow-Shop, Masalah Perutean Kendaraan serta banyak lainnya.
Sumber Artikel: en.wikipedia.org