Evolution

README.md

evolution.jl

# Two parents are better then one
# Three parents don't add much benefit on top of two
using Random
using ArgCheck

struct Entity
    genes::BitVector
end
fitness(e::Entity) = sum(e.genes)

function rand_entity(rng::AbstractRNG, ngenes)
    genes = BitVector(rand(Bool, ngenes))
    Entity(genes)
end

function procreate1(rng::AbstractRNG, e::Entity, rules)
    genes = copy(e.genes)
    mutate!!(rng, Entity(genes), rules)
end

function procreate2(rng::AbstractRNG, e1::Entity, e2::Entity, rules)
    genes = map(e1.genes, e2.genes) do g1,g2
        rand(rng, Bool) ? g1 : g2
    end
    mutate!!(rng, Entity(genes), rules)
end

function procreate3(rng::AbstractRNG, e1::Entity, e2::Entity, e3::Entity, rules)
    genes = map(e1.genes, e2.genes, e3.genes) do g1,g2,g3
        rand(rng, (g1,g2,g3))
    end
    mutate!!(rng, Entity(genes), rules)
end

struct Simulation{RNG}
    rng::RNG
    entities::Vector{Entity}
    stage::Vector{Entity}
    nparents::Int
    ngenes::Int
    nmutations::Int
end

function Simulation(rng::AbstractRNG=Random.GLOBAL_RNG;
        nentities, 
        ngenes,
        nparents,
        nmutations,
    )
    @argcheck nparents in 1:3
    entities = Entity[rand_entity(rng, ngenes) for _ in 1:nentities]
    sort!(entities, by=fitness, rev=true)
    stage = similar(entities, 2*nentities)
    Simulation(rng,entities, stage, nparents, ngenes, nmutations)
end

function mutate!!(rng::AbstractRNG, entity::Entity, rules)
    inds = eachindex(entity.genes)
    for _ in 1:rules.nmutations
        i = rand(rng, inds)
        entity.genes[i] = rand(rng, Bool)
    end
    return entity
end

function make_child(rng, entities, rules)
    if rules.nparents === 1
        e1 = rand(rng, entities)
        procreate1(rng, e1, rules)
    elseif rules.nparents === 2
        e1 = rand(rng, entities)
        e2 = rand(rng, entities)
        procreate2(rng, e1, e2, rules)
    elseif rules.nparents === 3
        e1 = rand(rng, entities)
        e2 = rand(rng, entities)
        e3 = rand(rng, entities)
        procreate3(rng, e1, e2, e3, rules)
    else
        error("Unreachable")
    end
end

function nextgen!(sim::Simulation)
    rng = sim.rng
    for i in eachindex(sim.stage)
        sim.stage[i] = make_child(rng, sim.entities, sim)
    end
    sort!(sim.stage, by=fitness, rev=true)
    sim.entities .= sim.stage[eachindex(sim.entities)]
    return sim
end



function run(sim::Simulation; ngenerations)
    fitness_histogram = fill(0, sim.ngenes+1, ngenerations)
    for j in 1:ngenerations
        for e in sim.entities
            i = sum(e.genes) + 1
            fitness_histogram[i,j] += 1
        end
        if j < ngenerations
            nextgen!(sim)
        end
    end
    return fitness_histogram
end

sim1 = Simulation(nentities=1024, ngenes=128, nparents=1, nmutations=4)
sim2 = Simulation(nentities=1024, ngenes=128, nparents=2, nmutations=4)
sim3 = Simulation(nentities=1024, ngenes=128, nparents=3, nmutations=4)
h1 = @time run(sim1, ngenerations=100)
h2 = @time run(sim2, ngenerations=100)
#h3 = @time run(sim3, ngenerations=100)
using Plots
display(heatmap(h1, xlabel="generation", ylabel="fitness", title="1 parents"))
display(heatmap(h2, xlabel="generation", ylabel="fitness", title="2 parents"))
#display(heatmap(h3, xlabel="generation", ylabel="fitness", title="3 parents"))
display(heatmap(h1 + h2, xlabel="generation", ylabel="fitness", title="1+2 parents"))
#display(heatmap(h2 + h3, xlabel="generation", ylabel="fitness", title="2+3 parents"))