-
Notifications
You must be signed in to change notification settings - Fork 1
/
index.js
133 lines (106 loc) · 3.34 KB
/
index.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
'use strict';
// Src: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random
function random(min, max) {
min = Math.ceil(min);
max = Math.floor(max);
// The maximum is exclusive and the minimum is inclusive
return Math.floor(Math.random() * (max - min)) + min;
}
function generateLetter() {
const code = random(97, 123); // ASCII char codes
return String.fromCharCode(code);
}
class Member {
constructor(target) {
this.target = target;
this.keys = [];
for (let i = 0; i < target.length; i += 1) {
this.keys[i] = generateLetter();
}
}
fitness() {
let matches = 0;
for (let i = 0; i < this.keys.length; i += 1) {
if (this.keys[i] === this.target[i]) {
matches += 1;
}
}
return matches / this.target.length;
}
crossover(partner) {
const { length } = this.target;
const child = new Member(this.target);
const midpoint = random(0, length);
for (let i = 0; i < length; i += 1) {
if (i > midpoint) {
child.keys[i] = this.keys[i];
} else {
child.keys[i] = partner.keys[i];
}
}
return child;
}
mutate(mutationRate) {
for (let i = 0; i < this.keys.length; i += 1) {
// If below predefined mutation rate,
// generate a new random letter on this position.
if (Math.random() < mutationRate) {
this.keys[i] = generateLetter();
}
}
}
}
class Population {
constructor(size, target, mutationRate) {
size = size || 1;
this.members = [];
this.mutationRate = mutationRate;
for (let i = 0; i < size; i += 1) {
this.members.push(new Member(target));
}
}
evolve(generations) {
for (let i = 0; i < generations; i += 1) {
const pool = this._selectMembersForMating();
this._reproduce(pool);
}
}
_selectMembersForMating() {
const matingPool = [];
this.members.forEach((m) => {
// The fitter he/she is, the more often will be present in the mating pool
// i.e. increasing the chances of selection
// If fitness == 0, add just one member
const f = Math.floor(m.fitness() * 100) || 1;
for (let i = 0; i < f; i += 1) {
matingPool.push(m);
}
});
return matingPool;
}
_reproduce(matingPool) {
for (let i = 0; i < this.members.length; i += 1) {
// Pick 2 random members/parent from the mating pool
const parentA = matingPool[random(0, matingPool.length)];
const parentB = matingPool[random(0, matingPool.length)];
// Perform crossover
const child = parentA.crossover(parentB);
// Perform mutation
child.mutate(this.mutationRate);
this.members[i] = child;
}
}
}
// Init function
function generate(populationSize, target, mutationRate, generations) {
// Create a population and evolve for N generations
const population = new Population(populationSize, target, mutationRate);
population.evolve(generations);
// Get the typed words from all members and find if someone was able to type the target
const membersKeys = population.members.map((m) => m.keys.join(''));
const perfectCandidatesNum = membersKeys.filter((w) => w === target);
// Print the results
console.log(membersKeys);
console.log(`${perfectCandidatesNum ? perfectCandidatesNum.length : 0} member(s) typed "${target}"`);
}
generate(20, 'hit', 0.05, 20);