### Natural selection

A naive genetic algorithm is used to reconstruct the quote: "Natural selection is anything but random." by Richard Dawkins.

The chance that a random sequence of 41 characters matches the quote is 1 : 95^41 ≈ 1 : 10^80.

#text #genetic

Created by reinder on 2019/9/8
96
0

```// Natural selection. Created by Reinder Nijhoff 2019
// @reindernijhoff
//
// https://turtletoy.net/turtle/2f92cd6aa3
//
// A naive genetic algorithm is used to reconstruct the quote: "Natural selection is anything
// but random." by Richard Dawkins.
///
// - The individuals of the first generation have random 'DNA' (41 characters).
// - The 'fittest' individual of each (generations/19)th generation is printed.
// - The fitness of an individual is given by the number of characters in its 'DNA' that match
//   the quote.
// - The two fittest individuals of each generation reproduce using crossovers and mutations.
//
// The chance that a fully random individual matches the quote is 1 : 95^41 ≈ 1 : 10^80.
// (10^80 is the estimated number of atoms in the known, observable universe)
//

const text = new Text();
const turtle = new Turtle(-92,-90);

const mutationRate = .02; // min=0.01, max=0.5, step=0.01
const populationSize = 2000; // min=10, max=2000, step=1
const generations = 40; // min=40, max=1000, step=10

const fittest = "Natural selection is anything but random.".split('');

//
// Individual
//
class Individual {
constructor() {
this.dna = [];
this.fitness = 0;
}
fillRandom() {
fittest.forEach( (v,i) => {
this.dna[i] = this.randomCharacter();
} );
this.calcFitness();
}
breed(p0, p1) {
let s = Math.floor(Math.random()*(fittest.length-2))+1;
// crossover
if (Math.random() < .5) {
this.dna = [...p0.dna.slice(0,s), ...p1.dna.slice(s)];
} else {
this.dna = [...p1.dna.slice(0,s), ...p0.dna.slice(s)];
}
// mutations
this.dna.forEach( (v,i) => {
if (Math.random() < mutationRate) {
this.dna[i] = this.randomCharacter();
}
} );
this.calcFitness();
}
calcFitness() {
this.fitness = 0;
fittest.forEach( (v,i) => {
if (this.dna[i] == v) this.fitness++;
});
}
randomCharacter() {
return  String.fromCharCode(Math.floor(Math.random()*95)+32);
}
}

//
// Generation
//
class Generation {
constructor() {
this.individuals = [];
for (let i=0; i<populationSize; i++) {
this.individuals[i] = new Individual();
}
}
fillRandom() {
this.individuals.forEach(i => i.fillRandom());
return this.sortFittest();
}
breed(parentGeneration) {
const p0 = parentGeneration.individuals[0];
const p1 = parentGeneration.individuals[1];
this.individuals.forEach(i => i.breed(p0, p1));
return this.sortFittest();
}
sortFittest() {
this.individuals.sort( (a, b) => b.fitness - a.fitness );
return this;
}
}

//
// Selection
//

let gen0 = new Generation().fillRandom();
let gen1 = new Generation();

function walk(i) {
turtle.jump(-92, -90+i*10);
text.print(turtle, gen0.individuals[0].dna.join(''),.21);

for (let i=0; i<generations/40; i++) {
gen1.breed(gen0)
gen0.breed(gen1)
}
return i<18;
}

////////////////////////////////////////////////////////////////
// Text utility code - https://turtletoy.net/turtle/1713ddbe99
// !! MODIFIED TO MAKE IT MONOSPACED
////////////////////////////////////////////////////////////////

function Text() {
class Text {
print (t, str, scale) {
let pos = [t.x(), t.y()], h = t.h(), o = pos;
str.split('').map(c => {
const i = c.charCodeAt(0) - 32;
if (i < 0 ) {
pos = o = this.rotAdd([0, 48*scale], o, h);
} else if (i > 96 ) {
pos = this.rotAdd([16*scale, 0], o, h);
} else {
const d = dat[i], paths = d[2];
paths.map( p => {
t.up();
p.map( s=> {
t.down();
});
});
pos = this.rotAdd([22*scale, 0], pos, h);
}
});
}
return [Math.cos(h)*a[0] - Math.sin(h)*a[1] + b[0],
Math.cos(h)*a[1] + Math.sin(h)*a[0] + b[1]];
}
}

const dat = ('br>eoj^jl<jqirjskrjq>brf^fe<n^ne>`ukZdz<qZjz<dgrg<cmqm>`thZhw<lZlw<qao_l^h^e_caccdeefg'+
'gmiojpkqmqporlshsercp>^vs^as<f^h`hbgdeeceacaab_d^f^h_k`n`q_s^<olmmlolqnspsrrspsnqlol>]wtgtfsereqfph'+
'nmlpjrhsdsbraq`o`makbjifjekckaj_h^f_eaecffhimporqssstrtq>eoj`i_j^k_kajcid>cqnZl\\j_hcghglhqjulxnz>c'+
'qfZh\\j_lcmhmllqjuhxfz>brjdjp<egom<ogem>]wjajs<ajsj>fnkojpiojnkokqis>]wajsj>fnjniojpkojn>_usZaz>`ti'+
'^f_dbcgcjdofrisksnrpoqjqgpbn_k^i^>`tfbhak^ks>`tdcdbe`f_h^l^n_o`pbpdofmicsqs>`te^p^jfmfogphqkqmppnrk'+
'shserdqco>`tm^clrl<m^ms>`to^e^dgefhekenfphqkqmppnrkshserdqco>`tpao_l^j^g_ebdgdlepgrjsksnrppqmqlping'+
'hcecddaf_i^j^m_oapepjoomrjshserdp>fnjgihjikhjg<jniojpkojn>fnjgihjikhjg<kojpiojnkokqis>^vrabjrs>]wag'+
'sg<amsm>^vbarjbs>asdcdbe`f_h^l^n_o`pbpdofngjijl<jqirjskrjq>]xofndlcicgdfeehekfmhnknmmnk<icgefhfkgmh'+
'q^qs<chqh>fnj^js>brn^nnmqlrjshsfreqdndl>_tc^cs<q^cl<hgqs>`qd^ds<dsps>^vb^bs<b^js<r^js<r^rs>_uc^cs<c'+
'^qs<q^qs>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^>_tc^cs<c^l^o_p`qbqepgohlici>_uh^f_daccbfbkcnd'+
'pfrhslsnrppqnrkrfqcpan_l^h^<koqu>_tc^cs<c^l^o_p`qbqdpfoglhch<jhqs>`tqao_l^h^e_caccdeefggmiojpkqmqpo'+
'rlshsercp>brj^js<c^q^>_uc^cmdpfrisksnrppqmq^>asb^js<r^js>^v`^es<j^es<j^os<t^os>`tc^qs<q^cs>asb^jhjs'+
'<r^jh>`tq^cs<c^q^<csqs>cqgZgz<hZhz<gZnZ<gznz>cqc^qv>cqlZlz<mZmz<fZmZ<fzmz>brj\\bj<j\\rj>asazsz>fnkc'+
'ieigjhkgjfig>atpeps<phnfleiegfehdkdmepgrislsnrpp>`sd^ds<dhffhekemfohpkpmopmrkshsfrdp>asphnfleiegfeh'+
'dkdmepgrislsnrpp>atp^ps<phnfleiegfehdkdmepgrislsnrpp>asdkpkpiognfleiegfehdkdmepgrislsnrpp>eqo^m^k_j'+
'bjs<gene>atpepuoxnylzizgy<phnfleiegfehdkdmepgrislsnrpp>ate^es<eihfjemeofpips>fni^j_k^j]i^<jejs>eoj^'+
'k_l^k]j^<kekvjyhzfz>are^es<oeeo<ikps>fnj^js>[y_e_s<_ibfdegeifjijs<jimfoeretfuius>ateees<eihfjemeofp'+
'ips>atiegfehdkdmepgrislsnrppqmqkphnfleie>`sdedz<dhffhekemfohpkpmopmrkshsfrdp>atpepz<phnfleiegfehdkd'+
'mepgrislsnrpp>cpgegs<gkhhjfleoe>bsphofleieffehfjhkmlompopporlsisfrep>eqj^jokrmsos<gene>ateeeofrhsks'+
'mrpo<peps>brdejs<pejs>_ubefs<jefs<jens<rens>bseeps<pees>brdejs<pejshwfydzcz>bspees<eepe<esps>cqlZj['+
'i\\h^h`ibjckekgii<j[i]i_jakbldlfkhgjkllnlpkrjsiuiwjy<ikkmkojqirhthvixjylz>fnjZjz>cqhZj[k\\l^l`kbjci'+
'eigki<j[k]k_jaibhdhfihmjilhnhpirjskukwjy<kkimiojqkrltlvkxjyhz>^vamakbhdgfghhlknlplrksi<akbidhfhhill'+
'nmpmrlsisg>brb^bscsc^d^dsese^f^fsgsg^h^hsisi^j^jsksk^l^lsmsm^n^nsoso^p^psqsq^r^rs').split('>').map(
r=> { return [r.charCodeAt(0)-106,r.charCodeAt(1)-106, r.substr(2).split('<').map(a => {const ret
= []; for (let i=0; i<a.length; i+=2) {ret.push(a.substr(i, 2).split('').map(b => b.charCodeAt(0)
-106));} return ret; })]; });

return new Text();
}```