Cerca local iterativa
Cerca local iterativa[1][2] (en anglès, Iterated local search, ILS)[3] és un terme de Matemàtiques aplicades i de Ciències de la computació que defineix una modificació de cerca local o de mètodes hill climbing per solucionar problemes d'optimització discreta.
Els mètodes de cerca local poden quedar atrapats en un mínim local, o sigui un punt solució que és òptim en el seu entorn.
Una modificació senzilla consisteix a fer crides iterativament a la rutina de cerca local, cada cop començant des d'una configuració inicial diferent. Això s'anomena cerca local repetida, i implica que el coneixement obtingut durant les fases de cerca locals anteriors no és utilitzat. Aprendre implica que la història anterior, per exemple la memòria sobre els mínims locals trobats anteriorment, s'extreu per produir cada vegada punts de partida millors per a la cerca local.
S'assumeix implícitament que hi ha una distribució agrupada de mínims localsː quan es minimitza una funció, és més fàcil determinar bons mínims locals quan es comença des d'un mínim local amb un valor baix que quan es comença des d'un punt aleatori. L'única precaució és evitar el confinament en una conca d'atracció, de manera que el salt per transformar un òptim local en el punt de partida per a la següent iteració ha de ser adequat. Si el salt és massa curt no ens escaparem de la zona del mínim local i si és massa llarg, el procés esdevindria un procés amb reinicis aleatoris sense memòria.
La cerca local iterativa està basada en la construcció d'una seqüència de solucions locals òptimes:
- pertorbant el mínim local actual;
- aplicant una cerca local després de començar des de la solució modificada.
La força de pertorbació ha de ser suficient per dirigir la trajectòria a una conca d'atracció diferent que condueixi a un òptim local diferent
El mètode ha estat aplicat a diversos problemes d'optimització combinatòria incloent -hi els problemes d'escalonament de processos,[4][5] els problemes de Flow-Shop,[3][6] els problemes d'enrutament de vehicles,[7] així com molts altres.
Referències modifica
- ↑ Lourenço, H.R. «Iterated Local Search: Framework and Applications». Handbook of Metaheuristics, 2nd. Edition., vol. 146, 2010, pàg. 363–397. DOI: 10.1007/978-1-4419-1665-5_12.
- ↑ Lourenço, H.R. «Iterated Local Search». Handbook of Metaheuristics, vol. 57, 2003, pàg. 321–353.
- ↑ 3,0 3,1 De Micheli, Mauro. Algoritmo de búsqueda local iterativa para la programación de piezas en un sistema flow shop híbrido. Universitat Politècnica de Catalunya. Departament d'Organització d'Empreses, 2009 (Escola Tècnica Superior d'Enginyeria Industrial de Barcelona - Enginyeria Industrial ; 2934).
- ↑ Lourenço, H.R. «Combining the large-step optimization with tabu-search: application to the job-shop scheduling problem». Meta-Heuristics: Theory and Applications, 1996, pàg. 219–236.
- ↑ Lourenço, H.R. «Job-Shop Scheduling: computational study of local search and large-step optimization methods». European Journal of Operational Research, vol. 83, 2, 1995, pàg. 347–364. DOI: 10.1016/0377-2217(95)00012-F.
- ↑ Juan, A.A. «Using Iterated Local Search for solving the Flow-Shop Problem: parametrization, randomization and parallelization issues». International Transactions in Operational Research, in press.
- ↑ Penna, Puca H.V..; Satori Ochi L. Subramanian A. «An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem». Journal of Heuristics, vol. 19, 2, 2013, pàg. 201–232. DOI: 10.1007/s10732-011-9186-y.