In [22]:
%matplotlib inline
import matplotlib
import numpy as np
import matplotlib.pyplot as plt
import json
In this training, I want to focus on the algorithm and not on its performance, this will be for a later study-case.
Artificial intelligence has always been present in games, so the player can play even alone. Finding some complex problems to solve shouldn't be a hard task.
Let's take a real game and try to make an artificial intelligence which solves the game. I choosed a french TV game "Le compte est bon". Let's explains the rules:
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100]+ - * / and the 6 numbers, you have to find the goal number247[3, 5, 7, 100, 25, 1]3 * 7 = 21
5 * 25 = 125
125 + 21 = 146
146 + 100 = 246
246 + 1 = 247We can represent the whole calcul in one line : (3 * 7) + (5 * 25) + 100 + 1
Which can also be represented as a tree :
+
/ \
1 +
/ \
100 +
/ \
/ \
* *
/ \ / \
3 7 5 25Genetic programming consists on applying the rules of genetic evolution to our algorithm.
On a random population, we determine which candidate solves the problem the best. This step is called evaluation.
The next step is to select the candidates that will be the parents of the next generation. This step is called selection.
We select random parts of both parents DNA to build a new one, and then apply a random mutation so the new candidate is unique.
We repeat this process until we have a new population to evaluate.
The most important part is in the selection step. Once we scored each candidate in the evaluation step we obviously must select the bests to make sure the next generation is closer to the answer.
But building an elite will prevents DNA diversity and the population could never find the solution.
It is important also to include less good candidate, as they can carry intersting genes to pass.
Lets say we have randomly generated a set of tree :
* *
/ \ / \
1 - 7 +
/ \ / \
100 + 100 +
/ \ / \
/ \ / \
+ / - /
/ \ / \ / \ / \
3 7 25 5 3 25 5 1Those tree could represent the DNA of our population. Genes would be each operators and links to the leafs.
We can easily select part of each tree to insert into a new one as in DNA combination. Then randomly change an operator or switch leafs as in random mutation.
Evaluation would consist on parsing the tree, and get the distance to the goal number : abs(goal - tree_result).
In [23]:
import random
elements = list(range(1, 11)) * 2 + [25, 50, 75, 100]
game = random.sample(elements, 6)
goal = random.randint(100, 999)
print goal, ':', game
Now, we need to generate our population, this means for each candidate we will generate random DNA :
In [26]:
# the DNA is just the calcul in a string
def random_dna(game):
# we want random links to node, so we need to shuffle the game
game_shuffled = list(game)
random.shuffle(game_shuffled)
# let start with an empty dna
dna = ''
i = 0
while i < len(game_shuffled):
try_dna = dna
if i > 0:
try_dna += random.choice([' * ', ' / ', ' + ', ' - '])
try_dna += str(float(game_shuffled[i]))
# we check that the result is still an int before recording the random gene
check_result = eval(try_dna)
if check_result == int(check_result):
dna = try_dna
i += 1
return dna
test_dna = random_dna(game)
test_res = eval(test_dna)
assert test_res == int(test_res)
population_size = 1000
def first_generation(population_size=1000):
return [random_dna(game) for _ in range(population_size)]
population = first_generation(population_size)
In [27]:
print 'Test:', test_dna, '=', test_res
print 'Population Size:', population_size
print 'Population:'
for dna in population[:5]:
print '->', dna, ' = ', eval(dna)
print '-> ...'
for dna in population[-5:]:
print '->', dna, ' = ', eval(dna)
Now, we would like to score our population :
In [28]:
def score(dna):
return abs(goal - eval(dna))
scored_population = sorted([(dna, score(dna)) for dna in population], key=lambda item: item[1])
In [29]:
def show_scored_population(scored_population):
for dna, score in scored_population[:5]:
print '->', dna, ' = ', eval(dna), '\t|', score
print '-> ...'
for dna, score in scored_population[-5:]:
print '->', dna, ' = ', eval(dna), '\t|', score
show_scored_population(scored_population)
If we are lucky, we have found the solution on the first generation. But it is unlikely on more complex problems.
For the fun lets make some stats of the generation:
In [30]:
from collections import OrderedDict
import math
def generation_stats(generation):
scores = [c[1] for c in generation]
stats = OrderedDict((
('avg', float(sum(scores)) / len(scores)),
('min', min(scores)),
('max', max(scores)),
('stdev', None),
('q1', None),
('med', None),
('q3', None)
))
variance = float(sum([(s - stats['avg'])**2 for s in scores])) / len(scores)
stats['stdev'] = math.sqrt(variance)
q1idx = len(scores) / 4
stats['q1'] = scores[q1idx]
q3idx = 3 * len(scores) / 4
stats['q3'] = scores[q3idx]
if len(scores) % 2 == 0:
i1idx = len(scores) / 2
i2idx = i1idx + 1
i1, i2 = scores[i1idx], scores[i2idx]
stats['med'] = (i1 + i2) / 2
else:
medidx = len(scores) / 2 + 1
stats['med'] = scores[medidx]
return stats, scores
In [31]:
def plot_stats(stats, scores, gen=0):
rows = zip(*stats.items())
dim = [0.05, 0.80, 0.9, 0.15]
# Figure 1: min avg/q3 max color graph
fig1 = plt.figure(figsize=(18, 3))
a1x = fig1.add_axes(dim)
cmap1 = matplotlib.colors.ListedColormap(['g', 'b', 'r'])
bounds1 = [
stats['min'],
min(stats['q3'], stats['avg']),
max(stats['q3'], stats['avg']),
stats['max']
]
norm1 = matplotlib.colors.BoundaryNorm(bounds1, cmap1.N)
cbl1 = matplotlib.colorbar.ColorbarBase(
a1x,
cmap=cmap1, norm=norm1,
spacing='proportional',
orientation='horizontal'
)
# Figure 2: min q1 med q3 color graph
fig2 = plt.figure(figsize=(18, 3))
a2x = fig2.add_axes(dim)
cmap2 = matplotlib.colors.ListedColormap(['g', 'b', 'y'])
bounds2 = [stats['min'], stats['q1'], stats['med'], stats['q3']]
norm2 = matplotlib.colors.BoundaryNorm(bounds2, cmap2.N)
cbl2 = matplotlib.colorbar.ColorbarBase(
a2x,
cmap=cmap2, norm=norm2,
spacing='proportional',
orientation='horizontal'
)
a1x.set_xticklabels([
'min',
'avg' if stats['avg'] <= stats['q3'] else 'q3',
'avg' if stats['avg'] > stats['q3'] else 'q3',
'max'
])
a2x.set_xticklabels(['min', 'q1', 'med', 'q3', 'max'])
# Figure 3: scores line chart
fig3, a3x = plt.subplots()
a3x.plot(scores)
a3x.grid(True)
a3x.set_ylabel('Score')
a3x.set_xlabel('Candidate')
a1x.set_title('Generation: {0}'.format(gen))
plt.show()
In [32]:
stats1, scores1 = generation_stats(scored_population)
print json.dumps(stats1, indent=2)
plot_stats(stats1, scores1)
Now that we have our first generation and we know what it looks like, we can proceed to selection.
If we just generate a new random population, our algorithm would be nothing else than a bruteforce.
The selection step makes everything. So how do we proceed ?
After a few runs, it looks like the distance from the goal grows slowly except a very few number of with an enormous distance due to random.
This is good! This means we have a lot of interesting solutions. Let's try the following approach for selection : the 50% best candidates of each quartile in this generation.
In [33]:
def selection(generation, stats):
parents = []
q1 = filter(lambda c: c[1] < stats['q1'], generation)
q2 = filter(lambda c: stats['q1'] <= c[1] < stats['med'], generation)
q3 = filter(lambda c: stats['med'] <= c[1] < stats['q3'], generation)
q4 = filter(lambda c: stats['q3'] <= c[1], generation)
for q in [q1, q2, q3, q4]:
parents += q[:len(q) / 2]
return parents
In [34]:
s1 = selection(scored_population, stats1)
show_scored_population(s1)
In [35]:
stats_s1, scores_s1 = generation_stats(s1)
print json.dumps(stats_s1, indent=2)
plot_stats(stats_s1, scores_s1)
In this part, we will parse the DNA code of each candidates of s1 in order to build the tree.
Because it is a simple calcul, it is also a valid Python code. We could use the library RedBaron, lets import it:
In [36]:
from redbaron import RedBaron, BinaryOperatorNode, FloatNode
red = RedBaron(s1[0][0])
print 'Example:', s1[0][0]
red.help()
Now we need to parse a pair of candidates, in order to return a new one. How do we proceed ?
I suggest that :
b's DNA into child cBinaryOperatorNode in parent a's DNA and find all FloatNode() it containsc's DNA, as well as the useless operatorswe insert the choosen BinaryOperatorNode into c's DNA with a new randomly choosen BinaryOperatorNode
Example :
Step 1:
* *
/ \ / \
1 - 7 +
/ \ / \
100 (+) 100 +
/ \ / \
/ \ / \
+ / - /
/ \ / \ / \ / \
3 7 25 5 3 25 5 1Step 2:
* *
/ \ / \
1 - x +
/ \ / \
100 (+) 100 +
/ \ / \
/ \ / \
+ / - /
/ \ / \ / \ / \
3 7 25 5 x x x 1
* +
/ \ / \
1 - 100 1
/ \
100 (+)
/ \
/ \
+ /
/ \ / \
3 7 25 5Step 3:
*
/ \
+ \
/ \ \
100 1 +
/ \
/ \
+ /
/ \ / \
3 7 25 5
In [ ]:
def gen_child(parents_dna):
# reimport things because it will be used in a IPython parallel engine
from redbaron import RedBaron
import random
tmpred = RedBaron(parents_dna[0])
child = RedBaron(parents_dna[1])
# Choose random operator from parent a
operators = tmpred.find_all('binary_operator')
op = random.choice(operators[1:]) # we don't want the root operator
# Find and remove all leafs from child
nbs = [float(nb.value) for nb in op.find_all('float')]
# mark the nodes as empty
for node in child.find_all('float'):
if float(node.value) in nbs:
if node.parent.first is node:
node.parent.first.replace('None')
elif node.parent.second is node:
node.parent.second.replace('None')
# keep going until nothing is done (which means there is no more empty nodes)
reparented = True
while reparented:
reparented = False
for node in child.find_all('binary_operator'):
if node.first.value == 'None' and node.second.value == 'None':
reparent = 'None'
elif node.first.value == 'None':
reparent = node.second.dumps()
elif node.second.value == 'None':
reparent = node.first.dumps()
else:
continue
if node.parent.parent is None:
node.replace(reparent)
reparented = True
elif node.parent.first is node:
node.parent.first.replace(reparent)
reparented = True
elif node.parent.second is node:
node.parent.second.replace(reparent)
reparented = True
# Combine parents DNA with a mutation: a random operator
notint = True
while notint:
combine = '{0} {2} {1}'.format(
op.dumps(),
child[0].dumps(),
random.choice(['+', '-', '*', '/'])
)
res = eval(combine)
if res == int(res):
notint = False
child[0].replace(combine)
print '.'
return child.dumps()
In [38]:
child = gen_child((s1[0][0], s1[-1][0]))
test_child = eval(child)
assert test_child == int(test_child)
print child, '=', test_child
Now that we are able to generate a child from two parents, let's make our couples:
In [39]:
def make_couples(selected):
parents = []
for _ in range(4):
_set = list(selected)
while len(_set) > 1:
i = random.randrange(0, len(_set))
a = _set.pop(i)
i = random.randrange(0, len(_set))
b = _set.pop(i)
parents.append((a[0], b[0]))
return parents
And generate our new population:
In [61]:
def new_population(selected, population_size):
population = []
couples = make_couples(selected)
while len(population) < population_size:
parents = random.choice(couples)
population.append(gen_child(parents))
return population
In [ ]:
def next_generation(population, gen):
scored_population = sorted([(dna, score(dna)) for dna in population], key=lambda item: item[1])
show_scored_population(scored_population)
for i in range(len(scored_population)):
if scored_population[i][1] == 0:
print 'WIN:', i, ':', scored_population[i][0]
else:
break
stats, scores = generation_stats(scored_population)
print json.dumps(stats, indent=2)
plot_stats(stats, scores, gen)
selected = selection(scored_population, stats)
return new_population(selected, len(population)), gen + 1
In [ ]:
def main(popsize=1000, nsteps=100):
pop, gen = first_generation(popsize), 0
while nsteps > 0:
pop, gen = next_generation(pop, gen)
nsteps -= 1
In [ ]:
main(popsize=10, nsteps=30)
In [ ]:
In [ ]: