Companion to:

A Critical Analysis of Parameter Adaptation in Ant Colony Optimization

Paola Pellegrini , Thomas St¨¹tzle and Mauro Birattari

IRIDIA, CoDE, Universit¨¦ Libre de Bruxelles, Brussels, Belgium




Abstract:

Applying parameter adaptation means operating on parameters of the algorithm at hand during the solution of an instance. For ant colony optimization, several parameter adaptation methods have been proposed. In the literature, these methods have been shown to improve the quality of the results achieved in some particular contexts. In particular, they proved to be successful when applied to novel ACO variants for tackling problems that are not a classical testbed for optimization algorithms. In this paper, we show that the adaptation methods proposed so far do not improve, and even worsen, the performance when applied to high performing ACO algorithm for some classical combinatorial optimization problems.



1. Instances used for the analysis on the TSP

2. Instances used for the analysis on the QAP

3. Complete results



Conclusions

In this paper, we empirically showed that the state-of-the-art parameter adaptation methods for ACO are not effective in a context different from the particular one for which they were proposed. The context that we considered is based on a high performing state-of-the-art ACO algorithm and two classical combinatorial optimization problems. We applied five adaptation methods to MMAS for both the traveling salesman problem and the quadratic assignment problem. We ran an extensive experimental analysis, considering several experimental setups. We exploited these setups for either refuting or corroborating four conjectures. Two of them were corroborated by the results, and two were refuted. We verified that: i) the higher the cardinality of the set of parameters adapted, and ii) the higher the quality of the results achieved by the algorithm, the smaller the improvement (or rather the larger the worsening) on the performance of the algorithm that adaptation methods can produce. We could not verify that: iii) the lower the heterogeneity of the set of instances to be tackled, and iv) the shorter the runtime, the smaller the improvement (or the larger the worsening) on the performance of the algorithm that adaptation methods can produce.
The ineffectiveness of the adaptation methods is evident in the results. We could observe only one exception to this conclusion, when the setting of non-adapted parameters leads the algorithm to achieve relatively low quality results. Otherwise, we could obtain better quality results without adapting any parameter during the runs. The cardinality of the set of parameters adapted does not affect these conclusions: even if considering the (unrealistic) a posteriori best case for the adaptation methods, applying an adaptation method worsens the results unless the setting of non-adapted parameters is performing poorly.
We will devote future research to the application of successful methods proposed for other metaheuristics to ACO. An example of such methods is the rank-based multi-armed bandit (Fialho, 2010) that was proposed for genetic algorithms. Despite the poor performance achieved by the methods proposed for ACO, in fact, our results do not contradict in absolute terms the merits of adaptation methods. In some specific cases, and when the appropriate method is used for adapting only the appropriate parameter(s), adaptation methods may provide an advantage. In future works we will better characterize situations in which parameter adaptation is useful. Moreover, we will devote further studies to the understanding of the impact each parameter has on the behavior of the algorithms. This may help in identifying the appropriate parameters to be adapted. In particular, we will try to combine off-line tuning and parameter adaptation by using off-line tuning to decide which parameters to adapt, and letting an adaptation method operate only on those parameters during the run.