Simple Genetic Algorithm#

class 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 strategy 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 mutation 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.

Note

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

Warning

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

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:
           20        6605.75         415.95
           60        6189.79        500.359
           80        5689.44        477.663
          100        5211.77        218.231
          120        4993.54        421.684
          160        4571.86        246.532
          200        4325.33        166.685
          220        4158.64        340.382
          280        3818.26        294.232
          300        3524.03        55.0358
          320        3468.99        452.544
          340        3016.45        16.7273
          380        2999.72         150.68
          420        2849.04        301.156
          440        2547.88        1.25038
          460        2546.63        192.561
          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