Iterated local search
# Iterated local search

Ricerca Locale Iterata oppure Iterated Local Search (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

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

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 Combinatorial Optimization e problemi che includono Job-Shop Scheduling problemi, Flow-Shop Problems, Vehicle Routing Problems e altri problemi.

