Meta-aprendizagem aplicada a problemas de máxima satisfabilidade

Abstract

Meta-learning has been used with success in optimization problems, like the Traveling Salesman Problem (TSP) and the Maximum Satisfability Problem (MaxSAT). The latter is considered NP-Hard while also being relevant for academic and industrial problems. However, most of the research on the MaxSAT problem focuses of exact solution methods. Due to the need of generating good solutions on a limited time frame, this work considers the use of meta-heuristics. A meta-learning framework for meta-heuristic selection is also proposed for the MaxSAT problem, including a new representation based on graphs, new meta-features derived from this representation, the definition of machine learning mechanisms based on previous experience. Experiments show that the proposed outline is effective for selection of meta-heuristics and parameters for MaxSAT. The new metafeatures derived are shown to be as good as the current state of the art. The graph meta-features proposed can be applied to other problems on the near future.