Ricerca locale

In informatica, la ricerca locale è una tipologia di metodi euristici atti a risolvere problemi di ricerca e di ottimizzazione computazionalmente complessi. La ricerca locale può essere utilizzata su problemi che possono essere formulati come problemi di ricerca di una soluzione fra un certo numero di soluzioni candidate che soddisfi vincoli dati o che massimizzi/minimizzi un criterio. Gli algoritmi di ricerca locale si spostano da una soluzione all'altra nello spazio delle soluzioni candidate (lo spazio di ricerca) applicando modifiche locali, fino a quando non viene trovata una soluzione ritenuta ottimale o non si è raggiunto un limite temporale.

Gli algoritmi di ricerca locale sono ampiamente applicati a numerosi problemi computazionali complessi, inclusi problemi di informatica (in particolare di intelligenza artificiale), matematica, ricerca operativa, ingegneria e bioinformatica. Esempi di algoritmi di ricerca locale sono WalkSAT, l'algoritmo 2-opt per il problema del commesso viaggiatore e l'algoritmo Metropolis-Hastings.

A volte è possibile sostituire la discesa di gradiente a un algoritmo di ricerca locale, ma la discesa del gradiente non appartiene alla stessa famiglia: sebbene essa costituisca un metodo iterativo per l'ottimizzazione locale, si basa sul gradiente di una funzione obiettivo piuttosto che sull'esplicita esplorazione dello spazio delle soluzioni.

Esempi

Seguono alcuni problemi risolubili tramite metodi di ricerca locale:

1. Il problema della copertura dei vertici, in cui una soluzione è una copertura dei vertici di un grafo e l'obiettivo è trovare una soluzione con un numero minimo di nodi.
2. Il problema del commesso viaggiatore, in cui una soluzione è un percorso ciclico contenente tutti i nodi del grafo e l'obiettivo è minimizzare la lunghezza totale del ciclo.
3. Il problema di soddisfacibilità booleana, in cui una soluzione candidata è un'assegnazione di verità e l'obiettivo è massimizzare il numero di clausole soddisfatte dall'assegnazione; in questo caso, la soluzione finale è utile solo se soddisfa tutte le clausole
4. Il problema della programmazione infermieristica in cui una soluzione è l'assegnazione degli infermieri a turni che soddisfano tutti i vincoli stabiliti.
5. Il problema del clustering con k-medoid e altri problemi correlati di localizzazione di strutture per i quali la ricerca locale offre i migliori gradi di approssimazione noti nella prospettiva del caso peggiore.
6. Il problema delle reti neurali di Hopfield consiste nel trovare configurazioni stabili nella rete.

Descrizione

La maggior parte dei problemi possono essere formulati in diversi modi in termini di spazio di ricerca e obiettivo. Ad esempio, per il problema del commesso viaggiatore, una soluzione può essere un itinerario che tocchi tutte le città e l'obiettivo è quello di trovare il percorso più breve. Ma una soluzione può anche essere un percorso, e il costituire un ciclo fa parte dell'obiettivo.

Un algoritmo di ricerca locale parte da una soluzione candidata e poi si sposta iterativamente verso una soluzione vicina; un vicinato è l'insieme di tutte le possibili soluzioni che differiscono il minimo possibile dalla soluzione corrente. Ciò richiede una relazione di vicinato definita sullo spazio di ricerca. Ad esempio, il vicinato di una copertura di vertici è un'altra copertura di vertici che differisce solo per un nodo. Nel caso della soddisfacibilità booleana, i vicini di un'assegnazione booleana sono quelli che hanno una singola variabile in uno stato opposto. Lo stesso problema può avere più vicini distinti definiti su di esso; l'ottimizzazione locale con vicini che comportano la modifica di un numero di componenti della soluzione fino a k viene spesso definita k-opt.

In genere, ogni soluzione candidata ha più di una soluzione vicina; la scelta di quella da selezionare viene effettuata utilizzando solo informazioni sulle soluzioni nel vicinato dell'assegnazione corrente, da cui il nome di ricerca locale. Quando la scelta della soluzione vicina viene effettuata prendendo quella che massimizza localmente il criterio, ovvero una ricerca greedy, la metaeuristica prende il nome di hill climbing. Quando non sono presenti vicini migliorativi, la ricerca locale si blocca in un punto localmente ottimo. Questo problema di ottimi locali può essere risolto utilizzando riavvii (ricerca locale ripetuta con diverse condizioni iniziali), randomizzazione o schemi più complessi basati, a loro volta, su iterazioni, come la ricerca locale iterata, sulla memorizzazione, come l'ottimizzazione a ricerca reattiva, oppure su modifiche stocastiche senza memoria, come il simulated annealing.

La ricerca locale non garantisce che ogni data soluzione sia ottimale. La ricerca può terminare dopo un dato limite di tempo o quando la migliore soluzione trovata fino a un dato momento non è migliorata in un dato numero di passi recenti. La ricerca locale è un algoritmo anytime; può restituire una soluzione valida anche se interrotta in qualsiasi momento dopo aver trovato la prima soluzione valida. La ricerca locale è effettuata in genere da un algoritmo di approssimazione o non completo perché la ricerca può interrompersi anche se la migliore soluzione corrente trovata non è ottimale. Ciò può accadere anche se la terminazione avviene perché la migliore soluzione corrente non può essere migliorata, poiché la soluzione ottimale può trovarsi lontano dal vicinato attraversato dall'algoritmo.

Schuurman e Southey propongono le seguenti tre misure di efficacia per metodi di ricerca locale:

• profondità: il costo della soluzione (migliore) attuale;
• mobilità: la capacità di spostarsi rapidamente in diverse aree dello spazio di ricerca (mantenendo bassi i costi);
• copertura: con quale sistematicità la ricerca copre lo spazio di ricerca, la distanza massima tra qualsiasi assegnazione inesplorata e tutte le assegnazioni visitate.

Si assume che gli algoritmi di ricerca locale funzionino bene non perché abbiano una qualche comprensione dello spazio di ricerca, ma perché si spostano rapidamente verso regioni promettenti ed esplorano lo spazio di ricerca a profondità basse nel modo più rapido, ampio e sistematico possibile.

Bibliografia

• Roberto Battiti, Mauro Brunato e Franco Mascia, Reactive Search and Intelligent Optimization, Springer Verlag, 2008, ISBN 978-0-387-09623-0.
• Hoos, H.H. and Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann.
• Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal of Computing 33(3).
• Juraj Hromkovič: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics (Springer)
• Wil Michiels, Emile Aarts, Jan Korst: Theoretical Aspects of Local Search (Springer)

Voci correlate

• Metaeuristica
• Ottimizzazione stocastica
• Ottimizzazione

I campi della ricerca locale includono:

• Hill climbing
• Simulated annealing (adatta per la ricerca locale o globale)
• Ricerca tabù
• Ottimizzazione della ricerca reattiva (combinazione di apprendimento automatico ed euristica di ricerca locale)

Spazi di ricerca a valori reali

Esistono diversi metodi per eseguire la ricerca locale di spazi di ricerca a valori reali:

• Il metodo di Luus–Jaakola effettua ricerche a livello locale utilizzando una distribuzione uniforme e un intervallo di ricerca che decresce in modo esponenziale.
• Ricerche con metodi di ottimizzazione casuale che usano localmente una distribuzione normale.
• La ricerca casuale effettua ricerche localmente campionando un'ipersfera attorno alla posizione corrente.
• La ricerca di pattern procede lungo gli assi dello spazio di ricerca utilizzando dimensioni dei passi che decrescono in modo esponenziale.