Errori tipici · In sintesi¶

31.13 Errori tipici¶

Attenzione

Dimenticare che un ottimo locale dipende dall'intorno. La soluzione di \(LPT\) è un ottimo locale per move, ma non per swap.
Usare il numero di contenitori come unico obiettivo. È cieco: la maggior parte dei vicini ha lo stesso valore, e la ricerca si ferma su un plateau; l'obiettivo ausiliario \(SQ\) li distingue.
Ignorare l'ordine di esame. Le mosse sono esaminate in un ordine fissato e i pareggi vanno alla prima esaminata (nell'Esempio 31.6 l'oggetto \(3\) viene prima dell'oggetto \(5\)).
Calcolare il \(\Delta\) sbagliato per una mossa 2-opt. Contano solo i due lati tolti e i due lati aggiunti; i due lati tolti non possono avere una città in comune.
Concludere che un ottimo locale è ottimo. Solo un bound duale può dirlo.

In sintesi

Una ricerca locale si sposta su un vicino migliore finché ne esiste uno: restituisce un ottimo locale, un bound primale migliore.
First improvement è più veloce a ogni passo, best improvement prende il guadagno massimo; entrambe si fermano in un ottimo locale dell'intorno.
Valutazione incrementale, obiettivi ausiliari e penalità rendono la ricerca veloce e capace di attraversare plateau e regioni non ammissibili.
La variable neighbourhood descent e il multi-start allargano ciò che la ricerca può raggiungere, ma le ripartenze non hanno memoria.

Quadro delle istanze di riferimento. Soluzione di partenza e ottimo locale:

problema	partenza	ricerca locale	\(z(I)\)
TSP	\(25\) (\(NN\))	\(18\) (2-opt)	\(18\)
\(P\,\|\|\,C_{\max}\)	\(11\) (\(LPT\))	\(9\) (swap, \(=\mathrm{LB}(I)\))	\(9\)
BPP	\(4\) (\(FF\))	\(3\) (move, \(SQ\))	\(3\)

I bound duali vengono dal capitolo «Algoritmi euristici: definizioni»: la sola ricerca locale non certifica il suo risultato.

Esercizi su questo capitolo: Ricerca locale