关键词: SAT问题, 蚁群算法, 最大最小蚂蚁系统, 启发式信息值

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