引入迷失探索與集群分裂機制的改進鴿群優(yōu)化算法

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

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

0 引言

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

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

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

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

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

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

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

在鴿群優(yōu)化算法中，首先運行地圖和羅盤算子，鴿子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是一個隨機數(shù)；Xg是當前全局最佳位置，可以通過比較所有鴿子中的所有位置來獲得;t表示當前迭代次數(shù).

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

(3)

(4)

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

(5)

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

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

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

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

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

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

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

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

(6)

(7)

(8)

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

(9)

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

(1)初始化種群和參數(shù)，隨機賦予每只虛擬鴿子的位置矢量和速度矢量并計算其適應度值，確定全局最優(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)生成隨機數(shù)rand，判斷是否rand

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

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

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

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

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

3 改進優(yōu)化算法仿真實驗

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

(1) Sphere函數(shù)：

(10)

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

圖2 測試函數(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是較為簡單的單模態(tài)函數(shù)，函數(shù)F3和F4主要考慮了平移和旋轉(zhuǎn)對優(yōu)化算法的影響，F(xiàn)6、F7、F9是具有多個局部最優(yōu)的函數(shù)，F(xiàn)8的全局最小值較搜索空間小.

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

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

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

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

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

圖3 最佳適應度演化曲線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

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

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

(19)

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

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

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

4 結論

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

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