量子遗传算法在TSP中的应用

量子遗传算法在TSP中的应用

潘子宇 耿鹏

（南京工程学院 通信工程学院 江苏 南京 211167）

摘要：本文提出了一种改进的量子遗传算法，其核心是对量子遗传算法中的量子旋转门的调整策略进行改进。在现有的静态、指数型动态调整策略的基础上提出了基于正弦函数的动态调整策略。文中对旅行商问题（TSP）的仿真实验结果表明：改进后的算法的优化质量和效率都优于遗传算法和一般量子遗传算法。

关键词：旅行商问题，遗传算法，量子遗传算法 中图分类号：TP301.6 文献标识码：A

Reaearch of using improved quautum genetic algorithm to solve TSP

PAN Ziyu GENG peng

(Communication Engineering Institute Nanjing Institute of Technology, Nanjing

Jiangsu 211167, China)

Abstract: This paper presents an improved Quantum Genetic Algorithm, whose cores are that amending the quantum rotation gate adjustment artifice of Quantum Genetic Algorithm. Based with the present quiescence, exponential dynamic quantum rotation gate adjustment artifice, this paper addresses a new adjustment artifice, which is based on sinusoid. We use it to solve TSP. Simulation results show that the improved algorithm is superior to either Genetic Algorithm or standard Quantum Genetic Algorithm in quality and efficiency. Key words： Traveling Salesman Problem，Genetic Algorithm，Quantum Genetic Algorithm

0. 引 言

近年来，启发式智能优化方法越来越引起人们的关注。如：模拟退火、遗传算法、蚁群算法等，它们是解决NP问题的有效工具。

量子计算作为计算机科学界一个新兴的研究领域，在过去的几年里一直是人们研究和探索的热点问题。由于量子计算的并行性可以大大地降低了算法的复杂度，所以被广泛地用于解决需要大量计算空间的复杂问题。因此，量子计算支持了更为强大功能的算法设计，而这些算法可以大大地拓宽我们解决复杂问题的视野。量子遗传算法（Quantum Genetic Algorithm,QGA）是量子计算与遗传算法相结合的产物，是一种新发展起来的概率进化算法，目前主要应用于低维函数优化中[1-3]。为了进一步提高算法的性能，相关文献对量子遗传算法进行了一系列改进。文献[4]引入单纯形法作为局部搜索策略，利用其强方向性，使得算法效率大幅提高。文献[5]提出一种实属编码混沌量子遗传算法，仿真实验表明算法的全局收敛能力和算法精度得到提高。但改进后的算法都存在收敛速度慢，计算时间长，易陷入局部最优解等缺点。本文针对现有的量子遗传算法进行了改进，提出了运用正弦函数动态调整量子旋转门的方案。通过解决TSP问题的仿真实验证明：这种改进的量子遗传算法无论在优化质量上还是在效率上都优于遗传算法和一般量子遗传算法。

因此，本文做如下安排：第2节给出量子遗传算法的基本原理，第3节给出算法的实现方案和实验的结果分析，最后将总结并提出设想。

1. 量子遗传算法

量子遗传算法（QGA）建立在量子的态矢量表述的基础上，将量子比特的几率幅表示应用于染色体的编码，使得一条染色体可以同时表达多个状态的叠加，并利用量子旋转门的

【】

调整和量子非门来实现染色体的更新操作，从而实现了目标的优化求解6。 1.1量子比特编码

1

在量子计算机中，充当信息存储单元的物理介质是一个双态量子系统，我们称之为量子比特。量子比特与经典位的不同之处就在于它可以同时处在两个量子态的叠加态之中。

比如：

|????|0???|1?

其中，（?,?）是两个复常数，满足

|?|2+|?|2=1

其中?|0>和?|1>分别表示自旋向下和自旋向上态。所以一个量子比特可同时包含态|0>和|1>的信息。

在量子遗传算法中，采用量子比特的存储和表达一个基因。该基因可以为一个“0”态或“1”态，或它们的任意叠加态。即该基因所表达的不再是某一确定的信息，而是包含所有可能的信息，对该基因的任一操作也会同时作用于所有可能的信息。 1.2量子遗传算法流程

量子遗传算法的算法流程具体如下[7-8]：

①初始化种群Q（t0）； ②对初始化种群中的各个体实施一次测量，得到一组状态P（t0）； ③对各状态进行适应度评估；

④记录下最佳个体状态及其适应度值； ⑤while非结束状态do begin

t=t+1；

对种群Q(t)实施一次测量，得到一组状态P(t)； 对各状态进行适应度评估；

依据一定的调整策略，利用量子旋转门U(t)和量子非门对种群进行更新，得到子代种群Q(t+1)；

记录下最佳个体状态及其适应度值。

End

算法的第一步是初始化种群Q（t0），种群中全部染色体的所有基因

化为???,??均被初始

titi?1?2,1??，这意味着一个染色体所表达的是其全部可能状态的等概率叠加： 2?|?q0??j?k?12m12m|Sk?

其中，Sk为该染色体的第k种状态，具体表现形式为一长度为m的二进制串（x1，x2，------，xm），其中xi（i=1，2，3，----，m）要么为0，要么为1。

算法的第二步是对初始种群中的个体进行一次测量，以获得一组确定的解

tttp(t)?p1,p2,...,pn?，表现形?，其中,ptj为第t代种群中第j个解（第j个个体的测量值）

2

t2t2式为长度为m的二进制串，其中每一位为0或1是根据量子比特的概率（|?ij|或|?ij|，

i=1,2,…,m）选择得到的。测量过程为：随机产生一个[0，1]数，若该数大于概率幅的平方，则测量结果取值为1，否则取值为0。然后对这一组解进行适应度评估，记录下最佳适应度个体作为下一步演化的目标值。

随后，算法进入循环迭代阶段，随着迭代的进行，种群逐渐向最优解收敛。在每一次迭代的过程中，首先对种群Q（t）进行测量，以获得一组确定解P（t），然后计算每一个解的适应度值，再根据当前的演化目标和事先确定的调整策略，利用量子旋转门U（t）对种群中的个体进行调整，获得更新后的种群Q（t+1），记录下当前的最优解并与当前的目标值进行比较，如果大于目标值，则以新的最优解作为下一次迭代的目标值，否则，保持当前的目标值不变。

1.3量子旋转门调整策略

作为演化操作的执行机构，量子门可根据具体问题进行选择。目前已有的量子门有很多种，根据量子遗传算法的计算特点，选择量子旋转门较为合适。量子旋转门U（t）的调整操作如下式所示：

??it??cos(?i)?sin(?i)???i??t????????? ????sin(?)cos(?)?ii??i??i??其中，??i,?i?为染色体中的第i个量子比特，?i为旋转角，其大小和方向根据事先设计的调整策略而确定。

量子遗传算法中，旋转门是最终实现演化操作的执行机构。其调整策略如下表1所示。

表1 旋转角选择策略 S??i?i? xi 0 0 0 0 1 1 1 1 bi 0 0 1 1 0 0 1 1 f(x)?f(b) ??i ?i?i?0 ?i?i?0 ?i?0 False True False True False True False True 0 0 - - +1 -1 -1 +1 - - - - -1 +1 +1 -1 - - - - 0 ?i?0 - - ????0 0 ?1 0 0 ?1 ?1 0 - - ?1 - - 旋转角?i?S??i?i???i，其中S??i,?i?和??i分别代表旋转的方向和角度，其值根据表1的选择策略确定。该调整策略是将个体qj当前的测量值的适应度f?xi?与该个体当

t前的目标值的适应度值f?bi?进行比较，如果f?xi?>f?bi?，则调整中相应位量子比特(xi?bi)，使得几率幅向着有利于xi出现的方向演化；反之则调整中相应位量子比特，使

3

几率幅对??i,?i?向着有利于bi出现的方向演化。

旋转角的选择可以通过静态或动态的方法调整。在表1中，?为每次调整的角步长。??的值太大可能会使结果发散或早熟收敛到局部值的选择对算法的效率也有着很大的影响，

【】【】

最优解。文献9采用固定旋转角度的策略。文献10采用动态旋转角度的策略，即根据代数的不同，将?值的大小在0.1?和0.005?之间动态调整。实验结果表明：动态调整旋转角策略的收敛速度优于固定旋转角策略。 1.4量子变异

变异的作用主要在于阻止未成熟收敛同时提供算法的局部搜索能力。变异的

【】

方法有许多种。文献11中通过量子非门设计了一种量子变异操作，具体操作方法如下：

（1） 以一定的概率Pm从种群中随机选取若干个个体；

（2） 对选种的个体按照一定的概率随机确定一个或多个变异位； （3） 对选中位的量子比特的几率幅执行量子非门操作（“0”变“1”，“1”变“0”），

即完成了该量子比特的变异操作。

注：和自然界的生物变异类似，量子遗传算法中变异发生的概率很低，通常变异概率取在0.01~0.1之间。

量子变异操作实际上是改变了该量子比特态叠加的状态，使得原来倾向于坍 缩到状态“0”的变为倾向于坍缩到状态“1”，或者相反。显然，这样的变异操作对染色体的所有叠加态均同时有效。

2. 算法实现与性能分析

2.1旅行商问题的数学描述

旅行商问题的数学描述十分简单，该问题的约束条件只有一个，就是路程[12-14]。因此，我们的目标就是搜索整数子集X?{1,2,......,n},（X中的元素表示对n个城市的编号）的一个排列?（X?{v1,v2,......，使 vn}）

Td??d(vi,vi?1)?d(vi,vn)

i?1n?1取得最小值。其中的d(vi,vi?1)表示城市vi到城市vi?1的距离。 2.2基于量子遗传算法的TSP问题求解

运用量子遗传算法求解TSP问题的算法流程图如下：

4