logo资料库

一种量子模拟退火算法.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.28M 资料格式：pdf 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    第33卷第10期 辽宁工程技术大学学报（自然科学版） 2014年10月 Vol.33 No.10 Journal of Liaoning Technical University（Natural Science） Oct. 2014 收稿日期：2014-01-14 基金项目：国家科技重大专项基金资助项目（2013ZX03002006） 作者简介：田 鑫（1983-），男，辽宁 沈阳人，硕士研究生，主要从事智能算法方面的研究. 本文编校：朱艳华 文章编号：1008-0562(2014)10-1372-06 doi:10.3969/j.issn.1008-0562.2014.10.006 一种量子模拟退火算法 田 鑫，杨广明，陈 列 （东北大学 软件学院，辽宁 沈阳110819） 摘 要：为扩展量子智能算法的研究领域，根据模拟退火算法的思想，提出量子模拟退火算法（QSA）.定义了量子染色体相位邻域空间，缩小了算法搜索范围；引入信息熵的概念，避免了搜索的盲目性；给出一个量子的旋转角增量的表达式，简化了计算过程；采用Boltzmann概率分布原则接受新解，提高了算法的搜索性能；同时增加了量子变异操作和量子随机行为，可以防止算法早熟现象.研究结果表明：该算法具有较强的全局收敛性和搜索能力. 关键词：量子模拟退火算法；量子进化算法；信息熵；函数优化；PID控制器 中图分类号：TP 301.6 文献标志码：A Quantum simulated annealing algorithm TIAN Xin, YANG Guangming, CHEN Lie (Software College, Northeastern University, Shenyang 110819, China) Abstract: By combining quantum evolutionary algorithms and simulated annealing algorithm, this paper presented a quantum simulated annealing algorithm. In this algorithm, chromosome is encoded according to the phase; This study defined the phase neighborhood space and narrowed the scope of the algorithm search. The concept of information entropy was introduced to avoid searching blindness and the expression of the angle of rotation increments based on quantum revolving door was derived to simplify the calculation process. This study adopted the Boltzmann probability distribution principle to accept the new solution and improve the search performance of the algorithm; at the same time, the mutation operation and quantum random behavior were added to prevent the phenomenon of prematurity. It has proved the global convergence of the algorithm. Function optimization problem and PID controller parameter optimization problems were simulated. The results show that the algorithm has stronger global convergence and searching ability. Key words: quantum simulate anneal; quantum evolution algorithm; information entropy; function optimization; PID controller 0 引 言 量子进化算法是以量子计算的理论为基础，采用染色体的量子位表示形式，用量子门更新染色体来完成进化搜索.目前的研究趋势是将量子进化算法与传统的智能算法结合，研究成果主要有：量子遗传算法[1-2]、量子蚁群优化算法[3-4]、量子禁忌搜索算法[5]、量子粒子群算法[6]、量子人工鱼群算法[7]、量子差分进化算法[8]等. 借鉴已有的研究成果，将量子进化算法[9]和模拟退火算法进行改进与融合，提出一种量子模拟退火算法（Quantum Simulate Anneal，QSA）.该算法引入信息论中信息熵的概念，对染色体采用量子比特相位编码，对不同维度的相位空间n等分，得到n个相位邻域空间，计算出每个相位邻域空间的信息熵值，相位邻域搜索依据信息熵降序原则优先得到寻优相位，对寻优相位用量子旋转门进行更新，旋转角的大小由当前温度决定，采用Boltzmann概率分布法判断接受新解的概率，同时增加量子变异操作和量子随机行为.以上可以看出量子模拟退火算法在总体上与量子进化算法保持一致，理论分析可以保证算法以概率1收敛到最优解.通过函数优化问题和PID控制器参数优化问题仿真验证，结果也表明量子模拟退火算法收敛速度快，求解精度高. 1 量子模拟退火算法 在QSA中，量子染色体由若干个按一定顺序
    第10期 田 鑫，等：一种量子模拟退火算法 1373排列的量子比特组成，下面以函数优化问题为例，阐述本文提出的量子模拟退火算法. 1.1 量子染色体编码 在QSA中，量子染色体采用相位编码. 12[]{1,2,,}iiiimiN ， （1） 式中，N为染色体总数，m为优化问题的维数，初始化时，量子比特相位角π(21)ijrand，{1,2,,}jm. 量子染色体概率幅编码为 )sin()cos()sin()cos()sin()cos(2211imimiiiiisicPP. 1.2 优化问题的求解方法 设优化问题的变量jX的定义域为[,]jjab，量子比特为T[cos(),sin()]ijij，利用线性变换[5]，相应的解空间变换为 jjijijijijjisjicabXX)sin(1)sin(1)cos(1)cos(121. （2） 1.3 退火温度 对于QSA算法来说，温度是一个重要的参数，它随着算法的迭代而逐步下降，以模拟固体退火的降温过程.一方面，温度用于限制QSA产生的新解与当前解之间的距离，也就是QSA的搜索范围；另一方面，温度决定了QSA以多大的概率接受目标函数适应度值比当前解的目标函数适应度值差的新解.QSA温度公式为 0genTT， （3） 式中，α为降温系数；gen为当前迭代次数；T0为初始温度，℃. 1.4 Meteopolis准则 Meteopolis准则是指接受新解的概率，QSA接受新解的概率采用Boltzmann概率分布. '''1()()()()()1()()1expiiiiiiiiiifitfitPPfitfitPfitfitT≤ ， （4） 式中，Φi为当前解，'iΦ为新解，)(fit为解的目标函数适应度.式（4）的含义是：对于当前解Φi和新解'iΦ，若'()()iifitfit，则接受新解为当前解；若Pi为大于(0,1)区间的随机数，则仍然接受新解为当前解；否则，将拒绝新解而保留当前解.该过程不断重复，可以看到，开始时温度较高，QSA接受较差解的概率也相对较高，这使得QSA有更大的机会跳出局部最优解，随着退火的进行，温度逐步下降，QSA接受较差解的概率变小. 1.5 相位邻域空间定义 设m维优化问题第j个量子比特相位j的取值范围为[min(),max()]jj，并把该相位空间M等分，得到M个相位邻域空间Aj1, Aj2,… ,AjM，邻域空间长度jAL均为 max()min()jjjALM， 则相位邻域空间(1)jkAkM≤≤定义为 [min()(1),min()]jjjjjkAAAkLkL. （5） 1.6 信息熵的计算 在第t代种群中，第j个变量的种群熵定义为 1log()0MjjkjkjkkEppp. （6） pjk的计算公式为pjk=sjk /N，式中，sjk为第t代种群中量子染色体的第j个量子比特相位θ j属于区域Ajk的个体的数目；N为种群个体数目；pjk即为任意一个个体的变量θ j属于区域Ajk的概率. 1.7 相位邻域搜索策略 采用随机性的原则，随机产生位置更新向量S， 从当前的种群中依次选出一个量子染色体Φi，设寻优相位向量viΦΦ，按照变量的种群熵Ej降序排列原则，在更新向量S指定位置的相位邻域空间Ajk内随机选取一个相位jk，计算公式为 (min(),max())jkjkjkrandAA. 对相位向量vΦ在更新向量S指定位置的的量子比特相位依次用jk替换生成新的寻优相位向量*vΦ，计算该解的适应度*v()fit，若*vv()()fitfit，则替换该维相位并计算下一维相位，直至得到最佳的寻优相位向量vΦ；并把vΦ作为量子旋转门操作的一个优良的个体.
    辽宁工程技术大学学报（自然科学版） 第33卷 13741.8 量子染色体位置更新 通过量子旋转门对寻优相位向量vΦ用位置更新向量S指定的位置对量子比特进行更新，形成寻优相位向量*vΦ.向量vΦ相位增量更新为 0(21)tijTrandT； 122ttijijtttijijijttijij≤≤， 式中，{(1),(2),,()}jwSSS，w为向量S的长度. 基于相位编码的量子旋转门的更新为 11[]tttijijij . （7） 若满足Meteopolis准则，iΦΦ*v，否则，iΦΦv，同时更新当前位置的量子染色体没有进化的次数1)()(itrialitrial. 1.9 量子变异操作 变异目的是增加种群的多样性，避免算法早熟收敛.基于相位编码的量子非门更新相应表示为 []2ijij. （8） 设变异概率为Pm，若rand limit，执行随机行为，trial(i)=0；否则，执行下一步操作. Step13 判断是否满足结束条件，是则结束；反之，执行Step5. 2 量子模拟退火算法收敛性分析 QSA利用了量子进化算法的机理，是一种保留最优个体的实数进化算法.对于所要求解的目标问题Sxxf),(min，假设全局最优解为xbest，对应函数值为fbest.给定求解精度ε，则QSA可以视为一个有限状态空间的马氏链，其状态空间S为 01max{,,,}sSSSS， niiixxs)(max， 式中，n为搜索空间维度，x为搜索空间上域，x为搜索空间下域. 定义1 {(),0}Ann≥是QSA种群序列，如果对于任意的初始分布SS0均有 *0lim{()|(0)}1kPAkAAS， 则称算法概率1收敛[10]. 定理1 QSA是概率1收敛的. 证明 设种群第k代的概率为})0(|)({0*SAAkAPPk，第 k 代种群处于状态 i的概率为})0(|)({)(0SAikAPkPi，则*)(AiikkPP. 算法采用最优解保留策略，所以转移概率(){()|(0)}ijPkPAkjAi 有2种情况： （1）当**,AjAi时, 0)(kPij； （2）当**,AjAi时, 1)(kPij.
    第10期 田 鑫，等：一种量子模拟退火算法 1375由马尔可夫性质可知种群第k+1代的概率为)()()()(****1kPkPkPkPPijAiAjiijAiAjik. 由转移概率的性质有1)()(**AjijAjijkPkP，故 ********()()(()())()()()().kiiijijiAiAjAjAiijiijiAjAiAjAPPkPkPkPkPkPkPkPk 由转移概率的第一种情况有0)()(**kPkPijAiAji，可得)()(**kPkPPijAiAjik， 故kijAiAjikkPPkPPP)1()(**1，所以， 1121kkkkPPPP≥，因此lim1kkP，由定义1 ，QSA是概率1收敛的. 3 仿真实验 为验证QSA算法的性能，选择函数极值问题和PID控制器参数优化问题进行测试，仿真程序分别用Matlab 2009a编程实现，测试结果在CPU为Intel Core(TM) i5 3.2 GHz的PC上运行得到. 3.1 函数优化问题 从文献[11]～文献[14]中选取了4个国际上通用高维函数F1～F4，分别检验QIGA的性能. （1）5维函数 Rosenbrock函数为 4222111()10[100()(1)],110.iiiiiiFxxxxx≤≤ 该函数全局最大值为10(xi=1)，当函数值为9.8时认为算法寻优成功. Sinc 函数为 25511()sin(5)/5,1,10.iiiiiFxxxxy≤≤ 该函数全局最大值为1(xi=5)，当函数值为0.999时认为算法寻优成功. 利用文献[11]实例应用量子模拟退火算法（QSA）、改进量子扩展蚁群算法[11]（QACOR）和扩展蚁群算法[12]（ACOR）进行仿真实验. QACOR、ACOR算法参数的选择见文献[11]，对照文献[11]，QSA算法初始参数选择：种群规模为70，变异概率为0.1；3种算法独立运行10次，其中，“BV”、“AV”分别为 10 次独立运行结果中的最好最优值、平均最优值；“AG”为发现全局最优值的平均代数；“NS”为10次独立运行中找出全局最优值的成功次数.计算结果对比见表1. 表1 极值问题优化结果对比(10 次实验) Tab.1 comparison of optimization results on functionsextremum (10 experiments) 函数算法 状态值 BV AV AG NS F1 ACOR 10 8.034 334 7 QACOR 10 9.987 131 10 QSA 10 9.983 25 10 F2 ACOR 1.000 0.9865 170 6 QACOR 1.000 1.000 48 10 QSA 1.000 1.000 48 10 从表1可以看出，QSA和QACOR算法在处理5维函数的优化上效果明显，但QSA算法发现全局最优值的平均代数更小. （2）10维及以上函数 Rastrigin函数为 231()(10cos(2)10), 5.125.12.niiiiiFxxxx≤≤ Ackley函数为 24111()20exp0.21 expcos(2) 20exp(1), 3232.niiiniiiFxxnxnx≤≤ 两个函数的理论最小值均为0. 实验设置：参考文献[14]的实验设置两个函数分别采用10维、20维、30维的情况，对应算法的最大迭代次数为1 000、1 500、2 000. 在种群规模为20、40、80的情况下，分别用DGQPSO[13]、QPSO-TS[14]、QPSO-RS [14]、QSA对上述两个函数的优化性能进行比较. 每个实例运行50次所得到的最好目标函数的均值见表2和表3.
    辽宁工程技术大学学报（自然科学版） 第33卷 1376表2 rastrigin函数的测试结果 Tab.2 rastrigin’s calculation results 种群规模 维数 测试结果 DGQPSO QPSO-TS QPSO-RSQSA20 10 4.000 1 4.168 6 3.736 5 0 20 8.405 7 16.002 6 14.963 1 0 30 15.559 5 23.856 9 23.762 2 0 40 10 2.116 3 3.374 1 2.015 4 0 20 6.613 2 12.637 6 11.927 1 0 30 13.109 7 17.426 4 15.442 8 0 80 10 1.947 9 1.841 7 1.469 2 0 20 5.190 4 8.747 6 7.747 6 0 30 8.971 8 15.670 5 14.670 5 0 表3 ackley函数的测试结果 Tab.3 ackley’s calculation results 种群规模 维数 测试结果 DGQPSO QPSO-TSQPSO-RS QSA 20 10 13.204 5 9.991 5 3.736 5 8.881 8×10-1620 18.307 6 12.348 4 14.963 1 0.017 038 30 20.531 7 14.618 4 23.762 2 0.039 26 40 10 15.183 3 6.386 9 3.128×10-12 8.881 8×10-1620 18.716 2 8.647 4 5.39×10-19 8.881 8×10-1630 20.116 7 7.841 0 3.51×10-7 8.881 8×10-1680 10 13.208 0 0.809 3 3.029×10-13 8.881 8×10-1620 18.245 0 7.21×10-6 7.21×10-6 8.881 8×10-1630 19.679 1 1.915 1 1.143×10-7 8.881 8×10-16对于Rastrigin函数，QSA算法取得了最好的结果，其次是DGQPSO算法，再次是QPSO-RS算法，而QPSO-TS算法得到的结果最差. 对于Ackley函数，QSA算法的性能最优，其次是QPSO-RS，再次是QPSO-TS算法，性能最差的是DGQPSO算法. 3.2 PID 控制器参数优化 PID控制器具有结构简单、鲁棒性强、易于实现等特点，被广泛应用于控制领域，PID控制器的传递函数可描述为 ipd()KGsKKss， 式中，Kp为比例增益；Ki为积分增益；Kd为微分增益. PID控制器的优化问题就是确定一组合适的参数Kp、Ki、Kd，使得控制系统某一性能指标达到最佳.常用的误差性能指标包括误差积分（IE）、绝对误差积分（IAE）、平方误差积分（ISE）、时间和绝对误差乘积积分（ITAE）等，本文采用ITAE 积分性能指标作为评价函数，即 0|()|dJtett. 为与其他PID参数优化方法作对比，选取文献[14]中的控制对象进行仿真研究，其传递函数为 0.52e()21sGsss. 对照文献[15]，QSA算法参数：种群规模为8，迭代次数为100次，变异概率为0.1，分别用量子遗传算法QGA、IQGA[15]和QSA进行优化.各算法优化所得系统数据及性能指标见表4.优化后的控制系统单位阶跃响应输出曲线见图1.图2是采用QSA对PID优化时的ITAE函数变化. 表4 PID 参数及其性能指标对比 Tab.4 comparison of PID parameters and performance metrics 算法 状态值 Kp Ki Kd J 超调量σ/%调节时间ts/s QGA 2.933 60.839 1 1.612 2 7.032 3 8.48 3.67 IQGA 2.468 10.762 4 1.311 9 5.945 3 3.99 1.92 QSA 2.447 50.803 7 1.301 2 0.975 3 3.89 1.90 0.20.40.60.811.20246810时间t/s幅值/dBQGAIQGAQSA 图1 系统阶跃响应输出 Fig.1 comparison of control results 图2 QSA优化PID时ITAE变化 Fig.2 ITAE curve of the QSA optimize PID 从仿真结果看，采用量子模拟退火算法整定的PID控制器具有良好的控制效果，与其他算法整定的PID控制器相比，QSA优化所得系统具有更小的ITAE值，其阶跃输出响应具有更小的超调量σ，它响应速度较快，调节时间ts和上升时间较短，计算结果的波动较为平缓，说明算法也较稳定，
    第10期 田 鑫，等：一种量子模拟退火算法 1377具有更优秀的控制品质. 4 结 论 （1）提出一种量子模拟退火算法（QSA），把量子进化算法的多点并行搜索和模拟退火算法较好的单点串行搜索能力相结合. （2）定义了相位邻域空间，缩小了算法搜索范围；引入一种按信息熵降序原则的相位邻域搜索策略，避免了搜索的盲目性，加速了算法收敛速度. （3）给出一个基于量子旋转门的旋转角增量的表达式，且旋转角的大小随着温度下降过程逐渐减小，简化了算法的计算过程. （4）采用Boltzmann概率分布原则接受新解，高温时搜索算法具有较高的突跳性，可以避免陷入局部极值，而低温时有很好的保优搜索性能. 量子模拟退火算法具有较强的搜索能力和计算精度，将该算法推广到多目标优化领域是下一步的研究的课题. 参考文献: [1] Tiwari,Pawan Kumar,Vidyarthi Deo Prakash.A variant of quantum genetic algorithm and its possible applications[J].Advances in Intelligent and Soft Computing,2012,130(1):797-811. [2] 陈晓峰,杨广明.基于信息熵的量子免疫遗传算法[J].辽宁工程技术大学学报:自然科学版,2013,32(4):549-556. Chen Xiaofeng,Yang Guangming.Quantum immune genetic algorithm based on information entropy[J].Journal of Liaoning Technical University:Natural Science,2013,32(4):549-556. [3] Li Panchi,Wang Haiying.Quantum ant colony optimization algorithm based on bloch spherical search[J].Neural Network World,2012,22 (4):325-341. [4] Chen Xiaofeng,Xia Xingyou,Yu Ruiyun.Improved quantum ant colony algorithm based on bloch coordinates[J].Journal of Computers:Finland, 2013,8(6):1 536-1 543. [5] 陈晓峰,姜慧研.量子禁忌搜索算法的研究[J].电子学报,2013,41(11): 2 161-2 166. Chen Xiaofeng,Jiang Huiyan.Research of quantum tabu search algorithm[J].Acta Electronica Sinica,2013,41(11):2 161-2 166. [6] Li Junying,Shen Yudi,Liu Haitao. Quantum particle swarm optimization based search space partition with application to continuous space optimization[J].Journal of Information and Computational Science,2012, 9(2):521-531. [7] 陈晓峰,宋杰.量子人工鱼群算法[J].东北大学学报:自然科学版,2012,33 (12):1 710-1 713. Chen Xiaofeng,Song Jie.Quantum artificial fish school algorithm[J]. Journal of Northeastern University:Natural Science,2012,33(12):1 710-1 713. [8] 陈晓峰,杨广明,黄明.一种实数编码的量子差分进化算法[J].小型微型计算机系统,2013,34(5):1 141-1 145. Chen Xiaofeng,Yang Guangming,Huang Ming.Real-coded quantum differential evolution algorithm[J].Journal of Chinese Computer Systems, 2013,34(5):1 141-1 145 [9] Ajit Narayanan,Mark Moore.Quantum-Inspired Genetic Algorithms[C]// Proceedings of the 1996 IEE InternationalConference on Evolutionary Computation.Nagoya:IEEE Press,1996: 61-66. [10] 潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998. Pan Zhengjun,Kang Lishan,Chen Yuping.Evolutionary Computation[M]. Beijing:Tsinghua University Press,1998. [11] 李士勇,柏继云.连续函数寻优的改进量子扩展蚁群算法[J].哈尔滨工程大学学报,2012,33(1):80-84. Li Shiyong,Bai Jiyun.Extended quantum ant colony algorithm for continuous function optimization[J].Journal of Harbin Engineering University,2012,33(1):80-84. [12] Sochak,Dorigo M.Ant colony optimization for continuous domains[J]. European Journal of Operational Research,2008,185(3):1 155-1 173. [13] Sun J,Xu W B,Fang W.A diversity-guided quantum behaved particle swarm optimization algorithm[C]//Proc of IEEE Int Conf on Simulated Evolution and Learning.Washington:IEEE Press,2006:497-504. [14] 龙海侠,须文波,王小根,等.基于选择操作的量子粒子群算法[J].控制与决策,2010,25(10):1499-1505. Long Haixia,Xu Wenbo,Wang Xiaogen,et al.Using selection to improve quantum-behaved particle swarm optimization[J].Control and Decision,2010,25(10):1 499-1 505. [15] 李士勇,李浩.一种基于相位比较的量子遗传算法[J].系统工程与电子技术,2010,32(10):2 219-2 222. Li Shiyong,Li Hao.Quantum genetic algorithm based on phase comparison[J].Systems Engineering and Electronics,2010,32(10): 2 219-2 222.
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料