Iterated local search
Ricerca Locale Iterata oppure Iterated Local Search[1][2] (ILS) è un termine utilizzato in matematica e in informatica definisce 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 ad ogni iterazione applicando una perturbazione sui valori. Tuttavia questa perturbazione segue alcuni criteri e proprietà.
Algoritmo di Perturbazione modifica
Un buon algoritmo di perturbazione deve evitare di farci 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 modifica
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 modifica
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 modifica
In ogni caso è possibile ottimizzare una sottoparte del problema in modo da avere automaticamente ottimizzate tutte le nuove soluzioni generate dall'algoritmo.
Conclusioni modifica
Questo metodo viene applicato in diversi casi di Combinatorial Optimization e problemi che includono Job-Shop Scheduling problemi,[3][4] Flow-Shop Problems,[5] Vehicle Routing Problems[6] e altri problemi.
Note modifica
- ^ 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.
