量子混合蛙跳算法求解连续空间优化问题

第５１卷第３期　２０１３年５月　吉林大学学报（理学版）　

Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉ｝ｙ（Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　ＶｏＩ＿５１　Ｎｏ．３　

Ｍａｖ　２Ｏ１３　

ｄｏｉ：１０．７６９４／ｊｄｘｂｌｘｂ２Ｏ１３０３２６　

量子混合蛙跳算法求解连续空间优化问题　张强，李盼池　（东北石油大学计算机与信息技术学院，黑龙江大庆１６３３１８）　

摘要：基于量子理论提出一种量子混合蛙跳算法，该算法采用量子位的Ｂｌｏｃｈ球面坐标编　个体，利用量子位在Ｂｌｏｃｈ球面上绕轴旋转的方法更新个体，通过自适应混沌旋转角度算　提高子群内部局部搜索能力，采用Ｈａｄａｍａｒｄ门实现个体变异避免早熟，有效扩展了解空　的搜索范围．实验结果表明，该方法优于普通的混合蛙跳算法、粒子群算法和遗传算法，　有较高的优化能力和效率，更适合高维复杂函数的优化．　关键词：量子计算；混合蛙跳算法ｌ连续空间优化；仿真　中图分类号：ＴＰ３０１。６　文献标志码：Ａ　文章编号：１６７１—５４８９（２０１３）０３—０４７１－０７　’　

Ｑｕａｎｔｕｍ　Ｓｈｕｆｆｌｅｄ　Ｆｒｏｇ　Ｌｅａｐｉｎｇ　Ａ　Ｃｏｎｔｉｎｕｏｕｓ　Ｓｐａｃｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｌｇｏｒｉｔｈｍ　ｆｏｒ　

Ｐｒｏｂｌｅｍｓ　

ＺＨＡＮＧ　Ｑｉａｎｇ，ＬＩ　Ｐａｎ—ｃｈｉ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎｏｒｔｈｅａｓｔ　Ｐｅｔｒｏｌｅｕｍ　Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｑｉｎｇ　１６３３１８，　ＨｅｉｌｏｎｇＪ　ｉａｎｇ　Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ）　、　

Ａｂｓｔｒａｃｔ：Ａ　ｑｕａｎｔｕｍ　ｓｈｕｆｆｌｅｄ　ｆｒｏｇ　ｌｅａｐｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｐｒｏｐｏｓｅｄ　ｗｈｉｃｈ　ｃｏｍｂｉｎｅｓ　ｗｉｔｈ　ｔｈｅ　ｑｕａｎｔｕｍ　ｔｈｅｏｒｙ．Ｉｎ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｉｎｄｉｖｉｄｕａｌｓ　ａｒｅ　ｅｘｐｒｅｓｓｅｄ　ｗｉｔｈ　Ｂｌｏｃｈ　ｓｐｈｅｒｉｃａｌ　ｃｏｏｒｄｉｎａｔｅｓ　ｏｆ　ａ　ｕｂｉｔｓ，ｔｈｅ　ｉｎｄｉｖｉｄｕａｌ　ｕｐｄａｔｅ　ｉｓ　ｒｅａｌｉｚｅｄ　ｗｉｔｈ　ｔｈｅ　ｒｏｔａｔｉｏｎ　ｏｆ　ｑｕｈｉｔｓ　ｉｎ　Ｂｌｏｃｈ　ｓｐｈｅｒｅ，ａｎｄ　ｔｈｅ　ｌｏｃａｌ　ｓｅａｒｃｈ　ｃａｐａｂｉｌｉｔｉｅｓ　ｗｉｔｈｉｎ　ｔｈｅ　ｓｕｂｇｒｏｕｐ　ｉｓ　ｉｍｐｒｏｖｅｄ　ｗｉｔｈ　ａｄａｐｔｉｖｅ　ｃｈａｏｔｉｃ　ｒｏｔａｔｉｏｎ　ａｎｇｌｅ　ｏｐｅｒａｔｏｒ．Ｔｈｅｎ，ｔｏ　

ａｖｏｉｄ　ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ，ｔｈｅ　ｍｕｔａｔｉｏｎ　ｏｆ　ｉｎｄｉｖｉｄｕａｌｓ　ｉｓ　ａｃｈｉｅｖｅｄ　ｗｉｔｈ　Ｈａｄａｍａｒｄ　ｇａｔｅＳ．Ａｂｏｖｅ　

ｏｐｅｒａｔｉｏｎｓ　ｅｘｔｅｎｄ　ｔｈｅ　ｓｅａｒｃｈ　ｏｆ　ｔｈｅ　ｓｏｌｕｔｉｏｎ　ｓｐａｃｅ　ｅｆｆｅｃｔｉｖｅｌｙ．Ｒｅｓｕｌｔｓ　ｏｆ　ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ＳＦＬＡ，ＰＳＯ　ａｎｄ　ＧＡ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ａ　ｈｉｇｈｅｒ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｃａｐａｂｉｌｉｔｙ　ａｎｄ　ｅｆｆｉｃｉｅｎｃｙ，ａｎｄ　ｉｓ　ｍｏｒｅ　ｓｕｉｔａｂｌｅ　ｆｏｒ　ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｃｏｍｐｌｅｘ　ｆｕｎｃｔｉｏｎｓ．　Ｋｅｙ　ｗｏｒｄｓ：　ｑｕａｎｔｕｍ　ｃｏｍｐｕｔｉｎｇ；　ｓｈｕｆｆｌｅｄ　ｆｒｏｇ　ｌｅａｐｉｎｇ　ａｌｇｏｒｉｔｈｍ；　ｃｏｎｔｉｎｕｏｕｓ　ｓｐａｃｅ　

ｏｐｔｉｍｉｚｉｎｇ：ｓｉｍｕｌａｔｉｏｎ　

混合蛙跳算法（ＳＦＬＡ）。’　具有计算速度快、全局搜索寻优能力强和易于实现的优点，在很多领域　应用广泛，但也存在早熟、收敛速度慢且求解精度不高的缺点，使其在求解高维连续优化问题时效果　不理想　．为了提高蛙跳算法的寻优性能，文献［３—７］分别通过在子群中引入吸引排斥机制、引人搜索　加速因子、加入过去经验、利用Ｌｏｇｉｓｔｉｃ混沌序列构造变异算子令算法自适应的调整变异尺度实现对　解空间的高效搜索、利用ＱＰＳＯ作为子群局部搜索策略加强局部各簇群中个体的多样性和均匀性等方　法对算法进行了改进，提高ＴＪｇＮＮ收敛速度．这些方法都是在原有蛙跳算法的子群搜索策略上进行　

收稿日期：２０１２－１２—０８．　作者简介：张强（１９８２　），男，汉族，　基金项目：国家自然科学基金（批准号　科研基金（批准号：１２５１１００９）．　

博士，讲师，从事智能算法和神经网络的研究，Ｅ－ｍａｉｌ：ｄｑｐｉ—ｚｑ＠１６３．ｃｏｒｎ，　

６１１７０１３２）、黑龙江省教育厅科学技术研究项目（批准号：１１５５１ｏ１５）和黑龙江省教育厅　

码子问具　４７２　吉林大　学学报（理学版）　第５１卷　改进，以提高算法的全局寻优能力．　量子进化算法嘲是一种以量子计算的相关概念和理论为基础的进化算法，与传统进化算法相比，　量子进化算法的种群多样性更好，且可以用较小的种群规模获得很好的全局寻优性能嘲．本文结合量　子优化与混合蛙跳算法的优势，提出一种量子混合蛙跳算法（ｑｕａｎｔｕｍ　ｓｈｕｆｆｌｅｄ　ｆｒｏｇ　ｌｅａｐｉｎｇ　ａｌｇｏｒｉｔｈｍ，ＱＳＦＬＡ）．该算法用量子位的Ｂｌｏｃｈ球面坐标编码个体，采用量子位在Ｂｌｏｃｈ球面上绕轴　旋转的方法实现优化搜索，从而使每个个体代表的３个优化解同时得到更新，并构造一种自适应混沌　旋转角度算子增强局部优化的遍历性，利用Ｈａｄａｍａｒｄ　ｆ－ｉ实现个体变异避免早熟，进而有效扩展解空　间的搜索范围，快速逼近全局最优解．　

１标准混合蛙跳算法　假设一个蛙群共有Ｐ（Ｐ—　×　）只青蛙，将蛙群分成　个子蛙群，其中每个子蛙群中含有　只青　蛙，每只青蛙代表解空间的一个向量ｘ一（ｚ　，ｚ。，…，３５＂　），ｚ表示维数．分组方式如下：首先对蛙群中　的个体按适应度进行排序；然后将排序好的第一只青蛙放入第一个子蛙群，第二只青蛙放入第二个子　蛙群，以此类推，则　＋１只青蛙放人第一个子蛙群；在每个子蛙群中查找适应度最优青蛙　和最差　青蛙　，将目前整个蛙群中的最优青蛙记为　；最后按下式对最差青蛙的位置进行调整．　青蛙移动距离：　Ｓ　一ｒａｎｄ（ｚ６一ｚ　），　ｒａｎｄ∈［０，１］，　（１）　新位置：　ｚ　：＝ｚ　＋Ｓ　，　Ｓ…≥Ｓ　≥——Ｓ…．　（２）　其中５　是允许青蛙移动的最大距离．若调整后生成的新解优于ｚ　，则用其代替ｚ　；否则，用　替换　

，再用式（１）和（２）继续生成新解，若该新解优于ｚ　，则用其代替ｚ　，否则随机生成一个新解代替ｚ　．　

２量子混合蛙跳算法（ＱＳＦＬＡ）　２．１个体编码方案设计　在量子计算中，根据量子叠加原理，量子比特的任何态可写成　

＞一ｃｏｓ导１　０　５＋ｅ‘ｌ９ｓｉｎ导ｌ　１），０≤　≤　，０≤　≤２ｒｒ．　（３）　

此时，量子态可借助于嵌入三维笛卡尔坐标系中的Ｂｌｏｃｈ球面上的一个点直观表示，其中　和　定义　了该球面上的一个点，　—ＣＯＳ　９ｓｉｎ　，　—ｓｉｎ　９ｓｉｎ　，　—ＣＯＳ臼．于是，量子态Ｊ　）可以写成　ｒ　—＿一　．　、Ｔ　一【√　，　Ｊ・　㈩　

因此，Ｂ［ｏｃｈ球面上的任意一点　（ｚ，ｙ，ｚ）与一个量子比特ｌ　＞一一对应．在ＱＳＦＬＡ中，待优化的　个体直接采用量子位的Ｂｌｏｅｈ球面坐标编码，设种群为ｍ，优化空间为　维，则第ｉ个个体的编码为　ｌ　ＣＯＳ　ｌ　ｓｉｎ　ｎ；　ｌ　ＣＯＳ　ｓｉｎ　｝　—ｌｉｎ　ｎ　ｓ　ｎ　０ｉｌ　ｌ…ｌ　ｉｎ　ｍ　ｉｎ　ｍ　Ｉ，　（５）　Ｉ　ＣＯＳ　１　ｌ　ｌ　ＣＯＳ　Ｉ　ｉ一１，２，…，ｍ；　一１，２，…，　；０≤０　≤７ｃ；０≤‰≤２ｒｒ．　２．２　ＱＳＦＬＡ的种群评估　２．２．１　个体解空间变换　在ＱＳＦＬＡ中，每个个体均包含３组（ｚ组，ｙ组，ｚ￣ｉ１）Ｂｌｏｃｈ坐标，故每个个　体包含３个优化解．根据式（５）可知其解空间每维均为［一１，１］，要比较个体的优劣性需进行解空间变　换．若解空间的第Ｊ维变量取值范围为［ｍｉｎ（　），ｍａｘ（ｊ）￣，则解空间变换为如下形式：　

Ｘ　一　１［ｍｉｎ（ｊ）（１一ｚ　）＋ｍａｘ（ｊ）（１＋ｚ　）］，　

Ｙ　一去［ｍｉｎ（ｊ）（１一．ｙ　）＋ｍａｘ（ｊ）（１＋　）Ｊ，　第３期　张强，等：量子混合蛙跳算法求解连续空间优化问题４７３　Ｚ　一告［ｍｉｎ（ｊ）（１一ｚ　）＋ｍａｘ（ｊ）（１＋ｚ　）］．　（６）　厶　２．２．２　ＱＳＦＬＡ的种群评估将个体对应的三组解（ｘ［Ｊ，Ｙ　Ｚ　）分别代入适应度函数计算该个体的适　

应度．令ｇｇｌｏｂａｌ　为整个种群的最优适应度，对应的幅角为　和　，ｇＰ　。　为每个子群中的最优个　体，对应的幅角为Ｏｂ和　，ｇＰｗｏ　为每个子群中的最差个体，对应的幅角为　和　．　２．３　ＱＳＦＬＡ的种群进化　２．３．１　ＱＳＦＬＡ个体更新策略　子群中最差个体量子位幅角增量更新公式如下：　△　一ｒａｎｄ（：）（　一　），　△　＝ｒａｎｄ（：）（　一　）．　（７）　量子比特相位的改变可通过量子旋转门实现，定义＿ｌ。。如下：　ｆＣＯＳ．Ａ　９ｓｉｎ△０　一ｓｉｎ△９ｃｏｓ△０　ｓｉｎ　Ａ　０ｃｏｓ（９＋△　）１　Ｕ—ｌ　ｓｉｎ△９ｃｏｓ△　ＣＯＳ△９ｓｉｎ△０　ｓｉｎ△０ｓｉｎ（９＋△　）ｌ；　【一ｓｉｎ　一ｔａｎ（９／２）ｓｉｎ△　ｃ。ｓ　Ａ－０　ｊ　

基于量子旋转门的量子位概率幅角更新公式如下：　，（ＣＯＳ　９ｓｉｎ　ｆＣＯＳ（　＋△　）ｓｉｎ（０＋△　）１　己，ｌＳｓｉｎ　９ｃｏｓ　０ｌ—ｌ　ｓｉｎ（９－‘［－△　）ｃｏｓ（０＋．Ａ　）１．　（８）　ｌ　ｃｏｓ　０　Ｊ　ｌ　ｃｏｓ（　＋△　）　ｊ　

若上述更新操作生成的新解优于最差青蛙，则用新解取代最差青蛙，否则，用　替换　，％替换　，再用式（７）和（８）生成新解　如果该新解仍未优于最差解，则随机生成一个新解替代最差青蛙．　由式（８）可见，两个转角△　，△０的符号及大小至关重要，符号决定收敛方向，大小决定收敛速　度，关于这两个转角的确定，传统方法［１１－１４］都是构造一个查询表，由于涉及多路条件判断，因此影响　了算法的效率．实际上旋转角的确定可视为是沿Ｂｌｏｃｈ球面的一种旋转，本文提出一种量子比特绕轴　旋转方法，该方法可同时改变量子比特的０和　，进而提高了算法的寻优能力和优化效率．　２．３．２　ＱＳＦＬＡ个体更新旋转轴的确定　设到目前为止最佳个体ｇＰ　上的第Ｊ个量子位为　

ｌ　９ｂｅｓｔ，　）一ｆｃ。ｓ　￣ｅｉｇｂｅｓｔ，ｊ　ｓｉｎ　），　，　当前种群中的第Ｊ个量子位为　

，＞一（ｃ。ｓ譬　ｉｎ譬），　．　－