Create a gist now

Instantly share code, notes, and snippets.

Happy New Year with a simple Genetic Algorithm
import numpy as np
import random
import sys
goal = 'All work and no play makes Jack a dull boy.'
idx2c = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890,. '
c2idx = { c : i for i,c in enumerate(idx2c) }
def encode(seq):
return np.array([c2idx[c] for c in seq ])
def decode(seq):
assert len(seq) == len(goal)
try:
decoded = ''.join( [idx2c[idx] for idx in seq] )
except:
return seq
return decoded
def fitness(phrase):
return (encode(goal) == phrase).sum()
def goal_test(phrase):
return True if fitness(phrase) == len(goal) else False
def crossover(p0, p1):
len_ = len(p1)
l1, l2 = (len_//3) , 2*(len_//3)
# pieces
p0, p1 = list(p0), list(p1)
p0_ = [ p0[:l1], p0[l1:l2], p0[l2:] ]
p1_ = [ p1[:l1], p1[l1:l2], p1[l2:] ]
children = []
children.append(p0_[0] + p0_[1] + p1_[2])
children.append(p0_[0] + p1_[1] + p0_[2])
children.append(p0_[0] + p1_[1] + p1_[2])
children.append(p1_[0] + p0_[1] + p0_[2])
children.append(p1_[0] + p0_[1] + p1_[2])
children.append(p1_[0] + p1_[1] + p0_[2])
return children
def new_pop(fit_parents):
new_parents = []
for i in range(len(fit_parents)):
for j in range(len(fit_parents)):
if i != j:
new_parents.extend(crossover(fit_parents[i], fit_parents[j]))
# add mutation here
return np.array(mutate(new_parents))
def top_parents(pop):
# calculate fitness
pop_fitness = [ fitness(phrase) for phrase in pop ]
# pick the top 1%
best_parents_idx = np.array(pop_fitness).argsort()
fit_parents = pop[best_parents_idx[::-1]][:20]
return fit_parents
def mutate(pop, mut_num=2):
mutated_pop = []
for phrase in pop:
idxs = [ random.choice(range(len(phrase))) for i in range(mut_num) ]
chidxs = [ random.choice(range(len(idx2c))) for i in range(mut_num) ]
for i in range(mut_num):
phrase[idxs[i]] = chidxs[i]
mutated_pop.append(phrase)
return mutated_pop
def create_population(n, seq_len):
return np.random.randint(0,len(idx2c),[n, seq_len])
if __name__ == '__main__':
# create a population of 10 phrases
pop = create_population(1000, len(goal))
# loop till goal
i=0
while True:
i += 1
# find top 1% fit parents
fit_parents = top_parents(pop)
sys.stdout.write('\rGeneration #' + str(i) + '\t' + decode(fit_parents[0]) )
# goal test
if goal_test(fit_parents[0]):
print('\n______________________')
print(':: Evolution complete!')
print(':: Final product')
print('\n' + decode(fit_parents[0]))
print('______________________')
break
# find new population, using crossover
pop = new_pop(fit_parents)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment