期刊信息
曾用名:量子电子学
主办:中国光学学会基础光学专业委员会;中国科学院合肥物质科学家研究院
主管:中国科学院
ISSN:1007-5461
CN:34-1163/TN
语言:中文
周期:双月
影响因子:0.365217
数据库收录:
文摘杂志;北大核心期刊(2000版);北大核心期刊(2004版);北大核心期刊(2008版);北大核心期刊(2011版);北大核心期刊(2014版);北大核心期刊(2017版);化学文摘(网络版);中国科学引文数据库(2011-2012);中国科学引文数据库(2013-2014);中国科学引文数据库(2015-2016);中国科学引文数据库(2017-2018);中国科学引文数据库(2019-2020);日本科学技术振兴机构数据库;中国科技核心期刊;期刊分类:无线电电子学;物理学
期刊热词:
学术活动_第十三届全国光学前沿问题讨论会论文摘要集
一种新的自适应量子遗传算法研究(3)
【作者】网站采编
【关键词】
【摘要】图5 三种算法的进化图 5 结语 本文提出了基于实数和量子比特共同编码的自适应量子遗传算法,该算法运用实数和量子比特共同编码,采用自适应频率的临
图5 三种算法的进化图
5 结语
本文提出了基于实数和量子比特共同编码的自适应量子遗传算法,该算法运用实数和量子比特共同编码,采用自适应频率的临近算符对编码进行更新,运用自适应转角策略更新量子比特串,保证了算法保持搜索性能和求解性能的平衡,避免了使用二进制量子遗传算法时编码和解码过程。通过bGA、bQGA、RQGA三种算法对Schaffer’f6函数的测试实验表明,RQGA比bGA、bQGA所受问题的约束条件限制较少,能够将进化前期良好的搜索性能和进化后期良好的求精性结合起来,以较大概率收敛到全局最优解,具有很强的全局搜索能力,搜索速度快,收敛性好,尤其在解决数值优化问题时体现了很强的优越性。
[1]Platel M,Schliebs S,Kasabov evolutionary algorithm:a multi-model EDA[J].IEEE Trans on Evol Comput,2009,13(6):1218-1232.
[2]Babu G S,Das D B,Patvardhan quantum evolutionary algorithm for economic load dispatch[J].IET Generation Transmission&Distribution,2008,2:22-31.
[3]梁昌勇,柏桦,蔡美菊,等.量子遗传算法研究进展[J].计算机应用研究,2012,29(7):2401-2405.
[4]Talbi H,Draa A.A new real-coded quantum-inspired evolutionary algorithm for continuous optimization[J].Applied Soft Computing,2017,61:765-791.
[5]Silveira L R,Marley R T,Vellasco M B inspired evolutionary algorithm for ordering problems[J].Expert Systems with Applications,2017,67:71-83.
[6]Ho S L,Yang Shiyou,Ni quantum-inspired evolutionary algorithm for multi-objective design[J].IEEE Transactions on Magnetics,2013,49(5):1609-1612.
[7]Li Yangyang,Feng Shixia,Zhang Xiangrong,et al.SAR image segmentation based on quantum-inspired multiobjective evolutionary clustering algorithm[J].Information Processing Letters,2014,114(6):287-293.
[8]鹿艳晶,马苗.基于灰色遗传算法的快速图像匹配方法研究[J].计算机工程与应用,2008,44(32):169-172.
[9]Shantanu C,Takayuki I,Tomonobu economic operation of smart-grid facilitating fuzzy advanced quantum evolutionary method[J].IEEE Transactions on Sustainable Energy,2013,4(4):905-916.
[10]Gao Jiaquan,He Guixia,Liang Ronghua,et al.A quantuminspired artificial immune system for the multi-objective 0-1 knapsack problem[J].Applied Mathematics and Computation,2014,230:120-137.
[11]李胜,张培林,李兵,等.基于通用量子门的量子遗传算法及应用[J].计算机工程与应用,2017,53(7):54-59.
[12]吴瑞杰,孙鹏,孙昱,等.自适应量子遗传算法在指挥控制结构设计中的应用[J].计算机应用研究,2017,34(7):2045-2048.
[13]贺敏伟,李贵海,阮柏尧,等.改进量子遗传算法用于多峰值函数优化[J].计算机工程与应用,2008,44(7):41-43.
[14]Zhang Renlong,Shan Miyuan,Liu Xiaohong,et al.A novel fuzzy hybrid quantum artificial immune clustering algorithm based on cloud model[J].Engineering Applications of Artificial Intelligence,2014,35:1-13.
[15]Lei Huajun,Qin evolutionary algorithm for analog test point selection[J].Analog Integrated Circuits and Signal Processing,2013,75(3):491-498.
[16]Chou Y H,Chen C Y,Chiu C and quantuminspired electromagnetism-like mechanism and its applications[J].IET Control Theory and Applications,2012,6(10):1424-1433.
[17]Zhou Rigui,Cao novel genetic algorithm based on parallel subpopulation computing and its application[J].Artificial Intelligence Review,2012,41(3):359-371.
传统的量子进化算法基于二进制编码,α和β分别是0和1的概率幅[1]。所以传统的量子进化算法求解二进制参数的优化函数和组合问题时,具有较好的性能[2]。为了使量子进化算法能够更好地解决实参优化函数,需要设计基于实数参数的量子进化算法[3]。HichemTalbi针对实际参数优化问题,通过将本地搜索技术与量子激发的进化算法相结合,提出了一种新的实编码量子激励进化算法来解决连续优化问题[4]。Luciano Reisda Silveira提出了一种新的量子启发进化算法来解决排序问题,并对旅行商问题和车辆路径问题这两个基准应用程序进行了评估[5]。为了充分挖掘量子启发进化算法在多目标设计优化中的潜力,S L Ho提出了一个考虑整体目标函数的改进数和特定目标函数的改进量的适合性赋值公式来寻求最佳解决方案[6]。实现实参量子进化方法的一种直接方法是,每个参数用多个量子比特进行编码,然后把通过量子测量得到的二进制编码转换为0到1之间的实数[7]。然而,这种方法处理某些区间突变的函数时,需要使用大量的量子比特表示参数,这将导致计算量和搜索空间的增长,使计算效率降低。而且使用这种表示方法的另一个弊端是,一个二进制数的改变,有时不能得到临近解(例如,00和10)。灰色的编码方法可以缓解上述问题[8-9],但是灰色编码方法由于其灰色关联理论的不确定性和模糊性,难以设计出准确且有意义的遗传算子。所以需要设计性能较好的实数编码的量子遗传算法来解决数值优化问题[10]。1 实数编码的遗传算法编码方法实数编码的量子遗传算法(Real-coded Quantum Genetic Algorithm,RQGA)的初始染色体包括实数值和量子比特值,表示为:{P1(t)P2(t)… PNp(t)},其中,Ng)是实数编码值,(j=1,2,…,Ng)表示量子比特相位角,所以每个染色体同时包含实数空间和相位空间的信息。实数编码的量子遗传算法在搜寻过程中生成实数候选解字符串。一组Np个量子比特串,(i=1,2,…,Np)是第t代的第i个量子位串,相应地,另一组Ng个实数的Np个字符串(i=1,2,…,Np),保持不变。每个Qi有Ng个量子比特,代表αi的概率幅。生成比现值的大(小)的实数的概率由确定。搜索初期,所有概率相等,Qi的αi和βi都被初始化为0.707[11-13]。Pi(i=1,2,…,Np)的每个元素初始化为参数允许范围内的随机数。每对Qi和Pi代表第t代的第i个族。对第i个族的Nc个解的字符串(j=1,2,…,Nc)由、和(当前找到的适应度最好的解)生成。适应度在确定约束条件后计算。生成的示意图如图1所示。2 实数编码的遗传算法进化方法RQGA利用两种临近算符实现进化。两个临近算符,临近算符1(NO1)和临近算符2(NO2)用于生成 Nc个临近解字符串。其中,最好的临近解决定第i个族。如果优于,代替成为。所有中的最优值(若其优于)代替成为。在RQGA中,量子比特的进化表示0和1的重叠状态的进化,|α|2和|β|2的改变转化为问题空间中用两个临近算符进行实参的改变。临近算符1:第t代,Nq个量子比特串Qi,每个量子比特串有Ng个元素。NO1生成解字符串(j=1,2,…,Nc),每个解字符串有Ng个元素。图1 生成新Pbest的示意图生成有Ng个元素的数组Rij,Rij中的元素为随机的+1或-1。ρijk为Rij中的第k个元素,则其中δ是角度的变化,是旋转角,=arctan(βijk/αijk),若 ρijk=-1,δ 是的随机数;若 ρijk=+1,δ是的随机数。新的概率幅计算公式是:则个体元素的计算公式是:其中,Pkmax和Pkmin是允许范围的最大值和最小值。临近算符2:NO2的机制大部分和NO1一样,除此之外,NO2生成一个Pb和Pbest之间的点,并用这个点进行初始搜索空间的开发。NO2用公式确定,其中,Pkmax=max(Pbestik,),Pkmin=min(Pbestik,),是第t代第i族的最优个体。两种临近算符的特点如下:NO1有更好的搜索性能,因为由所给字符串生成的解很大程度上与所给字符串是不同的;NO2有更好的求精性能,因为随着算法的进行,Pj会向着Pbestj收敛。这一算法避免了二进制表示实数的缺点,同时可以在搜索和求精中取得平衡。用临近算符1计算第t代,第i个种群的第 j个个体的第k个元素的流程图如图2所示。图2 临近算符1计算第t代,第i个种群的第 j个个体的第k个元素的流程图NO1具有较好的寻优性能,NO2有较好的求精性能。由于在进化初期,算法以搜索为主,在进化后期,以求精为主,所以在进化前期以较大的频率比率进行NO1,在进化后期以较大的频率比率进行NO2。具体的频率比率按式(2)确定。其中,FNO1是NO1的使用频率比率,FNO2是NO2的使用频率比率,t是RQGA的当前进化代数,T是每次循环的RQGA的进化总代数。3 量子比特字符串更新在更新过程中,Q中的所有的量子比特的个体状态都变化,以至于生成与当前最优解相似的解的概率逐代增加[14]。几率的改变由学习速率Δθ确定[15]。表1给出第t代的Pi和Pbest的第k个元素的目标函数值不同条件下的Δθ的取值。其中,θt为第t代的旋转角大小,θt=θmax?exp(-t/T),θmax为最大旋转角,T 为总进化代数,t为当前进化代数。θt的这种取法有利于算法前期的寻优和后期的收敛精度。表1 第t代的Δθ查询表元素值适应度X F(P)>F(Pbest)F(P)<F(Pbest)Δθ 0 θt-θt-θtF(P)=F(Pbest)Cij=Pbest j Cij>Pbest j Cij<Pbest j Cij>Pbest j Cij<Pbest j Cij>Pbest j Cij<Pbest j θt 0 0Δθ决定了量子比特从0.707到最终值0或1的速率。Δθ要保证足够小以确保α从0.707到0(或1)的变换能经历较长的代数[16]。因此,生成与“当前最优解”极为相似的解的概率只有当大部分量子比特收敛到接近0或1时比较高[17]。图3 RQGA的流程图因此,RQGA的特点可总结如下:(1)RQGA利用量子比特编码染色体,避免了二进制编码和解码的计算,使种群具有更好的多样性,减少了计算量,提高了计算效率。(2)RQGA利用的是特殊的量子进化算符生成包含实参的候选解,RQGA算符必须保证搜索和求精的平衡。RQGA的搜索性能和量子算符使其更具有有效性、灵活性、鲁棒性等特点,可较好地解决复杂实参问题。(3)RQGA在求解问题时,不受问题的性质、问题模型的结构等约束条件的限制,能以较大概率收敛到全局最优解,具有很强的全局搜索能力。(4)在RQGA中,不同的量子比特串的迁移实现了不同的解的种群迁移,提高了解的收敛度和解的字符串的质量。4 算例分析运用遗传算法、二进制量子遗传算法和实数编码的自适应量子遗传算法进行函数寻优的对比实验,以验证函数的性能 问题描述求Schaffer’f6函数最大值的表达式为:对式(3)分析可知,该函数不能用一般的求导方法求最大值。此函数具有无穷多个局部极大值点,极大值为0.990 28,函数在(0,0)处取得全局最大值1。函数图形如图4所示 参数设置运用二进制编码的遗传算法(bGA)、二进制编码的量子遗传算法(bQGA)和实数编码的量子遗传算法(RQGA)三种算法寻找函数的最大值。三种算法的参数设置分别为:图4 Schaffer’f6函数图(1)bGA:种群大小为40,最大遗传代数为200,变量的二进制位数为20,代沟为0.95,交叉概率为0.7,变异概率为0.01。(2)bQGA:种群大小为40,最大遗传代数为200,变量的二进制位数为20,旋转角为0.01π。(3)RQGA:最大遗传代数为200,Np=5;子代个体Nc=10;Ng= 运行结果三种算法均运行10次,所得的运行结果分别如表2~表4所示,bQGA算法受二进制编码长度的影响,长度大则精度高,然而在RQGA算法计算过程中不需要对结果保留位数太多,因此,算法的优越性主要还是用全局最优的收敛性和平均运行时间来衡量,最优值大于0.999,就认为是近似收敛。对三种算法的寻优结果进行分析可知,bGA只有1次收敛到全局最优值,收敛性最差;bQGA有6次收敛到全局最优值,收敛性较好;RQGA有9次近似收敛到全局最优值,收敛性最好。且bQGA的平均运行时间为5.79 s,RQGA的平均运行时间为1.06 s,运行时间明显缩短。所以无论从收敛性、还是运行速度方面,RQGA均更适于数值寻优。采用这三种算法进行一次实验所得的进化图如图5所示。从图5的进化曲线可以看出,RQGA的进化最快,收敛性最好。表2 bGA运行结果指标次数3 2 4 5 6 7 8 9 x y最优值运行时间/s 1-2.155 8-2.281 1 0.990 28 4 0.026 107 0.990 28 6-1.430 5E-005 1 9 0.603 6 0.990 28 8 2.135 7 0.990 28 4 2.491 6 0.990 28 4 2.769 0.990 28 7-2.625 4 0.990 28 9-0.478 1 0.990 28 1.061 10 2.487 1.914 3 0.990 28 0.824表3 bQGA运行结果指标 次数4 2 5 3 6 7 89 x y最优值找到最优值时的进化代数运行时间/s 1 4.768 4E-6 4.768 4E-6 1 78 7.313 4.768 4E-6 4.768 4E-6 1 60 7.015 4.768 4E-6 4.768 4E-6 1 50 7.039 4.768 4E-6 1 78 5.842 4.768 4E-6 1 22 17 3.081 9 0.990 28 20 4E-6 4.768 4E-6 1 58 68 3.113 3 0.990 28 9 6.743 0.625 13 3.075 6 0.990 28 30 6.492 10-2.939 5-1.099 8 0.990 28 10 6.459表4 RQGA运行结果指标次数3 2 4 x y 0.002 634最优值找到最优值时的进化代数运行时间/s 1 0.024 395 0.000 797 0.999 4 91 2.830 0.000 363 1 132 0.706 0.000 595 1 55 6E-5 0.000 657 1 84 1.023 1.748 6 2.606 2 0.990 28 8 0.701 1 9 0.728 0.010 208 0.005 849 0.999 86 70 0.898 1.304 973 0.999 9 52 0.788 0.004 70 0.000 260 0.999 98 88 0.795 10 0.000 626 0.010 993 0.999 88 153 1.352图5 三种算法的进化图5 结语本文提出了基于实数和量子比特共同编码的自适应量子遗传算法,该算法运用实数和量子比特共同编码,采用自适应频率的临近算符对编码进行更新,运用自适应转角策略更新量子比特串,保证了算法保持搜索性能和求解性能的平衡,避免了使用二进制量子遗传算法时编码和解码过程。通过bGA、bQGA、RQGA三种算法对Schaffer’f6函数的测试实验表明,RQGA比bGA、bQGA所受问题的约束条件限制较少,能够将进化前期良好的搜索性能和进化后期良好的求精性结合起来,以较大概率收敛到全局最优解,具有很强的全局搜索能力,搜索速度快,收敛性好,尤其在解决数值优化问题时体现了很强的优越性。参考文献:[1]Platel M,Schliebs S,Kasabov evolutionary algorithm:a multi-model EDA[J].IEEE Trans on Evol Comput,2009,13(6):1218-1232.[2]Babu G S,Das D B,Patvardhan quantum evolutionary algorithm for economic load dispatch[J].IET Generation Transmission&Distribution,2008,2:22-31.[3]梁昌勇,柏桦,蔡美菊,等.量子遗传算法研究进展[J].计算机应用研究,2012,29(7):2401-2405.[4]Talbi H,Draa A.A new real-coded quantum-inspired evolutionary algorithm for continuous optimization[J].Applied Soft Computing,2017,61:765-791.[5]Silveira L R,Marley R T,Vellasco M B inspired evolutionary algorithm for ordering problems[J].Expert Systems with Applications,2017,67:71-83.[6]Ho S L,Yang Shiyou,Ni quantum-inspired evolutionary algorithm for multi-objective design[J].IEEE Transactions on Magnetics,2013,49(5):1609-1612.[7]Li Yangyang,Feng Shixia,Zhang Xiangrong,et al.SAR image segmentation based on quantum-inspired multiobjective evolutionary clustering algorithm[J].Information Processing Letters,2014,114(6):287-293.[8]鹿艳晶,马苗.基于灰色遗传算法的快速图像匹配方法研究[J].计算机工程与应用,2008,44(32):169-172.[9]Shantanu C,Takayuki I,Tomonobu economic operation of smart-grid facilitating fuzzy advanced quantum evolutionary method[J].IEEE Transactions on Sustainable Energy,2013,4(4):905-916.[10]Gao Jiaquan,He Guixia,Liang Ronghua,et al.A quantuminspired artificial immune system for the multi-objective 0-1 knapsack problem[J].Applied Mathematics and Computation,2014,230:120-137.[11]李胜,张培林,李兵,等.基于通用量子门的量子遗传算法及应用[J].计算机工程与应用,2017,53(7):54-59.[12]吴瑞杰,孙鹏,孙昱,等.自适应量子遗传算法在指挥控制结构设计中的应用[J].计算机应用研究,2017,34(7):2045-2048.[13]贺敏伟,李贵海,阮柏尧,等.改进量子遗传算法用于多峰值函数优化[J].计算机工程与应用,2008,44(7):41-43.[14]Zhang Renlong,Shan Miyuan,Liu Xiaohong,et al.A novel fuzzy hybrid quantum artificial immune clustering algorithm based on cloud model[J].Engineering Applications of Artificial Intelligence,2014,35:1-13.[15]Lei Huajun,Qin evolutionary algorithm for analog test point selection[J].Analog Integrated Circuits and Signal Processing,2013,75(3):491-498.[16]Chou Y H,Chen C Y,Chiu C and quantuminspired electromagnetism-like mechanism and its applications[J].IET Control Theory and Applications,2012,6(10):1424-1433.[17]Zhou Rigui,Cao novel genetic algorithm based on parallel subpopulation computing and its application[J].Artificial Intelligence Review,2012,41(3):359-371.
文章来源:《量子电子学报》 网址: http://www.lzdzxbzz.cn/qikandaodu/2020/1224/401.html
上一篇:一种QACO-LEACH无线传感器网络分簇路由算法
下一篇:书山拾英