Skip to content

Instantly share code, notes, and snippets.

@wil3
Created April 12, 2015 21:16
Show Gist options
  • Save wil3/1671fbde4c698565040a to your computer and use it in GitHub Desktop.
Save wil3/1671fbde4c698565040a to your computer and use it in GitHub Desktop.
Genetic algorithm to evolve strings
#!/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"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment