A multimodal particle swarm optimizer based on fitness Euclidean-distance ratio

ABSTRACT

One of the most critical issues that remains to be fully addressed in existing multimodal evolutionary algorithms is the difficulty in pre-specifying parameters used for estimating how far apart optima are. These parameters are typically represented as some sorts of niching parameters in existing EAs. Without prior knowledge of a problem, it is almost impossible to determine appropriate values for such niching parameters. This paper proposes a PSO for multimodal optimization that removes the need of these niching parameters. Our results show that the proposed algorithm, Fitness Euclidean-distance Ratio based PSO (FER-PSO) is able to reliably locate multiple global optima on the search landscape over some widely used multimodal optimization test functions, given that the population size is sufficiently large.

References

1. D. Beasley, D. R. Bull, andR. R. Martin. Asequential niche technique for multimodal function optimization. Evolutionary Computation 1(2):101--125, 1993.
2. M. Bessaou, A. Pétrowski, and P. Siarry. Island model cooperating with speciation for multimodal optimization. In Parallel Problem Solving from Nature-PPSNVI Springer Verlag, 16-20.
3. S. Bird and X. Li. Adaptively choosing niching parameters in a PSO. In M. Cattolico, editor, Genetic and Evolutionary Computation Conference, GECCO 2006, Proceedings, Seattl e, Washington, USA, July 8-12, 2006 pages 3--10. ACM, 2006.
4. S. Bird and X. Li. Enhancing the robustness of a speciation-based PSO. In e. a. Gary G. Yen, editor, Proceedings of the 2006 IEEE Congress on Evolutionary Computation pages 843--850, Vancouver, BC, Canada, 16-21 July 2006. IEEE Press.
5. R. Brits, A. Engelbrecht, andF. vandenBergh. A niching particle swarm optimizer. In Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning 2002(SEAL 2002)pages 692--696, 2002.
6. M. Clerc. Particle Swarm Optimization ISTELtd, London, UK, 2006.
7. M. Clerc and J. Kennedy. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evol. Comput. 6:58--73, Feb. 2002.
8. K. Deb and D. Goldberg. An investigation of niche and species formation in genetic function optimization. In J. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms pages 42--50, 1989.
9. R. Eberhart and Y. Shi. Comparing inertia weights and constriction factors in particle swarm optimization. In Proc. of IEEE Int. Conf. Evolutionary Computation pages 84--88, 2000.
10. D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In J. Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms pages 41--49, 1987.
11. G. R. Harik. Finding multimodal solutions using restricted tournament selection. In Proceedings of the Sixth International Conference on Genetic Algorithms Morgan Kaufmann.
12. K. A. D. Jong. An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, 1975.
13. J. Kennedy. In search of the essential particle swarm. In Proc. of 2006 IEEE Congress on Evolutionary Computation pages 6158--6165, 2006.
14. J. Kennedy and R. Eberhart. Swarm Intelligence Morgan Kaufmann, 2001.
15. J.-P. Li, M. E. Balazs, G. T. Parks, and P. J. Clarkson. A species conserving genetic algorithm for multimodal function optimization. Evol. Comput. 10(3):207--234, 2002.
16. X. Li. Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization. In K. Deb, editor, Proc. of Genetic and Evolutionary Computation Conference 2004(LNCS 3102)pages 105--116, 2004.
17. S. W. Mahfoud. Crowding and preselection revisited. In R. Männer and B. Manderick, editors, Parallel problem solving from nature 2 pages 27--36, Amsterdam, 1992. North-Holland.
18. R. Mendes, J. Kennedy, and J. Neves. The fully informed particle swarm:simpler, maybe better. IEEE Trans. Evol. Comput. 8:204--210, Jun. 2004.
19. Z. Michalewicz. Genetic Algorithms + Data Structures = EvolutionPrograms Springer-Verlag, New York, New York, 1996.
20. D. Parrott and X. Li. Locating and tracking multiple dynamic optima by a particle swarm model using speciation. IEEE Transactions on Evolutionary Computation 10(4):440--458, August 2006.
21. A. Pétrowski. A clearing procedure as a niching method for genetic algorithms. In Proceedings of the 3rd IEEE International Conference on Evolutionary Computation pages 798--803, 1996.
22. K. Veeramachaneni, T. Peram, C. Mohan, and L. Osadciw. Optimization using particle swarm with near neighbor interactions. In Proc. of Genetic and Evolutionary Computation Conference pages 110--121, Chicago, Illinois, 2003.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization