Exploring extended particle swarms: a genetic programming approach

ABSTRACT

Particle Swarm Optimisation (PSO) uses a population of particles that fly over the fitness landscape in search of an optimal solution. The particles are controlled by forces that encourage each particle to fly back both towards the best point sampled by it and towards the swarm's best point, while its momentum tries to keep it moving in its current direction.Previous research started exploring the possibility of evolving the force generating equations which control the particles through the use of genetic programming (GP).We independently verify the findings of the previous research and then extend it by considering additional meaningful ingredients for the PSO force-generating equations, such as global measures of dispersion and position of the swarm. We show that, on a range of problems, GP can automatically generate new PSO algorithms that outperform standard human-generated as well as some previously evolved ones.

REFERENCES

• 1: P.J. Angeline, Using Selection to Improve Particle Swarm Optimization, ICEC, 84--89, 1998.
• 2: Wolfgang Banzhaf , Frank D. Francone , Robert E. Keller , Peter Nordin, Genetic programming: an introduction: on the automatic evolution of computer programs and its applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 3: T. M. Blackwell , Peter J. Bentley, Dynamic Search With Charged Swarms, Proceedings of the Genetic and Evolutionary Computation Conference, p.19-26, July 09-13, 2002
• 4: T.M. Blackwell and J. Branke, Multi-swarm Optimization in Dynamic Environments., EvoWorkshops, 489--500, 2004.
• 5: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 6: R. Brits, A.P. Engelbrecht and B. Bergh, A Niching Particle Swarm Optimizer, SEAL, 692--696, 2002.
• 7: M. Clerc and J. Kennedy, The Particle Swarm - Explosion, Stability, and Convergence in a Multidimensional Complex Space, IEEE Trans. Evolutionary Computation, 6, 1, 58--73, 2002.
• 8: James Kennedy, The Behavior of Particles, Proceedings of the 7th International Conference on Evolutionary Programming VII, p.581-589, March 25-27, 1998
• 9: James Kennedy , Russell C. Eberhart, Swarm intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 10: J. Kennedy and R.C. Eberhart, Particle Swarm Optimization, IEEE ICNN, 1942--1948, 1995.
• 11: John R. Koza , James P. Rice, Genetic programming (videotape): the movie, MIT Press, Cambridge, MA, 1992
• 12: T. Krink, J.S. Vesterstrøm, and R. Riget, Particle Swarm Optimisation with Spatial Particle Extension, CEC, 1474--1479, 2002.
• 13: Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
• 14: M. Løvbjerg and T. Krink, Extending Particle Swarms with Self-Organized Criticality, CEC, 1588--1593, 2002.
• 15: E. Ozcan and C.K. Mohan, Particle Swarm Optimization: Surfing the Waves, CEC, 1939--1944, 1999.
• 16: R. Poli and C.R. Stephens, Constrained Molecular Dynamics as a Search and Optimization Tool, EuroGP, 150--161, 2004.
• 17: R. Poli, W.B. Langdon and O. Holland, Extending Particle Swarm Optimisation via Genetic Programming, EuroGP, 291--300, 2005.
• 18: Y. Shi and R.C. Eberhart, A Modified Particle Swarm Optimizer, CEC, 69--73, 1999.
• 19: J.S. Vesterstrøm, J. Riget and T. Krink, Division of Labor in Particle Swarm Optimisation, CEC, 1570--1575, 2002.
• 20: D. Wolpert and W.G. Macready, No Free Lunch Theorems for Optimization, IEEE Trans. Evolutionary Computation, 1, 1, 67--82, 1997.

INDEX TERMS

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

General Terms:
Performance

Keywords:
genetic programming, particle swarm optimisation, swarm intelligence