TL;DR
In this post I present an implementation of the Classic Genetic Algorithm version, as an interactive widget, using binary representation of chromosome (we use 0/1 bits as a genes in chromosome, to encode variables). As you may know from previous post, this king of representation make operators easier to implement.
In this post I would like to share with you an implementation of the Classic Genetic Algorithm version in JavaScript. The implementation is available on this blog Github.
Below I embedded my implementation of the Classic Genetic Algorithm using binary chromosome representation.
Classic Genetic Algorithm widget
Just click Execute button and see the results. I created three sections, first with all parameters prefilled, second to see visualization of the function in 3D and results with all chromosomes from the last population containing final solution. Feel free to manipulate parameters to see how it affects results.
Above widget available also repository Github page here.
The code
The widget above has a little bit more than just a RAW classic algorithm. I added there function visualization and some basic controls parametrizing the algorithm. I will focus on algorithm code only. I implemented solution in pure JavaScript ES5, to make it work everywhere just like that. Implementation was quite easy, so I could resign of ES6.
The code I prepared consists of two main JavaScript files:
Chromosome structure
I used following object structure for single chromosome (expressed here in TypeScript):
{
genes: number[]; // array of bits (0/1 values)
eval: number; // calculated value of function for given x,y => f(x,y)
x: number; // decoded position X (from genes binary array)
y: number; // decoded position Y (from genes binary array)
}Helper functions
I implemented following helper functions for encoding/decoding binary representation of chromosome. First one is to decode binary array into decimal number.
/**
* Converts binary array to decimal number.
* @param binaryArray Array of 0/1 values to convert.
* @returns {number} Result is a decimal number.
*/
function binaryArrayToNumber(binaryArray) {
var result = 0;
var exponent = binaryArray.length - 1;
for (var i = 0; i < binaryArray.length; i++) {
if (binaryArray[i]) {
result += Math.pow(2, exponent);
}
exponent--;
}
return result;
}To decode chromosome into two x,y values we have to calculate following equations, which I explained earlier in [3] Genetic Algorithms: Binary chromosomes.
\[ x = x_1 + \frac{decimal(\textrm{genes representing x})\cdot (x_n – x_1)}{2^N – 1}\]
\[ y = y_1 + \frac{decimal(\textrm{genes representing y})\cdot (y_n – y_1)}{2^N – 1}\]
where
\( x, y \) – represent position of chromosome – solution in search space,
\( x_1 \dots x_n \) – is the available range on X axis,
\( y_n \dots y_n \) – is the available range on Y axis,
\( N \) – is the number of bits representing single variable x or y in genes: number[] array,
\( decimal(…) \) – is the function binaryArrayToNumber(binaryArray).
In code it looks like this:
/**
* Decodes array of numbers 0 or 1 into array of variables.
* @param binaryArray Array of 0,1 values that represents a chromosome (array of genes).
* The length of the array must be divisible by numberOfVariables.
* @param numberOfVariables The number of variables encoded in binary array.
* @param ranges An array of two element arrays containing ranges of values,
* first element in each array is starting value, second element is ending value.
* @returns {number[]} Returns array of floating point numbers encoded in {@param binaryArray}.
*/
function decodeBinaryChromosome(binaryArray, numberOfVariables, ranges) {
if (binaryArray.length % numberOfVariables > 0) {
throw new Error('Invalid number of variables or binary array length. ' +
'The length of the array must be divisible by number of variables.');
}
var result = [];
var variableSize = binaryArray.length / numberOfVariables;
for (var i = 0; i < numberOfVariables; i++) {
var binArray = binaryArray.slice(i * variableSize, i * variableSize + variableSize);
var decimalValue = binaryArrayToNumber(binArray);
var value = ranges[i][0] + decimalValue * (ranges[i][1] - ranges[i][0]) / (Math.pow(2, variableSize) - 1);
result.push(value);
}
return result;
}Additionally I created opposite function to encode x,y chromosome variables back into binary array. We can transform previous equations into:
\[ decimal(\textrm{genes representing x}) = \frac{(x-x_1) \cdot (2^N-1)}{x_n-x_1} \]
\[ decimal(\textrm{genes representing y}) = \frac{(y-y_1) \cdot (2^N-1)}{y_n-y_1} \]
In code I’ve made small optimization and I create whole string array of bits first then, I convert string of 0/1 into numeric array.
/**
* Encodes given variables into binary array of given ranges, with fixed number of bits for each of variables.
* @param values Floating point values to be encoded.
* @param variableSize Size of the single variable in bits.
* @param ranges An array of two-element arrays containing ranges of values,
* first element in each array is starting value, second element is ending value.
* @returns {number[]} An array of 0,1 values representing a chromosome.
*/
function encodeBinaryChromosome(values, variableSize, ranges) {
var finalBinaryString = '';
for (var i = 0; i < values.length; i++) {
var range = ranges[i];
var decValue = Math.round((Math.pow(2, variableSize) - 1) * (values[i] - range[0]) / (range[1] - range[0]));
var binaryString = decValue.toString(2);
var missingNumberOfZeroes = variableSize - binaryString.length;
finalBinaryString += Array(missingNumberOfZeroes + 1).join('0') + binaryString;
}
return Array.from(finalBinaryString.split(''), Number);
}The decimal value calculation is highlighted. You can notice that the result is rounded to integer. This is caused by possible JavaScript precision problems, because in JS, sometimes after calculation you can get a small error on 10-th position after the comma. That would cause above equations to fail. I assume that possible x and y values are not any floating point numbers, but values with specific precision denoted by \( N \) (number of bits representing single variable). Bigger \( N \) gives as better precision (more discrete values), so we get our ranges divided into more sub ranges.
Algorithm structure function
The main part of algorithm is a function run(options) below:
function run(options) {
if (options) {
EVAL_FN = options.evalFunction;
VARIABLE_SIZE = options.variableSize;
CHROMOSOME_SIZE = VARIABLE_SIZE * 2;
MUTATION_PROBABILITY = options.pm;
CROSSOVER_PROBABILITY = options.pc;
POPULATION_SIZE = options.popSize;
SELECTION_COUNT = options.selCount;
MAX_GENERATIONS = options.maxGenerations;
MAXIMIZATION = options.maximize;
space.x1 = options.x1;
space.xn = options.xn;
space.y1 = options.y1;
space.yn = options.yn;
}
// Classic genetic algorithm - binary chromosome representation
// 1. Create an initial population
// during generation we also evaluate each chromosome value
population = createPopulation();
// 2. Start calculations
var generation = 0;
while (generation < MAX_GENERATIONS) {
crossover(); // generates new chromosomes to fill in population
mutation(); // mutate random genes in chosen chromosomes
evaluation(); // make sure everything is calculated correctly after all operators
selection(); // leave only the best solutions and limit population back to fixed size
generation++;
}
// 3. Sort population and get the best individual
selection();
return population;
}We have 3 sections here:
- Initial population generation
The initial chromosomes set is randomly generated, this is the population which we start with. - Main calculations loop
Here we create generations of chromosomes. One by one, the part of old population dies, new chromosomes are created by crossover, mutation introduces unpredictable changes, finally we make sure that all chromosomes have calculated objective function value. - Final sorting (selection)
At the end we finally make one more final population selection, to sort population and leave only the best chromosomes with the highest evaluation function values.
Function requires a set of parameters that are explained below:
options.evalFunction // string representation of evaluation function e.g. sin(x)*y
options.variableSize // number of bits (genes) used to encode one variable e.g. x position
options.pm // mutation probability 0.0 ... 1.0
options.pc // crossover probability 0.0 ... 1.0
ptions.popSize // population initial size
options.selCount // selection count - number of the best chromosomes left after selection
options.maxGenerations // maximum number of iterations of algorithm
options.maximize // true if we search for maximum, false if minimum
options.x1 // starting point of search space on X axis
options.xn // ending point of search space on X axis
options.y1 // starting point of search space on Y axis
options.yn // ending point of search space on Y axisInitial population
In first part of algorithm we prepare initial population from random chromosomes:
/**
* Creates a new population of chromosomes.
* @returns {[]} An array of new random chromosomes.
*/
function createPopulation() {
var population = [];
for (var i = 0; i < POPULATION_SIZE; i++) {
population.push(generateChromosome());
}
return population;
}Breeding / Crossover
Nest step is to start first of 4 common algorithm phases – crossover. This operator extends a population by new chromosomes created from two parents selected randomly from actual population.
/**
* Generates new chromosomes by crossover (extends population).
*/
function crossover() {
var parents = [];
for (var i = 0; i < population.length; i++) {
if (parents.indexOf(i) >= 0) {
continue; // skip already selected parent
}
if (Math.random() < CROSSOVER_PROBABILITY) {
parents.push(i);
}
}
// if odd number of parents choose one more
var index = -1;
while (parents.length % 2 === 1) {
index++;
index = index === population.length ? 0 : index;
// select another parent
if (parents.indexOf(index) >= 0) {
continue; // skip already selected parent
}
if (Math.random() < CROSSOVER_PROBABILITY) {
parents.push(index);
break;
}
}
// crossover parents and extend population by new children
for (var i = 0; i < parents.length; i+=2) {
// crossover parents
var crossingPoint = getRandomInt(1, CHROMOSOME_SIZE - 2);// from 1 to make crossover up to one less than last one
var chromosomeA = cloneChromosome(population[parents[i]]);
var chromosomeB = cloneChromosome(population[parents[i+1]]);
var a1 = chromosomeA.genes.slice(0, crossingPoint);
var a2 = chromosomeA.genes.slice(crossingPoint);
var b1 = chromosomeB.genes.slice(0, crossingPoint);
var b2 = chromosomeB.genes.slice(crossingPoint);
chromosomeA.genes = a1.concat(b2);
chromosomeB.genes = b1.concat(a2);
// clear old information about position and eval in chromosomes
chromosomeA.x = undefined;
chromosomeA.y = undefined;
chromosomeA.eval = undefined;
chromosomeB.x = undefined;
chromosomeB.y = undefined;
chromosomeB.eval = undefined;
population.push(chromosomeA);
population.push(chromosomeB);
}
}Uniform Mutation
The simplest mutation version I know, which randomly introduces some mutated genes into new chromosomes generated during breeding. We choose or not chromosome, and then we select which gene to mutate.
/**
* Randomly introduce mutated genes into new chromosomes.
* Mutation is done only for new child chromosomes, that are beyond
* original population size.
*/
function mutation() {
// mutate only children
for (var i = POPULATION_SIZE - 1; i < population.length; i++) {
var shouldMutate = Math.random() < MUTATION_PROBABILITY;
if (shouldMutate) {
// choose gene to mutate
var geneIndex = getRandomInt(0, CHROMOSOME_SIZE - 1);
population[i].genes[geneIndex] = getRandomInt(0, 1); // random value 0 or 1 - mutation
}
}
}Evaluation function (objective)
Evaluation is penultimate step in GA, which ensures that every chromosome in population has calculated fitness. We simply iterate over population to execute \(f(x,y)\) function for each chromosome, like below.
/**
* Calculate each chromosome fitness.
*/
function evaluation() {
for (var i = 0; i < population.length; i++) {
fxy(population[i]);
}
}I used great freeware JavaScript library math.js to evaluate function expression from string representation. The evaluation function \(f(x,y)\) is defined as below.
/**
* Evaluates value of the objective function, sets the chromosome position x,y and eval.
* @param chromosome The chromosome representing solution.
*/
function fxy(chromosome) {
var variables = decodeBinaryChromosome(chromosome.genes, 2, ranges);
// calculate real x,y coordinates
var x = variables[0];
var y = variables[1];
chromosome.x = x;
chromosome.y = y;
// here we can implement penalty function when the chromosome is outside the ranges or violates constraints
if (x < space.x1 || x > space.xn || y < space.y1 || y > space.yn) {
// make this chromosome very bad one according to target optimization
chromosome.eval = MAXIMIZATION ? Number.MIN_VALUE : Number.MAX_VALUE;
return chromosome;
}
chromosome.eval = math.evaluate(EVAL_FN, {
x: x, y: y
});
return chromosome;
}Very important part of this function is a “penalty” applied to the result. If the solution position is located outside the available search space, we make the chromosome a “very bad looking one”, I mean with very low evaluation value, we set it to Number.MIN_VALUE – minimal available JavaScript number. This finally will eliminate such chromosome from population, so no invalid individuals in population. We call this behavior a penalty function.
// here we can implement penalty function when the chromosome is outside the
// ranges or violates constraints
if (x < space.x1 || x > space.xn || y < space.y1 || y > space.yn) {
// make this chromosome very bad one according to target optimization
chromosome.eval = MAXIMIZATION ? Number.MIN_VALUE : Number.MAX_VALUE;
return chromosome;
}Selection operator
Below you can see the implementation of selection operator. Selection is executed also at the end to finally sort and trim the population after the main loop will end.
/**
* Selects a number of the best individuals from population and removes the rest,
* the population is decreased by the worst chromosomes.
* @param trim Trim the population to SELECTION_COUNT.
*/
function selection(trim) {
// sort population
population.sort(function (chromosomeA, chromosomeB) {
// search for maximum, so we sort bigger values (evaluations) at the beginning as the
// best chromosomes
return MAXIMIZATION
// result < 0 will sort A before B (B < A => result < 0)
// result > 0 will sort B before A (A < B => result > 0)
// result = 0 will leave the order
? chromosomeB.eval - chromosomeA.eval
// result < 0 will sort B before A (A < B => result < 0)
// result > 0 will sort A before B (B < A => result > 0)
// result = 0 will leave the order
: chromosomeA.eval - chromosomeB.eval;
});
// select only the best chromosomes, remove the rest from population
population = population.slice(0, SELECTION_COUNT);
}Summary
And… that’s it. It looks like the code grown more than I was expecting. I hope it is clear for everyone. If you have questions, ask me in comments.
Thank you for reading.
I love the example above. Really interesting description and very good example. Can I use it in my school project?
Yes of course, no problem. Use it wherever you need 🙂