Abstract
The issue of setting the values of various parameters of an evolutionary algorithm (EA) is crucial for good performance. One way to do it is by controlling EA parameters on-the-fly, which can be done in various ways and for various parameters. We briefly review these options in general and present the findings of a literature search and some statistics about themost popular options. Thereafter, we provide three case studies indicating a high potential for uncommon variants. In particular, we recommend focusing on parameters regulating selection and population size, rather than those concerning crossover and mutation. On the technical side, the case study on adjusting tournament size shows by example that global parameters can also be selfadapted, and that heuristic adaptation and pure self-adaptation can be successfully combined into a hybrid of the two.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Genetic Algorithm
- Population Size
- Mutation Rate
- Evolutionary Computation
- Constraint Satisfaction Problem
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
P.J. Angeline. Adaptive and self-adaptive evolutionary computations. In Computational Intelligence, pages 152–161. IEEE Press, 1995
J. Arabas, Z. Michalewicz, and J. Mulawka. GAVaPS – a genetic algorithm with varying population size. In Proceedings of the First IEEE Conference on Evolutionary Computation, pages 73–78. IEEE Press, Piscataway, NJ, 1994
D.V. Arnold. Evolution strategies with adaptively rescaled mutation vectors. In 2005 Congress on Evolutionary Computation (CEC’2005), pages 2592–2599. IEEE Press, Piscataway, NJ, 2005
T. Bäck. The interaction of mutation rate, selection, and self-adaptation within a genetic algorithm. In Männer and Manderick [40], pages 85–94
T. Bäck. Self adaptation in genetic algorithms. In F.J. Varela and P. Bourgine, editors, Toward a Practice of Autonomous Systems: Proceedings of the 1st European Conference on Artificial Life, pages 263–271. MIT Press, Cambridge, MA, 1992
T. Bäck. Self-adaptation. In T. Bäck, D.B. Fogel, and Z. Michalewicz, editors, Evolutionary Computation 2: Advanced Algorithms and Operators, Chapter 21, pages 188–211. Institute of Physics Publishing, Bristol, 2000
T. Bäck, A.E. Eiben, and N.A.L. van der Vaart. An empirical study on GAs “without parameters”. In Schoenauer et al. [46], pages 315–324
T. Bäck and Z. Michalewicz. Test landscapes. In T. Bäck, D.B. Fogel, and Z. Michalewicz, editors, Handbook of Evolutionary Computation, Chapter B2.7, pages 14–20. Institute of Physics Publishing, Bristol, and Oxford University Press, New York, 1997
Th. Bäck and M. Schütz. Intelligent mutation rate control in canonical genetic algorithms. In Zbigniew W. Ras and Maciej Michalewicz, editors, Foundations of Intelligent Systems, 9th International Symposium, ISMIS ’96, Zakopane, Poland, June 9-13, 1996, Proceedings, volume 1079 of Lecture Notes in Computer Science, pages 158–167. Springer, Berlin, Heidelberg, New York, 1996
Y. Davidor, H.-P. Schwefel, and R. Männer, editors. Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, number 866 in Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, New York, 1994
L. Davis. Adapting operator probabilities in genetic algorithms. In J.D. Schaffer, editor, Proceedings of the 3rd International Conference on Genetic Algorithms, pages 61–69. Morgan Kaufmann, San Francisco, 1989
A.E. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel, editors. Proceedings of the 5th Conference on Parallel Problem Solving from Nature, number 1498 in Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, New York, 1998
A.E. Eiben, R. Hinterding, and Z. Michalewicz. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 3(2):124–141, 1999.
A.E. Eiben and M. Jelasity. A critical note on experimental research methodology in EC. In Proceedings of the 2002 Congress on Evolutionary Computation (CEC’2002), pages 582–587. IEEE Press, Piscataway, NJ, 2002
A.E. Eiben, E. Marchiori, and V.A. Valko. Evolutionary algorithms with on-the-fly population size adjustment. In X. Yao et al., editor, Parallel Problem Solving from Nature, PPSN VIII, number 3242 in Lecture Notes in Computer Science, pages 41–50. Springer, Berlin, Heidelberg, New York, 2004
A.E. Eiben, Z. Michalewicz, M. Schoenauer, and J.E. Smith. Parameter Control in Evolutionary Algorithms. In Lobo, Fernando G., Lima, Cláudio F. and Michalewicz, Zbigniew, editors, Parameter Setting in Evolutionary Algorithms, Studies in Computational Intelligence. Springer, 2007, pages 19–46
A.E. Eiben, M.C. Schut, and A.R. deWilde. Boosting genetic algorithms with (self-) adaptive selection. In Proceedings of the IEEE Conference on Evolutionary Computation, 2006, pages 1584–1589
A.E. Eiben and J.E. Smith. Introduction to Evolutionary Computing. Springer, Berlin, Heidelberg, New York, 2003
R. Eriksson and B. Olsson. On the performance of evolutionary algorithms with life-time adaptation in dynamic fitness landscapes. In 2004 Congress on Evolutionary Computation (CEC’2004), pages 1293–1300. IEEE Press, Piscataway, NJ, 2004
L.J. Eshelman, editor. Proceedings of the 6th International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco, 1995
H.-G. Beyer et al., editor. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005). ACM, 2005
C. Fernandes and A. Rosa. Self-regulated population size in evolutionary algorithms. In Th.-P. Runarsson, H.-G. Beyer, E. Burke, J.-J. Merelo-Guervos, L. Darell Whitley, and X. Yao, editors, Parallel Problem Solving from Nature – PPSN IX, number 4193 in Lecture Notes in Computer Science, pages 920–929. Springer, Berlin, Heidelberg, New York, 2006
D.B. Fogel. Evolutionary Computation. IEEE Press, 1995
A.S. Fukunga. Restart scheduling for genetic algorithms. In Eiben et al. [12], pages 357–366
M. Gorges-Schleuter. A comparative study of global and local selection in evolution strategies. In Eiben et al. [12], pages 367–377
J. Gottlieb and N. Voss. Adaptive fitness functions for the satisfiability problem. In Schoenauer et al. [46], pages 621–630
Georges R. Harik and Fernando G. Lobo. A parameter-less genetic algorithm. In Wolfgang Banzhaf et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference, volume 1, pages 258–265. Morgan Kaufmann, 1999
I. Harvey. The saga-cross: the mechanics of recombination for species with variable-length genotypes. In Männer and Manderick [40], pages 269–278
R. Hinterding, Z. Michalewicz, and T.C. Peachey. Self-adaptive genetic algorithm for numeric functions. In Voigt et al. [58], pages 420–429
C.W. Ho, K.H. Lee, and K.S. Leung. A genetic algorithm based on mutation and crossover with adaptive probabilities. In 1999 Congress on Evolutionary Computation (CEC’1999), pages 768–775. IEEE Press, Piscataway, NJ, 1999
T. Jansen. On the analysis of dynamic restart strategies for evolutionary algorithms. In J.J. Merelo Guervos, P. Adamidis, H.-G. Beyer, J.-L. Fernandez-Villacanas, and H.-P. Schwefel, editors, Proceedings of the 7th Conference on Parallel Problem Solving from Nature, number 2439 in Lecture Notes in Computer Science, pages 33–43. Springer, Berlin, Heidelberg, New York, 2002
B.A. Julstrom. What have you done for me lately?: Adapting operator probabilities in a steady-state genetic algorithm. In Eshelman [20], pages 81–87
Y. Katada, K. Okhura, and K. Ueda. An approach to evolutionary robotics using a genetic algorithm with a variable mutation rate strategy. In Yao et al. [61], pages 952–961
S. Kazarlis and V. Petridis. Varying fitness functions in genetic algorithms: studying the rate of increase of the dynamics penalty terms. In Eiben et al. [12], pages 211–220
N. Krasnogor and J.E. Smith. Emergence of profitable search strategies based on a simple inheritance mechanism. In Spector et al. [55], pages 432–439
C.-Y. Lee and E.K. Antonsson. Adaptive evolvability via non-coding segment induced linkage. In Spector et al. [55], pages 448–453
M. Lee and H. Takagi. Dynamic control of genetic algorithms using fuzzy logic techniques. In S. Forrest, editor, Proceedings of the 5th International Conference on Genetic Algorithms, pages 76–83. Morgan Kaufmann, San Francisco, 1993
J. Lis. Parallel genetic algorithm with dynamic control parameter. In Proceedings of the 1996 IEEE Conference on Evolutionary Computation, pages 324–329. IEEE Press, Piscataway, NJ, 1996
H. Lu and G.G. Yen. Dynamic population size in multiobjective evolutionary algorithm. In 2002 Congress on Evolutionary Computation (CEC’2002), pages 1648–1653. IEEE Press, Piscataway, NJ, 2002
R. Männer and B. Manderick, editors. Proceedings of the 2nd Conference on Parallel Problem Solving from Nature. North-Holland, Amsterdam, 1992
K.E. Mathias, J.D. Schaffer, L.J. Eshelman, and M. Mani. The effects of control parameters and restarts on search stagnation in evolutionary programming. In Eiben et al. [12], pages 398–407
Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin, Heidelberg, New York, 3rd edition, 1996
C.L. Ramsey, K.A. de Jong, J.J. Grefenstette, A.S. Wu, and D.S. Burke. Genome length as an evolutionary self-adaptation. In Eiben et al. [12], pages 345–353
C. Reis, J.A. Tenreiro Machado and J. Boaventura Cunha. Fractional dynamic fitness functions for ga-based circuit design. In Beyer et al. [12], pages 1571–1572
D. Schlierkamp-Voosen and H. Mühlenbein. Strategy adaptation by competing subpopulations. In Davidor et al. [21], pages 199–209
M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J.J. Merelo, and H.-P. Schwefel, editors. Proceedings of the 6th Conference on Parallel Problem Solving from Nature, number 1917 in Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, New York, 2000
H.-P. Schwefel. Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie, volume 26 of ISR. Birkhaeuser, Basel/Stuttgart, 1977
I. Sekaj. Robust parallel genetic algorithms with re-initialisation. In Yao et al. [61], pages 411–419
J.E. Smith. Self Adaptation in Evolutionary Algorithms. PhD Thesis, University of the West of England, Bristol, UK, 1998
J.E. Smith and T.C. Fogarty. Adaptively parameterised evolutionary systems: Self adaptive recombination and mutation in a genetic algorithm. In Voigt et al. [58], pages 441–450
J.E. Smith and T.C. Fogarty. Operator and parameter adaptation in genetic algorithms. Soft Computing, 1(2):81–87, 1997
R.E. Smith and E. Smuda. Adaptively resizing populations: Algorithm, analysis and first results. Complex Systems, 9(1):47–72, 1995
W.M. Spears. Adapting crossover in evolutionary algorithms. In J.R. McDonnell, R.G. Reynolds, and D.B. Fogel, editors, Proceedings of the 4th Annual Conference on Evolutionary Programming, pages 367–384. MIT Press, Cambridge, MA, 1995
W.M. Spears. Evolutionary Algorithms: the Role of Mutation and Recombination. Springer, Berlin, Heidelberg, New York, 2000
L. Spector, E. Goodman, A. Wu, W.B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, editors. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). Morgan Kaufmann, San Francisco, 2001
H. Stringer and A.S. Wu. Behavior of finite population variable length genetic algorithms under random selection. In Beyer et al. [21], pages 1249–1255
K. Vekaria and C. Clack. Biases introduced by adaptive recombination operators. In W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela, and R.E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), pages 670–677. Morgan Kaufmann, San Francisco, 1999
H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, editors. Proceedings of the 4th Conference on Parallel Problem Solving from Nature, number 1141 in Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, New York, 1996
T. White and F. Oppacher. Adaptive crossover using automata. In Davidor et al. [10], pages 229–238
D. Whitley, K. Mathias, S. Rana, and J. Dzubera. Building better test functions. In Eshelman [20], pages 239–246
X. Yao, E. Burke, J.A. Lozano, J. Smith, J.-J. Merelo-Guervos, J.A. Bullinaria, J. Rowe, P. Tino, A. Kaban, and H.-P. Schwefel, editors. Parallel Problem Solving from Nature – PPSN-VIII, number 3242 in Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, New York, 2004
J. Zhang, S.H. Chung, and J. Zhong. Adaptive crossover and mutation in genetic algorithms based on clustering technique. In Beyer et al. [21], pages 1577–1578
J. Costa, R. Tavares, and A. Rosa. An experimental study on dynamic random variation of population size. In Proc. IEEE Systems, Man and Cybernetics Conf., volume 6, pages 607–612, Tokyo, 1999. IEEE Press
S. Forrest, editor. Proceedings of the 5th International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco, 1993
D.E. Goldberg. Optimal population size for binary-coded genetic algorithms. TCGA Report No. 85001, 1985
D.E. Goldberg. Sizing populations for serial and parallel genetic algorithms. In J.D. Schaffer, editor, Proceedings of the 3rd International Conference on Genetic Algorithms, pages 70–79. Morgan Kaufmann, San Francisco, 1989
D.E. Goldberg, K. Deb, and J.H. Clark. Genetic Algorithms, Noise, and the Sizing of Populations. IlliGAL Report No. 91010, 1991
N. Hansen, A. Gawelczyk, and A. Ostermeier. Sizing the population with respect to the local progress in (1,λ)-evolution strategies – a theoretical analysis. In Proceedings of the 1995 IEEE Conference on Evolutionary Computation, pages 80–85. IEEE Press, Piscataway, NJ, 1995
F.G. Lobo. The parameter-less Genetic Algorithm: rational and automated parameter selection for simplified Genetic Algorithm operation. PhD Thesis, Universidade de Lisboa, 2000
C.R. Reeves. Using genetic algorithms with small populations. In Forrest [64], pages 92–99
J. Roughgarden. Theory of Population Genetics and Evolutionary Ecology. Prentice-Hall, 1979
D. Schlierkamp-Voosen and H. Mühlenbein. Adaptation of population sizes by competing subpopulations. In Proceedings of the 1996 IEEE Conference on Evolutionary Computation. IEEE Press, Piscataway, NJ, 1996
R.E. Smith. Adaptively resizing populations: An algorithm and analysis. In Forrest [64]
R.E. Smith. Population Sizing, pages 134–141. Institute of Physics Publishing, 2000
J. Song and J. Yu. Population System Control. Springer, 1988
V.A. Valkó. Self-calibrating evolutionary algorithms: Adaptive population size. Master’s Thesis, Free University Amsterdam, 2003
B. Craenen and A.E. Eiben. Stepwise adaptation of weights with refinement and decay on constraint satisfaction problems. In L. Spector, E. Goodman, A. Wu, W.B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference, pages 291–298. Morgan Kaufmann, 2001
B. Craenen, A.E. Eiben, and J.I. van Hemert. Comparing evolutionary algorithms on binary constraint satisfaction problems. IEEE Transactions on Evolutionary Computation, 7(5):424–444, 2003
J. Eggermont, A.E. Eiben, and J.I. van Hemert. Adapting the fitness function in GP for data mining. In R. Poli, P. Nordin, W.B. Langdon, and T.C. Fogarty, editors, Genetic Programming, Proceedings of EuroGP’99, Volume 1598 of LNCS, pages 195–204. Springer-Verlag, 1999
A.E. Eiben, B. Jansen, Z. Michalewicz, and B. Paechter. Solving CSPs using self-adaptive constraint weights: how to prevent EAs from cheating. In D. Whitley, D. Goldberg, E. Cantu-Paz, L. Spector, I. Parmee, and H.-G. Beyer, editors, Proceedings of the Genetic and Evolutionary Computation Conference, pages 128–134. Morgan Kaufmann, 2000
A.E. Eiben and J.I. van Hemert. SAW-ing EAs: adapting the fitness function for solving constrained problems. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, Chapter 26, pages 389–402. McGraw-Hill, London, 1999
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Eiben, G., Schut, M. (2007). New Ways to Calibrate Evolutionary Algorithms. In: Siarry, P., Michalewicz, Z. (eds) Advances in Metaheuristics for Hard Optimization. Natural Computing Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72960-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-72960-0_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72959-4
Online ISBN: 978-3-540-72960-0
eBook Packages: Computer ScienceComputer Science (R0)