量子粒子群算法及其在贝叶斯网络结构学习的应用地研究论文.docx

Quantum-behaved Particle Swarm OptimizationAlgorithm and Applying It on Learning BayesianNetworksThesis Submitted to Nanjing University of Posts andTelecommunications for the Degree ofMaster of EngineeringByWang YingyingSupervisor: Prof. Li FeiFebruary 2014万方数据南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。研究生签名：_____________ 日期：____________南京邮电大学学位论文使用授权声明本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索；可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院办理。涉密学位论文在解密后适用本授权书。研究生签名：____________ 导师签名：____________ 日期：_____________万方数据摘要对贝叶斯网络结构进行学习是一个 NP 难解问题，并且当数据集比较大时用经典算法如粒子群算法和爬山算法容易陷入局部最优值，K2 算法要已知节点的次序，最大加权生成树算法寻优能力比较差。因此，本文提出一种新的方法对贝叶斯网络进行结构学习—离散的基于二进制编码的量子粒子群算法，采用了贝叶斯准则打分函数，并在学习的过程中引入了去环的操作，提高了有哪些信誉好的足球投注网站网络的准确性。在研究经典贝叶斯网络的基础上，引入了量子计算的概念，研究了量子贝叶斯网络及其结构。提出一种新的量子贝叶斯网络，证明其可以表示为概率幅的乘积，降低量子图模型的运算复杂度，主要工作如下：第一，研究了贝叶斯网络的结构，分析了一个贝叶斯网络模型实例结构及其条件概率分布。在此基础上，研究了贝叶斯网络的结构学习。重点研究了基于依赖分析的贝叶斯网络结构学习和基于评分有哪些信誉好的足球投注网站的贝叶斯网络结构学习，分析了现有一些经典算法比如 K2 算法和最大加权生成树（MWST）算法的优势和不足，并运用这两种算法仿真得到了贝叶斯网络的结构。第二，研究了两种主要的量子粒子群算法，基于量子位概率幅的粒子群算法 QPSEA 与基于量子力学波函数的 QPSO 算法，并以八个标准测试函数的仿真实验结果说明 QPSO 算法性能较好。针对贝叶斯网络是离散个体的特点，提出一种改进的量子粒子群算法-离散二进制编码量子粒子群算法作为贝叶斯网络结构的学习算法。第三，针对贝叶斯网络结构学习的特点，运用提出的改进算法对贝叶斯网络结构进行学习。为了提高结构学习的准确性，提出一种新的去环操作。并将本文算法学习得到的网络结构与粒子群算法、K2 算法和 MWST 算法学习得到的网络结构进行比较，证明了本文算法能够学习出最优的贝叶斯网络结构，并且相比于其余三种算法拥有较高的学习效率和准确性。第四，将经典贝叶斯网络和量子计算理论相结合，研究了两种类型的量子贝叶斯网络，并对其性质进行研究。为了更直观地描述量子贝叶斯网络，降低计算复杂度，提出了一种新的量子贝叶斯网络结构。并证明了如何给量子贝叶斯网络拓扑结构的每个节点分配概率幅度。类比于经典贝叶斯网络，证明了量子贝叶斯网络也可以表示成概率幅度的乘积。最后给出了量子贝叶斯网络将来的应用方向。关键词:贝叶斯网络、结构学习、量子粒子群算法、量子贝叶斯网络I万方数据AbstractSince learning Bayesian networks from data is a NP-hard problem, especially when the set ofdata is big, the process of learning Bayesian networks structure is prone to fall into prematureconvergence and obtain a local optimal Bayesian networks under Particle Swarm Optimizationalgorithm and H