Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Genetic Algorithm
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];
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment