论文研究求解可满足问题的改进的蚁群算法.pdf

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