Top

Soft Computing

Published in:

01-01-2010 | Original Paper

An investigation on niching multiple species based on population replacement strategies for multimodal functions optimization

Authors: Minqiang Li, Dan Lin, Jisong Kou

Published in: Soft Computing | Issue 1/2010

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper studies the niching mechanism based on population replacement in the process of evolution to solve the multimodal functions optimization (MMFO) problems. In order to niche multiple species for the MMFO tasks, the overlapping population replacement is surely needed because the offspring population most probably does not inherit all of the genetic information contained in its parental population, and the basic procedure for niching genetic algorithms with overlapping population replacement is presented. Then four niching schemes, the nearest neighbors replacement crowding (NNRC), the species conservation technique (SCT), the HFC-I (implicit hierarchical fair competition), and the CPE (clearing procedure with elitist) are investigated. These niching schemes are characterized with regard to different niching strategies and parameterizations, and the corresponding niching procedures are outlined. Finally, experiments are carried out on a suite of test functions to compare different niching strategies regarding niching efficiency and scalability. Experimental results illustrate the intrinsic difference of the four niching schemes. The NNRC and HFC-I have a mechanism of multiple species coevolution via adapting multiple species to different niches, while the SCT and CPE tend to make use of a mandatory mechanism to conserve species just like the grid searching over the solution space based on species distance or clearing radius. All niching methods are able to deal with complex MMFO problems, while the NNRC and HFC-I show a better performance in terms of niching efficiency and scalability, and are more robust regarding the algorithm parameterization.

previous article Using evolution strategies to solve DEC-POMDP problems

next article Triangular approximations of fuzzy numbers using α-weighted valuations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

The niching convergence and equilibrium is measured by population entropy. First, the real-valued variables are discretized into 32 intervals or \( 32 \times 32 \) grids in the 1-d or 2-d definition domain of a function. Second, the population entropy is computed by \( E_{\text{pop}} = - \sum\nolimits_{i = 0}^{K - 1} {\sum\nolimits_{j = 0}^{K - 1} {p_{ij} \log p_{ij} } } , \) where \( p_{ij} \) is the approximate proportion of individuals in the \( i \times j \) grid, \( i,j = 1,2, \ldots ,K,\;K = 31. \) If the relative decrease rate of the population entropy (smoothed for algorithms with fitness proportional selection) per 1000 fitness evaluations was smaller than the threshold (5%), the algorithm is taken as reaching niching convergence and equilibrium.

Bäck T, Fogel DB, Michalewicz Z (2000) Evolutionary Computation. Institute of Physics Publishing, Bristol and Philadelphia

Ballester P, Carter J (2003) Real-parameter genetic algorithms for finding multiple optimal solutions in multi-modal optimization. In: Erick Cantú-Paz et al (eds) Proceedings of the 2003 genetic and evolutionary computation conference (GECCO 2003), Lecture Notes in Computer Science 2, Springer, Berlin, pp 706–717

Beasley D, Bull DR, Martin RR (1993) A sequential niche technique for multimodal function optimization. Evolut Comput 1(2):10–125CrossRef

Beyer H-G (2001) The theory of evolution strategies. Springer, Berlin

Cedeño W, Vemuri V (1999) Analysis of speciation and niching in multi-niche crowding genetic algorithms. Theor Comput Sci 229(1–2):177–197MATHCrossRef

Cioppa AD, De Stefano C, Marcelli A (2004) On the role of population size and niche radius in fitness sharing. IEEE Trans Evolut Comput 8(6):580–592CrossRef

De Jong KA (1975) An Analysis of The Behavior of A Class of Genetic Adaptive Systems. Dissertation, University of Michigan, Ann Arbor. (University Microfilms No. 76-9381)

Eiben AE, Smith JE (2003) Introduction to Evolutionary Computing. Springer, BerlinMATH

Eshelman LJ, Shaffer JD (1993) Real coded genetic algorithms and interval schemata. In: Whitley LD (ed) Foundations of genetic algorithms II. Morgan Kaufmann, San Mateo, pp 187–202

Gan J, Warwick K (2001) Dynamic niche clustering: a fuzzy variable radius niching technique for multimodal optimization in GAs. In: Proceedings of the 2001 Congress on Evolutionary Computation (CEC 2001), vol 1. 27–30 May 2001, pp 215–222

Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company, New YorkMATH

Goldberg DE, Richardson JJ (1987) Genetic algorithms with sharing for multimodal function optimization. In: Proceedings of the second international conference on genetic algorithms (ICGA 2), pp 41–49

Goldberg DE, Deb K, Korb B (1990) Messy genetic algorithms revisited: studies in mixed size and scale. Complex Syst 4(4):415–444MATH

Goldberg DE, Deb K, Horn J (1992) Massive multimodality, deception, and genetic algorithms. Parallel Problem Solving from Nature, 2, pp 37–46. (Also IlliGAL Report No. 92007)

Gudla PK, Ganguli R (2005) An automated hybrid genetic-conjugate gradient algorithm for multimodal optimization problems. Applied Mathematics and Computation 167(2):1457–1474MATHCrossRefMathSciNet

Harik GR (1995) Finding multimodal solutions using restricted tournament selection. In: Proceedings of the sixth international conference on genetic algorithms (ICGA 6), pp 24–31 (Also IlliGAL Report No. 94002)

Herrera F, Lozano M, Sànchez AM (2003) A taxonomy for the crossover operator for real-coded genetic algorithms: an experimental study. Int J Intell Syst 18(3):309–338MATHCrossRef

Holland JH (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, 2nd edn. MIT Press, Cambridge

Horn J (1997) The Nature of niching: genetic algorithms and the evolution of optimal, cooperative populations. Dissertation, University of Illinois at Urbana-Champaign, Urbana, IL61801. (Also IlliGAL Report No. 97008)

Hu J, Goodman E (2004) Robust and efficient genetic algorithms with hierarchical niching and sustainable evolutionary computation model. In: Deb K et al (eds) Proceedings of genetic and evolutionary computation conference (GECCO 2004), Seattle, Washington, USA, June 2004; Part 1, Lecture Notes in Computer Science, vol 3,102, Springer, Berlin, pp 1220–1232

Hu J, Goodman ED, Seo K, Fan Z, Rosenberg R (2005) The hierarchical fair competition (HFC) framework for sustainable evolutionary algorithms. Evolut Comput 13(2):241–277CrossRef

Iwamatsu M (2006) Multi-species particle swarm optimizer for multimodal function optimization. IEICE Trans Inf Syst E89-D(3):1181–1187CrossRef

Jelasity M, Ortigosa PM, Garcia I (2001) UEGO, an abstract clustering technique for multimodal global optimization. J Heuristics 7(3):215–233MATHCrossRefMathSciNet

Lee C-G, Cho D-H, Jung H-K (1999) Niching genetic algorithm with restricted competition selection for multimodal function optimization. IEEE Transactions on Magnetics 35(3), Part 1, pp 1722–1725

Li M, Kou J (2005) A novel type of niching methods based on steady-state genetic algorithm. In: Wang L, Chen K, Ong YS (eds) Advances in natural computation: first international conference (ICNC 2005), lecture notes in computer science, vol 3612/2005, Springer, Berlin, pp 37–47

Li M, Kou J (2008) Crowding with nearest neighbors replacement for multiple species niching and building blocks preservation in binary multimodal functions optimization. J Heuristics 14(3):243–270MATHCrossRef

Li J-P, Balazs ME, Parks GT, Clarkson PJ (2002) A species conserving genetic algorithm for multimodal function optimization. Evolut Comput 10(3):207–234CrossRef

Lin C-Y, Yang Y-J (1998) Cluster identification techniques in genetic algorithms for multimodal optimization. Comput Aided Civil Infrastruct Eng 13(1):53–62(10)

Mahfoud SW (1995) Niching methods for genetic algorithms. Dissertation, University of Illinois at Urbana-Champaign, Urbana, IL61801 (Also IlliGAL Report No. 95001)

Pelikan M, Goldberg DE (2000) Genetic algorithms, clustering, and the breaking of symmetry. In: Proceedings of parallel problem solving from Nature VI, Springer, Berlin, pp 385–394 (Also IlliGAL Report No. 2000013)

Peña JM, Lozano JA, Larrañaga P (2005) Globally multimodal problem optimization via an estimation of distribution algorithm based on unsupervised learning of Bayesian networks. Evolut Comput 13(1):43–66CrossRef

Pétrowski A (1996) A clearing procedure as a niching method for genetic algorithms. In: Proceedings of the IEEE international conference evolutionary computation, Nagoya, Japan, pp 798–803

Reeves CR, Rowe JE (2003) Genetic algorithms: principles and perspectives—a guide to GA theory. Kluwer Academic Publishers, Boston

Sareni B, Krähenbühl L (1998) Fitness sharing and niching methods revisited. IEEE Trans Evolut Comput 2(3):97–106CrossRef

Siarry P, Pétrowski A, Bessaou M (2000) Island model cooperating with speciation for multimodal optimization. In: Schoenauer M et al (eds) Proceedings of 6th international conference on parallel problem solving from nature (PPSN-VI}), parallel problem solving from nature, Paris, France. Springer, Berlin, pp 437–446

Siarry P, Pétrowski A, Bessaou M (2002) A multipopulation genetic algorithm aimed at multimodal optimization. Adv Eng Softw 33(4):207–213MATHCrossRef

Van Hoyweghen C, Naudts B, Goldberg DE (2002) Spin-flip symmetry and synchronization. Evolut Comput 10(4):317–344CrossRef

Yin X, Germany N (1993) A fast algorithm with sharing scheme using cluster analysis methods in multimodal function optimization. In: Albrecht RF, Reeves CR, Steel NC (eds) Proceedings of the international conference on artificial neural nets and genetic algorithms. Springer, Berlin, pp 450–457

Yuan B, Gallagher M (2003) On building a principled framework for evaluating and testing evolutionary algorithms: a continuous landscape generator. In: Sarkar R et al (ed) Proceedings of the 2003 congress on evolutionary computation (CEC 2003), vol 1, 8–12 Dec 2003, pp 451–458

Title: An investigation on niching multiple species based on population replacement strategies for multimodal functions optimization
Authors: Minqiang Li
Dan Lin
Jisong Kou
Publication date: 01-01-2010
Publisher: Springer-Verlag
Published in: Soft Computing / Issue 1/2010
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-008-0389-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2010

Genetic hybrid tuning of VARMAX and state space algorithms

Using evolution strategies to solve DEC-POMDP problems

A niching genetic k-means algorithm and its applications to gene expression data

Level sets and the representation theorem for intuitionistic fuzzy sets

A multi-granular linguistic model for management decision-making in performance appraisal

Triangular approximations of fuzzy numbers using α-weighted valuations

Premium Partner