-
Notifications
You must be signed in to change notification settings - Fork 0
/
geneticalgorithm.py
147 lines (134 loc) · 5.53 KB
/
geneticalgorithm.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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
# Genetic Algorithm and Reinforcement Learning
import os, random
import numpy as np
import neuralnetwork, inputs, snake
class Population:
def __init__(self, population_size, mutation_rate):
# Round population size to nearest even number
self.population_size = population_size + population_size%2
# Set mutation rate
self.mutation_rate = mutation_rate
# Generate a random neural network and snake for each species
self.neuralnetworks = []
self.snakes = []
for i in range(self.population_size):
self.neuralnetworks.append(neuralnetwork.NeuralNetwork())
self.snakes.append(snake.Snake())
# Current mode (training (0) or resume (1))
self.current_mode = 0
# Current generation number
self.generation = 1
# Best score achieved by population
self.population_best = 0
# Best fitness achieved by population
self.population_best_fitness = 0
# Best neural network achieved by population
self.population_best_nn = self.neuralnetworks[0]
# Current best score in generation
self.current_best = 0
# Current best species in generation
self.current_best_species = 0
# When false stops feedforward so that next generation can be built
self.proceed = True
# Number of snakes still alive
self.snakes_alive = self.population_size
# Update population
def update(self):
snakes_alive = 0
self.current_best = 0
# For each snake
for i in range(self.population_size):
# If it is alive
if self.snakes[i].is_alive:
# Increase alive count
snakes_alive += 1
# If it has the highest score, set it as current_best_species
if self.snakes[i].score > self.current_best:
self.current_best = self.snakes[i].score
self.current_best_species = i
# Same for high score
if self.current_best > self.population_best:
self.population_best = self.current_best
# Gather inputs and feed them through neural network
nn_input_batches = inputs.calculate_inputs([self.snakes[i].head[0],self.snakes[i].head[1]], [self.snakes[i].food[0], self.snakes[i].food[1]], self.snakes[i].segments, self.snakes[i].direction)
outputs = []
for nn_input_batch in nn_input_batches:
outputs.append(self.neuralnetworks[i].feedforward(nn_input_batch))
# Find highest output, apply it to current direction, and clip it
decision = self.snakes[i].direction + np.argmax(outputs) - 1
if decision > 3:
decision = 0
elif decision < 0:
decision = 3
self.snakes[i].direction = decision
# Move the snake
self.snakes[i].move()
self.snakes_alive = snakes_alive
if snakes_alive < 1:
self.proceed = False
self.natural_selection()
# Perform natural selection to create next generation
def natural_selection(self):
# Auxiliary functions for natural_selection()
# Calculate all fitnesses
def calculate_fitnesses(snakes):
fitnesses = []
for snake in snakes:
fitnesses.append(snake.lifetime*((snake.length-2)**2))
return np.array(fitnesses)
# Fitness Proportionate Selection (Roulette Wheel Selection) of snakes for crossover
def select_snake(fitnesses_sum, fitnesses, population_size, neuralnetworks):
# Randomize cutoff
fitnesses_cutoff = random.randint(0, fitnesses_sum)
# Run through each snake's fitness and add it to a running sum, as soon as the sum surpasses the cutoff, select that snake
running_sum = 0
for i in range(int(population_size/2)):
running_sum += fitnesses[i]
if running_sum >= fitnesses_cutoff:
return neuralnetworks[i]
# Crossover two parent neural networks to form a child neural network
def crossover(parent_one, parent_two):
def matrix_crossover(parent_matrix_one, parent_matrix_two):
child_matrix = []
row_cutoff = random.randint(0, len(parent_matrix_one))
column_cutoff = random.randint(0, len(parent_matrix_one[0]))
for row in range(len(parent_matrix_one)):
for column in range(len(parent_matrix_one[0])):
if row < row_cutoff or (row == row_cutoff and column < column_cutoff):
child_matrix.append(parent_matrix_one[row][column])
else:
child_matrix.append(parent_matrix_two[row][column])
return np.array(child_matrix).reshape(parent_matrix_one.shape)
child = neuralnetwork.NeuralNetwork()
for i in range(len(parent_one.weights)):
child.weights[i] = matrix_crossover(parent_one.weights[i], parent_two.weights[i])
return child
# Calculate fitnesses
fitnesses = calculate_fitnesses(self.snakes)
for i in range(len(fitnesses)):
if fitnesses[i] > self.population_best_fitness:
self.population_best_fitness = i
self.population_best_nn = self.neuralnetworks[i]
# Keep top 50% fittest neural networks
best_fitnesses = np.argsort(fitnesses)
best_fitnesses = best_fitnesses[::-1]
best_fitnesses = best_fitnesses[:int(self.population_size/2)]
self.neuralnetworks = [self.neuralnetworks[i] for i in best_fitnesses]
# Crossover and mutate bottom 50% of species
fitnesses = [fitnesses[i] for i in best_fitnesses]
fitnesses_sum = np.sum(fitnesses)
for i in range(int(self.population_size/2)):
child = crossover(select_snake(fitnesses_sum, fitnesses, self.population_size, self.neuralnetworks), select_snake(fitnesses_sum, fitnesses, self.population_size, self.neuralnetworks))
child.mutate(self.mutation_rate)
self.neuralnetworks.append(child)
# Reset variables for next generation
self.snakes = []
for i in range(self.population_size):
self.snakes.append(snake.Snake())
self.generation += 1
self.current_best = 0
self.current_best_species = 0
self.proceed = True
# Save best snake
def save_best(self):
self.population_best_nn.save("saved")