基于線性遞減權值更新的雞群算法

李春紅， 陸安江， 邵麗萍

(貴州大學 大數據與信息工程學院， 貴陽 550025)

0 引 言

隨著人工智能神經網絡的不斷發展，各類算法也相繼陸續涌現出來。如遺傳算法、模擬蝙蝠回聲定位行為提出的蝙蝠算法、差分進化算法、狼群算法等[1-2]。這些算法被廣泛應用于各個方面，如求函數最優解、減速器設計、最優路徑規劃問題等[3-5]。

雞群算法是由中國學者孟獻兵于2014年提出來[6-7]。該算法模擬了雞群的覓食行為，對雞群中存在的等級制度和行為進行了數學分析[8-9]。在此基礎上，韓斐斐等人[10]提出了一種全局優化的改進雞群算法，有效地提升了算法的收斂速度。吳定會等人[8，11]對雞群算法的收斂性進行了馬爾科夫鏈的分析，建立了Markov鏈數學分析模型。也有學者用雞群算法來解決神經網絡方面的問題。本文針對雞群算法容易陷入局部最優和收斂較慢的問題提出了一種改進型的算法[12-14]。并用6個基準函數來測試，再和目前的3種智能算法進行比較，以此來測試改進的雞群算法的有效性。實驗表明該改進型算法更容易收斂[15]。

1 基本的CSO算法

雞群算法(CSO)是受到已有群體智能算法的啟發而提出的一種模擬雞群生活習性，抽象化得出的新型群體智能算法。在實際生活中，雞群中存在著競爭關系，同時又存在著很嚴格的等級制度。雞群中每一個體所具有的優勢性能通過其所在位置對應的目標函數適應值來表示，也是待優化問題的最優解。按照雞群中適應度值的不同，將每個雞群都劃分有公雞、母雞和小雞三個等級。適應度最高的規定為公雞，適應度最低的規定為小雞，其余的雞規定為母雞。整個雞群中因為公雞起著領導作用，母雞會跟著公雞覓食。相應的公雞在雞群的覓食競爭中具有最大的優勢，母雞其次，而小雞處在最不利的位置，所以小雞需要跟隨與其有母親關系的母雞一起生活，母雞媽媽對其加以保護，以保證小雞能正常生活。

設覓食空間為D維，種群規模為pop，其中公雞數量為NR,母雞數量為HN，小雞數量為CN。這里給出算法設計的研究表述如下。

(1)公雞的位置更新。在公雞的覓食行為中，第i只公雞在第j維空間中經過t次覓食后的位置為xtij(i=1,2,3…,NR;j=1,2,3,…,D)，則經過t+1次覓食后的位置更新為：

xt+1ij=xtij*(1+Rand(0,σ2)),

(1)

k∈[1,N],k≠i.

(2)

其中，Rand(0，σ2)表示均值為0，方差為σ2的高斯分布；ε表示一個很小的平衡常數；k表示所有公雞中除去第i個個體外的任意一個個體。

(2)母雞的位置更新。在母雞的覓食行為中，第i只母雞在第j維空間中經過t次覓食后的位置為xij(i=1,2,3…,HN;j=1,2,3…,D)，則經過t+1次覓食后的位置更新為：

xt+1ij=xtij+S1*Rand*(xtr1,j+xtij)+

S2*(xtr2, j-xtij),

(3)

S1=exp((fi-fr1)/(abs(fi)+ε)),

(4)

S2=exp(fr2-fi),

(5)

其中，Rand∈(0,1)，r1是第i只母雞所在子群中的公雞個體，r2是從公雞和母雞中隨機選擇的個體，且r1≠r2。顯然，fi>fr1,fi>fr2，因此公式中S2<1

(3)小雞位置更新。在小雞的覓食行為中，小雞跟隨自己的母雞搜索食物，小雞的位置更新公式如下：

xt+1ij=xtij+FL*(xtm,j-xtij).

(6)

其中，xim, j(m∈[1,N])表示第i只小雞跟隨的母雞，FL表示小雞跟隨母雞尋找食物時的跟隨系數，由于個體之間的差異性，小雞的跟隨系數FL為[0,2]范圍內選擇的隨機數。

2 改進的CSO算法

2.1 引入權值公式

改進型的雞群算法主要是在公雞、母雞、小雞的位置更新公式中引入了權值，在母雞與小雞的位置更新公式中還引入了向自己群體里最優的個體學習的參數，這不僅可以解決收斂速度慢、易陷入局部最優問題，還可以使公式以更快的速度達到全局最優。權值更新公式如下：

(7)

對權值更新公式用Matlab2014(a)進行仿真分析，仿真分析結果如圖1所示。

圖1 權值變化趨勢

由圖1可以看到，此方法的權值變化范圍在0.6～0.9之間。最大慣性權值wmax取0.9，最小慣性權值wmin取0.6時算法的性能最好，t表示當前迭代次數，M表示最大迭代次數。

2.2 改進后雞群的位置更新公式

在整個雞群中公雞的適應度值是最高的，已經是各個群體中的最優個體，因此在公雞的位置更新公式中只引入了線性遞減慣性權值來提高算法的搜索能力。改進的公式如下：

xt+1ij=ω*xtij*(1+Rand(0,σ2))，

(8)

母雞數量在整個雞群中是最多的，所以在尋優精度和速度上發揮重要作用。母雞作為雞群中的紐帶，所以起著信息傳遞的作用。母雞的適應度值在群體中不高，所以在母雞的位置更新公式中引入慣性權值因子和向群體里面最優的個體學習，其中R是取(0，1)之間的隨機數。改進公式如下：

xt+1ij=ω*xtij+S1*Rand*(xtr1,j-xtij)+S2*

Rand*(xtr2,j-xtij)+R*(xtbest,j-xtij)，

(9)

小雞在整個雞群中適應度值是最低的，學習的空間很大，既可以向公雞學習，也可以向母雞學習，所以在小雞的位置更新公式中既引入了慣性權值因子，也引入了向全局最優個體學習的因子，R是取(0,1)之間的隨機數，改進的公式如下：

xt+1ij=ω*xtij+FL*(xtm, j-xtij)+R*(xtbest, j-xtij).

(10)

2.3 算法流程

改進集群算法設計流程如圖2所示。由圖2可知，改進后的算法流程表述詳見如下。

Step 1雞群規模假設為N，搜索空間維數為D，最大迭代次數為M。

Step 2計算N個個體的適應度值，并設置t=0。

Step 3如果mod(t,G)=0，按照個體適應度值的大小將整個雞群中的個體進行排序，并確定整個雞群的等級制度。

Step 4將整個雞群分為不同的組，母雞隨機選擇要跟隨的公雞，并確定小雞和母雞在一組中的關系。

Step 5更新各個雞群的位置。

Step 6計算個體的適應度值。

Step 7更新個體最優和全局最優。

Step 8置t=t+1，若達到最終條件，則轉

Step 9,否則，轉到Step 3。

Step 9輸出全局最優位置。

圖2 改進雞群算法流程圖

3 數值分析與實驗

3.1 測試函數和實驗設置

為了驗證改進雞群算法(ACSO)的有效性，本文選取了6個標準的測試函數進行仿真實驗，并與基本的雞群算法(CSO)、粒子群算法(PSO)、差分算法(DE)進行對比分析。測試函數的基本信息見表1，測試函數的參數設置見表2。

表1 基本測試函數

表2 各算法參數的設置

通過這6個基準函數的不同特點，可以充分考察改進的雞群算法對不同類型問題的優化性能。這幾個函數可以分為單峰函數(F1),多峰函數(F2～F6)，選取這些函數可以考察改進算法的收斂速度、收斂精度、有效性以及全局搜索能力。

3.2 結果分析

在Matlab2014(a)的環境下，對3.1節中表1、表2中的函數和算法進行仿真實驗。仿真實驗測試結果見圖3～圖8。

圖3 Sphere測試函數

圖4 Ackley測試函數

圖5 Griewank測試函數

圖6 Rastrigin測試函數

圖7 Zakharov測試函數

圖8 Shekel測試函數

通過上述結果可以看出，對于Sphere函數來說，ACSO明顯優于其余三種算法，在迭代次數到150次左右的時候就已經達到最優值。對于Ackley函數來說，在迭代次數到100左右即達到最優值，而且要勝過其余三種算法，對于Griewank函數來說，同樣明顯優于其余三種算法。對于Rastrigin函數來說，改進的ACSO稍微優于CSO算法，但是要顯著優于PSO、DE兩種算法。對于Zakharov測試函數來說，在迭代初期并沒有其他算法出色，但是到100代左右則明顯優于其余測試函數。對于Shekel測試函數，雖然起始并未優于DE和PSO算法，但是到迭代后期達到了最優值。總而言之，ACSO算法在函數尋優過程中，優于傳統的雞群算法、粒子群算法和差分算法。

4 結束語

通過對基本雞群算法的改進，可以得到一種更好的雞群算法。改進的雞群算法在保證種群多樣性的情況下，引入線性遞減權值，在母雞和小雞的更新公式中加入向最優個體學習的因子。如此更新后，通過6個測試函數進行實驗，與標準粒子群算法、差分算法、標準雞群算法三種基本算法做比較，由仿真實驗結果可以得到，在其收斂速度和迭代次數方面都有改善。