New techniques for grammar guided genetic programmingdealing with large derivation trees and high cardinality terminal symbol sets

Resumo

Los algoritmos metaheurísticos han demostrado tener un importante papel en la resolución de problemas de búsqueda y optimización complejos. La programación genética guiada por gramáticas es una técnica de optimización metaheurística, enmarcada dentro del campo de la computación natural, que permite manejar soluciones de dimensión variable. No obstante, aunque es un método metaheurístico, muestra ciertas limitaciones en la resolución de problemas con gramáticas libre de contexto que generan espacios de búsqueda grandes. Concretamente, cuando se generan árboles de derivación grandes o el conjunto de símbolos terminales tiene una alta cardinalidad. El trabajo de investigación presentado en esta tesis muestra que la inicialización de poblaciones y los operadores de modificación son las principales causas de estas limitaciones. Los métodos de inicialización de poblaciones existentes no generan generan muestras representativas del espacio de búsqueda. Por su parte, los operadores de modificación son altamente exploratorios o demasiado destructivos, por lo que no son capaces de guiar el proceso de optimización de forma adecuada. Con el fin de disminuir o resolver el efecto de estas limitaciones se presentan tres contribuciones principales: un método de inicialización de poblaciones gramaticalmente uniforme, un operador de cruce basado en la estimación de distribución de poblaciones y un método de optimización cooperativa asíncrono que permite trabajar con gramáticas con una alta cardinalidad del conjunto de símbolos terminales. Los experimentos realizados muestran las ventajas de utilizar estas técnicas originales en la resolución de problemas con las características antes mencionadas. Se han diseñado problemas de laboratorio con el fin de mostrar las limitaciones de las técnicas actuales en GGGP. Asimismo, se han llevado a cabo experimentos de forma satisfactoria con problemas cuyos espacios de búsqueda son grandes para la búsqueda y optimización de distintos tipos sistemas inteligentes.