Ricerca locale iterata

Iterated local search perturba una soluzione in modo da uscire dall'ottimo locale

in matematica e in informatica, la ricerca locale Iterata (in inglese Iterated local search, in acronimo ILS)[1][2] è 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à.

  1. ^ 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.
  2. ^ 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.

© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search