尚志剛，王 力， 李蒙蒙， 李志輝

(1.鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450001； 2.鄭州大學(xué) 產(chǎn)業(yè)技術(shù)研究院，河南 鄭州 450001； 3.河南省腦科學(xué)與腦機(jī)接口技術(shù)重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001)

0 引言

生物種群中單個(gè)個(gè)體的智能水平往往有限，但整個(gè)生物群體卻表現(xiàn)出處理復(fù)雜問題的能力.群體智能就是受自然生物群體行為的啟發(fā)而產(chǎn)生的一類重要的人工智能方法.Colorni等從生物進(jìn)化的機(jī)理中受到啟發(fā)，通過模擬螞蟻的尋徑行為，提出了蟻群優(yōu)化算法[1]，但其收斂時(shí)間過長(zhǎng)，易陷入局部最優(yōu)[2]；Kennedy等通過觀察鳥群覓食行為提出了粒子群優(yōu)化算法[3](particle swarm optimization，PSO)，其收斂速度較快，但易陷入局部最優(yōu)[4].鴿子具有特殊的歸巢能力，它們被認(rèn)為使用太陽、地球磁場(chǎng)和地標(biāo)的組合來尋找巢穴.Roberts等認(rèn)為，鴿子可能在旅程的不同階段使用不同的導(dǎo)航工具[5]，Guilford和他的同事開發(fā)了一個(gè)數(shù)學(xué)模型，可以預(yù)測(cè)鴿子何時(shí)從一種導(dǎo)航方式轉(zhuǎn)換到另一種方式.當(dāng)鴿子開始它們的旅程時(shí)，它們可能會(huì)更多地依賴類似指南針的工具[6]；在旅途中，當(dāng)它們找到熟悉的地形或者標(biāo)志性建筑時(shí)，它們轉(zhuǎn)而使用地標(biāo)[7-8].受這種鴿群歸巢行為機(jī)制的啟發(fā)，Duan等提出了一種鴿群優(yōu)化算法[9](pigeon-inspired optimization，PIO)，其簡(jiǎn)單、有效的特點(diǎn)[10]促使它得到了眾多學(xué)者的重視和研究[11-12].

鴿群優(yōu)化算法收斂速度快，精度高，但是與其他一些全局最優(yōu)算法一樣，它也有早熟收斂的現(xiàn)象.針對(duì)算法的這一缺陷，現(xiàn)在也有一些改進(jìn)方法，例如Sun等將捕食者機(jī)制引入鴿群算法[13]， Li等引入了模擬退火法[14]，Yang等將柯西變異引入鴿群算法[15]，這些改進(jìn)雖然增加了種群規(guī)?；蚍N群活躍性，但是對(duì)具有局部最優(yōu)值的函數(shù)優(yōu)化依然不太理想.筆者對(duì)自然界鴿子群體飛行行為進(jìn)行了總結(jié)，提出了一種生物行為啟發(fā)式的引入迷失探索與集群分裂機(jī)制的改進(jìn)鴿群優(yōu)化算法(lost and split pigeon-inspired optimization，LSPIO).新的算法以當(dāng)前全局最優(yōu)位置作為羅盤方向，受鴿子自然飛行過程中可能會(huì)迷失方向(感應(yīng)不到羅盤)，從而采用有限時(shí)間感知探索機(jī)制[16]的啟發(fā)，賦予算法中個(gè)體一個(gè)迷失概率，在迷失期間鴿子會(huì)自由探索，增加算法的全局搜索能力.同時(shí)借鑒鴿子飛行過程中發(fā)生的集群分裂機(jī)制，隨機(jī)分裂出若干子群進(jìn)行地標(biāo)探索，這樣既保證了全局搜索性能，也兼顧了局部搜索性能.筆者采用9個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)測(cè)試LSPIO算法的性能，并與標(biāo)準(zhǔn)鴿群算法和粒子群算法結(jié)果進(jìn)行對(duì)比分析，在多個(gè)測(cè)試函數(shù)上的結(jié)果表明，筆者提出的算法不僅具有更高的收斂性能，可以有效地避免早熟問題，并且有效提高了種群多樣性.

1 鴿群優(yōu)化算法介紹

在鴿群優(yōu)化算法中，分別基于鴿子的太陽、地磁導(dǎo)航機(jī)制和地標(biāo)導(dǎo)航機(jī)制提出了兩種算子：地圖羅盤算子和地標(biāo)算子.在迭代優(yōu)化過程中，前期使用地圖羅盤算子，后期使用地標(biāo)算子.

(1)地圖羅盤算子：鴿子可以通過使用磁感應(yīng)在大腦中塑造地圖.它們將太陽的高度視為指南針來調(diào)整方向.

(2)地標(biāo)算子：當(dāng)鴿子靠近目的地飛行時(shí)，它們將依賴鄰近的地標(biāo)指示方向.

PIO模型中，每個(gè)優(yōu)化問題的解都是搜索空間中的一只虛擬鴿子.每只鴿子都有一個(gè)速度矢量和位置矢量來決定它們的當(dāng)前位置以及飛翔方向和距離，每只鴿子的位置所對(duì)應(yīng)的目標(biāo)函數(shù)值作為該鴿子的適應(yīng)度(fitness value).所有鴿子個(gè)體按照一定的規(guī)則在解空間中尋找最優(yōu)解，即適應(yīng)度的最大值或最小值，筆者以最小值優(yōu)化為例進(jìn)行討論.

在鴿群優(yōu)化算法中，首先運(yùn)行地圖和羅盤算子，鴿子i的位置和速度分別用Xi和Vi表示，如下公式為地圖和羅盤算子位置速度更新公式：

Vi(t)=rand·(Xg(t)-Xi(t-1))+

Vi(t-1)·e-Rt;

(1)

Xi(t)=Xi(t-1)+Vi(t),

(2)

式中：R是地圖和羅盤因子；rand是一個(gè)隨機(jī)數(shù)；Xg是當(dāng)前全局最佳位置，可以通過比較所有鴿子中的所有位置來獲得;t表示當(dāng)前迭代次數(shù).

地圖和羅盤算子運(yùn)行一段時(shí)間后，轉(zhuǎn)為地標(biāo)算子運(yùn)行，其中遠(yuǎn)離目的地的鴿子對(duì)地標(biāo)不熟悉，它們將不再有分辨路徑的能力，因而被舍去，然后將剩余鴿子的中心位置Xc當(dāng)作地標(biāo)，所有看到地標(biāo)的鴿子直接飛向地標(biāo).地標(biāo)算子運(yùn)行一段時(shí)間后輸出最優(yōu)解.地標(biāo)算子的位置更新公式如下所示：

(3)

(4)

Xi(t)=rand·(Xc(t)-Xi(t-1))+Xi(t-1)，

(5)

式中：fitness表示鴿子個(gè)體的適應(yīng)度；Np為種群數(shù)量.

2 改進(jìn)的鴿群優(yōu)化算法

在鴿群優(yōu)化算法運(yùn)行過程中后期，如果某只鴿子發(fā)現(xiàn)一個(gè)當(dāng)前種群最優(yōu)位置，其他鴿子將迅速向其靠攏.如果該最優(yōu)位置為一局部最優(yōu)點(diǎn)，鴿群就無法在解空間內(nèi)重新搜索，因此，算法陷入局部最優(yōu)，出現(xiàn)了所謂的早熟收斂現(xiàn)象.

筆者結(jié)合現(xiàn)有研究資料和鴿群放飛實(shí)驗(yàn)觀察發(fā)現(xiàn)，鴿群飛行時(shí)存在以下兩個(gè)特別的行為機(jī)制：

(1)鴿子會(huì)在歸巢導(dǎo)航過程中發(fā)生察覺不到羅盤信息而自由探索的情況，而在自由探索過程中，鴿子存在一個(gè)有限時(shí)間感知探索機(jī)制[16]：鴿子在飛行探索時(shí)不會(huì)不停轉(zhuǎn)向，而是會(huì)沿一個(gè)方向飛行一段時(shí)間，如果在該時(shí)段內(nèi)不能獲得目標(biāo)方向信息，則會(huì)選擇反向或根據(jù)自身探索到的一些信息而調(diào)整方向.

(2) 由于某些外界因素(如障礙物、天敵等)的干擾，鴿群歸巢過程中會(huì)發(fā)生集群分裂的情況，分裂后的子群通常會(huì)脫離主群飛行，子群飛行中可能會(huì)探索到熟悉的建筑或感興趣的地標(biāo).

基于上述機(jī)制，筆者對(duì)鴿群算法進(jìn)行改進(jìn)，提出一種新的改進(jìn)LSPIO算法.首先引入迷失探索機(jī)制改進(jìn)地圖羅盤算子以增強(qiáng)算法的全局搜索能力.在原有的算子基礎(chǔ)上加入了一個(gè)迷失因子m1，表示鴿子的迷失概率.算法每次迭代都會(huì)生成一個(gè)隨機(jī)數(shù)，如果該隨機(jī)數(shù)小于m1則進(jìn)行迷失探索操作.鴿子進(jìn)入迷失狀態(tài)時(shí)，會(huì)進(jìn)行自由探索，首先隨機(jī)產(chǎn)生下一時(shí)刻的速度方向，經(jīng)過一定時(shí)間的探索飛行后，如果自身適應(yīng)度沒有向希望的方向變化，則改變飛行方向，然后重復(fù)迭代一段時(shí)間后，恢復(fù)可以探測(cè)到羅盤的狀態(tài).迷失狀態(tài)時(shí)位置速度更新公式：

diffitnessi(t)=fitnessi(t)-fitnessi(t-1).

(6)

(7)

(8)

式中：Vi(t)為當(dāng)前時(shí)刻速度；Vi(t-1)為上一時(shí)刻速度；Vmax為個(gè)體最大允許速度；diffitness為適應(yīng)度差值；bi為適應(yīng)度變化標(biāo)記.每次更新位置后，如果適應(yīng)度沒有減少，則標(biāo)記bi增加1點(diǎn)，連續(xù)3次適應(yīng)度沒有減少(即bi≥2),則更換飛行方向進(jìn)行探索，如果適應(yīng)度減少，則保持飛行方向探索且標(biāo)記bi置零.

(9)

綜上的鴿群優(yōu)化算法，算法流程如下：

(1)初始化種群和參數(shù)，隨機(jī)賦予每只虛擬鴿子的位置矢量和速度矢量并計(jì)算其適應(yīng)度值，確定全局最優(yōu).

(2)判斷如果迭代次數(shù)p=gencmax，則p=0，轉(zhuǎn)入步驟(7)，否則p=p+1,i=1并轉(zhuǎn)入步驟(3).

(3)判斷鴿子i的分裂狀態(tài)，若處于分裂狀態(tài)，則根據(jù)式(9)更新其速度和位置并轉(zhuǎn)入步驟6)；否則轉(zhuǎn)入步驟(4).

(4)生成隨機(jī)數(shù)rand，判斷是否rand

(5)生成隨機(jī)數(shù)rand，判斷是否rand

(6)計(jì)算鴿子適應(yīng)度，i=i+1，判斷是否i>Nmax，若是，轉(zhuǎn)入步驟(2)；否則轉(zhuǎn)入步驟(3).

(7)根據(jù)式(3)、(4)、(5)更新位置，計(jì)算鴿子適應(yīng)度，確定最優(yōu)解，迭代更新直至p=genlmax，輸出結(jié)果.

算法流程圖如圖1所示.迷失因子m1和分裂因子m2的選取直接影響算法的收斂性能，如果選取的因子過大，則種群會(huì)有更多的機(jī)會(huì)進(jìn)行探索，對(duì)全局的搜索能力更強(qiáng)，但收斂速度會(huì)變慢；反之收斂速度加快，但可能陷入局部最優(yōu)解.筆者建議m1與m2的取值分別為0.2和0.1.

圖1 LSPIO算法流程圖Fig.1 Flow chart of LSPIO algorithm

3 改進(jìn)優(yōu)化算法仿真實(shí)驗(yàn)

為測(cè)試筆者提出的LSPIO算法的有效性，下面將通過9個(gè)典型的標(biāo)準(zhǔn)測(cè)試函數(shù)[17]展開實(shí)驗(yàn)，同時(shí)與PIO算法和PSO算法進(jìn)行比較，3種算法種群規(guī)模和總迭代次數(shù)相同，并且在每次迭代過程中，每個(gè)個(gè)體都只評(píng)價(jià)一次個(gè)體適應(yīng)度.9個(gè)測(cè)試函數(shù)公式如下，圖2為測(cè)試函數(shù)三維示例圖.

(1) Sphere函數(shù)：

(10)

(2) Three-hump camel函數(shù)：

圖2 測(cè)試函數(shù)三維示例圖Fig.2 3D example of test function

-5≤x1,x2≤5.

(11)

(3) Rotated Schaffers函數(shù)：

(12)

(4) Rotated Weierstrass函數(shù)：

其中，a=0.5；b=3；kmax=20；

(13)

(5) Matyas函數(shù)：

-10≤xi≤10.

(14)

(6) Griewank函數(shù)：

-600≤xi≤600.

(15)

(7) Levy函數(shù)：

F7=2(x2-1)2(1+sin2(2πx2))+

(x1-1)2(1+sin2(3πx2))+

sin2(3πx1),-10≤x1,x2≤10.

(16)

(8) Easom函數(shù)：

F8=cosx1cosx2·

exp(-(x1-π)2+(x2-π)2),

-100≤x1,x2≤100.

(17)

(9) Eggholder函數(shù)：

-512≤x,y≤512.

(18)

其中函數(shù)F1、F2、F5是較為簡(jiǎn)單的單模態(tài)函數(shù)，函數(shù)F3和F4主要考慮了平移和旋轉(zhuǎn)對(duì)優(yōu)化算法的影響，F(xiàn)6、F7、F9是具有多個(gè)局部最優(yōu)的函數(shù)，F(xiàn)8的全局最小值較搜索空間小.

實(shí)驗(yàn)設(shè)置參數(shù)如下：3種算法種群大小都相同，粒子群算法(PSO)學(xué)習(xí)因子c1=2,c2=2；PIO算法地圖羅盤因子R=-0.02；LSPIO算法迷失因子和分裂因子m1=0.2,m2=0.1，分別將9個(gè)測(cè)試函數(shù)當(dāng)作目標(biāo)函數(shù)，進(jìn)行測(cè)試.

表1列出了用3種算法求解上述優(yōu)化問題運(yùn)行10次后得到的平均函數(shù)最優(yōu)解.從表1可以看出，對(duì)于簡(jiǎn)單函數(shù)和具有局部最優(yōu)陷阱函數(shù)，LSPIO算法的優(yōu)化結(jié)果優(yōu)于其他兩種算法，而對(duì)于旋轉(zhuǎn)函數(shù)，LSPIO的表現(xiàn)和其他兩種算法相當(dāng).

圖3為3種算法對(duì)函數(shù)優(yōu)化10次后的平均最佳適應(yīng)度演化曲線.為了驗(yàn)證上述結(jié)果差異是不是顯著性的，筆者將上述所得數(shù)據(jù)進(jìn)行假設(shè)檢驗(yàn).由于秩和檢驗(yàn)[18]具有易于理解、易于計(jì)算的優(yōu)點(diǎn)，筆者選用秩和檢驗(yàn)進(jìn)行驗(yàn)證.秩和檢驗(yàn)的基本思想：若檢驗(yàn)假設(shè)成立，則差值的總體分布應(yīng)是對(duì)稱的，故正負(fù)秩和不應(yīng)懸殊.分別對(duì)LSPIO、PIO和LSPIO、PSO進(jìn)行秩和檢驗(yàn)，當(dāng)前者優(yōu)于后者并且檢測(cè)P值小于0.05，則標(biāo)“+”號(hào)，表示前者優(yōu)于后者是顯著性的.當(dāng)后者優(yōu)于前者并且P值小于0.05，則標(biāo)“-”號(hào)，表示后者優(yōu)于前者是顯著性的.若檢測(cè)P≥0.05，則認(rèn)為它們差異不顯著.表2是統(tǒng)計(jì)檢驗(yàn)結(jié)果，從表2中可以看出，LSPIO在其中7個(gè)函數(shù)上的表現(xiàn)優(yōu)于PIO，證明LSPIO比PIO收斂性能更強(qiáng)；而與PSO相比，LSPIO也在6個(gè)函數(shù)上表現(xiàn)出更優(yōu)的性能.綜上所述，筆者提出的LSPIO算法表現(xiàn)出較好的全局搜索能力，可以有效避免早熟收斂問題.

表1 3種算法運(yùn)行10次平均最優(yōu)解Tab.1 The average optimal solution of three algorithms with 10 runs

注：加黑字體表示最接近最優(yōu)解的優(yōu)化結(jié)果.

圖3 最佳適應(yīng)度演化曲線Fig.3 Best fitness evolution curve

函數(shù)LSPIO vs PIOLSPIO vs PSOP值優(yōu)劣性比較P值優(yōu)劣性比較F11.8E-04+1.8E-04+F21.8E-04+1.6E-04+F37.6E-06+3.1E-04+F40.3E+00=0.9E+00=F52.4E-04+1.8E-04+F61.8E-01=3.8E-01=F71.5E-04+1.2E-04+F81.8E-04+0.8E+0=F90.1E-04+4.1E-04+-00+76=23

注：“+”號(hào)表示LSPIO顯著優(yōu)越；“-”號(hào)表示PIO/PSO顯著優(yōu)越；“=”表示兩者優(yōu)劣性無顯著差異.

為了評(píng)估算法的種群多樣性，定義了每一代的種群分布散度，其公式為:

(19)

式中：D為個(gè)體總維數(shù)；N為種群個(gè)體數(shù).

筆者計(jì)算了迭代過程中每代種群的分布散度，如圖4所示為9個(gè)測(cè)試函數(shù)分別運(yùn)行10次后取平均得到的種群分布散度-迭代次數(shù)曲線.可以看出在迭代過程中，LSPIO算法的種群分布散度顯著高于PSO和PIO，從而說明LSPIO算法保證了較好的種群多樣性.

圖4 種群分布散度演化曲線Fig.4 Evolution curve of divergence of population distribution

4 結(jié)論

筆者針對(duì)鴿群優(yōu)化算法的早熟收斂問題，提出了一種迷失探索與集群分裂機(jī)制的改進(jìn)鴿群優(yōu)化算法.這種優(yōu)化算法的靈感來源于實(shí)際中鴿群飛行的迷失探索和集群分裂現(xiàn)象.為了測(cè)試和對(duì)比算法性能，筆者選取9個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行函數(shù)優(yōu)化實(shí)驗(yàn)，并與標(biāo)準(zhǔn)鴿群算法和粒子群算法進(jìn)行了對(duì)比分析，在多個(gè)測(cè)試函數(shù)上的結(jié)果表明：筆者提出的LSPIO算法具有良好的全局搜索能力，有效避免了早熟收斂問題，且較好地保持了迭代過程中的種群多樣性.

筆者提出的算法雖然可以有效避免早熟收斂問題，但是它的收斂速度并不理想，并且只考慮了低維問題，接下來筆者將針對(duì)這兩方面的問題進(jìn)行深入研究，進(jìn)一步進(jìn)行算法改進(jìn)以提高收斂速度和優(yōu)化性能.