Simple Genetic Algorithm
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 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_schromosomes 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
crup 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
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_mand 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.
The algorithm is not suitable for multi-objective problems, nor for constrained optimization.
Most genetic operators use the lower and upper bound information. Hence, unbounded problems will produce undefined behaviours.
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.
typedef std::tuple<unsigned, unsigned long long, double, double> log_line_type
Single entry of the log (gen, fevals, best, improvement)
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())
Constructs a simple genetic algorithm.
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
std::invalid_argument – if
crnot in [0,1],
eta_cnot in [1, 100],
mnot in [0,1],
mutationnot one of “gaussian”, “uniform” or “polynomial”,
selectionnot one of “roulette” or “truncated”
crossovernot one of “exponential”, “binomial”, “sbx” or “single”, if
param_mis not in [0,1] and
mutationis not “polynomial” or
mutationis not in [1,100] and
population evolve(population) const
Algorithm evolve method.
Evolves the population for a maximum number of generations
pop – population to be evolved
std::invalid_argument – if the problem is multi-objective or constrained, if the population size is smaller than 2, if
param_sis larger than the population size, if the size of
popis odd and a “sbx” crossover has been selected upon construction.
Sets the seed.
seed – the seed controlling the algorithm stochastic behaviour
inline unsigned get_seed() const
Gets the seed.
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().
0: no verbosity
1: will only print and log when the population is improved
>1: will print and log one line each
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
level – verbosity level
inline unsigned get_verbosity() const
Gets the verbosity level.
the verbosity level
inline std::string get_name() const
a string containing the algorithm name
std::string get_extra_info() const
a string containing extra info on the algorithm
inline const log_type &get_log() const
A log containing relevant quantities monitoring the last call to evolve. Each element of the returned
std::vectoris a sga::log_line_type containing: Gen, Fevals, Current best, Best as described in sga::set_verbosity().
std::vectorof sga::log_line_type containing the logged values Gen, Fevals, Best improvement
- typedef std::tuple<unsigned, unsigned long long, double, double> log_line_type