量子混合蛙跳算法求解連續(xù)空間優(yōu)化問題

張 強(qiáng),李盼池

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

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

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

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

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

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

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

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

(3)

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

(4)

因此,Bloch球面上的任意一點(diǎn)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ìn)行解空間變換. 若解空間的第j維變量取值范圍為[min(j),max(j)],則解空間變換為如下形式：

(6)

2.2.2 QSFLA的種群評估 將個體對應(yīng)的三組解(Xij,Yij,Zij)分別代入適應(yīng)度函數(shù)計(jì)算該個體的適應(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的種群進(jìn)化

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

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

(7)

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

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

(8)

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

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

證明：球面上兩點(diǎn)間的最短距離是經(jīng)過這兩點(diǎn)的大圓在這兩點(diǎn)間的一段劣弧長度. 因此,要使pi,j通過旋轉(zhuǎn)后能快速逼近pbest,j,需令pi,j沿球面上經(jīng)過這兩點(diǎn)大圓的劣弧移動. 設(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)過這兩點(diǎn)大圓上的劣弧,且距離最短,故r為旋轉(zhuǎn)軸.

2.3.3 QSFLA個體更新操作 在Bloch球面上,由量子計(jì)算原理可知,沿單位矢量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)中,無需附加任何隨機(jī)因素便能產(chǎn)生類似隨機(jī)的行為,具有隨機(jī)性、 規(guī)律性和遍歷性的特點(diǎn)[15]. 其隨機(jī)性可保證進(jìn)行大范圍搜索,遍歷性使搜索過程能在一定范圍內(nèi)不重復(fù)地遍歷所有狀態(tài). 基于混沌的優(yōu)化方法在搜索解空間相對較小時具有顯著效果,但解空間相對較大時效果并不理想[16],這種特點(diǎn)正好適合蛙跳算法子群內(nèi)部的全局遍歷,公式如下：

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

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

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

根據(jù)

2.4 QSFLA分組方法的改進(jìn)

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

QSFLA流程如下:

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

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

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

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

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

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

3 收斂性分析

定理2QSFLA以概率1收斂.

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

由

得

故

即QSFLA是以概率1收斂的.

4 仿真實(shí)驗(yàn)

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

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ù)有多個局部極大點(diǎn),全局極大值為1.002,當(dāng)優(yōu)化結(jié)果大于1時算法收斂.

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

該函數(shù)有多個局部極大點(diǎn),全局極大值為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é)果也最好,這是因?yàn)镼SFLA采用三鏈編碼方式提高了算法的尋優(yōu)能力,并應(yīng)用自適應(yīng)混沌旋轉(zhuǎn)角度算子提高了算法子群的局部搜索能力,同時引入的變異算子可使算法避免陷入局部最優(yōu)解,且量子位兩個幅角的更新是通過繞某一旋轉(zhuǎn)軸向目標(biāo)量子位旋轉(zhuǎn),實(shí)現(xiàn)了兩個參數(shù)調(diào)整量的最佳匹配,極大提高了算法的優(yōu)化效率.

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

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

[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ìn)化混合算法 [J]. 計(jì)算機(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]. 計(jì)算機(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. (鄭仕鏈,樓才義,楊小牛. 基于改進(jìn)混合蛙跳算法的認(rèn)知無線電協(xié)作頻譜感知 [J]. 物理學(xué)報(bào),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]. 計(jì)算機(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]. 計(jì)算機(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é)報(bào),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é)報(bào),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ìn)展 [J]. 計(jì)算機(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]. 計(jì)算機(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]. 計(jì)算機(jī)學(xué)報(bào),2007,30(2): 176-183.)