A Multistage Optimization Method based on WALKSAT and Clustering for the Hard MAX-SAT Problems

摘要：

It is widely recognized that WALKSAT is the one of the most effective local search algorithm for the satisfiability (SAT) and maximum satisfiability (MAX-SAT) problems. Inspired by the idea of population learning the large-scale structure of the landscape, this paper presents a multistage optimization method called MS-WALKSAT, which is based on WALKSAT and clustering. The experimental results on a variety of large and hard MAX-SAT problem instances have shown the MS-WALKSAT provides better performance than most of the reported algorithms.

关键词： Multistage optimization WALKSAT Clustering Maximum satisfiability problems

作者: ZENG Guoqiang ZHANG Zhengjiang LU Yongzai DAI Yuxing ZHENG Chongwei

作者单位: College of Physics &Electronic Information Engineering, Wenzhou University, Wenzhou, 325035, China State Key Laboratory of Industrial Control Technology &Institute of Cyber-Systems and Control,Zhejia

会议类型: 国际会议

会议名称: The 31st Chinese Control Conference(第三十一届中国控制会议)

会议地点: 合肥

会议语种:英文

页码: 2358-2361

在线出版日期: 2012-07-01（万方平台首次上网日期，不代表论文的发表时间）