A Importância da Informação Heurística Visibilidade para Algoritmos Baseados em Otimização por Colônia de Formigas Aplicados a Domínios Contínuos

• Cassio Rodrigo Conti UFSC
• Mauro Roisenberg UFSC

Resumo

Otimização por Colônia de Formigas (sigla em inglês, ACO) é uma meta-heurística baseada no comportamento das formigas na busca por alimento e foi originalmente desenvolvida para encontrar boas soluções em problemas de otimização combinatória (domínio discreto). Extensões do ACO para trabalhar diretamente no domínio contínuo têm surgido, entretanto as propostas mais similares à ideia clássica não usam a informação heurística chamada “visibilidade”, geralmente presente em algoritmos de ACO discreto. Neste trabalho é mostrada a importância da visibilidade em domínio discreto e proposta sua implementação em domínio contínuo. Resultados dos experimentos mostram melhora na velocidade de convergência com o uso da visibilidade.

Referências

Bilchev, G. and Parmee, I. C. (1995). The ant colony metaphor for searching continuous design spaces. AISB Workshop on Evolutionary Computing, 993:25–39.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Greedy Algorithms, chapter 16. MIT Press, 3rd edition.

Dorigo, M. (1992). Optimization, Learning and Natural Algorithms. PhD thesis, Dip. Elettronica e Informazione, Politecnico di Milano, Italy.

Dorigo, M., Maniezzo, V., and Colorni, A. (1991). Positive feedback as a search strategy. Technical report, Dipartimento di Elettronica - Politecnico di Milano - Italy.

Dorigo, M., Maniezzo, V., and Colorni, A. (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26(1):29–41.

Dréo, J. and Siarry, P. (2002). A new ant colony algorithm using the heterarchical concept aimed at optimization of multiminima continuous functions. In Dorigo, M., Di Caro, G., and Sampels, M., editors, Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 216–221. Springer Berlin / Heidelberg.

Huang, H. and Hao, Z. (2006). Aco for continuous optimization based on discrete encoding. Ant Colony Optimization and Swarm Intelligence, pages 504–505.

Kong, M. and Tian, P. (2005). A binary ant colony optimization for the unconstrained function optimization problem. In Hao, Y., Liu, J., Wang, Y.-P., Cheung, Y.-m., Yin, H., Jiao, L., Ma, J., and Jiao, Y.-C., editors, Computational Intelligence and Security, volume 3801 of Lecture Notes in Computer Science, pages 682–687. Springer Berlin / Heidelberg.

Kong, M. and Tian, P. (2006). A direct application of ant colony optimization to function optimization problem in continuous domain. Ant Colony Optimization and Swarm Intelligence, pages 324–331.

Madadgar, S. and Afshar, A. (2008). An Improved Continuous Ant Algorithm for Optimization of Water Resources Problems. Water Resources Management, 23(10):2119–2139.

Mathur, M., Karale, S. B., Priye, S., Jayaraman, V. K., and Kulkarni, B. D. (2000). Ant colony approach to continuous function optimization. Industrial & Engineering Chemistry Research, 39(10):3814–3822.

Monmarchè, N., Venturini, G., and Slimane, M. (2000). On how pachycondyla apicalis ants suggest a new search algorithm. Future Generation Computer Systems, 16(9):937–946.

Socha, K. (2004). Aco for continuous and mixed-variable optimization. Ant Colony Optimization and Swarm Intelligence, pages 25–36.

Socha, K. and Dorigo, M. (2006). Ant colony optimization for continuous domains. European Journal of Operational Research, 185:1155–1173.

Vannimenus, J. and Mézard, M. (1984). On the statistical mechanics of optimization problems of the travelling salesman type. Journal de Physique Lettres, 45(24):1145–1153.