Benchmark of open-source metaheuristic solvers

Differential Evolution (DE) is a powerful method of derivative-free global optimization. The ALGLIB numerical library includes GDEMO - one of the best open-source implementations of differential evolution available in C++, C#, Java and other languages under free and commercial licenses. The solver is robust, parallelized and capable of efficiently handling unconstrained and constrained problems with box, linear and nonlinear constraints.

This article compares GDEMO with other open-source metaheuristic solvers, including both Differential Evolution solvers and other similar algorithms. An overview of the ALGLIB solver itself is provided on another page.

Benchmark setup

Solvers compared: the following solvers were chosen for comparison:

• ALGLIB-DE: ALGLIB implementation of DE using an adaptive parameter selection and parallelism support.
• SCIPY-DE: SciPy implementation of DE.
• PYMOO-DE: Pymoo implementation of DE.
• PYMOO-ES: Pymoo implementation of Evolutionary Strategy (ES).

All solvers are used with default parameters in a single-threaded mode. Whilst ALGLIB (and some other solvers tested) supports parallelism, for the simplicity of comparison we used a single-threaded mode in this benchmark.

Test set: a small-dimensional subset (up to 10 vars, up to 20 constraints) of the CUTEst set. Because support for constrained optimization strongly varies between packages (ALGLIB is the most powerful one in this regard), we reduced problems to unconstrained ones by adding an L1 penalty.

Measurement methodology: all solvers were run until either an evaluation budget of 50000 simplex gradients equivalents (a batch of N+1 target evaluations) or a time budget of 30 seconds was exhausted.

The solver running time is defined as a point in its evaluation history where the best value found so far was within ε=0.01 from the global minimum. The global minimum is defined as the best value found by all solvers. If the solver failed to converge to the global minimum, its running time is equal to ∞.

The median running time over entire dataset is used as a measure of the quality. Using median instead of mean allows us to easily deal with infinite running times (failures) as long as the solver fails in less than 50% of cases.

Benchmark result

ALGLIB Differential Evolution is slightly better than Pymoo's Evolutionary Strategy and significantly better than Pymoo's own Differential Evolution. SciPy implementation severely lags behind.

This article is licensed for personal use only.