Typical mistakes · In summary¶

32.12 Typical mistakes¶

Warning

Reporting one run. The results depend on the seed: report minimum, average and maximum over several runs.
Tuning and evaluating on the same instances. The picture is optimistic; use training instances for the parameters and different ones for the evaluation.
Losing the best solution. In simulated annealing and tabu search the current solution can be worse than the best one found: the best is stored apart.
Choosing the tenure without testing it. With tenure \(0\) tabu search is a local search; a tenure that is too small cycles, one that is too large forbids almost every move.
Miscounting the random numbers. Every iteration consumes a fixed number of them (ten in the genetic algorithm of the exercises, with \(n=5\)); a wrong count changes every later step.

In summary

A metaheuristic escapes from local optima by accepting worse solutions (SA, TS), by perturbing (ILS, VNS), by randomizing the construction (GRASP), by destroying and repairing (LNS) or by recombining a population (GA).
Each method balances intensification and diversification through a few parameters, and the results depend strongly on them.
They use no relaxation: they produce primal bounds only, and cannot tell how good their solutions are.

Dashboard of the medium instances. Best value of the methods against the optimum (the optimum computed by an exact algorithm):

instance	constructive	local search	best metaheuristic	optimum
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\)

Next: References