Explorando el poder y los límites de los algoritmos genéticos

En este punto de la serie de programación genética (PG), hemos aprendido qué es la programación genética y cómo representa la información, cómo funcionan los operadores genéticos en los algoritmos evolutivos, y hemos trabajado en la evolución de un programa de ordenación mediante regresión simbólica.

Aquí, echaremos un vistazo de alto nivel a lo que esta tecnología puede lograr a medida que se desarrolla.

Consideraciones prácticas de la programación genética

Para entender este capítulo final de nuestra serie, recordemos un ejemplo XOR que discutimos en la primera parte de esta serie:

Una solución perfecta al problema XOR descubierta por PG:
(defun program ()
  (AND (OR X1 X2)
  (NOT (AND X1 X2) )
  )
)

Listado 1. Resultado XOR.

Veamos también el ejemplo de regresión simbólica del artículo anterior:

Aproximación polinómica a sen(x) en el intervalo (0 <= x <= pi/2)

(defun program ()
  (+ (* (* (* X X) X)
  (* 0.2283 -0.6535))
  X)
)

Simplificando el programa anterior se obtiene la siguiente ecuación equivalente:

polysen(x) = -.1492 x3 + x

Resultados:

Listado 4. Regresión simbólica.

Observe que tanto el ejemplo XOR como el de regresión simbólica presentados aquí devuelven un único valor cuando se evalúan.

Esta característica no necesita ser una restricción, ya que ciertamente es posible que una función o terminal tenga un efecto secundario cuando se ejecuta. Este es a menudo el caso del programa de ordenación, que contiene una función con el efecto secundario potencial de intercambiar un par de elementos en un vector. En la práctica, es común que existan efectos secundarios. Algunos ejemplos adicionales de efectos secundarios útiles son asignar una variable a otra o cambiar la dirección hacia la que mira un robot.

Nuestro conjunto de funciones puede incluir funciones condicionales que proporcionan a los programas evolucionados la capacidad de tomar decisiones. Las funciones condicionales evalúan selectivamente sus argumentos. Como ejemplo, considere una función, con una aridad de tres, como (si arg1 arg2 arg3). La función se evalúa evaluando el primer argumento y si el resultado es verdadero, se evalúa el segundo argumento; de lo contrario, se evalúa el tercer argumento. Los constructos iterativos también son posibles, ya que una función puede evaluar uno de sus argumentos múltiples veces. Se introduce complejidad adicional, sin embargo, por la necesidad de limitar el número de iteraciones y el nivel de anidamiento para evitar una situación donde la evaluación de un individuo pueda llevar un tiempo excesivamente largo. Se ha realizado algún trabajo para permitir formulaciones recursivas, aunque el éxito en esta área ha sido algo limitado.

Aunque los resultados de los sistemas de PG tienden a ser programas similares a LISP, un sistema de PG no necesita implementarse en LISP. Muchos sistemas se implementan en C o C++. Se puede emplear una representación linealizada del árbol del programa y se puede evitar la sobrecarga de memoria dinámica junto con la costosa recolección de basura. La eficiencia de la función de aptitud merece una atención especial, ya que a menudo es un cuello de botella debido al gran número de veces que se invoca durante cada generación. Un excelente artículo que discute varias técnicas de implementación se puede encontrar en Advances in Genetic Programming (citado en la sección de Lecturas sugeridas a continuación).

Como en otros paradigmas de aprendizaje automático, como las redes neuronales, existe el potencial de sobreajustar los datos de entrenamiento (casos de prueba de PG). El sobreajuste puede ocurrir cuando la solución "memoriza" efectivamente los datos, proporcionando poco más que una tabla de búsqueda elaborada. Una forma simple de ayudar a limitar este efecto es mediante el uso de un factor de parsimonia. Un factor de parsimonia es típicamente una pequeña fracción multiplicada por el número de nodos dentro del árbol del programa, cuyo resultado se incorpora a la función de aptitud. La idea es recompensar soluciones más pequeñas, presumiblemente más generales. Además, se recomienda utilizar técnicas de diseño experimental apropiadas. Por ejemplo, si está intentando desarrollar un modelo para predicción, es una buena idea restringir la evaluación de aptitud a un subconjunto de los datos disponibles. De esta manera, los datos restantes pueden medir el rendimiento predictivo del modelo resultante.

Como ocurre con los algoritmos evolutivos, la PG no garantiza encontrar una solución exacta ni siquiera una solución aceptable. Los resultados pueden variar mucho de una ejecución a otra. A menudo, el proceso converge prematuramente en un mínimo local. El rendimiento depende en gran medida de la complejidad del problema, su representación caracterizada por la elección de funciones y terminales, y las propiedades de la función de aptitud.

Aplicaciones de la programación genética

La programación genética se ha aplicado con éxito a problemas que ocurren en áreas como:

• Diseño de circuitos
• Optimización combinatoria
• Sistemas de control
• Ajuste de curvas/análisis de regresión
• Compresión de datos
• Predicción económica/modelado financiero
• Adquisición de estrategias de juego
• Inducción de secuencias matemáticas
• Diseño de redes neuronales
• Reconocimiento y clasificación de patrones
• Generación de números aleatorios
• Navegación de robots
• Integración y diferenciación simbólica
• Diseño tridimensional

Direcciones futuras para la programación genética

Dependiendo de la complejidad del problema, pueden requerirse varias ejecuciones de PG para encontrar una solución aceptable, si es que se puede encontrar una. Idealmente, nos gustaría que la PG "escalara" a medida que aumenta la complejidad del problema. Encontrar buenas formas de lograr este objetivo es un área activa de investigación. Al igual que en la programación convencional, la noción de construir representaciones de nivel superior a través de subrutinas es una forma de abordar este problema. En Genetic Programming II, Koza discute métodos que pueden descubrir subrutinas reutilizables y presenta resultados que apoyan la capacidad de programas modulares jerárquicos para resolver problemas más complejos.

Como hemos visto, la PG combina las características autoorganizadas del algoritmo genético con el poder de representación y generalidad de las S-expresiones. La elegancia de este enfoque simplifica la especificación del problema a la de proporcionar una función de aptitud específica del dominio y un conjunto apropiado de funciones y terminales. Aplicable a una amplia gama de problemas, la PG continúa siendo un terreno fértil para la investigación.

Aún en su infancia, futuros avances pueden llevarnos un paso más allá hacia el Santo Grial de sistemas capaces de escribir sus propios programas.

Lecturas sugeridas

• Kinnear, Jr., K. E. (ed.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass.: Addison-Wesley, 1973
• Koza, J. R. Genetic Programming. Cambridge, Mass.: The MIT Press, 1992.
• Koza, J. R. Genetic Programming II. Cambridge, Mass.: The MIT Press, 1994.
• Montana, D. J. "Strongly Typed Genetic Programming." BBN Technical Report #7866, May 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.