coblezc/DNA.js

## DNA.js
// The Nature of Code
// Daniel Shiffman
// http://natureofcode.com

// Genetic Algorithm, Evolving Shakespeare

// A class to describe a pseudo-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

function newChar() {
  var c = floor(random(63, 122));
  if (c === 63) c = 32;
  if (c === 64) c = 46;

  return String.fromCharCode(c);
}

// Constructor (makes a random DNA)
function DNA(num) {
  // The genetic sequence
  this.genes = [];
  this.fitness = 0;
  for (var i = 0; i < num; i++) {
    this.genes[i] = newChar(); // Pick from range of chars
  }

  // Converts character array to a String
  this.getPhrase = function() {
    return this.genes.join("");
  }

  // Fitness function (returns floating point % of "correct" characters)
  this.calcFitness = function(target) {
    var score = 0;
    for (var i = 0; i < this.genes.length; i++) {
      if (this.genes[i] == target.charAt(i)) {
        score++;
      }
    }
    this.fitness = score / target.length;
  }

  // Crossover
  this.crossover = function(partner) {
    // A new child
    var child = new DNA(this.genes.length);

    var midpoint = floor(random(this.genes.length)); // Pick a midpoint

    // Half from one, half from the other
    for (var i = 0; i < this.genes.length; i++) {
      if (i > midpoint) child.genes[i] = this.genes[i];
      else child.genes[i] = partner.genes[i];
    }
    return child;
  }

  // Based on a mutation probability, picks a new random character
  this.mutate = function(mutationRate) {
    for (var i = 0; i < this.genes.length; i++) {
      if (random(1) < mutationRate) {
        this.genes[i] = newChar();
      }
    }
  }
}

## index.html
<html>
<head>
  <meta charset="UTF-8">
  <script language="javascript" type="text/javascript" src="libraries/p5.js"></script>
  <!-- uncomment lines below to include extra p5 libraries -->
  <script language="javascript" src="libraries/p5.dom.js"></script>
  <!--<script language="javascript" src="libraries/p5.sound.js"></script>-->
  <script language="javascript" type="text/javascript" src="sketch.js"></script>
  <script language="javascript" type="text/javascript" src="DNA.js"></script>
  <script language="javascript" type="text/javascript" src="Population.js"></script>
    <link rel="stylesheet" href="style.css">
</head>

<body>
</body>
</html>

## population.js
// The Nature of Code
// Daniel Shiffman
// http://natureofcode.com

// Genetic Algorithm, Evolving Shakespeare

// A class to describe a population of virtual organisms
// In this case, each organism is just an instance of a DNA object

function Population(p, m, num) {

  this.population;                   // Array to hold the current population
  this.matingPool;                   // ArrayList which we will use for our "mating pool"
  this.generations = 0;              // Number of generations
  this.finished = false;             // Are we finished evolving?
  this.target = p;                   // Target phrase
  this.mutationRate = m;             // Mutation rate
  this.perfectScore = 1;

  this.best = "";

  this.population = [];
  for (var i = 0; i < num; i++) {
    this.population[i] = new DNA(this.target.length);
  }
    this.matingPool = [];

  // Fill our fitness array with a value for every member of the population
  this.calcFitness = function() {
    for (var i = 0; i < this.population.length; i++) {
      this.population[i].calcFitness(target);
    }
  }
  this.calcFitness();

  // Generate a mating pool
  this.naturalSelection = function() {
    // Clear the ArrayList
    this.matingPool = [];

    var maxFitness = 0;
    for (var i = 0; i < this.population.length; i++) {
      if (this.population[i].fitness > maxFitness) {
        maxFitness = this.population[i].fitness;
      }
    }

    // Based on fitness, each member will get added to the mating pool a certain number of times
    // a higher fitness = more entries to mating pool = more likely to be picked as a parent
    // a lower fitness = fewer entries to mating pool = less likely to be picked as a parent
    for (var i = 0; i < this.population.length; i++) {

      var fitness = map(this.population[i].fitness,0,maxFitness,0,1);
      var n = floor(fitness * 100);  // Arbitrary multiplier, we can also use monte carlo method
      for (var j = 0; j < n; j++) {              // and pick two random numbers
        this.matingPool.push(this.population[i]);
      }
    }
  }

  // Create a new generation
  this.generate = function() {
    // var popLast;
    // Refill the population with children from the mating pool
    for (var i = 0; i < this.population.length; i++) {
      var a = floor(random(this.matingPool.length));
      var b = floor(random(this.matingPool.length));
      var partnerA = this.matingPool[a];
      var partnerB = this.matingPool[b];
      var child = partnerA.crossover(partnerB);
      child.mutate(this.mutationRate);
      this.population[i] = child;
    }
    this.generations++;
  }


  this.getBest = function() {
    newPhrasePosition = this.population.length - 1;
    newPhrase = this.population[newPhrasePosition].getPhrase();
    return newPhrase;
  }

  // Compute the current "most fit" member of the population
  this.evaluate = function() {
    var worldrecord = 0.0;
    var index = 0;
    for (var i = 0; i < this.population.length; i++) {
      if (this.population[i].fitness > worldrecord) {
        index = i;
        worldrecord = this.population[i].fitness;
      }
    }

    this.best = this.population[index].getPhrase();
    if (worldrecord === this.perfectScore) {
      this.finished = true;
    }
  }

  this.isFinished = function() {
    return this.finished;
  }

  this.getGenerations = function() {
    return this.generations;
  }

  // Compute average fitness for the population
  this.getAverageFitness = function() {
    var total = 0;
    for (var i = 0; i < this.population.length; i++) {
      total += this.population[i].fitness;
    }
    return total / (this.population.length);
  }

  this.allPhrases = function() {
    var everything = "";

    var displayLimit = min(this.population.length,50);


    for (var i = 0; i < displayLimit; i++) {
      everything += this.population[i].getPhrase() + "<br>";
    }
    return everything;
  }
}


## sketch.js
// The Nature of Code
// Daniel Shiffman
// http://natureofcode.com

// ZC: not including p5 libraies here, but they're required

// Genetic Algorithm, Evolving Shakespeare

// Demonstration of using a genetic algorithm to perform a search

// 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


var target;
var popmax;
var mutationRate;
var population;

var bestPhrase;
var allPhrases;
var stats;

var newPhrases;

function setup() {
  // bestPhrase = createP("Best phrase:");
  bestPhrase = createP("");
  //bestPhrase.position(10,10);
  bestPhrase.class("stats");

  bestPhrase1 = createP();
  bestPhrase1.class("stats");

  bestPhrase2 = createP();
  bestPhrase2.class("stats");

  bestPhrase3 = createP();
  bestPhrase3.class("stats");

  stats = createP("");
  stats.class("stats");

  target = "1 cup peanut butter";
  target1 = "1 large egg";
  target2 = "1 cup sugar";
  target3 = "1 teaspoon vanilla";
  popmax = 200;
  mutationRate = 0.01;

  // Create a population with a target phrase, mutation rate, and population max
  population = new Population(target, mutationRate, popmax);
  population1 = new Population(target1, mutationRate, popmax);
  population2 = new Population(target2, mutationRate, popmax);
  population3 = new Population(target3, mutationRate, popmax);
}

function draw() {
  population.naturalSelection();
  population.generate();
  population.calcFitness();
  population.evaluate();
  displayInfo();
  if (population.isFinished()) {
    noLoop();
  }

  population1.naturalSelection();
  population1.generate();
  population1.calcFitness();
  population1.evaluate();
  displayInfo1();
  if (population1.isFinished()) {
    noLoop();
  }

  population2.naturalSelection();
  population2.generate();
  population2.calcFitness();
  population2.evaluate();
  displayInfo2();
  if (population2.isFinished()) {
    noLoop();
  }

  population3.naturalSelection();
  population3.generate();
  population3.calcFitness();
  population3.evaluate();
  displayInfo3();
  if (population3.isFinished()) {
    noLoop();
  }
}

function displayInfo() {
  // Display current status of population
  var answer = population.getBest();
  // bestPhrase.html("Best phrase:<br>" + answer);
  bestPhrase.html("<i>Granny's Peanut Butter Cookies:</i>:<br>" + answer);
}

function displayInfo1() {
  var answer1 = population1.getBest();
  bestPhrase1.html(answer1);
}

function displayInfo2() {
  var answer2 = population2.getBest();
  bestPhrase2.html(answer2);
}

function displayInfo3() {
  var answer3 = population3.getBest();
  bestPhrase3.html(answer3);
}

## style.css
.stats, .all, .best {
  font-family: "Courier";
}

.best {
  font-size: 48;
}

.stats {
  font-size: 24;
}
	// The Nature of Code
	// Daniel Shiffman
	// http://natureofcode.com

	// Genetic Algorithm, Evolving Shakespeare

	// A class to describe a pseudo-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

	function newChar() {
	var c = floor(random(63, 122));
	if (c === 63) c = 32;
	if (c === 64) c = 46;

	return String.fromCharCode(c);
	}

	// Constructor (makes a random DNA)
	function DNA(num) {
	// The genetic sequence
	this.genes = [];
	this.fitness = 0;
	for (var i = 0; i < num; i++) {
	this.genes[i] = newChar(); // Pick from range of chars
	}

	// Converts character array to a String
	this.getPhrase = function() {
	return this.genes.join("");
	}

	// Fitness function (returns floating point % of "correct" characters)
	this.calcFitness = function(target) {
	var score = 0;
	for (var i = 0; i < this.genes.length; i++) {
	if (this.genes[i] == target.charAt(i)) {
	score++;
	}
	}
	this.fitness = score / target.length;
	}

	// Crossover
	this.crossover = function(partner) {
	// A new child
	var child = new DNA(this.genes.length);

	var midpoint = floor(random(this.genes.length)); // Pick a midpoint

	// Half from one, half from the other
	for (var i = 0; i < this.genes.length; i++) {
	if (i > midpoint) child.genes[i] = this.genes[i];
	else child.genes[i] = partner.genes[i];
	}
	return child;
	}

	// Based on a mutation probability, picks a new random character
	this.mutate = function(mutationRate) {
	for (var i = 0; i < this.genes.length; i++) {
	if (random(1) < mutationRate) {
	this.genes[i] = newChar();
	}
	}
	}
	}
	<html>
	<head>
	<meta charset="UTF-8">
	<script language="javascript" type="text/javascript" src="libraries/p5.js"></script>
	<!-- uncomment lines below to include extra p5 libraries -->
	<script language="javascript" src="libraries/p5.dom.js"></script>
	<!--<script language="javascript" src="libraries/p5.sound.js"></script>-->
	<script language="javascript" type="text/javascript" src="sketch.js"></script>
	<script language="javascript" type="text/javascript" src="DNA.js"></script>
	<script language="javascript" type="text/javascript" src="Population.js"></script>
	<link rel="stylesheet" href="style.css">
	</head>

	<body>
	</body>
	</html>
	.stats, .all, .best {
	font-family: "Courier";
	}

	.best {
	font-size: 48;
	}

	.stats {
	font-size: 24;
	}