| 求解SAT问题的改进粒子群优化算法 |
| |
| 引用本文： | 贺毅朝,刘坤起. 求解SAT问题的改进粒子群优化算法[J]. 计算机工程与设计, 2006, 27(15): 2731-2733,2758 |
| |
| 作者姓名： | 贺毅朝 刘坤起 |
| |
| 作者单位： | 石家庄经济学院,信息工程系,河北,石家庄,050031;石家庄经济学院,信息工程系,河北,石家庄,050031;中国地质大学计算机学院,湖北,武汉,430074 |
| |
| 基金项目： | 中国科学院资助项目;河北省科技攻关项目;河北省教育厅科研项目 |
| |
| 摘 要： | 利用限制哆公式的相关理论将可满足性问题（SAT）等价转换为定义在{0，1}^n上的多项式函数优化问题，并将二进制粒子群优化算法（BPSO）与局部爬山搜索策略相结合，给出了一种求解SAT问题的新算法：基于局部爬山搜索的改进二进制粒子群优化算法（简称IBPSO）．数值实验表明，对于随机产生的3-SAT问题测试实例，该算法的计算结果均优于著名的WalkSAT算法和SATI．3算法．
|
| 关 键 词： | 可满足性问题 限制性公式 合取范式 BPSO算法 爬山法 |
| 文章编号： | 1000-7024（2006）15-2731-03 |
| 收稿时间： | 2006-01-03 |
| 修稿时间： | 2006-01-03 |
Improved particle swarm optimizers for solving SAT problem |
| |
| HE Yi-chao,LIU Kun-qi. Improved particle swarm optimizers for solving SAT problem[J]. Computer Engineering and Design, 2006, 27(15): 2731-2733,2758 |
| |
| Authors: | HE Yi-chao LIU Kun-qi |
| |
| Affiliation: | 1. Department of Information Project, Shijiazhuang University of Economics, Shijiazhuang 050031, China; 2. School of Computer, China University of Geosciences, Wuhan 430074, China |
| |
| Abstract: | By using the connected theory ofrestrictive formulas, SAT problem is translated equally into the function optimization problem defined on {0,1 }^n. 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. |
| |
| Keywords: | satisfiability problem, restrictive formula conjunctive normal form BPSO algorithm hill-climbing method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
