Self Adaptation in Ant Colony Optimisation

Authors

Abstract

ACO is a global metaheuristic loosely inspired by the behaviour of social ants. Several variants were proposed over the past two decades and, throughout this period, they have been successfully applied to solve difficult combinatorial optimisation problems. Notwith- standing its relevance in optimisation, ant colony algorithms have several well-known drawbacks. One important limitation is that they tend to be particularly sensitive to pa- rameterisation and different settings may obtain significant different results on the same situation. Also, they have strong greedy components that can easily lead to the loss of diversity and to premature convergence. This dissertation proposes two novel self-adaptive ant algorithms. Both of them rely on the coexistence of heterogeneous groups of ants within a single optimisation framework, each set with its own search strategy. Moreover, the search strategy is not fixed and, in- stead, the algorithms can autonomously adapt their behaviour to the different stages of the optimisation problem being solved. On-line self-adaptation has two crucial advan- tages: it frees the practitioner from having to carefully define settings for each specific optimisation situation and it grants the algorithm the ability to adjust its behaviour in accordance to the structure of the search landscape. The first contribution is MC-Ant, a multi-colony ant algorithm. Each colony is defined as a group of ants with its own search settings and acquired knowledge. Different colonies coexist in the algorithm while independently solving a problem. Periodically, good quality solutions migrate and effective search strategies are shared. Results obtained with the NPP show that MC-Ant outperforms single colony approaches, reinforcing the relevance of migration to avoid premature convergence and to allow an effective parameter self- adaptation. Multi-caste ACS is the second contribution of the work. It is an alternative self- adaptive, multi-strategy ACO approach, designed in such a way as to avoid a few efficiency issues exhibited by MC-Ant. In this framework, ants are divided in castes, and each caste has its own q0 value, a critical parameter to define the search strategy. Ants can migrate between castes according to some simple rules and this allows the algorithm to autonomously adjust its search strategy achieving a suitable balance between exploitation and exploration. Multi-caste ACS was applied to the symmetric TSP, both to the static and to the periodic and non-cyclic dynamic variants. Results confirm the advantage of the heterogeneous approach. Standard ACO variants excel in a subset of the optimisation scenarios but fail completely on others. On the contrary, Multi-caste approaches are extremely robust and are able to keep a balanced performance across all optimisation scenarios considered. This robustness is particularly evident in the dynamic environments.

Keywords

Ant Colony Optimisation, Dynamic Problems, Multi-population, Robustness, Self-adaptation

Subject

Doctoral Program in Information Science and Technology

PhD Thesis

Self Adaptation in Ant Colony Optimisation, August 2018

PDF File

DOI