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.