进化非选择算法是通过借鉴生物免疫进化机制与免疫非选择机制而提出的,具有较好的全局搜索能力。可满足性问题是六个基本的NP完全问题之一,其他NP完全问题均可在多项式时间内转换为可满足性问题。因此,SAT问题具有重要的研究价值。本文旨在分析进化非选择算法用于可满足性问题求解时的性能,并与传统的启发式翻转方法相结合,以设计高效的可满足性问题求解算法。具体工作包括以下几个方面:(1)从实验角度分析了非选择在求解可满足性问题时的作用。大量的实验结果表明,非选择在求解可满足性问题时具有协助算法跳出局部最优的作用。同时,实验结果也表明,仅仅依靠非选择并不能取得理想的结果,需要考虑其他启发式技术的加入,以增强局部搜索能力,从而进一步提高算法的求解性能。(2)提出了用于求解可满足性问题的混合算法HENSA-SAT。HENSA-SAT在进化非选择算法的基础上结合了传统的启发式翻转方法,一方面通过非选择协助算法跳出局部最优,另一方面通过启发式翻转方法提高算法的局部寻优能力。实验结果表明,HENSA-SAT在求解可满足性问题,尤其是在求解大规模可满足性问题时,与当前代表性算法GASAT相比具有较好的性能。同时,通过实验对HENSA-SAT算法的参数设置及非选择在协助算法跳出局部最优方面的作用进行了分析。总的来说,本文对非选择在求解可满足性问题时的作用作了具体分析,提出了用于求解可满足性问题的混合算法HENSA-SAT,不仅对可满足性问题本身的求解有参考价值,而且在设计用于其他约束满足及组合优化问题的进化非选择算法时有一定的指导意义。