張 強,李盼池

(東北石油大學(xué) 計算機與信息技術(shù)學(xué)院,黑龍江 大慶 163318)

混合蛙跳算法(SFLA)[1]具有計算速度快、 全局搜索尋優(yōu)能力強和易于實現(xiàn)的優(yōu)點,在很多領(lǐng)域應(yīng)用廣泛,但也存在早熟、 收斂速度慢且求解精度不高的缺點,使其在求解高維連續(xù)優(yōu)化問題時效果不理想[2]. 為了提高蛙跳算法的尋優(yōu)性能,文獻[3-7]分別通過在子群中引入吸引排斥機制、 引入搜索加速因子、 加入過去經(jīng)驗、 利用Logistic混沌序列構(gòu)造變異算子令算法自適應(yīng)的調(diào)整變異尺度實現(xiàn)對解空間的高效搜索、 利用QPSO作為子群局部搜索策略加強局部各簇群中個體的多樣性和均勻性等方法對算法進行了改進,提高了算法的收斂速度. 這些方法都是在原有蛙跳算法的子群搜索策略上進行改進,以提高算法的全局尋優(yōu)能力.

量子進化算法[8]是一種以量子計算的相關(guān)概念和理論為基礎(chǔ)的進化算法,與傳統(tǒng)進化算法相比,量子進化算法的種群多樣性更好,且可以用較小的種群規(guī)模獲得很好的全局尋優(yōu)性能[9]. 本文結(jié)合量子優(yōu)化與混合蛙跳算法的優(yōu)勢,提出一種量子混合蛙跳算法(quantum shuffled frog leaping algorithm,QSFLA). 該算法用量子位的Bloch球面坐標(biāo)編碼個體,采用量子位在Bloch球面上繞軸旋轉(zhuǎn)的方法實現(xiàn)優(yōu)化搜索,從而使每個個體代表的3個優(yōu)化解同時得到更新,并構(gòu)造一種自適應(yīng)混沌旋轉(zhuǎn)角度算子增強局部優(yōu)化的遍歷性,利用Hadamard門實現(xiàn)個體變異避免早熟,進而有效擴展解空間的搜索范圍,快速逼近全局最優(yōu)解.

1 標(biāo)準(zhǔn)混合蛙跳算法

假設(shè)一個蛙群共有P(P=m×n)只青蛙,將蛙群分成m個子蛙群,其中每個子蛙群中含有n只青蛙,每只青蛙代表解空間的一個向量X=(x1,x2,…,xl),l表示維數(shù). 分組方式如下：首先對蛙群中的個體按適應(yīng)度進行排序;然后將排序好的第一只青蛙放入第一個子蛙群,第二只青蛙放入第二個子蛙群,以此類推,則m+1只青蛙放入第一個子蛙群;在每個子蛙群中查找適應(yīng)度最優(yōu)青蛙xb和最差青蛙xw,將目前整個蛙群中的最優(yōu)青蛙記為xg;最后按下式對最差青蛙的位置進行調(diào)整.

青蛙移動距離：

Si=rand(xb-xw), rand∈[0,1],

(1)

新位置：

xw=xw+Si,Smax≥Si≥-Smax.

(2)

其中Smax是允許青蛙移動的最大距離. 若調(diào)整后生成的新解優(yōu)于xw,則用其代替xw；否則,用xg替換xb,再用式(1)和(2)繼續(xù)生成新解,若該新解優(yōu)于xw,則用其代替xw,否則隨機生成一個新解代替xw.

2 量子混合蛙跳算法(QSFLA)

2.1 個體編碼方案設(shè)計

在量子計算中,根據(jù)量子疊加原理,量子比特的任何態(tài)可寫成

(3)

此時,量子態(tài)可借助于嵌入三維笛卡爾坐標(biāo)系中的Bloch球面上的一個點直觀表示,其中θ和φ定義了該球面上的一個點,x=cosφsinθ,y=sinφsinθ,z=cosθ. 于是,量子態(tài)|φ〉可以寫成

(4)

因此,Bloch球面上的任意一點p(x,y,z)與一個量子比特|φ〉一一對應(yīng). 在QSFLA中,待優(yōu)化的個體直接采用量子位的Bloch球面坐標(biāo)編碼,設(shè)種群為m,優(yōu)化空間為n維,則第i個個體的編碼為

(5)

2.2 QSFLA的種群評估

2.2.1 個體解空間變換 在QSFLA中,每個個體均包含3組(x組,y組,z組)Bloch坐標(biāo),故每個個體包含3個優(yōu)化解. 根據(jù)式(5)可知其解空間每維均為[-1,1],要比較個體的優(yōu)劣性需進行解空間變換. 若解空間的第j維變量取值范圍為[min(j),max(j)],則解空間變換為如下形式：

(6)

2.2.2 QSFLA的種群評估 將個體對應(yīng)的三組解(Xij,Yij,Zij)分別代入適應(yīng)度函數(shù)計算該個體的適應(yīng)度. 令gglobalbest為整個種群的最優(yōu)適應(yīng)度,對應(yīng)的幅角為θg和φg,gpbest為每個子群中的最優(yōu)個體,對應(yīng)的幅角為θb和φb,gpworst為每個子群中的最差個體,對應(yīng)的幅角為θw和φw.

2.3 QSFLA的種群進化

2.3.1 QSFLA個體更新策略 子群中最差個體量子位幅角增量更新公式如下：

Δθ=rand( )(θb-θw), Δφ=rand( )(φb-φw).

(7)

量子比特相位的改變可通過量子旋轉(zhuǎn)門實現(xiàn),定義[10]如下：

基于量子旋轉(zhuǎn)門的量子位概率幅角更新公式如下：

(8)

若上述更新操作生成的新解優(yōu)于最差青蛙,則用新解取代最差青蛙,否則,用θg替換θb,φg替換φb,再用式(7)和(8)生成新解. 如果該新解仍未優(yōu)于最差解,則隨機生成一個新解替代最差青蛙.

由式(8)可見,兩個轉(zhuǎn)角Δφ,Δθ的符號及大小至關(guān)重要,符號決定收斂方向,大小決定收斂速度,關(guān)于這兩個轉(zhuǎn)角的確定,傳統(tǒng)方法[11-14]都是構(gòu)造一個查詢表,由于涉及多路條件判斷,因此影響了算法的效率. 實際上旋轉(zhuǎn)角的確定可視為是沿Bloch球面的一種旋轉(zhuǎn),本文提出一種量子比特繞軸旋轉(zhuǎn)方法,該方法可同時改變量子比特的θ和φ,進而提高了算法的尋優(yōu)能力和優(yōu)化效率.

2.3.2 QSFLA個體更新旋轉(zhuǎn)軸的確定 設(shè)到目前為止最佳個體gpbest上的第j個量子位為

當(dāng)前種群中的第j個量子位為

為使|φi,j〉沿Bloch球面準(zhǔn)確向|φbest,j〉旋轉(zhuǎn),旋轉(zhuǎn)軸的合理選擇至關(guān)重要,否則將使|φi,j〉偏離最優(yōu)解方向,導(dǎo)致優(yōu)化性能降低.

定理1記pbest,j=(xbest,j,ybest,j,zbest,j),pi,j=(xi,j,yi,j,zi,j),則由pi,j轉(zhuǎn)向pbest,j的旋轉(zhuǎn)軸為r=pi,j×pbest,j.

圖1 量子比特的Bloch球面旋轉(zhuǎn)示意圖Fig.1 Qubit Bloch spherical rotation representation

證明：球面上兩點間的最短距離是經(jīng)過這兩點的大圓在這兩點間的一段劣弧長度. 因此,要使pi,j通過旋轉(zhuǎn)后能快速逼近pbest,j,需令pi,j沿球面上經(jīng)過這兩點大圓的劣弧移動. 設(shè)pi,j和pbest,j的向量積為r,則根據(jù)向量積的定義可知,向量r的方向垂直于pi,j和pbest,j所決定的平面,r的指向按右手規(guī)則以小于π的角度從pi,j轉(zhuǎn)向pbest,j確定. 如圖1所示,若使pi,j繞著軸r旋轉(zhuǎn)到pbest,j,其旋轉(zhuǎn)軌跡恰好為Bloch球面上經(jīng)過這兩點大圓上的劣弧,且距離最短,故r為旋轉(zhuǎn)軸.

2.3.3 QSFLA個體更新操作 在Bloch球面上,由量子計算原理可知,沿單位矢量n=(nx,ny,nz)旋轉(zhuǎn)角度δ的旋轉(zhuǎn)矩陣為

其中σ=(σx,σy,σz). 因此,根據(jù)定理1,當(dāng)前量子比特|φi,j〉在Bloch球面上,繞軸r向|φbest,j〉旋轉(zhuǎn)δ的旋轉(zhuǎn)矩陣為

其中r=pi,j×pbest,j. 在Bloch球面上,當(dāng)前量子比特|φi,j〉向最優(yōu)量子比特|φbest,j〉旋轉(zhuǎn)δ角度的旋轉(zhuǎn)為|φi,j〉=Rn(δ)|φi,j〉,可見旋轉(zhuǎn)角度δ值太小將影響收斂速度,δ值太大可能會使結(jié)果發(fā)散或早熟收斂到局部最優(yōu)解,所以每次調(diào)整旋轉(zhuǎn)角δ值都很困難,本文給出一種自適應(yīng)混沌旋轉(zhuǎn)角度算子.

2.3.4 自適應(yīng)混沌旋轉(zhuǎn)角度算子 混沌是指在確定性非線性系統(tǒng)中,無需附加任何隨機因素便能產(chǎn)生類似隨機的行為,具有隨機性、 規(guī)律性和遍歷性的特點[15]. 其隨機性可保證進行大范圍搜索,遍歷性使搜索過程能在一定范圍內(nèi)不重復(fù)地遍歷所有狀態(tài). 基于混沌的優(yōu)化方法在搜索解空間相對較小時具有顯著效果,但解空間相對較大時效果并不理想[16],這種特點正好適合蛙跳算法子群內(nèi)部的全局遍歷,公式如下：

δ(t)=δmin+exp{-a×(t/Tmax)2}×L×(δmax-δmin),

其中：t/Tmax把迭代次數(shù)和旋轉(zhuǎn)角度聯(lián)系在一起進行自適應(yīng)調(diào)整,在迭代初期,算法用較大的旋轉(zhuǎn)角度進行全局搜索,隨著迭代次數(shù)的不斷增加,則逐漸減小旋轉(zhuǎn)角度進行精細搜索；Lj+1=μLj(1-Lj);μ=4是Logistic混沌序列,能使旋轉(zhuǎn)操作不重復(fù)地遍歷解空間,有利于提高算法優(yōu)化性能和搜索效率；δmin和δmax為轉(zhuǎn)角允許旋轉(zhuǎn)的最小值和最大值,有利于加快收斂速度. 在小區(qū)域內(nèi)引入混沌變量,并結(jié)合當(dāng)前個體進化代數(shù)動態(tài)控制旋轉(zhuǎn)角度,實現(xiàn)旋轉(zhuǎn)角度的自適應(yīng)調(diào)整,有利于提高局部解空間的遍歷性和青蛙種群的多樣性.

2.3.5 QSFLA個體變異操作 為增加種群多樣性,防止早熟收斂,利用Hadamard門對個體進行變異,定義如下:

根據(jù)

2.4 QSFLA分組方法的改進

標(biāo)準(zhǔn)SFLA分組方法中,相對適應(yīng)值較差的個體總被分在最后一組,使得該組最差個體向本組最好個體學(xué)習(xí)所獲得的效果不如前面的分組,這種分組方法導(dǎo)致個體學(xué)習(xí)具有一定的局限性. 本文提出一種改進分組方式：先按標(biāo)準(zhǔn)分組方法對種群分組,然后在其他組中隨機選擇一個個體和該組中的最優(yōu)個體產(chǎn)生一個新個體加入到本組,這樣每組就擴大到n+(m-1)個個體,增大了每組的多樣化. 每組都迭代完成后,再將各組重新合并成一個種群,此時,該種群含有m×n+m×(m-1)個個體,然后重新計算這些個體適應(yīng)值并重新排序,取前P個進入下一輪迭代.

QSFLA流程如下:

1) 初始化,計算Bloch坐標(biāo)；

2) 進行解空間變換,計算適應(yīng)度；

3) 對適應(yīng)度進行排序,對種群進行分組,并更新全局最優(yōu)解；

4) 對每一分組的最差個體執(zhí)行更新操作；

5) 對每個個體根據(jù)變異概率及式(5)實施變異操作；

6) 判斷是否滿足結(jié)束條件,不滿足則轉(zhuǎn)2),否則退出.

3 收斂性分析

定理2QSFLA以概率1收斂.

利用Markov鏈的相關(guān)理論證明QSFLA的收斂性.

由

得

故

即QSFLA是以概率1收斂的.

4 仿真實驗

為驗證QSFLA的性能,下面針對以下4個函數(shù)極值優(yōu)化問題,分別用QSFLA,SFLA,PSO和GA算法進行實驗.

1)f1(x,y)=10cos(2πx)+10cos(2πy)-x2-y2-20,x,y∈(-5.12,5.12).

該函數(shù)為典型的多峰函數(shù),當(dāng)優(yōu)化結(jié)果大于-0.005時算法收斂.

該函數(shù)有多個局部極大點,全局極大值為1.002,當(dāng)優(yōu)化結(jié)果大于1時算法收斂.

該函數(shù)有4個全局極大值點,全局極大值為2.118 76,當(dāng)優(yōu)化結(jié)果大于2.118時算法收斂.

該函數(shù)有多個局部極大點,全局極大值為1,當(dāng)優(yōu)化結(jié)果大于0.995 時算法收斂.

對上述4個函數(shù)分別用QSFLA,SFLA,GA和PSO算法各優(yōu)化50次,4種算法種群均取50,迭代次數(shù)為100,QSFLA和SFLA分組數(shù)m=5,n=10,δmin=0.001π,δmax=0.05π;GA的交叉概率pc∈(0.6,0.8),變異概率pm∈(0.01,0.08);PSO算法的慣性因子ω=0.5,自身因子c1=2,全局因子c2=2,變異概率pm=0.08,優(yōu)化結(jié)果列于表1. 由表1可見,QSFLA的收斂次數(shù)最多,優(yōu)化結(jié)果也最好,這是因為QSFLA采用三鏈編碼方式提高了算法的尋優(yōu)能力,并應(yīng)用自適應(yīng)混沌旋轉(zhuǎn)角度算子提高了算法子群的局部搜索能力,同時引入的變異算子可使算法避免陷入局部最優(yōu)解,且量子位兩個幅角的更新是通過繞某一旋轉(zhuǎn)軸向目標(biāo)量子位旋轉(zhuǎn),實現(xiàn)了兩個參數(shù)調(diào)整量的最佳匹配,極大提高了算法的優(yōu)化效率.

表1 不同算法對函數(shù)極值問題的優(yōu)化對比結(jié)果Table 1 Function extremum issues optimized results of different algorithms

綜上所述,本文提出了一種量子混合蛙跳算法,該算法用量子位的概率幅角對青蛙進行編碼,采用量子位在Bloch球面上的繞軸旋轉(zhuǎn)實現(xiàn)個體更新；采用自適應(yīng)混沌旋轉(zhuǎn)角度算子提高局部搜索能力,利用Hadamard門完成個體變異；并且本文算法的編碼方式使個體占據(jù)優(yōu)化空間的3個位置,擴大了獲得最優(yōu)解的幾率,提升了算法的尋優(yōu)效率. 實驗結(jié)果表明,QSFLA算法具有很強的全局搜索能力和較高的搜索精度,且運算簡單、 計算效率高、 收斂速度快.

[1] Eusuff M M,Lansey K E. Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm [J]. Journal of Water Sources Planning and Management,2003,129(3): 210-225.

[2] HE Bing,CHE Lin-xian,LIU Chu-sheng. Novel Hybrid Shuffled Frog Leaping and Differential Evolution Algorithm [J]. Computer Engineering and Applications,2011,47(18): 4-8. (何兵,車林仙,劉初升. 一種蛙跳和差分進化混合算法 [J]. 計算機工程與應(yīng)用,2011,47(18): 4-8.)

[3] ZHAO Peng-jun,LIU San-yang. Shuffled Frog Leaping Algorithm for Solving Complex Functions [J]. Application Research of Computers,2009,26(7): 2435-2437. (趙鵬軍,劉三陽. 求解復(fù)雜函數(shù)問題優(yōu)化問題的混合蛙跳算法 [J]. 計算機應(yīng)用研究,2009,26(7): 2435-2437.)

[4] Elbeltag E,Hegazy T,Grierson D. Amodified Shuffled Frog-Leaping Optimization Algorithm Applications to Project Management [J]. Structure and Infrastructure Engineering,2007,3(1): 53-60.

[5] ZHENG Shi-lian,LOU Cai-yi,YANG Xiao-niu. Cooperative Spectrum Sensing for Cognitive Radios Based on a Modified Shuffled Frog Leaping Algorithm [J]. Acta Physica Sinica,2010,59(5): 3611-3617. (鄭仕鏈,樓才義,楊小牛. 基于改進混合蛙跳算法的認知無線電協(xié)作頻譜感知 [J]. 物理學(xué)報,2010,59(5): 3611-3617.)

[6] GE Yu,WANG Xue-ping,LIANG Jing. Adaptive Chaotic Mutation Shuffled Frog Leaping Algorithms [J]. Application Research of Computers,2011,28(3): 945-947. (葛宇,王學(xué)平,梁靜. 自適應(yīng)混沌變異蛙跳算法 [J]. 計算機應(yīng)用研究,2011,28(3): 945-947.)

[7] TANG De-yu,CAI Xian-fa,QI De-yu,et al. Shuffled Frog Leaping Algorithm Based on Particle Swarm Optimization Searching Strategy [J]. Computer Engineering and Applications,2012,48(29): 29-33. (唐德玉,蔡先發(fā),齊德昱,等. 基于量子粒子群搜索策略的混合蛙跳算法 [J]. 計算機工程與應(yīng)用,2012,48(29): 29-33.)

[8] Hun K H,Kim J H. Quantum-Inspired Evolutionary Algorithm for a Class of Combznatorial Optimization [J]. IEEE Transon Evolutionary Computing,2002,6(6): 580-593.

[9] LI Shi-yong,LI Pan-chi. Quantum Particle Swarms Algorithm for Continuous Space Optimization [J]. Chinese Journal of Quantum Electronics,2007,24(5): 569-574. (李士勇,李盼池. 求解連續(xù)空間優(yōu)化問題的量子粒子群算法 [J]. 量子電子學(xué)報,2007,24(5): 569-574.)

[10] LI Pan-chi. Quantum Genetic Algorithm Based on Bloch Coordinates of Qubits and Its Application [J]. Control Theory &Applications,2008,25(6): 985-989. (李盼池. 基于量子位Bloch坐標(biāo)的量子遺傳算法及其應(yīng)用 [J]. 控制理論與應(yīng)用,2008,25(6): 985-989.)

[11] Han K H,Kim J H. Genetic Quantum Algorithm and Its Application to Combinational Optimization Problem [C]//Proc of IEEE Int Conference on Evolutionary Computation. La Jolla: IEEE Press,2000: 1354-1360.

[12] WANG Peng-jun,LI Hui,WU Wen-jin,et al. Application of Quantum Genetic Algorithm in Searching for Best Polarity of Multi-output Reed-Muller Logic Circuits [J]. Acta Electronica Sinica,2010,38(5): 1058-1063. (汪鵬君,李輝,吳文晉,等. 量子遺傳算法在多輸出Reed-Muller邏輯電路最佳極性搜索中的應(yīng)用 [J]. 電子學(xué)報,2010,38(5): 1058-1063.)

[13] LIANG Chang-yong,BAI Hua,CAI Mei-ju,et al. Advances in Quantum Genetic Algorithm [J]. Application Research of Computers,2012,29(7): 2401-2405. (梁昌勇,柏樺,蔡美菊,等. 量子遺傳算法研究進展 [J]. 計算機應(yīng)用研究,2012,29(7): 2401-2405.)

[14] Han K H,Kim J H. Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization [J]. IEEE Transactions on Evolutionary Computation,2002,6(6): 580-593.

[15] YANG Ling-ling,MA Liang,ZHANG Hui-zhen. Chaotic Optimization Algorithm for Multi-objective 0-1 Programming Problem [J]. Application Research of Computers,2012,29(12): 4486-4488. (楊玲玲， 馬良， 張惠珍. 多目標(biāo)0-1規(guī)劃的混沌優(yōu)化算法 [J]. 計算機應(yīng)用研究,2012,29(12): 4486-4488.)

[16] ZHANG Tong,WANG Hong-wei,WANG Zi-cai. Mutative Scale Chaos Optimization Algorithm and Its Application [J]. Control and Decision,1999,14(3): 285-288. (張彤,王宏偉,王子才. 變尺度混沌優(yōu)化方法及其應(yīng)用 [J]. 控制與決策,1999,14(3): 285-288.)

[17] LI Yang-yang,JIAO Li-cheng. Quantum-Inspired Immune Clonal Algorithm for SAT Problem [J]. Chinese Journal of Computers,2007,30(2): 176-183. (李陽陽,焦李成. 求解SAT問題的量子免疫克隆算法 [J]. 計算機學(xué)報,2007,30(2): 176-183.)