Top

Published in:

2018 | OriginalPaper | Chapter

Can Evolution Strategies Benefit from Shrinkage Estimators?

Authors : Silja Meyer-Nieberg, Erik Kropat

Published in: Transactions on Computational Collective Intelligence XXVIII

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Evolution strategies are evolutionary algorithms usually applied for solving continuous optimization tasks. As they rely on mutation as one of the main search operators, the control and the adaptation of this process is of high importance. This paper discusses the covariance matrix adaptation in evolution strategies, a central and essential mechanism for the search. The current form bases the estimation of the covariance matrix on small samples sizes compared to the search space dimension which is known to be problematic. This leads to the question, whether the performance of the evolutionary algorithms could be improved if other estimators were utilized. In statistics, several alternative approaches have been considered. Up to now, they have only been seldom applied in evolutionary computation. The paper investigates whether evolution strategies may benefit from linear shrinkage estimators. Several shrinkage targets are considered, integrated in the so-called CMSA-ES, and analyzed experimentally with a special focus on the shrinkage intensity.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Controlling a Single Transport Robot in a Flexible Job Shop Environment by Hybrid Metaheuristics

next chapter An Emotional Multi-personality Architecture for Intelligent Conversational Agents

http://www.econ.uzh.ch/faculty/wolf/publications.html.

http://cran.r-project.org/web/packages/ShrinkCovMat.

The latest software can be obtained from COmparing Continuous Optimisers: COCO (http://coco.gforge.inria.fr/).

Bäck, T., Foussette, C., Krause, P.: Contemporary Evolution Strategies. Natural Computing. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40137-4CrossRefMATH

Beyer, H.G., Meyer-Nieberg, S.: Self-adaptation of evolution strategies under noisy fitness evaluations. Genet. Program. Evolvable Mach. 7(4), 295–328 (2006)CrossRef

Beyer, H.G., Schwefel, H.P.: Evolution strategies: a comprehensive introduction. Nat. Comput. 1(1), 3–52 (2002)MathSciNetCrossRefMATH

Beyer, H.G., Sendhoff, B.: Robust optimization - a comprehensive survey. Comput. Methods Appl. Mech. Eng. 196(33–34), 3190–3218 (2007). https://doi.org/10.1016/j.cma.2007.03.003MathSciNetCrossRefMATH

Beyer, H.-G., Sendhoff, B.: Covariance matrix adaptation revisited –the CMSA evolution strategy–. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 123–132. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87700-4_13CrossRef

Chen, X., Wang, Z., McKeown, M.: Shrinkage-to-tapering estimation of large covariance matrices. IEEE Trans. Signal Process. 60(11), 5640–5656 (2012)MathSciNetCrossRef

Chen, Y., Wiesel, A., Eldar, Y.C., Hero, A.O.: Shrinkage algorithms for MMSE covariance estimation. IEEE Trans. Signal Process. 58(10), 5016–5029 (2010)MathSciNetCrossRef

Dong, W., Yao, X.: Covariance matrix repairing in gaussian based EDAs. In: 2007 IEEE Congress on Evolutionary Computation, CEC 2007, pp. 415–422 (2007)

Finck, S., Hansen, N., Ros, R., Auger, A.: Real-parameter black-box optimization benchmarking 2010: presentation of the noiseless functions. Technical report, Institute National de Recherche en Informatique et Automatique, 2009/22 (2010)

10.

Finck, S., Hansen, N., Ros, R., Auger, A.: Real-parameter black-box optimization benchmarking 2010: Presentation of the noisy functions. Working paper 2009/21 (2010). http://coco.lri.fr/downloads/download15.03/bbobdocnoisyfunctions.pdf

11.

Fisher, T.J., Sun, X.: Improved Stein-type shrinkage estimators for the high-dimensional multivariate normal covariance matrix. Comput. Stat. Data Anal. 55(5), 1909–1918 (2011). http://www.sciencedirect.com/science/article/pii/S0167947310004743MathSciNetCrossRefMATH

12.

Hansen, N.: The CMA evolution strategy: a comparing review. In: Lozano, J., et al. (eds.) Towards a New Evolutionary Computation: Advances in Estimation of Distribution Algorithms. Studies in Fuzziness and Soft Computing, vol. 192, pp. 75–102. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-32494-1_4

13.

Hansen, N., Auger, A., Finck, S., Ros, R.: Real-parameter black-box optimization benchmarking 2012: Experimental setup. Technical report, INRIA (2012). http://coco.gforge.inria.fr/bbob2012-downloads

14.

Hansen, N.: Adaptive encoding: how to render search coordinate system invariant. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 205–214. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87700-4_21CrossRef

15.

Hansen, N., Auger, A., Ros, R., Finck, S., Pošík, P.: Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009. In: Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO 2010, pp. 1689–1696. ACM, New York (2010). http://doi.acm.org/10.1145/1830761.1830790

16.

Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments - a survey. IEEE Trans. Evol. Comput. 9(3), 303–317 (2005)CrossRef

17.

Kramer, O.: Evolution strategies with Ledoit-Wolf covariance matrix estimation. In: 2015 IEEE Congress on Evolutionary Computation (IEEE CEC) (2015)

18.

Ledoit, O., Wolf, M.: Improved estimation of the covariance matrix of stock returns with an application to portfolio selection. J. Empirical Finance 10(5), 603–621 (2003)CrossRef

19.

Ledoit, O., Wolf, M.: Honey, I shrunk the sample covariance matrix. J. Portf. Manage. 30(4), 110–119 (2004)CrossRef

20.

Ledoit, O., Wolf, M.: A well-conditioned estimator for large dimensional covariance matrices. J. Multivar. Anal. Arch. 88(2), 265–411 (2004)MathSciNetMATH

21.

Ledoit, O., Wolf, M.: Non-linear shrinkage estimation of large dimensional covariance matrices. Ann. Stat. 40(2), 1024–1060 (2012)CrossRefMATH

22.

Ledoit, O., Wolf, M.: Nonlinear shrinkage of the covariance matrix for portfolio selection: Markowitz meets goldilocks. Available at SSRN 2383361 (2014)

23.

Meyer-Nieberg, S., Beyer, H.G.: On the analysis of self-adaptive recombination strategies: first results. In: McKay, B., et al. (eds.) Proceedings of the 2005 Congress on Evolutionary Computation (CEC 2005), Edinburgh, UK, pp. 2341–2348. IEEE Press, Piscataway (2005)

24.

Meyer-Nieberg, S., Beyer, H.G.: Self-adaptation in evolutionary algorithms. In: Lobo, F., Lima, C., Michalewicz, Z. (eds.) Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence, vol. 54, pp. 47–76. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-69432-8_3CrossRef

25.

Meyer-Nieberg, S., Kropat, E.: Small populations, high-dimensional spaces: Sparse covariance matrix adaptation. In: 2015 Federated Conference on Computer Science and Information Systems (FedCSIS), pp. 525–535, September 2015

26.

Meyer-Nieberg, S., Kropat, E.: Evolution strategies and covariance matrix adaptation - investigating new shrinkage techniques. In: Proceedings of the 8th International Conference on Agents and Artificial Intelligence, pp. 105–116 (2016)

27.

Meyer-Nieberg, S., Kropat, E.: Adapting the covariance in evolution strategies. In: Proceedings of ICORES 2014, pp. 89–99. SCITEPRESS (2014)

28.

Meyer-Nieberg, S., Kropat, E.: A new look at the covariance matrix estimation in evolution strategies. In: Pinson, E., Valente, F., Vitoriano, B. (eds.) ICORES 2014. CCIS, vol. 509, pp. 157–172. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-17509-6_11CrossRef

29.

Meyer-Nieberg, S., Kropat, E.: Sparse covariance matrix adaptation techniques for evolution strategies. In: Bramer, M., Petridis, M. (eds.) Research and Development in Intelligent Systems XXXII, pp. 5–21. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25032-8_1CrossRef

30.

Pourahmadi, M.: High-Dimensional Covariance Estimation: With High-Dimensional Data. Wiley, New York (2013)CrossRefMATH

31.

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

32.

Rudolph, G.: Evolutionary strategies. In: Rozenberg, G., Bäck, T., Kok, J.N. (eds.) Handbook of Natural Computing, pp. 673–698. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-540-92910-9_22CrossRef

33.

Schwefel, H.P.: Numerical Optimization of Computer Models. Wiley, Chichester (1981)MATH

34.

Soysal, O., Sahin, E.: Probabilistic aggregation strategies in swarm robotic systems. In: Proceedings 2005 IEEE Swarm Intelligence Symposium, SIS 2005, pp. 325–332, June 2005

35.

Stein, C.: Inadmissibility of the usual estimator for the mean of a multivariate distribution. In: Proceedings of the 3rd Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, CA, vol. 1, pp. 197–206 (1956)

36.

Stein, C.: Estimation of a covariance matrix. In: Rietz Lecture, 39th Annual Meeting. IMS, Atlanta, GA (1975)

37.

Thomaz, C.E., Gillies, D., Feitosa, R.: A new covariance estimate for bayesian classifiers in biometric recognition. IEEE Trans. Circuits Syst. Video Technol. 14(2), 214–223 (2004)CrossRef

38.

Tong, T., Wang, C., Wang, Y.: Estimation of variances and covariances for high-dimensional data: a selective review. Wiley Interdisc. Rev. Comput. Stat. 6(4), 255–264 (2014)CrossRef

39.

Touloumis, A.: Nonparametric Stein-type shrinkage covariance matrix estimators in high-dimensional settings. Comput. Stat. Data Anal. 83, 251–261 (2015)MathSciNetCrossRef

Title: Can Evolution Strategies Benefit from Shrinkage Estimators?
Authors: Silja Meyer-Nieberg
Erik Kropat
Publisher: Springer International Publishing
Book: Transactions on Computational Collective Intelligence XXVIII
Print ISBN: 978-3-319-78300-0

Electronic ISBN: 978-3-319-78301-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-78301-7_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner