Self Adaptation in Ant Colony Optimisation

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.

A otimização baseada em colónias de formigas (ACO) é uma metaheurística global vaga- mente inspirada no comportamento social das formigas. Múltiplas variantes foram propos- tas ao longo das últimas duas décadas e, durante esse período, têm vindo a ser aplicadas com sucesso na resolução de problemas difíceis de otimização combinatória. Contudo, e apesar da sua relevância na área da otimização, os algoritmos de colónias de formigas pos- suem alguns inconvenientes conhecidos. Uma limitação importante é a sua sensibilidade à parametrização, de tal modo que, para uma dada situação, diferentes configurações po- dem obter resultados significativamente diferentes. Além disso, as componentes sôfregas do algoritmo podem facilmente levar à perda de diversidade e à convergência prematura. Esta dissertação propõe dois novos algoritmos auto-adaptativos baseados em colónias de formigas. Ambas as propostas se baseiam na coexistência de grupos heterogéneos de formigas para a resolução de um mesmo problema de otimização, mas em que cada grupo possui a sua própria estratégia de pesquisa. Além disso a estratégia de pesquisa não é fixa e os algoritmos podem adaptar, de forma autónoma, o seu comportamento às diversas fases da resolução do problema de otimização. A auto-adaptação em tempo real (on-line) tem duas vantagens cruciais: liberta o utilizador da necessidade de definir cuidadosamente as configurações para cada situação de otimização específica, e concede ao algoritmo a capacidade de ajustar o seu comportamento de acordo com a estrutura do espaço de pesquisa. A primeira contribuição é o MC-Ant, um algoritmo de formigas com várias colónias. Cada colónia consiste num grupo de formigas com as suas próprias configurações e co- nhecimento adquirido. As diferentes colónias existem em simultâneo e resolvem de forma independente o mesmo problema. Periodicamente são partilhadas soluções de boa quali- dade e estratégias de pesquisa. Os resultados obtidos com o NPP mostram que o MC-Ant tem um desempenho superior a abordagens de colónia única, reforçando a relevância da migração para evitar a convergência prematura e permitir uma auto-adaptação eficaz. O Multi-caste ACS é a segunda contribuição deste trabalho. É uma abordagem ACO multi-estratégica e auto-adaptativa alternativa, concebida de forma a evitar alguns pro- blemas de eficiência apresentados pelo MC-Ant. As formigas são divididas em castas, e cada casta tem o seu próprio q0, um parâmetro crucial na definição da estratégia de pesquisa. As formigas podem migrar entre castas de acordo com algumas regras simples. Deste modo, permite-se que o algoritmo ajuste a sua estratégia de pesquisa de forma au- tónoma e alcance um equilíbrio adequado entre a utilização do conhecimento adquirido e a exploração de novas áreas do espaço de pesquisa. O Multi-caste ACS foi aplicado ao TSP simétrico, tanto à versão estática como à ver- são dinâmica, periódica e não cíclica do problema. Os resultados confirmam a vantagem da abordagem heterogénea. As variantes clássicas dos ACO são eficazes num subcon- junto de cenários de otimização, mas falham completamente em outros. Pelo contrário, abordagens com várias castas são extremamente robustas e são capazes de manter um desempenho equilibrado em todos os cenários de otimização considerados. Essa robustez é particularmente evidente em ambientes dinâmicos.