// Cloned by Theo Delettre on 19 Nov 2021 from World "GA (Finnegans Wake)" by "Coding Train" project
// Please leave this clone trail here.
// 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 = 1000; // 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 = "Let any fish who meets my gaze learn the true meaning of fear; for I am the harbinger of death. The bane of creatures sub-aqueous, my rod is true and unwavering as I cast into the aquatic abyss. A man, scorned by this uncaring Earth, finds solace in the sea. My only friend, the worm upon my hook. Wriggling, writhing, struggling to surmount the mortal pointlessness that permeates this barren world. I am alone. I am empty. And yet, I fish."; // 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);
}