New techniques for Grammar Guided Genetic Programming: dealing with large derivation trees and high cardinality terminal symbol sets

Ramos Criado, Pablo (2017). New techniques for Grammar Guided Genetic Programming: dealing with large derivation trees and high cardinality terminal symbol sets. Thesis (Doctoral), E.T.S. de Ingenieros Informáticos (UPM). https://doi.org/10.20868/UPM.thesis.48795.

Description

Title: New techniques for Grammar Guided Genetic Programming: dealing with large derivation trees and high cardinality terminal symbol sets
Author/s:
  • Ramos Criado, Pablo
Contributor/s:
  • Manrique Gamo, Daniel
  • Font Fernández, José María
Item Type: Thesis (Doctoral)
Date: 2017
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (5MB) | Preview

Abstract

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. ----------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.

More information

Item ID: 48795
DC Identifier: http://oa.upm.es/48795/
OAI Identifier: oai:oa.upm.es:48795
DOI: 10.20868/UPM.thesis.48795
Deposited by: Archivo Digital UPM 2
Deposited on: 09 Jan 2018 08:59
Last Modified: 09 Jul 2018 22:30
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM