Simple Genetic Algorithm

class pagmo::sga

A Simple Genetic Algorithm.

../../../_images/sga.jpg

New in version 2.2.

Approximately during the same decades as Evolutionary Strategies (see pagmo::sea) were studied, a different group led by John Holland, and later by his student David Goldberg, introduced and studied an algorithmic framework called “genetic algorithms” that were, essentially, leveraging on the same idea but introducing also crossover as a genetic operator. This led to a few decades of confusion and discussions on what was an evolutionary startegy and what a genetic algorithm and on whether the crossover was a useful operator or mutation only algorithms were to be preferred.

In pagmo we provide a rather classical implementation of a genetic algorithm, letting the user choose between some selected crossover types, selection schemes and mutation types.

The pseudo code of our version is:

> Start from a pagmo::population (pop) of dimension N
> while i < gen
> > Selection: create a new population (pop2) with N individuals selected from pop (with repetition allowed)
> > Crossover: create a new population (pop3) with N individuals obtained applying crossover to pop2
> > Mutation:  create a new population (pop4) with N individuals obtained applying mutation to pop3
> > Evaluate all new chromosomes in pop4
> > Reinsertion: set pop to contain the best N individuals taken from pop and pop4

The various blocks of pagmo genetic algorithm are listed below:

Selection: two selection methods are provided: “tournament” and “truncated”. Tournament selection works by selecting each offspring as the one having the minimal fitness in a random group of size param_s. The truncated selection, instead, works selecting the best param_s chromosomes in the entire population over and over. We have deliberately not implemented the popular roulette wheel selection as we are of the opinion that such a system does not generalize much being highly sensitive to the fitness scaling.

Crossover: four different crossover schemes are provided: “single”, “exponential”, “binomial”, “sbx”. The single point crossover, called “single”, works selecting a random point in the parent chromosome and inserting the partner chromosome thereafter. The exponential crossover is taken from the algorithm differential evolution, implemented, in pagmo, as pagmo::de. It essentially selects a random point in the parent chromosome and inserts, in each successive gene, the partner values with probability cr up to when it stops. The binomial crossover inserts each gene from the partner with probability cr. The simulated binary crossover (called “sbx”), is taken from the NSGA-II algorithm, implemented in pagmo as pagmo::nsga2, and makes use of an additional parameter called distribution index eta_c.

Mutation: three different mutations schemes are provided: “uniform”, “gaussian” and “polynomial”. Uniform mutation simply randomly samples from the bounds. Gaussian muattion samples around each gene using a normal distribution with standard deviation proportional to the m_param_m and the bounds width. The last scheme is the polynomial mutation.

Reinsertion: the only reinsertion strategy provided is what we call pure elitism. After each generation all parents and children are put in the same pool and only the best are passed to the next generation.

Warning

The algorithm is not suitable for multi-objective problems, nor for constrained optimization.

Note

Most genetic operators use the lower and upper bound information. Hence, unbounded problems will produce undefined behaviours.

See also

Oliveto, Pietro S., Jun He, and Xin Yao. “Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results.” International Journal of Automation and Computing 4.3 (2007): 281-293.

Public Types

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

Single entry of the log (gen, fevals, best, improvement)

typedef std::vector<log_line_type> log_type

The log.

Public Functions

sga(unsigned gen = 1u, double cr = .90, double eta_c = 1., double m = 0.02, double param_m = 1., unsigned param_s = 2u, std::string crossover = "exponential", std::string mutation = "polynomial", std::string selection = "tournament", unsigned seed = pagmo::random_device::next())

Constructor.

Constructs a simple genetic algorithm.

Parameters
  • gen – number of generations.

  • cr – crossover probability.

  • eta_c – distribution index for “sbx” crossover. This is an inactive parameter if other types of crossovers are selected.

  • m – mutation probability.

  • param_m – distribution index (“polynomial” mutation), gaussian width (“gaussian” mutation) or inactive (“uniform” mutation)

  • param_s – when “truncated” selection is used this indicates the number of best individuals to use. When “tournament” selection is used this indicates the size of the tournament.

  • mutation – the mutation strategy. One of “gaussian”, “polynomial” or “uniform”.

  • selection – the selection strategy. One of “tournament”, “truncated”.

  • crossover – the crossover strategy. One of “exponential”, “binomial”, “single” or “sbx”

  • seed – seed used by the internal random number generator

Throws

std::invalid_argument – if cr not in [0,1], eta_c not in [1, 100], m not in [0,1], mutation not one of “gaussian”, “uniform” or “polynomial”, selection not one of “roulette” or “truncated” crossover not one of “exponential”, “binomial”, “sbx” or “single”, if param_m is not in [0,1] and mutation is not “polynomial” or mutation is not in [1,100] and mutation is polynomial.

population evolve(population) const

Algorithm evolve method.

Evolves the population for a maximum number of generations

Parameters

pop – population to be evolved

Throws

std::invalid_argument – if the problem is multi-objective or constrained, if the population size is smaller than 2, if param_s is larger than the population size, if the size of pop is odd and a “sbx” crossover has been selected upon construction.

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

  • 1: will only print and log when the population is improved

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

Example (verbosity 1):

Gen:        Fevals:          Best:   Improvement:
   1             20        6605.75         415.95
   3             60        6189.79        500.359
   4             80        5689.44        477.663
   5            100        5211.77        218.231
   6            120        4993.54        421.684
   8            160        4571.86        246.532
  10            200        4325.33        166.685
  11            220        4158.64        340.382
  14            280        3818.26        294.232
  15            300        3524.03        55.0358
  16            320        3468.99        452.544
  17            340        3016.45        16.7273
  19            380        2999.72         150.68
  21            420        2849.04        301.156
  22            440        2547.88        1.25038
  23            460        2546.63        192.561
  25            500        2354.07        22.6248
Gen is the generation number, Fevals the number of fitness evaluations , Best is the best fitness found, Improvement is the improvement of the new population of offspring with respect to the parents.

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

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 sga::log_line_type containing: Gen, Fevals, Current best, Best as described in sga::set_verbosity().

Returns

an std::vector of sga::log_line_type containing the logged values Gen, Fevals, Best improvement