Hace unas semanas, estuve escribiendo:
https://github.com/ajlopez/SimpleGA
un framework simple de soporte de algoritmos genéticos, que implementa población de genotipios, su evaluación, la formación de una nueva población aplicando operadores de mutación (debería agregar operadores de cruzamiento (“crossover”)). Me basé en lo descripto en
A Genetic Algorithm Tutorial (pdf)
Puedo crear una población de genotipos, aportando en cada caso de uso nuevo su función de evaluación y los operadores a usar. La librería entonces evalúa cada individuo de la población, y preparar la nueva generación copiando los mejores individuos/genotipos, y mutando algunos de los mejores, basados en su “fitness”. El valor de “fitness” es v = fi/fa, donde fi es la evaluación individual de un genotipo y fa es el promedio. La parte entera de ese valor determina la cantidad de copias que se hace de un individuo para la nueva generación. La parte fraccionaria se usa como probabilidad de tener una copia mutada para esa nueva generación:
var newpopulation = [];
for (var k = 0; k < l; k++) {
if (values[k] < 0)
continue;
var fitness = values[k] / total;
if (fitness < 0)
continue;
var ntimes = Math.floor(fitness);
var fraction = fitness - ntimes;
for (var j = 0; j < ntimes; j++)
newpopulation.push(population[k]);
if (fraction > 0 && Math.random() <= fraction)
newpopulation.push(population[k]);
}
if (mutators && mutators.length > 0) {
l = newpopulation.length;
var lm = mutators.length;
for (k = 0; k < l; k++) {
var mutator = mutators[Math.floor(Math.random() * lm)];
newpopulation[k] = mutator.mutate(newpopulation[k]);
}
}
Como escribí antes, debería agregar el soporte de operadores de cruzamiento. Tengo un ejemplo simple del Travelling Saleman Problem
https://github.com/ajlopez/SimpleGA/blob/master/samples/tsp/tsp.js
hay una versión en consola https://github.com/ajlopez/SimpleGA/blob/master/samples/tsp/program.js
Y también en una página web:
https://github.com/ajlopez/SimpleGA/blob/master/samples/tsphtml/index.html
Escribí dos versiones más: una cliente/servidor, con página web cliente, pero con cálculo en un servidor Node.js. La otra versión es distribuida: una página web, un servidor que recibe el pedido de cálculo de poblaciones, y lo reparte en los nodos Node.js cliente que se hayan conectado a ese servidor. Esto permite repartir el trabajo en varias máquinas.
Próximos pasos: agregar operadores de cruzamiento, explicar los ejemplos en README.md, y agregar nuevos ejemplos.
Nos leemos!
Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez