Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2011, Vol. 12 Issue (7): 589-596    DOI: 10.1631/jzus.C1000313
    
Modified extremal optimization for the hard maximum satisfiability problem
Guo-qiang Zeng*,1, Yong-zai Lu2, Wei-Jie Mao2
College of Physics & Electronic Information Engineering, Wenzhou University, Wenzhou 325035, China, State Key Laboratory of Industrial Control Technology, Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, China
Modified extremal optimization for the hard maximum satisfiability problem
Guo-qiang Zeng*,1, Yong-zai Lu2, Wei-Jie Mao2
College of Physics & Electronic Information Engineering, Wenzhou University, Wenzhou 325035, China, State Key Laboratory of Industrial Control Technology, Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, China
 全文: PDF(196 KB)  
摘要： Based on our recent study on probability distributions for evolution in extremal optimization (EO), we propose a modified framework called EOSAT to approximate ground states of the hard maximum satisfiability (MAXSAT) problem, a generalized version of the satisfiability (SAT) problem. The basic idea behind EOSAT is to generalize the evolutionary probability distribution in the Bose-Einstein-EO (BE-EO) algorithm, competing with other popular algorithms such as simulated annealing and WALKSAT. Experimental results on the hard MAXSAT instances from SATLIB show that the modified algorithms are superior to the original BE-EO algorithm.
关键词： Extremal optimization (EO);  Evolution;  Probability distributions;  Maximum satisfiability (MAXSAT) problem    
Abstract: Based on our recent study on probability distributions for evolution in extremal optimization (EO), we propose a modified framework called EOSAT to approximate ground states of the hard maximum satisfiability (MAXSAT) problem, a generalized version of the satisfiability (SAT) problem. The basic idea behind EOSAT is to generalize the evolutionary probability distribution in the Bose-Einstein-EO (BE-EO) algorithm, competing with other popular algorithms such as simulated annealing and WALKSAT. Experimental results on the hard MAXSAT instances from SATLIB show that the modified algorithms are superior to the original BE-EO algorithm.
Key words: Extremal optimization (EO)    Evolution    Probability distributions    Maximum satisfiability (MAXSAT) problem
收稿日期: 2010-09-09 出版日期: 2011-07-04
CLC:  TP18  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Guo-qiang Zeng
Yong-zai Lu
Wei-Jie Mao

引用本文:

Guo-qiang Zeng, Yong-zai Lu, Wei-Jie Mao. Modified extremal optimization for the hard maximum satisfiability problem. Front. Inform. Technol. Electron. Eng., 2011, 12(7): 589-596.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C1000313    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2011/V12/I7/589

[1] Huan-feng PENG, Zhi-qiu HUANG, Lin-yuan LIU, Yong LI, Da-juan FAN, Yu-qing WANG. Preserving privacy information flow security in composite service evolution[J]. Front. Inform. Technol. Electron. Eng., 2018, 19(5): 626-638.
[2] Bo YU, Ying FANG, Qiang YANG, Yong TANG, Liu LIU. A survey of malware behavior description and analysis[J]. Front. Inform. Technol. Electron. Eng., 2018, 19(5): 583-603.
[3] Hou-kui ZHOU, Hui-min YU, Roland HU. Topic discovery and evolution in scientific literature based on content and citations[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(10): 1511-1524.
[4] Lin-jun Fan, Yun-xiang Ling, Xing-tao Zhang, Jun Tang. Quantitative evaluation of model consistency evolution in compositional service-oriented simulation using a connected hyper-digraph[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(1): 1-12.
[5] Xiao-hong Tan, Rui-min Shen, Yan Wang. Personalized course generation and evolution based on genetic algorithms[J]. Front. Inform. Technol. Electron. Eng., 2012, 13(12): 909-917.
[6] Peng Chen, Yong-zai Lu. Extremal optimization for optimizing kernel function and its parameters in support vector regression[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(4): 297-306.
[7] Bo-yang Qu, Ponnuthurai-Nagaratnam Suganthan. Multi-objective differential evolution with diversity enhancement[J]. Front. Inform. Technol. Electron. Eng., 2010, 11(7): 538-543.
[8] Wei Chen, Chun Chen, Li-jun Zhang, Can Wang, Jia-jun Bu. Online detection of bursty events and their evolution in news streams[J]. Front. Inform. Technol. Electron. Eng., 2010, 11(5): 340-355.
[9] Cheng-gang Cui, Yan-jun Li, Tie-jun Wu. A relative feasibility degree based approach for constrained optimization problems[J]. Front. Inform. Technol. Electron. Eng., 2010, 11(4): 249-260.
[10] Jian Bao, Yu Chen, Jin-shou Yu. A regeneratable dynamic differential evolution algorithm for neural networks with integer weights[J]. Front. Inform. Technol. Electron. Eng., 2010, 11(12): 939-947.