Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.1/2746
Título: Application of substructural local search in the MAXSAT problem
Autor: Gonzalez, Pedro Frazão
Orientador: Lobo, Fernando
Palavras-chave: Algoritmos genéticos
Algoritmos da estimação da distribuição
Redes Bayesianas
Pesquisa local sub-estrutural
MAXSAT
Data de Defesa: 2011
Resumo: Genetic Algorithms (GAs) are stochastic optimizers usually applied to problems where the use of deterministic methods is not practical or when information about how to solve the problem is scarce. Although traditional GAs show good results in a broad range of problems, they do not take into account the dependencies that may exist among the variables of a given problem. Without respecting these links, achieving the optimum can be very hard or even impossible. Estimation of Distribution Algorithms (EDAs) are methods inspired on GAs that are able to learn the linkage between variables without providing any information about the problem structure. These methods use machine learning techniques to build a probabilistic model that captures the regularities present in the population (a set of candidate solutions for our problem). The learned model is used to generate new solutions similar to those present in the population but also with some innovation. The Substructural Local Search (SLS) is a method recently proposed that takes advantage from the model built by the EDA and performs local search in each substructure of the model, providing in the end a high quality solution. This method has shown to improve the e_ciency of the search when applied to di_erent EDAs in several arti_cial problems of bounded di_culty. In this thesis, the utility of SLS in the hierarchical Bayesian Optimization Algorithm (hBOA) (an EDA that uses Bayesian networks as probabilistic model), is investigated in the MAXSAT problem. Results show that SLS is able to improve the e_ciency of hBOA, but only on MAXSAT instances with a small number of variables. For larger instances that behavior is not observed. Additionally, the SLS execution is analyzed in order to better understand the obtained results. Finally, some observations and suggestions are exposed for an improvement of SLS.
Descrição: Dissertação de mest., Engenharia Informática, Faculdade de Ciências e Tecnologia, Univ. do Algarve, 2011
Peer review: yes
URI: http://hdl.handle.net/10400.1/2746
Designação: Mestrado em Engenharia Inform atica
Aparece nas colecções:UA01-Teses

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
thesis_Pedro_gonzalez.pdf1,62 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.