Aplicaciones y limitaciones de algoritmos genéticos

En este punto de la serie de programación genética (GP), 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 clasificación mediante regresión simbólica.

Aquí, analizaremos de alto nivel 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 de XOR que discutimos en la primera parte de esta serie:

  Una solución perfecta al problema de XOR descubierto por GP: (programa defun () (Y (O X1 X2) (NO (Y X1 X2)) ) ) 

Listado 1. Resultado XOR.

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

 Una aproximación polinomial a sin (x) en el intervalo (0 <=x <=pi / 2) (programa defun () (+ (* (* (* X X) X) (* 0,2283 -0,6535)) X) ) Simplificar el programa anterior produce la siguiente ecuación equivalente:polisina (x) =-.1492 x 
 3 
 + x Resultados:

Listado 4. Regresión simbólica.

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

Esta característica no tiene por qué ser una restricción, ya que ciertamente es posible que una función o terminal tenga un efecto secundario cuando se ejecuta. Este suele ser el caso del programa de clasificació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 se presenten efectos secundarios. Algunos ejemplos adicionales de efectos secundarios útiles son asignar una variable a otra o cambiar la dirección en 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. Las construcciones iterativas también son posibles, ya que una función puede evaluar uno de sus argumentos varias veces. Sin embargo, se introduce una complejidad adicional por la necesidad de limitar el número de iteraciones y el nivel de anidamiento para evitar una situación en la que la evaluación de un individuo puede 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 GP tienden a ser programas similares a LISP, no es necesario implementar un sistema GP en LISP. Muchos sistemas se implementan en C o C ++. Se puede emplear una representación lineal del árbol del programa y se puede evitar la sobrecarga de la 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 a la gran cantidad de veces que se invoca durante cada generación. Se puede encontrar un excelente artículo que analiza varias técnicas de implementación en Advances in Genetic Programming (citado en la sección de lecturas sugeridas a continuación).

Al igual que en otros paradigmas de aprendizaje automático, como las redes neuronales, existe la posibilidad de sobreajustar los datos de entrenamiento (casos de prueba de GP). El sobreajuste puede ocurrir cuando la solución "memoriza" efectivamente los datos, proporcionando así poco más que una elaborada tabla de búsqueda. Una forma sencilla de ayudar a reducir 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 adecuación. La idea es recompensar las soluciones más pequeñas, presumiblemente más generales. Además, se le anima a utilizar técnicas apropiadas de diseño experimental. Por ejemplo, si está intentando desarrollar un modelo de 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 es el caso de los algoritmos evolutivos, GP no ofrece ninguna garantía de encontrar una solución exacta o incluso una solución aceptable. Los resultados pueden variar mucho de una ejecución a otra. A menudo, el proceso converge prematuramente en mínimos locales. 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 para programación genética

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

• Diseño de circuito
• Optimización combinatoria
• Sistemas de control
• Ajuste de curvas / análisis de regresión
• Compresión de datos
• Previsión económica / modelos financieros
• Adquisición de estrategias de juego
• Inducción de secuencia matemática
• Diseño de redes neuronales
• Reconocimiento y clasificación de patrones
• Generación de números aleatorios
• Navegación del robot
• Integración y diferenciación simbólicas
• Diseño tridimensional

Orientaciones futuras para la programación genética

Dependiendo de la complejidad del problema, es posible que se requieran varias ejecuciones de GP para encontrar una solución aceptable, si es que se puede encontrar alguna. Idealmente, nos gustaría que GP "escale" a medida que aumenta la complejidad del problema. Encontrar buenas formas de lograr este objetivo es un área activa de investigación. Como 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 Programación genética II , Koza analiza los métodos que pueden descubrir subrutinas reutilizables y presenta resultados que respaldan la capacidad de los programas modulares jerárquicos para resolver problemas más complejos.

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

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

Lectura sugerida

• Kinnear, Jr., K. E. (ed.). Avances en la programación genética . Cambridge, Mass .:The MIT Press, 1994.
• Knuth, D. E. El arte de la programación informática, volumen 3, clasificación y búsqueda . Reading, Mass .:Addison-Wesley, 1973
• Koza, J. R. Programación genética . Cambridge, Mass .:The MIT Press, 1992.
• Koza, J. R. Programación genética II . Cambridge, Mass .:The MIT Press, 1994.
• Montana, D. J. "Programación genética fuertemente tipificada". Informe técnico de BBN # 7866, mayo de 1993.
• Mitchell, Melanie, Introducción a los algoritmos genéticos , The MIT Press, 1998.