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

陸俊明， 張向鋒

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

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

1 PSO原理

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

第i個粒子位置狀態(tài)為

第i個粒子速度為

第i個粒子歷史最好點

第k+1次迭代的粒子的數(shù)學描述為

(1)

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

2 AFSA原理

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

2.1 覓食行為

(2)

2.2 聚群行為

(3)

式中，δ是擁擠因子。

2.3 追尾行為

(4)

3 PSO-AFSA原理

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

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

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

(3) 利用PSO更新Xe，在PSO內(nèi)部進行nmax次尋優(yōu)；

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

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

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

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

算法流程如圖1所示。

圖1 PSO-AFSA流程圖

4 仿真結(jié)果與分析

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

4.1 基準測試函數(shù)及參數(shù)設(shè)置

(1) Sphere函數(shù)

(5)

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

表1 參數(shù)的設(shè)置

(2) Ackley函數(shù)

(6)

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

(3) Griewank函數(shù)

(7)

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

4.2 結(jié)果與分析

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

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

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

表2 3種算法仿真數(shù)據(jù)結(jié)果

圖2D為10時Sphere函數(shù)進化曲線

圖3D為10時Ackley函數(shù)進化曲線

圖4D為10時Griewank函數(shù)進化曲線

圖5D=20時Sphere函數(shù)進化曲線

圖6D=20時Ackley函數(shù)進化曲線

圖7D=20時Griewank函數(shù)進化曲線

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

圖8 精英魚群數(shù)對Sphere函數(shù)的影響

圖9 精英魚群數(shù)對Ackley函數(shù)的影響

圖10 精英魚群數(shù)對Griewank函數(shù)的影響

5 結(jié) 語

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