Studies on the Evolution Strategies for Continuous Black-Box Optimization

Abstract

Covariance matrix adaptation evolution strategy (CMA-ES) is one of the most successful evolutionary algorithms for continuous black box optimization. One main limitation of CMA-ES is that it involves matrix decomposition to generate new solutions, which is computationally expensive and prevents its applications for optimization problems with a moderate to high dimensional search space.

We focus on the designing of simple and efficient evolution strategies in this thesis. Our main contributions are summarized in the following.

First, we propose an efficient rank-one update for the Cholesky factor of the covariance matrix with two evolution paths involving historical information. We further greatly simplify it by analyzing the changing rate, and obtain an efficient approximated rank one update to the Cholesky factor. It is as simple as the rank one update of the CMA-ES, while avoiding the computational matrix decomposition. The algorithms' properties and behaviors are analyzed and experimentally studied. The algorithms' performances are evaluated on a set of commonly used test problems.

Second, we propose two efficient adaptation schemes for the mutation matrix that satisfies $\mathbf{C}\approx \mathbf{AA}^T$, the mutation matrix adaptation (MMA-ES) and exponential MMA-ES (xMMA-ES). These two adaptation schemes incorporate both rank-one and rank-$\mu$ updates, where the rank-one update involves historical search information, and the rank-$\mu$ update uses the selected solutions of the current population. The algorithms' properties and behaviors are analyzed and experimentally studied. The algorithms' performances are extensively studied, and further evaluated on the black box optimization benchmarks with the BiPop restart strategy. The experimental results show that MMA-ES and xMMA-ES achieve better or competitive performances to the state-of-the-art algorithms.

Third, we develop a sparse and low rank model to handle large scale black box optimization. In this model, a single or a few evolution paths are used to construct the covariance matrix, and used as principal search directions. The new solutions can be generated without involving matrix-vector multiplication. It is of linear complexity. We investigate the algorithm behaviors, the invariance under rotation, and the running time. The experimental results show that, with only two evolution paths, it outperforms or performs competitively with regard to the CMA-ES on dimension 1000. We further evaluate the algorithm performance on CEC’2010 LSGO benchmarks compared with state-of-the-art variants.

Date of Award	31 Jan 2018
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Qingfu ZHANG (Supervisor)