Genetic Algorithm

Evolution as an algorithm

Some problems have no formula and too many possibilities to try them all, for example designing a timetable or the shape of an antenna. A genetic algorithm (GA) searches by imitating natural selection.

The loop

1. Population: start with many random candidate solutions.
2. Fitness: score each candidate.
3. Selection: pick parents, favouring higher scores. Here each parent is the winner of a random 3-way tournament.
4. Crossover: build a child by mixing the letters of two parents.
5. Mutation: with probability 0.2 each letter is replaced by a random one.
6. Elitism: the best individual is copied unchanged into the next generation.
7. Repeat until a good enough solution appears.

population ← random strings
repeat:
    sort by fitness
    new ← [best]
    while len(new) < size:
        a, b ← tournament(), tournament()
        child ← crossover(a, b)
        new.append(mutate(child))
    population ← new
until best == target

Why it works

Selection gives good letters a better chance to spread, crossover combines them in new ways, and mutation keeps supplying variety. Each generation is slightly better than the last, so a 5-letter word that has 26⁵ = 11,881,376 possibilities is typically found after only a few hundred evaluations.

Strengths and weaknesses

Compare with gradient descent, which follows a smooth slope, and with N-Queens backtracking, which tries possibilities systematically.

Code

import random, string

def evolve(target, pop_size=16, mutation=0.2, max_gen=80):
    L, A = len(target), string.ascii_uppercase
    fit = lambda s: sum(a == b for a, b in zip(s, target))
    pop = [''.join(random.choice(A) for _ in range(L)) for _ in range(pop_size)]
    for gen in range(max_gen + 1):
        pop.sort(key=fit, reverse=True)
        if pop[0] == target:
            return gen
        tour = lambda: max(random.sample(pop, 3), key=fit)
        new = [pop[0]]
        while len(new) < pop_size:
            a, b = tour(), tour()
            child = ''.join(x if random.random() < 0.5 else y for x, y in zip(a, b))
            child = ''.join(random.choice(A) if random.random() < mutation else c for c in child)
            new.append(child)
        pop = new
    return None

Common mistakes

• A mutation rate that is too low makes the population converge to a poor answer. One that is too high turns the search into random guessing.
• Forgetting elitism, so the best solution can be lost.
• A fitness function that does not reward partial progress, which gives selection nothing to work with.
• Expecting the same result every run. The algorithm is random, so use a seed to repeat an experiment.