作为经典的NP难度问题,最大可满足性问题(Max-SAT)是理论计算机科学的核心问题之一。现实生活中许多组合优化问题都可以转化成Max-SAT问题,如电路规划、车辆调度和神经网络优化等问题。对于Max-SAT问题求解算法的研究有着重要的理论意义和实际的应用价值。Max-SAT问题的求解算法分为精确算法和启发式算法。其中精确算法能够搜索整个求解空间从而给出全局最优解,但是理论上的算法时间复杂度是指数级的,因而不适合短时间内求解大规模算例;而启发式算法可以在较短的时间内给出近似全局最优解,这对于求解需要快速响应的问题是十分占据优势的。本文通过对Max-SAT问题的研究,提出了一种新的基于种群演化的Max-SAT求解算法。设计用于求解Max-SAT问题的基于对立学习的种群演化算法框架,基于对立学习的种群同时考虑候选个体及对立个体,从而扩展种群的多样性。提出结合禁忌和结合路径重连的两种局部搜索算法。在禁忌搜索算法中,采用双重禁忌策略,不仅禁忌搜索过程中变元的翻转选择,同时限制搜索解的选择;在路径重连算法中,采用双重对立搜索,不仅从初始解搜索到目标解,同时从目标解搜索到初始解。测试使用2016年Max-SAT国际竞赛中的随机组的454个算例和人工构造组的402个算例,并实验对比提出的优化策略对算法的影响。将优化的算法与目前文献中表现最好的几个算法进行了对比实验,实验结果表明,所提出算法的最优解求解数目与目前最优的算法相近,而且所提算法的求解速度要快于目前最优算法的求解速度。