粒子群优化算法在MAX-SAT上的应用研究

摘要

命题逻辑中的可满足性问题(SAT)是判断给定的命题公式是否存在模型的问题。SAT问题是第一个被证明是NP完全的问题，在理论计算机研究领域中具有非常重要的地位。MAX-SAT是SAT问题的一种最优化形式的变形。目前针对MAX-SAT的不完全算法中，元启发式算法的研究相对比较活跃。粒子群优化算法(PSO)作为一种群体智能算法，具有简单、高效的特点，在连续优化问题上有非常广泛的应用，但是在离散域上的组合优化问题应用得很少，特别在MAX-SAT问题上的研究还是一片空白。 本文首先对MAX-SAT问题上的局部搜索算法和元启发式算法的研究现状做了比较全面的介绍。在分析粒子群算法和MAX-SAT问题特点后，引入粒子群的模糊化和量子化模型，提出相应的解决算法QtPSO和FuzzyPSO，并与经典遗传算法进行比较分析。 随后本文在重新定义粒子运动方式后提出一种新的算法PSOSAT。在粒子速度低且稳定时，算法表现为局部搜索形式，在收敛速度和求解质量上有不错的表现。接着针对PSOSAT提出了相应的改进策略，并在混合禁忌搜索后，与当前流行的一些局部搜索算法进行全面的比较分析。 最后本文从并行化角度讨论提高性能的方法，针对PSOSAT算法提出独立式、合作式和分治式三种并行化策略。 在实验结果上，本文中的FuzzyPSO在收敛速度和寻解质量都明显优于经典的遗传算法。同时，在随机实例上PSOSAT相比其他一些局部搜索算法也有相对优越的寻解能力。

目录

文摘

英文文摘

第1章引言

第2章MAX-SAT及其不完全算法

第3章粒子群优化算法

第4章离散域上的粒子群算法

第5章PSOSAT算法

第6章并行策略研究

第7章总结与展望

参考文献

附录A实验环境

致谢

原创性声明