www.rdiaz.es

La programación de Darwin

Hace un rato pensando en un tema para la entrada de hoy, me acordé de los algoritmos evolutivos, también conocidos como algoritmos genéticos. Los algoritmos genéticos se suelen utilizar para llevar a cabo procesos de optimización y minimización en numerosas aplicaciones como diseño de piezas, análisis de sistemas de distribución de energía electrica y de agua y en general en todos aquellos procesos en los que sea necesaria una optimización de una o varias variables.

La clave del algoritmo genético se centra en replicar los procesos evolutivos de las especies animales dentro del algoritmo. Para facilitar un poco más la comprensión de los algoritmos genéticos voy a plantear un problema que tuve que resolver el año pasado en un curso de doctorado sobre algoritmos evolutivos. El problema era el siguiente: Dada la función seno(X) encontrar todos los mínimos de la función en el entorno [-1,1]. Para la resolución de este problema tuve que actuar de la siguiente forma:

• Creación de la población inicial: La población inicial estaba compuesta por valores aleatorios en el intervalo [-1,1], lo importante en este paso es crear una población lo más aleatoria posible para evitar en las siguientes fases que se produzcan estancamientos de la población.
• Evaluación de la población: En este paso se aplica a cada uno de los individuos de la población la función sen(x), obteniendo de este modo los primeros resultados del problema.
• Ordenación de la población: Una vez evaluada toda la población se procede a ordenar a los individuos por la calidad (es decir ordenarlos de menor a mayo en el problema propuesto).
• Cruce: A los mejores elementos de la población se les aplica una función que representa a la reproducción, creando un nuevo individuo de mejores características que sus progenitores.
• Mutación: Aleatoriamente se provocan variaciones en individuos de la población para evitar que la población se estanque alrededor de un único mínimo y forzar así la busqueda en nuevos entornos.
• Reemplazo: Con toda la población existente, se desechan a los peores individuos y se define una nueva generación de individuos, volviendo de nuevo a llevar a cabo el proceso de evaluación de la población.

Los reusltados obtenidos con este tipo de algoritmos en problemas muy concretos son sorprendentes porque en relativamente pocas iteraciones de programa se obtienen unos resultados muy buenos. En el caso del problema del seno, al cabo de unas 100 iteraciones se obtenían resultados exactos con 3 decimales de precisión.

Para más información en este blog hay un artículo interesantísimo sobre algoritmo genético