基于混合蚁群遗传算法的SAT问题求解

Solving the SAT Problem Based on Hybrid Ant Colony and Genetic Algorithm

根据SAT问题的特点,通过分析传统蚁群算法和遗传算法在求解SAT问题上的不足,提出一种基于混合蚁群遗传算法的SAT问题求解方法。给出一种新的初始解的生成方式;在迭代过程中,根据较优解的累积信息提出进化算子;利用当前得到的最优解,通过改变不满足子句中文字的取值,增加变异算子。最后选取标准测试集中的20个实例对算法进行测试,实验结果表明:改进后的算法通常仅通过较少次数的迭代就能找到解,能够有效避免蚁群算法和遗传算法过早收敛的缺点,具有较强的寻优能力。

According to the characteristics of the satisfiability problem （SAT）, in the analysis of the weakness of the traditional ant colony algorithm and genetic algorithm in solving the SAT problem, we put forward a new kind of solving method of SAT problem based on hybrid ant colo- ny and genetic algorithm （HAG）. Improvements are given in the following aspects. Firstly a new method for generating initial solutions is proposed. Then an evolution operator is presented depending on the accumulated information of Meanwhile a mutation operator is added by c the suboptimal solutions in the process of iteration. hanging literal value in the unsatisfied clause under the condition of current optimal solution. Finally 20 instances are selected from benchmarking sets to test the algorithm. The experimental results showed that in most cases our algorithm has better global searching performance and is able to find the optimal solution through only a few iterations, which has high searching performance and can effectively avoid the premature convergence of ant colony algorithm and genetic algorithm.