Self-adaptive Differential Evolution (DE 1220 aka pDE)

class pagmo::de1220

A Differential Evolution Algorithm (1220, or pDE: our own DE flavour!!)

.../../../_images/original.jpg

Differential Evolution (pagmo::de, pagmo::sade) is one of the best meta-heuristics in PaGMO, so we dared to propose our own algoritmic variant we call DE 1220 (a.k.a. pDE as in pagmo DE). Our variant makes use of the pagmo::sade adaptation schemes for CR and F and adds self-adaptation for the mutation variant. The only parameter left to be specified is thus population size.

Similarly to what done in pagmo::sade for F and CR, in DE 1220 each individual chromosome (index \(i\)) is augmented also with an integer \(V_i\) that specifies the mutation variant used to produce the next trial individual. Right before mutating the chromosome the value of \(V_i\) is adapted according to the equation:

\[\begin{split} V_i = \left\{\begin{array}{ll} random & r_i < \tau \\ V_i & \mbox{otherwise} \end{array}\right. \end{split}\]

where \(\tau\) is set to be 0.1, \(random\) selects a random mutation variant and \(r_i\) is a random uniformly distributed number in [0, 1]

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.

Note

The search range is defined relative to the box-bounds. Hence, unbounded problems will produce an error.

See also

pagmo::de, pagmo::sade For other available algorithms based on Differential Evolution

Public Types

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

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

typedef std::vector<log_line_type> log_type

The log.

Public Functions

de1220(unsigned gen = 1u, std::vector<unsigned> allowed_variants = de1220_statics<void>::allowed_variants, unsigned variant_adptv = 1u, double ftol = 1e-6, double xtol = 1e-6, bool memory = false, unsigned seed = pagmo::random_device::next())

Constructor.

Constructs pDE (a.k.a. DE 1220)

The same two self-adaptation variants used in pagmo::sade are used to self-adapt the CR and F parameters:

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

A subset of the following mutation variants is considered when adapting the mutation variant:

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 variants introduced in the orginal DE algorithm, the remaining ones are, instead, introduced in the work by Elsayed et al.

See: (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: (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.

Parameters
  • gen – number of generations.

  • allowed_variants – the subset of mutation variants to be considered (default is {2u ,3u ,7u ,10u ,13u ,14u ,15u ,16u})

  • variant_adptv – 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 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 in [0,1]

  • std::invalid_argument – if allowed_variants contains a number not in 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:       Variant:            dx:            df:
    1             15        45.4245       0.480391       0.567908              4        10.9413        35061.1
    2             30        45.4245       0.480391       0.567908              4        10.9413        35061.1
    3             45        45.4245       0.480391       0.567908              4        10.9413        35061.1
    4             60        6.55036       0.194324      0.0732594              6        9.35874        4105.24
    5             75        6.55036       0.194324      0.0732594              6        6.57553         3558.4
    6             90        2.43304       0.448999       0.678681             14        3.71972        1026.26
    7            105        2.43304       0.448999       0.678681             14        11.3925        820.816
    8            120        1.61794       0.194324      0.0732594              6        11.0693        821.631
    9            135        1.61794       0.194324      0.0732594              6        11.0693        821.631
   10            150        1.61794       0.194324      0.0732594              6        11.0693        821.631
   11            165       0.643149       0.388876       0.680573              7        11.2983        822.606
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, Variant is the mutation variant 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 de1220::log_line_type containing: Gen, Fevals, Best, F, CR, Variant, dx, df as described in de1220::set_verbosity

Returns

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

template<typename T>
struct pagmo::de1220_statics

Static variables used in pagmo::de1220.

Public Static Attributes

static const std::vector<unsigned> allowed_variants = {2u, 3u, 7u, 10u, 13u, 14u, 15u, 16u}

Allowed mutation variants considered by default: {2u ,3u ,7u ,10u ,13u ,14u ,15u ,16u}.