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
highl_aug06_1
highl_aug06_2
highl_aug06_3






30D
highl_aug06_4
highl_aug06_5
highl_aug06_6

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, FEsbest. Shown is, for each algorithm, the empirical cumulative distribution function of FEs / FEsbest over the given set of functions. Small values for FEs / FEsbest 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 / FEsbest = 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 / FEsbest = 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.

  1. 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.

  2. No parameter tuning is conducted for the CMA-ES (the default parameter values are always applied) which was not true for all submitted algorithms.
  3. 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

References

  1. 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).
  2. 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).