La evolución gramatical (GE) es una computación evolutiva y, más específicamente, una técnica (o enfoque) de programación genética (GP) iniciada por Conor Ryan, JJ Collins y Michael O'Neill en 1998 [1] en el BDS Group en la Universidad de Limerick , aunque hay otros trabajos relacionados, que fueron publicados incluso antes, como. [2]
Como en cualquier otro enfoque de GP, el objetivo es encontrar un programa ejecutable, un fragmento de programa o una función que logre un buen valor de adecuación para una función objetivo determinada . En la mayoría de los trabajos publicados sobre GP, una expresión estructurada en árbol de estilo LISP se manipula directamente, mientras que GE aplica operadores genéticos a una cadena entera, posteriormente mapeada a un programa (o similar) mediante el uso de una gramática, que generalmente se expresa en Forma Backus-Naur . Uno de los beneficios de GE es que este mapeo simplifica la aplicación de la búsqueda a diferentes lenguajes de programación y otras estructuras.
Problema abordado
En GP de estilo Koza convencional, libre de tipos , el conjunto de funciones debe cumplir el requisito de cierre: todas las funciones deben ser capaces de aceptar como argumentos la salida de todas las demás funciones del conjunto de funciones. Por lo general, esto se implementa tratando con un solo tipo de datos, como el punto flotante de doble precisión. Si bien los marcos de programación genética modernos admiten la escritura, tales sistemas de tipos tienen limitaciones de las que la evolución gramatical no sufre.
La solución de GE
GE ofrece una solución a esto [ ¿cuál? ] problema al desarrollar soluciones de acuerdo con una gramática especificada por el usuario (generalmente una gramática en forma Backus-Naur ). Por lo tanto, se puede restringir el espacio de búsqueda y se puede incorporar el conocimiento del dominio del problema. 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 la aptitud son uno y lo mismo. En contraste, los "genotipos" de GE son listas ordenadas de números enteros que codifican para seleccionar reglas de la gramática libre de contexto proporcionada. El fenotipo, sin embargo, es el mismo que en el estilo de Koza GP: una estructura en forma de árbol que se evalúa de forma recursiva. Este modelo está más en línea con el 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 de genotipo y fenotipo permite un enfoque modular. En particular, la parte de búsqueda del paradigma GE no necesita llevarse a cabo mediante ningún algoritmo o método en particular. Observe que los objetos en los que GE realiza la búsqueda son los mismos que se utilizan en los algoritmos genéticos . Esto significa, en principio, que cualquier paquete de algoritmo genético existente, como el popular GAlib , puede usarse para realizar la búsqueda, y un desarrollador que implemente un sistema GE solo debe preocuparse por realizar el mapeo de la lista de números enteros al árbol del programa. . En principio, también es posible realizar la búsqueda utilizando algún otro método, como la optimización del enjambre de partículas (consulte el comentario a continuación); la naturaleza modular de GE crea muchas oportunidades para los híbridos según lo dicta el problema de interés a resolver.
Brabazon y O'Neill han aplicado con éxito a GE para predecir quiebras corporativas, pronosticar índices bursátiles, calificaciones crediticias de bonos y otras aplicaciones financieras. [ cita requerida ] GE también se ha utilizado con un modelo clásico de depredador-presa para explorar el impacto de parámetros como la eficiencia del depredador, el número de nicho y las mutaciones aleatorias en la estabilidad ecológica . [3]
Es posible estructurar una gramática GE que para una función / conjunto terminal dado es equivalente a la programación genética.
Crí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 logran una alta localidad [4] [5], que es una propiedad muy apreciada de los operadores genéticos en algoritmos evolutivos. [4]
Variantes
Aunque GE es bastante nuevo, ya se han elaborado versiones mejoradas y variantes. Los investigadores de GE han experimentado con el uso de optimización de enjambres de partículas para llevar a cabo la búsqueda en lugar de algoritmos genéticos con resultados comparables a los de GE normal; esto se conoce como "enjambre gramatical"; utilizando sólo el modelo básico de PSO, se ha encontrado que PSO es probablemente igualmente capaz de llevar a cabo el proceso de búsqueda en GE como lo son los algoritmos genéticos simples. (Aunque PSO es normalmente un paradigma de búsqueda de punto flotante, se puede discretizar, por ejemplo, simplemente redondeando cada vector al número entero más cercano, para su uso con GE).
Sin embargo, otra posible variación con la que se ha experimentado en la literatura es intentar codificar información semántica en la gramática para sesgar aún más el proceso de búsqueda.
Ver también
Notas
- ^ http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/ryan_1998_geepal.html
- ^ https://www.researchgate.net/profile/PA_Whigham/publication/2450222_Grammatic-based_Genetic_Programming/links/55c3c89908aebc967df1b765.pdf
- ↑ Alfonseca, Manuel; Soler Gil, Francisco José (2 de enero de 2015). "Evolución de un ecosistema depredador-presa de expresiones matemáticas con evolución gramatical". Complejidad . 20 (3): 66–83. doi : 10.1002 / cplx.21507 . hdl : 10486/663611 .
- ^ a b DOI.org
- ^ http://www.cs.kent.ac.uk/pubs/2010/3004/index.html
Recursos
- Tutorial de evolución gramatical .
- Evolución gramatical en Java .
- jGE - Evolución gramatical de Java .
- El Grupo de Biocomputación y Sistemas de Desarrollo (BDS) de la Universidad de Limerick .
- Página de evolución gramatical de Michael O'Neill , que incluye una bibliografía.
- DRP , Directed Ruby Programming, es un sistema experimental diseñado para permitir a los usuarios crear sistemas híbridos GE / GP. Está implementado en Ruby puro.
- GERET , Kit de herramientas exploratorias de Ruby de evolución gramatical.
- gramEvol , gramaticales Evolución para R .