Primer acercamiento a los Algoritmos Genéticos
Fecha: May 31st, 2010 | Categoría: Informatica | 1 Comment »El año pasado, el Dr. Pablo Coll me mostró la página de competencias de programación de Al Zimmermann. Se trata de problemas que son muy difíciles computacionalmente, y ganan los que aproximen las mejores soluciones. Un problema del que ya terminó el período para mandar soluciones es uno de Point Packaging: ubicar N puntos en coordenadas enteras de manera tal que no se repitan las distancias; y minimizar el área de la circunferencia que los contiene.
Para resolverlo, implementé un algoritmo genético. Un algoritmo genético lo que hace es tomar individuos en un grupo llamado generación y elegir los individuos de cada generación más aptos mediante una función de "aptitud" (fitness), para concebir quiénes serán los individuos de una nueva generación. Este proceso se repite hasta que se tiene una generación donde los individuos son más o menos los mismos.
Mis individuos eran colecciones de puntos, y su aptitud era evaluada de acuerdo al radio de la circunferencia que los contiene y a la cantidad de repeticiones de distancias entre puntos. Las repeticiones de distancias pesaba mucho, con esto podía tener individuos incorrectos pero con mucha aptitud, con colisiones de distancias que se irían solucionando a medida que prosigue el algoritmo.
Este es un video en youtube que armé con gráficas de los individuos más aptos de cada generación:
Al final, me fijé en la página del concurso y mi solución era pésima (el radio era el doble de la mejor solución entregada). Y además, me di cuenta que después de unos cuántos cientos de generaciones, todos los individuos eran casi iguales excepto por los que habían mutado en la última generación. Declaré mi aplicación de algoritmos genéticos a este problema como un fracaso, pero estuvo bueno el intento y tener cosas para plotear (me estoy volviendo cada vez más fanático de los plots).
