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

// Cloned by Andrey Totev on 27 Dec 2020 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  = 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, "&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 ) )
      {
        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);
   
}