Large Scale Evolution Strategy Based on Search Direction Adaptation
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.
IEEE Transactions on Cybernetics