Strategies for reducing the size of the search space in semantic genetic programming

Luis Fernando Miranda

Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/ESBF-B5UMN3

Full metadata record

DC Field	Value	Language
dc.contributor.advisor1	Gisele Lobo Pappa	pt_BR
dc.contributor.advisor-co1	Luiz Otavio Vilas Boas Oliveira	pt_BR
dc.contributor.referee1	Fabricio Murai Ferreira	pt_BR
dc.contributor.referee2	Thiago Ferreira de Noronha	pt_BR
dc.contributor.referee3	Eduardo Gontijo Carrano	pt_BR
dc.creator	Luis Fernando Miranda	pt_BR
dc.date.accessioned	2019-08-10T09:44:00Z	-
dc.date.available	2019-08-10T09:44:00Z	-
dc.date.issued	2018-03-12	pt_BR
dc.identifier.uri	http://hdl.handle.net/1843/ESBF-B5UMN3	-
dc.description.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.	pt_BR
dc.description.resumo	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.	pt_BR
dc.language	Inglês	pt_BR
dc.publisher	Universidade Federal de Minas Gerais	pt_BR
dc.publisher.initials	UFMG	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.subject	Supervised Learning	pt_BR
dc.subject	Instance Selection	pt_BR
dc.subject	Geometric Semantic Genetic Programming	pt_BR
dc.subject	Symbolic Regression	pt_BR
dc.subject.other	Programação Genética ( Computação)	pt_BR
dc.subject.other	Computação	pt_BR
dc.title	Strategies for reducing the size of the search space in semantic genetic programming	pt_BR
dc.type	Dissertação de Mestrado	pt_BR
Appears in Collections:	Dissertações de Mestrado

Files in This Item:

File	Description	Size	Format
luisfernandomiranda.pdf		5.31 MB	Adobe PDF	View/Open

Show simple item record