Simple genetic algorithm

genetic.py

import random
import string
from time import sleep


POSSIBLE_CHARS = string.ascii_letters + string.punctuation + " "


def evolve(population, pop_count, crossover_mutation_ratio):
    def swap(src, dst, i, j=None):
        if j is None:
            j = i
        src[i], dst[j] = dst[j], src[i]

    remaining = pop_count - len(population)
    l = len(population[0])

    # crossover
    for _ in xrange(remaining):

        # choose 2 random clones
        e1, e2 = map(lambda e: e[:], random.sample(population, 2))

        # randomly swap a few
        for _ in xrange(random.randrange(l / 2, l)):
            i = random.randrange(0, l)
            swap(e1, e2, i)

        # add to population
        population.append(e1)

    # mutate
    for entity in population:
        chance = random.random()
        # random swap
        if chance < crossover_mutation_ratio[1]/2:
            i, j = random.randrange(0, l), random.randrange(0, l)
            swap(entity, entity, i, j)

        # new random char
        elif chance < crossover_mutation_ratio[1]:
            i = random.randrange(0, l)
            entity[i] = random.choice(POSSIBLE_CHARS)


def run(pop_count, crossover_mutation_ratio, create_func, fitness_func, complete_func, stringify_func):

    assert pop_count > 3
    assert all(x > 0 for x in crossover_mutation_ratio)

    # create random initial population
    population = [create_func() for _ in xrange(pop_count)]
    generation = 0
    while True:
        generation += 1

        # evaluate fitness
        fitness = []
        for entity in population:
            x = fitness_func(entity)
            fitness.append((entity, x))

        # sort by fitness
        sorted_population = [x[0] for x in sorted(fitness, key=lambda f: f[1], reverse=True)]

        # complete?
        best = fitness[0]
        if complete_func(best):
            print "The winner is %s with a fitness of %s (generation %d)!" % (stringify_func(best[0]), str(best[1]), generation)
            break

        # print out best
        if generation % 10 == 0:
            print("%5d : %s (%f)" % (generation, stringify_func(best[0]), best[1]))

        # choose top 10
        count = pop_count // 2
        new_pop = sorted_population[:count]

        # crossover, then mutate randomly
        evolve(new_pop, pop_count, crossover_mutation_ratio)

        # repeat
        del population[:]
        population = new_pop

        sleep(0.01)


def list_cmp_fitness(x, target):
    total = 0
    for xc, tc in zip(x, target):
        total += abs(ord(tc) - ord(xc)) ** 2

    return -total


def main():
    goal = list("These words are breeding")

    count = 200
    crossover_mutation_ratio = (0.5, 0.2)
    fitness = lambda l: list_cmp_fitness(l, goal)
    create = lambda: [random.choice(POSSIBLE_CHARS) for _ in xrange(len(goal))]
    complete = lambda (best, fitness): fitness == 0
    stringify = lambda l: ''.join(l)

    run(count, crossover_mutation_ratio, create, fitness, complete, stringify)


if __name__ == "__main__":
    main()