-
Notifications
You must be signed in to change notification settings - Fork 2
/
genetic.py
76 lines (59 loc) · 2.24 KB
/
genetic.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
"""
Genetic Algorithm Builder
"""
import pdb
from random import randint, random
from Gene import Gene
MUTATION_RATE = 0.0001
def binsearch(items, val, get=lambda x: x):
"""
Returns the item in items whose bucket contains val - assumes items is (item, bottom of bucket)
"""
low, high = 0, len(items)-1
while ((high - low) > 1):
if val < get(items[(low+high)/2]):
high = (low+high)/2
elif val == get(items[(low+high)/2]):
low = high = (low+high)/2
else:
low = (low+high)/2
return items[high]
def roulette(items, num, get=lambda x: x):
"""
Runs a roulette selection algorithm on the items in the list given.
The algorithm is roughly a binary search on the list to find out which item is to be selected (with random values)
"""
max_value = max(items, key=get)
selection = [ binsearch(items, random() * (get(max_value)), get) for i in xrange(num)]
return selection
def evolve(population, population_limit=100, mutation_rate=0.1):
"""
Evolve the initial population a generation at a time
Expects that the input population is a class that computes
the fitness and mates two members
"""
# Initialise the algorithm
population.sort(key = lambda x: x.fitness, reverse=True)
while(True):
# Select Breeders
# At this point the population is already sorted!
# Construct a "cdf"
sum = 0
items = []
for x in population:
sum += x.fitness
items.append((x, sum))
population_size = len(population)
matables = roulette(items, population_size, lambda x: x[1])
mating_pairs = [(matables[i][0], matables[i+len(matables)/2][0]) for i in xrange(len(matables)/2)]
# Mate Pairs
for pair in mating_pairs:
children = pair[0].mate(pair[1])
if random() < mutation_rate:
children = [child.mutate() for child in children]
population += children
# Select fittest
population.sort(key = lambda x: x.fitness, reverse=True)
if(len(population) > population_limit):
population[:] = population[0:population_limit]
yield population