网络中Steiner树问题的量子与智能优化算法研究

论文摘要

近年来随着网络和多媒体技术的飞速发展,网络多媒体服务(如视频会议、视频点播,数据分发和网络游戏等)应用成为网络应用的大势所趋,如果应用传统通信方式,它们大都需要消耗很多的网络带宽资源。为了节约带宽,提高网络中各种资源的利用率,当前比较现实的也是比较有效的方法就是使用组播技术。构建费用较小、性能较好的组播分发树成为制约组播应用的一个瓶颈。在这类问题中,以求解最小Steiner树最为典型。一般的求解Steiner树算法,首先要计算源端点到每个目的端点的路径费用等数据,然后依据这些费用信息,进行路径的合并来得到可行解。这些方法简单可行,但是重复计算较多,从而导致算法平均搜索时间较大,算法整体上效率不高。另外一类算法就是智能优化算法,如蚁群优化、粒子群优化算法等,它们都具有分布式并行性、较好的寻优能力等特点,被越来越多地应用到求解Steiner树问题,取得了较好的结果。但是,此类算法仍然存在诸如收敛速度慢、计算复杂、早熟收敛等不足之处。以量子力学为基础的量子算法在近年来快速崛起,具有高度并行性、存储容量超大、可以加速其他算法的优点。将量子的思想应用到求解Steiner树问题中,既可以提高原算法的性能,又拓宽了量子算法的应用范围。借鉴“组合优化”的思想,为了充分发挥智能优化算法与量子算法各自的优点,克服原有算法早熟收敛等不足之处,提高全局寻优能力,加快收敛速度,本文将量子算法与智能优化算法结合起来,提出了新的求解网络中Steiner树问题的方法。本文所做的主要工作是研究量子及其智能优化算法在求解网络中Steiner树的应用,具体内容如下：(1)在基本量子算法的基础上,提出了一种新的基于量子的算法来求解网络中Steiner树问题。该算法以量子比的概率幅表示其代表的图中的边被选入Steiner树的概率,之后通过观测量子比特来得到解。针对原有算法中要计算源端点到每个目的端点的路径来形成树,重复计算较多,效率不高的缺点,本算法采用直接合并代表可行解的树的方式对结果从整体上进行优化,同时用自适应的量子旋转门策略更新量子比特的相位,优化量子个体,以进化该种群。该本文算法在一般情况下能够增强全局寻优能力,并较快地加速了算法的收敛。通过仿真实验结果表明,大多数情况下,本文算法与传统算法相比,在得到更优解的同时,大大缩短了收敛时间,提高了算法的效率,尤其是当网络的拓扑规模增大时,该算法收敛速度快的优越性会变得更加明显。(2)为了使智能优化算法与量子算法发挥各自的优点,依照“组合优化”的思想,在蚁群优化算法和粒子群优化算法的基础上,结合量子算法,分别提出了量子蚁群算法和量子粒子群算法来求解Steiner树问题。其中,在量子蚁群算法中,蚂蚁看作是量子比特,并用量子比特的概率幅表示蚂蚁当前位置,用量子旋转门实现量子的进化,通过量子非门实现种群的变异；在量子粒子群算法中,将量子进化的思想引入粒子群算法,采用量子比特对粒子的当前位置进行编码,用量子选择门搜索粒子最优位置,用量子非门实现粒子位置的变异以避免早熟收敛。仿真实验结果表明,与原有的蚁群算法和粒子群算法相比,新的算法能够增强全局寻优能力,加快收敛速度,并能避免早熟收敛,有效地提高了原有算法的优化性能。当网络的拓扑规模越大时,新算法在全局寻优能力和收敛速度方面的优越性就表现得越明显。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 论文的选题意义及背景
• 1.2 国内外研究现状
• 1.3 本文研究的主要内容
• 1.4 本文的内容结构
• 第二章 量子算法基础知识
• 2.1 量子力学的基本概念
• 2.1.1 量子态及其表象
• 2.1.2 量子的叠加
• 2.1.3 量子的数学基础
• 2.2 量子比特
• 2.2.1 单量子比特
• 2.2.2 双量子比特
• 2.2.3 多量子比特
• 2.3 量子逻辑门
• 2.3.1 单比特量子门
• 2.3.2 多比特量子门
• 2.4 量子的并行计算
• 2.5 本章小结
• 第三章 量子算法在求解网络中Steiner树的应用
• 3.1 计算机网络的通信方式
• 3.1.1 单播
• 3.1.2 广播
• 3.1.3 组播
• 3.2 组播路由和Steiner树
• 3.2.1 组播网络模型
• 3.2.2 Steiner树
• 3.3 基本的量子算法
• 3.4 求解Steiner树问题的量子算法
• 3.4.1 算法的基本思想
• 3.4.2 算法的主要内容
• 3.4.3 算法步骤及描述
• 3.5 实验结果及分析
• 3.5.1 MRSIM简介
• 3.5.2 结果及分析
• 3.6 本章小结
• 第四章 量子进化算法在解Steiner树中的应用
• 4.1 量子蚁群
• 4.1.1 蚁群优化简介
• 4.1.2 量子蚁群算法
• 4.2 量子粒子群
• 4.2.1 粒子群算法简介
• 4.2.2 量子粒子群算法
• 4.3 实验结果及分析
• 4.4 本章小结
• 第五章 总结与展望
• 参考文献
• 致谢
• 攻读学位期间发表的主要学术论文目录
• 学位论文评阅及答辩情况表