《1 前言》

1 前言

量子遗传算法（QGA）是近年发展起来的一种基于量子计算[1] 原理的概率优化算法，主要是在遗传算法（GA）中引入量子计算的一些概念，使遗传操作更有效，具有种群规模小但不影响算法性能，同时兼有全局寻优能力强和收敛速度快的特点。Narayanan 等[2] 首次将量子计算理论与进化算法相结合，提出了 QGA 的概念，Han K H 等[3~5] 将 QGA 用于典型组合优化问题——背包问题，实现了组合优化问题的求解，之后关于QGA的研究成果大量出现在各种学术会议与期刊中。张葛祥等[6] 提出一种新量子遗传算法（NQGA），其核心是采用自适应调整搜索网格的策略与量子比特相位比较法更新量子门。李盼池[7] 则利用实数变量和量子位构成实数染色体，并设计了互补变异算子来进化染色体。李士勇等[8，9] 针对 QGA 不适于连续函数优化的问题，提出改进的QGA，直接将量子染色体与当前最优解相比较来确定旋转门的旋转角，种群中各个体以不同速率向最优解进化，以同时实现全局搜索与局部搜索，引入变异操作以防止算法早熟收敛。张亮等[10] 提出一种基于球面解空间划分的QGA，引入多区域并行搜索机制，制定了群间的染色体置换策略，设计了新的量子变异操作，并以种群退化的程度来确定变异的概率。目前国内外各种QGA中有关量子旋转门旋转角的方向和大小几乎都是基于查表法，涉及多路条件判断，从而影响了算法的效率[11] ；变异概率大多采用给定的方式并且在进化过程中不作调整[12] 。

2003年，Eusuff等结合混合竞争进化的思想在粒子群算法的基础上提出了混合蛙跳算法（SFLA）[13，14] 。 SFLA是有限度随机搜索与确定性竞争进化策略的有机结合，是一种新型的仿生进化算法。目前该算法已经在一些经典组合优化问题上取得成功应用。为此，本文提出一种基于蛙跳思想的量子编码遗传算法（QRGA），该算法采用自适应的方式对量子旋转门旋转角进行调整，并基于模糊逻辑将蛙跳的步长进行量化以指导变异概率调整，保证进化的方向性和提高算法效率。

《2 基于蛙跳思想的QRGA》

2 基于蛙跳思想的QRGA

《2.1 量子编码与种群初始化》

2.1 量子编码与种群初始化

在 QRGA 中，染色体采用量子位表示，一个量子位的状态可表示为

一个量子位可能处于 0 或 1 ，或者处于 0 和 1 之间的中间态，即 0 和1的不同叠加态，其中 α 和 β 是复数，表示相应状态的概率幅，且满足下列归一化条件

式（2）中，|α|2 表示 |0 > 的概率，|β|2 表示 |1 > 的概率 。定义随机生成的量子染色体群 P ={P1 ，P2，…，PF} ，其中采用量子比特幅编码的染色体结构如下

式（3）中， m 为染色体基因个数。

初始化时，令所有个体基因位的概率幅（α1 ， β1）都为（ ， ），这意味着整个解空间中所有可能解的取值概率相同，可行解是通过对一个用概率幅编码的量子染色体进行“测量”来获得的，某一位在某一次“测量”中取“0”还是取“1”的概率由其相应概率幅大小决定。测量过程是对一个用概率幅编码的染色体进行测量获得的一个确定的二进制表示的解。把每个量子染色体看成一个青蛙，那么对于量子染色体群 P ={P1 ，P2，…，PF} 可看成含有 F 个青蛙的群体，对于解为 t 维的问题，第 i 个青蛙的位置为 ] 。生成群体之后，计算每个青蛙位置的适应度值 ，将其从大到小进行排序。将排序后的青蛙按式（4）平均分配到 m 个族群，每个族群有 k 个青蛙，因此有 F = m × k

式（4）中， 为第 个族群，族群中适应度函数值最小的青蛙位置用 表示

《2.2 基于蛙跳思想的更新策略》

2.2 基于蛙跳思想的更新策略

量子门的构造是QGA的关键问题。量子门的类型有很多，目前在 QGA 中主要采用的是量子旋转门[10]

量子旋转门的更新过程如下

式（5）和（6）中， Δθ 为旋转角，在更新的过程中，它的大小和符号起关键作用，太大可能使结果发散或早熟收敛到局部最优解，太小又会影响收敛速度。

为更好地利用量子旋转门，根据蛙跳的思想将Δθ 的大小设置为动态调整，大小与方向都不再使用传统的查表方式， Δθ 的具体计算方法如下

式（7）中， 为当前族群适应度最佳的青蛙位置； 为当前整个群体适应度最佳的青蛙位置； 为族群中适应度函数值最小的青蛙位置；和 为[0，1]内的随机数。利用式（7）自动调整量子门旋转角度的大小和方向。这样做有两个主要的优点：一是进化方程具有记忆特性，不仅利用整个群体最优状态的信息，也利用当前族群的局部最优信息，从而更加合理地调整角度 θ ，具有更好跳出局部极值的能力；二是简化了量子旋转角更新过程，不涉及多路条件判断。迭代更新后适应度值为 ，如 优于原适应度 ，则用 取代 ；否则用式（8）代替

式（8）和（9）中，D 为青蛙移动步长；Dmax 和 Dmin 分别为青蛙位置所允许移动距离的最大值和最小值。

《2.3 基于蛙跳步长的变异概率选择策略》

2.3 基于蛙跳步长的变异概率选择策略

蛙跳算法中蛙跳的移动步长大小直接影响着算法的全局收敛性。当其较小时，青蛙可在局部区域内精细搜索，但容易陷入局部最优；当其较大时，有利于青蛙在全局范围内广泛搜索，但有可能越过最优解[15] 。本文利用模糊逻辑的方法将 D 量化为 3 级，语言变量分别取为大、中、小。青蛙 变异概率 调整策略需同时考虑青蛙 的 D 值、 当前适应度值 、当前整个群体适应度最佳的青蛙适应度值 3个因素。现定义规则如下。

1）若 D 为大且 ，这表明当前青蛙 优于整个群体适应度最佳的青蛙适应度值，且当前青蛙 有可能跃过最优解，这不会影响到全局最优解，因此变异概率 不做调整。

2）若 D 为大且 < ，这表明当前青蛙次于整个群体适应度最佳的青蛙适应度值，且当前青蛙 有可能跃过最优解，变异概率 在原来的基础上应向增大的方向调整。

3）若 D 为中且 ，这表明当前青蛙 优于整个群体适应度最佳的青蛙适应度值，且当前青蛙移动步长的大小比较合适，变异概率 不做调整。

4）若 D 为中且 < ，这表明当前青蛙 次于整个群体适应度最佳的青蛙适应度值，且当前青蛙 移动步长的大小比较合适，变异概率 不做调整。

5）若 D 为小且 ，这表明当前青蛙 优于整个群体适应度最佳的青蛙适应度值，且当前青蛙 容易陷入局部最优，这会影响到局部搜索效果，变异概率 在原来的基础上向增大的方向调整。

6）若 D 为小且 < ，这表明当前青蛙 次于整个群体适应度最佳的青蛙适应度值，且当前青蛙 容易陷入局部最优，这会影响到局部搜索效果，变异概率 在原来的基础上向增大的方向调整。具体变异概率选择策略如表1所示。

《表1》

表1 变异概率pm选择策略

Table 1 The selection strategy of mutation probability pm

《3 实验仿真与分析》

3 实验仿真与分析

为了充分考察和比较GA、文献[10]的QGA、文献[8]的双链量子遗传算法（DCQGA）和本文QRGA 的性能，实验通过求解 0/1 背包问题与典型的数值优化函数来对这4个算法进行性能比较，以便于综合比较算法在组合优化以及数值优化方面的收敛性及全局搜索能力。

《3.1 0/1背包问题》

3.1 0/1背包问题

针对传统的典型组合优化问题——0/1背包问题，本文对GA、QGA和QRGA进行了对比实验。实验参数设置如下：GA 种群规模设为50，交叉概率为 0.95，变异概率为 0.5；QGA 种群规模设为 50，量子变异概率为 0.5，概率幅旋转角度Δθ = 0.001× ； QRGA 采用种群规模设为 50，量子变异概率为 0.5。图1给出了3种算法迭代次数为500的某一次进化曲线，图2给出了3种算法迭代次数为300的某一次进化曲线。

《图1》

图1 3种算法的进化曲线对比（500次）

Fig.1 The evolution curve comparison of the three algorithms（500 statistics）

《图2》

图2 3种算法的进化曲线对比（300次）

Fig.2 The evolution curve comparison of the three algorithms（300 statistics）

在图1和图2中，QRGA、QGA、GA分别在150 代、300代、500代附近找到其较优解，且较优解的值依次减小，这是因为QRGA算法充分采用了旋转角与变异概率的动态调整策略，收敛速度最快，在150 代已得到较优解，且较优解值要优于 QGA 和 GA，这充分体现了 QRGA 收敛速度快和全局搜索能力强的特点。

《3.2 数值优化问题》

3.2 数值优化问题

针对数值优化问题，本文采用 DCQGA 和 QRGA 同时求解标准数值优化问题，以测试本文算法在数值优化方面的性能。选取的两个典型的测试函数均来自于参考文献，为了更好地体现对比的可信性，测试函数 F2选取文献[8]中的测试函数。

测试函数1：多维多峰值函数+ ，其中 5x12.1，4y5.8，对比实验结果如图3和表2所示。

《图3》

图3 F1函数DCQGA和QRGA对比图

Fig.3 DCQGA and QRGA comparison chart of the F1 function

《表2》

表2 函数优化结果对比（100次统计结果）

Table 2 Results contrast of function optimization （100 statistical results）

测试函数 2：=0.5-

此函数有无限个局部极大点，其中只有（0，0）为全局最大，自变量取值范围为（-100，100），对比实验结果如图4和表2所示。

《图4》

图4 F2函数DCQGA和QRGA对比图

Fig.4 DCQGA and QRGA comparison chart of F2 function

图3、图4描绘了两种算法在最优值随迭代数变化的情况，其中点画线代表本文算法，表2给出了两种算法在函数优化的100次统计结果对比。从图3、图4以及表2可以看出，对于 F1 和 F2 ，在进化初期 QRGA 的收敛速度明显优于DCQGA，并且在整个进化过程中QRGA始终保持较快的收敛速度，同时 QRGA的求解质量也优于DCQGA。

综上所述，本文的算法充分采用了旋转角以及变异概率的动态调整策略，使量子态的干涉性和纠缠性等优势特性得到更好的体现，具有运行时间短、收敛速度快、全局寻优能力强等优点，能较好地适用组合优化与数值优化问题的要求。

《4 结语》

4 结语

本文提出一种基于蛙跳思想的QRGA，采用自适应的方式对量子旋转门旋转角与变异概率进行调整，保证了进化的方向性和种群的多样性，实验结果表明该算法能快速收敛到全局最优，在运行时间以及解的质量上取得了较好的效果。如何对算法的理论进行分析以及拓宽算法在优化问题中的应用范围将是下一步的研究方向。