Evolución gramatical

La evolución gramatical (GE) es una técnica (o enfoque) de programación genética (GP) de computación evolutiva iniciada por Conor Ryan, JJ Collins y Michael O'Neill en 1998 ^{[ 1 ]} en el Grupo BDS de la Universidad de Limerick .

Como en cualquier otro enfoque de programación genética (PG), el objetivo es encontrar un programa ejecutable, un fragmento de programa o una función que alcance un buen valor de aptitud para una función objetivo dada . En la mayoría de los trabajos publicados sobre PG, se manipula directamente una expresión estructurada en árbol al estilo LISP , mientras que la gramática genética (GE) aplica operadores genéticos a una cadena entera, que posteriormente se asigna a un programa (o similar) mediante una gramática, que normalmente se expresa en forma de Backus-Naur . Una de las ventajas de la GE es que esta asignación simplifica la aplicación de la búsqueda a diferentes lenguajes de programación y otras estructuras.

En la programación genética convencional de estilo Koza , sin tipado estático , el conjunto de funciones debe cumplir el requisito de cierre: todas las funciones deben poder aceptar como argumentos la salida de todas las demás funciones del conjunto. Normalmente, esto se implementa trabajando con un único tipo de dato, como el de punto flotante de doble precisión. Si bien los marcos de programación genética modernos admiten el tipado, estos sistemas de tipos presentan limitaciones que la Evolución Gramatical no padece.

GE ofrece una solución a la limitación de un solo tipo mediante la evolución de soluciones según una gramática especificada por el usuario (generalmente una gramática en forma de Backus-Naur ). Por lo tanto, el espacio de búsqueda puede restringirse y el conocimiento del dominio del problema puede incorporarse. La inspiración para este enfoque proviene del deseo de separar el "genotipo" del "fenotipo": en GP, ​​los objetos sobre los que opera el algoritmo de búsqueda y lo que interpreta la función de evaluación de aptitud son idénticos. En cambio, los "genotipos" de GE son listas ordenadas de enteros que codifican las reglas de selección de la gramática libre de contexto proporcionada. El fenotipo, sin embargo, es el mismo que en GP de estilo Koza: una estructura arbórea que se evalúa recursivamente. Este modelo se ajusta mejor al funcionamiento de la genética en la naturaleza, donde existe una separación entre el genotipo de un organismo y la expresión final del fenotipo en proteínas, etc.

La separación entre genotipo y fenotipo permite un enfoque modular. En particular, la búsqueda en el paradigma de GE no necesita realizarse mediante un algoritmo o método específico. Cabe destacar que los objetos sobre los que GE realiza la búsqueda son los mismos que los utilizados en los algoritmos genéticos . Esto significa que, en principio, cualquier paquete de algoritmos genéticos existente, como la popular biblioteca GAlib , puede utilizarse para llevar a cabo la búsqueda, y un desarrollador que implemente un sistema GE solo debe preocuparse por realizar la asignación de la lista de enteros al árbol del programa. También es posible, en principio, realizar la búsqueda utilizando otro método, como la optimización por enjambre de partículas (véase la nota a continuación); la naturaleza modular de GE crea numerosas oportunidades para la creación de híbridos, según lo requiera el problema a resolver.

Brabazon y O'Neill han aplicado con éxito la GE para predecir la quiebra de empresas, pronosticar índices bursátiles, calificaciones crediticias de bonos y otras aplicaciones financieras. La GE también se ha utilizado con un modelo clásico depredador-presa para explorar el impacto de parámetros como la eficiencia del depredador, el número de nichos y las mutaciones aleatorias en la estabilidad ecológica . ^{[ 2 ]}

Es posible estructurar una gramática GE que, para un conjunto de funciones/terminales dado, sea equivalente a la programación genética.

A pesar de sus éxitos, GE ha sido objeto de algunas críticas. Un problema es que, como resultado de su operación de mapeo, los operadores genéticos de GE no alcanzan una alta localidad ^{[ 3 ] [ 4 ]} , que es una propiedad muy valorada de los operadores genéticos en los algoritmos evolutivos. ^{[ 3 ]}

Aunque la GE se describió originalmente en términos del uso de un algoritmo evolutivo, específicamente un algoritmo genético, existen otras variantes. Por ejemplo, los investigadores de GE han experimentado con el uso de la optimización por enjambre de partículas (PSO) para llevar a cabo la búsqueda en lugar de algoritmos genéticos, obteniendo resultados comparables a los de la GE convencional; esto se conoce como "enjambre gramatical". Utilizando únicamente el modelo básico de PSO, se ha descubierto que este algoritmo es probablemente igual de capaz de realizar el proceso de búsqueda en GE que los algoritmos genéticos simples. (Si bien PSO suele ser un paradigma de búsqueda de punto flotante, puede discretizarse, por ejemplo, redondeando cada vector al entero más cercano, para su uso en GE).

Otra posible variación que se ha experimentado en la literatura consiste en intentar codificar información semántica en la gramática para sesgar aún más el proceso de búsqueda. Otros trabajos demostraron que, con gramáticas sesgadas que aprovechan el conocimiento del dominio, incluso la búsqueda aleatoria puede utilizarse para impulsar la GE. ^{[ 5 ]}

GE fue originalmente una combinación de la representación lineal utilizada por el Algoritmo Genético para el Desarrollo de Software (GADS) ^{[ 6 ]} y las gramáticas de la Forma de Backus-Naur, que fueron utilizadas originalmente en GP basado en árboles por Wong y Leung ^{[ 7 ]} en 1995 y Whigham en 1996. ^{[ 8 ]} Otro trabajo relacionado mencionado en el artículo original de GE fue el de Frederic Gruau, ^{[ 9 ]} quien utilizó un enfoque "embrionario" conceptualmente similar, así como el de Keller y Banzhaf, ^{[ 10 ]} que utilizó de manera similar genomas lineales.

Existen varias implementaciones de GE. Estas incluyen las siguientes.

• Programación genética
• Evolución gramatical de Java
• Programación genética cartesiana
• Programación de la expresión génica
• Programación genética lineal
• Programación de expresiones múltiples