Genetic algorithm to evolve strings

ga_string.py

#!/usr/bin/env python
__author__ = "William Koch"
import re
import sys
import random
import numpy
from deap import algorithms
from deap import base
from deap import creator
from deap import tools

VALID_CHARS = map(ord, list(" abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"))
MAX_LENGTH = 20


def get_random_char():
    r = random.randint(0, len(VALID_CHARS)-1)
    return VALID_CHARS[r]

def gen_word(min, max):
    l = random.randint(min, max)
    return [get_random_char() for i in range(l)]
        
def evalName(individual):
    delta = len(target) - len(individual)
    if delta > 0:
        a = individual + [0]*delta
        b = target
    elif delta < 0:
        a = individual
        b = target + [0]* (delta * -1)
    else:
        a = individual
        b = target

    accum = 0
    for i in range(len(a)):
        accum += abs(a[i] - b[i])
    return accum,

def mut(individual):
    r = random.random()
    c = get_random_char()
    pos = random.randint(0, len(individual)-1)
    if r < 0.3: 
        individual.append(c)
    elif r >= 0.3 and r <= 0.6:
        individual.pop(pos)
    else:
        individual[pos] = c
    return individual, 

def mate(ind1, ind2):
    
    for i in range(min(len(ind1), len(ind2))):
        if random.random() < 0.5:
            ind1[i], ind2[i] = ind2[i], ind1[i]
    return ind1, ind2

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
# Attribute generator
toolbox.register("attr_item", get_random_char)
toolbox.register("attr_len", random.randint, 0, MAX_LENGTH)

toolbox.register("word", gen_word, 1, MAX_LENGTH)
# Structure initializers
#toolbox.register("individual", init_individual) 
#toolbox.register("individual",tools.initRepeat, creator.Individual,
#                 toolbox.attr_item, toolbox.attr_len) 
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.word)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
# Operator registering
toolbox.register("evaluate",evalName)
toolbox.register("mate", mate)
toolbox.register("mutate",mut)
toolbox.register("select",tools.selBest )

def main():
    random.seed(64)

    CXPB, MUTPB, MU, NGEN = 0.5, 0.2, 50, 1000

    pop = toolbox.population(n=MU)
    hof = tools.ParetoFront()
    
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean, axis=0)
    stats.register("std", numpy.std, axis=0)
    stats.register("min", numpy.min, axis=0)
    stats.register("max", numpy.max, axis=0)
    
    logbook = tools.Logbook()
    logbook.header = "gen", "evals", "std", "min", "avg", "max", "best"
    
    # Evaluate every individuals
    fitnesses = toolbox.map(toolbox.evaluate, pop)
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit

    hof.update(pop)
    record = stats.compile(pop)
    logbook.record(gen=0, evals=len(pop), **record)
    print(logbook.stream)

    gen = 1
    while gen <= NGEN and logbook[-1]["max"] != 0.0:
        
        # Select the next generation individuals
        offspring = toolbox.select(pop, len(pop))
        # Clone the selected individuals
        offspring = list(map(toolbox.clone, offspring))
    
        # Apply crossover and mutation on the offspring
        for child1, child2 in zip(offspring[::2], offspring[1::2]):
            if random.random() < CXPB:
                toolbox.mate(child1, child2)
                del child1.fitness.values
                del child2.fitness.values

        for mutant in offspring:
            if random.random() < MUTPB:
                toolbox.mutate(mutant)
                del mutant.fitness.values
    
        # Evaluate the individuals with an invalid fitness
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit
        
        b = map(chr, tools.selBest(pop, k=1)[0])
        w = "".join(b) 
        
        # Select the next generation population
        pop = toolbox.select(pop + offspring, MU)
        record = stats.compile(pop)
        logbook.record(gen=gen, evals=len(invalid_ind), best=w, **record)
        print(logbook.stream)

        gen += 1

    return pop, logbook

if __name__ == "__main__":
    if len(sys.argv) < 2:
        print "Specify string to evolve at command line"
    else:
        w = sys.argv[1] 
        if re.match("^[a-zA-Z ]+$", w):
            target = map(ord, list(w))
            pop, stats = main() 
            b = map(chr, tools.selBest(pop, k=1)[0])
            print "".join(b)
        else:
            print "Your string can only contain spaces and letters"