Programación genética explicada: Cómo las máquinas aprenden a escribir su propio código

Quizás el "Santo Grial" de la informática se haya descubierto el día en que nuestras máquinas puedan escribir sus propios programas. La programación genética (PG) es un paradigma de aprendizaje automático relativamente nuevo que representa un paso en esa dirección.

La PG tiene una gran promesa en el ámbito de la ingeniería de control. En este artículo, discutiremos qué es la programación genética, cómo puede representarse y veremos un programa de ejemplo.

Este artículo es el primero de una serie. Para saltar a las siguientes entradas, seleccione una a continuación:

• Operadores genéticos en algoritmos evolutivos
• Ejemplos de algoritmos genéticos: Evolución de un programa de ordenación y regresión simbólica
• Aplicaciones y limitaciones de la programación genética

Programación genética y algoritmos genéticos

La PG es esencialmente una variación del algoritmo genético (AG) originalmente concebido por John Holland. Al igual que un AG, la PG es un algoritmo evolutivo que se basa en operadores genéticos como reproducción proporcional a la aptitud, cruce y mutación para impulsar una población de programas codificados, o "individuos", a través de generaciones sucesivas hacia una solución.

Sin embargo, a diferencia de un AG, que típicamente usa una codificación de cadena de bits de longitud fija, la PG emplea una representación basada en árboles de tamaño variable de un programa real. Por lo tanto, el resultado de una ejecución exitosa de PG produce un programa de computadora que, cuando se le da la entrada apropiada y se ejecuta, produce el resultado deseado.

Nichael Cramer y John Koza son acreditados por sentar las bases de la PG. John Koza (quien también posee una patente sobre PG) ha realizado una cantidad significativa de investigación sobre PG y su libro emblemático, "Genetic Programming", es considerado la obra seminal sobre el tema. La investigación actual ha demostrado algunos éxitos alentadores de PG en una amplia gama de aplicaciones, incluyendo navegación de robots, adquisición de estrategias de juego, análisis de regresión simbólica y sistemas de control.

Representación de la programación genética

La representación basada en árboles mencionada anteriormente es central para el tema de la PG, ya que prácticamente cualquier programa de computadora puede representarse de esta manera. En la práctica, un lenguaje funcional como LISP se adapta bien a esta forma y es fácil ver cómo una S-expresión de LISP puede diagramarse como un árbol (Figura 1).

A continuación, encontrará tres representaciones separadas de la misma información:

Un fragmento de programa simple:
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;

END


Equivalente en LISP:
 (progn (if (a < b)
 (setq a (+ a 1))
 (setq b (* b b))
 )
 (setq c (* (* a b) 2))
)

Figura 1. Representación en árbol de un programa. Nota que (progn arg1 arg2 arg3 ... argn) evalúa secuencialmente cada argumento.

Los nodos interiores del árbol consisten en funciones, mientras que los nodos hoja consisten en terminales. Las funciones deben tener un recuento de argumentos (comúnmente referido como aridad) de al menos uno, permitiéndoles conectarse a otras funciones o terminales, proporcionando así el "pegamento" para las ramas dentro del árbol.

Los terminales típicamente incluyen cosas como constantes y variables. Dado que los terminales forman las hojas del árbol, siempre tienen una aridad de cero. Se le requiere elegir el conjunto de funciones y terminales para el problema que está intentando resolver. Por ejemplo, las funciones lógicas AND, OR y NOT y los terminales X1 y X2, que representan dos variables de entrada booleanas, son apropiados si está intentando descubrir un programa capaz de sintetizar la función booleana XOR. También se requiere una función de aptitud, ya que debe proporcionar los medios para que un programa sea medido contra otro en el sentido de que uno es mejor para resolver un problema dado.

Por ejemplo, en el caso XOR, podemos probar la aptitud de un programa ejecutando el programa una vez para cada caso de aptitud correspondiente a las cuatro posibles entradas booleanas para X1 y X2 (0 0, 0 1, 1 0, 1 1) y sumando el número de respuestas correctas (0, 1, 1, 0) respectivamente, para cada caso de prueba.

Obviamente, un programa que produce una puntuación perfecta de cuatro se considera una solución al problema XOR, como se muestra en el Listado 1.

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

Listado 1. Resultado XOR

Siguiente: Operadores genéticos

En el próximo artículo, echaremos un vistazo a los operadores genéticos que hacen posibles los algoritmos evolutivos. También los usaremos en un algoritmo de ejemplo más complejo.

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.