Căutare locală iterată
Căutare locală iterată sau iterată Căutare locală [1] [2] (ILS) este un termen folosit în matematică și informatică care definește o schimbare la nivelul căutării locale pentru a rezolva problemele combinatorii altfel dificile.
Metodele propuse de o căutare locală se pot bloca într-un minim local , în care nu se află niciun cartier îmbunătățit.
O simplă modificare este de a itera apelurile unei căutări locale, astfel încât la fiecare iterație parametrii de configurare să fie diferiți. Acest mod se mai numește căutare locală iterată și implică faptul că informațiile obținute în timpul iterațiilor anterioare nu sunt utilizate.
Ideea generală este de a modifica parametrii la fiecare iterație prin aplicarea unei perturbații asupra valorilor. Cu toate acestea, această perturbare urmează câteva criterii și proprietăți.
Algoritm de perturbare
Un algoritm de perturbare bun trebuie să evite să ne lase să cădem mereu în același „minim local”. Pentru aceasta este bine să evitați următoarele tulburări:
- prea slab: în acest caz riscul de a cădea în același minim este foarte mare.
- prea puternic: duce la o repornire aleatorie care duce la pierderea tuturor informațiilor.
Reperul instanțelor
Folosind această tehnică este posibil să testați un set de instanțe semnificative, astfel încât să nu aibă o probabilitate redusă de a se întâmpla. Odată selectat, puteți rula algoritmul pentru a verifica graficul instanțelor de pe Benchmark și pentru a avea o imagine de ansamblu a instanțelor transmise în intrare.
Perturbație adaptivă
O a doua metodă este de a face perturbarea adaptivă în timp de execuție atunci când nu există o funcție a priori care să ne informeze care este cel mai bun rezultat pentru perturbarea aleasă. În acest fel, este posibil să se facă fiecare modificare de iterație în funcție de condiții sau instanțe pseudo-aleatorii. Un exemplu este dat de lucrările lui Battiti și Protasi care demonstrează modul în care o perturbație adaptivă bazată pe căutare tabu duce la rezultate excelente pentru MAX-SAT .
Optimizarea subpărților
În orice caz, este posibilă optimizarea unei sub-părți a problemei pentru a fi optimizate automat toate noile soluții generate de algoritm.
Concluzii
Această metodă este aplicată în mai multe cazuri de optimizare combinatorie și probleme care includ probleme de programare a magazinului de locuri de muncă , [3] [4] probleme de flux de magazine, [5] probleme de rutare a vehiculelor [6] și alte probleme.
Notă
- ^ HR Lourenço, Martin O. și Stützle T., Iterated Local Search: Framework and Applications , în Handbook of Metaheuristics, 2nd. Ediție. , Kluwer Academic Publishers, International Series in Operations Research & Management Science, vol. 146, 2010, pp. 363–397, DOI : 10.1007 / 978-1-4419-1665-5_12 .
- ^ HR Lourenço, Martin O. și Stützle T., Iterated Local Search , în Handbook of Metaheuristics , Kluwer Academic Publishers, International Series in Operations Research & Management Science, vol. 57, 2003, pp. 321–353.
- ^ HR Lourenço și Zwijnenburg M., Combinarea optimizării pasului mare cu tabu-căutare: aplicație la problema de planificare a magazinului de locuri de muncă , în Meta-Heuristics: Theory and Applications , Kluwer Academic Publishers, 1996, pp. 219-236.
- ^ HR Lourenço, Job-Shop Scheduling: studiu computațional de căutare locală și metode de optimizare în pași mari , în European Journal of Operational Research , vol. 83, nr. 2, 1995, pp. 347–364, DOI : 10.1016 / 0377-2217 (95) 00012-F .
- ^ AA Juan, Lourenço, H., Mateo, M., Luo, R. și Castella, Q., Utilizarea căutării locale iterate pentru rezolvarea problemei Flow-Shop: probleme de parametrizare, randomizare și paralelizare , în Tranzacții internaționale în cercetarea operațională , 2013.
- ^ Puca HV Penna, L. Satori Ochi și A. Subramanian, o euristică de căutare locală iterată pentru problema de rutare a vehiculelor flotei heterogene , în Journal of Heuristics , vol. 19, nr. 2, 2013, pp. 201–232, DOI : 10.1007 / s10732-011-9186-y .
