陸俊明， 張向鋒

(上海電機(jī)學(xué)院 電氣學(xué)院, 上海 201306)

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

1 PSO原理

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

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

第i個(gè)粒子速度為

第i個(gè)粒子歷史最好點(diǎn)

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

(1)

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

2 AFSA原理

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

2.1 覓食行為

(2)

2.2 聚群行為

(3)

式中，δ是擁擠因子。

2.3 追尾行為

(4)

3 PSO-AFSA原理

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

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

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

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

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

(5) 比較Y和Yb，判斷適應(yīng)度值Y有沒(méi)有變大，如果變大則更新Yb，否則利用覓食算子Fp對(duì)Xn進(jìn)行更新；

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

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

算法流程如圖1所示。

圖1 PSO-AFSA流程圖

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

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

4.1 基準(zhǔn)測(cè)試函數(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é)果與分析

為了消除算法的隨機(jī)性干擾，在維數(shù)D為10和20維時(shí)，對(duì)每個(gè)函數(shù)分別用AFSA、PSO-AFSA各自獨(dú)立進(jìn)行20次實(shí)驗(yàn)(見(jiàn)表2)。

由表2可知隨著維數(shù)增大，AFSA與PSO-AFSA的尋優(yōu)精度都大幅下降，但是PSO-AFSA的尋優(yōu)精度始終遠(yuǎn)遠(yuǎn)優(yōu)于AFSA。對(duì)函數(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倍。對(duì)函數(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)一致。但是對(duì)于函數(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倍，說(shuō)明PSO-AFSA相對(duì)于AFSA在該函數(shù)下對(duì)維度變化適應(yīng)性更好。圖2～圖7為3個(gè)目標(biāo)函數(shù)在不同維數(shù)時(shí)的優(yōu)化結(jié)果圖，其中橫軸為迭代次數(shù)，縱軸為log化的函數(shù)最優(yōu)解。

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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