Variation operators#
Variation operators are used in evolutionary algorithms to
produce new decision vectors, called offspring, from
existing ones, called parents.
This usually happens in two steps: first, a crossover operator combines the
parents to produce one or more offspring, and then a mutation operator randomly
changes some of the offspring’s decision variables. We currently provide a
number of crossover operators.
Every operator takes a 2D array with one
decision vector per row and accepts a seed for reproducible results. The
crossover example shows
the behaviour of the crossover operators.
Crossover#
|
Uniform crossover. |
|
Single-point crossover. |
|
Blend crossover (BLX-\(\alpha\)). |
|
Single arithmetic crossover. |
|
Local crossover. |
|
Bounded exponential crossover (BEX). |
|
Differential evolution crossover (DE/rand/1/bin). |
|
Differential evolution crossover used by MOEA/D-DE (DE/current/1). |
|
Parent-centric crossover (PCX). |
The operators differ in how many parents one crossover operation uses and how many offspring it produces:
Function |
Offspring per operation |
Parents per operation |
|---|---|---|
2 |
2 |
|
2 |
2 |
|
1 |
2 |
|
2 |
2 |
|
2 |
2 |
|
2 |
2 |
|
1 |
1, plus 3 other parents chosen at random |
|
1 |
1, plus 2 other parents chosen at random |
|
1 |
1, plus 2 other parents chosen at random |
The functions that use 2 parents per operation take a matrix parents and
cross over rows 2i and 2i + 1, so the order of the rows decides which
parents are crossed over, for example after a selection step. If the number
of rows is odd, the last row is crossed over with the first one.
When an
operation produces 2 offspring, the output has as many rows as parents, and
one offspring is dropped when the number of rows is odd.
blend_alpha_crossover() returns one row per pair.
The functions that use 1 parent per operation take a matrix population and
the row indices targets of the parents, and return one offspring per target.
They choose the other parents at random from population.
Differential evolution (DE) comes in two variants that are common in
multi-objective optimization. de_rand_1_bin_crossover() is the
DE/rand/1/bin scheme of Storn and Price[1], which most Pareto-based
multi-objective DE algorithms use [2].
de_current_1_crossover() is the operator of MOEA/D-DE
[3]. It starts from the target instead of a
random row and does not force any variable to change. Its 2 other parents may
include the target itself. Tanabe and Ishibuchi (2019) call this mutation the current/1
strategy, a term introduced by Gong et al. (2017).
Certain crossover operators tend to produce offspring that are close to one
or the other parent.
Operators that produce 2 offspring from 2 parents or 1 offspring from 1 parent
preserve the order, so that the index of an offspring corresponds to the index
of the parent it is closest to, assuming a parent-centric crossover operation.
For the operators that take population, the parent of offspring i is
row targets[i].
Random seeds#
Every operator takes a seed. With an integer seed, the operator draws the
same random numbers on every call. This makes a single call reproducible, but
in an evolutionary algorithm every generation would reuse the same random
numbers. Instead, create one numpy.random.Generator at the start of a
run and pass it as seed to every call. Each call then draws a new seed
from the generator, and the seed of the generator still reproduces the whole
run:
rng = np.random.default_rng(42)
for generation in range(n_generations):
parents = ... # Select and order the parents.
offspring = moocore.uniform_crossover(parents, seed=rng)
...
With seed=None, every call uses a new random seed, so the results cannot be
reproduced.