Genetic Algorithm Hello World

The Hello World of Genetic Algorithms is a simple phrase solver. While useless in terms of utility, it is probably the simplest way to understand this class of algorithm.

How it Works

Entities in this system start out as randomly generated strings (See genetic.seed = function() below). At each iteration a portion of entites are selected for mutation. Another portition is selected for crossover (aka. mating). From there you let the system run and watch it converge on a solution, there isn't much more to it than that!

Mutation

When an entity (string) is selected for mutation, a character in a random location is either increased or decreased by one lexicographically. See genetic.mutate = function(entity) below for code.

Crossover

In Genetic.js crossover always results in two children from from two parents. In this simulation we implement two-point crossover. See genetic.crossover = function(mother, father) below.

Fitness

The phrase solver demo scores entities (strings) by how close they are to the goal. The formula is simple, add one for each character that matches. Also add fractional points if it is close. The result is a floating point number, the larger the better. See genetic.fitness = function(entity) for implementation.

Phrase Solver Demo

Refer to /system/genetic-js.html for all the configuration/options that are available. The code can be cloned from https://github.com/subprotocol/genetic-js.

Generation Fitness Solution
Press 'Solve' Button to begin.

Code

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
var genetic = Genetic.create();

genetic.optimize = Genetic.Optimize.Maximize; genetic.select1 = Genetic.Select1.Tournament2; genetic.select2 = Genetic.Select2.Tournament2;

genetic.seed = function() {

<span class="kd">function</span> <span class="nx">randomString</span><span class="p">(</span><span class="nx">len</span><span class="p">)</span> <span class="p">{</span>
    <span class="kd">var</span> <span class="nx">text</span> <span class="o">=</span> <span class="s2">""</span><span class="p">;</span>
    <span class="kd">var</span> <span class="nx">charset</span> <span class="o">=</span> <span class="s2">"abcdefghijklmnopqrstuvwxyz0123456789"</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kd">var</span> <span class="nx">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="nx">i</span><span class="o">&lt;</span><span class="nx">len</span><span class="p">;</span><span class="nx">i</span><span class="o">++</span><span class="p">)</span>
        <span class="nx">text</span> <span class="o">+=</span> <span class="nx">charset</span><span class="p">.</span><span class="nx">charAt</span><span class="p">(</span><span class="nb">Math</span><span class="p">.</span><span class="nx">floor</span><span class="p">(</span><span class="nb">Math</span><span class="p">.</span><span class="nx">random</span><span class="p">()</span> <span class="o">*</span> <span class="nx">charset</span><span class="p">.</span><span class="nx">length</span><span class="p">));</span>

    <span class="k">return</span> <span class="nx">text</span><span class="p">;</span>
<span class="p">}</span>

<span class="c1">// create random strings that are equal in length to solution</span>
<span class="k">return</span> <span class="nx">randomString</span><span class="p">(</span><span class="k">this</span><span class="p">.</span><span class="nx">userData</span><span class="p">[</span><span class="s2">"solution"</span><span class="p">].</span><span class="nx">length</span><span class="p">);</span>

};

genetic.mutate = function(entity) {

<span class="kd">function</span> <span class="nx">replaceAt</span><span class="p">(</span><span class="nx">str</span><span class="p">,</span> <span class="nx">index</span><span class="p">,</span> <span class="nx">character</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">return</span> <span class="nx">str</span><span class="p">.</span><span class="nx">substr</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="nx">index</span><span class="p">)</span> <span class="o">+</span> <span class="nx">character</span> <span class="o">+</span> <span class="nx">str</span><span class="p">.</span><span class="nx">substr</span><span class="p">(</span><span class="nx">index</span><span class="o">+</span><span class="nx">character</span><span class="p">.</span><span class="nx">length</span><span class="p">);</span>
<span class="p">}</span>

<span class="c1">// chromosomal drift</span>
<span class="kd">var</span> <span class="nx">i</span> <span class="o">=</span> <span class="nb">Math</span><span class="p">.</span><span class="nx">floor</span><span class="p">(</span><span class="nb">Math</span><span class="p">.</span><span class="nx">random</span><span class="p">()</span><span class="o">*</span><span class="nx">entity</span><span class="p">.</span><span class="nx">length</span><span class="p">)</span>     
<span class="k">return</span> <span class="nx">replaceAt</span><span class="p">(</span><span class="nx">entity</span><span class="p">,</span> <span class="nx">i</span><span class="p">,</span> <span class="nb">String</span><span class="p">.</span><span class="nx">fromCharCode</span><span class="p">(</span><span class="nx">entity</span><span class="p">.</span><span class="nx">charCodeAt</span><span class="p">(</span><span class="nx">i</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="nb">Math</span><span class="p">.</span><span class="nx">floor</span><span class="p">(</span><span class="nb">Math</span><span class="p">.</span><span class="nx">random</span><span class="p">()</span><span class="o">*</span><span class="mi">2</span><span class="p">)</span> <span class="p">?</span> <span class="mi">1</span> <span class="p">:</span> <span class="o">-</span><span class="mi">1</span><span class="p">)));</span>

};

genetic.crossover = function(mother, father) {

<span class="c1">// two-point crossover</span>
<span class="kd">var</span> <span class="nx">len</span> <span class="o">=</span> <span class="nx">mother</span><span class="p">.</span><span class="nx">length</span><span class="p">;</span>
<span class="kd">var</span> <span class="nx">ca</span> <span class="o">=</span> <span class="nb">Math</span><span class="p">.</span><span class="nx">floor</span><span class="p">(</span><span class="nb">Math</span><span class="p">.</span><span class="nx">random</span><span class="p">()</span><span class="o">*</span><span class="nx">len</span><span class="p">);</span>
<span class="kd">var</span> <span class="nx">cb</span> <span class="o">=</span> <span class="nb">Math</span><span class="p">.</span><span class="nx">floor</span><span class="p">(</span><span class="nb">Math</span><span class="p">.</span><span class="nx">random</span><span class="p">()</span><span class="o">*</span><span class="nx">len</span><span class="p">);</span>        
<span class="k">if</span> <span class="p">(</span><span class="nx">ca</span> <span class="o">&gt;</span> <span class="nx">cb</span><span class="p">)</span> <span class="p">{</span>
    <span class="kd">var</span> <span class="nx">tmp</span> <span class="o">=</span> <span class="nx">cb</span><span class="p">;</span>
    <span class="nx">cb</span> <span class="o">=</span> <span class="nx">ca</span><span class="p">;</span>
    <span class="nx">ca</span> <span class="o">=</span> <span class="nx">tmp</span><span class="p">;</span>
<span class="p">}</span>

<span class="kd">var</span> <span class="nx">son</span> <span class="o">=</span> <span class="nx">father</span><span class="p">.</span><span class="nx">substr</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="nx">ca</span><span class="p">)</span> <span class="o">+</span> <span class="nx">mother</span><span class="p">.</span><span class="nx">substr</span><span class="p">(</span><span class="nx">ca</span><span class="p">,</span> <span class="nx">cb</span><span class="o">-</span><span class="nx">ca</span><span class="p">)</span> <span class="o">+</span> <span class="nx">father</span><span class="p">.</span><span class="nx">substr</span><span class="p">(</span><span class="nx">cb</span><span class="p">);</span>
<span class="kd">var</span> <span class="nx">daughter</span> <span class="o">=</span> <span class="nx">mother</span><span class="p">.</span><span class="nx">substr</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="nx">ca</span><span class="p">)</span> <span class="o">+</span> <span class="nx">father</span><span class="p">.</span><span class="nx">substr</span><span class="p">(</span><span class="nx">ca</span><span class="p">,</span> <span class="nx">cb</span><span class="o">-</span><span class="nx">ca</span><span class="p">)</span> <span class="o">+</span> <span class="nx">mother</span><span class="p">.</span><span class="nx">substr</span><span class="p">(</span><span class="nx">cb</span><span class="p">);</span>

<span class="k">return</span> <span class="p">[</span><span class="nx">son</span><span class="p">,</span> <span class="nx">daughter</span><span class="p">];</span>

};

genetic.fitness = function(entity) { var fitness = 0;

<span class="kd">var</span> <span class="nx">i</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="nx">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="nx">i</span><span class="o">&lt;</span><span class="nx">entity</span><span class="p">.</span><span class="nx">length</span><span class="p">;</span><span class="o">++</span><span class="nx">i</span><span class="p">)</span> <span class="p">{</span>
    <span class="c1">// increase fitness for each character that matches</span>
    <span class="k">if</span> <span class="p">(</span><span class="nx">entity</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span> <span class="o">==</span> <span class="k">this</span><span class="p">.</span><span class="nx">userData</span><span class="p">[</span><span class="s2">"solution"</span><span class="p">][</span><span class="nx">i</span><span class="p">])</span>
        <span class="nx">fitness</span> <span class="o">+=</span> <span class="mi">1</span><span class="p">;</span>

    <span class="c1">// award fractions of a point as we get warmer</span>
    <span class="nx">fitness</span> <span class="o">+=</span> <span class="p">(</span><span class="mi">127</span><span class="o">-</span><span class="nb">Math</span><span class="p">.</span><span class="nx">abs</span><span class="p">(</span><span class="nx">entity</span><span class="p">.</span><span class="nx">charCodeAt</span><span class="p">(</span><span class="nx">i</span><span class="p">)</span> <span class="o">-</span> <span class="k">this</span><span class="p">.</span><span class="nx">userData</span><span class="p">[</span><span class="s2">"solution"</span><span class="p">].</span><span class="nx">charCodeAt</span><span class="p">(</span><span class="nx">i</span><span class="p">)))</span><span class="o">/</span><span class="mi">50</span><span class="p">;</span>
<span class="p">}</span>

<span class="k">return</span> <span class="nx">fitness</span><span class="p">;</span>

};

genetic.generation = function(pop, generation, stats) { // stop running once we've reached the solution return pop[0].entity != this.userData["solution"]; };

genetic.notification = function(pop, generation, stats, isFinished) {

<span class="kd">function</span> <span class="nx">lerp</span><span class="p">(</span><span class="nx">a</span><span class="p">,</span> <span class="nx">b</span><span class="p">,</span> <span class="nx">p</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">return</span> <span class="nx">a</span> <span class="o">+</span> <span class="p">(</span><span class="nx">b</span><span class="o">-</span><span class="nx">a</span><span class="p">)</span><span class="o">*</span><span class="nx">p</span><span class="p">;</span>
<span class="p">}</span>

<span class="kd">var</span> <span class="nx">value</span> <span class="o">=</span> <span class="nx">pop</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="nx">entity</span><span class="p">;</span>
<span class="k">this</span><span class="p">.</span><span class="nx">last</span> <span class="o">=</span> <span class="k">this</span><span class="p">.</span><span class="nx">last</span><span class="o">||</span><span class="nx">value</span><span class="p">;</span>

<span class="k">if</span> <span class="p">(</span><span class="nx">pop</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="nx">value</span> <span class="o">==</span> <span class="k">this</span><span class="p">.</span><span class="nx">last</span><span class="p">)</span>
    <span class="k">return</span><span class="p">;</span>


<span class="kd">var</span> <span class="nx">solution</span> <span class="o">=</span> <span class="p">[];</span>
<span class="kd">var</span> <span class="nx">i</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="nx">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="nx">i</span><span class="o">&lt;</span><span class="nx">value</span><span class="p">.</span><span class="nx">length</span><span class="p">;</span><span class="o">++</span><span class="nx">i</span><span class="p">)</span> <span class="p">{</span>
    <span class="kd">var</span> <span class="nx">diff</span> <span class="o">=</span> <span class="nx">value</span><span class="p">.</span><span class="nx">charCodeAt</span><span class="p">(</span><span class="nx">i</span><span class="p">)</span> <span class="o">-</span> <span class="k">this</span><span class="p">.</span><span class="nx">last</span><span class="p">.</span><span class="nx">charCodeAt</span><span class="p">(</span><span class="nx">i</span><span class="p">);</span>
    <span class="kd">var</span> <span class="nx">style</span> <span class="o">=</span> <span class="s2">"background: transparent;"</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="nx">diff</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
        <span class="nx">style</span> <span class="o">=</span> <span class="s2">"background: rgb(0,200,50); color: #fff;"</span><span class="p">;</span>
    <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="nx">diff</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
        <span class="nx">style</span> <span class="o">=</span> <span class="s2">"background: rgb(0,100,50); color: #fff;"</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="nx">solution</span><span class="p">.</span><span class="nx">push</span><span class="p">(</span><span class="s2">"&lt;span style=\""</span> <span class="o">+</span> <span class="nx">style</span> <span class="o">+</span> <span class="s2">"\"&gt;"</span> <span class="o">+</span> <span class="nx">value</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span> <span class="o">+</span> <span class="s2">"&lt;/span&gt;"</span><span class="p">);</span>
<span class="p">}</span>

<span class="kd">var</span> <span class="nx">buf</span> <span class="o">=</span> <span class="s2">""</span><span class="p">;</span>
<span class="nx">buf</span> <span class="o">+=</span> <span class="s2">"&lt;tr&gt;"</span><span class="p">;</span>
<span class="nx">buf</span> <span class="o">+=</span> <span class="s2">"&lt;td&gt;"</span> <span class="o">+</span> <span class="nx">generation</span> <span class="o">+</span> <span class="s2">"&lt;/td&gt;"</span><span class="p">;</span>
<span class="nx">buf</span> <span class="o">+=</span> <span class="s2">"&lt;td&gt;"</span> <span class="o">+</span> <span class="nx">pop</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="nx">fitness</span><span class="p">.</span><span class="nx">toPrecision</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span> <span class="o">+</span> <span class="s2">"&lt;/td&gt;"</span><span class="p">;</span>
<span class="nx">buf</span> <span class="o">+=</span> <span class="s2">"&lt;td&gt;"</span> <span class="o">+</span> <span class="nx">solution</span><span class="p">.</span><span class="nx">join</span><span class="p">(</span><span class="s2">""</span><span class="p">)</span> <span class="o">+</span> <span class="s2">"&lt;/td&gt;"</span><span class="p">;</span>
<span class="nx">buf</span> <span class="o">+=</span> <span class="s2">"&lt;/tr&gt;"</span><span class="p">;</span>
<span class="nx">$</span><span class="p">(</span><span class="s2">"#results tbody"</span><span class="p">).</span><span class="nx">prepend</span><span class="p">(</span><span class="nx">buf</span><span class="p">);</span>

<span class="k">this</span><span class="p">.</span><span class="nx">last</span> <span class="o">=</span> <span class="nx">value</span><span class="p">;</span>

};

$(document).ready(function () { $("#solve").click(function () {

    <span class="nx">$</span><span class="p">(</span><span class="s2">"#results tbody"</span><span class="p">).</span><span class="nx">html</span><span class="p">(</span><span class="s2">""</span><span class="p">);</span>

    <span class="kd">var</span> <span class="nx">config</span> <span class="o">=</span> <span class="p">{</span>
        <span class="s2">"iterations"</span><span class="p">:</span> <span class="mi">4000</span>
        <span class="p">,</span> <span class="s2">"size"</span><span class="p">:</span> <span class="mi">250</span>
        <span class="p">,</span> <span class="s2">"crossover"</span><span class="p">:</span> <span class="mf">0.3</span>
        <span class="p">,</span> <span class="s2">"mutation"</span><span class="p">:</span> <span class="mf">0.3</span>
        <span class="p">,</span> <span class="s2">"skip"</span><span class="p">:</span> <span class="mi">20</span>
    <span class="p">};</span>

    <span class="kd">var</span> <span class="nx">userData</span> <span class="o">=</span> <span class="p">{</span>
        <span class="s2">"solution"</span><span class="p">:</span> <span class="nx">$</span><span class="p">(</span><span class="s2">"#quote"</span><span class="p">).</span><span class="nx">val</span><span class="p">()</span>
    <span class="p">};</span>

    <span class="nx">genetic</span><span class="p">.</span><span class="nx">evolve</span><span class="p">(</span><span class="nx">config</span><span class="p">,</span> <span class="nx">userData</span><span class="p">);</span>
<span class="p">});</span>

});

Sean