节点文献
求解SAT问题的改进粒子群优化算法
Improved particle swarm optimizers for solving SAT problem
【摘要】 利用限制性公式的相关理论将可满足性问题(SAT)等价转换为定义在{0,1}m上的多项式函数优化问题,并将二进制粒子群优化算法(BPSO)与局部爬山搜索策略相结合,给出了一种求解SAT问题的新算法:基于局部爬山搜索的改进二进制粒子群优化算法(简称IBPSO)。数值实验表明,对于随机产生的3-SAT问题测试实例,该算法的计算结果均优于著名的WalkSAT算法和SAT1.3算法。
【Abstract】 By using the connected theory of restrictive formulas,SAT problem is translated equally into the function optimization problem defined on {0,1}m.Then combining BPSO with local search strategy,an advanced new algorithm to solve SAT that is IBPSO algorithm bases on local Hill-climbing search is presented.The numerical experiments show that,to the random generated 3-SAT problems testing sample,the calculated results of the algorithm are all superior to the famous WalkSAT algorithm and SAT 1.3 algorithm.
【关键词】 可满足性问题；
限制性公式；
合取范式；
BPSO算法；
爬山法；
【Key words】 satisfiability problem； restrictive formula； conjunctive normal form； BPSO algorithm； hill-climbing method；
【Key words】 satisfiability problem； restrictive formula； conjunctive normal form； BPSO algorithm； hill-climbing method；
【基金】 国家自然科学基金项目(60473037);河北省科技攻关基金项目(05213567);河北省教育厅科研基金项目(2005338)
- 【文献出处】 计算机工程与设计 ,Computer Engineering and Design , 编辑部邮箱 ,2006年15期
- 【分类号】TP18
- 【被引频次】12
- 【下载频次】204