31.11 Variable neighbourhood descent¶
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
- Gli esempi delle sezioni precedenti mostrano che un ottimo locale per un intorno spesso non è un ottimo locale per un altro: la soluzione di \(LPT\) per move e swap, l'ottimo locale 2-opt di lunghezza \(41\) per 2-opt e Or-opt. L'idea naturale è usare più intorni \(N_1,\dots,N_K\), e fermarsi solo quando nessuno di essi contiene un vicino migliorante.
La variable neighbourhood descent (indicata con \(VND\)) esplora gli intorni \(N_1,\dots,N_K\) in quest'ordine. Cerca una mossa migliorante nell'intorno corrente \(N_k\): se ne trova una, la applica e torna a \(N_1\); altrimenti passa a \(N_{k+1}\). Si ferma quando la soluzione corrente è un ottimo locale per tutti i \(K\) intorni.
Algoritmo: Variable neighbourhood descent
-
\(VND\) si ferma dopo un numero finito di mosse, per l'argomento della Proposizione 31.2. Quando si ferma, \(\textit{Step}_K\) è fallito e, dall'ultima mossa migliorante, sono falliti sulla stessa soluzione tutti i passi \(\textit{Step}_1,\dots,\textit{Step}_{K-1}\): la soluzione restituita è un ottimo locale per ogni \(N_k\), cioè per l'unione \(N_1\cup\dots\cup N_K\).
-
Gli intorni sono ordinati dal più piccolo e meno costoso al più grande: gli intorni costosi si esplorano solo quando quelli economici sono esauriti. \(VND\) è la parte deterministica della variable neighbourhood search di Mladenovic e Hansen (Computers & Operations Research 24, 1997).
Esempio 31.9: \(VND\) su \(P\,||\,C_{\max}\) con move e swap
Sull'istanza di riferimento, dalla soluzione di \(LPT\), con \(N_1=\) move e \(N_2=\) swap, e il makespan come obiettivo:
| \(k\) | risultato di \(\textit{Step}_k\) | carichi | poi |
|---|---|---|---|
| \(1\) | nessuna mossa migliorante | \((11,8,8)\) | \(k=2\) |
| \(2\) | swap dei lavori \(1\) e \(3\) | \((10,8,9)\) | \(k=1\) |
| \(1\) | nessuna mossa migliorante | \((10,8,9)\) | \(k=2\) |
| \(2\) | swap dei lavori \(3\) e \(6\) | \((9,9,9)\) | \(k=1\) |
| \(1\) | nessuna mossa migliorante | \((9,9,9)\) | \(k=2\) |
| \(2\) | nessuno swap migliorante | \((9,9,9)\) | stop |
Nella soluzione con carichi \((10,8,9)\) la mossa migliore dà makespan \(11\) (lavoro \(5\) o lavoro \(7\) dalla macchina \(1\) alla macchina \(2\)), quindi move è di nuovo esaurito, e swap trova l'ottimo.
Esempio 31.10: \(VND\) sul TSP con 2-opt e Or-opt
Sull'istanza con \(10\) città dell'Esempio 31.3, dal giro di \(NN\) (lunghezza \(49\)), con \(N_1=\) 2-opt, \(N_2=\) Or-opt e la regola first improvement, \(VND\) esegue le quattro mosse 2-opt della ricerca locale 2-opt (\(49\to47\to46\to43\to41\)), poi la mossa Or-opt dell'Esempio 31.4, che inserisce la città \(9\) fra le città \(3\) e \(4\) (\(41\to39\)), e si ferma: il giro ottimo è un ottimo locale per entrambi gli intorni. Con la regola best improvement, il solo 2-opt raggiunge già l'ottimo.
- Sulle due istanze medie della Sezione 31.9, con \(100\) soluzioni di partenza casuali (seme \(1\)) e best improvement, \(VND\) con \(N_1=\) move e \(N_2=\) swap dà:
| istanza | obiettivo | esecuzioni che terminano in un ottimo | valore medio |
|---|---|---|---|
| \(P\,||\,C_{\max}\), \(m=4\), \(n=12\) | \(C_{\max}\) | \(15\) | \(20.62\) |
| \(P\,||\,C_{\max}\), \(m=4\), \(n=12\) | \(\sum_h L_h^2\) | \(68\) | \(19.32\) |
| BPP, \(c=10\), \(n=12\) | \(\sum_b L_b^2\) | \(89\) | \(5.11\) |
- Rispetto ai singoli intorni della Sezione 31.9, \(VND\) con l'obiettivo ausiliario raggiunge l'ottimo in \(68\) esecuzioni su \(100\) per \(P\,||\,C_{\max}\) (solo move: \(4\)) e in \(89\) per il BPP (solo move: \(76\)). Combinare gli intorni e usare l'obiettivo ausiliario sono miglioramenti indipendenti, e si sommano.
Avanti: 31.12 Ricerca locale multi-start