A Bose-Einstein Extremal Optimization Method for Solving Real-World Instances of Maximum Satisfiability

摘要

Satisfiability problems are of great interest to combinatorial optimization as a model for several constraint satisfaction problems. Stochastic local search methods have been increasingly applied to solve them and several studies have shown that providing interesting initial solutions to the search process can be quite effective. In this paper we describe a new method, called Bose-Einstein Extremal Optimization (BE-EO), for solving the maximum satisfiability problem. Under the framework of Extremal Optimization, a recently introduced meta-heuristic for hard optimization problems, we use Bose-Einstein probability distribution rather than the traditional uniform one to sample initial solutions. Experiments were conducted on hard real-world instances of MAXSAT from graph coloring and time tabling problems and the preliminary results show good prospects of this new approach.