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

关键词：sat问题 遗传算法 聚类排序选择 

单位：贵州大学计算机科学与信息学院 贵州贵阳550025