求解可满足问题的改进的蚁群算法

• 作者: 周育人 林奋
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: SAT问题 蚁群算法 最大最小蚂蚁系统 启发式信息值
• 年，卷（期）: 2009,（3）
• 所属期刊栏目: 研究、探讨
• 页码范围: 42-44,54
• 页数: 4页
• 分类号: TP301.6
• 字数: 5367字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.03.011

摘要

可满足问题(SAT)是一个NP-hard问题,将SAT问题转换为无约束的离散优化(最小值)问题.并根据M Dorigo提出的蚁群算法,给出了一种求解SAT问题的新方法:改进的最大最小蚁群系统(MMAS-SAT).在改进的算法中,给出了sAT问题的构造图,指出了启发式信息值的求法,对衰变系数进行了动态调整.测试问题的数值实验表明,采用MMAS-SAT的结果优于Gwsat、Walksat、Novelty等局部搜索算法,因此该算法是求解SAT问题的一种可行高效的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周育人	华南理工大学计算机科学与工程学院	26	561	9.0	23.0
2	林奋	华南理工大学计算机科学与工程学院	1	9	1.0	1.0