- author = "Pablo {Ramos Criado}",
- title = "New techniques for Grammar Guided Genetic Programming: dealing with large derivation trees and high cardinality terminal symbol sets",
- school = "Inteligencia Artificial, E.T.S. de Ingenieros Informaticos, Universidad Politecnica de Madrid",
- year = "2017",
- address = "Spain",
- keywords = "genetic algorithms, genetic programming, CFG",
- number = "10.20868/UPM.thesis.48795",
-
URL = "
http://oa.upm.es/48795/1/PABLO_RAMOS_CRIADO.pdf",
-
URL = "
http://oa.upm.es/48795/",
-
DOI = "
doi:10.20868/upm.thesis.48795",
- size = "270 pages",
-
abstract = "Metaheuristic algorithms have shown an important role
in the resolution of complex search and optimization
problems. Grammar guided genetic programming is a
metaheuristic optimization technique within natural
computing that works with solutions of variable size.
However, although it is a metaheuristic method, it has
shown some limitations when solving problems using
context free grammars that generate large search
spaces. Concretely, when they generate large derivation
trees or possess a high cardinality terminal symbol
set.
The presented research work has determined the population initialization and the variation operators as the main causes of these limitations. Population initialization methods are unable to generate a representative sample of the search space. The variation operators are either very explorative or too destructive, being unable to actively guide the optimization process. To address these limitations, three major contributions are presented: a grammatically uniform population initialization, an estimation of distribution crossover operator and an asynchronous endosymbiotic co-optimization technique designed to work with high cardinality terminal symbol sets. The performed experiments show the advantages of using these novel techniques when solving problems with the above-mentioned characteristics. To such aim, laboratory experiments have been designed to highlight the limitations of the current GGGP methods. Moreover, experiments have been also successfully performed with large search spaced problems involving search and optimization of different types of intelligent systems.",
-
resumen = "Los algoritmos metaheur{\'i}sticos han demostrado
tener un importante papel en la resoluci{\'o}n de
problemas de b{\'u}squeda y optimizaci{\'o}n complejos.
La programaci{\'o}n gen{\'e}tica guiada por
gram{\'a}ticas es una t{\'e}cnica de optimizaci{\'o}n
metaheur{\'i}stica, enmarcada dentro del campo de la
computaci{\'o}n natural, que permite manejar soluciones
de dimensi{\'o}n variable. No obstante, aunque es un
m{\'e}todo metaheur{\'i}stico, muestra ciertas
limitaciones en la resoluci{\'o}n de problemas con
gram{\'a}ticas libre de contexto que generan espacios
de b{\'u}squeda grandes. Concretamente, cuando se
generan {\'a}rboles de derivaci{\'o}n grandes o el
conjunto de s{\'i}mbolos terminales tiene una alta
cardinalidad.
El trabajo de investigaci{\'o}n presentado en esta tesis muestra que la inicializaci{\'o}n de poblaciones y los operadores de modificaci{\'o}n son las principales causas de estas limitaciones. Los m{\'e}todos de inicializaci{\'o}n de poblaciones existentes no generan generan muestras representativas del espacio de b{\'u}squeda. Por su parte, los operadores de modificaci{\'o}n son altamente exploratorios o demasiado destructivos, por lo que no son capaces de guiar el proceso de optimizaci{\'o}n de forma adecuada. Con el fin de disminuir o resolver el efecto de estas limitaciones se presentan tres contribuciones principales: un m{\'e}todo de inicializaci{\'o}n de poblaciones gramaticalmente uniforme, un operador de cruce basado en la estimaci{\'o}n de distribuci{\'o}n de poblaciones y un m{\'e}todo de optimizaci{\'o}n cooperativa as{\'i}ncrono que permite trabajar con gram{\'a}ticas con una alta cardinalidad del conjunto de s{\'i}mbolos terminales. Los experimentos realizados muestran las ventajas de utilizar estas t{\'e}cnicas originales en la resoluci{\'o}n de problemas con las caracter{\'i}sticas antes mencionadas. Se han dise{\~n}ado problemas de laboratorio con el fin de mostrar las limitaciones de las t{\'e}cnicas actuales en GGGP. Asimismo, se han llevado a cabo experimentos de forma satisfactoria con problemas cuyos espacios de b{\'u}squeda son grandes para la b{\'u}squeda y optimizaci{\'o}n de distintos tipos sistemas inteligentes.",
-
notes = "In English
Supervisors: Daniel Manrique Gamo (dmanrique@fi.upm.es) and Jose Maria Font Fernandez",
