Vai al contenuto

31.7 TSP: 2-opt e Or-opt

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

31.7.1 La ricerca locale 2-opt

La ricerca locale 2-opt (indicata con \(2OPT\)) è una ricerca locale per il TSP con l'intorno 2-opt. A ogni iterazione valuta le mosse 2-opt del giro corrente con la formula incrementale, applica una mossa migliorante scelta con la regola first improvement o best improvement, e si ferma quando nessuna mossa accorcia il giro.

Algoritmo: Passo 2-opt

Input: \(n\) città, distanze \(d[1..n][1..n]\), giro \(\sigma[1..n]\) con \(\sigma[1]=1\), regola \(\in\{\textit{first},\textit{best}\}\)
Output: true se a \(\sigma\) è stata applicata una mossa 2-opt migliorante, false altrimenti
1Function TwoOptStep(\(n, d, \sigma, \textit{rule}\))
2\(\bar\Delta := 0\) \((\bar\imath, \bar\jmath) := (0,0)\) ▹ miglior variazione di lunghezza trovata finora miglior mossa trovata finora
3for \(i := 1\) to \(n-2\) do
4for \(j := i+2\) to \(n\) do
5if \(i=1\) and \(j=n\) then continue ▹ i due lati sono adiacenti
6\(u_1 := \sigma[i]\); \(v_1 := \sigma[i+1]\) \(u_2 := \sigma[j]\); \(v_2 := \sigma[j \bmod n+1]\) \(\Delta := d[u_1][u_2]+d[v_1][v_2]-d[u_1][v_1]-d[u_2][v_2]\) ▹ primo lato tolto secondo lato tolto
7if \(\Delta < \bar\Delta\) then
8\(\bar\Delta \leftarrow \Delta\); \((\bar\imath,\bar\jmath) \leftarrow (i,j)\) ▹ mossa migliorante
9if \(\textit{rule}=\textit{first}\) then
10uscire da entrambi i cicli
11end
12end
13end
14end
15if \(\bar\imath = 0\) then return false ▹ nessuna mossa migliorante: ottimo locale
16invertire il cammino \(\sigma[\bar\imath+1], \dots, \sigma[\bar\jmath]\) ▹ applicare la mossa
17return true

Esegui in Colab:PythonC++

  • Nell'implementazione, \(\textit{Improve}\) e lo spostamento sul vicino migliorante sono riuniti in un'unica funzione \(\textit{Step}\), che esplora l'intorno con la valutazione incrementale e, se trova una mossa migliorante, la applica alla soluzione corrente e restituisce true; altrimenti restituisce false. \(LS\) chiama \(\textit{Step}\) finché non restituisce false.

  • \(2OPT\) è \(\textit{LocalSearch}\) con \(\textit{TwoOptStep}\); non cambia mai \(\sigma[1]=1\), perché \(i\ge 1\) e il cammino invertito parte dalla posizione \(i+1\ge 2\).

  • Un'iterazione costa tempo \(O(n^2)\); l'inversione del cammino costa \(O(n)\).

  • Quando le distanze sono euclidee, un ottimo locale 2-opt non ha lati che si incrociano: se i lati \(\{u_1,v_1\}\) e \(\{u_2,v_2\}\) si incrociano in un punto \(X\), la disuguaglianza triangolare dà \(d_{u_1u_2}\le d_{u_1X}+d_{Xu_2}\) e \(d_{v_1v_2}\le d_{v_1X}+d_{Xv_2}\), quindi \(\Delta\le 0\), con \(\Delta<0\) a meno che le quattro città non siano allineate. La mossa 2-opt “scioglie” l'incrocio dei due lati.

Esempio 31.2: \(2OPT\) sull'istanza di riferimento del TSP

Partiamo dal giro di \(NN\) dalla città \(1\), \(\sigma=(1,3,2,4,5)\), di lunghezza \(25\). Le sue \(5\) mosse sono

\((i,j)\) lati tolti lati aggiunti \(\Delta\) nuovo giro, lunghezza
\((1,3)\) \(\{1,3\},\{2,4\}\) \(\{1,2\},\{3,4\}\) \(5+4-2-3=+4\) \((1,2,3,4,5)\), \(29\)
\((1,4)\) \(\{1,3\},\{4,5\}\) \(\{1,4\},\{3,5\}\) \(2+7-2-7=0\) \((1,4,2,3,5)\), \(25\)
\((2,4)\) \(\{3,2\},\{4,5\}\) \(\{3,4\},\{2,5\}\) \(4+4-4-7=-3\) \((1,3,4,2,5)\), \(22\)
\((2,5)\) \(\{3,2\},\{5,1\}\) \(\{3,5\},\{2,1\}\) \(7+5-4-9=-1\) \((1,3,5,4,2)\), \(24\)
\((3,5)\) \(\{2,4\},\{5,1\}\) \(\{2,5\},\{4,1\}\) \(4+2-3-9=-6\) \((1,3,2,5,4)\), \(19\)

First improvement accetta la mossa \((2,4)\), la prima con \(\Delta<0\), dopo \(3\) valutazioni: \(\sigma=(1,3,4,2,5)\), di lunghezza \(22\). Le sue mosse hanno \(\Delta=+1,+6,+3,-4,0\); la mossa \((2,5)\), che toglie \(\{3,4\}\) e \(\{5,1\}\) e aggiunge \(\{3,5\}\) e \(\{4,1\}\), è accettata dopo \(4\) valutazioni: \(\sigma=(1,3,5,2,4)\), di lunghezza \(18\). Tutte le sue \(5\) mosse hanno \(\Delta>0\) (\(+7,+4,+1,+4,+6\)): la ricerca si ferma dopo \(3+4+5=12\) valutazioni.

Best improvement accetta la mossa \((3,5)\), con \(\Delta=-6\): \(\sigma=(1,3,2,5,4)\), di lunghezza \(19\). Le sue mosse hanno \(\Delta=+6,+4,-1,+3,+6\), e la mossa \((2,4)\), che toglie \(\{3,2\}\) e \(\{5,4\}\) e aggiunge \(\{3,5\}\) e \(\{2,4\}\), dà \(\sigma=(1,3,5,2,4)\), di lunghezza \(18\). La ricerca si ferma dopo \(5+5+5=15\) valutazioni.

Entrambe le regole raggiungono il giro ottimo, con \(2\) mosse ciascuna. La figura mostra i due percorsi; le città sono disposte nell'ordine del giro ottimo, quindi il giro ottimo è il bordo del pentagono (l'istanza non è euclidea: il disegno è solo uno schema). I lati rossi tratteggiati sono tolti, quelli blu sono aggiunti.

Figura 3

31.7.2 La ricerca locale Or-opt

La ricerca locale Or-opt (indicata con \(OROPT\)) è una ricerca locale per il TSP con l'intorno Or-opt. A ogni iterazione valuta, con la formula incrementale, l'inserimento di ogni segmento di \(1\), \(2\) o \(3\) città consecutive fra altre due città consecutive, applica una mossa migliorante scelta con la regola first improvement o best improvement, e si ferma quando nessuna mossa accorcia il giro.

Algoritmo: Passo Or-opt

Input: \(n\) città, distanze \(d[1..n][1..n]\), giro \(\sigma[1..n]\) con \(\sigma[1]=1\), regola \(\in\{\textit{first},\textit{best}\}\)
Output: true se a \(\sigma\) è stata applicata una mossa Or-opt migliorante, false altrimenti
1Function OrOptStep(\(n, d, \sigma, \textit{rule}\))
2\(\bar\Delta := 0\); \((\bar\ell,\bar\imath,\bar k) := (0,0,0)\) ▹ miglior mossa trovata finora
3for \(\ell := 1\) to \(3\) do
4for \(i := 2\) to \(n-\ell+1\) do
5\(p := \sigma[i-1]\); \(s_1 := \sigma[i]\) \(s_\ell := \sigma[i+\ell-1]\); \(q := \sigma[(i+\ell-1) \bmod n+1]\) ▹ predecessore, prima città del segmento ultima città, successore
6for \(k := 1\) to \(n\) do
7if \(i-1 \le k \le i+\ell-1\) then continue ▹ stesso posto, o dentro il segmento
8\(a := \sigma[k]\); \(b := \sigma[k \bmod n+1]\) \(\Delta := d[p][q]+d[a][s_1]+d[s_\ell][b]-d[p][s_1]-d[s_\ell][q]-d[a][b]\) ▹ lato in cui va il segmento
9if \(\Delta < \bar\Delta\) then
10\(\bar\Delta \leftarrow \Delta\); \((\bar\ell,\bar\imath,\bar k) \leftarrow (\ell,i,k)\) ▹ mossa migliorante
11if \(\textit{rule}=\textit{first}\) then
12uscire dai tre cicli
13end
14end
15end
16end
17end
18if \(\bar\ell = 0\) then return false ▹ nessuna mossa migliorante: ottimo locale
19spostare \(\sigma[\bar\imath],\dots,\sigma[\bar\imath+\bar\ell-1]\) fra \(\sigma[\bar k]\) e \(\sigma[\bar k \bmod n+1]\) ▹ applicare
20return true

Esegui in Colab:PythonC++

  • Or-opt sposta un breve tratto del giro in un posto migliore, senza invertire nulla: è l'intorno naturale quando alcune città sono state “lasciate indietro” dalla costruzione. Un'iterazione costa tempo \(O(n^2)\).

  • Un ottimo locale 2-opt non è necessariamente un ottimo locale Or-opt, e viceversa: i due intorni contengono mosse diverse.

31.7.3 First e best improvement su un'istanza media

  • Con \(5\) città l'intorno 2-opt è piccolo ed entrambe le regole raggiungono l'ottimo. Per vedere la differenza fra le due regole, e il ruolo di Or-opt, usiamo un'istanza media con \(10\) città. Questa istanza non è metrica: \(d_{68}=8>d_{67}+d_{78}=4+3\) e \(d_{6,10}=11>d_{67}+d_{7,10}=4+6\).

Esempio 31.3: Un'istanza del TSP con \(10\) città

Le città hanno coordinate intere, e \(d_{ij}\) è la distanza euclidea arrotondata all'intero più vicino:

città \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\)
coordinate \((1,1)\) \((3,8)\) \((6,10)\) \((10,9)\) \((13,6)\) \((12,1)\) \((8,3)\) \((5,4)\) \((8,7)\) \((2,5)\)

\[ \begin{array}{c|cccccccccc} \hline {d_{ij}} & {1} & {2} & {3} & {4} & {5} & {6} & {7} & {8} & {9} & {10} \\ \hline {1} & --- & {7} & {10} & {12} & {13} & {11} & {7} & {5} & {9} & {4} \\ {2} & {7} & --- & {4} & {7} & {10} & {11} & {7} & {4} & {5} & {3} \\ {3} & {10} & {4} & --- & {4} & {8} & {11} & {7} & {6} & {4} & {6} \\ {4} & {12} & {7} & {4} & --- & {4} & {8} & {6} & {7} & {3} & {9} \\ {5} & {13} & {10} & {8} & {4} & --- & {5} & {6} & {8} & {5} & {11} \\ {6} & {11} & {11} & {11} & {8} & {5} & --- & {4} & {8} & {7} & {11} \\ {7} & {7} & {7} & {7} & {6} & {6} & {4} & --- & {3} & {4} & {6} \\ {8} & {5} & {4} & {6} & {7} & {8} & {8} & {3} & --- & {4} & {3} \\ {9} & {9} & {5} & {4} & {3} & {5} & {7} & {4} & {4} & --- & {6} \\ {10} & {4} & {3} & {6} & {9} & {11} & {11} & {6} & {3} & {6} & --- \\ \hline \end{array} \]

Fra i suoi \(181\,440\) giri distinti, l'unico ottimo è \((1,10,2,3,9,4,5,6,7,8)\), di lunghezza \(z(I)=39\). Il giro di \(NN\) dalla città \(1\) è \((1,10,2,3,4,9,7,8,5,6)\), di lunghezza \(49\), e l'intorno 2-opt ha \(\frac{10\cdot 7}{2}=35\) mosse.

First improvement esegue \(4\) mosse:

lati tolti nuovo giro \(\Delta\) lunghezza valutazioni
\(\{3,4\},\{8,5\}\) \((1,10,2,3,8,7,9,4,5,6)\) \(-2\) \(47\) \(23\)
\(\{3,8\},\{6,1\}\) \((1,10,2,3,6,5,4,9,7,8)\) \(-1\) \(46\) \(25\)
\(\{3,6\},\{4,9\}\) \((1,10,2,3,4,5,6,9,7,8)\) \(-3\) \(43\) \(22\)
\(\{6,9\},\{7,8\}\) \((1,10,2,3,4,5,6,7,9,8)\) \(-2\) \(41\) \(33\)

e si ferma nell'ottimo locale \((1,10,2,3,4,5,6,7,9,8)\), di lunghezza \(41\), dopo \(138\) valutazioni in totale (le ultime \(35\) per certificare l'ottimo locale).

Best improvement esegue \(3\) mosse:

lati tolti nuovo giro \(\Delta\) lunghezza
\(\{7,8\},\{6,1\}\) \((1,10,2,3,4,9,7,6,5,8)\) \(-5\) \(44\)
\(\{9,7\},\{5,8\}\) \((1,10,2,3,4,9,5,6,7,8)\) \(-4\) \(40\)
\(\{3,4\},\{9,5\}\) \((1,10,2,3,9,4,5,6,7,8)\) \(-1\) \(39\)

e si ferma nel giro ottimo dopo \(4\cdot 35=140\) valutazioni.

Dallo stesso giro di partenza, le due regole si fermano in ottimi locali diversi, dopo quasi lo stesso numero di valutazioni. Fra tutti i \(181\,440\) giri, solo \(3\) sono ottimi locali 2-opt, di lunghezza \(39\), \(41\) e \(43\).

Figura 4

Esempio 31.4: \(OROPT\) da un ottimo locale 2-opt

Sull'istanza dell'Esempio 31.3, first improvement si è fermato nell'ottimo locale 2-opt \(\sigma=(1,10,2,3,4,5,6,7,9,8)\), di lunghezza \(41\). La mossa Or-opt che prende il segmento \((9)\), con \(\ell=1\), fra \(p=7\) e \(q=8\), e lo inserisce fra \(a=3\) e \(b=4\) ha

\[ \Delta = d_{78}+d_{39}+d_{94}-d_{79}-d_{98}-d_{34} = 3+4+3-4-4-4 = -2 . \]

È la prima mossa migliorante trovata, dopo \(60\) valutazioni, e anche la migliore delle \(170\) mosse. Il nuovo giro \((1,10,2,3,9,4,5,6,7,8)\), di lunghezza \(39\), è ottimo. Fra tutti i \(181\,440\) giri, solo \(3\) sono ottimi locali Or-opt, di lunghezza \(39\), \(43\) e \(44\), e solo il giro ottimo è un ottimo locale sia per 2-opt sia per Or-opt.

31.7.4 3-opt e Lin–Kernighan

  • L'intorno 3-opt toglie tre lati e ricollega i tre cammini in tutti i modi possibili (Lin, 1965). I suoi ottimi locali sono migliori di quelli di 2-opt, ma un'iterazione costa tempo \(O(n^3)\), e in pratica l'intorno si esplora solo in parte.

  • L'euristica di Lin–Kernighan (Lin, Kernighan, Operations Research 21, 1973) costruisce un numero variabile \(k\) di scambi di lati, uno alla volta, scegliendo ogni scambio in modo greedy e fermandosi quando il guadagno totale non può più diventare positivo. Esplora parte dell'intorno \(k\)-opt per ogni \(k\), in un tempo vicino a quello di 2-opt, e le sue implementazioni sono fra le migliori euristiche per il TSP.

  • La sequenza 2-opt, 3-opt, \(k\)-opt mostra il compromesso del capitolo «Algoritmi euristici: definizioni»: un intorno più grande ha ottimi locali migliori, e costa di più da esplorare.

Avanti: 31.8 \(P\,||\,C_{\max}\): move e swap