Small Populations, High-Dimensional Spaces: Sparse Covariance Matrix Adaptation

• Autorzy: Silja Meyer-Nieberg , Erik Kropat
• Języki publikacji: EN

Abstrakty

EN

Evolution strategies are powerful evolutionary algorithms for continuous optimization. The main search operator is mutation. Its extend is controlled by the covariance matrix and must be adapted during a run. Modern Evolution Strategies accomplish this with covariance matrix adaptation techniques. However, the quality of the common estimate of the covariance is known to be questionable for high search space dimensions. This paper introduces a new approach by changing the coordinate system and introducing sparse covariance matrix techniques. The results are evaluated in experiments. (original abstract)

Słowa kluczowe

EN

Matrix; Algorithms

PL

Macierze; Algorytmy

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 525--535

Twórcy

autor

Silja Meyer-Nieberg

• Universitat der Bundeswehr Munchen, Germany

autor

Erik Kropat

• Universitat der Bundeswehr Munchen, Germany

Bibliografia

• T. Back, C. Foussette, and P. Krause, ¨ Contemporary Evolution Strategies, ser. Natural Computing. Springer, 2013.
• W. Dong and X. Yao, "Covariance matrix repairing in gaussian based EDAs," in Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, 2007. doi: 10.1109/CEC.2007.4424501 pp. 415-422.
• O. Ledoit and M. Wolf, "A well-conditioned estimator for large dimensional covariance matrices," Journal of Multivariate Analysis Archive, vol. 88, no. 2, pp. 265-411, 2004.
• S. Meyer-Nieberg and E. Kropat, "Adapting the covariance in evolution strategies," in Proceedings of ICORES 2014. SCITEPRESS, 2014, pp. 89-99.
• "A new look at the covariance matrix estimation in evolution strategies," in Operations Research and Enterprise Systems, ser. Communications in Computer and Information Science, E. Pinson, F. Valente, and B. Vitoriano, Eds. Springer International Publishing, 2015, vol. 509, pp. 157-172. ISBN 978-3-319-17508-9. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-17509-6 11
• A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, ser. Natural Computing Series. Berlin: Springer, 2003.
• I. Rechenberg, Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart: FrommannHolzboog Verlag, 1973.
• H.-P. Schwefel, Numerical Optimization of Computer Models. Chichester: Wiley, 1981.
• H.-G. Beyer and H.-P. Schwefel, "Evolution strategies: A comprehensive introduction," Natural Computing, vol. 1, no. 1, pp. 3-52, 2002.
• N. Hansen and A. Ostermeier, "Completely derandomized selfadaptation in evolution strategies," Evolutionary Computation, vol. 9, no. 2, pp. 159-195, 2001.
• H.-G. Beyer and B. Sendhoff, "Covariance matrix adaptation revisited - the CMSA evolution strategy -," in PPSN, ser. Lecture Notes in Computer Science, G. Rudolph et al., Eds., vol. 5199. Springer, 2008. ISBN 978-3-540-87699-1 pp. 123-132.
• H.-G. Beyer and S. Meyer-Nieberg, "Self-adaptation of evolution strategies under noisy fitness evaluations," Genetic Programming and Evolvable Machines, vol. 7, no. 4, pp. 295-328, 2006.
• N. Hansen, "The CMA evolution strategy: A comparing review," in Towards a new evolutionary computation. Advances in estimation of distribution algorithms, J. Lozano et al., Eds. Springer, 2006, pp. 75- 102.
• C. Stein, "Inadmissibility of the usual estimator for the mean of a multivariate distribution," in Proc. 3rd Berkeley Symp. Math. Statist. Prob. 1, Berkeley, CA, 1956, pp. 197-206.
• "Estimation of a covariance matrix," in Rietz Lecture, 39th Annual Meeting. Atlanta, GA: IMS, 1975.
• J. Schaffer and K. Strimmer, "A shrinkage approach to large-scale ¨ covariance matrix estimation and implications for functional genomics,," Statistical Applications in Genetics and Molecular Biology, vol. 4, no. 1, p. Article 32, 2005.
• V. A. Marcenko and L. A. Pastur, "Distribution of eigenvalues for some ˇ sets of random matrices," Sbornik: Mathematics, vol. 1, no. 4, pp. 457- 483, 1967.
• J. Friedman, T. Hastie, and R. Tibshirani, "Sparse inverse covariance estimation with the graphical lasso," Biostatistics, vol. 9, no. 3, pp. 432-441, 2008. doi: 10.1093/biostatistics/kxm045. [Online]. Available: http://biostatistics.oxfordjournals.org/content/9/3/432.abstract
• E. Levina, A. Rothman, and J. Zhu, "Sparse estimation of large covariance matrices via a nested lasso penalty," Ann. Appl. Stat., vol. 2, no. 1, pp. 245-263, 03 2008. doi: 10.1214/07-AOAS139. [Online]. Available: http://dx.doi.org/10.1214/07-AOAS139
• ] T. J. Fisher and X. Sun, "Improved Stein-type shrinkage estimators for the high-dimensional multivariate normal covariance matrix," Computational Statistics & Data Analysis, vol. 55, no. 5, pp. 1909 - 1918, 2011. doi: http://dx.doi.org/10.1016/j.csda.2010.12.006. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0167947310004743
• X. Chen, Z. Wang, and M. McKeown, "Shrinkage-to-tapering estimation of large covariance matrices," Signal Processing, IEEE Transactions on, vol. 60, no. 11, pp. 5640-5656, 2012. doi: 10.1109/TSP.2012.2210546
• T. Cai and W. Liu, "Adaptive thresholding for sparse covariance matrix estimation," Journal of the American Statistical Association, vol. 106, no. 494, pp. 672-684, 2011.
• J. Fan, Y. Liao, and M. Mincheva, "Large covariance estimation by thresholding principal orthogonal complements," Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol. 75, no. 4, pp. 603-680, 2013.
• R. Ros and N. Hansen, "A simple modification in cma-es achieving linear time and space complexity," in Parallel Problem Solving from Nature-PPSN X. Springer, 2008, pp. 296-305.
• N. Hansen, "Adaptive encoding: How to render search coordinate system invariant," in Parallel Problem Solving from Nature - PPSN X, ser. Lecture Notes in Computer Science, G. Rudolph, T. Jansen, N. Beume, S. Lucas, and C. Poloni, Eds. Springer Berlin Heidelberg, 2008, vol. 5199, pp. 205-214. ISBN 978-3-540-87699-1. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-87700-4 21
• M. Pourahmadi, High-Dimensional Covariance Estimation: With HighDimensional Data. John Wiley & Sons, 2013.
• J. Fan, Y. Liao, and H. Liu, "An overview on the estimation of large covariance and precision matrices," arXiv:1504.02995.
• D. Guillot and B. Rajaratnam, "Functions preserving positive definiteness for sparse matrices," Transactions of the American Mathematical Society, vol. 367, no. 1, pp. 627-649, 2015.
• N. Hansen, A. Auger, S. Finck, and R. Ros, "Real-parameter black-box optimization benchmarking 2012: Experimental setup," INRIA, Tech. Rep., 2012. [Online]. Available: http://coco.gforge.inria. fr/bbob2012-downloads
• S. Finck, N. Hansen, R. Ros, and A. Auger, "Real-parameter black-box optimization benchmarking 2010: Presentation of the noiseless functions," Institute National de Recherche en Informatique et Automatique, Tech. Rep., 2010, 2009/22.

Identyfikatory

DOI

10.15439/2015F261