基于聚类排序选择方法求解3-SAT问题的遗传算法

GA Solution of 3-SAT based on Clustering Ranking Selection

使用聚类排序选择方法的遗传算法,加入交叉算子和变异算子求解3-SAT问题。根据适应度函数及问题本身的特性,对阈值δ进行调节,重新生成新的种群聚类,有效地抑制了算法延迟收敛的可能性及可满足性范式无解的可能性,使得与同类算法相比,在时间上有很大的改进。最后给出基本的求解算法并分析了该算法的复杂性。

In this paper, we use clustering ranking selection method for GA, by adding crossover and mutation to solve 3 - SAT. Moreover, according to the fitness function and its own characteristics, we regulate the δ to produce the new population clustering, which effectively suppresses the possibility of delayed convergence algorithm and satisfiability formula without the solution. Compared with other algorithms, great improvement has been made in regarding to the time. Finally, we give the basic solution of 3 -SAT and analyze its complexity.