Algoritmos genéticos – demo versión 2

Debo decir dos cosas acerca de los algoritmos genéticos. Primero ¡están buenísimos!, una vez que te metés en tema resulta totalmente atrapante. Segundo: en la diversidad está la solución.

El video muestra una actualización de la demo. Esta actualización tiene cinco diferentes algoritmos de cruce (para crear descendencia) y cinco diferentes algoritmos de mutación. La aplicación permite seleccionar con cuales y cuantos algoritmos se quiere trabajar.

Los resultados son bastante elocuentes: cuanto más algoritmos utilizo, menor población inicial (y por consiguiente menor tiempo) necesitamos para resolver el problema. Cuanto más diversidad, más probabilidad de encontrar mejores soluciones.

En la primer demo, para 20 ciudades necesitábamos una población inicial de 1000 individuos y ahora (utilizando los 10 algoritmos juntos) con sólo 250 llegamos al mismo resultado y en forma mucho más veloz.

Ahora empezó la etapa de optimización y “emprolijamiento” de código, agregar algunas validaciones para los campos y demás.

¡Si se les ocurre alguna problemática para resolver con algoritmos genéticos avisen!

Algoritmos Genéticos – Mi primer demo

Finalmente puedo mostrar avances en mi aprendizaje de Algoritmos Genéticos. Luego de varias semanas de lectura y algunas pruebas me puse a construir mi primera aplicación.

Problema del Viajante

La aplicación busca una solución al problema del viajante. Elegí este problema porque es el más conocido para explicar algoritmos genéticos y además porque tiene características impactantes.

Tiene un enunciado muy simple: un viajante debe recorrer una cantidad dada de ciudades, ¿cuál es la ruta que pasa por todas las ciudades y que recorre la menor distancia?

Tienen una solución muy complicada: deberíamos calcular todas las rutas posibles y seleccionar la más corta. El problema es que para sólo 12 ciudades existen 479.001.600 rutas posibles. Si una computadora pudiera calcular la distancia de una ruta en un microsegundo (millonésima parte de un segundo) tardaría 3 segundos en resolver el problema para 10 ciudades, más de medio minuto para 11 y 777.146 años para 20 ciudades (fuente Wikipedia).

Mi implementación con Algoritmos Genéticos

Para crear descendencia, la aplicación elige un operador de cruce al azar. Hasta ahora sólo incluí tres: PMX (Correspondencia Parcial, Goldberg y Lingle, 1985), CX (Cruce basado en ciclos, Oliver y col., 1987) y OX1 (Cruce basado en orden, Davis, 1985).

Y sólo implementé un algoritmo de mutación: DM (basado en desplazamiento, Michalewizc, 1997).

Para mi sorpresa, los resultados son muy buenos incluso usando un solo algoritmo de cruce (cualquiera de ellos) y sin mutación.

Sobre la Demo

En la demo dispuse 20 ciudades en círculo (ya que es muy evidente cual es la mejor ruta), una población inicial de 1000 individuos, un máximo de 50 generaciones (aunque la solución la encuentra por la generación 35 aprox.), de cada generación se queda con el 25% “mejor adaptado”, y el 10% de la descendencia incluye alguna mutación.

La aplicación está construída en C# .NET 3.5 y la idea es agregar más algoritmos tanto de cruce como de mutación.