Solving the Maximum Satisfiability Problem Using an Evolutionary Local Search Algorithm

Mohamed El Bachir Menai¹ and Mohamed Batouche²

¹Artificial Intelligence Laboratory, University of Paris 8, France

² Computer Science Department, University Mentouri of Constantine, Algeria

Abstract: The MAXimum propositional SATisfiability problem (MAXSAT) is a well known NP-hard optimization problem with many theoretical and practical applications in artificial intelligence and mathematical logic. Heuristic local search algorithms are widely recognized as the most effective approaches used to solve them. However, their performance depends both on their complexity and their tuning parameters which are controlled experimentally and remain a difficult task. Extremal Optimization (EO) is one of the simplest heuristic methods with only one free parameter, which has proved competitive with the more elaborate general-purpose method on graph partitioning and coloring. It is inspired by the dynamics of physical systems with emergent complexity and their ability to self-organize to reach an optimal adaptation state. In this paper, we propose an extremal optimization procedure for MAXSAT and consider its effectiveness by computational experiments on a benchmark of random instances. Comparative tests showed that this procedure improves significantly previous results obtained on the same benchmark with other modern local search methods like WSAT, simulated annealing and Tabu Search (TS).

Keywords: Constraint satisfaction, MAXSAT, heuristic local search, extremal optimization.

Received February 29, 2004; accepted June 30, 2004