Ricerca locale iterata
in matematica e in informatica, la ricerca locale Iterata (in inglese Iterated local search, in acronimo ILS) è una modifica al livello di ricerca locale per risolvere problemi di combinatoria altrimenti difficili.
I metodi proposti da una ricerca locale possono rimanere bloccati in un minimo locale, dove non risiede alcun intorno migliorante.
Una semplice modifica consiste nell’iterare le chiamate di una ricerca locale in modo che ad ogni iterazione i parametri di configurazione siano diversi. Questa modalità viene anche chiamata ricerca locale iterata e implica che le informazioni ottenute durante le precedenti iterazioni non vengano utilizzate.
L'idea generica è di modificare i parametri a ogni iterazione applicando una perturbazione sui valori. Tuttavia questa perturbazione segue alcuni criteri e proprietà.
Algoritmo di perturbazione
Un buon algoritmo di perturbazione deve evitare di far cadere sempre nello stesso ''minimo locale''. Per questo è bene evitare le seguenti perturbazioni:
- troppo debole: in questo caso il rischio di cadere nello stesso minimo locale è molto alto.
- troppo forte: porta a un riavvio casuale da cui consegue una perdita di tutte le informazioni.
Benchmark di istanze
Mediante questa tecnica è possibile testare un insieme di istanze significative, quindi che non abbiano una probabilità bassa di accadere. Una volta selezionate, è possibile eseguire l'algoritmo per verificare il grafico di istanze su Benchmark e avere una visione d'insieme delle istanze passate in input.
Perturbazione adattiva
Un secondo metodo è rendere la perturbazione adattiva in run-time nel momento in cui non esiste alcuna funzione a priori che ci informa su quale sia il miglior risultato per la perturbazione scelta. In questo modo è possibile far sì che ad ogni iterazione cambi in base a condizioni o a istanze pseudo-casuali. Un esempio è dato dal lavoro di Battiti e Protasi che dimostrano come una perturbazione adattiva basata su tabu search porta a ottimi risultati per MAX-SAT.
Ottimizzazione delle sottoparti
In ogni caso è possibile ottimizzare una sottoparte del problema in modo da avere automaticamente ottimizzate tutte le nuove soluzioni generate dall'algoritmo.
Conclusioni
Questo metodo viene applicato in diversi casi di ottimizzazione combinatoria e problemi che includono job-shop scheduling, flow-shop problem, vehicle routing problem e altri.
Note
- ↑ H.R. Lourenço, Martin O. e Stützle T., Iterated Local Search: Framework and Applications, in Handbook of Metaheuristics, 2nd. Edition., 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.
- ↑ H.R. Lourenço, Martin O. e Stützle T., Iterated Local Search, in Handbook of Metaheuristics, Kluwer Academic Publishers, International Series in Operations Research & Management Science, vol. 57, 2003, pp. 321-353.
- ↑ H.R. Lourenço e Zwijnenburg M., Combining the large-step optimization with tabu-search: application to the job-shop scheduling problem, in Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, 1996, pp. 219-236.
- ↑ H.R. Lourenço, Job-Shop Scheduling: computational study of local search and large-step optimization methods, in European Journal of Operational Research, vol. 83, n. 2, 1995, pp. 347-364, DOI:10.1016/0377-2217(95)00012-F.
- ↑ A.A. Juan, Lourenço, H., Mateo, M., Luo, R. e Castella, Q., Using Iterated Local Search for solving the Flow-Shop Problem: parametrization, randomization and parallelization issues, in International Transactions in Operational Research, 2013.
- ↑ Puca H.V. Penna, L. Satori Ochi e A. Subramanian, An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem, in Journal of Heuristics, vol. 19, n. 2, 2013, pp. 201-232, DOI:10.1007/s10732-011-9186-y.
