JavaScript Genetic Algorithm

A small example 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: