Generational GA for continuous optimisation

This tutorial details how to use the built-in Genetic Algorithm (GA) on a continuous test function.

We start by importing EvoLP. We will compute some statistics using the Logbook so we need some additional modules as well:

using Statistics
using EvoLP
using OrderedCollections

For this example we will use the Rosenbrock function, which is already included as a benchmark function in EvoLP. We can look at the documentation like so:

EvoLP.rosenbrock — Function

rosenbrock(x; b=100)

Changed since EvoLP 1.3

This is the $d$-dimensional Rosenbrock function. In previous releases, it was 2d only and had an additional keyword argument a.

Update your workflow accordingly.

The $d$-dimensional Rosenbrock banana benchmark function. With $b=100$, minimum is at $f([1, \dots, 1]) = 0$

\[f(x) = \sum_{i=1}^{d-1} \left[b(x_{i+1} - x_i^2)^2 + (x_i - 1)^2 \right]\]

source

Implementing the solution

Let's start creating the population. We can use the normal_rand_vector_pop generator, which uses a normal distribution for initialisation:

EvoLP.normal_rand_vector_pop — Function

normal_rand_vector_pop(μ, m, C; rng=Random.GLOBAL_RNG)

Generate a population of μ vector individuals using a normal distribution with means m and covariance C.

m expects a vector of length l (i.e. length of an individual) while C expects an l x l matrix of covariances.

Examples

julia> normal_rand_vector_pop(3, [0, 0], [1 0; 0 1])
3-element Vector{Vector{Float64}}:
 [-0.15290525182234904, 0.8715880371871617]
 [-1.1283800329864322, -0.9256584563613383]
 [-0.5384758126777555, -0.8141702145510666]

source

pop_size = 50
population = normal_rand_vector_pop(pop_size, [0, 0], [1 0; 0 1])
first(population, 3)

3-element Vector{Vector{Float64}}:
 [-0.8613428228755716, -0.8552445983280004]
 [0.49171416964856196, 0.6757521554274838]
 [0.5574237221631648, -0.626335954882642]

In a GA, we have selection, crossover and mutation.

We can easily set up these operators using the built-ins provided by EvoLP. Let's use rank based selection and interpolation crossover with 0.5 as the scaling factor:

EvoLP.InterpolationRecombinator — Type

Interpolation crossover with scaling parameter α.

source

S = RankBasedSelector()
C = InterpolationRecombinator(0.5)

InterpolationRecombinator(0.5)

For mutation, we can use Gaussian noise:

EvoLP.GaussianMutator — Type

Gaussian mutation with standard deviation σ, which must be a real number.

source

M = GaussianMutator(0.05)

GaussianMutator(0.05)

Now we can set up the Logbook to record statistics about our run:

statnames = ["mean_eval", "max_f", "min_f", "median_f"]
fns = [mean, maximum, minimum, median]
thedict = LittleDict(statnames, fns)
thelogger = Logbook(thedict)

Logbook(OrderedCollections.LittleDict{AbstractString, Function, Vector{AbstractString}, Vector{Function}}("mean_eval" => Statistics.mean, "max_f" => maximum, "min_f" => minimum, "median_f" => Statistics.median), NamedTuple{(:mean_eval, :max_f, :min_f, :median_f)}[])

And now we're ready to use the GA built-in algorithm:

EvoLP.GA — Function

GA(f, pop, k_max, S, C, M)
GA(logbook::Logbook, f, population, k_max, S, C, M)
GA(notebooks::Vector{Logbook}, f, population, k_max, S, C, M)

Generational Genetic Algorithm.

Arguments

f::Function: objective function to minimise.
population::AbstractVector: a list of vector individuals.
k_max::Integer: number of iterations.
S::ParentSelector: one of the available ParentSelector.
C::Recombinator: one of the available Recombinator.
M::Mutator: one of the available Mutator.

Returns a Result.

source

result = GA(thelogger, rosenbrock, population, 300, S, C, M);

Result(0.036993195014780274, [0.7578961392910342, 0.6125314244848545], [[0.8187683018392516, 0.5607335342201665], [0.7774712589334152, 0.6038685073042384], [0.8195383058866619, 0.6401695218793594], [0.7552558422438959, 0.5996214188006196], [0.8745080373855292, 0.5987358559859736], [0.6949148199074008, 0.5717454126898376], [0.8151259672573069, 0.6515686023273844], [0.7937084889030638, 0.6050724100718765], [0.7705468112038855, 0.5177547793124777], [0.778110095214055, 0.6156542835184621]  …  [0.769204020921573, 0.48531750070505847], [0.7598739849021643, 0.4369743726977168], [0.7258111133295339, 0.4703259656721003], [0.749679173106434, 0.5467808448031546], [0.7296260663863074, 0.5458807324300955], [0.7676565771124361, 0.5668509794956453], [0.8514570406278618, 0.6889526182712459], [0.8454864851886471, 0.6621403006282743], [0.7578961392910342, 0.6125314244848545], [0.8013992737637123, 0.5150101904073077]], 300, 15000, 1.747740836)

The output was suppressed so that we can analyse each part of the result separately using functions instead:

@show optimum(result)

0.036993195014780274

@show optimizer(result)

2-element Vector{Float64}:
 0.7578961392910342
 0.6125314244848545

@show f_calls(result)

thelogger.records[end]

(mean_eval = 0.9254202827726183, max_f = 4.315585400286292, min_f = 0.036993195014780274, median_f = 0.6074002425237157)

The records in the Logbook are NamedTuples. This makes it easier to export and analyse using DataFrames, for example:

using DataFrames
DataFrame(thelogger.records)

500×4 DataFrame
 Row │ mean_eval   max_f       min_f        median_f  
     │ Float64     Float64     Float64      Float64   
─────┼────────────────────────────────────────────────
   1 │ 22.0251     406.9       0.447041     6.78992
   2 │  3.61617     36.062     0.124031     1.96466
   3 │  1.13189      3.18343   0.127583     1.07601
   4 │  0.781777     1.6644    0.309661     0.711803
   5 │  0.593735     0.935043  0.294026     0.588684
   6 │  0.527621     0.766033  0.315916     0.518089
   7 │  0.522381     0.745129  0.37027      0.527158
   8 │  0.493569     0.807639  0.275269     0.498038
  ⋮ │     ⋮           ⋮            ⋮           ⋮