An evolutionary algorithm with species-specific explosion for multimodal optimization

ABSTRACT

This paper presents an evolutionary algorithm, which we call Evolutionary Algorithm with Species-specific Explosion (EASE), for multimodal optimization. EASE is built on the Species Conserving Genetic Algorithm (SCGA), and the design is improved in several ways. In particular, it not only identifies species seeds, but also exploits the species seeds to create multiple mutated copies in order to further converge to the respective optimum for each species. Experiments were conducted to compare EASE and SCGA on four benchmark functions. Cross-comparison with recent rival techniques on another five benchmark functions was also reported. The results reveal that EASE has a competitive edge over the other algorithms tested.

REFERENCES

• 1: David Beasley , David R. Bull , Ralph R. Martin, A sequential niche technique for multimodal function optimization, Evolutionary Computation, v.1 n.2, p.101-125, Summer 1993 [doi>10.1162/evco.1993.1.2.101]
• 2: Mourad Bessaou , Alain Pétrowski , Patrick Siarry, Island Model Cooperating with Speciation for Multimodal Optimization, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.437-446, September 18-20, 2000
• 3: Kalyanmoy Deb , David E. Goldberg, An Investigation of Niche and Species Formation in Genetic Function Optimization, Proceedings of the 3rd International Conference on Genetic Algorithms, p.42-50, June 01, 1989
• 4: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 5: David E. Goldberg , Jon Richardson, Genetic algorithms with sharing for multimodal function optimization, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.41-49, October 1987, Cambridge, Massachusetts, United States
• 6: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 7: Kenneth Alan De Jong, An analysis of the behavior of a class of genetic adaptive systems., University of Michigan, Ann Arbor, MI, 1975
• 8: K. A. D. Jong. Evolutionary Computation. A Unified Approach. MIT Press, Cambridge, MA, USA, 2006.
• 9: K. S. Leung and Y. Liang. Adaptive elitist-population based genetic algorithm for multimodal function optimization. In In GECCO 2003, LNCS 2723, pages 1160--1171. Springer-Verlag, 2003.
• 10: Jian-Ping Li , Marton E. Balazs , Geoffrey T. Parks , P. John Clarkson, A species conserving genetic algorithm for multimodal function optimization, Evolutionary Computation, v.10 n.3, p.207-234, Fall 2002 [doi>10.1162/106365602760234081]
• 11: Rodica I. Lung , Camelia Chira , D. Dumitrescu, An agent-based collaborative evolutionary model for multimodal optimization, Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1388969.1389008]
• 12: Rodica Ioana Lung , D. Dumitrescu, A new evolutionary model for detecting multiple optima, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277204]
• 13: R. Manner, S. W. Mahfoud, and S. W. Mahfoud. Crowding and preselection revisited. In Parallel Problem Solving From Nature, pages 27--36. North-Holland, 1992.,
• 14: Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.), Springer-Verlag, London, 1996
• 15: A. Petrowski. A clearing procedure as a niching method for genetic algorithms. In Evolutionary Computation, 1996., Proceedings of IEEE International Conference on, pages 798--803, Nagoya, Japan, May 1996.
• 16: Gulshan Singh , Kalyanmoy Deb, Dr., Comparison of multi-modal optimization algorithms based on evolutionary algorithms, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144200]
• 17: P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y. P. Chen, A. Auger, and S. Tiwari. Problem definitions and evaluation criteria for the cec 2005 special session on real parameter optimization. Technical report, Nanyang Technological University, 2005.
• 18: R. Thomsen. Multimodal optimization using crowding-based differential evolution. In Evolutionary Computation, 2004. CEC2004. Congress on, volume 2, pages 1382--1389, June 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
evolutionary algorithm, function optimization, genetic algorithm, multimodal optimization, species conserving genetic algorithm, species-specific explosion