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
Download:   PDF(196KB)
Export: BibTeX | EndNote (RIS)      

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     
Received: 09 September 2010      Published: 04 July 2011
CLC:  TP18  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Guo-qiang Zeng
Yong-zai Lu
Wei-Jie Mao
Cite this article:

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.

URL:

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


Modified extremal optimization for the hard maximum satisfiability problem

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 
[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] Shafqat Ullah Khan, Ijaz Mansoor Qureshi, Fawad Zaman, Wasim Khan. Detecting faulty sensors in an array using symmetrical structure and cultural algorithm hybridized with differential evolution[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 235-245.
[4] Jun-hong Zhang, Yu Liu. Application of complete ensemble intrinsic time-scale decomposition and least-square SVM optimized using hybrid DE and PSO to fault diagnosis of diesel engines[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 272-286.
[5] 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.
[6] Zi-wu Ren, Zhen-hua Wang, Li-ning Sun. A hybrid biogeography-based optimization method for the inverse kinematics problem of an 8-DOF redundant humanoid manipulator[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(7): 607-616.
[7] Zhen-ming Yuan, Chi Huang, Xiao-yan Sun, Xing-xing Li, Dong-rong Xu. A microblog recommendation algorithm based on social tagging and a temporal interest evolution model[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(7): 532-540.
[8] Tahir Nadeem Malik, Salman Zafar, Saaqib Haroon. An improved chaotic hybrid differential evolution for the short-term hydrothermal scheduling problem considering practical constraints[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(5): 404-417.
[9] Xiao-dong Tan, Jian-lu Luo, Qing Li, Bing Lu, Jing Qiu. Fault evolution-test dependency modeling for mechanical systems[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(10): 848-857.
[10] De-xuan Zou, Li-qun Gao, Steven Li. Volterra filter modeling of a nonlinear discrete-time system based on a ranked differential evolution algorithm[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(8): 687-696.
[11] 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.
[12] 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.
[13] 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.
[14] Bo-yang Qu, Ponnuthurai-Nagaratnam Suganthan. Multi-objective differential evolution with diversity enhancement[J]. Front. Inform. Technol. Electron. Eng., 2010, 11(7): 538-543.
[15] 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.