Convergence behavior of the fully informed particle swarm optimization algorithm

ABSTRACT

The fully informed particle swarm optimization algorithm (FIPS) is very sensitive to changes in the population topology. The velocity update rule used in FIPS considers all the neighbors of a particle to update its velocity instead of just the best one as it is done in most variants. It has been argued that this rule induces a random behavior of the particle swarm when a fully connected topology is used. This argument could explain the often observed poor performance of the algorithm under that circumstance.

In this paper we study experimentally the convergence behavior of the particles in FIPS when using topologies with different levels of connectivity. We show that the particles tend to search a region whose size decreases as the connectivity of the population topology increases. We therefore put forward the idea that spatial convergence, and not a random behavior, is the cause of the poor performance of FIPS with a fully connected topology. The practical implications of this result are explored.

REFERENCES

• 1: M. Clerc and J. Kennedy. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1):58--73, 2002.
• 2: Andries P. Engelbrecht, Fundamentals of Computational Swarm Intelligence, John Wiley & Sons, 2006
• 3: B. Gaboune, G. Laporte, and F. Soumis. Expected distances between two uniformly distributed random points in renctangles and rectangluar parallelpipeds. The Journal of the Operational Research Society, 44(5):513--519, 1993.
• 4: Holger Hoos , Thomas Sttzle, Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 5: J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of IEEE International Conference on Neural Networks, pages 1942--1948, Piscataway, NJ, USA, 1995. IEEE Press.
• 6: J. Kennedy and R. Mendes. Neighborhood topologies in fully informed and best-of-neighborhood particle swarms. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 36(4):515--519, 2006.
• 7: R. Mendes. Population Topologies and Their Influence in Particle Swarm Performance. PhD thesis, Escola de Engenharia, Universidade do Minho, 2004.
• 8: R. Mendes, J. Kennedy, and J. Neves. The fully informed particle swarm: Simpler, maybe better. IEEE Transactions on Evolutionary Computation, 8(3):204--210, 2004.
• 9: Riccardo Poli, On the moments of the sampling distribution of particle swarm optimisers, Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, July 07-11, 2007, London, United Kingdom [doi>10.1145/1274000.1274075]
• 10: R. Poli, J. Kennedy, and T. Blackwell. Particle swarm optimization. An overview. Swarm Intelligence, 1(1):33--57, 2007.
• 11: Andrew M. Sutton , Darrell Whitley , Monte Lunacek , Adele Howe, PSO and multi-funnel landscapes: how cooperation might limit exploration, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144008]

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
          Subjects: Global optimization

General Terms:
Algorithms

Keywords:
experiments, particle swarm optimization, swarm intelligence