一種量子行為磷蝦算法及其仿真分析

劉 振， 劉文彪， 魯華杰

(海軍航空大學 岸防兵學院，山東 煙臺 264001)

0 引言

磷蝦算法作為一種低階群智能進化算法[1]，具有進化機制簡單、收斂速度快等特性，但同時也容易陷入局部極值的情況.因此磷蝦算法的改進方式不斷涌現(xiàn)，當前對其改進主要可以概括為以下幾類：

(1)與局部進化方式進行有效融合.如文獻[2]提出個體進化方式依據(jù)列維飛行，并利用精英個體更新磷蝦個體位置；文獻[3]引入反向?qū)W習方法初始化種群，用于提高進化效率；文獻[4]將混沌算法的思想引入到磷蝦算法中；文獻[5]對當前種群進化獲得的新位置，再次進行局部調(diào)整和二次開發(fā)，并采用貪婪選擇方式.

(2)對磷蝦算法中的進化參數(shù)進行調(diào)整，文獻[6]將靜態(tài)常數(shù)Δt進行了自適應推廣；文獻[7]不僅使Δt自適應變化，同時對慣性權(quán)重依據(jù)正弦方式進行調(diào)整.

(3)在磷蝦個體的進化過程中引入傳統(tǒng)進化規(guī)劃的操作算子，如個體遷移、交叉、變異等操作.文獻[8]引入了側(cè)重于開采的磷蝦遷移操作，能讓磷蝦個體在進化后期處于全局最優(yōu)值附近搜索；文獻[9]將交叉、變異引入到基本磷蝦進化算法中，保證算法進化過程中的全局勘探和局部開采的有機統(tǒng)一.

(4)與其他進化算法的有機融合，文獻[10]提出一種混合磷蝦進化算法，將磷蝦個體依據(jù)粒子群算法中的粒子進化操作方式執(zhí)行.

當前各種群智能進化算法大量涌現(xiàn)，如頭腦風暴優(yōu)化算法[11]，通過聚類和變異等操作方式驅(qū)動進化過程，克服傳統(tǒng)群智能進化算法存在的隨機性和盲目性，但相比磷蝦算法缺少生物學進化基礎(chǔ)，種群進化中也沒有考慮協(xié)同機制.量子計算以經(jīng)典的量子力學為理論基礎(chǔ)，充分利用量子的疊加性、相干性、糾纏性，因而使量子計算具有極好的并行計算能力.文獻[12-14]將量子計算與人工智能演化算法相結(jié)合，使量子計算技術(shù)可以結(jié)合人工智能進化優(yōu)勢，從而使進化算法具備全局收斂能力強、魯棒性好等特性.文獻[12]較早將量子編碼引入到免疫克隆算法中；文獻[13]和[14]將量子力學思想分別與引力搜索算法和粒子群算法相融合，構(gòu)成量子引力搜索算法和量子粒子群算法，有效提升了原有算法的收斂性能.根據(jù)量子理論，并利用協(xié)同進化思想，筆者提出一種協(xié)同進化量子磷蝦算法(cooperative evolution quantum krill herd algorithm, CEQKHA).將磷蝦進化種群分為主種群、輔種群，將磷蝦個體的運動狀態(tài)以量子態(tài)中的波函數(shù)表示，以一維delta勢阱作為勢場，在得到變量分離形式的波函數(shù)以后，適當選擇勢阱參數(shù)，使量子磷蝦個體在更新位置過程中趨向于當前勢阱中心最優(yōu)個體的位置，從而提高個體局部開采能力.

1 基本磷蝦算法及其特性分析

基本磷蝦算法用于模擬磷蝦群體受到食物源及群體影響的覓食行為，其覓食行為主要受食物吸引度、種群趨同性以及外部不確定因素影響.個體位置的進化過程可以利用拉格朗日模型表示為

(1)

式中：Xi(t)={xi,1,xi,2,…,xi,n}表示第i個磷蝦個體在t時刻的位置，n為問題維數(shù)；Ni(t)表示t時刻第i個磷蝦個體受群體影響的向量；Fi(t)表示第i個磷蝦個體受到食物吸引而產(chǎn)生的運動向量；Di(t)表示外界不確定性因素對其運動位置影響的向量，則個體在下一時刻的位置更新可按照式(2)進行：

(2)

磷蝦算法進化機制簡便，所需控制參數(shù)少，由于編碼機制設(shè)計過于簡單，多樣性不高，無法在進化過程中保持良好的全局勘探和局部開采性能.為提高基本磷蝦算法的全局收斂性能，筆者提出一種協(xié)同進化量子磷蝦算法.

2 協(xié)同進化量子磷蝦算法

2.1 多種群協(xié)同進化框架結(jié)構(gòu)

傳統(tǒng)磷蝦進化算法通常都維持單一種群進化模式，無法實現(xiàn)種群之間個體交流和信息的交互.多種群的進化模式能夠有效地保證個體進化過程中的多樣性[15]，使個體能夠以較大的概率接近最優(yōu)值.因此筆者將磷蝦群體劃分為主種群和輔種群，經(jīng)分析驗證設(shè)置輔種群數(shù)目為4，其進化結(jié)構(gòu)如圖1所示.

圖1 種群協(xié)同進化框架Fig.1 Framework for the cooperative evolution

在協(xié)同進化量子磷蝦算法中，設(shè)置主種群為M，輔種群為Subi(i=1,2,3,4).每個輔種群在完成一次進化后，都會把當前尋找到的最優(yōu)個體gbi(i=1,2,3,4)傳遞給主種群M，主種群M進行貪婪選擇判斷后，更新當前全局最優(yōu)解集.

2.2 量子進化行為

一個微觀粒子的量子態(tài)一般用波函數(shù)表示，因此波函數(shù)的演化狀態(tài)確定以后，就足以描述整個系統(tǒng)的狀態(tài)[16].薛定諤方程具有和經(jīng)典牛頓力學等同的作用，在任何時刻粒子的狀態(tài)都可以用波函數(shù)ψ(X,t)表示為:

(3)

式中：?為普朗克常數(shù)；H為與時間t無關(guān)的漢密爾頓操作符.

(4)

式(4)中，等式左邊是關(guān)于t的函數(shù)，而等式右邊是關(guān)于X的函數(shù)，兩邊相等并且都是能量E.因此，可以獲得微分方程為：

(5)

假定在磷蝦算法中，所有個體都具備量子行為，選擇其中最優(yōu)的Gbest個體構(gòu)成吸引勢場.不失一般性，假定用量子表示的個體都在一維空間中，因此所有向量X將變成標量x，設(shè)定y=x-gbest，其中g(shù)best表示最優(yōu)個體的位置.應用δ勢阱，令其中心在零點處，假定一維勢阱的數(shù)目和Gbest數(shù)目一致，則V(y)=-γδ(y)(γ>0)，其中γ為勢阱深度.勢阱深度在原點處為無窮，而在其他處為零，此時薛定諤方程為：

(6)

(7)

2.3 不同種群個體多樣化位置更新方式

為了充分發(fā)揮優(yōu)良個體引導作用，文獻[17]以等概率方式使磷蝦個體在最優(yōu)值附近進行搜索；文獻[18]在其基礎(chǔ)上，引入了群體平均值，增加了個體位置選擇的隨機性.筆者借鑒上述思想，提出在主種群中進行全局勘探，采用式(8)更新當前磷蝦個體的位置：

k|xi,d(t)-xmean(t)|·ln(1/u),

(8)

在輔種群中，為了進行局部精細開采操作，采用式(9)更新當前磷蝦個體的位置：

(9)

通過以上的描述，筆者提出的協(xié)同進化量子磷蝦算法(CEQKHA)整體流程可以表述如下:

步驟1設(shè)定算法進化參數(shù)信息，初始化種群P(t)，循環(huán)迭代次數(shù)t=1；

步驟2將種群P(t)劃分為一個主種群和4個輔種群分別獨立進化；

步驟4將輔種群Subi(i=1,2,3,4)中最優(yōu)個體gbi(i=1,2,3,4)傳遞給主種群M，輔種群向主種群進行精英個體交流；

步驟5按照2.2節(jié)的方式對磷蝦個體進行量子進化，并依據(jù)式(8)和式(9)進行更新；

步驟6判斷是否迭代結(jié)束，沒有結(jié)束，則t=t+1，返回步驟3，否則輸出最優(yōu)解，算法結(jié)束.

3 收斂性分析

由式(1)和式(2)，并結(jié)合式(8)和式(9)可以得到

X(t+1)=X(t)+G(t).

(10)

G(t+1)=μG(t)+αX(t)+β.

(11)

因此,根據(jù)式(10)和式(11),可以得到

X(t+2)-(1+μ)X(t+1)+(μ-α)=β.

(12)

由式(12)方程兩邊的構(gòu)造可以看出，其為一個差分方程，因此給出定理1.

Δ=(1+μ)2-4(μ-α)≥0，

則可得到

定理1得證.

4 仿真分析

利用基準函數(shù)f1～f18進行仿真分析，其中慣性權(quán)重ωn=ωf=0.9，Ct=2，最大引導速度為0.01，最大擴散速度為0.005，覓食速度為0.02，種群規(guī)模NP=100，循環(huán)迭代次數(shù)為100.所有仿真分析均在Intel(R) Core(TM) i3-3220處理器，內(nèi)存2.00 GB，Windows 7系統(tǒng)的計算機上進行，仿真軟件為Matlab R2009a.將筆者提出的協(xié)同進化量子磷蝦算法(CEQKHA)，與基本磷蝦算法(KHA)[1]、對立搜索磷蝦算法[3](OKHA)以及改進磷蝦算法[5](IKHA)進行仿真對比分析，變量取值范圍均設(shè)定在[-100,100]內(nèi)，分別利用單模函數(shù)、多模函數(shù)進行仿真分析，并分析進化框架結(jié)構(gòu)和位置更新方式對算法影響.

4.1 單模函數(shù)對比分析

將筆者提出的CEQKHA，利用單?；鶞屎瘮?shù)f1～f6進行仿真分析，其中f1～f3維數(shù)為5，f4～f6維數(shù)為10.并與基本磷蝦算法(KHA)、對立搜索磷蝦算法(OKHA)以及改進磷蝦算法(IKHA)進行對比，其中基準函數(shù)的全局最優(yōu)值均為0.4種算法分別獨立運行30次，統(tǒng)計獲得的最優(yōu)值、平均值和標準差，對比分析結(jié)果如表1所示.

表1 單模函數(shù)仿真對比分析Tab.1 Comparison results for unimodal functions

從表1的統(tǒng)計結(jié)果能夠看出，在設(shè)定的循環(huán)迭代次數(shù)范圍內(nèi)，幾種磷蝦改進算法(OKHA、IKHA、CEQKHA)，相比基本磷蝦算法(KHA)收斂性能都有了一定程度的提高.另外,從表1還可以看出，筆者提出的CEQKHA在大部分函數(shù)上的進化性能都優(yōu)于其他幾種進化算法.這是由于筆者采用了協(xié)同進化框架結(jié)構(gòu)，并應用量子勢阱機制，提升了個體在整個搜索空間中勘探和開采能力，因而尋優(yōu)效果整體優(yōu)于其他幾種改進算法.

為了充分進行算法對比，以f5函數(shù)為例進行進一步詳細分析，取一次迭代進化收斂如圖2所示. 從圖2可以看出，OKHA和IKHA分別采用了對立搜索方式和局部搜索算子，提高了算法的基本進化性能;而本文算法不僅采用了協(xié)同進化框架，而且采用了量子編碼提高了個體的全局和局部搜索能力.另外，基本磷蝦算法由于搜索的盲目性，初始進化效果不佳，OKHA和IKHA由于采用了對立搜索方式及局部搜索設(shè)計，因而提高了進化能力；而本文的CEQKHA尋優(yōu)迭代效果較好，能夠利用較少的迭代次數(shù)就能鎖定在最優(yōu)值附近搜索，因而無論是方差和均值性能均優(yōu)于其他對比算法.

圖2 f5函數(shù)仿真對比結(jié)果Fig.2 Comparison results for function f5

4.2 多模函數(shù)對比分析

將本文算法CEQKHA以多峰基準函數(shù)f7～f9為例進行仿真對比分析，其中3個多峰函數(shù)的全局最優(yōu)值均為0，函數(shù)維數(shù)均設(shè)置為20.對比算法也分別是基本磷蝦算法(KHA)、對立搜索磷蝦算法(OKHA)以及改進磷蝦算法(IKHA).4種算法分別運行30次，對其最優(yōu)值、平均值及標準差進行統(tǒng)計對比，同時進行單側(cè)t檢驗，并構(gòu)造檢驗統(tǒng)計量：

式中：n1和n2表示運行次數(shù)；S1和S2表示對比方差；M1和M2為對比均值.

檢驗假設(shè)為：H0：μ1≥μ2，H1：μ1<μ2，μ1和μ2理論最優(yōu)均值，給定顯著性水平0.05，拒絕域為：W={t>t0.05(n1+n2-2)}，經(jīng)查表后t0.05(58)=1.672 ，統(tǒng)計結(jié)果如表2所示.

從表2的統(tǒng)計結(jié)果能夠看出，當對多模函數(shù)進行優(yōu)化時，本文的CEQKHA相比其他幾種進化算法，在大部分函數(shù)上都能取得較好的收斂結(jié)果.從多模函數(shù)優(yōu)化對比結(jié)果可以看到，算法的進化能力得到了考驗，對算法的全局開采能力提出了更高的要求.同時表2還給出單側(cè)t檢驗結(jié)果，當顯著性水平為0.05時，t的計算結(jié)果均大于1.672，因此拒絕假設(shè)H0：μ1≥μ2，接受H1：μ1<μ2，說明本文算法平均值優(yōu)于其他對比算法.

表2 多模函數(shù)仿真對比分析Tab.2 Comparison results for multimodal function

4.3 高維函數(shù)對比分析

利用高維基準函數(shù)f10～f12為例進行仿真分析，其中函數(shù)維數(shù)均設(shè)置為100，3個高維函數(shù)的全局最優(yōu)值均為0.對比算法也仍然是基本磷蝦算法(KHA)、對立搜索磷蝦算法(OKHA)以及改進磷蝦算法(IKHA).4種算法分別運行30次，對平均值、標準差和平均運行時間進行統(tǒng)計,結(jié)果如表3所示.

表3 高維函數(shù)仿真對比分析Tab.3 Comparison results for high-dimension functions

當函數(shù)的維數(shù)達到100維時，對于幾種進化算法來說，尋找到最優(yōu)值都會變得較為困難.從表3的統(tǒng)計結(jié)果能夠看出，整體尋優(yōu)精度都會有所下降，特別是基本磷蝦算法(KHA)，函數(shù)尋優(yōu)性能下降明顯，性能指標相比其他幾種改進的磷蝦算法差距較大，甚至有時無法收斂到全局最優(yōu)值附近.從所有性能指標的對比可以看出，本文算法仍然能夠取得較為優(yōu)越的尋優(yōu)效果，顯示出算法具有較好的魯棒性.筆者采用的協(xié)同進化搜索框架和量子進化行為增強了算法的全局勘探和局部開采能力，使得CEQKHA相比其他改進的磷蝦算法，如OKHA和IKHA，能夠獲得更優(yōu)解.

4.4 算法進化行為影響分析

4.4.1 進化結(jié)構(gòu)影響分析

對筆者提出的CEQKHA，當不采用協(xié)同進化機制時，將算法標記為CEQKHAwce(CEQKHA without cooperative evolution)，將KHA、CEQKHAwce和CEQKHA，利用f13～f15函數(shù)進行對比分析，以驗證協(xié)同進化框架對算法運行結(jié)果的影響，各種算法分別獨立運行30次，函數(shù)維數(shù)均為20，對平均值、標準差和平均運行時間進行統(tǒng)計，如表4所示.

表4 協(xié)同進化對算法影響對比分析Tab.4 Comparison results of cooperative evolution

從表4的進化結(jié)果可以看到，CEQKHA由于采用了協(xié)同進化框架結(jié)構(gòu)和量子進化機制，因此其尋優(yōu)迭代效果優(yōu)于CEQKHAwce和KHA，雖然CEQKHAwce沒有采用協(xié)同進化框架結(jié)構(gòu)，但由于量子進化機制優(yōu)良的進化性能，其尋優(yōu)效果還是優(yōu)于KHA，顯示出本文算法良好的進化性能.從表4也可以看到，協(xié)同進化框架在提高了算法進化性能的同時，也相應地增加了算法的運行時間，因此適用于對時間要求不高而對精度要求較高的場合.

4.4.2 位置更新方式影響分析

文獻[13]提出建立最優(yōu)粒子集合，并采用輪盤賭方式選擇粒子作為勢阱中心，用于產(chǎn)生下一代個體，筆者沒有采用這種方式，而是采用式(26)和式(27)進行個體更新.將筆者采用的磷蝦個體更新方式，以f16～f18函數(shù)為仿真對象，函數(shù)維數(shù)均為20，與文獻[13]采用的更新方式進行仿真對比.各種算法獨立運行30次，其統(tǒng)計結(jié)果如表5所示，其中采用文獻[13]更新方式的算法標記為CEQKHAwrw(CEQKHA with roulette wheel).

表5 位置更新方式對算法影響分析Tab.5 Comparison results of position refresh

從表5的統(tǒng)計數(shù)據(jù)可以看到，筆者提出的CEQKHA在大部分函數(shù)上的平均值和標準差都略優(yōu)于CEQKHAwrw，只是在時間性能上處于劣勢;KHA的進化性能相對較差，但其運行時間最短.可以看出,本文算法的進化性能得到了提高，但同時也注意到，為了單純追求算法的尋優(yōu)效果，運行時間呈現(xiàn)倍數(shù)級增長，對應用時機和場合提出了一定的要求.

5 結(jié)論

筆者提出了一種協(xié)同進化量子磷蝦算法(CEQKHA)，將進化種群劃分為主種群和輔種群，采用具有量子進化的行為模式，將當前最優(yōu)個體設(shè)置為量子勢阱中心，并在主種群和輔種群內(nèi)采用不同的個體更新方式.對所提出的CEQKHA進行了收斂性分析和函數(shù)仿真分析，顯示出所提出算法的優(yōu)良性能和應用前景.但同時也注意到，受制于進化算法的特性和基本規(guī)律，尋找一種既能保證收斂精度又能保證收斂速度的“全優(yōu)”算法是很困難的.因此，提高算法的運行速度，降低算法的系統(tǒng)開銷，將是以后發(fā)展方向.