Multimodal Optimization through Evolutionary Computation and Cluster Analysis

• Leonardo Ramos Emmendorfer UFPR
• Aurora Trinidad Ramirez Pozo UFPR

Abstract

Diversity preservation has shown to be very important for identification and maintenance of the problem structure, as much as for keeping several global optima during the process, in the context of evolutionary computation. The currently most important algorithms adopt diversity preservation techniques just as an auxiliary tool in the process, while trusting on more sophisticated models for the identification of the problem structure. A novel approach is proposed, where a clustering algorithm plays a central role in the evolutionary process, beyond just maintaining the diversity required. Empirical results show the effectiveness of this new approach when solving multimodal optimization problems.

References

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.