计算机基础理论的研究,特别是对计算复杂性和基本算法的研究,是发展应用理论和高性能软件系统的基础。找到NP完全问题解的快速算法是计算复杂性研究的主要研究方向,布尔变量的可满足性(SAT)问题就是NP完全问题中的一个典型问题。它具有重要的理论价值和广泛的应用背景。利用融合其它算法优秀思想的混合演化算法求解SAT问题是当前设计更强大求解算法的一个趋势,本文利用经典的演化算法——遗传算法和新兴的演化算法——粒子群优化算法,来对求解SAT问题进行研究和试验。 通过分析基本遗传算法在局部搜索能力方面的不足和易陷入局部最优的问题,针对SAT问题对其加以改进,本文提出了一种改进的混合遗传算法。在改进的混合遗传算法中,融合调查传播(SP)算法思想设计了一种新的初始种群生成方法来提高群体在算法执行初期的分散多样性,融合WalkSAT算法思想设计了一种局部搜索算子来优化算法执行后期对个体进行局部搜索的能力。通过一系列实验证明,以上改进有效的改善了基本遗传算法的早熟停滞现象,提高了算法的求解性能和求解质量。 通过分析粒子群算法求解离散优化问题上的不足,本文提出了一种改进的混合粒子群算法来求解SAT问题。在改进的混合粒子群算法中,首次在粒子群算法中尝试利用量子角编码方式对SAT问题进行编码,并设计出一种新的与这种编码方式相适应的适应值函数,另外,为了对陷入局部最优的算法注入新的全局搜索能力和局部寻优能力,结合WalkSAT算法思想设计出一种新的重启操作。实验证明,通过以上的改进,使粒子群算法成功的用于求解SAT问题,与传统的二进制粒子群算法相比,求解性能和求解质量都有了一定程度的提高。