一种改进的量子演化算法及其在TSP问题上的应用研究

摘要

旅行商问题是数学组合优化领域最著名的问题之一,是一个非常典型的易于描述却难以大规模处理的NP-hard问题,如何有效地解决TSP问题,对组合优化问题的研究有重要的理论意义以及对实际应用有广泛价值。因为,只要是可以抽象成为访问带权完全图中全部结点一次且仅一次,求解最小费用Hamilton圈的问题,都可以当作此问题来解决。
　　量子演化算法是量子计算和演化算法的有效融合,利用演化算法具有的操作简单、不需要确定规则、采用概率化寻优方法、自动获取和优化搜索空间,自适应地调整搜索方向、隐并行性、全局寻优能力、鲁棒性强等性能,结合量子计算强大的并行计算能力以及可以有效的模拟量子行为的能力,以此来克服传统演化算法在解决规模较大、比较复杂的问题时存在计算量和存储量巨大、易陷入局部收敛等缺陷。量子演化算法融入了量子力学的许多基本特性,量子计算与演化算法的结合,将大大提高算法的效率。同时,本论文提出一种改进的量子演化算法进行TSP问题求解研究,并通过实验表明,该算法与传统的演化算法相以及改进前的量子演化算法比具有较好的优越性。主要工作和创新点如下:
　　1、在改进的量子演化算法中引入量子比特。使得算法染色体的编码建立在量子态的矢量表述基础上,采用量子比特和城市序号相结合的量子染色体编码方式,使量子个体具有并行性和叠加性,有效的减小种群的规模,使编码和译码方式简单,易于编码和译码的实现。
　　2、采用改进的量子旋转门——动态Hε量子门,进行自适应动态量子更新。使用改进的量子旋转门来更新种群,算法在不同的演化状态和阶段自动调整量子旋转角的大小,改变种群朝优秀个体演化的速度,设定概率触发器,利用量子非门进行量子变异操作,加快收敛速度而又使其不易陷入局部最优解。
　　3、提出一种改进的量子演化算法在 TSP问题上的求解方法。采用量子比特和城市序号相结合的几率幅量子染色体编码方式,使得算法的量子染色体的编码,既建立在量子态的矢量表述基础上又易于实现问题的编码和译码;利用改进的量子旋转门——动态Hε量子门进行动态自适应的量子更新,算法根据适应度值、演化代数及状态自动调整量子旋转角的大小,利用概率触发器触发量子非门作用于量子位变异操作。结合TSP问题,介绍改进的量子演化算法及其求解TSP问题的过程。仿真实验的结果表明其搜索到最优解的成功率高,稳定性好,在性能上优于改进前的算法。

目录

封面

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题的研究背景

1.2 本论文的创新点

1.3 本论文结构及主要内容

第二章 TSP问题及求解方法简介

2.1 TSP问题的定义

2.2 TSP问题求解算法

第三章 演化算法

3.1 演化算法的概述

3.2 遗传算法

3.2 演化算法的特点

3.3 影响演化算法性能的因素

3.4 本章小结

第四章 量子计算

4.1 量子计算及相关概念

4.2 量子计算的特性

4.3 基本量子算法

4.4 本章小结

第五章 量子演化算法

5.1 量子演化算法的基本概念

5.2 量子演化算法流程

5.3 本章小结

第六章 一种改进的量子演化算法及其在TSP问题上的应用

6.1 引言

6.2 改进的量子演化算法及其在TSP问题上的应用

6.3 算法的实验仿真与分析

6.4 本章小结

第七章 总结与展望

7.1 本论文的主要工作

7.2 对研究的展望

参考文献

致谢

声明