-
Notifications
You must be signed in to change notification settings - Fork 1
/
Population.js
105 lines (91 loc) · 2.89 KB
/
Population.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
class Population {
salespeople = [];
totalFitness;
generationCounter = 1;
bestSalespersonIndex;
bestFitness = 0;
bestFitnessGen;
constructor(size) {
for (let i = 0; i < size; i++) {
this.salespeople.push(new Salesperson());
}
}
// same functions as in Salesperson class but for entire population
randomizeAllRoutes() {
this.salespeople.forEach((sp) => {
sp.setRoute = sp.randomizeRoute(sp.getRoute);
});
}
drawAllPaths() {
this.salespeople.forEach((sp) => {
sp.drawPath(DEFAULT_PATH_COLOR);
});
}
calculateFitnesses() {
this.salespeople.forEach((sp) => {
sp.calculateFitness();
});
}
// natural selection (genetic algorithm) --> survival of fittest
naturalSelection() {
let nextGen = [];
// add best salesperson from previous generation
this.setBestSalesperson();
nextGen[0] = this.createChild(this.salespeople[this.bestSalespersonIndex]);
nextGen[0].isBest = true;
// sum fitnesses of all salespersons (total pool)
this.totalFitness = 0;
this.salespeople.forEach((sp) => {
this.totalFitness += sp.getFitness;
});
for (let i = 1; i < this.salespeople.length; i++) {
// randomly choose parent from the population
let parent = this.selectRandomParent();
// create child from parent
let child = this.createChild(parent);
nextGen[i] = child;
}
this.salespeople = nextGen.slice(0);
this.generationCounter++;
}
// higher fitness parents should have a greater chance of being chosen
selectRandomParent() {
// pick random value from range (each salesperson's fitness is proportional to the whole)
let randomFitness = Math.random() * this.totalFitness;
let threshold = 0;
for (let i = 0; i < this.salespeople.length; i++) {
threshold += this.salespeople[i].getFitness;
// higher fitness is higher proportion of total sum --> higher chance of being selected
if (threshold > randomFitness) {
return this.salespeople[i];
}
}
}
// for simplicity --> child will be duplicate of parent (instead of mixing two parents)
createChild(parent) {
let parentClone = new Salesperson();
parentClone.setRoute = parent.getRoute;
return parentClone;
}
mutateAll() {
for (let i = 1; i < this.salespeople.length; i++) {
this.salespeople[i].mutate();
}
}
// prevent de-evolution; randomization causes generations to do worse than before
setBestSalesperson() {
let maxFitness = 0;
let maxIndex = 0;
for (let i = 0; i < this.salespeople.length; i++) {
if (this.salespeople[i].getFitness > maxFitness) {
maxFitness = this.salespeople[i].getFitness;
maxIndex = i;
}
if (maxFitness > this.bestFitness) {
this.bestFitness = maxFitness;
this.bestFitnessGen = this.generationCounter;
}
}
this.bestSalespersonIndex = maxIndex;
}
}