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

DOI

10.2991/iccasm.2012.332How to use a DOI?

Keywords

Backbone, Extremal optimization, Maximum satisfiability problem, Phase transition

Abstract

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.

Copyright

© 2012, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Guoqiang Zeng
AU  - Chongwei Zheng
AU  - Zhengjiang Zhang
AU  - Yongzai Lu
PY  - 2012/08
DA  - 2012/08
TI  - An Backbone Guided Extremal Optimization Method for Solving the Hard Maximum Satisfiability Problem
BT  - Proceedings of the 2012 International Conference on Computer Application and System Modeling (ICCASM 2012)
PB  - Atlantis Press
SP  - 1301
EP  - 1304
SN  - 1951-6851
UR  - https://doi.org/10.2991/iccasm.2012.332
DO  - 10.2991/iccasm.2012.332
ID  - Zeng2012/08
ER  -