Vai al contenuto

31.6 Valutare una mossa in modo incrementale

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

  • Ogni iterazione di \(LS\) valuta molti vicini, e la maggior parte del tempo di esecuzione si spende lì. Calcolare \(f(y)\) da zero costa \(O(n)\) per ciascuno dei quattro problemi: il profitto di una soluzione del KP, i carichi dei contenitori o delle macchine, la lunghezza di un giro sono somme di \(n\) termini.

  • Una mossa cambia solo poche componenti della soluzione. La valutazione incrementale calcola la variazione \(\Delta=f(y)-f(x)\) dalle componenti che cambiano, conservando alcune informazioni sulla soluzione corrente (il suo profitto e il suo peso, i suoi carichi), senza ricalcolare \(f(y)\).

Proposizione 31.3

Sia \(\sigma'\) il giro ottenuto da \(\sigma\) con la mossa 2-opt di posizioni \(i<j\), e siano \(u_1=\sigma_i\), \(v_1=\sigma_{i+1}\), \(u_2=\sigma_j\), \(v_2=\sigma_{j+1}\). Allora \(L(\sigma')=L(\sigma)+\Delta\), con

\[ \Delta \;=\; d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}. \]
Dimostrazione

I giri \(\sigma\) e \(\sigma'\) hanno gli stessi lati, tranne che \(\sigma\) contiene \(\{u_1,v_1\}\) e \(\{u_2,v_2\}\) mentre \(\sigma'\) contiene \(\{u_1,u_2\}\) e \(\{v_1,v_2\}\). Il cammino invertito \(v_1,\dots,u_2\) usa gli stessi lati nel verso opposto, e la sua lunghezza non cambia perché le distanze sono simmetriche. □

La variazione di lunghezza di una mossa 2-opt si calcola in tempo \(O(1)\):

\[ \Delta \;=\; \underbrace{d_{u_1u_2}+d_{v_1v_2}}_{\text{lati aggiunti}}\;-\;\underbrace{d_{u_1v_1}+d_{u_2v_2}}_{\text{lati tolti}} \]

e la mossa è migliorante se e solo se \(\Delta<0\).

  • Per esempio, sul giro \((1,3,2,4,5)\) dell'istanza di riferimento, di lunghezza \(25\), la mossa con posizioni \(i=2\), \(j=4\) toglie \(\{3,2\}\) e \(\{4,5\}\) e aggiunge \(\{3,4\}\) e \(\{2,5\}\): \(\Delta=d_{34}+d_{25}-d_{32}-d_{45}=4+4-4-7=-3\). Il nuovo giro \((1,3,4,2,5)\) ha lunghezza \(25-3=22\), come conferma il calcolo diretto: \(2+4+3+4+9=22\).

  • Perché conta. L'intorno 2-opt ha \(\frac{n(n-3)}{2}\) mosse. Con la valutazione incrementale un'iterazione di best improvement costa \(O(n^2)\); ricalcolare ogni giro da zero costerebbe \(O(n^3)\). Per \(n=1000\) città, un'iterazione valuta \(498\,500\) mosse: circa \(5\cdot 10^5\) operazioni invece di circa \(5\cdot 10^8\). L'inversione del cammino, che costa \(O(n)\), si esegue una sola volta per iterazione, per la mossa accettata.

  • La stessa idea si applica agli altri intorni:

mossa variazione della soluzione tempo
KP, flip di \(j\) profitto \(\pm p_j\), peso \(\pm w_j\) \(O(1)\)
KP, swap \(j\) fuori, \(k\) dentro profitto \(+p_k-p_j\), peso \(+w_k-w_j\) \(O(1)\)
BPP, move di \(j\) da \(a\) a \(b\) \(L_a-w_j\), \(L_b+w_j\); il contenitore \(a\) si svuota sse \(L_a=w_j\) \(O(1)\)
TSP, 2-opt \(d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}\) \(O(1)\)
TSP, Or-opt \(d_{pq}+d_{as_1}+d_{s_\ell b}-d_{ps_1}-d_{s_\ell q}-d_{ab}\) \(O(1)\)
\(P\,||\,C_{\max}\), move di \(j\) da \(a\) a \(h\) \(L_a-t_j\), \(L_h+t_j\); \(C_{\max}=\max\{L_a-t_j,\,L_h+t_j,\,\max_{q\ne a,h}L_q\}\) \(O(m)\)

  • La formula di Or-opt si ottiene come per 2-opt: la mossa toglie i lati \(\{p,s_1\}\), \(\{s_\ell,q\}\), \(\{a,b\}\) e aggiunge \(\{p,q\}\), \(\{a,s_1\}\), \(\{s_\ell,b\}\), e il segmento mantiene il suo orientamento.

  • Il costo di un'iterazione di \(LS\) è la dimensione dell'intorno per il costo della valutazione di una mossa (più il costo di applicare la mossa accettata, che si paga una volta per iterazione):

problema intorno valutazione di una mossa costo di un'iterazione
KP flip \(O(1)\) \(O(n)\)
KP swap \(O(1)\) \(O(n^2)\)
BPP move \(O(1)\) \(O(n\cdot nb)\)
BPP swap \(O(1)\) \(O(n^2)\)
TSP 2-opt, Or-opt \(O(1)\) \(O(n^2)\)
TSP 3-opt \(O(1)\) \(O(n^3)\)
\(P\,||\,C_{\max}\) move \(O(m)\) \(O(nm^2)\)
\(P\,||\,C_{\max}\) swap \(O(m)\) \(O(n^2m)\)
  • La valutazione incrementale non cambia gli ottimi locali, né il percorso seguito dalla ricerca: cambia solo il tempo necessario a seguirlo. Per questo il progetto di una ricerca locale parte sempre da due domande: quali mosse? e quanto velocemente si può valutare una mossa?

Avanti: 31.7 TSP: 2-opt e Or-opt