量子遗传算法的改进研究及在路由选择问题中的应用

摘要

量子遗传算法是将量子计算与遗传算法相结合而形成的一种混合遗传算法，它弥补了传统遗传算法的某些不足；利用量子计算的一些概念和理论，如量子位、量子叠加态等，使用量子比特编码染色体，这种概率幅表示可以使一个量子染色体同时表达多个状态的信息，用量子门对叠加态的作用作为进化操作，能很好地保持种群多样性和避免选择压力问题，而且当前最优个体的信息能够很容易用来引导变异，使得种群以大概率向着优良模式进化，从而实现目标的优化求解。 在量子遗传算法被提出以后，由于量子算法的内在并行性，在许多领域的应用都获得了成功；人们也相继提出了许多改进算法。本文在已有研究的基础上，主要做了以下研究工作： 1.进一步改进了量子遗传算法的收敛性能，提出了一种改进的混合量子遗传算法(An Improved Hybrid Quantum Genetic Algorithm，IHQGA)，该算法在量子个体上实施量子交叉，这一操作有利于保留相对较好的基因段；采用量子比特相位法更新量子门和自适应调整搜索网格的策略；引入拟Newton算法进行局部搜索操作，使得种群的多样性强，解的收敛精度高，收敛速度快；通过复杂函数测试标明此算法的优化质量和效率都强于传统遗传算法和量子遗传算法。 2.将量子遗传算法用在组合优化问题中，提出了一种基于改进量子遗传算法的QoS组播路由算法，该算法通过量子非门进行量子变异操作阻止未成熟收敛和提高算法的全局搜索能力；采用量子比特相位法更新量子门策略保持种群的多样性；使用最小代价组播树算法(简称KMB算法，由Kou Markowsky和Berman提出的)进行受约束最小Steiner树的生成，通过仿真实验标明，此算法在种群规模较小、迭代次数较少的情况下就可以收敛到最优解，该算法的优化质量和效率都强于传统遗传算法和量子遗传算法。 量子遗传算法将量子机制引入到常规遗传算法中，具有收敛速度快和全局寻优能力强的特点，这将使得它有望获得更广泛的关注和应用。本文对量子遗传算法改进与应用研究，进一步提高了算法的性能，拓展了算法的应用领域，对丰富和完善该算法起到一定的促进作用。

目录

文摘

英文文摘

声明

第一章绪论

1.1课题的研究背景

1.2本文创新点

1.3本文结构及主要内容

第二章量子计算

2.1量子计算相关概念

2.1.1量子位

2.1.2多量子位

2.1.3量子逻辑门

2.2量子计算的特性

2.2.1状态叠加特性

2.2.2状态的相干特性

2.2.3状态的纠缠特性

2.2.4量子并行特性

2.3基本量子算法

2.3.1 Deutsch问题

2.3.2 Grover量子搜索算法

2.4本章小结

第三章遗传算法

3.1遗传算法概述

3.2遗传算法产生与发展

3.3遗传算法的构成要素

3.3.1编码技术

2.3.2适应度函数

3.3.3遗传操作

3.3.4遗传参数

3.4遗传算法的数学基础

3.4.1模式定理

3.4.2遗传算法收敛判据

3.5遗传算法的特点

3.5.1遗传算法的优点

3.5.2遗传算法的缺点

3.6本章小结

第四章量子遗传算法及改进研究

4.1量子遗传算法的提出

4.2量子遗传算法的基本概念

4.2.1量子比特

4.2.2量子染色体

4.2.3量子交叉

4.2.4量子变异

4.3量子遗传算法

4.3.1量子遗传算法流程

4.3.2量子遗传算法的研究综述

4.4量子遗传算法的改进研究

4.4.1问题的提出

4.4.2改进量子遗传算法的设计

4.4.3改进的混合量子遗传算法流程

4.4.4算法性能测试

4.5本章小结

第五章基于改进量子遗传算法的QOS组播路由选择算法

5.1引言

5.2 QoS组播路由模型

5.3基于量子遗传算法的QoS组播路由算法

5.3.1网络结构的简化处理

5.3.2染色体的量子比特编码

5.3.3对初始种群进行测量

5.3.4适应度函数

5.3.5 KMB算法

5.3.6变异策略

5.3.7 QoS-IQGA算法流程

5.3.8 QoS-IQGA算法时间复杂度分析

5.4仿真实验与比较

5.4.1比较算法

5.4.2网络拓扑图的生成

5.4.3算法实现及实验比较

5.5本章小结

第六章总结与展望

6.1本文的主要工作

6.2对研究的展望

参考文献

攻读硕士学位期间的主要成果

致 谢