Evolutionary Strategy (UDA)

class es4cgp

Evolutionary Strategy for a Cartesian Genetic Program.

../../_images/EvolutionaryStrategy.jpg

Evolutionary strategies are popular global optimization meta-heuristics essentially based on the following simple pseudo-algorithm:

> Start from a population (pop) of dimension N
> while i < gen
> > Mutation: create a new population pop2 containing N different mutations of pop best.
> > Evaluate all new chromosomes in pop2
> > Reinsertion: set pop to contain the best N individuals taken from pop and pop2

The key to the success of such a search strategy is in the quality of its mutation operator. In the case of chrosomoses that encode a Cartesian Genetic Program (CGP), it makes sense to have mutation act on active genes only (that is on that part of the chromosome that is actually expressed in the final CGP / formula / model). This introduces a coupling between the optimization problem (say a symbolic regression problem) and its solution strategy which, although not preventing, makes the use of general purpose optimization algorithms inefficient (e.g. a generic evolutionary strategy would have a mutation operator which is agnostic of the existence of active genes).

In this class we provide an evolutionary strategy tailored to solve :class:dcgp::symbolic_regression problems leveraging the kowledge on the genetic structure of Cartesian Genetic Programs (i.e. able to mutate only active genes).

Public Types

typedef std::tuple<unsigned, unsigned long long, double, pagmo::vector_double, std::string> log_line_type

Single entry of the log (gen, fevals, best, constants, formula)

typedef std::vector<log_line_type> log_type

The log.

Public Functions

inline es4cgp(unsigned gen = 1u, unsigned max_mut = 4u, double ftol = 0., bool learn_constants = true, unsigned seed = random_device::next())

Constructor.

Constructs an evolutionary strategy algorithm for use with a cgp::symbolic_regression UDP.

Parameters
  • gen – number of generations.

  • max_mut – maximum number of active genes to be mutated for each individual.

  • ftol – the algorithm will exit when the loss is below this tolerance. This is useful for cases where an exact formula is seeked, rather than just an approximated one.

  • learn_constants – when true a gaussian mutation is applied also to the ephemeral constants (std = 0.1).

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

Throws

std::invalid_argument – if max_mut is 0 or ftol is negative

inline pagmo::population evolve(pagmo::population pop) const

Algorithm evolve method.

Evolves the population for a maximum number of generations

Parameters

pop – population to be evolved

Throws
  • std::invalid_argument – if a dcgp::symbolic_regression cannot be extracted from the problem

  • std::invalid_argument – if the population size is smaller than 2

  • std::invalid_argument – if the number of objectives is not 1.

Returns

evolved population

inline void set_seed(unsigned seed)

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_bfe(const pagmo::bfe &b)

Sets the batch function evaluation scheme.

Parameters

b – batch function evaluation object

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 100):

Gen:        Fevals:          Best:    Constants:    Model:
    0              0        4087.68    [3.52114]    [0] ...
  100            400        324.845    [3.61414]    [2*x0**4] ...
  200            800        324.845    [3.61414]    [2*x0**4] ...
  300           1200        165.212    [3.56702]    [x0**2*(-x0 + 2*x0**2)] ...
  400           1600         28.814    [3.45813]    [x0*(-x0 + x0**2*(-x0 + x0**2) - (-x0 +  ...
  500           2000        10.5589    [3.59501]    [x0*(-4*x0 + x0**2*(-x0 + x0**2) + x0**2 ...
  600           2400         2.2459    [3.44443]    [x0*(-x0*c1 + x0**2*(-x0 + x0**2) + x0** ...
  700           2800        2.24378    [3.43364]    [x0*(-x0*c1 + x0**2*(-x0 + x0**2) + x0** ...
  800           3200        2.24378    [3.43364]    [x0*(-x0*c1 + x0**2*(-x0 + x0**2) + x0** ...
  900           3600        2.24378    [3.43364]    [x0*(-x0*c1 + x0**2*(-x0 + x0**2) + x0** ...
 1000           4000        2.24374    [3.43618]    [x0*(-x0*c1 + x0**2*(-x0 + x0**2) + x0** ...
 1100           4400        2.24372    [3.43479]    [x0*(-x0*c1 + x0**2*(-x0 + x0**2) + x0** ...
 1200           4800      0.0697188    [3.35616]    [x0*(x0 + x0**2*(-c1 + x0**2))] ...
 1300           5200      0.0254527    [3.37625]    [x0*(x0 + x0**2*(-c1 + x0**2))] ...
Gen is the generation number, Fevals the number of function evaluation used, Best is the best fitness found, Constants contains the value of the ephemeral constants and Formula peeks into the prettier expression of the underlying CGP.

Parameters

level – verbosity level

inline unsigned get_verbosity() const

Gets the verbosity level.

Returns

the verbosity level

inline std::string get_name() const

Algorithm name.

Returns

a string containing the algorithm name

inline std::string get_extra_info() const

Extra info.

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 es4cgp::log_line_type as described in es4cgp::set_verbosity().

Returns

an std::vector of es4cgp::log_line_type containing the logged values.

template<typename Archive>
inline void serialize(Archive &ar, unsigned)

Object serialization.

This method will save/load this into the archive ar.

Parameters

ar – target archive.

Throws

unspecified – any exception thrown by the serialization of the expression and of primitive types.