劉 振， 劉文彪， 魯華杰

(海軍航空大學(xué) 岸防兵學(xué)院，山東 煙臺(tái) 264001)

0 引言

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

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

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

2.2 量子進(jìn)化行為

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

(3)

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

(4)

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

(5)

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

(6)

(7)

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

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

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

(8)

在輔種群中，為了進(jìn)行局部精細(xì)開(kāi)采操作，采用式(9)更新當(dāng)前磷蝦個(gè)體的位置：

(9)

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

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

步驟2將種群P(t)劃分為一個(gè)主種群和4個(gè)輔種群分別獨(dú)立進(jìn)化；

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

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

步驟6判斷是否迭代結(jié)束，沒(méi)有結(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)造可以看出，其為一個(gè)差分方程，因此給出定理1.

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

則可得到

定理1得證.

4 仿真分析

利用基準(zhǔn)函數(shù)f1～f18進(jìn)行仿真分析，其中慣性權(quán)重ωn=ωf=0.9，Ct=2，最大引導(dǎo)速度為0.01，最大擴(kuò)散速度為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)的計(jì)算機(jī)上進(jìn)行，仿真軟件為Matlab R2009a.將筆者提出的協(xié)同進(jìn)化量子磷蝦算法(CEQKHA)，與基本磷蝦算法(KHA)[1]、對(duì)立搜索磷蝦算法[3](OKHA)以及改進(jìn)磷蝦算法[5](IKHA)進(jìn)行仿真對(duì)比分析，變量取值范圍均設(shè)定在[-100,100]內(nèi)，分別利用單模函數(shù)、多模函數(shù)進(jìn)行仿真分析，并分析進(jìn)化框架結(jié)構(gòu)和位置更新方式對(duì)算法影響.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 算法進(jìn)化行為影響分析

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

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

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

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

4.4.2 位置更新方式影響分析

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

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

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

5 結(jié)論

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