Multi-swarm optimization

Multi-swarm optimization is a variant of Particle swarm optimization (PSO) based on the use of multiple sub-swarms instead of one (standard) swarm. The general approach in multi-swarm optimization is that each sub-swarm focuses on a specific region while a specific diversification method decides where and when to launch the sub-swarms. The multi-swarm framework is especially fitted for the optimization on multi-modal problems, where multiple (local) optima exist.

Description

In multi-modal problems it is important to achieve an effective balance between exploration and exploitation. Multi-swarm systems provide a new approach to improve this balance. Instead of trying to achieve a compromise between exploration and exploitation which could weaken both mechanisms of the search process, multi-swarm systems separate them into distinct phases. Each phase is more focused on either exploitation (individual sub-swarms) or exploration (diversification method).

The coordination of the sub-swarms depends on the specific diversification method(s) implemented by the multi-swarm system. Wave of Swarm of Particles (WOSP),[1] for example, bases its diversification mechanism on the “collision” of particles. When particles get too close they are expelled by a short range force into new waves/sub-swarms, avoiding thus a complete convergence. The Dynamic Multi-Swarm-Particle Swarm Optimizer (DMS-PSO) [2] periodically regroups the particles of the sub-swarms (after they have converged) into new sub-swarms, the new swarms are started with particles from previous swarms. Locust swarms [3] are based on a “devour and move on” strategy – after a sub-swarm “devours” a relatively small region of the search space (to find a local optimum) scouts are deployed to look for new promising regions to “move on”.

A distinctive feature of sub-swarms is that their initial positions and initial velocities are not randomly selected as in normal swarms. Instead, they maintain some information from the previous trajectories of the particles. In general, the development of multi-swarm systems leads to design decisions which did not exist during the original development of particle swarm optimization, such as the number of particles to use in each sub-swarm, the optimal value for the constriction factor and the effects of non-random initial positions and initial velocities. These design decisions have been thoroughly studied and have well-established guidelines – e.g. the use of non-random initial positions and initial velocities leads to improved results in multi-swarm systems, which is not the case for single-swarms.[4] Other design decisions, such as which diversification method to use or which specific search strategy will select the initial positions and initial velocities of a sub-swarm, have less established guidelines and constitute open questions in the field of multi-swarm systems.

Some of these design decisions can be addressed by relatively independent sub-components which allow different optimization techniques to be inserted. Multi-swarm systems thus provide a useful framework for the development of hybrid algorithms. For example, the UMDA-PSO[5] multi-swarm system effectively combines components from Particle swarm optimization, Estimation of distribution algorithm, and Differential evolution into a multi-swarm hybrid.

Current Work

A reading group on Mendeley is available to all interested researchers.

See also

References

  1. ↑ T. Hendtlass, “WoSP: A Multi-Optima Particle Swarm Algorithm,” in Proceedings IEEE Congress on Evolutionary Computation, 2005, pp. 727–734.
  2. ↑ S. Z. Zhao, J. J. Liang, P. N. Suganthan, and M. F. Tasgetiren, “Dynamic Multi-Swarm Particle Swarm Optimizer with Local Search for Large Scale Global Optimization,” in Proceedings IEEE Congress on Evolutionary Computation, 2008, pp. 3845–3852.
  3. ↑ S. Chen, “Locust Swarms – A New Multi-Optima Search Technique”, in Proceedings of the IEEE Congress on Evolutionary Computation, 2009, pp. 1745–1752.
  4. ↑ S.Chen and J. Montgomery “Selection Strategies for Initial Positions and Initial Velocities in Multi–optima Particle Swarms”, in Proceedings of the Genetic and Evolutionary Computation Conference, 2011 pp. 53–60.
  5. ↑ Antonio Bolufé Röhler and S. Chen, “Multi-swarm hybrid for multi-modal optimization”, in Proceedings of the IEEE Congress on Evolutionary Computation, 2012, pp. 1759-1766.