Differential Evolution

Table of contents


Algorithm Description

Differential Evolution (DE) is a stochastic genetic search algorithm for global optimization of problems of the form

\[\min_{x \in X} f(x)\]

where \(f\) is potentially ill-behaved in one or more ways, such as non-convexity and/or non-differentiability. The updating rule for DE is described below.

Let \(X^{(i)}\) denote the \(N \times d\) dimensional array of input values at stage \(i\) of the algorithm, where each row corresponds to a different vector of candidate solutions.

  1. The Mutation Step. For unique random indices \(a,b,c \in \{1, \ldots, d\}\), set the mutation proposal \(X^{(*)}\) as follows.

    1. If de_settings.mutation_method = 1, use the ‘rand’ method:

      \[X^{(*)} = X^{(i)}(c,:) + F \times \left( X^{(i)}(a,:) - X^{(i)}(b,:) \right)\]

      where \(F\) is the mutation parameter, set via de_settings.par_F.

    2. If de_settings.mutation_method = 2, use the ‘best’ method:

      \[X^{(*)} = X^{(i)}(\text{best},:) + F \times ( X^{(i)}(a,:) - X^{(i)}(b,:) )\]

      where

      \[X^{(i)} (\text{best},:) := \arg \min \left\{ f(X^{(i)}(1,:)), \ldots, f(X^{(i)}(N,:)) \right\}\]
  2. The Crossover Step.

    1. Choose a random integer \(r_k \in \{1, \ldots, d \}\).

    2. Draw a vector \(u\) of independent uniform random variables of length \(d\)

    3. For each \(j \in \{ 1, \ldots, N \}\) and \(k \in \{ 1, \ldots, d \}\), set

      \[X_c^{(*)} (j,k) = \begin{cases} X^*(j,k) & \text{ if } u_k \leq CR \text{ or } k = r_k \\ X^{(i)} (j,k) & \text{ else } \end{cases}\]

      where \(CR \in [0,1]\) is the crossover parameter, set via de_settings.par_CR.

  3. The Update Step.

    \[X^{(i+1)} (j,:) = \begin{cases} X_c^*(j,:) & \text{ if } f(X_c^*(j,:)) < f(X^{(i)}(j,:)) \\ X^{(i)} (j,:) & \text{ else } \end{cases}\]

The algorithm stops when at least one of the following conditions are met:

  1. the relative improvement in the objective function from the best candidate solution is less than rel_objfn_change_tol between the last de_settings.check_freq number of generations;

  2. the total number of generations exceeds de_settings.n_gen.


DE with Population Reduction and Multiple Mutation Strategies

TBW.


Function Declarations

bool de(ColVec_t &init_out_vals, std::function<fp_t(const ColVec_t &vals_inp, ColVec_t *grad_out, void *opt_data)> opt_objfn, void *opt_data)

The Differential Evolution (DE) Optimization Algorithm.

Parameters
  • init_out_vals – a column vector of initial values, which will be replaced by the solution upon successful completion of the optimization algorithm.

  • opt_objfn – the function to be minimized, taking three arguments:

    • vals_inp a vector of inputs;

    • grad_out a vector to store the gradient; and

    • opt_data additional data passed to the user-provided function.

  • opt_data – additional data passed to the user-provided function.

Returns

a boolean value indicating successful completion of the optimization algorithm.

bool de(ColVec_t &init_out_vals, std::function<fp_t(const ColVec_t &vals_inp, ColVec_t *grad_out, void *opt_data)> opt_objfn, void *opt_data, algo_settings_t &settings)

The Differential Evolution (DE) Optimization Algorithm.

Parameters
  • init_out_vals – a column vector of initial values, which will be replaced by the solution upon successful completion of the optimization algorithm.

  • opt_objfn – the function to be minimized, taking three arguments:

    • vals_inp a vector of inputs;

    • grad_out a vector to store the gradient; and

    • opt_data additional data passed to the user-provided function.

  • opt_data – additional data passed to the user-provided function.

  • settings – parameters controlling the optimization routine.

Returns

a boolean value indicating successful completion of the optimization algorithm.


bool de_prmm(ColVec_t &init_out_vals, std::function<fp_t(const ColVec_t &vals_inp, ColVec_t *grad_out, void *opt_data)> opt_objfn, void *opt_data)

The Differential Evolution (DE) with Population Reduction and Multiple Mutation Strategies (PRMM) Optimization Algorithm.

Parameters
  • init_out_vals – a column vector of initial values, which will be replaced by the solution upon successful completion of the optimization algorithm.

  • opt_objfn – the function to be minimized, taking three arguments:

    • vals_inp a vector of inputs;

    • grad_out a vector to store the gradient; and

    • opt_data additional data passed to the user-provided function.

  • opt_data – additional data passed to the user-provided function.

Returns

a boolean value indicating successful completion of the optimization algorithm.

bool de_prmm(ColVec_t &init_out_vals, std::function<fp_t(const ColVec_t &vals_inp, ColVec_t *grad_out, void *opt_data)> opt_objfn, void *opt_data, algo_settings_t &settings)

The Differential Evolution (DE) with Population Reduction and Multiple Mutation Strategies (PRMM) Optimization Algorithm.

Parameters
  • init_out_vals – a column vector of initial values, which will be replaced by the solution upon successful completion of the optimization algorithm.

  • opt_objfn – the function to be minimized, taking three arguments:

    • vals_inp a vector of inputs;

    • grad_out a vector to store the gradient; and

    • opt_data additional data passed to the user-provided function.

  • opt_data – additional data passed to the user-provided function.

  • settings – parameters controlling the optimization routine.

Returns

a boolean value indicating successful completion of the optimization algorithm.


Optimization Control Parameters

The basic control parameters are:

  • size_t de_settings.n_pop: size of population for each generation.

    • Default value: 200.

  • size_t de_settings.n_gen: number of generations.

    • Default value: 1000.

  • size_t de_settings.mutation_method: the mutation strategy, as described in step one of the algorithm description.

    • Default value: 1 (“rand”).

  • fp_t de_settings.par_F: the mutation parameter.

    • Default value: 0.8.

  • fp_t de_settings.par_CR: the crossover parameter.

    • Default value: 0.9.

  • size_t de_settings.check_freq: how many generations to skip when evaluating whether the best candidate value has improved between generations (i.e., to check for potential convergence).

    • Default value: (size_t)-1.

  • Upper and lower bounds of the uniform distributions used to generate the initial population:

    • ColVec_t de_settings.initial_lb: defines the lower bounds of the search space.

    • ColVec_t de_settings.initial_ub: defines the upper bounds of the search space.

  • fp_t rel_objfn_change_tol: the error tolerance value controlling how small the relative change in best candidate solution should be before ‘convergence’ is declared.

  • bool vals_bound: whether the search space of the algorithm is bounded. If true, then

    • ColVec_t lower_bounds: defines the lower bounds of the search space.

    • ColVec_t upper_bounds: defines the upper bounds of the search space.

In addition to these:

  • int print_level: Set print level.

    • Level 1: Print iteration count and the relative improvement in the objective function value between iterations.

    • Level 2: Level 1 and print best input values and corresponding objective function value.

    • Level 3: Level 2 and print full population matrix, \(X\).


Examples

Ackley Function

Code to run this example is given below.

Armadillo (Click to show/hide)

#define OPTIM_ENABLE_ARMA_WRAPPERS
#include "optim.hpp"

#define OPTIM_PI 3.14159265358979

double
ackley_fn(const arma::vec& vals_inp, arma::vec* grad_out, void* opt_data)
{
    const double x = vals_inp(0);
    const double y = vals_inp(1);

    const double obj_val = 20 + std::exp(1) - 20*std::exp( -0.2*std::sqrt(0.5*(x*x + y*y)) ) - std::exp( 0.5*(std::cos(2 * OPTIM_PI * x) + std::cos(2 * OPTIM_PI * y)) );

    return obj_val;
}

int main()
{
    arma::vec x = arma::ones(2,1) + 1.0; // initial values: (2,2)

    optim::algorithm_settings_t settings;
    settings.de_settings.check_freq = 100;

    bool success = optim::de(x, ackley_fn, settings);

    if (success) {
        std::cout << "de: Ackley test completed successfully." << std::endl;
    } else {
        std::cout << "de: Ackley test completed unsuccessfully." << std::endl;
    }

    arma::cout << "de: solution to Ackley test:\n" << x << arma::endl;

    return 0;
}

Eigen (Click to show/hide)

#define OPTIM_ENABLE_EIGEN_WRAPPERS
#include "optim.hpp"

#define OPTIM_PI 3.14159265358979

double
ackley_fn(const Eigen::VectorXd& vals_inp, Eigen::VectorXd* grad_out, void* opt_data)
{
    const double x = vals_inp(0);
    const double y = vals_inp(1);

    const double obj_val = 20 + std::exp(1) - 20*std::exp( -0.2*std::sqrt(0.5*(x*x + y*y)) ) - std::exp( 0.5*(std::cos(2 * OPTIM_PI * x) + std::cos(2 * OPTIM_PI * y)) );

    return obj_val;
}

int main()
{
    Eigen::VectorXd x = 2.0 * Eigen::VectorXd::Ones(2); // initial values: (2,2)

    optim::algorithm_settings_t settings;
    settings.de_settings.check_freq = 100;

    bool success = optim::de(x, ackley_fn, settings);

    if (success) {
        std::cout << "de: Ackley test completed successfully." << std::endl;
    } else {
        std::cout << "de: Ackley test completed unsuccessfully." << std::endl;
    }

    arma::cout << "de: solution to Ackley test:\n" << x << arma::endl;

    return 0;
}

Rastrigin Function

Code to run this example is given below.

Armadillo Code (Click to show/hide)

#define OPTIM_ENABLE_ARMA_WRAPPERS
#include "optim.hpp"

#define OPTIM_PI 3.14159265358979

struct rastrigin_fn_data {
    double A;
};

double
rastrigin_fn(const arma::vec& vals_inp, arma::vec* grad_out, void* opt_data)
{
    const int n = vals_inp.n_elem;

    rastrigin_fn_data* objfn_data = reinterpret_cast<rastrigin_fn_data*>(opt_data);
    const double A = objfn_data->A;

    double obj_val = A*n + arma::accu( arma::pow(vals_inp,2) - A*arma::cos(2 * OPTIM_PI * vals_inp) );

    return obj_val;
}

int main()
{
    rastrigin_fn_data test_data;
    test_data.A = 10;

    arma::vec x = arma::ones(2,1) + 1.0; // initial values: (2,2)

    bool success = optim::de(x, rastrigin_fn, &test_data);

    if (success) {
        std::cout << "de: Rastrigin test completed successfully." << std::endl;
    } else {
        std::cout << "de: Rastrigin test completed unsuccessfully." << std::endl;
    }

    arma::cout << "de: solution to Rastrigin test:\n" << x << arma::endl;

    return 0;
}

Eigen Code (Click to show/hide)

#define OPTIM_ENABLE_EIGEN_WRAPPERS
#include "optim.hpp"

#define OPTIM_PI 3.14159265358979

struct rastrigin_fn_data {
    double A;
};

double
rastrigin_fn(const Eigen::VectorXd& vals_inp, Eigen::VectorXd* grad_out, void* opt_data)
{
    const int n = vals_inp.n_elem;

    rastrigin_fn_data* objfn_data = reinterpret_cast<rastrigin_fn_data*>(opt_data);
    const double A = objfn_data->A;

    double obj_val = A*n + vals_inp.array().pow(2).sum() - A * (2 * OPTIM_PI * vals_inp).array().cos().sum();

    return obj_val;
}

int main()
{
    rastrigin_fn_data test_data;
    test_data.A = 10;

    Eigen::VectorXd x = 2.0 * Eigen::VectorXd::Ones(2); // initial values: (2,2)

    bool success = optim::de(x, rastrigin_fn, &test_data);

    if (success) {
        std::cout << "de: Rastrigin test completed successfully." << std::endl;
    } else {
        std::cout << "de: Rastrigin test completed unsuccessfully." << std::endl;
    }

    arma::cout << "de: solution to Rastrigin test:\n" << x << arma::endl;

    return 0;
}