31.5 First improvement e best improvement¶
Parte 4 · Algoritmi euristici · Capitolo 31 · Capitolo 31: Ricerca locale · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Ricerca locale · App: TSP: nearest neighbour e 2-opt
- La funzione \(\textit{Improve}\) di \(LS\) può fermarsi al primo vicino migliorante che trova, oppure esaminare tutto l'intorno e restituire il vicino migliore. Gli pseudocodici sono scritti per un problema di minimizzazione; per un problema di massimizzazione, “\(<\)” diventa “\(>\)”.
31.5.1 First improvement¶
La regola first improvement esamina i vicini della soluzione corrente in un ordine fissato e restituisce il primo vicino migliore della soluzione corrente. Se nessun vicino è migliore, restituisce \(\textit{NULL}\).
Algoritmo: First improvement
31.5.2 Best improvement¶
La regola best improvement esamina tutti i vicini della soluzione corrente e restituisce il migliore, se è migliore della soluzione corrente; i pareggi si risolvono a favore del vicino esaminato per primo. Se nessun vicino è migliore, restituisce \(\textit{NULL}\).
Algoritmo: Best improvement
31.5.3 Confronto¶
-
In un ottimo locale entrambe le regole esaminano tutto l'intorno: l'ultima iterazione costa lo stesso.
-
Prima di raggiungerlo, first improvement esegue iterazioni meno costose, perché si ferma al primo vicino migliorante, ma ogni mossa di solito migliora meno, quindi tende a eseguire più mosse. Best improvement esegue la discesa più ripida: ogni iterazione costa un'esplorazione completa dell'intorno, e ogni mossa migliora il più possibile.
-
Le due regole seguono percorsi diversi, quindi possono fermarsi in ottimi locali diversi. Nessuna delle due regole è migliore dell'altra su tutte le istanze: la mossa più ripida ora può portare in una valle peggiore dopo.
-
Con first improvement il risultato dipende dall'ordine in cui sono esaminati i vicini; rendere casuale quell'ordine è un modo semplice per ottenere ottimi locali diversi dalla stessa soluzione di partenza.
Esempio 31.1: First e best improvement sul KP
Partiamo dalla soluzione del greedy per peso \(GR_w\) sull'istanza di riferimento del KP (\(c=9\)), cioè \(x=(0,0,1,1)\), di peso \(6\) e profitto \(10\), con l'intorno flip+swap. I vicini sono esaminati nell'ordine della Sezione 31.4:
| mossa | vicino | peso | profitto | |
|---|---|---|---|---|
| flip \(1\) | \((1,0,1,1)\) | \(11\) | — | non ammissibile |
| flip \(2\) | \((0,1,1,1)\) | \(10\) | — | non ammissibile |
| flip \(3\) | \((0,0,0,1)\) | \(3\) | \(4\) | |
| flip \(4\) | \((0,0,1,0)\) | \(3\) | \(6\) | |
| swap \(3\) fuori, \(1\) dentro | \((1,0,0,1)\) | \(8\) | \(14\) | \(\leftarrow\) first improvement |
| swap \(3\) fuori, \(2\) dentro | \((0,1,0,1)\) | \(7\) | \(11\) | |
| swap \(4\) fuori, \(1\) dentro | \((1,0,1,0)\) | \(8\) | \(16\) | \(\leftarrow\) best improvement |
| swap \(4\) fuori, \(2\) dentro | \((0,1,1,0)\) | \(7\) | \(13\) |
First improvement accetta \((1,0,0,1)\), di profitto \(14\), dopo aver esaminato \(3\) vicini ammissibili. Da \((1,0,0,1)\) (peso \(8\)) i vicini sono esaminati di nuovo dall'inizio:
| mossa | vicino | peso | profitto | |
|---|---|---|---|---|
| flip \(1\) | \((0,0,0,1)\) | \(3\) | \(4\) | |
| flip \(2\) | \((1,1,0,1)\) | \(12\) | — | non ammissibile |
| flip \(3\) | \((1,0,1,1)\) | \(11\) | — | non ammissibile |
| flip \(4\) | \((1,0,0,0)\) | \(5\) | \(10\) | |
| swap \(1\) fuori, \(2\) dentro | \((0,1,0,1)\) | \(7\) | \(11\) | |
| swap \(1\) fuori, \(3\) dentro | \((0,0,1,1)\) | \(6\) | \(10\) | |
| swap \(4\) fuori, \(2\) dentro | \((1,1,0,0)\) | \(9\) | \(17\) | \(\leftarrow\) first improvement |
e \((1,1,0,0)\), di profitto \(17\), è accettata dopo \(5\) vicini ammissibili. È la soluzione ottima, quindi nessun vicino è migliore: i \(6\) vicini ammissibili sono esaminati e la ricerca si ferma. In totale: \(2\) mosse, \(3+5+6=14\) vicini ammissibili esaminati.
Best improvement esamina tutti i \(6\) vicini ammissibili di \((0,0,1,1)\) e si sposta su \((1,0,1,0)\), di profitto \(16\). È la soluzione di \(GR\), il cui intorno è nel capitolo «Algoritmi euristici: definizioni»: il vicino migliore è \((1,1,0,0)\), di profitto \(17\), raggiunto con lo swap “\(3\) fuori, \(2\) dentro”. La ricerca si ferma lì dopo aver esaminato i suoi \(6\) vicini ammissibili. In totale: \(2\) mosse, \(6+6+6=18\) vicini ammissibili esaminati.
Le due regole raggiungono l'ottimo lungo percorsi diversi, \(10\to14\to17\) e \(10\to16\to17\), e first improvement esamina meno vicini. Il solo intorno flip non si sarebbe mosso affatto: da \((0,0,1,1)\) ogni flip ammissibile toglie un oggetto, quindi \((0,0,1,1)\), di profitto \(10\), è un ottimo locale per flip.