一種改進的粒子群人工魚群算法

陸俊明， 張向鋒

(上海電機學院 電氣學院, 上海 201306)

群體智能行為是當今科學研究的一個熱點。人工魚群算法[1-4](Artificial Fish Swarm Algorithm, AFSA)和粒子群優化算法[5-7](Particle Swarm Optimization, PSO)都是群體智能算法[8]。AFSA跳出局部極值的尋優能力強，但迭代速度慢。PSO是模擬鳥類的覓食行為的仿生算法，具有快速收斂能力和簡單可行等優點，但是在算法的尋優后期很難跳出局部最優值。文獻[9-10]綜合利用PSO可移植性強和AFSA全局尋優能力強的特點得到一種改進的算法；文獻[11]利用最速下降法具有簡單、運算速度較快的優勢，提出了對精英加速的改進粒子群人工魚群算法(Particle Swarm Optimization-Artificial Fish Swarm Algorithm, PSO-AFSA)；文獻[12]在理論上證明PSO-AFSA的收斂性；文獻[13]將PSO-AFSA應用于采煤機的破碎率優化。PSO-AFSA可以用于解決列車運行調度問題[14]以及機器人路徑規劃問題[15]等。該改進的PSO-AFSA具有更加穩定快速的尋優能力，克服了AFSA后期收斂速度慢，高維度求解精度不高等問題。

1 PSO原理

PSO模仿鳥群的行為來尋最優解[5]。適應度函數值代表粒子在求解過程中的狀態結果。假設在D維的尋優空間存在由n個尋優粒子組成的種群，在第k次迭代后，其中：

第i個粒子位置狀態為

第i個粒子速度為

第i個粒子歷史最好點

第k+1次迭代的粒子的數學描述為

(1)

式中：k為迭代次數；c1和c2為慣性權重；ξ和η為在0到1之間內均勻分布的隨機數；設置粒子的飛行速度的下界、上界的值為-Vmax和Vmax。

2 AFSA原理

在AFSA中，人工魚有3種基本行為：覓食、聚群、追尾[1]。

2.1 覓食行為

(2)

2.2 聚群行為

(3)

式中，δ是擁擠因子。

2.3 追尾行為

(4)

3 PSO-AFSA原理

提出的PSO-AFSA綜合利用PSO和AFSA的特性，根據粒子的適應度值大小篩選出精英魚群與普通魚群，若求解最大值，則利用PSO對適應度值較大的精英人工魚群進行更新，在其內部進行nmax次循環，其余普通魚群利用AFSA更新，每輪更新之后利用排序選出新的精英魚群，直到滿足規定的迭代次數。PSO粒子具有飛行速度和慣性權重兩大屬性，速度使人工魚具備像粒子樣的飛行功能，可以加快算法的收斂；慣性權重使人工魚具備了承接先前速度的能力。設立精英魚群可以結合兩個算法的優點從而加快算法的收斂。PSO-AFSA計算流程如下：

(1) 隨機初始化N條人工魚，給定視野V，步長s，擁擠度因子δ，最大嘗試次數Nt，外部最大迭代次數Nmax等參數；

(2) 計算每條人工魚的適應度值Y，選出數量為Ne的精英魚群Xe，其他人工魚群為普通魚群Xn，并尋找適應度值Y最大的人工魚，記錄在公告板Yb；

(3) 利用PSO更新Xe，在PSO內部進行nmax次尋優；

(4) 對普通魚群進行聚群行為Fs和追尾行為Ff更新，選擇適應度值Y較大的作為更新結果；

(5) 比較Y和Yb，判斷適應度值Y有沒有變大，如果變大則更新Yb，否則利用覓食算子Fp對Xn進行更新；

(6) 將更新后的Xe與Xn的適應度值與公告板Yb進行比較，若更大，則將其賦予公告板Yb；

(7) 當所有人工魚進行更新完成之后，判斷是否達到終止條件(終止條件為達到最大迭代次數)，達到終止條件后輸出最優適應度函數值Yb，算法結束，否則轉步驟(3)。

算法流程如圖1所示。

圖1 PSO-AFSA流程圖

4 仿真結果與分析

本文用3個典型的多維度函數測試算法性能，這3個函數f(x)具有大量局部最小值，以及為0的全局最小值，利用算法尋找最小值，結果越接近0，說明算法的尋優能力越強。參數設置見表1，本文使用Matlab R2016a仿真，N為100，Nmax為1 000，當迭代達到Nmax時，算法輸出最優解。

4.1 基準測試函數及參數設置

(1) Sphere函數

(5)

式中，x?[-10,10]。

表1 參數的設置

(2) Ackley函數

(6)

式中：x?[-32.768,32.768]；a=b=c=d=1。

(3) Griewank函數

(7)

式中，x?[-5,5]。

4.2 結果與分析

為了消除算法的隨機性干擾，在維數D為10和20維時，對每個函數分別用AFSA、PSO-AFSA各自獨立進行20次實驗(見表2)。

由表2可知隨著維數增大，AFSA與PSO-AFSA的尋優精度都大幅下降，但是PSO-AFSA的尋優精度始終遠遠優于AFSA。對函數Ackley，隨著維數由10增大至20，AFSA的平均尋優結果由10.021 81增大至20.032 77，PSO-AFSA的平均尋優結果由0.152 39增大至0.305 02，均增大至2倍。對函數Sphere，隨著維數由10增大至20，AFSA的平均尋優結果由2.258 39增大至6.082 99，PSO-AFSA的平均尋優結果由0.010 07增大至 0.036 33，均增大至3倍。綜合Ackley和Sphere可知，隨著維數增大，AFSA和PSO-AFSA的表現一致。但是對于函數Griewank，隨著維數由10增大至20，AFSA的平均尋優結果由0.083 99增大至0.255 04，PSO-AFSA的平均尋優結果由0.004 29增大至0.008 65，AFSA的平均尋優結果增大至3倍，而PSO-AFSA的平均尋優結果增大至2倍，說明PSO-AFSA相對于AFSA在該函數下對維度變化適應性更好。圖2～圖7為3個目標函數在不同維數時的優化結果圖，其中橫軸為迭代次數，縱軸為log化的函數最優解。

根據圖2和圖5可以看出，對目標函數Sphere，PSO-AFSA較早地找到了最優值，AFSA在700次以后才收斂，收斂速度太慢。由圖3和圖6可看出，對目標函數Ackley，AFSA的效果不理想，一開始就陷入局部最優；由圖4和圖7可以看出，對目標函數Griewank，PSO-AFSA迭代100次前效果明顯，AFSA的最終結果遠大于PSO-AFSA；結合圖2～圖7可以看出在1 000次迭代情況下，AFSA尋優效果遠小于PSO-AFSA，且AFSA更容易陷入局部最優解，AFSA在高維度的表現不佳，而PSO-AFSA在高維度尋優上迭代速度快，尋優結果更準確，有較大優勢。

表2 3種算法仿真數據結果

圖2D為10時Sphere函數進化曲線

圖3D為10時Ackley函數進化曲線

圖4D為10時Griewank函數進化曲線

圖5D=20時Sphere函數進化曲線

圖6D=20時Ackley函數進化曲線

圖7D=20時Griewank函數進化曲線

為了深入研究人工魚群的搜索過程，分析精英魚群數對PSO-AFSA所起到的作用，在其他參數不變的情況下，分別采用精英魚群數Ne為30、50和70 3種模式，利用PSO-AFSA進行20維尋優。由圖8和圖9可知，精英魚群數為50時算法迭代效果較好；由圖10可知，精英魚群數為70時算法迭代效果較好。綜合分析可知，為了平衡算法迭代效果，精英魚群數不應過大也不應過小。隨著算法繼續迭代，不同比例的精英魚群對算法結果的影響區別不大。

圖8 精英魚群數對Sphere函數的影響

圖9 精英魚群數對Ackley函數的影響

圖10 精英魚群數對Griewank函數的影響

5 結 語

針對AFSA在高維度尋優上表現不佳，提出了PSO-AFSA，并利用AFSA和PSO-AFSA兩種算法對3個基準測試函數尋優。對比迭代圖形和尋優結果，仿真結果表明：隨著維度上升，PSO-AFSA和AFSA尋優精度都會下降，但PSO-AFSA相對于AFSA表現更穩定，且不同精英魚群數對PSO-AFSA的影響較小，PSO-AFSA在收斂速度和結果都明顯優于AFSA。