Simple Genetic Algorithm
Simple Genetic Algorithm#

class sga#
A Simple Genetic Algorithm.
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 bestparam_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 probabilitycr
. The simulated binary crossover (called “sbx”), is taken from the NSGAII algorithm, implemented in pagmo as pagmo::nsga2, and makes use of an additional parameter called distribution indexeta_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.
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): 281293.
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 multiobjective 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”, ifparam_m
is not in [0,1] andmutation
is not “polynomial” ormutation
is not in [1,100] andmutation
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 multiobjective or constrained, if the population size is smaller than 2, if
param_s
is larger than the population size, if the size ofpop
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 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.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
 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

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