Boost C++ Libraries

Synopsis

#include <boost/math/optimization/differential_evolution.hpp>

namespace boost::math::optimization {

template <typename ArgumentContainer> struct differential_evolution_parameters {
    using Real = typename ArgumentContainer::value_type;
    ArgumentContainer lower_bounds;
    ArgumentContainer upper_bounds;
    Real mutation_factor = static_cast<Real>(0.65);
    double crossover_probability = 0.5;
    // Population in each generation:
    size_t NP = 200;
    size_t max_generations = 1000;
    size_t threads = std::thread::hardware_concurrency();
    ArgumentContainer const * initial_guess = nullptr;
};

template <typename ArgumentContainer, class Func, class URBG>
ArgumentContainer differential_evolution(
    const Func cost_function, differential_evolution_parameters<ArgumentContainer> const &de_params, URBG &g,
    std::invoke_result_t<Func, ArgumentContainer> target_value = std::numeric_limits<std::invoke_result_t<Func, ArgumentContainer>>::quiet_NaN(),
    std::atomic<bool> *cancellation = nullptr,
    std::vector<std::pair<ArgumentContainer, std::invoke_result_t<Func, ArgumentContainer>>> *queries = nullptr,
    std::atomic<std::invoke_result_t<Func, ArgumentContainer>> *current_minimum_cost = nullptr);

} // namespaces

The differential_evolution function provides an implementation of the (classical) differential evolution optimization algorithm, often going by the label de/rand/bin/1. It is capable of minimizing a cost function defined on a continuous space represented by a set of bounds. This function has been designed more for progress observability, graceful cancellation, and post-hoc data analysis than for speed of convergence. We justify this design choice by reference to the "No free lunch" theorem of Wolpert and Macready, which establishes "that for any algorithm, any elevated performance over one class of problems is offset by performance over another class".

Parameters

The defaults were chosen by a reading of Price, Storn, and Lampinen, chapter 3, with the exception of the population size, which we have chosen a bit larger than they found as core counts have increased since publication of this reference and parallelization occurs within each generation. Note that there is a tradeoff between finding global minima and convergence speed. The most robust way of decreasing the probability of getting stuck in a local minima is to increase the population size.

The function

template <typename ArgumentContainer, class Func, class URBG>
ArgumentContainer differential_evolution(const Func cost_function,
                                         differential_evolution_parameters<ArgumentContainer> const &de_params,
                                         URBG &gen,
                                         std::invoke_result_t<Func, ArgumentContainer> value_to_reach
                                           = std::numeric_limits<std::invoke_result_t<Func, ArgumentContainer>>::quiet_NaN(),
                                         std::atomic<bool> *cancellation = nullptr,
                                         std::vector<std::pair<ArgumentContainer, std::invoke_result_t<Func, ArgumentContainer>>> *queries = nullptr,
                                         std::atomic<std::invoke_result_t<Func, ArgumentContainer>> *current_minimum_cost = nullptr)

Parameters:

Returns:

The ArgumentContainer corresponding to the minimum cost found by the optimization.

N.B.: The termination criteria is an "OR", not an "AND". So if the maximum generations is hit, the iteration stops, even if (say) a value_to_reach has not been attained.

Examples

An example use can be found here. More examples and API use cases can be studied in differential_evolution_test.cpp.

Caveats

We have decided to only support classic de/rand/1/bin because there are too many parameters for this class as it stands, and we have not seen benchmarks that indicate that other variants of the algorithm perform better. If a compelling usecase is provided, support for the de/x/y/z variants can be added.

Supported termination criteria are explicit requests for termination, value-to-reach, and max generations. Price, Storn, and Lampinen, Section 2.8 also list population statistics and lack of accepted trials over many generations as sensible termination criteria. These could be supported if there is demand.

Parallelization with std::thread does have overhead-especially for very fast function calls. We found that the function call needs to be roughly a microsecond for unambigous parallelization wins. However, we have not provided conditional parallelization as computationally inexpensive cost functions are the exception; not the rule. If there is a clear use case for conditional parallelization (cheap cost function in very high dimensions is a good example), we can provide it.

References