Large-Scale Evolution Strategy Based on Search Direction Adaptation
- 30 July 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Cybernetics
- Vol. 51 (3) , 1651-1665
Abstract
The covariance matrix adaptation evolution strategy (CMA-ES) is a powerful evolutionary algorithm for single-objective real-valued optimization. However, the time and space complexity may preclude its use in high-dimensional decision space. Recent studies suggest that putting sparse or low-rank constraints on the structure of the covariance matrix can improve the efficiency of CMA-ES in handling large-scale problems. Following this idea, this paper proposes a search direction adaptation evolution strategy (SDA-ES) which achieves linear time and space complexity. SDA-ES models the covariance matrix with an identity matrix and multiple search directions, and uses a heuristic to update the search directions in a way similar to the principal component analysis. We also generalize the traditional 1/5th success rule to adapt the mutation strength which exhibits the derandomization property. Numerical comparisons with nine state-of-the-art algorithms are carried out on 31 test problems. The experimental results have shown that SDA-ES is invariant under search-space rotational transformations, and is scalable with respect to the number of variables. It also achieves competitive performance on generic black-box problems, demonstrating its effectiveness in keeping a good tradeoff between solution quality and computational efficiency.Keywords
Funding Information
- National Natural Science Foundation of China (61773410, 61673403)
This publication has 48 references indexed in Scilit:
- Large scale evolutionary optimization using cooperative coevolutionInformation Sciences, 2008
- Performance Analysis of Evolutionary Optimization With Cumulative Step Length AdaptationIEEE Transactions on Automatic Control, 2004
- Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES)Evolutionary Computation, 2003
- Honey, I Shrunk the Sample Covariance MatrixSSRN Electronic Journal, 2003
- Completely Derandomized Self-Adaptation in Evolution StrategiesEvolutionary Computation, 2001
- Evolutionary algorithms and gradient search: similarities and differencesIEEE Transactions on Evolutionary Computation, 1998
- Principal component analysis in linear systems: Controllability, observability, and model reductionIEEE Transactions on Automatic Control, 1981
- Multiple Comparisons among MeansJournal of the American Statistical Association, 1961
- On a Test of Whether one of Two Random Variables is Stochastically Larger than the OtherThe Annals of Mathematical Statistics, 1947
- The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of VarianceJournal of the American Statistical Association, 1937