Introducción a la programación genética:¿un sistema que se programa a sí mismo?

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 (GP) es un paradigma de aprendizaje automático relativamente nuevo que representa un paso en esa dirección.

GP es muy prometedor en el ámbito de la ingeniería de control. En este artículo, discutiremos qué es la programación genética, cómo se puede representar y veremos un programa de ejemplo.

Este artículo es el primero de una serie. Para pasar a las siguientes entradas, seleccione una de las siguientes:

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

Programación genética y algoritmos genéticos

GP es esencialmente una variación del algoritmo genético (GA) originalmente concebido por John Holland. Al igual que un GA, GP es un algoritmo evolutivo que se basa en operadores genéticos, como la reproducción proporcional de la aptitud, el cruce y la 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 GA, que normalmente utiliza una codificación de cadena de bits de longitud fija, GP emplea una representación basada en árbol de tamaño variable de un programa real. Por lo tanto, el resultado de una ejecución exitosa de GP produce un programa de computadora que, cuando se le da la entrada apropiada y se ejecuta, produce el resultado deseado.

A Nichael Cramer y John Koza se les atribuye el mérito de sentar las bases de GP. John Koza (que también tiene una patente de GP) ha realizado una cantidad significativa de investigación sobre GP y su libro histórico, "Programación genética", se considera el trabajo fundamental sobre el tema. La investigación actual ha demostrado algunos éxitos alentadores de GP en una amplia gama de aplicaciones, incluida la navegación de robots, la adquisición de estrategias de juegos, el análisis de regresión simbólica y los sistemas de control.

Representación de programación genética

La representación basada en árboles mencionada anteriormente es fundamental para el tema GP, 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 expresión S de LISP se puede diagramar como un árbol (Figura 1).

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

  Un fragmento de programa simple: COMENZAR SI a  Equivalente a LISP: (progn (si (a  

 
 

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

 
 

 Los nodos interiores del árbol constan de funciones, mientras que los nodos hoja constan de terminales. Las funciones deben tener un recuento de argumentos (comúnmente conocido como arity) de al menos uno, lo que les permite conectarse a otras funciones o terminales, proporcionando así el "pegamento" para las ramas dentro del árbol. 
 

 Los terminales suelen incluir elementos tales como constantes y variables. Dado que los terminales forman las hojas del árbol, siempre tienen una aridad de cero. Debe elegir el conjunto de funciones y terminales para el problema que está intentando resolver. Por ejemplo, las funciones lógicas Y, O y NO y las terminales X1 y X2, que representan dos variables de entrada booleanas, son apropiadas 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 se compare con otro en el sentido de que uno sea mejor para resolver un problema determinado. 
 

 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 arroja 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 de XOR descubierto por GP: (programa defun () (Y (O X1 X2) (NO (Y X1 X2)) ) ) 
 
   Listado 1.  Resultado XOR  
 

 
 
 Siguiente:Operadores genéticos 
 

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

 
 
 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. 
 
 

            


            

               Evaluación de las palabras de moda:transformación digital        
                Cómo diseñar un controlador de lógica difusa