Locating multiple optima using particle swarm optimization.

*(English)*Zbl 1122.65358Summary: Many scientific and engineering applications require optimization methods to find more than one solution to multi-modal optimization problems. This paper presents a new particle swarm optimization (PSO) technique to locate and refine multiple solutions to such problems. The technique, NichePSO, extends the inherent unimodal nature of the standard PSO approach by growing multiple swarms from an initial particle population. Each subswarm represents a different solution or niche; optimized individually. The outcome of the NichePSO algorithm is a set of particle swarms, each representing a unique solution.

Experimental results are provided to show that NichePSO can successfully locate all optima on a small set of test functions. These results are compared with another PSO niching algorithm, lbest PSO, and two genetic algorithm niching approaches. The influence of control parameters is investigated, including the relationship between the swarm size and the number of solutions (niches). An initial scalability study is also done.

Experimental results are provided to show that NichePSO can successfully locate all optima on a small set of test functions. These results are compared with another PSO niching algorithm, lbest PSO, and two genetic algorithm niching approaches. The influence of control parameters is investigated, including the relationship between the swarm size and the number of solutions (niches). An initial scalability study is also done.

##### MSC:

65K05 | Numerical mathematical programming methods |

90C15 | Stochastic programming |

90C29 | Multi-objective and goal programming |

##### Keywords:

particle swarm optimization; niching; speciation; numerical examples; multi-modal optimization; genetic algorithm##### Software:

MOPSO
PDF
BibTeX
XML
Cite

\textit{R. Brits} et al., Appl. Math. Comput. 189, No. 2, 1859--1883 (2007; Zbl 1122.65358)

Full Text:
DOI

##### References:

[1] | Bäck, T.; Foge, D.B.; Michalewicz, A., Handbook of evolutionary computation, (1997), IOP Publishers and Oxford University Press |

[2] | Beasley, D.; Bull, D.R.; Martin, R.R., A sequential niching technique for multimodal function optimization, Evolutionary computation, 1, 2, 101-125, (1993) |

[3] | Bishop, C.M., Neural networks for pattern recognition, (1995), Oxford University Press |

[4] | R. Brits, Niching Strategies for Particle Swarm Optimization. Master’s thesis, Department of Computer Science, University of Pretoria, Pretoria, South Africa, November 2002. |

[5] | R. Brits, A.P. Engelbrecht, F. van den Bergh, Solving systems of unconstrained equations using particle swarm optimizers, in: Proceedings of the IEEE Conference on Systems, Man and Cybernetics, October 2002, pp. 102 - 107. |

[6] | Clerc, M.; Kennedy, J., The particle swarm – explosion, stability and convergence in a multidimensional complex space, IEEE transactions on evolutionary computation, 6, 1, 58-73, (2002), February |

[7] | C.A. Coello Coello, An updated survey of evolutionary multiobjective optimization techniques: state of the art and future trends, in: Proceedings of the IEEE Congress on Evolutionary Computation, Washington, DC, July 1999, pp. 3-13. |

[8] | C.A. Coello Coello, M.S. Lechuga, MOPSO: a proposal for multiple objective particle swarm optimization, in: Proceedings of the IEEE World Congress on Evolutionary Computation, Honolulu, Hawaii, May 2002, pp. 1051-1056. |

[9] | Coello Coello, C.A.; van Veldhuizen, D.A.; Lamont, G.B., Evolutionary algorithms for solving multi-objective problems, (2003), Kluwer Academic Publishers · Zbl 1130.90002 |

[10] | K.A. de Jong, An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D. thesis, Department of Computer Science, University of Michigan, Ann Arbor, Michigan, USA, 1975. |

[11] | K. Deb, Genetic Algorithms in Multimodal Function Optimization. Master’s thesis, Department of Engineering Mathematics, University of Alabama, 1989. |

[12] | Dorigo, M.; Stützle, T., Ant colony optimization, (2004), MIT Press · Zbl 1092.90066 |

[13] | Engelbrecht, A.P., Fundamentals of computational swarm intelligence, (2005), John Wiley & Sons |

[14] | A.P. Engelbrecht, B.S. Masiye, G. Pampara, Niching ability of basic particle swarm optimization algorithms, in: Proceedings of the IEEE Swarm Intelligence Symposium, 2005. |

[15] | J.E. Fieldsend, S. Singh, A multi-objective algorithm based upon particle swarm optimisation, and efficient data structure and turbulence, in: The 2002 UK Workshop on Computational Intelligence, 2002, pp. 33-44. |

[16] | () |

[17] | D.E. Goldberg, J. Richardson, Genetic algorithm with sharing for multimodal function optimization, in: Proceedings of the Second International Conference on Genetic Algorithms, 1987, pp. 41-49. |

[18] | D.E. Goldberg, L. Wang, Adaptive Niching via Coevolutionary Sharing, technical report, Genetic Algorithm Lab, Urbana, University of Illinois, Illinois, August 1997. IlliGAL Rep. 97007. |

[19] | J. Horn, The nature of niching: Genetic algorithms and the evolution of optimal, cooperative populations. Ph.D. thesis, Urbana, University of Illinois, Illinois, Genetic Algorithm Lab, 1997. |

[20] | X. Hu, R. Eberhart, Multiobjective optimization using dynamic neighborhood particle swarm optimization, in: Proceedings of the IEEE World Congress on Evolutionary Computation, Honolulu, Hawaii, 12-17 May 2002, pp. 1677-1681. |

[21] | J. Kennedy, Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance, in: Proceedings of the IEEE Congress on Evolutionary Computation, July 1999, pp. 1931-1938. |

[22] | J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of the IEEE International Conference on Neural Networks, vol. IV, Perth, Australia, 1995, pp. 1942-1948. |

[23] | Kennedy, J.; Eberhart, R.C., Swarm intelligence, (2001), Morgan Kaufman |

[24] | J. Kennedy, R. Mendes, Population structure and particle swarm performance, in: Proceedings of the IEEE World Congress on Evolutionary Computation, Honolulu, Hawaii, May 2002, pp. 1671-1676. |

[25] | M. Løvbjerg, T.K. Rasmussen, T. Krink, Hybrid particle swarm optimizer with breeding and subpopulations, in: Proceedings of the Genetic and Evolutionary Computation Conference, vol. 1, San Fransisco, USA, July 2001, pp. 469-476. |

[26] | S.W. Mahfoud, A comparison of parallel and sequential niching methods, in: Proceedings of the Sixth International Conference on Genetic Algorithms, 1995, pp. 136-143. |

[27] | S.W. Mahfoud, Niching Methods for Genetic Algorithms. Ph.D. thesis, Genetic Algorithm Lab, University of Illinois, Illinois, 1995. IlliGAL Rep. 95001. |

[28] | O.J. Mengshoel, D.E. Goldberg, Probabilistic crowding: deterministic crowding with probabilistic replacement, in: Proceedings of the Genetic and Evolutionary Computation Conference 1999, San Fransisco, USA, Morgan Kaufmann, 1999, pp. 409-416. |

[29] | B.L. Miller, M.J. Shaw, Genetic Algorithms with Dynamic Niche Sharing for Multimodal Function Optimization, Technical report, Genetic Algorithm Lab, Urbana, University of Illinois, Illinois, December 1995. IlliGAL Rep. 95010. |

[30] | K.E. Parsopoulos, V.P. Plagianakos, G.D. Magoulas, M.N. Vrahatis, Stretching technique for obtaining global minimizers through particle swarm optimization, in: Proceedings of the Particle Swarm Optimization Workshop, Indianapolis, USA, 2001, pp. 22-29. · Zbl 1015.90064 |

[31] | Parsopoulos, K.E.; Vrahatis, M.N., Modification of the particle swarm optimizer for locating all the global minima, (), 324-327 · Zbl 1011.68103 |

[32] | K.E. Parsopoulos, M.N. Vrahatis, Particle swarm optimization method in multiobjective problems, in: Proceedings of the 2002 ACM Symposium on Applied Computing (SAC 2002), 2002, pp. 603-607. · Zbl 1018.68063 |

[33] | Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P., Numerical recipes in C: the art of scientific computing, (1992), Cambridge University Press · Zbl 0845.65001 |

[34] | Y. Shi, R.C. Eberhart, A modified particle swarm optimizer, in: Proceedings of the IEEE World Conference on Computational Intelligence, Anchorage, Alaska, May 1998, pp. 69-73. |

[35] | Y. Shi, R.C. Eberhart, An empirical study of particle swarm optimization, in: Proceedings of the IEEE Congress on Evolutionary Computation, Piscataway, NJ, 1999, pp. 1945-1960. |

[36] | P.N. Suganthan, Particle swarm optimizer with neighborhood operator, in: Proceedings of the IEEE Congress on Evolutionary Computation, July 1999, pp. 1958-1961. |

[37] | E. Thiémard, Economic Generation of Low-Discrepancy Sequences with a b-ary Gray Code, Department of Mathematics, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland. |

[38] | F. van den Bergh, An Analysis of Particle Swarm Optimizers. Ph.D. thesis, Department of Computer Science, University of Pretoria, Pretoria, South Africa, 2002. |

[39] | van den Bergh, F.; Engelbrecht, A.P., Cooperative learning in neural networks using particle swarm optimizers, South african computer journal, 26, 84-90, (2000), November |

[40] | F. van den Bergh, A.P. Engelbrecht, A new locally convergent particle swarm optimizer, in: Proceedings of the IEEE Conference on Systems, Man and Cybernetics, October 2002, pp. 96-101. |

[41] | van den Bergh, F.; Engelbrecht, A.P., A study of particle swarm optimization particle trajectories, Information science, 176, 8, 937-971, (2006) · Zbl 1093.68105 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.