Geometric differential evolution

ABSTRACT

Geometric Particle Swarm Optimization (GPSO) is a recently introduced formal generalization of traditional Particle Swarm Optimization (PSO) that applies naturally to both continuous and combinatorial spaces. Differential Evolution (DE) is similar to PSO but it uses different equations governing the motion of the particles. This paper generalizes the DE algorithm to combinatorial search spaces extending its geometric interpretation to these spaces, analogously as what was done for the traditional PSO algorithm. Using this formal algorithm, Geometric Differential Evolution (GDE), we formally derive the specific GDE for the Hamming space associated with binary strings and present experimental results on a standard benchmark of problems.

REFERENCES

• 1: T. Gong and A.L. Tuson. Differential evolution for binary encoding. In Soft Computing in Industrial Applications, pages 251--262. Springer, 2007.
• 2: S. Kauffman. Origins of order: self-organization and selection in evolution. Oxford University Press, 1993.
• 3: J. Kennedy and R.C. Eberhart. A discrete binary version of the particle swarm algorithm. IEEE Transactions on Systems, Man, and Cybernetics, 5:4104--4108, 1997.
• 4: James Kennedy , Russell C. Eberhart, Swarm intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 5: E.F. Krause. Taxicab Geometry: An Adventure in Non-Euclidean Geometry. Courier Dover Publications, 1986.
• 6: A. Moraglio. Towards a geometric unification of evolutionary algorithms. PhD thesis, University of Essex, 2007.
• 7: Alberto Moraglio , Julian Togelius, Geometric particle swarm optimization for the sudoku puzzle, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1276975]
• 8: Alberto Moraglio , Cecilia Di Chio , Julian Togelius , Riccardo Poli, Geometric particle swarm optimization, Journal of Artificial Evolution and Applications, 2008, p.1-14, January 2008 [doi>10.1155/2008/143624]
• 9: Alberto Moraglio , Julian Togelius, Geometric particle swarm optimization for the sudoku puzzle, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1276975]
• 10: Godfrey C. Onwubolu , Donald Davendra, Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization, Springer Publishing Company, Incorporated, 2009
• 11: G. Pampara, A. Engelbrecht, and N. Franken. Binary differential evolution. In IEEE Congress on Evolutionary Computation, 2006.
• 12: Kenneth Price , Rainer M. Storn , Jouni A. Lampinen, Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 13: Gilbert Syswerda, Uniform Crossover in Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.2-9, June 01, 1989
• 14: J. Togelius, R.D. Nardi, and A. Moraglio. Geometric pso + gp = particle swarm programming. In Proceedings of the Congress on Evolutionary Comptutation (CEC), 2008.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Theory

Keywords:
differential evolution