31.2 I problemi, le ipotesi e le soluzioni di partenza¶
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 algoritmi sono illustrati sui quattro problemi del capitolo «Algoritmi euristici: definizioni»: il problema dello zaino 0/1 (KP), il problema del bin packing (BPP), il problema del commesso viaggiatore (TSP) e \(P\,||\,C_{\max}\). Le loro definizioni e ipotesi sono nelle rispettive pagine; la tabella richiama la notazione.
| problema | dati | soluzione | obiettivo |
|---|---|---|---|
| KP | \(p_j\), \(w_j\) (\(j\in\mathscr{I}\)), capacità \(c\) | vettore binario \(x\) | max profitto |
| BPP | \(w_j\) (\(j\in\mathscr{I}\)), capacità \(c\) | vettore \(bin\), schemi \(P_b\) | min numero di contenitori \(nb\) |
| TSP | \(d_{ij}\) (\(i,j\in\mathscr{V}\)) | giro \(\sigma\) | min lunghezza \(L(\sigma)\) |
| \(P\,||\,C_{\max}\) | \(t_j\) (\(j\in\mathscr{J}\)), \(m\) macchine | vettore \(mach\), insiemi \(J_h\) | min makespan \(C_{\max}\) |
-
Per \(P\,||\,C_{\max}\), \(L_h=\sum_{j\in J_h} t_j\) è il carico della macchina \(h\) e \(C_{\max}=\max_h L_h\). Per il BPP, \(L_b=\sum_{j\in P_b} w_j\) è il carico del contenitore \(b\). Una macchina (o un contenitore) il cui carico è uguale al valore obiettivo si dice critica (o critico).
-
Le istanze di riferimento sono quelle del capitolo «Algoritmi euristici: definizioni»: il KP con \(p=(10,7,6,4)\), \(w=(5,4,3,3)\), \(c=9\); il BPP con \(w=(4,4,5,3,2,3)\), \(c=7\); il TSP con \(5\) città; \(P\,||\,C_{\max}\) con \(t=(5,5,4,4,3,3,3)\) e \(m=3\). I loro valori ottimi sono \(17\), \(3\), \(18\) e \(9\).
31.2.1 Soluzioni di partenza¶
- Una ricerca locale ha bisogno di una soluzione di partenza ammissibile. Usiamo le soluzioni calcolate nel capitolo «Euristiche costruttive», richiamate qui sotto.
| problema | algoritmo | soluzione di partenza | valore | \(z(I)\) |
|---|---|---|---|---|
| KP | \(GR\) (greedy per efficienza) | \(x=(1,0,1,0)\), oggetti \(\{1,3\}\) | \(16\) | \(17\) |
| KP | greedy per peso \(GR_w\) | \(x=(0,0,1,1)\), oggetti \(\{3,4\}\) | \(10\) | \(17\) |
| BPP | \(NF\) | \(\{1\},\{2\},\{3\},\{4,5\},\{6\}\) | \(5\) | \(3\) |
| BPP | \(FF\) | \(\{1,4\},\{2,5\},\{3\},\{6\}\) | \(4\) | \(3\) |
| BPP | \(FFD\) | \(\{3,5\},\{1,4\},\{2,6\}\) | \(3\) | \(3\) |
| TSP | \(NN\) dalla città \(1\) | \(\sigma=(1,3,2,4,5)\) | \(25\) | \(18\) |
| \(P\,||\,C_{\max}\) | \(LPT\) | \(J_1=\{1,5,7\}\), \(J_2=\{2,6\}\), \(J_3=\{3,4\}\) | \(11\) | \(9\) |
-
La soluzione di \(FFD\) è già ottima, quindi nessuna ricerca locale può migliorarla: per il BPP partiamo dalle soluzioni di \(NF\) e \(FF\).
-
Per studiare il comportamento di una ricerca locale su molte soluzioni di partenza usiamo anche soluzioni di partenza casuali. Sono generate con il generatore minimal standard di Park–Miller: dato un seme intero \(s_0\in\{1,\dots,2^{31}-2\}\), il \(k\)-esimo numero pseudo-casuale è
e un intero pseudo-casuale in \(\{0,1,\dots,q-1\}\) è \(\lfloor q\, u_k\rfloor\).
- La sequenza è interamente determinata dal seme: lo stesso seme dà le stesse soluzioni di partenza, nelle note, negli esercizi e nel codice. Un giro casuale tiene la città \(1\) in prima posizione e rimescola le altre città (Fisher–Yates: per \(k=n,n-1,\dots,3\), la città in posizione \(k\) si scambia con la città in una posizione casuale fra \(2,\dots,k\)); un'assegnazione casuale dei lavori estrae la macchina dei lavori \(1,2,\dots,n\) in quest'ordine; una soluzione casuale del BPP si calcola con \(FF\) su un ordine casuale degli oggetti (Fisher–Yates su tutte le posizioni: per \(k=n,n-1,\dots,2\), l'oggetto in posizione \(k\) si scambia con l'oggetto in una posizione casuale fra \(1,\dots,k\)).
Avanti: Ricerca locale: lo schema · Intorni per i quattro problemi