Cursos de Verano de El Escorial:
Encuentro sobre Computación Natural

Teoría de la Computación Evolutiva: Carlos Cotta

Uno de los aspectos más frecuentemente criticados de los Algoritmos Evolutivos (AEs) es su falta de sustentación teórica. Siendo éste uno de los puntos más débiles de estas técnicas, no es cierto sin embargo que adolezcan completamente de tal base. De hecho, existen potentes herramientas que modelan y permiten analizar el funcionamiento de los AEs, proporcionando una inestimable ayuda al diseño de AEs efectivos para el problema de interés. El objetivo de esta ponencia es mostrar una panorámica general de las bases teóricas de los AEs, introduciendo de manera simple las herramientas que a tal fin se utilizan. La discusión se centrará en la variante de los AEs conocida como Algoritmos Genéticos (AGs) o más generalmente Programas de Evolución (PEs), si bien algunos de los conceptos presentados son fácilmente trasladables a otras variantes de AEs.

El primer aspecto que se tratará será la convergencia asintótica del algoritmo. Para ello se empleará un enfoque basado en cadenas de Markov, el cual mostrará que la convergencia global hacia la solución óptima está garantizada siempre que se empleen estrategias de reemplazo elitista (i.e., que el mejor individuo de la población no sea nunca reemplazado) y operadores reproductivos cuya expansión dinástica (conjunto de soluciones obtenibles mediante aplicación sucesiva de los mismos) abarque todo el espacio de búsqueda.

A continuación se abordará la justificación teórica tradicional del funcionamiento de los AEs, y en base a la cual la anteriormente mencionada convergencia asintótica se considera alcanzable de manera eficiente. Dicha justificación es el denominado ``Teorema de los Esquemas'', y de él emana la noción de superioridad global de los AEs sobre el resto de técnicas de búsqueda. A pesar de la popularidad que esta justificación alcanzó, su base matemática es defectuosa como brevemente se verá. Más aún, se mostrará un resultado formal (el denominado ``Teorema de No Free Lunch'' -NFL-) que contradice explícitamente esta noción de superioridad global.

Entre las diversas implicaciones del Teorema NFL está el hecho de que (a) un único algoritmo no puede ser la herramienta perfecta de optimización, y (b) las pruebas experimentales no proporcionarán en general información extrapolable a otros dominios de problemas. A raíz de lo primero, es necesario adaptar el AE al problema de interés, usando representaciones del problema y operadores reproductivos no estándar. En esta línea, el marco de trabajo conocido como Análisis de Formas provee un conjunto de herramientas que -en conjunción con un análisis estadístico- permiten diseñar AEs efectivos. Precisamente en relación con este análisis estadístico, y entroncando con el aspecto (b) mencionado anteriormente, hay que reseñar que el Teorema NFL no proscribe la realización de experimentos como vía para obtener comprensión sobre el comportamiento de un AE, sino que limita la validez de la información obtenida a través de dichos experimentos a los problemas estudiados. Por ello, el uso de modelos empíricos del funcionamiento de los AEs sigue siendo una herramienta útil para predecir el resultado que una cierta modificación de parámetros del AE producirá en un cierto contexto. Dichos modelos empíricos se basan frecuentemente en el estudio de las distribuciones de fitness de los operadores reproductivos, y su uso será descrito y ejemplificado.

Página principal del curso