摘要: SAT问题是计算科学中最基础的问题之一，大部分组合逻辑问题都可以归约求解SAT问题上面来，是非常具有理论研究价值和实际应用潜力的问题。对于一个布尔公式，如果存在一组变量赋值使得该公式是可以满足的，那么可以将公式的求解转化为等效的可满足性... 展开 SAT问题是计算科学中最基础的问题之一，大部分组合逻辑问题都可以归约求解SAT问题上面来，是非常具有理论研究价值和实际应用潜力的问题。对于一个布尔公式，如果存在一组变量赋值使得该公式是可以满足的，那么可以将公式的求解转化为等效的可满足性问题(Satisfibility)，自从遗传算法诞生以来，由于其盲搜索特性，被广泛地运用到组合优化等领域。但是传统的遗传算法求解SAT问题存在容易陷入早熟、搜索效率不高等不足。本文将家族谱系树的概念引入遗传算法中，提出了三种改进的遗传算子—greedy交叉操作、随机游走交叉操作以及子句变量惩罚交叉操作算子求解SAT问题，有效提高了求解成功率和收敛速度。遗传算法同其他局部搜索算法一样，不能判定 SAT问题是否存在解。 遗传算法中，种群过早收敛的主要原因是遗传算子的成熟化效应。在一个封闭的种群中，个体只能与种群内的个体交流信息，种群内部个体之间充分共享信息的同时，也会带来趋同化的问题。通过对全局搜索求解器zChaff、局部搜索求解算法 WalkSAT等的研究，本文首先提出了在交叉算子中结合局部搜索算法及基于子句变量的惩罚策略。通过引导基因的交流，使得种群既能保持多样性，又能提高遗传算法的效率。其次，基于种群的独岛模型，模拟生物演化过程中家族谱系树的概念，把种群划分成更具社会学意义的家族，提出一种基于谱系树的改进遗传算法。其主要思想是，把种群细分为较小的家族，每个家族都有各自的演化算子，在每一次迭代后，家族之间的个体成员通过联姻的方式进行结合，从而产生出比传统的交叉算子更多样、有潜力的后代个体。 最后，利用SATLIB库中的标准SAT问题对基于谱系树的遗传算法进行了测试并与经典的局部搜索算法 WalkSAT进行了比较。结果表明，基于谱系树的遗传算法明显改善了求解速度、成功率和求解规模等指标，其加速比最高为22倍，成功率最高提升49%。 收起