Genetic Algorithm

GeneticAlgorithm

var GeneticAlgorithm = function () {};

GeneticAlgorithm.prototype.generate = function(length) {
	var s = '';
	while (length--) {
		s += ~~(Math.random()+0.5);
	}
	return s;
};

GeneticAlgorithm.prototype.select = function(population, fitnesses) {
	var total = fitnesses.reduce(function(s,v){return s+v;}, 0);
	var R = Math.random() * total;
	var fc = 0;
	var i = 0, len = population.length;
	var c1;
	for (; i < len; i++) {
		fc += fitnesses[i];
		if (fc > R) {
			c1 = population[i];
			break;
		}
	}
	return c1 || population[len-1];
};

GeneticAlgorithm.prototype.mutate = function(chromosome, p) {
	var c = '';
	for (var i = 0, len = chromosome.length; i < len; i++) {
		c += Math.random() < p? + 1 ^ chromosome[i] : chromosome[i];
	}
	return c;
};

GeneticAlgorithm.prototype.crossover = function(chromosome1, chromosome2) {
	var r = ~~(Math.random() * chromosome1.length);
	return ['' + chromosome1.substr(0,r) + chromosome2.substr(r),
	'' + chromosome2.substr(0,r) + chromosome1.substr(r)];
};

GeneticAlgorithm.prototype.run = function(fitness, length, p_c, p_m, iterations) {
	var population = [];
	var newPopulation = [];
	var generate = this.generate;
	var select = this.select;
	var crossover = this.crossover;
	var mutate = this.mutate;
	var sel;
	var fitnesses = [];
	var i = 0,j = 0;
	var s = 150;
	iterations = iterations || 100;

	while (i < iterations) {
		population.push( generate(length) );
		i++;
	}

	while (i--) {
		fitnesses = population.map(fitness);
		newPopulation = [];
		while (j++ < s) {
			sel = [select(population, fitnesses), select(population, fitnesses)];

			if (Math.random() < p_c) sel = crossover(sel[0], sel[1]);
			newPopulation.push(mutate(sel[0], p_m));
			newPopulation.push(mutate(sel[1], p_m));
		}
		population = newPopulation;
		j = 0;
	}

	fitnesses = [];
	for (i = population.length - 1; i >= 0; i--) {
		fitnesses.push(fitness(population[i]));
	}
	i = fitnesses.indexOf( Math.max.apply(null,fitnesses) );
	return population[i];
};