-
Notifications
You must be signed in to change notification settings - Fork 0
/
genetic.py
100 lines (83 loc) · 2.97 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from numpy.random import randint, rand
import matplotlib.pyplot as plt
OBJECTIVE = 15
POPULATION_SIZE = 200
DNA_LENGTH = 10
KILL_RATE = 0.1
NUM_CROSSOVERS = 4
MUTATION_RATE = 0.2
class Organism:
DNA = ''
def __init__(self):
for i in range(DNA_LENGTH):
self.DNA += str(randint(2))
self.fitness = self.J(self.DNA)
def J(self, DNA):
return (OBJECTIVE-int(DNA, 2))**2
class Population:
def __init__(self):
self.organisms = []
for i in range(POPULATION_SIZE):
self.organisms.append(Organism())
self.compute_avg_fitness()
def display(self):
for i in range(POPULATION_SIZE):
print('organism ID = ' + str(i+1) + ', fitness = ', str(self.organisms[i].fitness))
def compute_avg_fitness(self):
self.avg_fitness = 0
for i in range(POPULATION_SIZE):
self.avg_fitness += self.organisms[i].fitness
self.avg_fitness = self.avg_fitness/POPULATION_SIZE
def kill_and_replace(self):
num_to_kill = int(KILL_RATE*POPULATION_SIZE)
self.organisms.sort(key = lambda x: x.fitness,reverse=True)
for i in range(num_to_kill):
parent_1 = self.organisms[randint(num_to_kill-1,POPULATION_SIZE)]
parent_2 = self.organisms[randint(num_to_kill-1,POPULATION_SIZE)]
new_DNA = self.crossover(parent_1.DNA,parent_2.DNA)
self.organisms[i] = Organism()
self.organisms[i].DNA = new_DNA
def crossover(self, DNA1, DNA2):
crossover_pts = []
for i in range(NUM_CROSSOVERS-1):
crossover_pts.append(randint(DNA_LENGTH))
crossover_pts.sort()
DNA_new = ''
i_prev = 0
for i in range(len(crossover_pts)):
i_current = crossover_pts[i]
if (i%2==0):
DNA_new += DNA1[i_prev:i_current]
else:
DNA_new += DNA2[i_prev:i_current]
i_prev = i_current
if (NUM_CROSSOVERS%2==1):
DNA_new += DNA1[i_current:]
else:
DNA_new += DNA2[i_current:]
return DNA_new
def mutate(self):
for i in range(POPULATION_SIZE):
for j in range(DNA_LENGTH):
if (rand() < MUTATION_RATE):
current_bit = self.organisms[i].DNA[j]
if (current_bit == '0'):
self.organisms[i].DNA = self.organisms[i].DNA[:j] + '1' + self.organisms[i].DNA[j+1:]
else:
self.organisms[i].DNA = self.organisms[i].DNA[:j] + '0' + self.organisms[i].DNA[j+1:]
def life_cycle(self):
self.compute_avg_fitness()
self.kill_and_replace()
self.mutate()
if __name__=="__main__":
N_generations = 1000
fitness = []
P = Population()
for iter in range(N_generations):
fitness.append(P.avg_fitness)
P.life_cycle()
P.display()
plt.plot(fitness)
plt.show()
# breed
# mutate