32.11 Comparison and conclusions¶
Part 4 · Heuristic algorithms · Chapter 32 · Chapter 32: Metaheuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Metaheuristics · App: TSP: simulated annealing and tabu search
32.11.1 The methods on the medium instances¶
- The table collects the results of the experiments of the previous sections: for each method, the best value found in \(10\) runs (\(seed=1,\dots,10\)), as minimum, average and maximum, and the number of runs that reach the optimum. Deterministic methods give the same value in every run.
| instance | method | parameters | min | average | max | optimal |
|---|---|---|---|---|---|---|
| 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 + local search | — | \(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\) | |
| memetic | \(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\), FFD repair | \(q=3\), \(200\) it. | \(10\) | \(10.0\) | \(10\) | \(0\) | |
| \(LNS\), exact repair | \(q=3\), \(200\) it. | \(9\) | \(9.0\) | \(9\) | \(10\) |
- Every metaheuristic improves on the local search it is built on, and with suitable parameters several of them reach the optimum in every run. The table, however, also shows how much the result depends on the parameters (the tenure of \(TS\), the strength \(q\) of the destruction, the cooling of \(SA\)) and on the components (the repair of \(LNS\), the local search of the memetic algorithm). On four small instances it does not rank the methods: such a ranking needs many instances and equal running times, as discussed in the chapter «Heuristic algorithms: definitions».
32.11.2 Intensification and diversification¶
- Every metaheuristic of this chapter combines a component that intensifies (searches around the good solutions already found) and a component that diversifies (moves the search to unexplored regions), and has parameters that set the balance between the two.
| method | intensification | diversification | balance set by |
|---|---|---|---|
| \(SA\) | accepting only improving moves at low temperature | accepting worse moves at high temperature | \(T_0\), cooling factor \(\alpha\), \(L\) |
| \(TS\) | moving to the best neighbour; restarting from elite solutions | tabu list; penalties on frequent attributes | tenure, aspiration criterion |
| \(ILS\) | local search after every kick; accepting only better local optima | the kick | strength of the kick, acceptance criterion |
| \(VNS\) | local search; return to \(k=1\) after an improvement | shaking in \(N_k\) with growing \(k\) | \(k_{\max}\), the neighbourhoods \(N_k\) |
| \(GRASP\) | local search on every constructed solution | randomized construction | \(\alpha\) |
| \(LNS\) / ALNS | repair (heuristic or exact), acceptance | random destroy | \(q\), choice of the methods, weights |
| \(GA\) / memetic | selection, replacement, local search (memetic) | crossover, mutation | population size, \(p_m\) |
32.11.3 Parameters and tuning¶
-
A metaheuristic is an algorithm only after its parameters are fixed, and the experiments of this chapter show that the parameters can make the difference between finding the optimum in every run and never finding it. Choosing them is called tuning.
-
The parameters must be tuned on training instances and evaluated on different ones, otherwise the picture is optimistic. Tuning one parameter at a time ignores their interactions (for \(SA\), the best \(T_0\) depends on \(\alpha\)); tools such as
irace(López-Ibáñez et al., 2016) tune all of them together. A method that works well for a wide range of parameters is preferable to one that works very well only for a narrow range.
32.11.4 What these methods do not use¶
-
None of the metaheuristics of this chapter uses a relaxation of the problem or a MIP solver. They manipulate feasible (or penalized) solutions only, and they produce only primal bounds.
-
As a consequence, they cannot tell how good their solutions are. On the medium instances we could measure the quality only because the optimal values had been computed separately, by exact algorithms.
-
The two exceptions confirm the rule: for \(P\,||\,C_{\max}\) and the BPP, \(TS\), \(VNS\) and \(LNS\) stopped as soon as they reached a simple lower bound, which is a dual bound that certifies optimality; when the optimum is above the bound, no such certificate exists, and the search goes on until the iteration limit.
-
The exact repair of \(LNS\) (Section 32.9.1), finally, showed that re-optimizing a part of the solution exactly, with the rest fixed, gives very powerful neighbourhoods.
Metaheuristics escape from local optima, but they give only one side of the gap: the primal bound.