30.9 Costruzione randomizzata¶

Parte 4 · Algoritmi euristici · Capitolo 30 · Capitolo 30: Euristiche costruttive · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Euristiche costruttive · App: Euristiche per il bin packing · App: List scheduling e LPT · App: Colorazione: greedy e DSATUR · App: TSP: nearest neighbour e 2-opt

Un'euristica greedy è deterministica: eseguita due volte sulla stessa istanza, restituisce la stessa soluzione. Il \(NN\) multi-start ottiene soluzioni diverse cambiando la città di partenza, ma il numero di partenze è limitato a \(n\). Un modo più flessibile per ottenere molte soluzioni diverse, e comunque buone, è randomizzare la scelta: a ogni passo, invece del candidato migliore, si sceglie a caso uno dei candidati buoni.
I candidati buoni formano la lista ristretta dei candidati (restricted candidate list, RCL). Per un criterio di minimo con valori \(g(q)\) dei candidati \(q\), siano \(g^{\min}\) e \(g^{\max}\) il valore minimo e il valore massimo; la RCL basata sul valore con parametro \(\alpha\in[0,1]\) è

\[ RCL \;=\; \Big\{\, q \;:\; g(q) \;\le\; g^{\min} + \alpha\,\big(g^{\max}-g^{\min}\big) \Big\} . \]

Con \(\alpha=0\) la RCL contiene solo i candidati migliori, e la costruzione è greedy (con pareggi risolti a caso); con \(\alpha=1\) contiene tutti i candidati, e la costruzione è puramente casuale.

Un'alternativa è la RCL basata sulla cardinalità, formata dai \(k\) candidati migliori per un \(k\) fissato. La costruzione randomizzata è il primo ingrediente della metaeuristica GRASP (T.A. Feo, M.G.C. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimization 6 (1995) 109–133).
Numeri casuali. Per rendere riproducibili esempi ed esercizi, le note sugli algoritmi euristici usano il generatore minimal standard di Park e Miller, che produce una successione di numeri \(u_1,u_2,\dots\) in \((0,1)\) a partire da un seme intero:

\[ seed \;\leftarrow\; (16807\cdot seed) \bmod 2147483647, \qquad\qquad u \;=\; \frac{seed}{2147483647} . \]

Il modulo è \(2^{31}-1\), un numero primo; con interi a \(64\) bit il prodotto non va mai in overflow. Lo stesso seme dà la stessa successione su ogni computer e in ogni linguaggio di programmazione. Un candidato si estrae da una RCL con \(|RCL|\) elementi, elencati per indice crescente, prendendo l'elemento in posizione \(\lfloor u\cdot|RCL|\rfloor+1\); si usa un numero casuale solo quando \(|RCL|\ge 2\).

L'algoritmo nearest neighbour randomizzato (indicato con \(RNN_\alpha\)) è un'euristica costruttiva per il TSP. Partendo dalla città \(s\), a ogni passo costruisce la RCL delle città non visitate la cui distanza dall'ultima città è al più \(d^{\min}+\alpha\,(d^{\max}-d^{\min})\), e accoda una città estratta in modo uniforme a caso dalla RCL.

Algoritmo: Nearest Neighbour randomizzato

Input: istanza del TSP con \(n\) città, distanze \(d[1..n][1..n]\); città di partenza \(s\); \(\alpha\in[0,1]\); \(seed\)

Output: giro \(\sigma[1..n]\)

1Function RandomizedNN(\(n, d, s, \alpha, seed\))

2\(\sigma[1] \leftarrow s\), \(visited := \{s\}\)

3for \(len := 2\) to \(n\) do

4\(last := \sigma[len-1]\)

5\(d^{\min} := \min_{j\notin visited} d[last][j]\), \(d^{\max} := \max_{j\notin visited} d[last][j]\)

6\(RCL := \{\, j\notin visited : d[last][j] \le d^{\min}+\alpha\,(d^{\max}-d^{\min})\,\}\) ▹ per indice

7if \(|RCL| \ge 2\) then

8\(u :=\) ParkMiller(\(seed\)) \(k :=\) l'elemento in posizione \(\lfloor u\cdot|RCL|\rfloor+1\) di \(RCL\) ▹ numero casuale in \((0,1)\)

9else

10\(k :=\) l'unico elemento di \(RCL\)

11end

12\(\sigma[len] \leftarrow k\), \(visited \leftarrow visited\cup\{k\}\)

13end

14return \(\sigma\)

Esegui in Colab:Python C++

Ripetendo la costruzione con lo stesso generatore — il seme non si reinizializza fra due esecuzioni — si ottengono giri diversi; si tiene il migliore. Il parametro \(\alpha\) bilancia qualità e varietà: un \(\alpha\) piccolo dà giri vicini al giro di \(NN\), un \(\alpha\) grande dà giri molto diversi ma di solito scadenti.

Esempio 30.15: \(RNN_{0.3}\) sull'istanza di riferimento del TSP

Eseguiamo \(RNN_\alpha\) quattro volte dalla città \(1\), con \(\alpha=0.3\) e seme iniziale \(1\). Il generatore dà

\[ \begin{array}{ccccccccc} \hline {u_1} & {u_2} & {u_3} & {u_4} & {u_5} & {u_6} & {u_7} & {u_8} & {u_9} \\ \hline {0.0000} & {0.1315} & {0.7556} & {0.4587} & {0.5328} & {0.2190} & {0.0470} & {0.6789} & {0.6793} \\ \hline \end{array} \]

(\(u_1=\frac{16807}{2147483647}\approx 0.0000078\)). Dalla città \(1\) le distanze verso \(2,3,4,5\) sono \(5,2,2,9\), quindi la soglia è \(2+0.3\cdot(9-2)=4.1\) e \(RCL=\{3,4\}\).

Esecuzione 1. \(u_1\): posizione \(\lfloor 0.0000\cdot 2\rfloor+1=1\), città \(3\). Da \(3\) le distanze verso \(2,4,5\) sono \(4,4,7\), soglia \(4+0.3\cdot 3=4.9\), \(RCL=\{2,4\}\); \(u_2\): posizione \(1\), città \(2\). Da \(2\) le distanze verso \(4,5\) sono \(3,4\), soglia \(3.3\), \(RCL=\{4\}\): città \(4\), poi città \(5\). Giro \((1,3,2,4,5)\), \(L=25\): il giro di \(NN\).

Esecuzione 2. \(u_3\): posizione \(\lfloor 0.7556\cdot 2\rfloor+1=2\), città \(4\). Da \(4\) le distanze verso \(2,3,5\) sono \(3,4,7\), soglia \(3+0.3\cdot 4=4.2\), \(RCL=\{2,3\}\); \(u_4\): posizione \(1\), città \(2\). Da \(2\) le distanze verso \(3,5\) sono \(4,4\): \(d^{\min}=d^{\max}=4\) e \(RCL=\{3,5\}\); \(u_5\): posizione \(\lfloor 0.5328\cdot 2\rfloor+1=2\), città \(5\); poi città \(3\). Giro \((1,4,2,5,3)\), \(L=18=z(I)\).

Esecuzione 3. \(u_6\): città \(3\); \(u_7\): città \(2\); poi le città \(4\) e \(5\). Giro \((1,3,2,4,5)\), \(L=25\).

Esecuzione 4. \(u_8\): città \(4\); \(RCL=\{2,3\}\) e \(u_9\): posizione \(2\), città \(3\). Da \(3\) le distanze verso \(2,5\) sono \(4,7\), soglia \(4.9\), \(RCL=\{2\}\): città \(2\), poi città \(5\). Giro \((1,4,3,2,5)\), \(L=2+4+4+4+9=23\).

Le quattro esecuzioni danno \(25,18,25,23\): la seconda trova il giro ottimo, che \(NN\) dalla città \(1\) non trova. La randomizzazione ha trasformato un'unica risposta deterministica in una piccola ricerca.

Avanti: 30.10 Look-ahead e regret