The Task
Black-box optimization of 25 benchmark functions under thoroughly defined experimental and recording conditions for the 2005 IEEE Congress on Evolutionary Computation: Session on Real-Parameter Optimization (see resources links below). 18 papers were submitted, 11 were accepted.
Algorithms
We submitted two algorithms.
- L-CMA-ES (Auger and Hansen 2005b): A CMA evolution strategy with small population size and small initial step size to emphasize on local search characteristics. Independent restarts are conducted until the target function value is reached or the maximum number of function evaluations is exceeded.
- G-CMA-ES (Auger and Hansen 2005a): A CMA evolution strategy restarted with increasing population size (IPOP). Independent restarts are conducted with increasing population size until the target function value is reached or the maximum number of function evaluations is exceeded. With the initial small population size the algorithm converges fast, with the succeeding larger population sizes the global search performance is emphasized in subsequent restarts.
Results
The following figures show the comparison of performance results from the 11 algorithms for search space dimension 10 and 30 on different function subsets.
All functions solved by at least one algorithm | Unimodal functions | Multimodal functions | |
10D |
|||
30D |
The expected number of function evaluations to reach the target function value is denoted with FEs (equivalent to the performance measure SP1 in Auger and Hansen 2005b) and normalized by the value of the best algorithm on the respective function, FEs_{best}. Shown is, for each algorithm, the empirical cumulative distribution function of FEs / FEs_{best} over the given set of functions. Small values for FEs / FEs_{best} and therefore large values of the graphs are preferable. The algorithms are referenced in the comparison of results (pdf) in the Resources section below. How to read the graphs. In the lower left figure (all solved functions in 30D) we find for FEs / FEs_{best} = 2 (x-axis) a value of about 0.82 (y-axis) for the graph of G-CMA-ES. That means, on 82% of the functions G-CMA-ES was maximum 2 times slower than the best algorithm (in terms of expected number of function evaluations). For FEs / FEs_{best} = 10 we find a value of 1 in the distribution graph, meaning that G-CMA-ES was at most 10 times slower on all of the functions. The right most values of the graphs give the ratio of ever solved functions, ranging here between 100% for G-CMA-ES and just under 20% for BLX-MA and DE (due to the comparatively low number of overall allowed function evaluations).
Discussion
Compared to all contributed algorithms the G-CMA-ES seems to be superior from three perspectives.
- The G-CMA-ES performes best in terms of number of function evaluations to reach a target function value
- over all solved functions (left figures)
- on the subset of unimodal functions (middle figures)
- on the subset of solved multimodal functions (right figures)
Also on the remaining subset of functions, where no algorithm reached the target function value in any trial, the G-CMA-ES performes best (in terms of ranking of the final function value, see comparison of results in the Resources section below). Only on two separable functions the CMA-ES is considerably outperformed by other contributed algorithms.
- No parameter tuning is conducted for the CMA-ES (the default parameter values are always applied) which was not true for all submitted algorithms.
- The CMA-ES exhibits the most invariance properties together with EDA and K-PCX. The two probably most important invariance properties are
- invariance against order preserving (i.e. strictly monotonic) transformations of the objective function value, and
- invariance against angle preserving (rigid) transformations of the search space (including rotation, reflection, and translation), if the initial search point is transformed accordingly.
Invariances are highly desirable, because they imply uniform behavior on classes of functions and therefore allow for generalization of empirical results.
Resources
- Session home page
- Benchmark function definitions (pdf)
- For all related sources see CEC05 Session at http://www.ntu.edu.sg/home/EPNSugan
- More detailed comparison of results (pdf) of all published papers
- CMA Evolution Strategies
- The Matlab code of the CMA Evolution Strategy (more recent versions might be available) used within this batch file (increasing population size, IPOP-CMA-ES, G-CMA-ES) and this batch file (local search with constant small population size and small initial step size, LS-CMA-ES, L-CMA-ES)
- All results, data, figures and source code (tar.gz 18M)
References
- Auger, A, and Hansen, N. (2005a). A Restart CMA Evolution Strategy With Increasing Population Size. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2005, pp. 1769-1776 (abstract & erratum, paper in pdf).
- Auger, A, and Hansen, N. (2005b). Performance Evaluation of an Advanced Local Search Evolutionary Algorithm. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2005, pp.1777-1784 (abstract & erratum, paper in pdf).