// 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, "'" ) ); } // 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( "
" +
"Image from here.
Generation " + generation + "
" +
" Total population score " + sumscore + "
" +
" Total population fitness " + sumfitness.toPrecision(3) + "
Maximum possible score found. Highlighted in green below.
" +
"Random search would have to search number of possible strings = " + NOCHARS + "" + len + "
" +
"But we found goal string after searching only " + generation + " * " + popsize + " strings.
"; } s = s + "
Population member | String | Score | Fitness |
" + i + " | " + "" + escapeAllHtml ( population[i].getPhrase() ) + " | " + "" + population[i].score + " | " + "" + population[i].fitness.toPrecision(3) + " |