Pencarian Lokal Teriterasi
Pencarian lokal berulang (ILS) adalah istilah dalam matematika terapan dan ilmu komputer yang mendefinisikan modifikasi metode pencarian atau penskalaan lokal untuk memecahkan masalah optimasi diskrit.Metode pencarian lokal bisa terjebak dalam kondisi minimum lokal di mana tidak ada tetangga terbaik yang tersedia.
Perubahan sederhana adalah mengulangi panggilan ke rutinitas pencarian lokal, setiap kali dimulai dengan konfigurasi awal yang berbeda. Ini disebut pencarian lokal berulang dan berarti bahwa pengetahuan yang diperoleh pada tahap pencarian lokal sebelumnya tidak digunakan. Pembelajaran berarti mengevaluasi sejarah sebelumnya, seperti ingatan tentang nilai minimum lokal yang ditemukan sebelumnya, untuk menciptakan titik awal yang lebih baik untuk penelusuran lokal.
ketika meminimalkan suatu fungsi, menentukan minimum lokal yang baik akan lebih mudah jika Anda memulai dari minimum lokal dengan nilai yang rendah dibandingkan jika Anda memulai dari titik acak. Satu-satunya batasan adalah menghindari pembatasan pada wadah penarik tertentu. Oleh karena itu, tendangan untuk menjadikan minimer lokal sebagai titik awal untuk putaran berikutnya harus cukup kuat, tetapi tidak terlalu kuat, sehinggaterhindar dari serangan balik. untuk reboot secara acak dari memori.
Algoritma Perturbasi
Menemukan algoritma perturbasi untuk pencarian lokal teriterasi (ILS) bukanlah tantangan yang mudah. Tujuan utamanya adalah untuk menghindari ketergantungan pada nilai minimum lokal yang sama dan untuk memastikan pencapaian properti ini, operasi penghapusan dilarang. Namun banyak hal yang perlu diperhatikan dalam merancang permutasi yang efektif karena ada dua jenis permutasi yang dianggap buruk. Pertama, permutasinya terlalu lemah, yang mungkin mengakibatkan penggunaan minimum lokal yang sama,. Kedua, permutasinya terlalu kuat, sehingga menyebabkan restart secara acak dan menyulitkan pencarian solusi optimal.Oleh karena itu, menciptakan algoritma perturbasi yang seimbang dan efisien sangat penting untuk mengoptimalkan kinerja pencarian lokal berulang.
Gangguan tolok ukur
Prosedurnya adalah menetapkan sekumpulan nilai gangguan sedemikian rupa sehingga nilai-nilai ini signifikan untuk suatu peristiwa: probabilitas sedang dan tidak jarang. Kemudian dimungkinkan untuk memeriksa grafik referensi pada waktu proses untuk mendapatkan gambaran rata-rata dari kejadian sebelumnya.
Gangguan adaptif
Karena tidak ada fungsi apriori yang menentukan nilai mana yang paling sesuai untuk suatu kelainan tertentu, pendekatan terbaik adalah menjadikannya adaptif. Misalnya, Battiti dan Protasi dalam mengusulkan algoritma pencarian reaktif untuk MAX-SAT, yang cocok dengan kerangka ILS. Mereka melakukan skema gangguan “terarah” yang diimplementasikan menggunakan algoritma pencarian Tabu dan menerapkan algoritma penurunan lokal standar setelah setiap gangguan. Cara lain untuk beradaptasi terhadap gangguan adalah dengan mengubah kekuatannya secara deterministik selama pencarian.
Optimalkan gangguan
Pendekatan lainnya adalah mengoptimalkan subbagian masalah dengan menjaga properti No Undo tetap aktif. Jika metode ini memungkinkan, solusi apa pun yang dihasilkan setelah gangguan mungkin akan sangat baik. Selain itu, suku cadang baru juga dioptimalkan.
Disadur dari: en.wikipedia.org