Application of substructural local search in the MAXSAT problem

Gonzalez, Pedro Frazão

http://hdl.handle.net/10400.1/2746

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
thesis_Pedro_gonzalez.pdf		1.58 MB	Adobe PDF	Download

Send Feedback

Authors

Gonzalez, Pedro Frazão

Advisor(s)

Lobo, Fernando

Abstract(s)

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.