Contenido
PalancaAlgoritmo de evolución gramatical
El algoritmo de evolución gramatical está inspirado en el proceso biológico utilizado para generar una proteína a partir de material genético, así como en el proceso evolutivo genético más amplio. El genoma está formado por ADN como una cadena de bloques de construcción que se transcriben en ARN. Los codones de ARN, a su vez, se traducen en secuencias de aminoácidos y se utilizan en la proteína. La proteína resultante en su entorno es el fenotipo.
El fenotipo es un programa informático creado a partir de un genoma basado en cadenas binarias. El genoma se decodifica en una secuencia de números enteros que, a su vez, se asignan a reglas predefinidas que componen el programa. El mapeo de genotipo a fenotipo es un proceso de uno a muchos que utiliza una función de empaquetado.
Es como el proceso biológico que se observa en muchas bacterias, virus y mitocondrias, donde se usa el mismo material genético en la expresión de diferentes genes. El mapeo agrega robustez al proceso tanto en la capacidad de adoptar operadores genéticos utilizados durante el proceso evolutivo en la representación sub-simbólica como en la transcripción de programas ejecutables bien formados a partir de la representación.
El objetivo del algoritmo de evolución gramatical es adaptar un programa ejecutable a una función objetivo específica del problema. Esto se logra a través de un proceso iterativo con sustitutos de mecanismos evolutivos tales como descendencia con variación, mutación y recombinación genética, transcripción genética y expresión génica. Una población de programas se expande en forma subsimbólica como cadenas binarias de longitud variable y se asigna a forma simbólica y bien estructurada como gramática sin contexto para la ejecución.
Una gramática se define en Backus Normal Form (BNF), que es una gramática sin contexto expresada como una serie de reglas de producción que comprenden terminales y no terminales. Se utiliza una representación de cadena binaria de longitud variable para el proceso de optimización. Los bits se leen del genoma de las soluciones candidatas en bloques de 8 llamados codones y se decodifican en un número entero (entre 0 y 2 ^ 8 - 1).
Si se alcanza el final de la cadena binaria mientras se lee números enteros, el proceso de lectura vuelve al principio de la cadena, creando un genoma circular. Los enteros se asignan a expresiones en el BNF hasta que se forma una expresión completa sintácticamente correcta. Esto no puede usar un genoma completo de soluciones, o usar el genoma decodificado más de una vez dada su naturaleza circular.
La evolución gramatical fue diseñada para optimizar los programas (como las ecuaciones Matemáticas) para funciones de coste específicas. Los operadores genéticos clásicos utilizados por losalgoritmo genético se puede utilizar en el algoritmo de evolución gramatical, como mutaciones puntuales y cruce de puntos. Se pueden usar operadores genéticos adicionales con representaciones de longitud variable, como segmentos de codones, duplicación (añadir al final), número de codones seleccionados aleatoriamente y eliminación.