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.
Backbone Extremal optimization Maximum satisfiability problem Phase transition
Guoqiang Zeng Chongwei Zheng Zhengjiang Zhang Yongzai Lu
College of Physics &Electronic Information Engineering,Wenzhou University, Wenzhou, 325035, China ;S College of Physics &Electronic Information Engineering,Wenzhou University Wenzhou, 325035, China State Key Laboratory of Industrial Control Technology &Institute of Cyber-systems and Control Zhejia
国际会议
沈阳
英文
1301-1304
2012-07-27（万方平台首次上网日期，不代表论文的发表时间）