Beyer, Hans-Georg Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practise. (English) Zbl 1064.90574 Comput. Methods Appl. Mech. Eng. 186, No. 2-4, 239-267 (2000). Summary: This paper is devoted to the effects of fitness noise in evolutionary algorithms (EAs). After a short introduction to the history of this research field, the performance of genetic algorithms (GAs) and evolution strategies (ESs) on the hyper-sphere test function is evaluated. It will be shown that the main effects of noise – the decrease of convergence velocity and the residual location error \(R_\infty\) – are observed in both GAs and ESs.Different methods for improving the performance are presented and hypotheses on their working mechanisms are discussed. The method of rescaled mutations is analyzed in depth for the \((1,\lambda)\)-ES on the sphere model. It is shown that this method needs advanced self-adaptation (SA) techniques in order to take advantage of the theoretically predicted performance gain. The troubles with current self-adaptation techniques are discussed and directions for further research will be worked out. Cited in 19 Documents MSC: 90C59 Approximation methods and heuristics in mathematical programming Keywords:Evolutionary algorithms (GA, ES, EP); Noisy fitness data; Convergence properties; Optimization under noise; Convergence improvement techniques; Self-adaptation PDFBibTeX XMLCite \textit{H.-G. Beyer}, Comput. Methods Appl. Mech. Eng. 186, No. 2--4, 239--267 (2000; Zbl 1064.90574) Full Text: DOI References: [1] Rechenberg, I., Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (1973), Frommann-Holzboog: Frommann-Holzboog Stuttgart [2] Beyer, H.-G., Toward a theory of evolution strategies: some asymptotical results from the \((1,^+λ)\)-theory, Evolutionary Computation, 1, 2, 165-188 (1993) [3] J.M. Fitzpatrick, J.J. Grefenstette, Genetic algorithms in noisy environments, in: P. Langley (Ed.), Machine Learning: Special Issue on Genetic Algorithms, vol. 3, Kluwer Academic Publishers, Dordrecht, 1988, pp. 101-120; J.M. Fitzpatrick, J.J. Grefenstette, Genetic algorithms in noisy environments, in: P. Langley (Ed.), Machine Learning: Special Issue on Genetic Algorithms, vol. 3, Kluwer Academic Publishers, Dordrecht, 1988, pp. 101-120 [4] U. Hammel, T. Bäck, Evolution strategies on noisy functions. How to improve convergence properties, in: Y. Davidor, R. Männer, H.-P. Schwefel (Ed.), Parallel Problem Solving from Nature, vol. 3, Springer, Heidelberg, 1994, pp. 159-168; U. Hammel, T. Bäck, Evolution strategies on noisy functions. How to improve convergence properties, in: Y. Davidor, R. Männer, H.-P. Schwefel (Ed.), Parallel Problem Solving from Nature, vol. 3, Springer, Heidelberg, 1994, pp. 159-168 [5] Bäck, T.; Hammel, U., Evolution strategies applied to perturbed objective functions, (Michalewicz, Z.; Schaffer, J. D.; Schwefel, H.-P.; Fogel, D. B.; Kitano, H., Proceedings of the First IEEE Conference on Evolutionary Computation (1994), IEEE Press: IEEE Press Piscataway, NJ), 40-45 [6] Angeline, P. J., The effects of noise on self-adaptive evolutionary optimization, (Fogel, L. J.; Angeline, P. J.; Bäck, T., Proceedings of the Fifth Annual Conference on Evolutionary Programming (1996), The MIT Press: The MIT Press Cambridge, MA), 432-439 [7] Fogel, D. B., Evolutionary Computation (1995), IEEE Press: IEEE Press New York · Zbl 0944.68061 [8] Levitan, B.; Kauffman, S., Adaptive walks with noisy fitness measurements, Molecular Diversity, 1, 1, 53-68 (1995) [9] S. Rana, L.D. Whitley, R. Cogswell, Searching in the presence of noise, in: H.-M. Voigt, W. Ebeling, I. Rechenberg, H.-P. Schwefel (Eds.), Parallel Problem Solving from Nature, vol. 4, Springer, Heidelberg, 1996, pp. 198-207; S. Rana, L.D. Whitley, R. Cogswell, Searching in the presence of noise, in: H.-M. Voigt, W. Ebeling, I. Rechenberg, H.-P. Schwefel (Eds.), Parallel Problem Solving from Nature, vol. 4, Springer, Heidelberg, 1996, pp. 198-207 [10] Goldberg, D. E.; Rudnick, M. W., Genetic algorithms and the variance of fitness, Complex Systems, 5, 3, 265-278 (1991) · Zbl 0729.68075 [11] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison Wesley: Addison Wesley Reading, MA · Zbl 0721.68056 [12] Goldberg, D. E.; Deb, K.; Clark, J. H., Genetic algorithms, noise, and the sizing of populations, Complex Systems, 6, 4, 333-362 (1992) · Zbl 0800.68600 [13] G.R. Harik, E. Cantú-Paz, B.L. Miller, D.E. Goldberg, The Gambler’s ruin problem, genetic algorithms, and the sizing of populations, in: Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC ’97), Indianapolis, IN, IEEE Press, Piscataway, NJ, 1997, pp. 7-12; G.R. Harik, E. Cantú-Paz, B.L. Miller, D.E. Goldberg, The Gambler’s ruin problem, genetic algorithms, and the sizing of populations, in: Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC ’97), Indianapolis, IN, IEEE Press, Piscataway, NJ, 1997, pp. 7-12 [14] B.L. Miller, Noise, sampling, and efficient genetic algorithms, Ph.D. thesis, University of Illinois at Urbana-Champaign, Urbana, IL 61801, IlliGAL Report No. 97001, 1997; B.L. Miller, Noise, sampling, and efficient genetic algorithms, Ph.D. thesis, University of Illinois at Urbana-Champaign, Urbana, IL 61801, IlliGAL Report No. 97001, 1997 [15] Miller, B. L.; Goldberg, D. E., Genetic algorithms, selection schemes, and the varying effects of noise, Evolutionary Computation, 4, 2, 113-131 (1997) [16] L.M. Rattray, Modelling the dynamics of genetic algorithms using statistical mechanics, Ph.D. thesis, University of Manchester, CS Department, Manchester, UK, 1996; L.M. Rattray, Modelling the dynamics of genetic algorithms using statistical mechanics, Ph.D. thesis, University of Manchester, CS Department, Manchester, UK, 1996 [17] M. Rattray, J. Shapiro, Noisy fitness evaluation in genetic algorithms and the dynamics of learning, in: R.K. Belew, M.D. Vose (Eds.), Foundations of Genetic Algorithms, vol. 4, Morgan Kaufmann, San Mateo, CA, 1997; M. Rattray, J. Shapiro, Noisy fitness evaluation in genetic algorithms and the dynamics of learning, in: R.K. Belew, M.D. Vose (Eds.), Foundations of Genetic Algorithms, vol. 4, Morgan Kaufmann, San Mateo, CA, 1997 [18] Ackley, D. H., A Connectionist Machine for Genetic Hillclimbing (1987), Kluwer Academic Publishers: Kluwer Academic Publishers Boston [19] E.T. Jaynes, Where do we stand on maximum entropy? in: R.D. Levine, M. Tribus (Eds.), The Maximum Entropy Formalism, 1979, pp. 15-118; E.T. Jaynes, Where do we stand on maximum entropy? in: R.D. Levine, M. Tribus (Eds.), The Maximum Entropy Formalism, 1979, pp. 15-118 [20] Syswerda, G., Uniform crossover in genetic algorithms, (Schaffer, J. D., Proceedings of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 2-9 [21] Rechenberg, I., Evolutionsstrategien, (Schneider, B.; Ranft, U., Simulationsmethoden in der Medizin und Biologie (1978), Springer: Springer Berlin), 83-114 [22] Rechenberg, I., Evolutionsstrategie ’94 (1994), Frommann-Holzboog: Frommann-Holzboog Stuttgart [23] Schwefel, H.-P., Evolution and Optimum Seeking (1995), Wiley: Wiley New York, NY [24] Beyer, H.-G., Toward a theory of evolution strategies: Self-adaptation, Evolutionary Computation, 3, 3, 311-347 (1996) [25] Beyer, H.-G., Toward a theory of evolution strategies: The \((μ,λ)\)-theory, Evolutionary Computation, 2, 4, 381-407 (1995) [26] Bäck, T.; Schwefel, H.-P., An overview of evolutionary algorithms for parameter optimization, Evolutionary Computation, 1, 1, 1-23 (1993) [27] Beyer, H.-G., Toward a theory of evolution strategies: on the benefit of sex – the \((μ/μ,λ)\)-theory, Evolutionary Computation, 3, 1, 81-111 (1995) [28] Arnold, B. C.; Balakrishnan, N.; Nagaraja, H. N., A First Course in Order Statistics (1992), Wiley: Wiley New York · Zbl 0850.62008 [29] Beyer, H.-G., An alternative explanation for the manner in which genetic algorithms operate, BioSystems, 41, 1-15 (1997) [30] H.-P. Schwefel, Collective phenomena in evolutionary systems, in: P. Checkland, I. Kiss (Eds.), Problems of Constancy and Change - The Complementarity of Systems Approaches to Complexity, Papers presented at the 31st Annual Meeting of the International Society for General System Research, vol. 2, 1-5 June. International Society for General System Research, Budapest, 1987, pp. 1025-1033; H.-P. Schwefel, Collective phenomena in evolutionary systems, in: P. Checkland, I. Kiss (Eds.), Problems of Constancy and Change - The Complementarity of Systems Approaches to Complexity, Papers presented at the 31st Annual Meeting of the International Society for General System Research, vol. 2, 1-5 June. International Society for General System Research, Budapest, 1987, pp. 1025-1033 [31] H.-G. Beyer, Zur Analyse der Evolutionsstrategien, Habilitationsschrift, University of Dortmund, 1996; H.-G. Beyer, Zur Analyse der Evolutionsstrategien, Habilitationsschrift, University of Dortmund, 1996 [32] H.-G. Beyer, Mutate large but inherit small! On the analysis of rescaled mutations in \((1̃λ̃\); H.-G. Beyer, Mutate large but inherit small! On the analysis of rescaled mutations in \((1̃λ̃\) [33] H.-G. Beyer, Towards a theory of “Evolution Strategies”: progress rates and quality gain for \((1,+\); H.-G. Beyer, Towards a theory of “Evolution Strategies”: progress rates and quality gain for \((1,+\) [34] Blumer, M. G., The Mathematical Theory of Quantitative Genetics (1980), Clarendon Press: Clarendon Press Oxford This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.