Proceedings of the 2012 International Conference on Computer Application and System Modeling (ICCASM 2012)

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

Authors
Guoqiang Zeng, Chongwei Zheng, Zhengjiang Zhang, Yongzai Lu
Corresponding Author
Guoqiang Zeng
Available Online August 2012.
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)

Volume Title
Proceedings of the 2012 International Conference on Computer Application and System Modeling (ICCASM 2012)
Series
Advances in Intelligent Systems Research
Publication Date
August 2012
ISBN
978-94-91216-00-8
ISSN
1951-6851
DOI
10.2991/iccasm.2012.332How to use a DOI?
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/).

Cite this article

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  -