Errori tipici · In sintesi¶

32.12 Errori tipici¶

Attenzione

Riportare una sola esecuzione. I risultati dipendono dal seme: riportare minimo, media e massimo su più esecuzioni.
Calibrare e valutare sulle stesse istanze. Il quadro è ottimistico; usare istanze di addestramento per i parametri e istanze diverse per la valutazione.
Perdere la soluzione migliore. Nel simulated annealing e nella tabu search la soluzione corrente può essere peggiore della migliore trovata: la migliore va memorizzata a parte.
Scegliere la durata tabu senza provarla. Con durata \(0\) la tabu search è una ricerca locale; una durata troppo piccola cicla, una troppo grande vieta quasi ogni mossa.
Contare male i numeri casuali. Ogni iterazione ne consuma un numero fisso (dieci nell'algoritmo genetico degli esercizi, con \(n=5\)); un conteggio sbagliato cambia tutti i passi successivi.

In sintesi

Una metaeuristica esce dagli ottimi locali accettando soluzioni peggiori (SA, TS), perturbando (ILS, VNS), randomizzando la costruzione (GRASP), distruggendo e riparando (LNS) o ricombinando una popolazione (GA).
Ogni metodo bilancia intensificazione e diversificazione con pochi parametri, e i risultati ne dipendono fortemente.
Non usano rilassamenti: producono solo bound primali, e non possono dire quanto siano buone le loro soluzioni.

Quadro riassuntivo delle istanze medie. Miglior valore dei metodi a confronto con l'ottimo (l'ottimo calcolato da un algoritmo esatto):

istanza	costruttiva	ricerca locale	migliore metaeuristica	ottimo
TSP20 (min)	\(326\) (\(NN\))	\(319\) (2-opt)	\(291\)	\(291\)
KP20 (max)	\(490\) (greedy)	\(514\)	\(521\)	\(521\)
PCM15 (min)	\(73\) (\(LPT\))	—	\(69\)	\(69\)
BPP24 (min)	\(10\) (FFD)	—	\(9\)	\(9\)

Avanti: Bibliografia