Programación Genética vs Gramáticas Evolutivas

Una de las principales problemas que se encuentran aquellos que descargan la plataforma Entropycs por primera vez es que el concepto de gramática evolutiva es difícil de entender. Y más concretamente, son muchos los que confunden las gramáticas evolutivas con la programación genética, y no es lo mismo. En esta entrada de blog intentaré explicar las diferencias entre ambas técnicas de optimización y búsqueda.

Quizás nos ayude a entender la diferencia si utilizamos el símil bioquímico de cómo se produce la evolución en la naturaleza. La información que nos permite "construir" un organismo vivo viene almacenada en una cadena de pares de bases denominada ADN, que a su vez se desliga en una cadena de ARN, que es interpretada generando secuencias de aminoácidos, que finalmente se convierten en las proteínas que son necesarias para el desarrollo de la vida. Cuando dos individuos se aparean, su descendencia herada una recombinación del ADN de los padres.

Tanto la programación genética como las gramaticas evolutivas se basan en mismo concepto de recombinación de la información de los padres; pero mientras las gramáticas evolutivas lo que recombinan son las cadenas de ADN (al igual que sucede en la naturaleza), la programación genética lo que recombina son las propias protenias finales. Traladado esto al mundo de la informática y de los lenguajes de programación, tenemos que las gramáticas evolutivas combinan cadenas de ADN que son interpretadas (por las gramáticas) para producir programas, y la programación genética lo que recombina son los propios programas.

En mi opinión, al añadir un nuevo nivel de abstracción introduciendo el concepto de gramática, se gana mucha flexibilidad, y se eliminan algunos de los principales problemas que nos encontramos con la programación genética.

Por ejemplo, las gramáticas evolutivas se basan en algoritmos genéticos para realizar la búsqueda de aquellos programas que mejor se adaptan a nuestras necesidades, pero nada nos impede utilizar otras técnicas de búsqueda, como son los enjambres de partículas, o evolución diferencial.

Por otro lado, con la programación genética el principal problema que nos encontramos es cómo garantizar que los programas que resultan de una recombinación son sintácitcamente correctos. Con las gramáticas evolutivas este problema simplemente desaparece, ya que la derivación de los programas, al estar basada en una gramática, por definición, son sintácticamente correctos.

Espero que con esta entrada haya quedado algo más clara la diferencia entre una optimización mediante gramáticas evolutivas y otra mediante programación genética.