-
Notifications
You must be signed in to change notification settings - Fork 0
/
genetic.js
205 lines (164 loc) · 7.07 KB
/
genetic.js
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/***********************************************************************************
/* Genetic Algorithm implementation
/***********************************************************************************/
var GeneticAlgorithm = function(max_units, top_units){
this.max_units = max_units; // max number of units in population
this.top_units = top_units; // number of top units (winners) used for evolving population
if (this.max_units < this.top_units) this.top_units = this.max_units;
this.Population = []; // array of all units in current population
this.SCALE_FACTOR = 200; // the factor used to scale normalized input values
}
GeneticAlgorithm.prototype = {
// resets genetic algorithm parameters
reset : function(){
this.iteration = 1; // current iteration number (it is equal to the current population number)
this.mutateRate = 1; // initial mutation rate
this.best_population = 0; // the population number of the best unit
this.best_fitness = 0; // the fitness of the best unit
this.best_score = 0; // the score of the best unit ever
},
// creates a new population
createPopulation : function(){
// clear any existing population
this.Population.splice(0, this.Population.length);
for (var i=0; i<this.max_units; i++){
// create a new unit by generating a random Synaptic neural network
// with 2 neurons in the input layer, 6 neurons in the hidden layer and 1 neuron in the output layer
var newUnit = new synaptic.Architect.Perceptron(2, 6, 1);
// set additional parameters for the new unit
newUnit.index = i;
newUnit.fitness = 0;
newUnit.score = 0;
newUnit.isWinner = false;
// add the new unit to the population
this.Population.push(newUnit);
}
},
// activates the neural network of an unit from the population
// to calculate an output action according to the inputs
activateBrain : function(bird, target){
// input 1: the horizontal distance between the bird and the target
var targetDeltaX = this.normalize(target.x, 700) * this.SCALE_FACTOR;
// input 2: the height difference between the bird and the target
var targetDeltaY = this.normalize(bird.y - target.y, 800) * this.SCALE_FACTOR;
// create an array of all inputs
var inputs = [targetDeltaX, targetDeltaY];
// calculate outputs by activating synaptic neural network of this bird
var outputs = this.Population[bird.index].activate(inputs);
// perform flap if output is greater than 0.5
if (outputs[0] > 0.5) bird.turnleft();
else if (outputs[0] < 0.5) bird.turnright();
},
// evolves the population by performing selection, crossover and mutations on the units
evolvePopulation : function(){
// select the top units of the current population to get an array of winners
// (they will be copied to the next population)
var Winners = this.selection();
if (this.mutateRate == 1 && Winners[0].fitness < 0){
// If the best unit from the initial population has a negative fitness
// then it means there is no any bird which reached the first barrier!
// Playing as the God, we can destroy this bad population and try with another one.
this.createPopulation();
} else {
this.mutateRate = 0.2; // else set the mutatation rate to the real value
}
// fill the rest of the next population with new units using crossover and mutation
for (var i=this.top_units; i<this.max_units; i++){
var parentA, parentB, offspring;
if (i == this.top_units){
// offspring is made by a crossover of two best winners
parentA = Winners[0].toJSON();
parentB = Winners[1].toJSON();
offspring = this.crossOver(parentA, parentB);
} else if (i < this.max_units-2){
// offspring is made by a crossover of two random winners
parentA = this.getRandomUnit(Winners).toJSON();
parentB = this.getRandomUnit(Winners).toJSON();
offspring = this.crossOver(parentA, parentB);
} else {
// offspring is a random winner
offspring = this.getRandomUnit(Winners).toJSON();
}
// mutate the offspring
offspring = this.mutation(offspring);
// create a new unit using the neural network from the offspring
var newUnit = synaptic.Network.fromJSON(offspring);
newUnit.index = this.Population[i].index;
newUnit.fitness = 0;
newUnit.score = 0;
newUnit.isWinner = false;
// update population by changing the old unit with the new one
this.Population[i] = newUnit;
}
// if the top winner has the best fitness in the history, store its achievement!
if (Winners[0].fitness > this.best_fitness){
this.best_population = this.iteration;
this.best_fitness = Winners[0].fitness;
this.best_score = Winners[0].score;
}
// sort the units of the new population in ascending order by their index
this.Population.sort(function(unitA, unitB){
return unitA.index - unitB.index;
});
},
// selects the best units from the current population
selection : function(){
// sort the units of the current population in descending order by their fitness
var sortedPopulation = this.Population.sort(
function(unitA, unitB){
return unitB.fitness - unitA.fitness;
}
);
// mark the top units as the winners!
for (var i=0; i<this.top_units; i++) this.Population[i].isWinner = true;
// return an array of the top units from the current population
return sortedPopulation.slice(0, this.top_units);
},
// performs a single point crossover between two parents
crossOver : function(parentA, parentB) {
// get a cross over cutting point
var cutPoint = this.random(0, parentA.neurons.length-1);
// swap 'bias' information between both parents:
// 1. left side to the crossover point is copied from one parent
// 2. right side after the crossover point is copied from the second parent
for (var i = cutPoint; i < parentA.neurons.length; i++){
var biasFromParentA = parentA.neurons[i]['bias'];
parentA.neurons[i]['bias'] = parentB.neurons[i]['bias'];
parentB.neurons[i]['bias'] = biasFromParentA;
}
return this.random(0, 1) == 1 ? parentA : parentB;
},
// performs random mutations on the offspring
mutation : function (offspring){
// mutate some 'bias' information of the offspring neurons
for (var i = 0; i < offspring.neurons.length; i++){
offspring.neurons[i]['bias'] = this.mutate(offspring.neurons[i]['bias']);
}
// mutate some 'weights' information of the offspring connections
for (var i = 0; i < offspring.connections.length; i++){
offspring.connections[i]['weight'] = this.mutate(offspring.connections[i]['weight']);
}
return offspring;
},
// mutates a gene
mutate : function (gene){
if (Math.random() < this.mutateRate) {
var mutateFactor = 1 + ((Math.random() - 0.5) * 3 + (Math.random() - 0.5));
gene *= mutateFactor;
}
return gene;
},
random : function(min, max){
return Math.floor(Math.random()*(max-min+1) + min);
},
getRandomUnit : function(array){
return array[this.random(0, array.length-1)];
},
normalize : function(value, max){
// clamp the value between its min/max limits
if (value < -max) value = -max;
else if (value > max) value = max;
// normalize the clamped value
return (value/max);
}
}