计算机应用 ›› 2013, Vol. 33 ›› Issue (06): 1595-1603.DOI: 10.3724/SP.J.1087.2013.01595

• 人工智能 • 上一篇    下一篇

基于拓扑序列和量子遗传算法的贝叶斯网结构学习

赵学武1,刘广亮1,程新党1,冀俊忠2   

  1. 1. 南阳师范学院 软件学院,河南 南阳 473061
    2. 北京工业大学 计算机学院,北京100124
  • 收稿日期:2012-12-10 修回日期:2013-02-25 出版日期:2013-06-01 发布日期:2013-06-05
  • 通讯作者: 赵学武
  • 作者简介:赵学武(1983-),男,河南南阳人,助教,硕士,主要研究方向:群集智能、数据挖掘;刘广亮(1978-),男,安徽阜阳人,讲师,硕士,主要研究方向:智能信息处理、网络安全;程新党(1976-),男,河南南阳人,副教授,硕士,主要研究方向:互联网技术;冀俊忠(1969-),男,山西晋中人,教授,博士生导师,主要研究方向:机器学习、Web智能。
  • 基金资助:

    河南省基础与前沿技术研究计划项目(122300410111);南阳师范学院青年项目(QN2010010)

Bayesian network structure learning algorithm based on topological order and quantum genetic algorithm

ZHAO Xuewu1,LIU Guangliang1,CHENG Xindang1,JI Junzhong2   

  1. 1. School of Software, Nanyang Normal University,Nanyang Henan 473061,China
    2. College of Computer Science and Technology, Beijing University of Technology, Beijing 100124,China
  • Received:2012-12-10 Revised:2013-02-25 Online:2013-06-05 Published:2013-06-01
  • Contact: ZHAO Xuewu

摘要: 贝叶斯网是处理不确定性问题知识表示和推理的最重要的理论模型之一,其结构学习是目前研究的一个热点。提出了一种基于拓扑序列和量子遗传算法的贝叶斯网结构学习算法,新算法首先利用量子信息的丰富性和量子计算的并行性,设计出基于量子染色体的拓扑序列生成策略提高了搜索效率,并为K2算法学得高质量的贝叶斯网结构提供了保障;然后采用带上下界的自适应量子变异策略,增强了种群的多样性,提高了算法的搜索能力。实验结果表明,与已有的一些算法相比,新算法不仅能获得较高质量的解,而且还有着较快的收敛速度。

关键词: 贝叶斯网, 结构学习, 量子遗传算法, K2算法, 拓扑序列, 量子计算

Abstract: Bayesian network is one of the most important theoretical models for the representation and reasoning of uncertainty. At present, its structure learning has become a focus of study. In this paper, a Bayesian network structure learning algorithm was developed, which was based on topological order and quantum genetic algorithm. With the richness of the quantum information and the parallelism of quantum computation, this paper designed generator strategy of topological order based on a quantum chromosome to improve not only the efficiency of search, but also the quality of Bayesian network structure. And then by using self-adaptive quantum mutation strategy with upper-lower limit, the diversity of the population was increased, so that the search performance of the new algorithm was improved. Compared to some existing algorithms, the experimental results show that the new algorithm not only searches higher quality Bayesian structure, but also has a quicker convergence rate.

Key words: Bayesian network, structure learning, quantum genetic algorithm, K2 algorithm, topological order, quantum computing

中图分类号: