31.12 Ricerca locale multi-start¶
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 ricerca locale si ferma nell'ottimo locale della valle in cui parte. Il modo più semplice di esplorare altre valli è ripartire da una soluzione diversa, e tenere il miglior ottimo locale.
La ricerca locale multi-start (indicata con \(MSLS\)) genera \(M\) soluzioni di partenza, a caso o con un'euristica costruttiva randomizzata, esegue una ricerca locale da ciascuna di esse, in modo indipendente, e restituisce il miglior ottimo locale trovato.
Algoritmo: 2-opt multi-start
- Le \(M\) ricerche locali sono indipendenti: possono essere eseguite in parallelo, e il risultato non dipende dal loro ordine. Il multi-start è la forma più semplice di diversificazione.
Esempio 31.11: \(MSLS\) sul TSP con \(10\) città
Sull'istanza dell'Esempio 31.3, \(100\) giri casuali (seme \(1\)), ciascuno migliorato da una ricerca locale, terminano nei seguenti ottimi locali:
| intorno | regola | esecuzioni nell'ottimo \(39\) | altri ottimi locali (esecuzioni) |
|---|---|---|---|
| 2-opt | first | \(46\) | \(41\) (\(54\)) |
| 2-opt | best | \(87\) | \(41\) (\(8\)), \(43\) (\(5\)) |
| Or-opt | first | \(72\) | \(43\) (\(26\)), \(44\) (\(2\)) |
| Or-opt | best | \(77\) | \(43\) (\(22\)), \(44\) (\(1\)) |
| \(VND\) (2-opt, Or-opt) | first | \(100\) | — |
| \(VND\) (2-opt, Or-opt) | best | \(100\) | — |
Con 2-opt e first improvement, il primo giro casuale termina nell'ottimo locale di lunghezza \(41\) e il terzo nell'ottimo. Su questa istanza best improvement è molto migliore di first improvement, e \(VND\) trova sempre l'ottimo, l'unico giro che è un ottimo locale per entrambi gli intorni.
Esempio 31.12: \(MSLS\) sul TSP con \(30\) città
Le \(30\) città hanno coordinate \((\lfloor 101u_{2k-1}\rfloor,\lfloor 101u_{2k}\rfloor)\), \(k=1,\dots,30\), dove \(u_1,u_2,\dots\) sono generati con seme \(12345\), e \(d_{ij}\) è la distanza euclidea arrotondata all'intero più vicino. Il giro ottimo, calcolato con un solutore MIP, ha lunghezza \(z(I)=478\). Il migliore dei \(30\) giri di \(NN\) (uno per ogni città di partenza) ha lunghezza \(537\).
I \(100\) giri casuali (seme \(1\)) hanno una lunghezza media di \(1768.73\) (fra \(1364\) e \(2080\)). Dopo la ricerca locale 2-opt:
| first improvement | best improvement | |
|---|---|---|
| ottimi locali distinti | \(59\) | \(54\) |
| esecuzioni che terminano nell'ottimo | \(14\) | \(12\) |
| lunghezza media (errore relativo) | \(488.45\) (\(2.2\%\)) | \(487.24\) (\(1.9\%\)) |
| lunghezza peggiore (errore relativo) | \(537\) (\(12.3\%\)) | \(567\) (\(18.6\%\)) |
| prima esecuzione che trova l'ottimo | \(2\) | \(9\) |
Gli ottimi locali si distribuiscono come segue (numero di esecuzioni per classe di lunghezza):
La ricerca locale trasforma giri di lunghezza circa \(1769\) in giri entro il \(2\%\) dall'ottimo in media; ma ogni esecuzione termina nella sua valle, e solo circa un'esecuzione su otto raggiunge l'ottimo.
31.12.1 I limiti del multi-start¶
-
Nessuna memoria. Ogni esecuzione riparte da zero e ignora ciò che hanno trovato le precedenti. Se un'esecuzione raggiunge l'ottimo con probabilità \(q\), indipendentemente dalle altre, \(M\) esecuzioni lo mancano tutte con probabilità \((1-q)^M\). Con \(q=0.12\), come nell'ultimo esempio con best improvement, \(10\) esecuzioni mancano l'ottimo con probabilità \(0.88^{10}\approx 0.28\), e servono \(37\) esecuzioni per portare questa probabilità sotto l'\(1\%\).
-
La probabilità \(q\) si riduce. Il numero di ottimi locali cresce molto rapidamente con \(n\): con \(10\) città solo \(3\) giri sono ottimi locali 2-opt, con \(30\) città \(100\) esecuzioni ne trovano più di \(50\) distinti. Sulle istanze grandi una partenza casuale non raggiunge quasi mai l'ottimo, e \((1-q)^M\) è vicino a \(1\) per ogni \(M\) ragionevole.
-
La maggior parte del tempo si spende a scendere. Una partenza casuale è lontana dalle buone soluzioni, e la ricerca locale spende la maggior parte delle sue mosse nella discesa; una buona euristica costruttiva dà soluzioni di partenza migliori, ma poche e poco diverse fra loro.
-
Una strategia migliore userebbe gli ottimi locali già trovati: ripartire vicino a un buon ottimo locale invece che da un punto qualsiasi, oppure continuare la ricerca da esso accettando alcune mosse peggioranti. Sono le idee delle metaeuristiche.
31.12.2 Che cosa dà la ricerca locale, e che cosa non dà¶
-
La ricerca locale migliora una soluzione ammissibile fino a raggiungere un ottimo locale: un bound primale migliore, spesso molto migliore di quello di partenza.
-
Non dà un bound duale, e il fatto che si sia fermata non significa che sia arrivata. Sull'istanza con \(30\) città sappiamo che \(478\) è ottimo solo perché lo ha dimostrato un solutore MIP; la sola ricerca locale non saprebbe distinguere dall'ottimo l'ottimo locale di lunghezza \(479\), trovato in molte esecuzioni.
Un ottimo locale non è un bound migliore: è una soluzione ammissibile, cioè un lato del gap. La sua qualità si può valutare solo rispetto a un bound duale calcolato in un altro modo.
Avanti: Errori tipici · In sintesi