Skip to content

Instantly share code, notes, and snippets.

@coblezc

coblezc/DNA.js

Created April 4, 2017 23:24
Show Gist options
  • Save coblezc/0a4598b796907c71ea0acc9305c4771d to your computer and use it in GitHub Desktop.
Save coblezc/0a4598b796907c71ea0acc9305c4771d to your computer and use it in GitHub Desktop.
Download ZIP
Family Recipes
Raw
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();
}
}
}
}
Raw
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>
Raw
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;
}
}
Raw
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);
}
Raw
style.css
.stats, .all, .best {
font-family: "Courier";
}
.best {
font-size: 48;
}
.stats {
font-size: 24;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment