AjGa: una librería de algoritmos genéticos
El código está en AjCodeKatas en Google Code :
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; }
using AjGa; public class Genome : BaseGenome<int, int> { public Genome(int size) { for (int k = 0; k < size; k++) { AddGene(k); } }
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:
0 comentarios:
Publicar un comentario