量子克隆进化策略

，焦李成11西安电子科技大学电子工程学院，西安(710071)E-mail:[e-mail]摘要：进化算法是解决优化问题的一种有效方法。但在实际应用中也存在着收敛速度慢，早熟等问题，使得其结果极不稳定。本文在量子进化算法的基础上结合基于克隆选择学说的克隆算子，提出了改进的进化算法——量子克隆进化策略(QCES)。它既借鉴了量子进化算法的高效并行性又利用克隆算子来代替其中的变异和选择算子，以增加种群的多样性，避免了早熟，且收敛速度快。本文不仅从理论上证明了该算法的收敛性，而且通过仿真实验表明了此算法的优越性。关键词：克隆算子进化算法量子克隆进化策略中图分类号：TN9571．引言计算是人类思维能力的最重要的方面之一，计算能力的提高与人类文明进步息息相关。从古老的算盘到现代的超级计算机，人类的计算技术实现了革命性的突破。综观当今，计算机的广泛应用已经并且仍在继续改变着我们的世界。一方面，人们为计算机的神奇能力所倾倒。另一方面，人们也为它无力完全满足实际的需要而烦恼。因此，加速计算机的运算速度以提高计算机的运算能力成为计算机科学的中心任务之一。如何加快计算机的运算能力呢？这一问题大体可以从两个方面着手解决。一是制造更为先进的计算机硬件，另一则是设计恰当的计算机运算流程，后者可以称之为“算法”。一类模拟生物进化过程与机制来求解问题的自组织、自适应人工智能技术即进化计算(包括用于机器学习问题的遗传算法，优化模型系统的进化规划和用于数值优化问题的进化策略)的出现为我们寻找快速算法提供了新思路。进化计算是一种仿生计算，依照达尔文的自然选择和孟德尔的遗传变异理论，生物的进化是通过繁殖、变异、竞争、选择来实现的，进化算法就是建立在上述生物模型基础上的随机搜索技术。我们所熟悉的遗传算法(GeneticAlgorithms)，它通过模拟达尔文的“优胜劣汰，适者生存”的原理鼓励好的个体，通过模拟孟德尔的遗传变异理论在进化过程中保持好的个体，同时寻找更好的个体，由此来模仿一切生命与智能的产生与进化过程[1]。理论上已经证明：进化算法能从概率的意义上以随机的方式寻求到问题的最优解；但在实际应用当中随着问题的复杂和海量的数据量，也出现了一些不尽人意的情况，主要表现在：计算后期解的多样性差即易造成早熟，收敛速度慢等缺点。因此，为克服上述缺点关键是构造性能良好的进化算法。在改进的进化算法中，有些是将传统寻优算法与遗传算法相结合提出了混合遗传算法[2][3][4]，有些则另辟蹊径提出了新颖的学习算法——量子进化算法[5]和免疫进化算法[6]，量子力学是20世纪物理学最惊心动魄的发现之一，量子计算是物理理论与计算机的成功结合，在量子体系中，一位的信息位不在是经典的1比特，而是由两个本征态的任意叠加态所构成即1本课题得到高等学校博士学科点专项科研基金（项目编号：20030701013）资助称之为量子比特位(qubit)，正是量子的并行性使得原来传统计算机无法解决的复杂问题以惊人的速度得以解决,但在量子计算机尚未构成的情况下，为了充分利用量子计算的高效并行性，本文借用了量子进化算法中的量子编码，继承了免疫克隆策略中的克隆算子将二者相结合，提出了量子克隆算法，并将其应用于函数优化中，与传统进化算法相比较,它具有收敛速度快、寻优能力强的特点。2．基本概念2.1量子位我们知道，经典计算机的存储单元是比特，它只有两种状态，或者为0，或者为1。而量子计算机最基本的存储单元是量子比特(qubit)，它是任何一个有二维Hilbert态空间的量子体系[7]，它的态空间有两个基，记为|0〉和|1〉。与经典计算机中的比特不同的是，量子比特的态可以为任意叠加的态：a|0〉+b|1〉，其中a和b为满足归一化条件|a|2+|b|2=1的任意复数，且称之为概率幅，其平方表示在任何基态出现的概率。由此可得到：如果有n位的量子位，可同时表示n2个状态(即n2个信息)，因而在对量子比特计算时，一次运算相当于对n2个状态同时操作，这就是量子并行性的由来。所以，一个量子比特所包含的信息要比经典的比特多。2.2量子编码进化算法的常用编码方式有二进制、十进制和符号编码。在量子进化策略算法中，采用了一种特殊的编码方式——量子比特编码，即用一对复数来表示一个量子比特，这也正是此算法高效性的所在。一个具有m个量子比特位的系统(即为一个量子个体)可以描述为：⎟⎟⎠⎞⎜⎜⎝⎛mmbbbaaa......2121（1）其中，如前所述，ia和ib要满足归一化条件。这种表示方法可以表征任意的线性叠加态，例如一个具有如下三对概率幅的3量子比特系统：⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎝⎛2302121121（2）则系统的状态可以表示为：221|000〉+223|001〉+221|100〉+223|101〉（3）上式表示状态|000〉，|001〉，|100〉，|101〉出现的概率分别是83,81,83,81。由此我们很清楚的看到一个3量子比特系统表示了四个状态叠加的信息，即它同时表示出四个状态的信息。因此通过使用量子比特个体增加了算法的解的多样性。如在上例中，一个量子个体足以表示四个状态，而在传统进化算法中至少需要四个个体(000)，(001)，(100)，(101)来表示。2.3克隆算子如前所述，进化算法在解决优化问题时虽具有简单、通用、鲁棒性等特点，但在搜索后期由于其算法的盲目性和随机性，就会出现退化早熟现象。为了防止这类现象的发生，就是要增大优良个体的比例减少坏个体的不良影响，即利用有用信息来指导进化。基于此杜海峰等人提出了免疫克隆策略算法[8]，算法中主要提出了克隆算子，包括三个步骤：克隆、克隆变异和克隆选择。其抗体群的状态转移情况可以表示成如下的随机过程：：sC──→─clonekA)()1()()('+───→────→─kAkAkAselectionmutation值得说明是的：抗原、抗体、抗原和抗体之间的亲合度分别对应优化问题的目标函数和各种约束条件、优化解、解与目标函数的匹配程度。克隆算子就是依据抗体与抗原的亲合度函数(*)f，将解空间中的一个点)(kai∈)(kA分裂成了iq个相同的点)()('kAkai∈，经过克隆变异和克隆选择后获得新的抗体。其实质是在一代进化中，在候选解的附近，根据亲合度的大小，产生一个变异解的群体，从而扩大搜索范围。很显然，在克隆算子中，为了保持解的多样性而扩大空间搜索范围，采取对父代进行克隆复制的策略，其解空间变大是以计算时间增长为代价的，由于量子进化算法具有量子并行运算的特点。因此，本文将二者相结合，提出了量子克隆进化策略，是一种解决多峰值函数优化问题行之有效的快速方法。具体算法描述如下。3．量子克隆进化策略算法(QCES)3.1算法描述本算法仍然借用量子进化算法中的量子比特个体，并对量子个体进行克隆、变异、选择，由于量子个体携带了多个个体的信息，对量子个体进行进化操作，程序的额外开销少。下面给出算法的具体步骤：①初始化进化代数：t=0；②初始化种群)(tQ：21=tia；（初始时以等概率出现,即给概率幅赋予实数值）③克隆)(tQ生成)('tQ；④对)('tQ进行高斯变异生成)(tQ；⑤通过选择压缩)(tQ生成)1+(tQ；⑥评价种群)1+(tQ的亲合度,保存最优解；⑦停机条件判断：当满足停机条件时，输出当前最优个体，算法结束，否则继续；⑧t=t+1，转到③.值得指出的是，本算法中第③步克隆采取的是按一定比例复制具体操作详见[6]，克隆选择是在克隆群体中选择亲合度最好的保留下来，并且要保证经选择后群体规模与克隆前一样。在本算法中对于多峰值函数优化问题亲合度采用目标函数值来度量。计算种群Q的亲合度采取如下方法：其中)(tQ为量子个体种群，设)(tP为二进制个体种群，在第t代中)(tP=},...,,{21tnttxxx，每个二进制解tjx(j=1，2，…，n)是长度为m的二进制串，它是以|tia|2或|tib|2(i=1，2，…，m)为概率选择得到的，具体操作如下：随机产生一个[0,1]数，若它大于|tia|2，取值1，否则取值0。当生成二进制编码后解码来计算目标函数值。3.2算法收敛性证明定理3.1：量子克隆进化策略算法的种群序列}0,{≥kXk是有限齐次马尔可夫链。定理3.2：对于量子克隆进化策略算法马尔可夫链序列的种群满意值序列是单调不减的，即对于任意的0≥k，有)()(1kkXfXf≥+，即种群中的任何一个个体都不会退化。定理3.3：量子克隆进化策略算法是以概率1收敛的。详细证明参见文献［8］。4．仿真实验本文以下面三个测试函数[9][1][10]为例，并与传统进化算法(CEA)进行比较。000010000000000.06)6sin()4sin()4sin(122221+++++-+=yxyxyyxxfppp]1,1[,-∈yx；3.04cos3.03cos3.0222++-+=yxyxfpp]1,1[,-∈yx；∑=-+=niiixAxnAf123))2cos((p]12.5,12.5[-∈ix。我们针对两种算法采用统一的参数，最大进化代数为1000。图1中给出分别采用QCES和CEA对函数1f和2f一次优化的结果(图1中的（b）的进化的代数为50的情况)，其中“*”表示最终的最优值，从图1中反映出QCES解集的多样性要明显优于CEA。（c）中给出对函数2f一次运行结果的收敛性比较(其中实线为QCES、虚线为CEA)，从中也反映出QCES(简称为QCA)具有较快的收敛性。表1中给出独立10次试验的统计结果，发现由于采用量子比特个体，在种群规模较小时仍能获得满意的解，这样在实际应用中可节省计算的时间和空间。对于函数3f,当n=6时，传统的进化算法根本无法收敛到最优解，故在表1的相应框中用“/”来表示无法统计。在表1中可以看到QCES一次运行的时间有所增加，这是由于本算法比传统的进化算法多了两步（即量子个体生成普通二进制个体和克隆复制），但解的性能有了明显提高。(x)QCACEA(a)CEA(1f)(b)QCES(1f)(c)（2f）图1不同算法对函数1f和2f的优化结果表1：10次独立试验的统计结果函数1f2f3f(n=6)采用的优化方法种群数105010501050找到最优解次数10101010810QCES一次运行的时间(s)0.180.340.140.328.4650.12找到最优解次数3646//CEA一次运行的时间(s)0.140.260.120.22//5．结论本文借鉴了量子进化算法中的量子比特个体并与人工免疫系统中的克隆算子相结合提出了一种新颖的学习算法——量子克隆进化算法。通过理论分析与仿真试验表明：该算法与传统的进化算法相比，保持了解的多样性，有效克服了早熟问题、而且收敛速度快。参考文献[1]陈国良，王煦法，庄镇泉，王东生．《遗传算法及其应用》［M］，人民邮电出版社，1997。[2]Ahuja,RavindraK.Greedygeneticalgorithmforthequadraticassignmentproblem.ComputersandOperationsResearch27102000ElsevierScienceLtd:917-934[3]朱学军，王安麟，张惠侨．非稳态罚函数遗传算法及其用于机械/结构系统的健壮性设计［J］，机械科学与技术，2000,19(1):49-51。[4]YuHongmei;YaoPingjing.Combinedgeneticalgorithm/simulatedammea