Ricerca locale¶
Parte 4 · Algoritmi euristici · Capitolo 31 · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Ricerca locale · App: TSP: nearest neighbour e 2-opt
Prerequisiti
-
Da questo modulo, il capitolo «Algoritmi euristici: definizioni»: intorni, ottimi locali, intensificazione e diversificazione.
-
Da questo modulo, il capitolo «Euristiche costruttive»: le soluzioni di partenza usate qui.
Obiettivi
Alla fine di questo capitolo saremo in grado di:
-
definire gli intorni del KP, del BPP, del TSP e di \(P\,||\,C_{\max}\);
-
eseguire una ricerca locale con le regole first improvement e best improvement;
-
valutare una mossa in modo incrementale, in \(O(1)\) per la mossa 2-opt;
-
uscire da un plateau con un obiettivo ausiliario, e gestire le soluzioni non ammissibili con una penalità;
-
combinare più intorni (variable neighbourhood descent) e più ripartenze (multi-start).
31.1 Ricerca locale¶
Definizione 31.1: Ricerca locale
Dato un intorno \(N\), una ricerca locale (indicata con \(LS\)) è un'euristica di miglioramento. Parte da una soluzione ammissibile e, a ogni iterazione, cerca nell'intorno della soluzione corrente una soluzione migliore. Se la trova, si sposta su di essa e ripete; se nessun vicino è migliore, la soluzione corrente è un ottimo locale rispetto a \(N\) e la ricerca si ferma.
- L'intorno \(N(S)\) di una soluzione ammissibile \(S\), la mossa da \(S\) a un vicino e l'ottimo locale rispetto a \(N\) sono definiti nel capitolo «Algoritmi euristici: definizioni».
Una ricerca locale migliora una soluzione ammissibile spostandosi da una soluzione a un vicino migliore, e si ferma in un ottimo locale rispetto a \(N\).
-
Panoramica
Ricerca locale
-
31.2 I problemi, le ipotesi e le soluzioni di partenza
-
Ricerca locale: lo schema · Intorni per i quattro problemi
KP: flip e swap · BPP: move e swap · TSP: 2-opt e Or-opt · P\,||\,Cmax: move e swap · Riepilogo
-
31.5 First improvement e best improvement
Best improvement · Confronto
-
31.6 Valutare una mossa in modo incrementale
-
31.7 TSP: 2-opt e Or-opt
La ricerca locale Or-opt · First e best improvement su un'istanza media · 3-opt e Lin–Kernighan
-
31.8 \(P\,||\,C_{\max}\): move e swap
La ricerca locale swap
-
31.9 Paesaggi piatti e obiettivi ausiliari
L'obiettivo ausiliario · La ricerca locale move per il BPP · La ricerca locale swap per il BPP · Proprietà dell'obiettivo ausiliario · Esempi
-
31.10 KP: ammissibilità e penalità
Penalizzare il peso in eccesso
-
31.11 Variable neighbourhood descent
-
31.12 Ricerca locale multi-start
Che cosa dà la ricerca locale, e che cosa non dà
-
Errori tipici · In sintesi
In sintesi
Avanti: 31.2 I problemi, le ipotesi e le soluzioni di partenza
Esercizi su questo capitolo: Ricerca locale
Nel laboratorio interattivo: TSP: nearest neighbour e 2-opt.