可满足性问题(即SAT问题)是第一个NP完全问题,这一个典型且著名的判定问题早在1971年的时候就已经被S.A.Cook证明出来。SAT问题不仅是逻辑学的一个基本核心问题,在计算机的理论与应用方面、人工智能领域、自动化推理领域等方面都有着举足轻重的作用。遗传算法作为不完备算法中比较典型的一种智能算法,一直因其自我进化的特点被广泛的用在求解SAT问题上,目前是比较有效的一种方法。本文根据SAT问题的特点,通过分析传统遗传算法和蚁群算法在求解SAT问题上的不足,提出了一种新的基于混合蚁群遗传算法的SAT问题求解方法。与一般遗传算法相比,本文在如下几个方面进行了改进:改进了原有遗传算法初始解的生成方式,用以提高初始解的质量;改进了变异算子,这种变异不再是盲目的变异,而是根据不满足子句中文字的分布情况来决定变异的方向,强化了搜索最优解的能力;在遗传算法的基础上融入了蚁群算法的思想,利用迭代过程中累积的信息,增加了进化算子,并且这种进化是单方向的,即只接受朝着好的方向进化,提高了下一代解的整体质量。最后通过实验结果表明:该算法大部分情况下仅通过迭代较少的次数就能找到解,能够有效避免蚁群算法和遗传算法过早收敛的缺点,具有较强的寻优能力。但是,注意到初始解集往往对最终的寻优结果存在较大的影响,一个质量不高的初始解集就意味着程序迭代更多的次数,甚至容易陷入局部最优而根本跳不出来。为了避免出现这类情况,本文随后提出了多种群遗传算法,即同时生成多个种群,替代原有的单一种群,各个种群即独立遗传进化又相互交流协作,当有某个种群找到真解时,迭代结束。并通过大量实例测试证明,多种群遗传算法的寻优能力和求解效率也要明显优于一般蚁群算法和遗传算法。最后,本文中改进的两种算法都是通过MATLAB算法实现,在标准测试库中选取了大量测试实例进行试验,实验结果证明本论文提出的两种改进算法是切实可行对的。