Self-adaptive Differential Evolution (jDE and iDE)

class pagmo::sade

Self-adaptive Differential Evolution Algorithm.

.../../../_images/adaptation.jpg

Two different variants of the Differential Evolution algorithm exploiting the idea of self-adaptation.

The original Differential Evolution algorithm (pagmo::de) can be significantly improved introducing the idea of parameter self-adaptation. Many different proposals have been made to self-adapt both the CR and the F parameters of the original differential evolution algorithm. In PaGMO we implement two different mechanisms we found effective. The first one, proposed by Brest et al., does not make use of the DE operators to produce new values for F and CR and, strictly speaking, is thus not self-adaptation, rather parameter control. The resulting DE variant is often referred to as jDE. The second variant here implemented is inspired by the ideas introduced by Elsayed et al. and uses a variaton of the selected DE operator to produce new CR anf F parameters for each individual. We refer to this variant as to iDE.

Warning

A moved-from pagmo::sade is destructible and assignable. Any other operation will result in undefined behaviour.

Warning

The algorithm referred to as SaDE in the literature is not the algorithm implemented in pagmo. We use the name sade to indicate, generically, self-adaptation in a differential evolution algorithm

Note

The feasibility correction, that is the correction applied to an allele when some mutation puts it outside the allowed box-bounds, is here done by creating a random number in the bounds.

See also

(jDE) - Brest, J., Greiner, S., Bošković, B., Mernik, M., & Zumer, V. (2006). Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. Evolutionary Computation, IEEE Transactions on, 10(6), 646-657. Chicago

See also

(iDE) - Elsayed, S. M., Sarker, R. A., & Essam, D. L. (2011, June). Differential evolution with multiple strategies for solving CEC2011 real-world numerical optimization problems. In Evolutionary Computation (CEC), 2011 IEEE Congress on (pp. 1041-1048). IEEE.

Public Types

typedef std::tuple<unsigned, unsigned long long, double, double, double, double, double> log_line_type

Single entry of the log (gen, fevals, best, F, CR, dx, df)

typedef std::vector<log_line_type> log_type

The log.

Public Functions

sade(unsigned gen = 1u, unsigned variant = 2u, unsigned variant_adptv = 1u, double ftol = 1e-6, double xtol = 1e-6, bool memory = false, unsigned seed = pagmo::random_device::next())

Constructor.

Constructs self-adaptive differential evolution

Two self-adaptation variants are available to control the F and CR parameters:

1 - jDE (Brest et al.)                       2 - iDE (Elsayed at al.)

The following variants are available to produce a mutant vector:

1 - best/1/exp                               2. - rand/1/exp
3 - rand-to-best/1/exp                       4. - best/2/exp
5 - rand/2/exp                               6. - best/1/bin
7 - rand/1/bin                               8. - rand-to-best/1/bin
9 - best/2/bin                               10. - rand/2/bin
11. - rand/3/exp                             12. - rand/3/bin
13. - best/3/exp                             14. - best/3/bin
15. - rand-to-current/2/exp                  16. - rand-to-current/2/bin
17. - rand-to-best-and-current/2/exp         18. - rand-to-best-and-current/2/bin

The first ten are the classical mutation variants introduced in the orginal DE algorithm, the remaining ones are, instead, considered in the work by Elsayed et al.

Parameters
  • gen – number of generations.

  • variant – mutation variant (dafault variant is 2: /rand/1/exp)

  • variant_adptv – F and CR parameter adaptation scheme to be used (one of 1..2)

  • ftol – stopping criteria on the x tolerance (default is 1e-6)

  • xtol – stopping criteria on the f tolerance (default is 1e-6)

  • memory – when true the adapted parameters CR anf F are not reset between successive calls to the evolve method

  • seed – seed used by the internal random number generator (default is random)

Throws
  • std::invalid_argument – if variant_adptv is not one of 0,1

  • std::invalid_argument – if variant is not one of 1, .., 18

population evolve(population) const

Algorithm evolve method.

Evolves the population for a maximum number of generations, until one of tolerances set on the population flatness (x_tol, f_tol) are met.

Parameters

pop – population to be evolved

Throws
  • std::invalid_argument – if the problem is multi-objective or constrained or stochastic

  • std::invalid_argument – if the population size is not at least 7

Returns

evolved population

void set_seed(unsigned)

Sets the seed.

Parameters

seed – the seed controlling the algorithm stochastic behaviour

inline unsigned get_seed() const

Gets the seed.

Returns

the seed controlling the algorithm stochastic behaviour

inline void set_verbosity(unsigned level)

Sets the algorithm verbosity.

Sets the verbosity level of the screen output and of the log returned by get_log(). level can be:

  • 0: no verbosity

  • >0: will print and log one line each level generations.

Example (verbosity 1):

Gen:        Fevals:          Best:             F:            CR:            dx:            df:
 301           4515       0.668472       0.374983       0.502932    0.000276682    0.000388866
 302           4530       0.668472       0.374983       0.502932    0.000213271     0.00020986
 303           4545       0.668426       0.598243       0.234825    0.000167061    0.000186339
 304           4560       0.668426       0.598243       0.234825    0.000217549    0.000144896
 305           4575       0.668339       0.807236       0.863048    0.000192539    0.000232005
 306           4590       0.668339       0.807236       0.863048    0.000143711    0.000229041
 307           4605       0.668307       0.374983       0.820731    0.000163919    0.000245393
Gen, is the generation number, Fevals the number of function evaluation used, Best is the best fitness function currently in the population, F is the F used to create the best so far, CR the CR used to create the best so far, dx is the population flatness evaluated as the distance between the decisions vector of the best and of the worst individual and df is the population flatness evaluated as the distance between the fitness of the best and of the worst individual.

Parameters

level – verbosity level

inline unsigned get_verbosity() const

Gets the verbosity level.

Returns

the verbosity level

inline unsigned get_gen() const

Gets the generations.

Returns

the number of generations to evolve for

inline std::string get_name() const

Algorithm name.

One of the optional methods of any user-defined algorithm (UDA).

Returns

a string containing the algorithm name

std::string get_extra_info() const

Extra info.

One of the optional methods of any user-defined algorithm (UDA).

Returns

a string containing extra info on the algorithm

inline const log_type &get_log() const

Get log.

A log containing relevant quantities monitoring the last call to evolve. Each element of the returned std::vector is a sade::log_line_type containing: Gen, Fevals, Best, F, CR, dx, df as described in sade::set_verbosity

Returns

an std::vector of sade::log_line_type containing the logged values Gen, Fevals, Best, F, CR, dx, df