Ricerca Locale

La tecnica di Ricerca Locale (RL) per la progettazione di algoritmi si applica a problemi di ottimizzazione, ovvero a quei problemi per i quali occorre trovare la soluzione ammissibile di costo ottimo. La tecnica si basa sulla definizione di un intorno di una soluzione e della scelta, ad ogni passo, della soluzione che migliora di più la soluzione corrente. Data la soluzione s appartenete alle possibili soluzioni S, si definisce l’intorno I(s) di s come l’insieme delle soluzioni s’ appartenenti a S, ottenibili da s attraverso una predeterminata regola di trasformazione, ovvero:

un passo di RL consiste nel selezionare:

Ovvero selezionare una soluzione Sm, dalle possibili soluzioni e verificare che sia più ottimizzata della soluzione s presa in partenza. Vediamo un esempio, si consideri il problema del minimo albero di copertura. Sia dato un grafo pesato G, prendiamo come possibile soluzione s, un albero di copertura T, quindi un albero avente tutti i nodi del grafo e solo un sottoinsieme dei suoi archi. A questo punto possiamo ottenere un albero T ’ semplicemente sostituendo un arco [i,j] appartenete a T con un arco [h,k] non appartenete a T, in modo che c(T’) <= c(T), ovvero la soluzione con l ‘alberoT’ deve essere più ottimizzata e quindi la somma del valore degli archi di T’ è minore di quella di T.

Un criterio di miglioramento consiste nello scegliere un albero T in cui l’ arco aggiunto ha un peso minore dell’ arco cancellato.

In generale, il procedimento di ricerca locale si arresta su una soluzione che è un ottimo locale, cioè che non può essere migliorata attraverso le trasformazioni possibili. Partendo da soluzioni iniziali diverse si possono raggiungere ottimi locali diversi. Ovviamente se I(T) comprende tutte le soluzioni ammissibili del problema, allora ogni ottimo locale è anche ottimo globale e la ricerca locale da sempre la soluzione ottima del problema. In modo più formale possiamo affermare che l’esplorazione dell’intorno genera una sequenza di soluzioni s₀,…,s_n tale che c(s₀)>=…>=c(s_n).
s_n è detta ottimo locale che risulta ottimo globale quando vale che:

Non sempre la RL trova un ottimo locale che risulta essere anche un ottimo globale, come mostrato in figura.

Un algoritmo di tipo Ricerca Locale appartengono alla classe delle euristiche di miglioramento. Sono euristici quegli algoritmi che non garantiscono di fornire la soluzione ottima. Ovvero, data una soluzione iniziale ammissibile s, essa è migliorata attraverso successive trasformazioni di s. Quindi è necessario fornire una soluzione come input. La soluzione iniziale può essere costruita con le cosiddette euristiche costruttive, che sono algoritmi di tipo Greedy, BackTrack … Uno schema consolidato nella progettazione di algoritmi prevede la costruzione della soluzione iniziale con un algoritmo di tipo Greedy e l’applicazione successiva di una RL. Per saperne di più consultai seguenti approfondimenti:

TSP "Traveling Salesman Problem"

Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.