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

基于"聚类排序选择"优化遗传算法求解SAT问题时,引入交叉算子和变异算子,并根据适应度函数及问题本身特性,调节阈值δ,生成新的种群聚类。这种遗传算法有效地抑制了算法的延迟收敛,从而保证了为可满足性公式能够快速找到一个可满足性指派。同时,在遗传算法中引入了DPLL算法,对部分变元进行消解,提高了算法的求解效率。相关的实验数据表明,本算法的性能明显优于同类算法。

A Hybrid Genetic Algorithm Based on DPLL for Solving the SAT Problem

When the Optimized Genetic Algorithm based on clustering and ranking selection is  used for the SAT problem, a crossover factor and a mutation factor are imported. Moreover, according to the fitness function and the characteristics of the related issue, threshold δ is adjusted, in order to produce a new population clustering. The algorithm has the effective suppression of delayed convergence, so the satisfiability of formula can be assigned rapidly. Meanwhile,we introduce the DPLL algorithm into the genetic algorithm. It performs the resolution to the variables, and raises the algorithm’s solution efficiency. According to the related experimental data, the performance of the algorithm is obviously better than other algorithms alike, and it has a high reliability.