求解SAT问题的改进粒子群优化算法

摘要

利用限制性公式的相关理论将可满足性问题(SAT)等价转换为定义在{0,1}m上的多项式函数优化问题,并将二进制粒子群优化算法(BPSO)与局部爬山搜索策略相结合,给出了一种求解SAT问题的新算法:基于局部爬山搜索的改进二进制粒子群优化算法(简称IBPSO).数值实验表明,对于随机产生的3-SAT问题测试实例,该算法的计算结果均优于著名的WalkSAT算法和SAT1.3算法.