Jump to content

Evolution strategy

From Wikipedia, the free encyclopedia

Evolution strategy (ES) from computer science is a subclass of evolutionary algorithms, which serves as an optimization technique.[1][2]

History

[edit]

The 'evolution strategy' optimization technique was created in the early 1960s and developed further in the 1970s and later by Ingo Rechenberg, Hans-Paul Schwefel and their co-workers.[2]

Timeline of ES - selected algorithms[2]
Year Description Reference
1973 ES introduced with mutation and selection [3]
1994 Derandomized self-adaptation ES - Derandomized scheme of mutative step size control is used [4]
1994 CSA-ES - usage information from the old generations [5]
2001 CMA-ES [6]
2006 Weighted multi-recombination ES - usage of weighted recombination [7]
2007 Meta-ES - incremental aggregation of partial semantic structures [8]
2008 Natural ES - usage of natural gradient [9]
2010 Exponential natural ES - a simpler version of natural ES [10]
2014 Limited memory CMA-ES - time–memory complexity reduction by covariance matrix decomposition [11]
2016 Fitness inheritance CMA-ES - fitness evaluation computational cost reduction using fitness inheritance [12]
2017 RS-CMSA ES - usage of subpopulations [13]
2017 MA-ES - COV update and COV matrix square root are not used [14]
2018 Weighted ES - weighted recombination of general convex quadratic functions [15]

Methods

[edit]

Evolution strategies use natural problem-dependent representations, so problem space and search space are identical. In common with evolutionary algorithms, the operators are applied in a loop. An iteration of the loop is called a generation. The sequence of generations is continued until a termination criterion is met.

The special feature of the ES is the self-adaptation of mutation step sizes and the coevolution associated with it. The ES is briefly presented using the standard form,[16][17][18] pointing out that there are many variants.[19][20][21][22] The real-valued chromosome contains, in addition to the decision variables, mutation step sizes , where: . Often one mutation step size is used for all decision variables or each has its own step size. Mate selection to produce offspring is random, i.e. independent of fitness. First, new mutation step sizes are generated per mating by intermediate recombination of the parental with subsequent mutation as follows:

where is a normally distributed random variable with mean and standard deviation . applies to all , while is newly determined for each . Next, discrete recombination of the decision variables is followed by a mutation using the new mutation step sizes as standard deviations of the normal distribution. The new decision variables are calculated as follows:

This results in an evolutionary search on two levels: First, at the problem level itself and second, at the mutation step size level. In this way, it can be ensured that the ES searches for its target in ever finer steps. However, there is also the danger of being able to skip larger invalid areas in the search space only with difficulty.

Variants

[edit]

The ES knows two variants of best selection for the generation of the next parent population: In the ES, only the best offspring are used, whereas in the elitist ES, the best are selected from parents and children.

Bäck and Schwefel recommend that the value of should be seven times the population size ,[17] whereby must not be chosen too small because of the strong selection pressure. Suitable values for are application-dependent and must be determined experimentally.

Individual step sizes for each coordinate, or correlations between coordinates, which are essentially defined by an underlying covariance matrix, are controlled in practice either by self-adaptation or by covariance matrix adaptation (CMA-ES).[21] When the mutation step is drawn from a multivariate normal distribution using an evolving covariance matrix, it has been hypothesized that this adapted matrix approximates the inverse Hessian of the search landscape. This hypothesis has been proven for a static model relying on a quadratic approximation.[23]

The selection of the next generation in evolution strategies is deterministic and only based on the fitness rankings, not on the actual fitness values. The resulting algorithm is therefore invariant with respect to monotonic transformations of the objective function. The simplest and oldest[2] evolution strategy operates on a population of size two: the current point (parent) and the result of its mutation. Only if the mutant's fitness is at least as good as the parent one, it becomes the parent of the next generation. Otherwise the mutant is disregarded. This is a ES. More generally, mutants can be generated and compete with the parent, called ES. In ES the best mutant becomes the parent of the next generation while the current parent is always disregarded. For some of these variants, proofs of linear convergence (in a stochastic sense) have been derived on unimodal objective functions.[24][25]

See also

[edit]

References

[edit]
  1. ^ Slowik, Adam; Kwasnicka, Halina (1 August 2020). "Evolutionary algorithms and their applications to engineering problems". Neural Computing and Applications. 32 (16): 12363–12379. doi:10.1007/s00521-020-04832-8. ISSN 1433-3058.
  2. ^ a b c d Slowik, Adam; Kwasnicka, Halina (1 August 2020). "Evolutionary algorithms and their applications to engineering problems". Neural Computing and Applications. 32 (16): 12363–12379. doi:10.1007/s00521-020-04832-8. ISSN 1433-3058.
  3. ^ Vent, W. (January 1975). "Rechenberg, Ingo, Evolutionsstrategie — Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. 170 S. mit 36 Abb. Frommann-Holzboog-Verlag. Stuttgart 1973. Broschiert". Feddes Repertorium. 86 (5): 337. doi:10.1002/fedr.19750860506.
  4. ^ Ostermeier, Andreas; Gawelczyk, Andreas; Hansen, Nikolaus (December 1994). "A Derandomized Approach to Self-Adaptation of Evolution Strategies". Evolutionary Computation. 2 (4): 369–380. doi:10.1162/evco.1994.2.4.369.
  5. ^ Ostermeier, Andreas; Gawelczyk, Andreas; Hansen, Nikolaus (1994). "Step-size adaptation based on non-local use of selection information". Parallel Problem Solving from Nature — PPSN III. Lecture Notes in Computer Science. Vol. 866. Springer. pp. 189–198. doi:10.1007/3-540-58484-6_263. ISBN 978-3-540-58484-1.
  6. ^ Hansen, Nikolaus; Ostermeier, Andreas (June 2001). "Completely Derandomized Self-Adaptation in Evolution Strategies". Evolutionary Computation. 9 (2): 159–195. doi:10.1162/106365601750190398. PMID 11382355.
  7. ^ Arnold, Dirk V. (28 August 2006). "Weighted multirecombination evolution strategies". Theoretical Computer Science. 361 (1): 18–37. doi:10.1016/j.tcs.2006.04.003. ISSN 0304-3975.
  8. ^ Jung, Jason J.; Jo, Geun-Sik; Yeo, Seong-Won (2007). "Meta-evolution Strategy to Focused Crawling on Semantic Web". Artificial Neural Networks – ICANN 2007. Lecture Notes in Computer Science. Vol. 4669. Springer. pp. 399–407. doi:10.1007/978-3-540-74695-9_41. ISBN 978-3-540-74693-5.
  9. ^ Wierstra, Daan; Schaul, Tom; Glasmachers, Tobias; Sun, Yi; Peters, Jan; Schmidhuber, Jürgen (1 January 2014). "Natural evolution strategies". J. Mach. Learn. Res. 15 (1): 949–980. ISSN 1532-4435.
  10. ^ Glasmachers, Tobias; Schaul, Tom; Yi, Sun; Wierstra, Daan; Schmidhuber, Jürgen (7 July 2010). "Exponential natural evolution strategies". Proceedings of the 12th annual conference on Genetic and evolutionary computation (PDF). Association for Computing Machinery. pp. 393–400. doi:10.1145/1830483.1830557. ISBN 978-1-4503-0072-8.
  11. ^ Loshchilov, Ilya (12 July 2014). "A computationally efficient limited memory CMA-ES for large scale optimization". Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. Association for Computing Machinery. pp. 397–404. arXiv:1404.5520. doi:10.1145/2576768.2598294. ISBN 978-1-4503-2662-9.
  12. ^ Liaw, Rung-Tzuo; Ting, Chuan-Kang (July 2016). "Enhancing covariance matrix adaptation evolution strategy through fitness inheritance". 2016 IEEE Congress on Evolutionary Computation (CEC): 1956–1963. doi:10.1109/CEC.2016.7744027. ISBN 978-1-5090-0623-6.
  13. ^ Ahrari, Ali; Deb, Kalyanmoy; Preuss, Mike (September 2017). "Multimodal Optimization by Covariance Matrix Self-Adaptation Evolution Strategy with Repelling Subpopulations". Evolutionary Computation. 25 (3): 439–471. doi:10.1162/evco_a_00182. hdl:1887/76707. PMID 27070282.
  14. ^ Beyer, Hans-Georg; Sendhoff, Bernhard (October 2017). "Simplify Your Covariance Matrix Adaptation Evolution Strategy". IEEE Transactions on Evolutionary Computation. 21 (5): 746–759. doi:10.1109/TEVC.2017.2680320.
  15. ^ Akimoto, Youhei; Auger, Anne; Hansen, Nikolaus (6 September 2020). "Quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions". Theoretical Computer Science. 832: 42–67. doi:10.1016/j.tcs.2018.05.015. ISSN 0304-3975.
  16. ^ Schwefel, Hans-Paul (1995). Evolution and Optimum Seeking. Sixth-generation computer technology series. New York: Wiley. ISBN 978-0-471-57148-3.
  17. ^ a b Bäck, Thomas; Schwefel, Hans-Paul (1993). "An Overview of Evolutionary Algorithms for Parameter Optimization". Evolutionary Computation. 1 (1): 1–23. doi:10.1162/evco.1993.1.1.1. ISSN 1063-6560.
  18. ^ Schwefel, Hans-Paul; Rudolph, Günter; Bäck, Thomas (1995), Morán, Frederico; Moreno, Alvaro; Merelo, J.J.; Chacón, Pablo (eds.), "Contemporary Evolution Strategies", Proceedings of the Third European Conference on Advances in Artificial Life, Berlin, Heidelberg: Springer, pp. 893–907, doi:10.1007/3-540-59496-5_351, ISBN 978-3-540-59496-3
  19. ^ Bäck, Thomas; Hoffmeister, Frank; Schwefel, Hans-Paul (1991), Belew, Richard K.; Booker, Lashon B. (eds.), "A Survey of Evolution Strategies", Proceedings of the Fourth International Conference on Genetic Algorithms (ICGA), San Mateo, Calif: Morgan Kaufmann, ISBN 978-1-55860-208-3
  20. ^ Coelho, V. N.; Coelho, I. M.; Souza, M. J. F.; Oliveira, T. A.; Cota, L. P.; Haddad, M. N.; Mladenovic, N.; Silva, R. C. P.; Guimarães, F. G. (2016). "Hybrid Self-Adaptive Evolution Strategies Guided by Neighborhood Structures for Combinatorial Optimization Problems". Evolutionary Computation. 24 (4): 637–666. doi:10.1162/EVCO_a_00187. ISSN 1063-6560.
  21. ^ a b Hansen, Nikolaus; Ostermeier, Andreas (2001). "Completely Derandomized Self-Adaptation in Evolution Strategies". Evolutionary Computation. 9 (2): 159–195. doi:10.1162/106365601750190398. ISSN 1063-6560.
  22. ^ Hansen, Nikolaus; Kern, Stefan (2004), Yao, Xin; Burke, Edmund K.; Lozano, José A.; Smith, Jim (eds.), "Evaluating the CMA Evolution Strategy on Multimodal Test Functions", Parallel Problem Solving from Nature - PPSN VIII, vol. 3242, Berlin, Heidelberg: Springer, pp. 282–291, doi:10.1007/978-3-540-30217-9_29, ISBN 978-3-540-23092-2
  23. ^ Shir, O.M.; A. Yehudayoff (2020). "On the covariance-Hessian relation in evolution strategies". Theoretical Computer Science. 801. Elsevier: 157–174. arXiv:1806.03674. doi:10.1016/j.tcs.2019.09.002.
  24. ^ Auger, A. (2005). "Convergence results for the ES(1,λ)-SA using the theory of φ-irreducible Markov chains". Theoretical Computer Science. 334 (1–3). Elsevier: 35–69. doi:10.1016/j.tcs.2004.11.017.
  25. ^ Jägersküpper, J. (2006). "How the ES(1+1) using isotropic mutations minimizes positive definite quadratic forms". Theoretical Computer Science. 361 (1). Elsevier: 38–56. doi:10.1016/j.tcs.2006.04.004.

Bibliography

[edit]

Research centers

[edit]