Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (3): 42-44.DOI: 10.3778/j.issn.1002-8331.2009.03.011
• 研究、探讨 • Previous Articles Next Articles
LIN Fen,ZHOU Yu-ren
Received:
Revised:
Online:
Published:
Contact:
林 奋,周育人
通讯作者:
Abstract: Satisfiability problem(SAT) is one of the NP-hard problems.In this paper,the SAT problem is transformed into a global minimize optimization problem without being constrained.According to the ant colony algorithm proposed by Dorigo M,a modified MAX-MIN Ant System for solving SAT problem is introduced,which is called MMAS-SAT.The improving algorithm introduces the construction graph for SAT,refers to the way to calculate the value of heuristic information,and indicates how to adjust the evaporation factor ρ dynamically.The numerical experiment of test problems show that the MMAS-SAT outperforms Gwsat,Walksat,Novelty and other local search algorithms,therefore the MMAS-SAT is feasible and efficient.
Key words: Satisfiability(SAT) problem, ant colony algorithms, MAX-MIN Ant System(MMAS), heuristic information
摘要: 可满足问题(SAT)是一个NP-hard问题,将SAT问题转换为无约束的离散优化(最小值)问题。并根据M Dorigo提出的蚁群算法,给出了一种求解SAT问题的新方法:改进的最大最小蚁群系统(MMAS-SAT)。在改进的算法中,给出了SAT问题的构造图,指出了启发式信息值的求法,对衰变系数进行了动态调整。测试问题的数值实验表明,采用MMAS-SAT的结果优于Gwsat、Walksat、Novelty等局部搜索算法,因此该算法是求解SAT问题的一种可行高效的算法。
关键词: SAT问题, 蚁群算法, 最大最小蚂蚁系统, 启发式信息值
LIN Fen,ZHOU Yu-ren. Modified ant colony algorithms for solving Satisfiability problem[J]. Computer Engineering and Applications, 2009, 45(3): 42-44.
林 奋,周育人. 求解可满足问题的改进的蚁群算法[J]. 计算机工程与应用, 2009, 45(3): 42-44.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2009.03.011
http://cea.ceaj.org/EN/Y2009/V45/I3/42