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

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

Modified ant colony algorithms for solving Satisfiability problem

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.