32.11 Confronto e conclusioni¶

32.11.1 I metodi sulle istanze medie¶

La tabella raccoglie i risultati degli esperimenti delle sezioni precedenti: per ogni metodo, il miglior valore trovato in \(10\) esecuzioni (\(seed=1,\dots,10\)), come minimo, media e massimo, e il numero di esecuzioni che raggiungono l'ottimo. I metodi deterministici danno lo stesso valore in ogni esecuzione.

istanza	metodo	parametri	min	media	max	ottime
TSP20	NN	—	\(326\)	\(326\)	\(326\)	\(0\)
	NN + 2-opt	—	\(319\)	\(319\)	\(319\)	\(0\)
	\(SA\)	\(T_0=20\), \(\alpha=0.95\)	\(291\)	\(294.3\)	\(298\)	\(5\)
	\(SA\)	\(T_0=20\), \(\alpha=0.99\)	\(291\)	\(291.0\)	\(291\)	\(10\)
	\(TS\)	\(tenure=5\), \(200\) it.	\(291\)	\(291\)	\(291\)	\(10\)
	\(ILS\)	\(100\) it.	\(291\)	\(291.0\)	\(291\)	\(10\)
	\(GRASP\)	\(\alpha=0.25\), \(20\) it.	\(291\)	\(291.0\)	\(291\)	\(10\)
	\(LNS\)	\(q=5\), \(200\) it.	\(291\)	\(293.8\)	\(319\)	\(9\)
	ALNS	\(q=5\), \(200\) it.	\(291\)	\(299.4\)	\(319\)	\(7\)
KP20	greedy	—	\(490\)	\(490\)	\(490\)	\(0\)
	greedy + ricerca locale	—	\(514\)	\(514\)	\(514\)	\(0\)
	\(GRASP\)	\(\alpha=0.25\), \(20\) it.	\(521\)	\(521.0\)	\(521\)	\(10\)
	\(GA\)	\(P=10\), \(300\) it.	\(508\)	\(516.9\)	\(521\)	\(4\)
	memetico	\(P=10\), \(300\) it.	\(521\)	\(521.0\)	\(521\)	\(10\)
PCM15	LPT	—	\(73\)	\(73\)	\(73\)	\(0\)
	\(TS\)	\(tenure=15\), \(300\) it.	\(69\)	\(69\)	\(69\)	\(10\)
	\(VNS\)	\(k_{\max}=3\), \(300\) it.	\(69\)	\(69.3\)	\(70\)	\(7\)
BPP24	FFD	—	\(10\)	\(10\)	\(10\)	\(0\)
	\(LNS\), riparazione FFD	\(q=3\), \(200\) it.	\(10\)	\(10.0\)	\(10\)	\(0\)
	\(LNS\), riparazione esatta	\(q=3\), \(200\) it.	\(9\)	\(9.0\)	\(9\)	\(10\)

Ogni metaeuristica migliora la ricerca locale su cui è costruita, e con parametri adatti diverse di esse raggiungono l'ottimo in ogni esecuzione. La tabella mostra però anche quanto il risultato dipenda dai parametri (la durata tabu di \(TS\), l'intensità \(q\) della distruzione, il raffreddamento di \(SA\)) e dalle componenti (la riparazione di \(LNS\), la ricerca locale dell'algoritmo memetico). Su quattro istanze piccole non stabilisce una classifica dei metodi: una classifica del genere richiede molte istanze e tempi di calcolo uguali, come discusso nel capitolo «Algoritmi euristici: definizioni».

Ogni metaeuristica di questo capitolo combina una componente che intensifica (cerca intorno alle soluzioni buone già trovate) e una componente che diversifica (sposta la ricerca in regioni inesplorate), e ha parametri che fissano l'equilibrio fra le due.

metodo	intensificazione	diversificazione	equilibrio fissato da
\(SA\)	accettare solo mosse miglioranti a bassa temperatura	accettare mosse peggioranti ad alta temperatura	\(T_0\), fattore di raffreddamento \(\alpha\), \(L\)
\(TS\)	spostarsi sul miglior vicino; ripartire da soluzioni d'élite	lista tabu; penalità sugli attributi frequenti	durata tabu, criterio di aspirazione
\(ILS\)	ricerca locale dopo ogni kick; accettare solo ottimi locali migliori	il kick	intensità del kick, criterio di accettazione
\(VNS\)	ricerca locale; ritorno a \(k=1\) dopo un miglioramento	shaking in \(N_k\) con \(k\) crescente	\(k_{\max}\), gli intorni \(N_k\)
\(GRASP\)	ricerca locale su ogni soluzione costruita	costruzione randomizzata	\(\alpha\)
\(LNS\) / ALNS	riparazione (euristica o esatta), accettazione	distruzione casuale	\(q\), scelta dei metodi, pesi
\(GA\) / memetico	selezione, sostituzione, ricerca locale (memetico)	crossover, mutazione	dimensione della popolazione, \(p_m\)

Una metaeuristica è un algoritmo solo dopo che i suoi parametri sono stati fissati, e gli esperimenti di questo capitolo mostrano che i parametri possono fare la differenza fra trovare l'ottimo in ogni esecuzione e non trovarlo mai. Sceglierli si chiama calibrazione (tuning).
I parametri vanno calibrati su istanze di addestramento e valutati su istanze diverse, altrimenti il quadro è ottimistico. Calibrare un parametro alla volta ignora le loro interazioni (per \(SA\), il \(T_0\) migliore dipende da \(\alpha\)); strumenti come irace (López-Ibáñez et al., 2016) li calibrano tutti insieme. Un metodo che funziona bene per un ampio intervallo di parametri è preferibile a uno che funziona molto bene solo per un intervallo ristretto.

Nessuna delle metaeuristiche di questo capitolo usa un rilassamento del problema o un solver MIP. Manipolano solo soluzioni ammissibili (o penalizzate), e producono solo bound primali.
Di conseguenza, non possono dire quanto siano buone le loro soluzioni. Sulle istanze medie abbiamo potuto misurare la qualità solo perché i valori ottimi erano stati calcolati a parte, con algoritmi esatti.
Le due eccezioni confermano la regola: per \(P\,||\,C_{\max}\) e il BPP, \(TS\), \(VNS\) e \(LNS\) si sono fermati appena hanno raggiunto un lower bound semplice, che è un bound duale che certifica l'ottimalità; quando l'ottimo è sopra il bound, un certificato del genere non esiste, e la ricerca prosegue fino al limite di iterazioni.
La riparazione esatta di \(LNS\) (Sezione 32.9.1), infine, ha mostrato che riottimizzare in modo esatto una parte della soluzione, con il resto fissato, dà intorni molto potenti.

Le metaeuristiche escono dagli ottimi locali, ma danno solo un lato del gap: il bound primale.

Avanti: Errori tipici · In sintesi