Programación genética - Genetic programming

No confundir con programación genérica , ingeniería genética o computación de ADN .
Parte de una serie sobre el
Algoritmo evolutivo
Algoritmo genético
Programación genética

En inteligencia artificial, la programación genética ( GP ) es una técnica de programas en evolución, a partir de una población de programas no aptos (generalmente aleatorios), aptos para una tarea particular mediante la aplicación de operaciones análogas a los procesos genéticos naturales a la población de programas. Es esencialmente una técnica de búsqueda heurística que a menudo se describe como "escalada de colinas", es decir, buscar un programa óptimo o al menos adecuado entre el espacio de todos los programas.

Las operaciones son: selección de los programas más aptos para la reproducción (cruce) y la mutación de acuerdo con una medida de aptitud predefinida, generalmente competencia en la tarea deseada. La operación de cruce implica intercambiar partes aleatorias de pares seleccionados (padres) para producir descendientes nuevos y diferentes que se vuelven parte de la nueva generación de programas. La mutación implica la sustitución de alguna parte aleatoria de un programa por otra parte aleatoria de un programa. Algunos programas no seleccionados para reproducción se copian de la generación actual a la nueva generación. Luego, la selección y otras operaciones se aplican de forma recursiva a la nueva generación de programas.

Por lo general, los miembros de cada nueva generación están en promedio más en forma que los miembros de la generación anterior, y el programa de la mejor generación suele ser mejor que los programas de la mejor generación de generaciones anteriores. La terminación de la recursividad es cuando algún programa individual alcanza un nivel de aptitud o competencia predefinido.

Puede suceder, y sucede a menudo, que una ejecución particular del algoritmo dé como resultado una convergencia prematura a un máximo local que no es una solución globalmente óptima o incluso buena. Por lo general, se necesitan varias ejecuciones (decenas a cientos) para producir un resultado muy bueno. También puede ser necesario aumentar el tamaño de la población inicial y la variabilidad de los individuos para evitar patologías.

Historia

El primer registro de la propuesta de desarrollar programas es probablemente el de Alan Turing en 1950. Hubo un intervalo de 25 años antes de que la publicación de John Holland, Adaptation in Natural and Artificial Systems, estableciera los fundamentos teóricos y empíricos de la ciencia. En 1981, Richard Forsyth demostró la exitosa evolución de pequeños programas, representados como árboles, para realizar la clasificación de las pruebas de la escena del crimen para el Ministerio del Interior del Reino Unido.

Aunque la idea de desarrollar programas, inicialmente en el lenguaje informático Lisp , era corriente entre los estudiantes de John Holland, no fue hasta que organizaron la primera conferencia de algoritmos genéticos (GA) en Pittsburgh que Nichael Cramer publicó programas evolucionados en dos lenguajes especialmente diseñados, que incluyó la primera declaración de la programación genética moderna "basada en árboles" (es decir, lenguajes de procedimiento organizados en estructuras basadas en árboles y operados por operadores GA adecuadamente definidos). En 1988, John Koza (también estudiante de doctorado de John Holland) patentó su invención de un GA para la evolución de programas. A esto le siguió la publicación en la Conferencia Internacional Conjunta sobre Inteligencia Artificial IJCAI-89.

Koza siguió con 205 publicaciones sobre “Programación genética” (GP), nombre acuñado por David Goldberg, también estudiante de doctorado de John Holland. Sin embargo, es la serie de 4 libros de Koza, que comenzó en 1992 con videos de acompañamiento, lo que realmente estableció a GP. Posteriormente, hubo una enorme expansión del número de publicaciones con Bibliografía de Programación Genética, superando las 10.000 entradas. En 2010, Koza enumeró 77 resultados en los que la programación genética era competitiva para los humanos.

En 1996, Koza inició la conferencia anual de programación genética, a la que siguió en 1998 la conferencia anual EuroGP, y el primer libro de una serie de GP editado por Koza. 1998 también vio el primer libro de texto GP. GP continuó floreciendo, lo que llevó a la primera revista especializada en GP y tres años más tarde (2003) Rick Riolo estableció el taller anual de teoría y práctica de la programación genética (GPTP). Los artículos sobre programación genética continúan publicándose en una diversidad de conferencias y revistas asociadas. Hoy en día hay diecinueve libros de medicina general, incluidos varios para estudiantes.

Trabajo fundacional en GP

El trabajo inicial que preparó el escenario para los temas y aplicaciones actuales de investigación en programación genética es diverso e incluye síntesis y reparación de software , modelado predictivo, minería de datos, modelado financiero, sensores blandos, diseño y procesamiento de imágenes. Las aplicaciones en algunas áreas, como el diseño, a menudo hacen uso de representaciones intermedias, como la codificación celular de Fred Gruau. La aceptación industrial ha sido significativa en varias áreas, incluidas las finanzas, la industria química, la bioinformática y la industria del acero.

Métodos

Representación del programa

Una función representada como una estructura de árbol
Artículo principal: representación genética

GP desarrolla programas de computadora, tradicionalmente representados en la memoria como estructuras de árbol . Los árboles se pueden evaluar fácilmente de forma recursiva. Cada nodo de árbol tiene una función de operador y cada nodo terminal tiene un operando, lo que hace que las expresiones matemáticas sean fáciles de evolucionar y evaluar. Así, tradicionalmente, GP favorece el uso de lenguajes de programación que incorporan naturalmente estructuras de árbol (por ejemplo, Lisp ; otros lenguajes de programación funcionales también son adecuados).

Se han sugerido e implementado con éxito representaciones que no son árboles, como la programación genética lineal que se adapta a los lenguajes imperativos más tradicionales [ver, por ejemplo, Banzhaf et al. (1998)]. El software comercial de GP Discipulus utiliza la inducción automática de código binario de máquina ("AIM") para lograr un mejor rendimiento. µGP usa multigrafos dirigidos para generar programas que explotan completamente la sintaxis de un lenguaje ensamblador dado . Otras representaciones de programas en las que se han realizado importantes investigaciones y desarrollos incluyen programas para máquinas virtuales basadas en pilas y secuencias de números enteros que se asignan a lenguajes de programación arbitrarios mediante gramáticas. La programación genética cartesiana es otra forma de GP, que utiliza una representación gráfica en lugar de la representación habitual basada en árboles para codificar programas informáticos.

La mayoría de las representaciones tienen un código estructuralmente no efectivo ( intrones ). Estos genes no codificantes pueden parecer inútiles porque no tienen ningún efecto sobre el desempeño de ningún individuo. Sin embargo, alteran las probabilidades de generar descendencia diferente bajo los operadores de variación y, por lo tanto, alteran las propiedades de variación del individuo . Los experimentos parecen mostrar una convergencia más rápida cuando se utilizan representaciones de programas que permiten tales genes no codificantes, en comparación con representaciones de programas que no tienen genes no codificantes.

Selección

La selección es un proceso mediante el cual se seleccionan ciertos individuos de la generación actual que servirían como padres para la próxima generación. Los individuos se seleccionan probabilísticamente de modo que los individuos con mejor desempeño tengan una mayor probabilidad de ser seleccionados. El método de selección más comúnmente utilizado en GP es la selección de torneos , aunque se ha demostrado que otros métodos, como la selección proporcional de aptitud física , la selección de lexicasa y otros, funcionan mejor para muchos problemas de GP.

El elitismo, que implica sembrar la próxima generación con el mejor individuo (o los mejores n individuos) de la generación actual, es una técnica que a veces se emplea para evitar la regresión.

Transversal

En la programación genética, se eligen dos individuos aptos de la población para que sean padres de uno o dos hijos. En la programación genética de árboles, estos padres se representan como árboles ceceos invertidos, con sus nodos de raíz en la parte superior. En el cruce de subárboles en cada padre, se elige aleatoriamente un subárbol. (Resaltado con amarillo en la animación). En el padre donante raíz (en la animación de la izquierda), el subárbol elegido se elimina y se reemplaza con una copia del subárbol elegido al azar del otro padre, para dar un nuevo árbol hijo.

A veces se usa el cruce de dos hijos, en cuyo caso el subárbol eliminado (en la animación de la izquierda) no se elimina simplemente sino que se copia en una copia del segundo padre (aquí a la derecha) reemplazando (en la copia) su elegido al azar subárbol. Por lo tanto, este tipo de cruce de subárboles toma dos árboles de ajuste y genera dos árboles secundarios. Cruce de subárboles de programación genética

Mutación

Hay muchos tipos de mutaciones en la programación genética. Parten de un padre adecuado sintácticamente correcto y tienen como objetivo crear aleatoriamente un hijo sintácticamente correcto. En la animación, se elige aleatoriamente un subárbol (resaltado en amarillo). Se elimina y se reemplaza por un subárbol generado aleatoriamente.

Otros operadores de mutación seleccionan una hoja (nodo externo) del árbol y la reemplazan con una hoja elegida al azar. Otra mutación es seleccionar al azar una función (nodo interno) y reemplazarla con otra función con la misma aridad (número de entradas). La mutación Hoist elige aleatoriamente un subárbol y lo reemplaza con un subárbol dentro de sí mismo. Por lo tanto, se garantiza que la mutación del polipasto hará que el niño sea más pequeño. La hoja y el reemplazo de la misma función de aridad garantizan que el niño tenga el mismo tamaño que el padre. Mientras que la mutación del subárbol (en la animación) puede, dependiendo de la función y los conjuntos terminales, tener un sesgo para aumentar o disminuir el tamaño del árbol. Otras mutaciones basadas en subárboles intentan controlar cuidadosamente el tamaño del subárbol de reemplazo y, por lo tanto, el tamaño del árbol hijo.

Animación de la creación de un hijo de programación genética mediante la mutación del padre, que elimina el subárbol y lo reemplaza con un código aleatorio.

De manera similar, existen muchos tipos de mutación de programación genética lineal, cada uno de los cuales intenta garantizar que el niño mutado siga siendo sintácticamente correcto.

Aplicaciones

GP se ha utilizado con éxito como una herramienta de programación automática , una herramienta de aprendizaje automático y un motor automático de resolución de problemas. GP es especialmente útil en los dominios donde la forma exacta de la solución no se conoce de antemano o una solución aproximada es aceptable (posiblemente porque encontrar la solución exacta es muy difícil). Algunas de las aplicaciones de GP son ajuste de curvas, modelado de datos, regresión simbólica , selección de características , clasificación, etc. John R. Koza menciona 76 casos en los que la Programación Genética ha podido producir resultados que son competitivos con los resultados producidos por humanos (denominados Human -resultados competitivos). Desde 2004, la Conferencia anual de Computación Genética y Evolutiva ( GECCO ) lleva a cabo la competencia Human Competitive Awards (llamada Humies), donde se otorgan premios en efectivo a los resultados competitivos humanos producidos por cualquier forma de computación genética y evolutiva. GP ha ganado muchos premios en esta competición a lo largo de los años.

Programación metagenética

Meta-programación genética es la propuesta de aprendizaje meta técnica de la evolución de un sistema de programación genética utilizando programación genética en sí. Sugiere que los cromosomas, el cruce y la mutación fueron ellos mismos evolucionados, por lo tanto, al igual que sus contrapartes de la vida real, deberían poder cambiar por sí mismos en lugar de ser determinados por un programador humano. Meta-GP fue propuesto formalmente por Jürgen Schmidhuber en 1987. Doug Lenat 's Eurisko es un esfuerzo anterior que puede ser la misma técnica. Es un algoritmo recursivo pero terminante, lo que le permite evitar la recursividad infinita. En el enfoque de la "evolución autoconstructiva" de la programación metagenética, los métodos para la producción y variación de la descendencia se codifican dentro de los propios programas en evolución, y los programas se ejecutan para producir nuevos programas que se agregarán a la población.

Los críticos de esta idea a menudo dicen que este enfoque tiene un alcance demasiado amplio. Sin embargo, podría ser posible restringir el criterio de aptitud a una clase general de resultados, y así obtener un GP evolucionado que produciría resultados de manera más eficiente para las subclases. Esto podría tomar la forma de un GP meta evolucionado para producir algoritmos de caminata humana que luego se usa para hacer evolucionar la carrera humana, el salto, etc. El criterio de aptitud aplicado al meta GP sería simplemente uno de eficiencia.

Ver también

Referencias

enlaces externos