Programación genética
En la inteligencia artificial, la programación genética (GP, de sus siglas en inglés: Genetic Programming) es una metodología basada en los algoritmos evolutivos e inspirada en la evolución biológica para desarrollar automáticamente programas de computadoras que realicen una tarea definida por el usuario. Es una especialización de los algoritmos genéticos (GA, de sus siglas en inglés: Genetic Algorithms) donde cada individuo es un programa de computadora. Es una técnica de aprendizaje automático utilizada para optimizar una población de programas de acuerdo a una función de ajuste o aptitud (en inglés: fitness function) que evalúa la capacidad de cada programa para llevar a cabo la tarea en cuestión.
En 1954, GP se inició con los algoritmos evolutivos utilizado por primera vez por Nils Aall Barricelli y aplicados a simulaciones evolutivas. En 1960 y principios de 1970, los algoritmos evolutivos fueron reconocidos como métodos de optimización. Ingo Rechenberg y su grupo fueron capaces de resolver problemas complejos de ingeniería a través de estrategias de evolutivas como lo documenta en su tesis PhD en 1971 y el libro resultante de 1973. John Holland fue muy influyente durante la década de 1970.
En 1964, Lawrence J. Fogel, uno de los primeros profesionales de la metodología de GP, aplica los algoritmos evolutivos para el problema de descubrir autómatas de estado finito. Más tarde, el trabajo relacionado con GP surgió la comunidad de los sistemas de clasificación basado en aprendizaje, la cual desarrolló un conjunto de reglas que describen las políticas óptimas para los procesos de decisión de Markov. La primera declaración de la moderna GP "basado en árboles" (es decir, procedimiento con una estructuración basada en árboles y operadores adecuadamente definidos en GA) fue dada por Nichael L. Cramer (1985). Este trabajo fue posteriormente ampliado en gran medida por John R. Koza., un proponente principal de GP que ha sido pionero en la aplicación de GP en la optimización de diversos y complejos problemas de búsqueda. Gianna Giavelli, un estudiante de Koza, luego fue el pionero en el uso de GP como una técnica para modelar la expresión del ADN.
En la década de los 1990's, GP se utilizó principalmente para resolver problemas relativamente simples, ya que es muy costoso computacionalmente. Recientemente, GP ha producido novedosos y excelentes resultados en áreas como la computación cuántica, diseño electrónico, juegos, ordenamiento y búsqueda, debido a las mejoras en la tecnología GP y la crecimiento exponencial de la potencia de la CPU. Estos resultados incluyen la reproducción o el desarrollo de varias invenciones posteriores al año 2000. GP también se ha aplicado a los programas de computadoras, así como hardware evolutivo.
El desarrollo de una teoría de la GP ha sido muy difícil, por lo que en la década de 1990's GP fue considerado una especie de paria entre las técnicas de búsqueda.
GP desarrolla programas informáticos, tradicionalmente representados en la memoria como estructuras de árboles. Los árboles pueden ser fácilmente evaluados de forma recursiva. Cada nodo del árbol tiene una función como operador y cada nodo terminal tiene un operando, por lo que las expresiones matemáticas son fáciles de evolucionar y evaluar. Así, tradicionalmente GP favorece el uso de lenguaje de programación que, naturalmente, introduce las estructuras de árbol (por ejemplo, Lisp; otros lenguajes de programación funcionales también son adecuados).
Representaciones que no utilizan árboles se han sugerido y aplicado con éxito, tales como programación genética lineal, la cual se adapta a los tradicionales lenguajes imperativos [véase, por ejemplo, Banzhaf et al. (1998)]. El software comercial de GP Discipulus utilizan la inducción automática de código máquina binario ("AIM") para lograr un mejor rendimiento. μGP usa multigrafos dirigidos para generar programas que explotan al máximo la sintaxis de un dado lenguaje ensamblador.
Los principales operadores usados en algoritmos evolutivos así como GP son cruzamiento y mutación.
El cruzamiento es aplicado a un individuo mediante simples intercambios entre uno de sus nodos por otro nodo de otro individuo de la población. Con una representación basada en árboles, la sustitución de un nodo implica la sustitución de toda la rama. Esto añade una mayor efectividad al operador de cruce. Las expresiones resultantes del cruce son muy diferentes de sus padres iniciales.
La mutación afecta a un individuo de la población. Se puede sustituir un nodo entero en el individuo seleccionado, o puede simplemente reemplazar la información del nodo. Para mantener la integridad, las operaciones deben ser salvo fallos o el tipo de información que el nodo tiene debe ser tomada en cuenta. Por ejemplo, la mutación debe ser consciente de nodos operación binaria, o el operador debe ser capaz de manejar los valores que faltan.
Las ideas básicas de la programación genética han sido modificadas y extendidas en una variedad de formas:
La Programación Meta-Genética es la técnica de evolucionar meta de aprendizaje un sistema de programación usando su propia programación genética. Se sugiere que los cromosomas, el cruzamiento, y la mutación vayan evolucionando ellos mismos, por lo tanto, al igual que sus homólogos en la vida real deben ser flexibles al cambio en el medio escogido por un programador humano. Programación Meta-Genética fue propuesta formalmente por Jürgen Schmidhuber en 1987. Doug Lenat Eurisko es un esfuerzo anterior que puede ser la misma técnica. Se trata de un algoritmo recursivo pero de terminación, lo que le permite evitar una recursión infinita.
Los críticos de esta idea a menudo dicen este enfoque es demasiado amplio en su alcance. Sin embargo, podría ser posible restringir el criterio de la aptitud en una clase general de los resultados, y así obtener un GP evolucionado que sería más eficiente para producir resultados para las sub-clases. Esto podría tomar la forma de una Meta evolutiva GP para producir algoritmos humanos caminantes que se utilizan para evolucionar el funcionamiento humano como correr, saltar, etc. El criterio de aptitud aplicado a la Meta-GP simplemente sería el de eficiencia.
Para las clases de problemas generales puede no haber manera de demostrar que Meta-GP pueda ser viable producir resultados de manera más eficiente que un algoritmo creado mediante distintos enfoques. Lo mismo vale para GP estándar y otros algoritmos de búsqueda.