// port of
// https://github.com/nature-of-code/noc-examples-processing/tree/master/chp09_ga/NOC_9_01_GA_Shakespeare_simplified
// hugely modified
// because ported from Processing to JS
// The Nature of Code
// Daniel Shiffman
// http://natureofcode.com
// Genetic Algorithm, Evolving Shakespeare
// Demonstration of using a genetic algorithm to perform a search
const popsize = 100; // Population size
const pm = 0.01; // Mutation rate
// where score = no. of chars that match
// fitness = POWERBASE ^ score
// and we look at sum of all fitnesses
// so the bigger POWERBASE is, the more it focuses on letting only the very fittest reproduce
const POWERBASE = 4 ;
// turn on to see how it works in console:
const debugMutate = false;
const debugCrossover = false;
const debugMate = false;
// target string:
const target = "riverrun, past Eve and Adam's, from swerve of shore to bend of bay"; // Finnegans Wake opening line
// "To be, or not to be.";
const len = target.length;
const maxscore = len; // maximum possible score
var maxscoreFound = false; // exit loop when find one
var population;
var generation;
var sumscore, sumfitness;
const searching_audio = "/uploads/codingtrain/rain.mp3"; // http://soundbible.com/2011-Rain-Background.html
const success_audio = "/uploads/codingtrain/movie.start.mp3"; // http://soundbible.com/1676-Movie-Start-Music.html
var background_audio;
// DNA is string of printable chars
// https://en.wikipedia.org/wiki/ASCII#Printable_characters
const LOCHAR = 32;
const HICHAR = 126;
const NOCHARS = (HICHAR-LOCHAR)+1; // no. of possible chars
function randomChar()
{
var c = AB.randomIntAtoB ( LOCHAR, HICHAR );
return ( String.fromCharCode(c) );
}
// setup()
// # Step 1: The Population
// # Create an empty population (an array or ArrayList)
// # Fill it with DNA encoded objects (pick random values to start)
// draw()
// # Step 1: Selection
// # Create an empty mating pool (an empty ArrayList)
// # For every member of the population, evaluate its fitness based on some criteria / function,
// and add it to the mating pool in a manner consistant with its fitness, i.e. the more fit it
// is the more times it appears in the mating pool, in order to be more likely picked for reproduction.
// # Step 2: Reproduction Create a new empty population
// # Fill the new population by executing the following steps:
// 1. Pick two "parent" objects from the mating pool.
// 2. Crossover -- create a "child" object by mating these two parents.
// 3. Mutation -- mutate the child's DNA based on a given probability.
// 4. Add the child object to the new population.
// # Replace the old population with the new population
//
// # Rinse and repeat
// escape HTML
// https://stackoverflow.com/questions/6234773/can-i-escape-html-special-chars-in-javascript
function escapeAllHtml ( str )
{
return (
str
.replace( /&/g, "&" )
.replace( /</g, "<" )
.replace( />/g, ">" )
.replace( /"/g, """ )
.replace( /'/g, "'" )
);
}
// The Nature of Code
// Daniel Shiffman
// http://natureofcode.com
// Genetic Algorithm, Evolving Shakespeare
// A class to describe a psuedo-DNA, i.e. genotype
// Here, a virtual organism's DNA is an array of character.
// Functionality:
// -- convert DNA into a string
// -- calculate DNA's "fitness"
// -- mate DNA with another set of DNA
// -- mutate DNA
//--- DNA class
function DNA()
{
// this code executes on construction:
this.genes = new Array(len);
for (var i = 0; i < len; i++)
this.genes[i] = randomChar();
this.score;
this.fitness;
// Converts character array to a String
this.getPhrase = function()
{
var s = "";
for (var i = 0; i < len; i++)
s = s + this.genes[i];
return ( s );
};
// Fitness function (how many correct characters)
this.calcFitness = function()
{
this.score = 0;
for (var i = 0; i < len; i++)
if ( this.genes[i] == target.charAt(i) )
this.score++;
if ( this.score == maxscore ) maxscoreFound = true;
// all fitness zero causes problems, maybe even divide by zero
// at start, most have char score zero - could even all have score zero
// x to power of score will always be non-zero
this.fitness = Math.pow ( POWERBASE, this.score );
};
// Crossover
this.crossover = function (partner)
{
// A new child
var child = new DNA();
var x = AB.randomIntAtoB ( 0, len-1 ); // Pick a cut point
// Half from one, half from the other
for (var i = 0; i < len; i++)
{
if (i < x) child.genes[i] = this.genes[i];
else child.genes[i] = partner.genes[i];
}
if ( debugCrossover )
{
console.log ("--- start crossover -----------")
console.log ("parent " + this.getPhrase() );
console.log ("parent " + partner.getPhrase() );
console.log ("x " + x );
console.log ("child " + child.getPhrase() );
}
return (child);
};
// Based on a mutation probability, picks a new random character
this.mutate = function()
{
for (var i = 0; i < len; i++)
if ( AB.randomEventProb ( pm ) )
{
if ( debugMutate )
{
console.log ("--- start mutate -----------")
console.log ("original " + this.getPhrase() );
console.log ("i " + i );
}
this.genes[i] = randomChar();
if ( debugMutate )
console.log ("new " + this.getPhrase() );
}
};
}
// end of DNA class
function setup()
{
background_audio = AB.backgroundMusic ( searching_audio );
// slower frame rate to see how it is working
// frameRate (1);
noCanvas();
AB.headerRHS();
AB.newDiv("header");
$("#header").css({
"padding-top": "30",
"padding-left": "30",
"padding-bottom": "10"
});
$("#header").html( "<h1> Writing the first line of Finnegans Wake </h1> " +
"<p><img border=1 src='/uploads/codingtrain/finnegans.jpg'> <br>" +
"Image from <a href='https://archive.org/details/finneganswake00joycuoft/page/n15'>here</a>.</p>" );
population = new Array(popsize);
for (var i = 0; i < popsize; i++)
population[i] = new DNA();
generation = 1;
calcAllFitness();
drawPopulation();
}
function draw() // every step, move the population on and draw it
{
// P5 shows runs header by default
// to get rid of run header:
// AB.hideRunHeader();
stepPopulation();
generation++;
calcAllFitness();
drawPopulation();
if ( maxscoreFound )
{
noLoop(); // end P5 loop
background_audio.pause();
background_audio = AB.backgroundMusic ( success_audio );
}
}
function calcAllFitness()
{
sumscore = 0;
sumfitness = 0;
for (var i = 0; i < popsize; i++)
{
population[i].calcFitness();
sumscore = sumscore + population[i].score;
sumfitness = sumfitness + population[i].fitness;
}
}
function pickFitMate()
// pick an individual for mating, based on fitness
// fittest need to be more likely to be picked for mating
// uses simple summation of fitness (not Boltzmann), plus spin the weighted wheel
// fitness cannot be zero or could get divide by zero
{
var p = AB.randomFloatAtoB ( 0, sumfitness );
// random point between 0 and sum of fitnesses
// find the individual intersecting this point
if ( debugMate )
{
console.log ("--- start pick mate ----------");
console.log ("p " + p);
}
var x = 0;
for (var i = 0; i < popsize; i++)
{
x = x + population[i].fitness;
if ( x > p ) return i;
}
return (popsize-1);
}
function stepPopulation()
{
var newpopulation = new Array(popsize);
for (var i = 0; i < popsize; i++)
{
var c = pickFitMate();
if ( debugMate ) console.log ("picked " + c );
var d = pickFitMate();
if ( debugMate ) console.log ("picked " + d );
var child = population[c].crossover ( population[d] );
child.mutate();
newpopulation[i] = child;
}
population = newpopulation;
}
function drawPopulation()
{
var s = "<p> Generation " + generation + "<br>" +
" Total population score " + sumscore + "<br>" +
" Total population fitness " + sumfitness.toPrecision(3) + "</p>";
if ( maxscoreFound )
{
s = s + "<p><b> Maximum possible score found. Highlighted in green below. <br> " +
"Random search would have to search number of possible strings = " + NOCHARS + "<sup>" + len + "</sup> <br>" +
"But we found goal string after searching only " + generation + " * " + popsize + " strings.</b> <p>";
}
s = s + "<table border=1 BORDERCOLOR=silver cellpadding=5 cellspacing=0 >" +
"<tr style='background-color:#ffffcc;'><td> Population member </td><td> String </td><td> Score </td><td> Fitness </td></tr>";
for (var i = 0; i < popsize; i++)
{
if ( population[i].score == maxscore ) s = s + "<tr style='background-color:#ccffcc;'>";
else s = s + "<tr>";
s = s + "<td>" + i + "</td>" +
"<td style='font-size:larger'><tt>" + escapeAllHtml ( population[i].getPhrase() ) + "</tt></td>" +
"<td>" + population[i].score + "</td>" +
"<td>" + population[i].fitness.toPrecision(3) + "</td></tr>";
}
s = s + "</table>";
AB.newDiv("theoutput");
$("#theoutput").css({
"padding-left": "30",
"padding-bottom": "30"
});
$("#theoutput").html(s);
}