32.5 Tabu search

Parte 4 · Algoritmi euristici · Capitolo 32 · Capitolo 32: Metaeuristiche · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Metaeuristiche · App: TSP: simulated annealing e tabu search

La tabu search (indicata con \(TS\)) esplora completamente l'intorno della soluzione corrente e si sposta sul miglior vicino, anche se è peggiore della soluzione corrente. Per evitare di tornare alle soluzioni appena visitate, mantiene una memoria a breve termine, la lista tabu: le mosse che annullerebbero le mosse recenti sono vietate (tabu) per un certo numero di iterazioni, la durata tabu (tenure), a meno che non portino a una soluzione migliore della migliore trovata (criterio di aspirazione).

• Lo pseudocodice di \(TS\) per \(P\,||\,C_{\max}\), con l'intorno move e il confronto lessicografico della Sezione 32.2.1, è il seguente; l'attributo \((j,h)\) vieta di riportare il lavoro \(j\) sulla macchina \(h\).

Algoritmo: Tabu search per \(P\,||\,C_{\max}\)

Input: tempi \(t[1..n]\), \(m\) macchine, assegnamento di partenza \(mach[1..n]\), \(tenure\), \(maxIter\)

Output: migliore assegnamento trovato

1Function TabuSearch(\(t, m, mach, tenure, maxIter\))

2\(L :=\) carichi di \(mach\); \(tabu[j][h] := 0\) per ogni \(j\), \(h\)

3\(best := mach\); \(bestC := \max_h L[h]\)

4\(\LB := \max\{\max_j t[j],\ \lceil \sum_j t[j]/m\rceil\}\) \(it := 0\) ▹ arresto se raggiunto

5while \(it < maxIter\) and \(bestC > \LB\) do

6\(it := it+1\); \(bj := 0\) ▹ migliore mossa non tabu \((bj,bh)\)

7for \(j := 1\) to \(n\) do

8for \(h := 1\) to \(m\), \(h\ne mach[j]\) do

9\(L' :=\) i carichi dopo lo spostamento del lavoro \(j\) da \(mach[j]\) a \(h\)

10if \(tabu[j][h]\ge it\) and not \(\max_k L'[k] < bestC\) then continue ▹ tabu

11if \(bj=0\) or \(L'\) è lessicograficamente migliore di \(bL\) then \((bj,bh,bL) := (j,h,L')\)

12end

13end

14if \(bj=0\) then break

15\(tabu[bj][mach[bj]] := it+tenure\) \(mach[bj] := bh\); \(L := bL\) ▹ vietare il ritorno anche se peggiore

16if \(\max_k L[k] < bestC\) then

17\(bestC := \max_k L[k]\); \(best := mach\)

18end

19end

20return \(best\)

Esegui in Colab:PythonC++

• La tabu search è stata proposta da Glover (1986); il libro di riferimento è Glover e Laguna, Tabu Search, Kluwer, 1997. A differenza di \(SA\), è deterministica: esce da un ottimo locale perché si sposta sempre, sul vicino meno cattivo se nessun vicino è migliore.

• Senza memoria, questa regola cicla: da un ottimo locale \(S\) la ricerca passa al miglior vicino \(S'\), che è peggiore, e da \(S'\) il miglior vicino è tipicamente di nuovo \(S\). La lista tabu spezza il ciclo vietando la mossa inversa.

• Attributi. Memorizzare le soluzioni visitate e confrontare con esse ogni vicino sarebbe troppo costoso. La lista tabu memorizza invece attributi delle mosse recenti: qui la coppia \((j,h)\) «il lavoro \(j\) ha lasciato la macchina \(h\)»; per il TSP, i lati appena tolti dal giro.

• Un attributo vieta più della sola soluzione appena lasciata: ogni soluzione con il lavoro \(j\) sulla macchina \(h\) è tabu, anche quelle mai visitate. Il criterio di aspirazione rimedia a questo eccesso di prudenza: una mossa tabu è ammessa se porta a una soluzione migliore della migliore trovata, che certamente non è stata visitata.

• Durata tabu. Se è troppo breve, la ricerca può ancora ciclare su cicli più lunghi; se è troppo lunga, sono vietate troppe mosse e la ricerca viene spinta lontano dalle regioni buone. Valori tipici sono fra \(5\) e \(20\), o proporzionali a \(\sqrt{n}\); estrarre la durata a caso in un intervallo a ogni iterazione (robust tabu search, Taillard 1991) rende improbabili i cicli.

• Criterio di arresto. Un numero massimo di iterazioni, o di iterazioni senza miglioramento della soluzione migliore. Per \(P\,||\,C_{\max}\) possiamo anche fermarci quando il makespan raggiunge il lower bound \(\LB\): allora la soluzione è ottima, e la ricerca può solo perdere tempo.

• Memoria a lungo termine. Oltre alla lista tabu (memoria a breve termine), \(TS\) può registrare quanto spesso ogni attributo compare nelle soluzioni visitate. La diversificazione penalizza gli attributi frequenti, per spingere la ricerca verso regioni inesplorate; l'intensificazione riparte dalle migliori soluzioni trovate, e fissa gli attributi che hanno in comune.

32.5.1 Esempio

Esempio 32.5: \(TS\) sull'istanza di riferimento di \(P\,||\,C_{\max}\)

Partiamo dalla soluzione calcolata da LPT nel capitolo «Euristiche costruttive», \(J_1=\{1,5,7\}\), \(J_2=\{2,6\}\), \(J_3=\{3,4\}\), con carichi \((11,8,8)\), \(C_{\max}=11\) e \(\sum_h L_h^2=249\). È un ottimo locale per l'intorno move: alla prima iterazione i \(14\) vicini sono

mossa	\(1\to M_2\)	\(1\to M_3\)	\(2\to M_1\)	\(2\to M_3\)	\(3\to M_1\)	\(3\to M_2\)	\(4\to M_1\)
\((C_{\max},\sum_hL_h^2)\)	\((13,269)\)	\((13,269)\)	\((16,329)\)	\((13,299)\)	\((15,305)\)	\((12,281)\)	\((15,305)\)
mossa	\(4\to M_2\)	\(5\to M_2\)	\(5\to M_3\)	\(6\to M_1\)	\(6\to M_3\)	\(7\to M_2\)	\(7\to M_3\)
\((C_{\max},\sum_hL_h^2)\)	\((12,281)\)	\((11,249)\)	\((11,249)\)	\((14,285)\)	\((11,267)\)	\((11,249)\)	\((11,249)\)

Nessun vicino ha \(C_{\max}<11\), e i quattro migliori hanno \(C_{\max}=11\) e \(\sum_hL_h^2=249\), come la soluzione corrente: una ricerca locale si ferma qui. \(TS\), con \(tenure=6\), si sposta invece sul miglior vicino non tabu (il primo dei quattro, il lavoro \(5\) su \(M_2\)), e prosegue:

it	mossa	carichi	\(C_{\max}\)	\(\sum_h L_h^2\)	\(bestC\)	nuovo attributo tabu
\(1\)	lavoro \(5\): \(M_1\to M_2\)	\((8,11,8)\)	\(11\)	\(249\)	\(11\)	\((5,M_1)\) fino all'it. \(7\)
\(2\)	lavoro \(5\): \(M_2\to M_3\)	\((8,8,11)\)	\(11\)	\(249\)	\(11\)	\((5,M_2)\) fino all'it. \(8\)
\(3\)	lavoro \(6\): \(M_2\to M_1\)	\((11,5,11)\)	\(11\)	\(267\)	\(11\)	\((6,M_2)\) fino all'it. \(9\)
\(4\)	lavoro \(7\): \(M_1\to M_2\)	\((8,8,11)\)	\(11\)	\(249\)	\(11\)	\((7,M_1)\) fino all'it. \(10\)
\(5\)	lavoro \(3\): \(M_3\to M_1\)	\((12,8,7)\)	\(12\)	\(257\)	\(11\)	\((3,M_3)\) fino all'it. \(11\)
\(6\)	lavoro \(6\): \(M_1\to M_3\)	\((9,8,10)\)	\(10\)	\(245\)	\(10\)	\((6,M_1)\) fino all'it. \(12\)
\(7\)	lavoro \(4\): \(M_3\to M_2\)	\((9,12,6)\)	\(12\)	\(261\)	\(10\)	\((4,M_3)\) fino all'it. \(13\)
\(8\)	lavoro \(7\): \(M_2\to M_3\)	\((9,9,9)\)	\(9\)	\(243\)	\(9\)	\((7,M_2)\) fino all'it. \(14\)

• All'iterazione \(2\) il miglior vicino riporterebbe il lavoro \(5\) su \(M_1\), tornando alla soluzione di partenza: la mossa è tabu (attributo \((5,M_1)\) fino all'iterazione \(7\)), e la ricerca sposta il lavoro \(5\) su \(M_3\).

• All'iterazione \(5\) i quattro vicini con \(C_{\max}=11\) sono tutti tabu, e nessuno soddisfa il criterio di aspirazione (\(C_{\max}<bestC=11\)): la migliore mossa non tabu peggiora il makespan a \(12\). È così che \(TS\) lascia il plateau.

• All'iterazione \(6\) il makespan scende a \(10\), e all'iterazione \(8\) a \(9\): \(C_{\max}=\LB=9\), quindi la soluzione \(J_1=\{1,3\}\), \(J_2=\{2,4\}\), \(J_3=\{5,6,7\}\) è ottima e la ricerca si ferma: \(TS(I)=9=z(I)\).

• La figura mostra i diagrammi di Gantt della soluzione di partenza, della soluzione dopo la mossa peggiorante dell'iterazione \(5\) (il lavoro spostato in arancione), e della soluzione ottima raggiunta all'iterazione \(8\).

• Con \(tenure\le 5\), \(TS\) non raggiunge l'ottimo su questa istanza entro \(50\) iterazioni: la lista tabu è troppo corta per impedire alla ricerca di tornare sul plateau di makespan \(11\).

32.5.2 Tabu search per il TSP, e l'effetto della durata tabu

• Per il TSP con l'intorno 2-opt, gli attributi naturali sono i lati: quando una mossa toglie i lati \((\sigma_i,\sigma_{i+1})\) e \((\sigma_j,\sigma_{j+1})\), questi due lati non possono essere rimessi nel giro per \(tenure\) iterazioni, a meno che la mossa non dia un giro più corto del migliore. Tutto il resto è come nello pseudocodice della Sezione 32.5: a ogni iterazione tutte le \(\frac{n(n-3)}{2}\) mosse sono valutate in \(O(1)\) ciascuna, e si esegue la migliore non tabu.

• Le tabelle riportano il risultato di \(TS\) sulle istanze medie, dal giro nearest neighbour (\(326\)) per TSP20 con \(200\) iterazioni, e dalla soluzione LPT (\(73\)) per PCM15 con \(300\) iterazioni, per diversi valori della durata tabu; per PCM15 la tabella dà anche il numero di iterazioni eseguite (\(300\) salvo che si raggiunga il lower bound).

TSP20: \(TS\) con 2-opt, \(200\) iterazioni (\(z(I)=291\))
\(tenure\)	\(0\)	\(1\)	\(2\)	\(5\)	\(10\)	\(20\)
lunghezza migliore	\(319\)	\(291\)	\(291\)	\(291\)	\(291\)	\(291\)

PCM15: \(TS\) con l'intorno move, al più \(300\) iterazioni (\(z(I)=69\))
\(tenure\)	\(0\)	\(1\)	\(2\)	\(3\)	\(5\)	\(7\)	\(10\)	\(15\)	\(20\)	\(30\)
\(C_{\max}\) migliore	\(73\)	\(73\)	\(73\)	\(73\)	\(73\)	\(72\)	\(71\)	\(69\)	\(70\)	\(70\)
iterazioni	\(300\)	\(300\)	\(300\)	\(300\)	\(300\)	\(300\)	\(300\)	\(231\)	\(300\)	\(300\)

• Con \(tenure=0\) non c'è memoria, e \(TS\) cicla: su TSP20 non lascia mai il primo ottimo locale 2-opt. Su PCM15 l'intorno move ha un ampio plateau, e \(TS\) ha bisogno di una lista tabu lunga per attraversarlo; ma una lista tabu troppo lunga vieta troppo, e con \(tenure\ge 20\) l'ottimo si perde di nuovo. La durata tabu va calibrata, e il suo valore migliore dipende dal problema e dall'istanza.

---

Avanti: 32.6 Iterated local search