唐 莉，張正軍，王俐莉

(1.南京理工大學 理學院，江蘇 南京 210094；2.海軍指揮學院 科研部，江蘇 南京 210016)

人工魚群算法的改進

唐 莉1，張正軍1，王俐莉2

(1.南京理工大學 理學院，江蘇 南京 210094；2.海軍指揮學院 科研部，江蘇 南京 210016)

人工魚群算法(AFSA)是一種新型隨機搜索優(yōu)化算法。通過初步的研究表明，該算法具有許多優(yōu)良的性質，但也有一些不足之處。針對均勻隨機行為和常數擁擠度因子而導致算法運行時間長或陷入局部最優(yōu)的問題，引入對稱正態(tài)隨機行為，自適應調整該行為參數，減少了由于迂回搜索導致的無用計算，也使人工魚可在解空間進行更為廣泛的搜索，提高了搜索效率。采用了自適應擁擠度因子并提出新的適應度函數，加快了系統(tǒng)滿意解的收斂速度，使數值解更加穩(wěn)定。實驗結果表明，與基本人工魚群算法相比，該方法具有明顯的優(yōu)越性。

隨機行為；擁擠度因子；適應度函數；人工魚群算法；優(yōu)化

0 引 言

隨著動物的進化，根據優(yōu)勝劣汰的自然法則，它們形成了各式各樣的生存方式，這些方式為人類帶來了許多靈感和啟發(fā)。一個動物集群通常定義為一群自治體的集合，自治體是指在自然環(huán)境中具備自身活動能力的一個實體。將自治體的概念引入動物優(yōu)化算法中，通過解決局部問題逐步達到解決最終問題的目的，從而形成人工魚群算法。該算法是由李曉磊等長時間通過對魚群生活習性的觀察而模仿魚類生存行動方式提出的，是一種基于動物行為的新型仿生優(yōu)化隨機搜索算法[1]，其歸納總結出符合魚群行為并適用于魚群算法的幾種典型行為：覓食行為、聚群行為、追尾行為和隨機行為。該算法根據“富含營養(yǎng)物質最多的地方一般是水域中魚生存數目最多的地方”這一特點來模擬各行為，從而實現全局優(yōu)化，是集群智能思想的一個具體應用，具有并行性、簡單性、快速性、較強的魯棒性和較好的收斂性等特點。但也存在不足之處：

(1)算法在尋優(yōu)過程中的隨機行為，存在迂回搜索的問題，對于求解多極值函數，由于隨機行為移動步長太小導致收斂速度慢甚至難以跳出局部最優(yōu)解。

(2)擁擠度因子δ與人工魚領域內伙伴的數目nf相結合決定人工魚群是否執(zhí)行追尾行為和聚群行為，避免人工魚過度擁擠而陷入局部極值，但在算法后期，固定數值的擁擠度因子會使得位于極值點附近的人工魚之間相互排斥，不能進行覓食、聚群和追尾行為，從而無法精確地逼近極值點。

2009年王聯國在基本人工魚群基礎上提出全局版人工魚群[2]；2007年范玉軍等對人工魚移動方式進行改進[3]；劉彥君等采用自適應視野和步長對人工魚群進行改進[4-6]，采用跳躍行為[7]；黃光球等利用網格劃分策略和禁忌搜索算法做了適當改進[8]，并證明了其全局性收斂[9-10]；2008年王聯國等基于領域正交交叉算子動態(tài)調整視野和步長[11]。

文中引入對稱正態(tài)行為，自適應調整正態(tài)分布方差，并提出新的自適應擁擠度因子對基本人工魚群算法進行改進。

1 基本人工魚群算法及參數擁擠度因子δ的性能分析

1.1 相關定義

人工魚狀態(tài)定義為X=(x1,x2,…,xn)，其中xi(i=1,2,…,n)為尋優(yōu)變量；每條人工魚當前食物濃度表示為Y=f(X)，其中Y為目標函數值，是一個關于xi的n元函數；任意兩條人工魚個體之間的距離表示為di,j=‖Xi-Xj‖；人工魚所能感應到的視野范圍表示為Visual；Step表示人工魚移動步長；δ表示擁擠度因子；Np表示魚群個數；trynumber表示嘗試次數。

1.2 基本行為

(1)覓食行為。

(2)聚群行為。

為了保證魚群的生存和躲避危害，魚在游動過程中會自然地聚集成群。在人工魚群算法中對每條人工魚做如下規(guī)定：一是避免每條人工魚相互之間過分擁擠；二是人工魚的移動盡量向臨近伙伴的中心靠攏。

(3)追尾行為。

(4)隨機行為。

在需要移動的人工魚視野范圍內隨機選擇一個狀態(tài)，然后向該方向移動，該行為事實上是覓食行為的缺省行為：

(1)

1.3 擁擠度因子δ對算法性能的影響

1.3.1 擁擠度因子定義

1.3.2 參數δ的性能分析

δ的引入避免了人工魚過度擁擠而陷入局部極值，與nf相結合，通過決定人工魚是否執(zhí)行追尾行為和聚群行為對尋優(yōu)產生影響。實驗證明[12]，δ越大，人工魚覓食或者隨機行為比較突出，擺脫局部極值能力越強；δ越小，聚群行為和追尾行為在尋優(yōu)過程中的作用逐漸凸顯，有利于提高極值的精確度。而由于每次迭代人工魚只向魚群中心位置或魚群最優(yōu)位置移動一步，因此影響了算法收斂速度。

2 改進的人工魚群算法

2.1 引入對稱正態(tài)隨機行為

在基本人工魚群算法中，覓食行為奠定了算法收斂的基礎，聚群行為提供了算法收斂的穩(wěn)定性，追尾行為增強了算法收斂的快速性和全局性，而隨機行為可以逃出局部極值域。然而對于一些多極值函數，特別是達到局部極值與全局最優(yōu)值的人工魚所處位置相差甚遠時：第一，若該人工魚X達到局部極值點，而隨機行為的步長過小，那么迭代多次仍然可能跳不出局部極值；第二，當人工魚X迭代至逼近局部極值的位置附近時，若根據該人工魚的行為評價選擇隨機行為，那么隨機移動步長的過小會使得人工魚X在局部最優(yōu)解的附近迂回，反之隨機移動步長的過大容易使得人工魚X跳過全局極值Xbest附近，從而增加收斂時間。

根據上述分析，文中引入對稱正態(tài)隨機行為，采用正態(tài)分布隨機數調整隨機行為中的移動步長step，定義該隨機數的方差σ為：

σ=(‖f‖+ε)-1

(2)

動態(tài)搜索增強了全局搜索能力，在一定程度上削弱了振蕩現象對優(yōu)化精度的影響并提高了收斂速度。

2.2 自適應擁擠度因子δ

隨著δ從大變小，人工魚逐漸從覓食行為或者隨機行為變?yōu)榫廴盒袨榛蜃肺残袨椋谶M行全局搜索迭代過程后逼近全局極值點，再逐步進行精確搜素，使結果更加準確。根據上述分析，針對聚群行為和追尾行為中的擁擠度因子δ，定義Xi在當前位置的適應度函數f(Xi)[13-14]為：

(3)

其中，N(Xi)表示當前人工魚視野范圍內感應到的人工魚個數；di,j表示任意兩條人工魚之間的距離，通常用歐幾里德距離；參數αi,j為：

(4)

采用指數式衰減變化策略[10]：δ=δ·T。其中，T=e-β·f(Xi)，β為一固定值，那么T稱為衰減因子。隨著迭代次數的增加，δ自適應減小，有利于提高搜索解的精度。

2.3 改進的人工魚群算法步驟

(1)初始參數設置，包括人工魚群的總數Np、每條人工魚的初始位置X、移動步長Step、視野范圍Visual、嘗試次數trynumber以及擁擠度因子δ。

(2)計算每條人工魚當前的目標函數值Y=f(X)，并在公告板中記錄所有函數值中全局最優(yōu)的人工魚狀態(tài)X。

(3)對每條人工魚評價即到達全局最優(yōu)的人工魚保持不動，未到達的進行移動并選擇所要執(zhí)行的行為，包括覓食行為、聚群行為、追尾行為和對稱正態(tài)隨機行為。

(4)將人工魚移動后與公告板中的值進行比較，更新每條人工魚目前所處的位置信息。

(5)更新全局最優(yōu)人工魚的狀態(tài)。

(6)根據循環(huán)條件，一般為判斷連續(xù)所得最優(yōu)目標函數值的均方差小于允許的誤差，或判斷聚在某個區(qū)域內的人工魚數目達到某個值(某個比例)，或判斷連續(xù)多次所獲取的值均不超過已尋找的極值的次數，或設置最大迭代次數等，則輸出結果，否則返回步驟(2)。

3 仿真實現

在Matlab7.0環(huán)境下，選取兩個經典測試函數進行實驗。

實例1：函數。

(5)

該函數在(0,0)處存在唯一極大值1，原點附近散布著一些局部極值。

參數選取：人工魚總數Np=20，迭代次數IT=50，步長Step=0.7，嘗試次數trynumber=5，視野范圍Visual=10。下面分別在圖1和圖2中給出基本人工魚群算法(AFSA)和改進人工魚群算法(IAFSA)公告板中最優(yōu)值的收斂曲線。其中，b_vaule曲線代表公告板最優(yōu)值，afs_value表示每經過一次迭代后所有人工魚中的最優(yōu)值。并在表1中記錄了兩種算法的執(zhí)行時間、最優(yōu)人工魚極值點(best_x，best_y)及公告板最優(yōu)值b_value。

圖1 AFSA實例1的收斂曲線

指標AFSAIAFSA執(zhí)行時間/s1.5910001.576000best_x3.322899e-001-1.723285e-001best_y-2.316029e-001-3.416143e-002b_value9.999037e-0019.999134e-001

從表1可以看出，在時間上IAFSA算法比AFSA加快1%，距極大值點(0，0)近0.229 356 9，且更加收斂于極大值1。

圖2 IAFSA實例1的收斂曲線

實例2：函數(Needle-in-a-haystack)。

該函數為典型的多極值問題，其中(0,0)點為全局極值點，且全局最優(yōu)值為3 600，(-5.12，5.12)、(-5.12，-5.12)，(5.12，-5.12)、(5.12，5.12)為函數的四個局部極值點，且局部極值為2 748.782 3。

參數選擇：人工魚總數Np=60，迭代次數IT=200，步長Step=0.2，嘗試次數trynumber=1，視野范圍Visual=2。

圖3、圖4分別為AFSA和IAFSA的收斂曲線，表2為對應的執(zhí)行時間、最優(yōu)人工魚位置(best_x，best_y)及公告板最優(yōu)值b_value。

圖3 AFSA實例2的收斂曲線

從表2可見，IAFSA算法比AFSA時間加快了1%，距極大值點(0,0)近0.008 938 7，且同樣更收斂于極大值1。

圖4 IAFSA實例2的收斂曲線

指標AFSAIAFSA執(zhí)行時間/s33.29000032.963000best_x-3.070736e-0022.420133e-002best_y2.586932e-0021.971042e-002b_value3.597964e+0033.599593e+003

綜上所述，基本人工魚群算法獲取的是近似最優(yōu)解，改進的人工魚群算法不僅縮短了算法運行時間，而且具有更好的穩(wěn)定性和更高的優(yōu)化精度。

4 結束語

人工魚群算法是一種新型隨機搜索優(yōu)化算法，具有許多優(yōu)良的性質。文中引入對稱正態(tài)隨機行為，對基本人工魚群算法中的隨機行為進行改進，減少了迂回搜索的無用計算，同時采用自適應擁擠度因子并提出新的適應度函數，加快了系統(tǒng)滿意解的確定。結果表明，與基本人工魚群算法相比，該方法有效可行。

[1] 李曉磊,邵之江,錢積新.一種基于動物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實踐,2002,22(11):32-38.

[2] 王聯國,洪 毅,施秋紅.全局版人工魚群算法[J].系統(tǒng)仿真學報,2009,21(23):7483-7486.

[3] 范玉軍,王冬冬,孫明明.改進的人工魚群算法[J].重慶師范大學學報:自然科學版,2007,24(3):23-26.

[4] 劉彥君,江銘炎.自適應視野和步長的改進人工魚群算法[J].計算機工程與應用,2009,45(25):35-37.

[5]JiangMingyan,MastorakisNE,YuanDongfeng.Multi-thresh-oldimagesegmentationwithimprovedartificialfishswarmalgorithm[C]//ProcofEuropeancomputingconference.AthensGreece:Springer-Verlag,2007.

[6] Jiang Mingyan,Yuan Dongfeng.Wavelet threshold optimization with artificial fish swarm algorithm[C]//Proceedings of 2005 international conference on neural networks.Piscataway,USA:IEEE Press,2005:569-572.

[7] Jiang Mingyan, Yuan Dongfeng, Francisco R,et al.Spread spectrum code estimation by artificial fish swarm algorithm[C]//Proc of IEEE international symposium on intelligent signal processing.Madrid,Spain:IEEE,2007.

[8] 黃光球,王西鄧,劉 冠.基于網格劃分策略的改進人工魚群算法[J].微電子學與計算機,2007,24(7):83-86.

[9] 黃光球,劉嘉飛,姚玉霞.人工魚群算法的全局收斂性證明[J].計算機工程,2012,38(2):204-206.

[10] Iisufescu M.Finite Markov processes and their application[M].Chichester,UK:Wiley Press,1980.

[11] 王聯國,施秋紅.人工魚群算法的參數分析[J].計算機工程,2010,36(24):169-171.

[12] 徐曉華,陳 崚.一種自適應的螞蟻聚類算法[J].軟件學報,2006,17(9):1884-1889.

[13] 朱 峰,陳 莉.一種改進的蟻群聚類算法[J].計算機工程與應用,2010,46(6):133-135.

[14] 陳廣洲,汪家權,李傳軍,等.一種改進的人工魚群算法及其應用[J].系統(tǒng)工程,2009,27(12):105-110.

Improvement of Artificial Fish Swarm Algorithm

TANG Li1,ZHANG Zheng-jun1,WANG Li-li2

(1.School of Science,Nanjing University of Science and Technology,Nanjing 210094,China; 2.Research and Development Section,Nanjing Naval Command Academy,Nanjing 210016,China)

Artificial Fish Swarm Algorithm (AFSA) is a new random search optimization algorithm.The preliminary study shows that it has many promising features,but also some disadvantages.Aiming at the problem of AFSA,such as long running time or being in local optimal,caused by uniformly random behavior and constant of congestion factor.Based on symmetric normality random behavior,self-adaption adjusts the parameter of this behavior,and a large number of unused circuitous searches are reduced,and a more complete search within solution space is obtained for artificial fishes so that a high search efficiency is arrived at.The self-adaption congestion factor is adopted and a new fitness function is porposed,increasing the convergence rate of satisfactory solution domain,making the result more stable.Results of experiments show that there is an obvious advantage for this improved method compared with the basic artificial fish-swarm algorithm.

random behavior;congestion factor;fitness function；artificial fish swarm algorithm;optimization

2016-01-27

2016-05-05

時間：2016-10-24

全國統(tǒng)計科學研究計劃重點項目(2013LZ45)

唐 莉(1993-)，女，碩士研究生，研究方向為數據挖掘與分析；張正軍，博士，副教授，研究方向為數據挖掘與分析。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1114.060.html

TP301.6

A

1673-629X(2016)11-0037-04

10.3969/j.issn.1673-629X.2016.11.008