Modified extremal optimization for the hard maximum satisfiability problem

作     者：Guo-qiang ZENG 1,Yong-zai LU 2,Wei-Jie MAO 2 (1 College of Physics & Electronic Information Engineering,Wenzhou University,Wenzhou 325035,China) (2 State Key Laboratory of Industrial Control Technology,Institute of Cyber-Systems and Control,Zhejiang University,Hangzhou 310027,China) 

作者机构：College of Physics & Electronic Information Engineering Wenzhou University State Key Laboratory of Industrial Control Technology Institute of Cyber-Systems and Control Zhejiang University 

出 版 物：《Journal of Zhejiang University-Science C(Computers and Electronics)》 (浙江大学学报C辑（计算机与电子（英文版）)

年 卷 期：2011年第12卷第7期

页      面：589-596页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China (No.61074045) the National Basic Research Program (973) of China (No.2007CB714000) the National Creative Research Groups Science Foundation of China (No.60721062) 

主　　题：Extremal optimization (EO) Evolution Probability distributions Maximum satisfiability (MAXSAT) 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) *** 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 *** results on the hard MAXSAT instances from SATLIB show that the modified algorithms are superior to the original BE-EO algorithm.