Otimização Multimodal através de Computação Evolutiva e Análise de Agrupamentos

• Leonardo Ramos Emmendorfer UFPR
• Aurora Trinidad Ramirez Pozo UFPR

Resumo

A preservação de diversidade tem se mostrado muito importante em computação evolutiva, tanto para permitir a identificação e manutenção da estrutura do problema, quanto para manter múltiplos ótimos globais ao longo do processo evolutivo. Os principais algoritmos existentes procuram utilizar a manutenção de diversidade apenas como uma ferramenta auxiliar do processo, confiando em modelos mais sofisticados para a identificação da estrutura do problema. Uma nova abordagem é proposta, onde um algoritmo de agrupamento exerce um papel central no processo evolutivo, além de apenas garantir a diversidade necessária. Resultados empíricos mostram que a nova abordagem é efetiva na resolução de problemas multimodais.

Referências

Baluja, S. and Caruana, R. (1995). Removing the genetics from the standard genetic algorithm. In Int. Conf. on Machine Learning, pages 38–46.

Goldberg, D. E., Korb, G., and Deb, G. (1989). Messy genetic algorithms: Motivation, analysis , and first results. Complex Systems, 3:493–530.

Harik, G. R. (1997). Learning gene linkage to efficiently solve problems of bounded difficulty using genetic algorithms. PhD thesis, University of Michigan.

Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI.

Jakulin, A. and Bratko, I. (2004). Testing the significance of attribute interactions. In ICML ’04: Proceedings of the twenty-first international conference on Machine learning, page 52, New York, NY, USA. ACM Press.

Li, J.-P., Balazs, M. E., Parks, G. T., and Clarkson, P. J. (2002). A species conserving genetic algorithm for multimodal function optimization. Evol. Comput., 10(3):207–234.

Mahfoud, S. W. (1995). Niching methods for genetic algorithms. Doctoral dissertation, University of Illinois at Urbana-Champaign,, Urbana, USA.

McQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkley symposium on Mathematics, Statistics and Probability, pages 281–296.

Minsky, M. and Papert, S. (1969). Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Mass.

Pelikan, M. and Goldberg, D. E. (2000). Genetic algorithms, clustering, and the breaking of symmetry. In Parallel Problem Solving from Nature VI, pages 385–394.

Pelikan, M., Goldberg, D. E., and E.Cantu-Paz (1999). BOA: The bayesian optimization algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), pages 525–532.

Peña, J., Lozano, J., and Larrañaga, P. (2005). Globally multimodal problem optimization via an estimation of distribution algorithm based on unsupervised learning of bayesian networks. Evol. Comput., 13(1):43–66.

Petrowski, A. (1997). A new selection operator dedicated to speciation. In Proceedings of the 7th International Converence on Genetic Algorithms, pages 144–451.

Sastry, K., Abbass, H. A., Goldberg, D. E., and Johnson, D. D. (2005). Sub-structural niching in estimation of distribution algorithms. In GECCO ’05: Proceedings of the 2005 conference on Genetic and evolutionary computation, pages 671–678, New York, NY, USA. ACM Press.

Watson, R. A., Hornby, G., and Pollack, J. B. (1998). Modeling building-block interdependency. In PPSN V: Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, pages 97–108, London, UK. Springer-Verlag.