Genetic algorithm: an implementation using JavaScript and HTML5

• Download GAPopulationViz.zip - 3 KB

Introduction

Genetic Algorithm (GA) is a heuristic search algorithm based on the principles of biological evolution. Scores of literature and implementations in different languages are available. The purpose of this article is to demonstrate building a simple genetic algorithm simulation using JavaScript and HTML5. The article highlights the basic building blocks of the GA - the operators: cross-over, mutation and selection implemented in JavaScript. A visualization for the simulation progress is also built using a HTML5 canvas; which basically shows the evolution of the genes as the simulation progresses. The article would not go over into very details of GA, as the reader can familiarize herself by referring elaborate treatise available. The basic intend here is to experiment with JavaScript and HTML5 in implementing a GA platform with a visual aid-in component.

A working demonstration of the simulation can be found here in this JSFiddle.

Background

Genetic Algorithm is commonly employed in optimization problems by adopting the principles of biological evolution. The GA benefits the most in scenarios where a deterministic solution may not be feasible or is very costly to implement and an approximation to the optimum solution is good enough. The basic idea is to evolve a set of candidate solutions called the Phenotypes towards a better solution. Each phenotype has a set of properties called Genotypes which are free to be altered and mutated. The process of representation of the phenotype in terms of the genotypes is called encoding. This is typically done in the form array of bits [0 and 1, 0 being the property not present and 1 being present] or strings, although many other forms encoding are available. This article uses array of bits as the encoding. 

Problem domain and Fitness Function

The original problem is taken from this post.

In this article, the Knapsack combinational problem would be demonstrated. Given a set of items each having a value point and weight. the optimum set of items needs to be found so that the total weight is within the maximum capacity (that of the container or the bag) and the total value point is maximized. Here, the set of items would be the phenotype and the sequence of inclusion or exclusion of the items (represented by 1 or 0) in the set would be the genotype. There can be many combinations of items which comprises the population of the phenotypes. The solution from the GA would be the optimum genotype. When it is said "optimum", the genotypes are evaluated based on a Fitness function. The optimum genotype(s) maximizes the fitness function for the problem domain. For the Knapsack problem the fitness function evaluates the sum of the value points of the selected items in a genotype. If for a particular genotype the sum of the weights of the selected items exceeds the capacity then a penalty is applied for the fitness function value by marking the evaluation as "0".  Basically a genotype which fails to meet the weight criteria is regarded as the most "unfit". The encoding schematic is depicted below:

The GA kicks off with an initial population of phenotypes which are typically randomly created. The GA needs to keep evolving new genotypes from the population, evaluate the fitness of each genotypes at each iteration. A portion of the unfit genotypes are discarded at each iteration and replaced with the genotypes which have better fitness. Thus the population continually evolves with genotypes having better fitness. Since this is a heuristic search the tolerance criteria to break the iteration varies and many times depends on the problem domain. Breaking after a certain number of iterations or checking if the fitness evaluation does not change within a set tolerance after a certain number of iterations are the common ones. This is where a visualization tools came in handy as it allows to monitor the progress of the GA.

Genetic Operators: Selection, Crossover and Mutation

Now the question is how the GA is going to evolve new genotypes? This is where the Genetic Operators come in. A GA would have typically three primary operators: cross-over, mutation and selection.

A cross-over operator mimics biological reproduction by combining two genotypes to produce the offspring. This is the primary operator to search the solution space for an optimum solution. The selection operator is applied first to select the genotypes for cross-over. The selection operator chooses the better genotypes for breeding (cross-over). The orchestration of the selection and the cross-over operator forms the core of the GA in terms of searching the optimum solution. The mutation operator mutates a genotype to inject genetic diversity in the population. This allows the algorithm to search for new solutions and avoid getting stuck in a local maxima. 

There can be many implementations for these operators and at times depend on the problem domain. For this article, the cross-over operator is implemented as a single point cross-over where the index (or the point) of the genotype array is randomly selected. The heads and the tails of the parent genotypes are exchanged at the chosen index to produce the offspring. When it comes to the selection operator, the basic idea is to choose the fittest genotypes for breeding with the perception that they would produce better offspring. In this implementation, at each stage of an iteration, the fitness of all the genotypes are evaluated and then they are sorted based on the evaluation. The first two genotypes are selected for cross-over. The bottom two genotypes in the population are discarded and the new offspring from the cross-over are put into the population. A cross-over probability is applied to introduce randomness in the process of cross-over which decides whether to cross-over or not.

The mutation operator implementation simply flips the bit of a genotype based on a mutation probability.

To stop the iteration, the algorithm is stopped at the 100^th iteration. This decision is arbitrary as the purpose of this article is to demonstrate a simple implementation. The implementation scheme of the cross-over and the mutation operators is shown below:

Using the code

Now the schematic of the GA is laid out it is time to implement it. This section would highlight implementation of each genetic operators in JavaScript and then would show how they are assembled together to build the GA. At the end, the visualization component developed in HTML5 would be discussed.

The code has just two files: scripts\ga_core.js and index.html. The reader can run the simulation by unzipping the attached zip and opening the index.html in her browser. Either Chrome or Firefox is required (the example does not work with the IE).

Phenotypes, Genotypes & Population

These are the core classes; this GA implementation is built on top of these classes.

The Phenotypes:

It represents an item which has a name, survival points (or value points) and weight. It is implemented using the Constructor pattern. 

//the Phenotype --> a Knapsack item
var Item = function(name, survivalPoints, weight) {
  this.name = name;
  this.survivalPoints = survivalPoints;
  this.weight = weight;
}

The following set of items is made available to the system:

//Knapsack items: name, survival points, weight
var items = [];
items.push(new Item("pocketknife", 10.00, 1.00));
items.push(new Item("beans", 20.00, 5.00));
items.push(new Item("potatoes", 15.00, 10.00));
items.push(new Item("unions", 2.00, 1.00));
items.push(new Item("sleeping bag", 30.00, 7.00));
items.push(new Item("rope", 10.00, 5.00));
items.push(new Item("compass", 30.00, 1.00));

The Genotypes:

It is modeled by the class Gene, which has the following properties: the underlying genotypes (an Array of bits [0/1]), the fitness function evaluation and the generation (at which iteration the Gene was created). A phenotype that is an Item object is required to create a Gene object. The prototype pattern is employed to define the functions at the Gene class level:

Gene construction and fitness related:

1. encode; which translates the phenotype to the corresponding genotype
2. calcFitness: evaluates the fitness function for the genotype
3. makeMax: a utility function to calculate the fitness if all the bits in the genotype were 1s: it would be used in the visualization of a Gene (explained later).

Genetic Operators:

1. onePointCrossOver: models the one point cross-over
2. mutate: mutates a genotype by randomly flipping the bits of the genotype

// represents an encoded gene
var Gene = function() {
  this.genotype;
  this.fitness;
  this.generation = 0;
}

The encode prototype function takes an Item (phenotype) as an input and encodes it as a bit Array. The idea is to randomly select an item from the items available and update the genotype Array. First the genotype array is initialized to 0s. A random item is selected by generating an index from 0 to the items.length - 1. The capacity is checked at each sampling and the genotype encoding is exited if the capacity is exceeded by the selected items so far. The encoding is done by marking the genotype entry at the selected index to 1.

// converts a phenotype to a genotype
Gene.prototype.encode = function(phenotype) {
  this.genotype = Array(phenotype.length).fill(0);
  var totalWeight = 0;
  while (totalWeight < weightlimit) { // make a genotype until criteria is met
    // pick an item at random
    var index = Math.floor(Math.random() * items.length);
    index == items.length ? index - 1 : index;
    totalWeight += items[index].weight;
    if (totalWeight >= weightlimit) { // break if weight limit exceeded
      break;
    }

    //encode as selected (=1)
    this.genotype[index] = 1;
  }
}

The calcFitness prototype function evaluates the fitness function for the problem domain based. The logic is simple: add up all survival points of all the selected items. Penalty is to be applied if the total weight of the selected items represented by the underlying genotype exceeds the capacity. Although while making a Gene the total weight is checked against the capacity, over the course of evolution a genotype may fail to meet this criteria (due to cross-over and mutation). The penalty is just to mark the evaluation as 0, as a genotype which fails the criteria is of no good value. 

//calculates the fitness function of the gene
Gene.prototype.calcFitness = function() {
  //select the genotype(s) with bit = 1
  function getItem(item, index) {
    return scope.genotype[index] > 0;
  }

  // calculate the sum of Survival Points --> used in reduce below
  function sumPoints(total, item) {
    return total + item.survivalPoints;
  }

  // calculate the sum of Weights --> used in reduce below
  function sumWeights(total, item) {
    return total + item.weight;
  }

  var scope = this;
  var selectedItems = items.filter(getItem); //fiter bits = 1
  this.fitness = selectedItems.reduce(sumPoints, 0);
  var totalWeight = selectedItems.reduce(sumWeights, 0);

  //penalty if > weightlimit => 0
  if (totalWeight > weightlimit) {
    this.fitness = 0;
  }
}

There is another utility prototype function called makeMax which basically computes the maximum fitness if all the items are encoded in the genotype, i.e.. the fitness of a genotype which has all the items selected. This is used to normalize the fitness value of various genotypes. The code list is not shown in the article, the reader can refer it in the source code attached. It's usage would be again discussed during the discourse of the visualization component.

The onePointCrossOver function performs cross-over of the Gene object with another Gene object supplied as parameter. First it generates a random number. If it is greater or equal than the cross-over probability then it performs the cross-over, otherwise it returns the original Gene objects.

//Cross-over operator: one point cross-over
Gene.prototype.onePointCrossOver = function(crossOverPr, anotherGene) {
  var prob = Math.random();

  //cross over if within cross over probability
  if (prob >= crossOverPr) {
    //cross over point:
    var crossOver = Math.floor(Math.random() * this.genotype.length);
    crossOver = crossOver == this.genotype.length ? crossOver - 1 : crossOver;
    var head1 = this.genotype.slice(0, crossOver);
    var head2 = anotherGene.genotype.slice(0, crossOver);
    var tail1 = this.genotype.slice(crossOver);
    var tail2 = anotherGene.genotype.slice(crossOver);

    //cross-over at the point and create the off-springs:
    var offSpring1 = new Gene();
    var offSpring2 = new Gene();
    offSpring1.genotype = head1.concat(tail2);
    offSpring2.genotype = head2.concat(tail1);
    return [offSpring1, offSpring2];
  }

  return [this, anotherGene];
}

The mutate function is driven by a mutation probability which logic is in similar lines with the onePointCrossOver function. It loops through the Array representing the genotype and generates a probability. If the probability is greater or equal than the mutation probability then the bit is flipped. 

//Mutation operator:
Gene.prototype.mutate = function(mutationPr) {
  for (var i = 0; i < this.genotype.length; i++) {
    //mutate if within cross over probability
    if (mutationPr >= Math.random()) {
      this.genotype[i] = 1 - this.genotype[i];
    }
  }
}

In the example code, a cross-over probability of 0.9 and a mutation probability of 0.3 is used. The reader is free to tweak these parameters and observe their effects on the simulation performance. It is one of critical aspects of a GA to get these parameters rightly tuned based on the problem at hand. It is not within the scope of this article to go over these details.

//the core genetic algorithm (cross over, mutation, selection)
//GA parameters:
//Cross-over probability:
var crossOverPr = 0.9;
//Mutation probability:
var mutationPr = 0.3;

Population:

With the Gene class modeled, it is time for the Population class. The Population class maintains the collection of the Phenotypes encoded as Genotypes and drives the evolution of the Genotypes towards the optimum solution. It has the following properties: 1) the Array of Gene objects 2) the current generation and 3) the solution which is the evaluation of the fittest Gene object at any level of iteration. The Population class also employs the constructor pattern which takes the size of the Phenotype space and then it creates number of Genes equal to the size parameter. It encodes each Gene object using a Gene object's encode function and pushes it to genes Array.

// represents a Population of Genes
var Population = function(size) {
  this.genes = [];
  this.generation = 0;
  this.solution = 0;
  // create and encode the genes
  while (size--) {
    var gene = new Gene();
    gene.encode(items);
    this.genes.push(gene);
  }
}

The Population class has the following prototype functions:

Solution related:

1. initialize: forces a re-calculation of fitness function for each Gene object in the Population object
2. generate: performs the core evolution of the Population using the various Genetic Operators

Genetic Operator:

1. select: selects the two best genotypes during each iteration.

The select function utilizes a helper function called compareFitness to sort the genes Array and then returns the first two genes:

//Compare fitness
function compareFitness(gene1, gene2) {
  return gene2.fitness - gene1.fitness;
}

//operator select : Rank-based fitness assignment
Population.prototype.select = function() {
  // sort and select the best
  this.genes.sort(compareFitness);
  return [this.genes[0], this.genes[1]];
}

The schematic of the generate function is depicted below which basically explains the algorithmic flow of the GA:

And here is the code listing of the function. The setTimeout method is called at end of every iteration, with a delay of 100 millisecond. After which it calls again the generate function. This is just to inject some delay between each iteration. The target problem is very simple here and the GA would run very fast which would make the visualization less interesting. In a real world application, no artificial delay would be desired between the iterations! The generate function calls a function called display which updates the simulation visually and is discussed in the following section.

//calculates one generation from the current population
Population.prototype.generate = function() {
  // select the parents
  parents = this.select();

  // cross-over
  var offSpring = parents[0].onePointCrossOver(crossOverPr, parents[1]);
  this.generation++;

  //re-place in population
  this.genes.splice(this.genes.length - 2, 2, offSpring[0], offSpring[1]);
  offSpring[0].generation = offSpring[1].generation = this.generation;

  //mutate the offspring
  for (var i = 0; i < this.genes.length; i++) {
    this.genes[i].mutate(mutationPr);
  }

  //recalculate fitness after cross-over & mutation:
  this.initialize();
  this.genes.sort(compareFitness);
  this.solution = population.genes[0].fitness; // pick the solution;

  //draw the population:
  display();

  //stop iteration after 100th generation
  //this assumption is arbitrary that the solution would convert after reaching
  //100th generation, there can be other criteria like no change in fitness
  if (this.generation >= 100) {
    return true;
  }

  // call generate again after a delay of 100 mili-second
  var scope = this;
  setTimeout(function() {
    scope.generate();
  }, 100);
}

Visualization of the Simulation:

At end of an iteration, the GA calls the helper function called display. The display function basically draws a matrix of circles on a HTML5 canvas, which is defined in the index.html. The matrix is 10x10 with each circle representing a Gene object in the Population object. A circle has a fill color with a certain opacity which is basically a normalized value of the fitness evaluation for the underlying Gene object. The makeMax function of the Gene class is used to normalize the evaluation value. A circle also carries a text which shows the generation number at which the underlying Gene object was created. As the simulation runs the circles in the upper region would have higher opacity and the below ones would have less opacity.

The display function also writes out an HTML before drawing the circle matrix which highlights the solution of the Population and the corresponding Genotype.

//function to draw the population on the canvas
function display(){
  var fitness = document.getElementById('fitness');
  //print the best Survival points and corresponding genotype:
  fitness.innerHTML = 'Survival Points:' + population.genes[0].fitness;
  fitness.innerHTML += '
Genotype:' + population.genes[0].genotype;

  context.clearRect(0, 0, canvas.width, canvas.height); //clear the canvas
  var index = 0;
  var radius = 30;
  //draw the Genes
  for(var i = 0; i < 10; i++){
    var centerY = radius + (i + 1) * 5 + i * 2 * radius; //Y
    for(var j = 0; j < 10; j++){
      var centerX = radius + (j + 1) * 5 + j * 2 * radius; //X
      context.beginPath();
      context.arc(centerX, centerY, radius, 0, 2 * Math.PI, false);
      // pick the fitness for opacity calculation;
      var opacity = population.genes[index].fitness / maxSurvivalPoints;
      context.fillStyle = 'rgba(0,0,255, ' + opacity + ')';
      context.fill();
      context.stroke();
      context.fillStyle = 'black';
      context.textAlign = 'center';
      context.font = 'bold 12pt Calibri';
      // print the generation number
      context.fillText(population.genes[index].generation, centerX, centerY);
      index++;
    }
  }
}

The JavaScript triggers the GA simulation in the window.onload. An output is shown below:

Points of Interest

The JavaScript in this example is developed as a quick prototyping exercise and is lumped in a single file. The future work can aim to separate the core algorithm and models from the visualization code. A Web-worker can be considered for loose coupling. The algorithm would send messages to the visualization code to continually update the simulation. Another dimension could be to host the algorithm as a NodeJS module and keep only the visualization code as the client script. I would encourage the reader to make the GA algorithm component fairly generic with the provision to inject the fitness function and keep the problem domain separate from the algorithm.

History