Code viewer for World: GA (Finnegans Wake) (clone...

// Cloned by Zhensheng Tan on 25 Nov 2019 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  = 2000;      // Population size
const  pm       = 0.25;     // Mutation rate
const  pmDeclinePerGen = 0.97


// 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    = "FROM fairest creatures we desire increase,That thereby beauty's rose might never die,But as the riper should by time decease,His tender heir might bear his memory: But thou, contracted to thine own bright eyes,Feed'st thy light'st flame with self-substantial fuel,Making a famine where abundance lies,Thyself thy foe, to thy sweet self too cruel.Thou that art now the world's fresh ornamentAnd only herald to the gaudy spring,Within thine own bud buriest thy content And, tender churl, makest waste in niggarding. Pity the world, or else this glutton be, To eat the world's due, by the grave and thee.";        // 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, "&lt;"   )
         .replace( />/g, "&gt;"   )
         .replace( /"/g, "&quot;" )
         .replace( /'/g, "&#039;" )
		);
}



// 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 * Math.pow( pmDeclinePerGen, generation ) ) )
      {
        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 (10);
   
    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);
   
}