Evolución gramatical y semántica

Résumé

La programación genética propuesta por Koza a principios de la década de los noventa es un algoritmo evolutivo que permite generar automáticamente programas en el lenguaje de programación LISP. Desde que Koza hizo su propuesta original hasta la actualidad ha habido un importante desarrollo en el área de la programación genética. Han sido propuestas distintas variantes del método de manera que, en la actualidad, están admitidas varias clasificaciones de los mismos. La más extendida, clasifica los métodos en función de la representación de los programas que forman la población objeto del proceso evolutivo. Por una parte, la "programación genética basada en árboles" agrupa a todos los métodos que representan los programas en forma de árbol, y al que pertenece la programación genética original de Koza. Otro importante grupo es el de la "programación genética lineal" en la que los programas se representan como secuencias de instrucciones de lenguajes imperativos, o código máquina, o también cadenas numéricas. Uno de los problemas que tienen que resolver los sistemas de programación genética es asegurar la clausura sintáctica, es decir, asegurar la corrección sintáctica de los programas que forman la población. Cada sistema resuelve este problema de una manera particular. En concreto, hay un grupo de propuestas que utilizan gramáticas independientes del contexto como formalismo para asegurar la clausura sintáctica del mtodo. A este grupo se le denomina "programación genética gramatical" o "programación genética basada en gramáticas". Las distintas clasificaciones de los métodos de programación genética permiten que haya métodos que pertenezcan a más de un grupo. Este es el caso de la "Evolución Gramatical", que pertenece al grupo de la programacin genética lineal porque representa los programas como una secuencia de bits, y también pertenece a la categoría de programación genética gramatical porque utiliza una gramática independiente del contexto para garantizar la clausura sintáctica. Los autores de la Evolución Gramatical, Michael O'Neill y Conor Ryan, definen su método como ``algoritmo evolutivo capaz de generar automáticamente programas escritos en cualquier lenguaje de programación''. La motivación de esta tesis es intentar responder a la pregunta: Qué resultados se obtendrán incorporando en la programación genética lo que podemos llamar clausura semántica o corrección semántica de los programas que forman la población? Mejorara el rendimiento si los programas adems de ser sintácticamente correctos también lo son semánticamente?. Para intentar responder a las preguntas anteriores, se proponen en esta tesis dos métodos que extienden con semántica la Evolución Gramatical, es decir, que garantizan la corrección semántica de los programas. El primer método utiliza las gramáticas de atributos como formalismo para la representación del lenguaje que genera las soluciones, y el segundo hace uso de las gramáticas de Christiansen. Junto con los métodos teóricos propuestos en esta tesis, se ha desarrollado una aplicación con el objetivo de disponer de un entorno en el que probar dichos métodos y así poder validar su funcionamiento y evaluar su rendimiento. Una de las posibles aplicaciones de las técnicas que se proponen en esta tesis es la programación automática de sistemas complejos, como por ejemplo los sistemas de computación con membranas (sistemas P) o los sistemas de splicing (sistemas H). Entendemos por programación automática de un sistema complejo la obtención de un diseño de dicho sistema de manera que se comporte de acuerdo con una funcionalidad previamente establecida. La programación automática de sistemas complejos mediante las técnicas propuestas en esta tesis supone, en primer lugar, definir el lenguaje con el que se van a expresar los sistemas. Esa definición en algunos casos se hará con gramáticas de atributos, y en otros con gramáticas de Christiansen. En segundo lugar, es necesario programar un simulador capaz de ejecutar los sistemas programados y así poder evaluar el comportamiento del sistema. Una vez que se dispone del lenguaje generador de los sistemas y de un evaluador de los mismos, es ya posible ejecutar el algoritmo evolutivo para encontrar el sistema que mejor se adapte a la funcionalidad previamente establecida. Si los sistemas solo se definen sintácticamente, como lo hace la técnica de Evolución Gramatical, el espacio de búsqueda es mucho mayor que cuando se incorporan aspectos semánticos, como lo hacen las técnicas propuestas en esta tesis