Efficient and Experimental Meta-heuristics for MAX-SAT Problems

摘要

Many problems in combinatorial optimization are NP-Hard. This has forced researchers to explore meta-heuristic techniques for dealing with this class of complex problems and finding an acceptable solution in reasonable time. The satisfiability problem, SAT, is studied by a great number of researchers the three last decades. Its wide application to the domain of AI in automatic reasoning and problem solving for instance and other domains like VLSI and graph theory motivates the huge interest shown for this problem. In this paper, tabu search, scatter search, genetic algorithms and memetic evolutionary meta-heuristics are studied for the NP-Complete satisfiability problems, in particular for its optimization version namely MAX-SAT. Experiments comparing the proposed approaches for solving MAX-SAT problems are represented. The empirical tests are performed on DIMACS benchmark instances.