JavaScript Genetic Algorithm

JavaScript Genetic Algorithm

A small page showing off a genetic algorithm implementation in JavaScript. The algorithm takes the JavaScript object from the text box and determine what values should be passed to the fitness function to produce the smallest resulting value.

The included example tries to find the shortest path between a set of points (the travelling salesman problem).

function salesman() {
    this.points = [ [0,0], [10,10], [6,6], [5,6], [3,3], [7,2] ];

this.distance = function(a, b) {
        var x = Math.abs(a[0] - b[0]);
        var y = Math.abs(a[1] - b[1]);
        return Math. sqrt(x * x + y * y);
    };

this.fitness = function(values) {
        var used = [this.points.length];
        var length = 0;
        var previous = values[0];
        var a = this.points[previous];
        used[previous] = 1;
        var b = 0;
        for (var i = 1; i < values.length; ++i) {
            b = this.points[values[i]];
            if (used[values[i]] == 1)
                return 1000;
            length += this.distance(a, b);
            previous = values[i];
            used[previous] = 1;
            a = b;
        }
        return length;
    };
    
    // the size of values that should be passed to fitness
    this.numberOfArgs = function() { return this.points.length; };
    
    // the max value needed for the arguments
    this.maxArg = function() { return this.points.length; };
    
    // convert the current chromosome value which can have a maxValue
    // into something fitness can use.
    this.getArg = function(value, maxValue) {
        return Math.round(value * (this.points.length - 1) / maxValue);
    };

// Paint the solution onto bestimage
    this.paint = function(values) {
        var canvas = document.getElementById('bestimage');
        if (canvas.getContext){
            var w = canvas.width;
            var h = canvas.height;
            var canvasContext = canvas.getContext('2d');
            canvasContext.clearRect(0, 0, w, h);

// draw points
            for (var i = 0; i < this.points.length; ++i){
                var x = this.points[values[i]][0] * 10;
                var y = this.points[values[i]][1] * 10;
                canvasContext.beginPath();
                canvasContext.arc(x, y, 3, 0, Math.PI*2, true);
                canvasContext.fill();
            }
            
            // draw path
            canvasContext.beginPath();
            for (var i = 0; i < this.points.length; ++i){
                var x = this.points[values[i]][0] * 10;
                var y = this.points[values[i]][1] * 10;
                if (i == 0)
                    canvasContext.moveTo(x, y);
                else
                    canvasContext.lineTo(x, y);
            }
            canvasContext.stroke();
        }
    }

}
salesman;

Number of generations: [?]
Number of chromosomes in the population: [?]
Mutation rate: % [?]
Crossover rate: % [?]

Results

Chromosome: Fitness:

If you are using a browser that supports that canvas tag (webkit or gecko engine) you will see below a nice graph of the history of the best values.

And the best value as painted by the fitness function itself:

Useful Links:

License

/*
* Copyright (C) 2007 by Benjamin C Meyer
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*     * Redistributions of source code must retain the above copyright
*       notice, this list of conditions and the following disclaimer.
*     * Redistributions in binary form must reproduce the above copyright
*       notice, this list of conditions and the following disclaimer in the
*       documentation and/or other materials provided with the distribution.
*     * The name of the contributors may not be used to endorse or promote products
*       derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY  ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL  BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/