nach oben

Evolutionary Intelligence

Erschienen in:

01.08.2010 | Review Article

Evolutionary self-adaptation: a survey of operators and strategy parameters

verfasst von: Oliver Kramer

Erschienen in: Evolutionary Intelligence | Ausgabe 2/2010

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The success of evolutionary search depends on adequate parameter settings. Ill conditioned strategy parameters decrease the success probabilities of genetic operators. Proper settings may change during the optimization process. The question arises if adequate settings can be found automatically during the optimization process. Evolution strategies gave an answer to the online parameter control problem decades ago: self-adaptation. Self-adaptation is the implicit search in the space of strategy parameters. The self-adaptive control of mutation strengths in evolution strategies turned out to be exceptionally successful. Nevertheless, for years self-adaptation has not achieved the attention it deserves. This paper is a survey of self-adaptive parameter control in evolutionary computation. It classifies self-adaptation in the taxonomy of parameter setting techniques, gives an overview of automatic online-controllable evolutionary operators and provides a coherent view on search techniques in the space of strategy parameters. Beyer and Sendhoff’s covariance matrix self-adaptation evolution strategy is reviewed as a successful example for self-adaptation and exemplarily tested for various concepts that are discussed.

Nächster Artikel Multi-stage fuzzy evaluation in evolutionary robot vision for face detection

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

Typically, genetic operators are crossover/recombination, mutation, inversion, gene deletion and duplication.

According to a tradition in ES, μ is the size of the parental population, while λ is the size of the offspring population.

Originally, σ denotes step sizes in ES. We use this symbol for all kinds of strategy variables in this paper.

The concept of global multi-recombination will be explained in Sect. 4.2.

For log-normal mutation of step sizes, see Sect. 4.1.2.

The index j denotes the index of the j-th ranked individual of the λ offspring individuals with regard to fitness f(x _j).

The Sphere problem is the continuous optimization problem to find an \({\bf x} \in {\mathbb{R}}^N\) minimizing \(f({\bf x}):=\sum_{i=1}^{N} x_{i}^{2}.\)

Optimal progress is problem-dependent and can be stated theoretically on artificial functions [12].

The success probability p _s of an evolutionary operator is the relation of solutions with better fitness than the original solution f(x) and all generated solutions.

OneMax is a pseudo-binary function. For a bit string \({\bf x} {\in}\{0,1\}^N\), maximize \(f({\bf x}):=\sum_{i=1}^{N}x_i \quad\hbox{ with } {\bf x} \in \{0,1\}^N\) optimum x ^* = (1, ..., 1) with f(x ^*) = N.

3-SAT is a propositional satisfiability problem, each clause contains k = 3 literals; we randomly generate formulas with N = 50 variables and 150 clauses; the fitness function is: \({\frac{\#\hbox{of true clauses}} {\#\hbox{of all clauses}}}.\)

Schwefel’s problem 2.40 [69]: Minimize f(x): = − ∑ _i=1 ⁵ x _i, constraints \(g_{j}({\bf x}):=x_{j} {\geq}0, \hbox{for } j=1,\ldots,5\) and \(g_{j}({\bf x})=-\sum\nolimits^{5}_{i=1}(9+i)x_{i}+50000 {\geq}0, \hbox{for } j=6\), minimum x ^* = (5000, 0, 0, 0, 0)^T with f(x ^*) = − 5000.

TR (tangent problem): minimize \(f({\bf x}):=\sum_{i=1}^{N} x_{i}^{2}\), constraints \(g({\bf x}):=\sum_{i=1}^{N} x_{i}-t>0, \qquad t \in {\mathbb{R}} \qquad \hbox{(tangent)},\) for N=k and t=k the minimum lies at: \({\bf x}^{*}=(1,\ldots,1)^{T},\hbox{with }\quad f({\bf x}^{*})=k\), TR2 means N = 2 and t = 2.

difference between the optimum and the best solution \(|f({\bf x}^{*})-f({\bf x}^{best})|.\)

Low innovation rates are caused by variation operators that produce offspring not far away from their parents, e.g. by low mutation rates.

Angeline PJ (1995) Adaptive and self-adaptive evolutionary computations. In: Palaniswami M, Attikiouzel Y (eds) Computational intelligence a dynamic systems perspective. IEEE Press, New York, pp 152–163

Arnold DV, Brauer D (2008) On the behaviour of the (1+1)-ES for a simple constrained problem. In: Proceedings of the 10th conference on parallel problem solving from nature—PPSN X, pp 1–10

Auger A (2003) Convergence results for (1, λ)-SA-ES using the theory of ϕ-irreducible markov chains. In: Proceedings of the evolutionary algorithms workshop of the 30th international colloquium on automata, languages and programming

Bäck T (1998) An overview of parameter control methods by self-adaption in evolutionary algorithms. Fundam Inf 35(1–4):51–66MATH

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

Bartz-Beielstein T, Lasarczyk C, Preu M (2005) Sequential parameter optimization. In: McKay B, et al (eds) Proceedings of the IEEE congress on evolutionary computation—CEC, vol 1. IEEE Press, pp 773–780

Bartz-Beielstein T, Preuss M (2006) Considerations of budget allocation for sequential parameter optimization (SPO). In: Paquete L, et al. (eds) Workshop on empirical methods for the analysis of algorithms, proceedings, Reykjavik, Iceland, pp 35–40

Bäck T (1991) Self-adaptation in genetic algorithms. In: Proceedings of the 1st European conference on artificial life—ECAL, pp 263–271

Bäck T (1992) The interaction of mutation rate, selection, and self-adaptation within a genetic algorithm. In: Proceedings of the 2nd conference on parallel problem solving from nature—PPSN II, pp 85–94

10.

Bäck T, Schütz M (1996) Intelligent mutation rate control in canonical genetic algorithms. In: Foundation of intelligent systems, 9th international symposium, ISMIS ’96. Springer, pp 158–167

11.

Berlik S (2004) A step size preserving directed mutation operator. In: Proceedings of the 6th conference on genetic and evolutionary computation—GECCO, pp 786–787

12.

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

13.

Beyer H-G, Deb K (2001) On self-adaptive features in real-parameter evolutionary algorithms. IEEE Trans Evol Comput 5(3):250–270CrossRef

14.

Beyer H-G, Meyer-Nieberg S (2006) Self-adaptation on the ridge function class: first results for the sharp ridge. In: Proceedings of the 9th conference on parallel problem solving from nature—PPSN IX, pp 72–81

15.

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

16.

Beyer HG, Sendhoff B (2008) Covariance matrix adaptation revisited—the cmsa evolution strategy. In: Proceedings of the 10th conference on parallel problem solving from nature—PPSN X, pp 123–132

17.

Coello CA (2000) Use of a self-adaptive penalty approach for engineering optimization problems. Comput Ind 41(2):113–127CrossRef

18.

Davis L (1989) Adapting operator probabilities in genetic algorithms. In: Proceedings of the 3rd international conference on genetic algorithms, San Francisco, Morgan Kaufmann Publishers Inc, pp 61–69

19.

de Landgraaf W, Eiben A, Nannen V (2007) Parameter calibration using meta-algorithms. In: Proceedings of the IEEE congress on evolutionary computation—CEC, pp 71–78

20.

DeJong K (2007) Parameter setting in EAs: a 30 year perspective. In: Parameter setting in evolutionary algorithms, studies in computational intelligence. Springer, pp 1–18

21.

Eiben A, Schut MC, de Wilde A (2006) Is self-adaptation of selection pressure and population size possible? A case study. In: Proceedings of the 9th conference on parallel problem solving from nature—PPSN IX, pp 900–909

22.

Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124–141CrossRef

23.

Eiben AE, Michalewicz Z, Schoenauer M, Smith JE (2007) Parameter control in evolutionary algorithms. In: Parameter setting in evolutionary algorithms, studies in computational intelligence. Springer, pp 19–46

24.

Fogarty TC (1989) Varying the probability of mutation in the genetic algorithm. In: Proceedings of the 3rd international conference on genetic algorithms, San Francisco, Morgan Kaufmann Publishers Inc, pp 104–109

25.

Fogel DB, Fogel LJ, Atma JW (1991) Meta-evolutionary programming. In: Proceedings of 25th asilomar conference on signals, systems & computers, pp 540–545

26.

georg Beyer H, Arnold DV (2003) Qualms regarding the optimality of cumulative path length control in csa/cma-evolution strategies. Evol Comput 11

27.

Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison Wesley, ReadingMATH

28.

Grefenstette J (1986) Optimization of control parameters for genetic algorithms. IEEE Trans Syst Man Cybern 16(1):122–128CrossRef

29.

Hansen N (2006) An analysis of mutative sigma self-adaptation on linear fitness functions. Evol Comput 14(3):255–275CrossRef

30.

Harik GR, Goldberg DE (1997) Learning linkage. In: Foundations of genetic algorithms 4. Morgan Kaufmann, pp 247–262

31.

Harik GR, Lobo FG, Sastry K (2006) Linkage learning via probabilistic modeling in the extended compact genetic algorithm (ECGA). In: Scalable optimization via probabilistic modeling, studies in computational intelligence, Springer, pp 39–61

32.

Herdy M (1992) Reproductive isolation as strategy parameter in hierarchically organized evolution strategies. In: Proceedings of the 10th conference on parallel problem solving from nature—PPSN II, pp 207–217

33.

Hesser J, Männer R (1990) Towards an optimal mutation probability for genetic algorithms. In: Proceedings of the 10th conference on parallel problem solving from nature—PPSN I, London, UK, Springer-Verlag, pp 23–32

34.

Hesser J, Männer R (1992) Investigation of the m-heuristic for optimal mutation probabilities. In PPSN, pp 115–124

35.

Hildebrand L (2002) Asymmetrische evolutionsstrategien. PhD thesis, University of Dortmund

36.

Holland JH (1992) Adaptation in natural and artificial systems, 1st edn, MIT Press, Cambridge

37.

Jägersknpper J (2005) Rigorous runtime analysis of the (1+1) es: 1/5-rule and ellipsoidal fitness landscapes. In: Proceedings of the workshop on foundation of genetic algorithms FOGA, pp 260–281

38.

Jägersknpper J (2006) Probabilistic runtime analysis of (1 + λ)es using isotropic mutations. In: Proceedings of the 8th conference on genetic and evolutionary computation—GECCO, New York, ACM, pp 461–468

39.

Joines J, Houck C (1994) On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GAs. In: Fogel DB (eds) Proceedings of the 1st IEEE conference on evolutionary computation, Orlando, Florida, IEEE Press, pp 579–584

40.

Jong KAD (1975) An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan

41.

Koumoutsakos P, Muller SD (2006) Flow optimization using stochastic algorithms. Lecture Notes Control Inf Sci 330:213–229CrossRef

42.

Kramer O (2008) Premature convergence in constrained continuous search spaces. In: Proceedings of the 10th conference on parallel problem solving from nature—PPSN X, Berlin, Springer, to appear

43.

Kramer O (2008) Self-adaptive inversion mutation for combinatorial representations. In: Proceedings of the 2008 international conference on genetic and evolutionary methods, to appear

44.

Kramer O, Barthelmes A, Rudolph G (2009) Surrogate constraint functions for cma evolution strategies. In: Proceedings of the conference on artificial intelligence and automation, page to appear

45.

Kramer O, Koch P (2007) Self-adaptive partially mapped crossover. In: Proceedings of the 9th conference on genetic and evolutionary computation—GECCO, New York, ACM Press, pp 1523–1523

46.

Kramer O, Ting CK, Büning HK (2005) A new mutation operator for evolution strategies for constrained problems. In: Proceedings of the IEEE congress on evolutionary computation—CEC, pp 2600–2606

47.

Kursawe F (1999) Grundlegende empirische Untersuchungen der Parameter von Evolutionsstrategien—Metastrategien. PhD thesis, University of Dortmund

48.

Liang KH, Yao X, Liu Y, Newton CS, Hoffman D (1998) An experimental investigation of self-adaptation in evolutionary programming. In: Proceedings of the 7th international conference on evolutionary programming VII—EP, Berlin, Springer, pp 291–300

49.

Maruo MH, Lopes HS, Delgado MR (2005) Self-adapting evolutionary parameters: encoding aspects for combinatorial optimization problems. In: Proceedings of EvoCOP, pp 154–165

50.

Mercer RE, Sampson JR (1978) Adaptive search using a reproductive metaplan. Kybernetes 7:215–228CrossRef

51.

Mersch B, Glasmachers T, Meinicke P, Igel C (2006) Evolutionary optimization of sequence kernels for detection of bacterial gene starts. In: ICANN (2), pp 827–836

52.

Meyer-Nieberg S, Beyer HG (2007) Self-adaptation in evolutionary algorithms. In: Lobo FG, Lima CF, Michalewicz Z (eds) Parameter setting in evolutionary algorithms. Springer, Berlin

53.

Mezura-Montes E, Palomeque-Ortiz AG (2009) Self-adaptive and deterministic parameter control in differential evolution for constrained optimization. Constraint-Handl Evol Optim 189:95–120CrossRef

54.

Mühlenbein H (1992) How genetic algorithms really work: mutation and hillclimbing. In: Proceedings of the 2nd conference on parallel problem solving from nature—PPSN II, pp 15–26

55.

Nannen V, Eiben A (2006) A method for parameter calibration and relevance estimation in evolutionary algorithms. In: Proceedings of the 8th conference on genetic and evolutionary computation—GECCO, New York, ACM Press, pp 183–190

56.

Nannen V, Eiben A (2007) Relevance estimation and value calibration of evolutionary algorithm parameters. In: IJCAI, pp 975–980

57.

Ostermeier A, Gawelczyk A, Hansen N (1994) A derandomized approach to self adaptation of evolution strategies. Evol Comput 2(4):369–380CrossRef

58.

Ostermeier A, Gawelczyk A, Hansen N (1995) A derandomized approach to self adaptation of evolution strategies. Evol Comput 2(4):369–380CrossRef

59.

Preuss M, Bartz-Beielstein T (2007) Sequential parameter optimization applied to self-adaptation for binary-coded evolutionary algorithms. In: Parameter setting in evolutionary algorithms, studies in computational intelligence. Springer, pp 91–119

60.

Rechenberg I (1973) Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, Stuttgart

61.

Rechenberg I (1994) Evolutionsstrategie ’94. Frommann-Holzboog, Stuttgart

62.

Reed J, Toombs R, Barricelli NA (1967) Simulation of biological evolution and machine learning: I. selection of self-reproducing numeric patterns by data processing machines, effects of hereditary control, mutation type and crossing. J Theor Biol 17:319–342CrossRef

63.

Reinelt G (1991) Tsplib—a traveling salesman problem library. ORSA J Comput 3:376–384MATH

64.

Rosenberg RS (1967) Simulation of genetic populations with biochemical properties. PhD thesis, University of Michigan

65.

Rudolph G (2001) Self-adaptive mutations may lead to premature convergence. IEEE Trans Evol Comput 5(4):410–414CrossRef

66.

Schaffer JD, Caruana R, Eshelman LJ, Das R (1989) A study of control parameters affecting online performance of genetic algorithms for function optimization. In: Proceedings of the 3rd international conference on genetic algorithms—ICGA 1989, pp 51–60

67.

Schaffer JD, Morishima A (1987) An adaptive crossover distribution mechanism for genetic algorithms. In: Proceedings of the second international conference on genetic algorithms on genetic algorithms and their application, Hillsdale, NJ, USA, L. Erlbaum Associates Inc, pp 36–40

68.

Schwefel H-P (1974) Adaptive Mechanismen in der biologischen Evolution und ihr Einflus auf die Evolutionsgeschwindigkeit. Interner Bericht der Arbeitsgruppe Bionik und Evolutionstechnik am Institut fnr Mess- und Regelungstechnik, TU Berlin

69.

Schwefel HP (1995) Evolution and Optimum Seeking. Sixth-generation computer technology. Wiley Interscience, New York

70.

Semenov MA, Terkel DA (2003) Analysis of convergence of an evolutionary algorithm with self-adaptation using a stochastic lyapunov function. Evol Comput 11(4):363–379CrossRef

71.

Smith J (2001) Modelling GAs with self adaptive mutation rates. In: Proceedings of the genetic and evolutionary computation conference, pp 599–606

72.

Smith J, Fogarty TC (1996) Recombination strategy adaptation via evolution of gene linkage. In: Proceedings of the IEEE congress on evolutionary computation—CEC, pp 826–831

73.

Smith J, Fogarty TC (1996) Self adaptation of mutation rates in a steady state genetic algorithm. In: Proceedings of the international conference on evolutionary computation—ICEC, pp 318–323

74.

Spears WM (1995) Adapting crossover in evolutionary algorithms. In: McDonnell JR, Reynolds RG, Fogel DB (eds) Proceedings of the fourth annual conference on evolutionary programming, Cambridge, MIT Press, pp 367–384

75.

Stone C, Smith J (2002) Strategy parameter variety in self-adaptation of mutation rates. In: Proceedings of the genetic and evolutionary computation conference—GECCO, San Francisco, Morgan Kaufmann Publishers Inc, pp 586–593

76.

Weinberg R (1970) Computer simulation of a living cell. PhD thesis, University of Michigan

Titel: Evolutionary self-adaptation: a survey of operators and strategy parameters
verfasst von: Oliver Kramer
Publikationsdatum: 01.08.2010
Verlag: Springer-Verlag
Erschienen in: Evolutionary Intelligence / Ausgabe 2/2010
Print ISSN: 1864-5909
Elektronische ISSN: 1864-5917
DOI: https://doi.org/10.1007/s12065-010-0035-y

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"

Premium Partner