调查传播算法和蚁群算法相结合求解可满足性问题

计算机科学 ›› 2012, Vol. 39 ›› Issue (4): 227-231.

调查传播算法和蚁群算法相结合求解可满足性问题

王芙,周育人,叶立

(华南理工大学计算机科学与工程学院广州510006)

出版日期:2018-11-16 发布日期:2018-11-16

Ant Colony Algorithm Combined with Survey Propagation for Satisfiability Problem

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 布尔可满足性问题(Boolcan Satisfiability Problcm,SAT)是逻辑学的一个基本问题，也是NP-hard问题。调查传播算法((Survey Propagation,SP)是求解SAT的一种非常高效的算法，但SP在难解区域极易不收敛，或者出现错误赋值。将SP算法与蚁群算法结合，把SP算法得到的消息值应用到蚁群算法中来求解3-SAT问题，使用这些消息值引导蚁群算法求解，并在算法中加入高效的局部搜索。新算法对于SP算法不收敛的一些实例也能很快找到解。

关键词: 调查传播算法，难解区域，蚁群算法，局部搜索

Abstract: Satisfiability problem is a basic problem in logic,and also is NP-hard. Survey propagation(SP) is a very effective algorithm for this problem. However, SP tends not to converge in hard region, or gives wrong assignments to the variables. An algorithm combined with SP and ant colony optimization(ACO) was proposed. The messages calculated in SP were used in ACO as guidance to help ACO find a solution. And local search was conducted in the new algorithm.The new algorithm can quickly find solutions for some instances that SP doesn't work.

Key words: Survey propagation, Hard region, Ant colony optimization, Local search

王芙,周育人,叶立. 调查传播算法和蚁群算法相结合求解可满足性问题[J]. 计算机科学, 2012, 39(4): 227-231. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed