量子进化算法

量子理论与进化算法相融合形成的算法

量子进化算法用量子位编码表示染色体，用量子门更新完成寻优能力强的特点。量子进化算法的研究已经取得一些成果。

基本信息

Narayanan等人于1996年首次将量子理论与进化算法相结合，提出了量子遗传算法（QIGA）的概念；2000年，Han等人提出了一种遗传量子算法（GQA）,然后又扩展为量子进化算法（QEA），实现了组合优化问题的求解。

QEA采用量子比特编码，一个量子比特表示为|ψ>=α|0+β|1>,α和β为复数，在第t代的染色体种群为

Q(t)={(q1)^t ， (q2)^t ，…… ，(qn)^t}

其中n为种群大小；t为进化代数，(qj)^t为染色体，即

式中：m表示染色体长度，满足|αji|^2 + |βji|^2 = 1。算法流程描述如下：

Begin

1） t = 0,初始化种群Q(0),所有中的都被初始化为(1/√2, 1/√2)。

2）对初始种群中的各个体实施测量，得到一组状态 . 是长度为m的串，每一位为0或1，是根据量子比特的概率|αji|^2或|βji|^2测量得到的。测量过称为：随机产生一个数r,。若r属于[0,1],则测量结果；否则，取0。

3）对各状态f( )进行适应度评价。

4）记录下最佳个体状态及其适应度值f( )。

5）While非结束状态do

Begin

1.t = t +1 ;

2.对种群Q(t-1)实施测量，得到一组状态P(t);

3.对各状态f( )适应度评价；

4.利用量子门U(t)更新Q(t);

5.保存B(t-1)和P(t)中的最佳解到B(t);

6.记录下B(t) 中最佳个体状态b

End

主要研究成果

QEA算法具有种群分散性好、全局搜索能力强、收敛速度快且易于与其他算法融合等优点。近几年，国内外许多重要文献对QEA算法进行了更近一步的研究，主要体现在以下几方面。

算法机理及性能研究

这类研究大多从分析QEA算法的运行机理入手，类比分析QEA与其他经典进化算法的区别和相似性。具有代表性的有Ming等人从概率角度分析QEA，从量子的“波粒二象性”分析量子在进化过程中的特点，将传统遗传算法（GA）和QEA借助“波粒二象性”特征进行了类比，如表1所示:

从表1可以看出：QEA的进化与GA的进化在本质上具有相似性，QEA的种群是由量子组成的概率系统，其个体适应度评价为量子的能量，进化过程是量子的熵和能量的一种竞争，最终求得最优解时量子熵降低，种群趋于聚集，进化过程是种群从一种不平衡状态到平衡状态的转变。QEA进化的本质是种群的量子处于不确定状态到最终确定状态的过程，量子检测到为0或者1的概率趋于确定，其熵值也趋于最小。另外，文献[3]利用量子的纠缠态理论解释说明了遗传算法的本质，认为遗传算法计算在本质上是一种量子并行计算。Michael和Zhou等人都从分布式估计算法（EDA）的角度分析了量子进化算法，认为两种算法共同特征是利用概率模型进行演算，并从概率模型、抽样选择、学习替换和种群结构等方面进行了类比，得出了QEA的实质是一种EDA的结论。

通过图1的比较可以看出：EDA通过个体分布建立概率模型，并利用该概率模型进行样本采样以产生新种群；而在QEA中，则通过对量子比特的概率幅测量、坍缩的方法产生新种群，坍缩的方法与EDA样本采样相对应，它能使种群向更高适应度方向进化。从实验分析得出，QEA相对EDA更具有优势，主要体现在以下两方面：一是量子编码样本具有多样性；二是其概率模型具有自适应性调节能力。另外，KaiFan等人对QEA算法的特性进行了分析，对比了QEA与经典遗传算法、粒子群算法在解决静态、动态函数优化问题的性能差别，并分别测试了二进制、十进制编码情况下这几种算法对低维、高维函数的优化效果。结果表明：在静态环境下，QEA求解结果和运行时间都优于其他几种算法；在动态环境，QEA稳定性更好，且运行时间更少，改进的QEA算法更适合动态环境下高维实空间问题。

种群改进

量子比特编码能用较小的种群规模表示问题的多个解，所以种群的规模、结构等对算法性能影响较大。此类研究主要可归纳为如下几方面：

1)种群结构的改进。Najaran等人将QEA的种群结构进行了分类。按图2所示可分为：环型、网格型、二叉树型、簇型、方格型、型、阶梯型和交叉阶梯型等。文献[2]利用测试函数寻优对比分析了不同种群结构算法的性能，结果表明网格型为QEA性能最好的种群结构。Alba等人讲网格型的种群结构细分为正方形、长方形、长条形等，设计了根据个体适应度值和群体的熵来动态调节群体结构的QEA，这种算法能很好地兼顾勘探和开采能力。Ali Nodehi等人提出了基于网格结构的QEA，在这种结构中每个节点表示一个个体，这种结构能保持种群的多样性，可有效避免早熟和陷入局部极值。另外，Guo等人利用复杂网络理论类比量子进化中的各个个体间关系，复杂网络中小世界原理为量子进化个体间关系提供了一种借鉴，为达到这种种群弱链接，算法将种群分解为局部小群，各小群进行局部进化，这种种群结构能有效避免算法早熟。

2) 种群大小的改进。Ali Nodehi等人利用函数动态改变QEA种群大小。当种群增加时，随机新加入的种群改善了种群的多样性；当种群减少时，去掉种群中比较差的个体，可以缩小搜索范围，加快算法的收敛。Tayarani等人利用环形作为种群结构，以保证每个个体只与2个邻居相邻，并在进化过程中使用正旋函数改变种群大小，以保持种群多样性。Imabeppu等人在粗粒度并行量子遗传算法的基础上，针对种群间个体迁移的方式，提出了一种成对交换的算法，该算法与局部、全局优秀个体迁移不同，它在所有种群个体中只选择n/2对个体进行交换。对0-1问题的求解证明了所提出的算法具有局部搜索和全局搜索的优势。

编码扩展

QEA算法设计之初为量子比特编码，在进化中测量产生二进制串，所以算法对多参数和高维问题的求解受到了限制。QEA编码的扩展成为研究的热点，一些具有代表性的改进可归纳如下：1) 概率实数编码。Cruz等人定义了一种实数编码方式的QEA，该思想是将个体中每个分量用表示取值空间，它表示为一矩形区域，其中表示变量取值的坐标中心，为矩形取值空间的宽度，矩形的高度为 ,N为变量个数，个体表示为。该编码利用高度表示概率，例如表2表示的是两个体q1，q2的初始值。图3表示了表2中两个体q1，q2和概率实数编码。图3中，个体q1由中心为-5，宽度为20的g11矩形框及中心为0，宽度为20的g12矩形框组成。图4表示两个体q1，q2和进行交叉的结果。从图4可以看出，当2个个体进行交叉时，是将q1，q2分别代表的矩形区域进行叠加来产生新的个体，叠加后的矩形框高度表示在该区域取值的概率。用这种方式编码的量子进化算法，对高维函数优化测试结果显示具有更好的收敛速度和寻优精度。覃朝勇等人在此基础上引入了势能的概念，并用于高维函数优化，也取得了较好的性能。

2）三倍体编码。Li等人提出了一种量子位Bloch球面坐标编码。图5表示Bloch球中的一个点对应一个量子比特，因此量子比特|ψ>可描述为

|ψ>=[cosΦsinθ sinΦsinθcosθ]^T

按照这种方式，将量子位的3个Bloch球面坐标作为基因位，则可将量子比特编码转换为Bloch球面编码，表示如下：

这种编码能够避免因对量子位测量产生二进制串所带来的随机性，可用于连续优化问题，能够扩展全局最优解的数量，提高获得全局最优解的概率。另外，高辉等人提出了一种三倍体实数编码，即该编码由自变量的一个分量与量子比特组成，算法设计了互补双变异算子来进化个体，这种算子融合了量子旋转门和量子比特归一化条件，实现了局部搜索与全局搜索的平衡。

(3) 混合二倍体编码。Zhao等人采用改进的二倍体编码形式，即

其中x属于[a,b]为定义域区间，是实数。该文利用这种编码提出了一种基于QEA的模糊神经网络模型。另外，申抒含等人提出一种多进制概率角复合位编码QEA，将量子位的概率幅表示法转化为复合位的概率角表示法，采用随机观测方法得到观测个体，采用概率角增减的方式对个体进行更新。其编码形式为其中0<φ1iφ2i<90。该算法适用于采用任意进制编码问题。实验表明，算法在适用范围、搜索能力和运算速度上均具有较为明显的优势。

算子创新

基本QEA与一般进化计算不同，没有选择、交叉、变异等算子，所以修改并提出新算子融入QEA中便成为研究方向，具有代表性的有：

1）粒子群算子。Wang和周殊等人采用粒子群优化算子调节量子旋转门，并根据QEA自身概率特性，引入了最优解方差函数来评价该算法的稳定性。

2）免疫算法。Hongjian 等人将免疫的概念引入QEA，免疫算子在保留原算法优良特性的前提下，力图有选择、有目的地利用待求问题中的一些特征信息或先验知识，抑制或避免求解过程中的一些重复或无效的工作，以提高算法的整体性能。Haoteng等人提出了基于混沌理论的免疫QEA，该算法应用混沌免疫理论并依据小生境机制将初始个体划分为实数编码染色体的子群，各子群应用免疫算子的局域搜索能力找出优化解。

3）克隆算子。李阳阳等人提出一种基于量子编码的免疫克隆算法来求解SAT问题，算法中采用量子位的编码方式表达种群中的抗体，采用量子旋转门和动态调整旋转角策略对抗体进行演化，加速原有克隆算子的收敛，利用克隆算子的局部寻优能力强的特点，在各个子群体间采用量子交叉操作来增强信息交流，以提高种群的多样性，防止早熟。

4）模拟退火、模糊算子，王毅等人借鉴模拟退火方法，根据进化代数及个体的适应度值修正传统QEA旋转门函数的旋转角度值，焦嵩鸣等人利用模糊推理的方法，自适应地提高了算法的计算精度和收敛速度。

5）文化算子，Cruz等人在QEA中引入了文化算子，该思想借鉴了文化算法中规范知识的概念，用以描述当代种群的有效搜索空间范围，规范知识可以规避不在该范围内个人，引导个体进入有效区域搜索，算法收敛速度和精度都得到了提高。

6）其他算子。AraujoM等人利用多目标优化对量子进化中的旋转角参数进行计算，算法分2个层次，上层为求解多个测试函数的旋转角和旋转方向参数，将得到的参数用于底层的量子进化优化过程。Xing等人利用两点交叉算子对量子旋转门调整进行改进，其核心思想是确保在任何状态下以较大的概率使当前解收敛到一个具有更高适应度的染色体。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省