Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/ESBF-B5UMN3| Type: | Dissertação de Mestrado |
| Title: | Strategies for reducing the size of the search space in semantic genetic programming |
| Authors: | Luis Fernando Miranda |
| First Advisor: | Gisele Lobo Pappa |
| First Co-advisor: | Luiz Otavio Vilas Boas Oliveira |
| First Referee: | Fabricio Murai Ferreira |
| Second Referee: | Thiago Ferreira de Noronha |
| Third Referee: | Eduardo Gontijo Carrano |
| Abstract: | Ao tentar resolver problemas de otimizacao, algoritmos de programacao genetica aplicam operacoes bio-inspiradas (mutacao e cruzamento, por exemplo) de forma a explorar o espaco de possiveis solucoes em busca de uma solucao satisfatoria. Normalmente tais algoritmos sao utilizados na resolucao de um problema conhecido como regressao simbolica, onde o objetivo e encontrar uma expressao matematica cuja curva correspondente se aproxime daquela induzida a partir de um conjunto de instancias de treinamento. Operadores canonicos de programacao genetica nao levam em conta aspectos semanticos, o que tende a piorar o desempenho e a robustez dos metodos que os uti- lizam. Operadores geneticos semanticos, por outro lado, agregam nocoes de semantica que permitem uma exploracao mais consistente do espaco de busca. Outra melhoria parte da exploracao de propriedades geometricas que descrevem a relacao espacial entre possiveis solucoes em um espaco semantico n-dimensional, onde n e igual ao numero de instancias de treinamento. O metodo normalmente tomado como referencia nesse contexto se chama Geometric Semantic Genetic Programming (GSGP). No entanto, em problemas onde o valor de n e alto - um cenario comum em aplicacoes reais - o processo de busca pode se tornar excessivamente complicado, uma vez que o volume do espaco semantico cresce exponencialmente em funcao do numero de dimensoes. Esta tese busca reduzir esse problema, focando na reducao da dimensionalidade do espaco de busca no contexto de programacao genetica semantica atraves de metodos de selecao de instancias. Nosso principal objetivo e projetar, implementar e validar metodos que reduzam o tamanho do espaco de busca. Mais precisamente, queremos entender ate que ponto o numero de dimensoes do espaco semantico e capaz de influenciar o processo de busca e qual o impacto da aplicacao de metodos de selecao sobre os resultados da busca realizada pelo GSGP. Alem disso, buscamos entender o impacto provocado pelo ruido sobre os metodos de programacao genetica e sobre as estrategias de selecao de instancia propostas. Duas abordagens sao consideradas: (i) aplicar metodos de selecao de instancias como uma etapa de pre-processamento, antes que as instancias de treinamento sejam fornecidas ao GSGP e (ii) incorporar a selecao de instancias ao processo evolutivo do GSGP. Um conjunto de experimentos foi realizado em um grupo de bases de dados reais e sinteticas. A analise experimental realizada indica que parte dos metodos propostos podem, de fato, melhorar aspectos relacionados a busca realizada pelo GSGP. |
| Abstract: | Genetic programming (GP) uses bio-inspired operations to find adequate solutions to a diverse range of problems, including symbolic regression. Recent works introduced semantic awareness into these operations, enhancing the search. In particular, Geometric Semantic GP (GSGP)-the method taken as reference in this context-exploits geometric properties describing the relationship between possible solutions in an n-dimensional semantic space, where n is the number of training instances. However, in problems where n is high-a common scenario in real applications-the search can become excessively complicated. We tackle this problem by reducing the dimensionality of the semantic space through instance selection (IS) methods. We present two distinct strategies: the first is implemented as a pre-processing step while the second incorporates IS to the search. Our results showed that IS methods can improve the search performed by GSGP, resulting in a faster search for models with smaller errors. |
| Subject: | Programação Genética ( Computação) Computação |
| language: | Inglês |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/ESBF-B5UMN3 |
| Issue Date: | 12-Mar-2018 |
| Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| luisfernandomiranda.pdf | 5.31 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.