GAFramework: a genetic algorithm framework with multi-threading

GAFramework is a framework for writing genetic algorithms in Julia. It supports parallelism by calculating crossovers and fitness using Julia's multi-threading capabilities.

Since GAFramework stores the entire state of your genetic algorithm in an object, it allows you to save the entire state to file. It allows you to continue running your GA after you load your state from file or after you stop at a generation. It allows you to change parameters such as crossover/mutation parameters after you stop at a generation and then continue from where you stopped.

GAFramework is replicable with respect to pseudo-randomness. So, if you specify a random number generator, GAFramework will fully replicate your GA run as long as the number of threads used is the same for both runs.

GAFramework also contains a genetic algorithm implementation that "minimizes" any function f : R^n -> R over a box in a Coordinate space.

Installation

using Pkg; Pkg.add("GAFramework")

Implementing a GA for a specific problem

To create a GA for a specific problem, we need to create a concrete sub-type of GAModel, and then create relevant functions for the sub-types.

To demonstrate this, we create a GA for optimizing a function over a box in a Coordinate space, i.e., a function f : R^n -> R.

First, we import the GAFramework module and import relevant functions.

using GAFramework
import GAFramework: fitness, genauxga, crossover!, mutation!, selection,
randcreature, printfitness, savecreature

Next, we create a sub-type of GAModel, which contains the function f, the corners of the box (xmin and xmax), and the span of the box (xspan). It also contains the clamp field: if clamp = true then we will clamp mutated or crossovered points back into the box, so that our solutions will be inside the box; otherwise, our solutions will not be constrained.

struct FunctionModel{F,T} <: GAModel
    f::F
    xmin::T
    xmax::T
    xspan::T # xmax-xmin
    clamp::Bool
end

function FunctionModel(f::F,xmin,xmax,clamp::Bool=true) where {F}
        xspan = xmax .- xmin
    FunctionModel{F,typeof(xspan)}(f,xmin,xmax,xspan,clamp)
end

Then, we create a type, which contains the "chromosomes" of the creature (value field) and the objective value of the function (objvalue field). We calculate the objective value when creating a CoordinateCreature{T} object.

struct CoordinateCreature{T}
    value :: T
    objvalue :: Float64
end

CoordinateCreature(value::T, model::FunctionModel{F,T}) where {F,T} =
    CoordinateCreature{T}(value, model.f(value))

Genetic algorithms maximize the fitness function. Since we are minimizing the objective value, we set fitness to be negative of the objective value. Depending on the selection function used, fitness(::CoordinateCreature) might need to be non-negative, be a probability value, etc. The bulk of the calculation should be relegated to when the CoordinateCreature{T} object is created; the fitness function below, since it will be repeatedly called during selection and sorting, should be a very fast and simple function such as identity or negation.

fitness(x::CoordinateCreature) = -x.objvalue

The following creates a randomly generated CoordinateCreature object. It creates a random point drawn with uniform probability from the box. Note: aux is used to store auxiliary scratch space in case we want to minimize memory allocations. aux can be created by overloading the genauxga(model::FunctionModel) function, which is used to produce memory-safe (with respect to multi-threading) auxiliary scratch space. In this example, we do not need any scratch space.

randcreature(m::FunctionModel{F,T}, aux, rng::AbstractRNG) where {F,T} =
    CoordinateCreature(m.xmin .+ m.xspan .* rand(rng,length(m.xspan)), m)

The following defines the crossover operator. We define a crossover as the average of two points (not the greatest crossover operator). Note: we re-use memory from the z object when creating the new CoordinateCreature.

function crossover!(z::CoordinateCreature{T}, x::CoordinateCreature{T},
                   y::CoordinateCreature{T}, st::GAState,
                   aux, rng::AbstractRNG) where {T}
              z.value[:] = 0.5 .* (x.value .+ y.value)
              CoordinateCreature(z.value, st.model)
end

The following defines the mutation operator. We draw a vector from a circular normal distribution, scale it by the box, and shift the original point with the drawn vector (again, not the greatest mutation operator). Clamping is optionally done to restrict points to be inside the box.

function mutation!(x::CoordinateCreature{T}, m::FunctionModel{F,T},
                params, curgen, aux, rng) where {F,T}
    if rand(rng) < params[:rate]
        x.value .+= 0.01 .* m.xspan .* randn(rng,length(x.value))
        if m.clamp
            x.value .= clamp.(x.value, m.xmin, m.xmax)
        end
        CoordinateCreature(x.value, m)
    else
        x
    end
end

We use tournament selection as our selection operator.

selection(pop::Vector{<:CoordinateCreature}, n::Integer, rng) =
    selection(TournamentSelection(2), pop, n, rng)

This defines how to print details of our creature in a compressed form.

printfitness(curgen::Integer, x::CoordinateCreature) =
    println("curgen: $curgen value: $(x.value) obj. value: $(x.objvalue)")

This defines how to save our creature to file. GAFramework will save the best creature to file using this function.

savecreature(file_name_prefix::AbstractString, curgen::Integer,
             creature::CoordinateCreature, model::FunctionModel) =
    save("$(file_name_prefix)_creature_$(curgen).jld", "creature", creature)

In summary, we can implement a new GA using the following code.

module CoordinateGA

using GAFramework
import GAFramework: fitness, crossover!, mutation!, selection, randcreature
using Random

struct FunctionModel{F,T} <: GAModel
    f::F
    xmin::T
    xmax::T
    xspan::T # xmax-xmin
    clamp::Bool
end

function FunctionModel(f::F,xmin,xmax,clamp::Bool=true) where {F}
        xspan = xmax .- xmin
    FunctionModel{F,typeof(xspan)}(f,xmin,xmax,xspan,clamp)
end

struct CoordinateCreature{T}
    value :: T
    objvalue :: Float64
end

CoordinateCreature(value::T, model::FunctionModel{F,T}) where {F,T} =
    CoordinateCreature{T}(value, model.f(value))

fitness(x::CoordinateCreature) = -x.objvalue

randcreature(m::FunctionModel{F,T}, aux, rng::AbstractRNG) where {F,T} =
    CoordinateCreature(m.xmin .+ m.xspan .* rand(rng,length(m.xspan)), m)

function crossover!(z::CoordinateCreature{T}, x::CoordinateCreature{T},
                   y::CoordinateCreature{T}, st::GAState,
                   aux, rng::AbstractRNG) where {T}
              z.value[:] = 0.5 .* (x.value .+ y.value)
              CoordinateCreature(z.value, st.model)
end

function mutation!(x::CoordinateCreature{T}, m::FunctionModel{F,T},
                params, curgen, aux, rng) where {F,T}
    if rand(rng) < params[:rate]
        x.value .+= 0.01 .* m.xspan .* randn(rng,length(x.value))
        if m.clamp
            x.value .= clamp.(x.value, m.xmin, m.xmax)
        end
        CoordinateCreature(x.value, m)
    else
        x
    end
end

selection(pop::Vector{<:CoordinateCreature}, n::Integer, rng) =
    selection(TournamentSelection(2), pop, n, rng)

end

A variation of this GA is in src/models/coordinatega.jl. Further examples are in src/models/permga.jl and src/models/magnaga.jl.

Running the GA

That takes care of how to implement our problem using GAFramework. Now, we define our problem by creating a FunctionModel.

For fun, we want to minimize the function x sin(1/x) over the [-1,1] interval.

model = FunctionModel(x -> x[1]==0 ? 0.0 : x[1] * sin(1/x[1]), [-1.0], [1.0])

Or, we want to minimize the function <x, sin(1/x)> in 2D Euclidean space over the [-1,1]^2 rectangle.

using LinearAlgebra

model = FunctionModel(x -> any(x.==0) ? 0.0 : dot(x, sin.(1./x)),
                         [-1.,-1.], [1.,1.])

Or, we want to minimize the function |x - (0.25,0.25,0.5,0.5,0.5)|_1 in 5-dimensional Euclidean space over the [-1,1]^5 box.

using LinearAlgebra

x0 = [0.25,0.25,0.5,0.5,0.5]
model = FunctionModel(x -> norm(x-x0,1),
                         [-1.,-1.,-1.,-1.,-1], # minimum corner
                         [1.,1.,1.,1.,1]) # maximum corner in box

Here, we create the GA state, with population size 1000, maximum number of generations 100, fraction of elite creatures 0.01, and mutation rate 0.1, printing the objective value every 10 iterations. The GAState function generates the population and state contains all data required to start/restart a GA. Each generation, the GA will create children (using crossover!) from selected (using selection) parents, replace the non-elites in the current generation with the children (with respect to fitness), and then mutate everyone in the population (using mutation!).

state = GAState(model, ngen=100, npop=1000, elite_fraction=0.01,
    params = Dict(:mutation_rate =>0.1, :print_fitness_iter => 10))

This runs the GA and we are done.

ga!(state)

state.pop[1] gives you the creature with the best fitness.

A version of FunctionModel and CoordinateCreature are included GAFramework. It can be used by executing the statement using GAFramework.CoordinateGA.

Restarting

After we finish a GA run using ga!(state), if we decide that we want to continue optimizing for a few more generations, we can do the following. Here, we change maximum number of generations to 200, and then restart the GA, continuing on from where the GA stopped earlier.

state.ngen = 200

ga!(state)

Replicability with respect to pseudo-randomness

Although GAFramework uses pseudo-random numbers for many operations, we can replicate a GA run using the rng option and by using only the random number generators provided by the functions to generate random numbers. Setting rng to be an object that is a sub-type of AbstractRNG will percolate it throughout the GA, allowing us to replicate a run. By default, rng is set to MersenneTwister(rand(UInt)).

state1 = GAState(model, ngen=100, npop=1000, elite_fraction=0.01,
    params = Dict(:mutation_rate => 0.1, :print_fitness_iter => 10),
    rng=MersenneTwister(12))
best1 = ga!(state1)

state2 = GAState(model, ngen=100, npop=1000, elite_fraction=0.01,
    params = Dict(:mutation_rate => 0.1, :print_fitness_iter => 10),
    rng=MersenneTwister(12))
best2 = ga!(state2)

println(all([getfield(state1,x) == getfield(state2,x) for x in fieldnames(GAState)]))
# true
println(best1 == best2)
# true

Saving creature to file

We can save the creature to file every 10 iterations using the following.

state = GAState(m, ngen=100, npop=1000, elite_fraction=0.01,
    params = Dict(:mutation_rate => 0.1, :print_fitness_iter => 10,
        :save_creature_iter => 10, :file_name_prefix="minexp_6000"))

After we finish a GA run using ga!(state), and we decide that we want to save the best creature to file afterwards, we can do the following.

savecreature("minexp_6000", state.ngen, state.pop[1], model)

Saving GA state to file

This save the full GA state to file every 100 iterations using the following. Note: unfortunately, this doesn't work with FunctionModel{F,T} since it contains the function f::F as a field. It should work for other types that do not contain functions.

state = GAState(m, ngen=100, npop=1000, elite_fraction=0.01,
    params = Dict(:mutation_rate => 0.1, :print_fitness_iter => 10,
        :save_creature_iter => 100, :file_name_prefix="minexp_6000"))

If something happens during the middle of running ga!(state), we can reload the state from file from the 100th generation as follows, and then restart the GA from the saved generation.

state = loadgastate("minexp_6000_state_100.jld")

ga!(state)

We can also directly save the state using the following.

savegastate("minexp_6000", state.ngen, state)