|
|||||
|
|
| 结合启发式算子的单变量边缘分布算法求解SAT问题 | |
| 引用本文： | 武燕,王宇平,刘小雄.结合启发式算子的单变量边缘分布算法求解SAT问题[J].计算机科学,2008,35(5):220-222. |
| 作者姓名： | 武燕 王宇平 刘小雄 |
| 作者单位： | 1. 西安电子科技大学理学院,西安,710071 2. 西安电子科技大学计算机学院,西安,710071 3. 西北工业大学自动化学院,西安,710072 |
| 摘 要： | 单变量边缘分布算法(UMDA)是一种新的进化算法,是求解复杂问题的一种有效算法.根据SAT问题的特点,本文提出了一种求解SAT问题的改进单变量边缘分布算法(HeUMDASAT),该算法结合SAT问题本身固有的结构信息与当前群体的优秀解所提供的全局信息,构造了一个新的启发算子,并将此算子结合到单变量边缘分布算法中.此算子不同于随机搜索算子,由其产生的个体可以使得算法跳出局部最优并探索新的潜在区域,并且加快算法的收敛速度.用SATLIB库中的标准SAT问题对HeUMDASAT算法进行测试,实验结果表明该算法在求解速度和成功率方面都有明显的改善. |
| 关 键 词： | 单变量边缘分布算法 启发算子 SAT问题 |
Bayesian Optimization Algorithm for SAT Problem Incorporating Heuristic Operator |
|
| WU Yan,WANG Yu-ping,LIU Xiao-xiong.Bayesian Optimization Algorithm for SAT Problem Incorporating Heuristic Operator[J].Computer Science,2008,35(5):220-222. | |
| Authors: | WU Yan WANG Yu-ping LIU Xiao-xiong |
| Affiliation: | WU Yan~1 WANG Yu-ping~2 LIU Xiao-xiong~3 (School of Science Xidian University Xi'an 710071,China)~1(School of computer Science , Technology,Xidian University,Xi'an 710071,China)~2(College of Automation,Northwestern Polytechnical University,Xi'an 710072,China)~3 |
| Abstract: | Univariate marginal distribution algorithm(UMDA)is a new evolutionary algorithm and is an efficient algo- rithm for complicate problem.According to the characteristics of SAT problem,an improved UMDA for solving SAT problem(HeUMDASAT)is proposed in this paper.A new heuristic operator is presented by combing the structure in- formation of SAT problem with the global information extracted from promising individuals of current population.Dif- ferent from the stochastic searching operator,the heuristic operator... |
| Keywords: | Univariate marginal distribution algorithm(UMDA) Heuristic operator Satisfiability problem(SAT) |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机科学》下载全文 | |
