An Backbone Guided Extremal Optimization Method for Solving the Hard Maximum Satisfiability Problem

The original Extremal Optimization (EO) algorithm and its modified versions have been successfully applied to a variety of NP-hard optimization problems. However, almost all existing EO-based algorithms have overlooked the inherent structural properties behind the optimization problems, e.g., the backbone information. This paper presents a novel stochastic local search method called Backbone Guided Extremal Optimization (BGEO) to solve the hard maximum satisfiability (MAX-SAT) problem, one of typical NP-hard problems. The key idea behind the proposed method is to incorporate the backbone information into a recent developed optimization algorithm termed extremal optimization (EO) to guide the entire search process approach the optimal solutions. The superiority of BGEO to the reported BE-EEO algorithm without backbone information is demonstrated by the experimental results on the hard Max-SAT instances. Keywords-Backbone, Extremal optimization, Maximum satisfiability problem, Phase transition