nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

Niching in Evolutionary Algorithms

verfasst von : Ofer M. Shir

Erschienen in: Handbook of Natural Computing

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Niching techniques are the extension of standard evolutionary algorithms (EAs) to multi-modal domains, in scenarios where the location of multiple optima is targeted and where EAs tend to lose population diversity and converge to a solitary basin of attraction. The development and investigation of EA niching methods have been carried out for several decades, primarily within the branches of genetic algorithms (GAs) and evolution strategies (ES). This research yielded altogether a long list of algorithmic approaches, some of which are bio-inspired by various concepts of organic speciation and ecological niches, while others are more computational-oriented. This chapter will lay the theoretical foundations for niching, from the perspectives of biology as well as optimization, provide a summary of the main contemporary niching techniques within EAs, and discuss the topic of experimental methodology for niching techniques. This will be accompanied by the discussion of specific case-studies, including the employment of the popular covariance matrix adaptation ES within a niching framework, the application to real-world problems, and the treatment of the so-called niche radius problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Coevolutionary Principles

Nächstes Kapitel DNA Computing — Foundations and Implications

Adamidis P (1994) Review of parallel genetic algorithms bibliography. Tech. rep., Automation and Robotics Lab., Dept. of Electrical and Computer Eng., Aristotle University of Thessaloniki, Greece

Aichholzer O, Aurenhammer F, Brandtstätter B, Ebner T, Krasser H, Magele C (2000) Niching evolution strategy with cluster algorithms. In: Proceedings of the 9th biennial IEEE conference on electromagnetic field computations. IEEE Press, New York

Ando S, Sakuma J, Kobayashi S (2005) Adaptive isolation model using data clustering for multimodal function optimization. In: Proceedings of the 2005 conference on genetic and evolutionary computation, GECCO 2005. ACM, New York, pp 1417–1424

Angus D (2006) Niching for population-based ant colony optimization. In: Second international conference on e-science and grid technologies (e-science 2006), December 4–6, 2006, Amsterdam, The Netherlands, IEEE Computer Society, p 115

Auger A, Hansen N (2005a) A restart CMA evolution strategy with increasing population size. In: Proceedings of the 2005 congress on evolutionary computation CEC 2005. IEEE Press, Piscataway, NJ, pp 1769–1776

Auger A, Hansen N (2005b) Performance evaluation of an advanced local search evolutionary algorithm. In: Proceedings of the 2005 congress on evolutionary computation CEC 2005. IEEE Press, Piscataway, NJ, pp 1777–1784

Avigad G, Moshaiov A, Brauner N (2004) Concept-based interactive brainstorming in engineering design. J Adv Comput Intell Intell Informatics 8(5): 454–459

Avigad G, Moshaiov A, Brauner N (2005) Interactive concept-based search using MOEA: the hierarchical preferences case. Int J Comput Intell 2(3):182–191

Bäck T (1994) Selective pressure in evolutionary algorithms: a characterization of selection mechanisms. In: Michalewicz Z, Schaffer JD, Schwefel HP, Fogel DB, Kitano H (eds) Proceedings of the first IEEE conference on evolutionary computation (ICEC’94). Orlando FL. IEEE Press, Piscataway, NJ, pp 57–62CrossRef

Bäck T (1996) Evolutionary algorithms in theory and practice. Oxford University Press, New YorkMATH

Bartz-Beielstein T (2006) Experimental research in evolutionary computation – the new experimentalism. Natural computing series. Springer, BerlinMATH

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

Beyer HG (1999) On the dynamics of GAs without selection. In: Banzhaf W, Reeves C (eds) Foundations of genetic algorithms 5. Morgan Kaufmann, San Francisco, CA, pp 5–26

Beyer HG, Schwefel HP (2002) Evolution strategies a comprehensive introduction. Nat Comput Int J 1(1):3–52MathSciNetCrossRefMATH

Beyer HG, Brucherseifer E, Jakob W, Pohlheim H, Sendhoff B, To TB (2002) Evolutionary algorithms - terms and definitions. http://ls11-www.cs.uni-dortmund.de/people/beyer/EA-glossary/

Blum C (2005) Ant colony optimization: introduction and recent trends. Phys Life Rev 2:353–373CrossRef

Bradshaw A (1965) Evolutionary significance of phenotypic plasticity in plants. Adv Genet 13:115–155CrossRef

Branke J (2001) Evolutionary optimization in dynamic environments. Kluwer, Norwell, MA

Brits R, Engelbrecht AP, Bergh FVD (2002) A niching particle swarm optimizer. In: The fourth Asia-Pacific conference on simulated evolution and learning (SEAL2002). Singapore, pp 692–696

Cavicchio D (1970) Adaptive search using simulated evolution. Ph.D. thesis, University of Michigan, Ann Arbor, MI

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

Coello Coello CA, Lamont GB, Van Veldhuizen DA (2007) Evolutionary algorithms for solving multiobjective problems. Springer, Berlin

Coello Coello CA (1999) A survey of constraint handling techniques used with evolutionary algorithms. Tech. Rep. Lania-RI-99-04, Laboratorio Nacional de Informática Avanzada. Xalapa, Veracruz, México

Cristiano JJ, White CC, Liker JK (2001) Application of multiattribute decision analysis to quality function deployment for target setting. IEEE Trans Syst Man Cybern Part C 31(3):366–382CrossRef

Darwin CR (1999) The origin of species: by means of natural selection or the preservation of favoured races in the struggle for life. Bantam Classics, New York

De Jong KA (1975) An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, University of Michigan, Ann Arbor, MI

Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, New YorkMATH

Deb K, Goldberg DE (1989) An investigation of niche and species formation in genetic function optimization. In: Proceedings of the third international conference on genetic algorithms. Morgan Kaufmann, San Francisco, CA, pp 42–50

Deb K, Spears WM (1997) Speciation methods. In: Bäck T, Fogel D, Michalewicz Z (eds) The handbook of evolutionary computation. IOP Publishing and Oxford University Press, Bristol

Deb K, Tiwari S (2005) Omni-optimizer: a procedure for single and multi-objective optimization. In: Evolutionary multi-criterion optimization, third international conference, EMO 2005, Lecture notes in computer science, vol 3410. Springer, Guanajuato, Mexico, pp 47–61

Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge, MACrossRefMATH

Doye J, Leary R, Locatelli M, Schoen F (2004) Global optimization of Morse clusters by potential energy transformations. INFORMS J Comput 16(4): 371–379CrossRefMATH

Engelbrecht A (2005) Fundamentals of computational swarm intelligence. New York

Fisher RA (1922) Darwinian evolution of mutations. Eugen Rev 14:31–34

Fogel LJ (1966) Artificial intelligence through simulated evolution. Wiley, New YorkMATH

Freeman S, Herron JC (2003) Evolutionary analysis. Benjamin Cummings, 3rd edn. Redwood City, CA

Gan J, Warwick K (2001) Dynamic niche clustering: a fuzzy variable radius niching technique for multimodal optimisation in GAs. In: Proceedings of the 2001 congress on evolutionary computation CEC2001, IEEE Press, COEX, World Trade Center, 159 Samseong-dong. Gangnam-gu, Seoul, Korea, pp 215–222

van der Goes V, Shir OM, Bäck T (2008) Niche radius adaptation with asymmetric sharing. In: Parallel problem solving from nature – PPSN X, Lecture notes in computer science, vol 5199. Springer, pp 195–204

Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, MAMATH

Goldberg DE, Richardson J (1987) Genetic algorithms with sharing for multimodal function optimization. In: Proceedings of the second international conference on genetic algorithms and their application. Lawrence Erlbaum, Mahwah, NJ, pp 41–49

Grosso PB (1985) Computer simulations of genetic adaptation: parallel subcomponent interaction in a multilocus model. Ph.D. thesis, University of Michigan, Ann Arbor, MI

Hanagandi V, Nikolaou M (1998) A hybrid approach to global optimization using a clustering algorithm in a genetic search framework. Comput Chem Eng 22(12):1913–1925CrossRef

Hansen N, Ostermeier A (2001) Completely derandomized self-adaptation in evolution strategies. Evolut Comput 9(2):159–195CrossRef

Hansen N, Ostermeier A, Gawelczyk A (1995) On the adaptation of arbitrary normal mutation distributions in evolution strategies: the generating set adaptation. In: Proceedings of the sixth international conference on genetic algorithms (ICGA6). Morgan Kaufmann, San Francisco, CA, pp 57–64

Haykin S (1999) Neural networks: a comprehensive foundation, 2nd edn. Prentice Hall, NJ, USAMATH

Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor, MI

Igel C, Suttorp T, Hansen N (2006) A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies. In: Proceedings of the genetic and evolutionary computation conference, GECCO 2006. ACM, New York, pp 453–460

Jelasity M (1998) UEGO, an abstract niching technique for global optimization. In: Parallel problem solving from nature - PPSN V, Lecture notes in computer science, vol 1498. Springer, Amsterdam, pp 378–387

Kennedy J, Eberhart R (2001) Swarm intelligence. Morgan Kaufmann, San Francisco, CA

Kimura M (1983) The neutral theory of molecular evolution. Cambridge University Press, CambridgeCrossRef

Kramer O, Schwefel HP (2006) On three new approaches to handle constraints within evolution strategies. Nat Comput Int J 5(4):363–385MathSciNetCrossRefMATH

Li R, Eggermont J, Shir OM, Emmerich M, Bäck T, Dijkstra J, Reiber J (2008) Mixed-integer evolution strategies with dynamic niching. In: Parallel problem solving from nature - PPSN X, Lecture notes in computer science, vol 5199. Springer, pp 246–255

Lunacek M, Whitley D (2006) The dispersion metric and the CMA evolution strategy. In: Proceedings of the genetic and evolutionary computation conference, GECCO 2006. ACM, New York, pp 477–484

Lunacek M, Whitley D, Sutton A (2008) The impact of global structure on search. In: Parallel problem solving from nature - PPSN X, Lecture notes in computer science, vol 5199. Springer, pp 498–507

Mahfoud SW (1995a) Niching methods for genetic algorithms. Ph.D. thesis, University of Illinois at Urbana Champaign, IL

Mahfoud SW (1995b) A comparison of parallel and sequential niching methods. In: Eshelman L (ed) Proceedings of the sixth international conference on genetic algorithms. Morgan Kaufmann, San Francisco, CA, pp 136–143

Martin W, Lienig J, Cohoon J (1997) Island (migration) models: evolutionary algorithms based on punctuated equilibria. In: Bäck T, Fogel DB, Michalewicz Z (eds) Handbook of evolutionary computation. Oxford University Press, New York, and Institute of Physics, Bristol, pp C6.3:1–16

McPheron BA, Smith DC, Berlocher SH (1988) Genetic differences between host races of Rhagoletis pomonella. Nature 336:64–66CrossRef

Miller B, Shaw M (1996) Genetic algorithms with dynamic niche sharing for multimodal function optimization. In: Proceedings of the 1996 IEEE international conference on evolutionary computation (ICEC’96). New York, pp 786–791

Ostermeier A, Gawelczyk A, Hansen N (1993) A derandomized approach to self adaptation of evolution strategies. Tech. rep., TU Berlin

Ostermeier A, Gawelczyk A, Hansen N (1994) Step-size adaptation based on non-local use of selection information. In: Parallel problem solving from nature - PPSN III, Lecture notes in computer science, vol 866. Springer, Berlin, pp 189–198

Parrott D, Li X (2006) Locating and tracking multiple dynamic optima by a particle swarm model using speciation. Evolut Comput, IEEE Trans 10(4): 440–458, doi: 10.1109/TEVC.2005.859468CrossRef

Petrowski A (1996) A clearing procedure as a niching method for genetic algorithms. In: Proceedings of the 1996 IEEE international conference on evolutionary computation (ICEC’96). New York, pp 798–803

Preuss M (2006) Niching prospects. In: Proceedings of the international conference on bioinspired optimization methods and their applications, BIOMA 2006. Jožef Stefan Institute, Slovenia, pp 25–34

Preuss M (2007) Reporting on experiments in evolutionary computation. Tech. Rep. CI-221/07, University of Dortmund, SFB 531

Ramalhinho-Lourenco H, Martin OC, Stützle T (2000) Iterated local search. Economics Working Papers 513, Department of Economics and Business, Universitat Pompeu Fabra

Scheiner SM, Goodnight CJ (1984) The comparison of phenotypic plasticity and genetic variation in populations of the grass Danthonia spicata. Evolution 38(4):845–855CrossRef

Schönemann L, Emmerich M, Preuss M (2004) On the extinction of sub-populations on multimodal landscapes. In: Proceedings of the international conference on bioinspired optimization methods and their applications, BIOMA 2004. Jožef Stefan Institute, Slovenia, pp 31–40

Shir OM (2008) Niching in derandomized evolution strategies and its applications in quantum control. Ph.D. thesis, Leiden University, The Netherlands

Shir OM, Bäck T (2005a) Dynamic niching in evolution strategies with covariance matrix adaptation. In: Proceedings of the 2005 congress on evolutionary computation CEC-2005. IEEE Press, Piscataway, NJ, pp 2584–2591

Shir OM, Bäck T (2005b) Niching in evolution strategies. Tech. Rep. TR-2005-01, LIACS, Leiden University

Shir OM, Bäck T (2006) Niche radius adaptation in the CMA-ES niching algorithm. In: Parallel problem solving from nature - PPSN IX, Lecture notes in computer science, vol 4193. Springer, pp 142–151

Shir OM, Bäck T (2008) Niching with derandomized evolution strategies in artificial and real-world landscapes. Nat Comput Int J (2008), doi: 10.1007/s11047-007-9065-5

Shir OM, Beltrani V, Bäck T, Rabitz H, Vrakking MJ (2008) On the diversity of multiple optimal controls for quantum systems. J Phys B At Mol Opt Phys 41(7):(2008). doi: 10.1088/0953-4075/41/7/074021

Shir OM, Emmerich M, Bäck T (2010) Adaptive niche-radii and niche-shapes approaches for niching with the CMA-ES. Evolut Comput 18(1):97–126. doi: 10.1162/evco.2010.18.1.18104

Singh G, Deb K (2006) Comparison of multi-modal optimization algorithms based on evolutionary algorithms. In: Proceedings of the 2006 annual conference on genetic and evolutionary computation, GECCO 2006. ACM Press, New York, pp 1305–1312

Smith RE, Bonacina C (2003) Mating restriction and niching pressure: results from agents and implications for general EC. In: Proceedings of the 2003 conference on genetic and evolutionary computation, GECCO 2003, Lecture notes on computer science, vol 2724. Springer, Chicago, IL, pp 1382–1393

Spears WM (1994) Simple subpopulation schemes. In: Proceedings of the 3rd annual conference on evolutionary programming, World Scientific. San Diego, CA, Singapore, pp 296–307

Stoean C, Preuss M, Gorunescu R, Dumitrescu D (2005) Elitist generational genetic chromodynamics – a new radii-based evolutionary algorithm for multimodal optimization. In: Proceedings of the 2005 congress on evolutionary computation (CEC’05). IEEE Press, Piscataway NJ, pp 1839–1846

Stoean C, Preuss M, Stoean R, Dumitrescu D (2007) Disburdening the species conservation evolutionary algorithm of arguing with radii. In: Proceedings of the genetic and evolutionary computation conference, GECCO 2007. ACM Press, New York, pp 1420–1427

Streichert F, Stein G, Ulmer H, Zell A (2003) A clustering based niching EA for multimodal search spaces. In: Proceedings of the international conference evolution artificielle, Lecture notes in computer science, vol 2936. Springer, Heidelberg, Berlin, pp 293–304

Suganthan PN, Hansen N, Liang JJ, Deb K, Chen YP, Auger A, Tiwari S (2005) Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Tech. rep., Nanyang Technological University, Singapore

Törn A, Zilinskas A (1987) Global optimization, Lecture notes in computer science, vol 350. Springer, Berlin

Tsui K (1992) An overview of Taguchi method and newly developed statistical methods for robust design. IIE Trans 24:44–57CrossRef

Ursem RK (1999) Multinational evolutionary algorithms. In: Proceedings of the 1999 congress on evolutionary computation (CEC 1999). IEEE Press, Piscataway NJ, pp 1633–1640

Whitley D, Mathias KE, Rana SB, Dzubera J (1996) Evaluating evolutionary algorithms. Artif Intell 85(1–2):245–276CrossRef

Wright S (1931) Evolution in Mendelian populations. Genetics 16:97–159

Yin X, Germany N (1993) A fast genetic algorithm with sharing using cluster analysis methods in multimodal function optimization. In: Proceedings of the international conference on artificial neural nets and genetic algorithms, Innsbruck. Austria, 1993, Springer, pp 450–457

Titel: Niching in Evolutionary Algorithms
verfasst von: Ofer M. Shir
Verlag: Springer Berlin Heidelberg
Buch: Handbook of Natural Computing
Print ISBN: 978-3-540-92909-3

Electronic ISBN: 978-3-540-92910-9

Copyright-Jahr: 2012
DOI: https://doi.org/10.1007/978-3-540-92910-9_32

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"