Estuve codificando una librería de algoritmos genéticos, usando C#. El código está en mi proyecto AjCodeKatas en Google Code dentro de:
http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjGa
El proyecto principal es AjGa (con AjGa.Tests para testing):
Las principales interfaces son:
Uso generics, con dos tipos genéricos: G, que es el tipo de implementación de un gen, y V como el tipo al que se evalúa un genoma (por ejemplo, int, double). Con ese valor se catalogan los genomas.
IPopulation es una colección de genomas.
IGenome es una colección de genes, que es evaluado a un valor de tipo V.
IEvaluator está a cargo de evaluar un genoma.
La implementación de IEvolution ejecuta generaciones sobre una población, que va cambiando, usando mutadores, operadores de cruzamiento, para irla modificando después de cada ejecución.
Hay interfaces para generar un genoma, mutar uno existente o hacer cruzamiento de dos genomas.
Para probar estas ideas, implementé un proyecto con gen, genoma, y operadores, que ataca el clásico problema del Travelling Salesman Problem, el vendedor que tiene que visitar una serie de ciudades, minimazando la distancia a recorrrer:
En este ejemplo, el evaluador tiene una lista de posiciones de ciudades a visitar:
public class Evaluator : IEvaluator<int, int>
{
private List<Position> positions;
public Evaluator(List<Position> positions)
{
this.positions = positions;
}
El tipo de gen acá es int, y cada valor de genoma se expresa como un int. El genoma mantiene una lista de enteros, que representan el número ordinal de las ciudades a visitar:
using AjGa;
public class Genome : BaseGenome<int, int>
{
public Genome(int size)
{
for (int k = 0; k < size; k++)
{
AddGene(k);
}
}
Esto es, cada gen es un int, y un genoma con genes 2, 0, 1, representa un viaje que visita la tercera ciudad, pasa por la primera, y termina en la segunda.
Podemos ejecutar el proyecto WinForm, para probar esta implementación:
En la ejecución de arriba, la distribución de ciudades es al azar. Las ciudades pueden ser distribuidas en una grilla:
De esta forma, podemos probar la eficiencia del algoritmo para encontrar un solución óptima, que en el caso de disponer las ciudades en grilla, se conoce de antemano.
Si queremos implementar un nuevo proyecto GA, tenemos que:
- Definir el tipo que tendrán los genes
- Definir el tipo valor a usar
- Escribir operadores (creadores, mutadores, cruzadores) de genomas
Los tests que tengo están en verde:
Buen Code coverage:
En 4 horas tuve la primera versión, gasté 3 horas explorando TSP, y cerca de 8 horas preparando y "tuneando" la aplicación WinForm.
Como de costumbre, ¡me divertí escribiendo este ejemplo!
Nos leemos!
Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez