Memetic Evolutionary Strategy (UDA)

class mes4cgp

Memetic Evolutionary Strategy for a Cartesian Genetic Program.

../../_images/neo-darwinism.jpg

The term Memetic is widely used, in the context of meta-heuristic search, to indicate a synergy between any population-based approach with local improvement procedures. The resulting algorithms are also referred to, in the literature, as Baldwinian evolutionary algorithms (EAs), Lamarckian EAs, cultural algorithms, or genetic local searches. The very same approach, is seen by many just as an hybridization of a global search technique with a local search technique. Regardless of the terminology and point of view, a memetic approach is applicable to symbolic regression tasks and able to improve considerably on the long standing issue of finding constants in Genetic Programming.

In this C++ class we offer an UDA (User Defined Algorithm for the pagmo optimization suite) hybridizing the classic Evolutionary Strategy that is traditionally used in Cartesian Genetic Programming research with a second order Newton search step able to help finding the best values for the ephemeral constants. The resulting algorithm is outlined by the following pseudo-algorithm:

See also

Izzo, Dario, Francesco Biscani, and Alessio Mereta. “Differentiable genetic programming.” In European Conference on Genetic Programming, pp. 35-51. Springer, 2017.

> Start from a population (pop) of dimension N
> while i < gen
> > Mutation: create a new population pop2 mutating N times the best individual (only the integer part is affected)
> > Life long learning: apply a one step of a second order Newton method to each individual (only the continuous part
    is affected)
> > Reinsertion: set pop to contain the best N individuals taken from pop and pop2

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 mes4cgp(unsigned gen = 1u, unsigned max_mut = 4u, double ftol = 0., unsigned seed = random_device::next())

Constructor.

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

Parameters

  • gen – number of generations.

  • max_mut – number of active genes to be mutated.

  • ftol – the algorithm will exit when the loss is below this tolerance.

  • 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_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 10): 

Gen:        Fevals:          Best:    Constants:   Formula:
   0              0        2802.82    [5.35943]    [c1**2] ...
  10             40        948.839    [10.9722]    [x0**2*c1] ...
  20             80        823.816    [8.38173]    [(c1 + x0)*x0**2] ...
  30            120        473.274    [4.48466]    [x0**3*c1] ...
  40            160        338.735    [24.2287]    [-x0 + x0**2*c1 - (c1 + x0*c1) + x0**2] ...
  50            200        107.126    [24.2287]    [x0**2*(-x0 - x0**2 + x0**3)] ...
  60            240        10.2064    [0.844799]   [x0**2*(-(c1 + x0**2) + x0**3)] ...
  70            280        10.2064    [0.844799]   [x0**2*(-(c1 + x0**2) + x0**3)] ...
  80            320         6.3605    [1.03424]    [x0**2*(x0**3*c1 - (c1 + x0**2*c1))] ...
  90            360         6.3605    [1.03424]    [x0**2*(x0**3*c1 - (c1 + x0**2*c1))] ...
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 mes4cgp::log_line_type containing: Gen, Fevals, Current best, Best as described in mes4cgp::set_verbosity().

Returns

an std::vector of mes4cgp::log_line_type containing the logged values Gen, Fevals, Current best, Best

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.