人工魚(yú)群算法的改進(jìn)

唐 莉，張正軍，王俐莉

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

人工魚(yú)群算法的改進(jìn)

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

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

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

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

0 引 言

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

(1)算法在尋優(yōu)過(guò)程中的隨機(jī)行為，存在迂回搜索的問(wèn)題，對(duì)于求解多極值函數(shù)，由于隨機(jī)行為移動(dòng)步長(zhǎng)太小導(dǎo)致收斂速度慢甚至難以跳出局部最優(yōu)解。

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

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

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

1 基本人工魚(yú)群算法及參數(shù)擁擠度因子δ的性能分析

1.1 相關(guān)定義

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

1.2 基本行為

(1)覓食行為。

(2)聚群行為。

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

(3)追尾行為。

(4)隨機(jī)行為。

在需要移動(dòng)的人工魚(yú)視野范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)，然后向該方向移動(dòng)，該行為事實(shí)上是覓食行為的缺省行為：

(1)

1.3 擁擠度因子δ對(duì)算法性能的影響

1.3.1 擁擠度因子定義

1.3.2 參數(shù)δ的性能分析

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

2 改進(jìn)的人工魚(yú)群算法

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

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

根據(jù)上述分析，文中引入對(duì)稱正態(tài)隨機(jī)行為，采用正態(tài)分布隨機(jī)數(shù)調(diào)整隨機(jī)行為中的移動(dòng)步長(zhǎng)step，定義該隨機(jī)數(shù)的方差σ為：

σ=(‖f‖+ε)-1

(2)

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

2.2 自適應(yīng)擁擠度因子δ

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

(3)

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

(4)

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

2.3 改進(jìn)的人工魚(yú)群算法步驟

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

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

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

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

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

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

3 仿真實(shí)現(xiàn)

在Matlab7.0環(huán)境下，選取兩個(gè)經(jīng)典測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)。

實(shí)例1：函數(shù)。

(5)

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

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

圖1 AFSA實(shí)例1的收斂曲線

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

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

圖2 IAFSA實(shí)例1的收斂曲線

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

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

參數(shù)選擇：人工魚(yú)總數(shù)Np=60，迭代次數(shù)IT=200，步長(zhǎng)Step=0.2，嘗試次數(shù)trynumber=1，視野范圍Visual=2。

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

圖3 AFSA實(shí)例2的收斂曲線

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

圖4 IAFSA實(shí)例2的收斂曲線

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

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

4 結(jié)束語(yǔ)

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

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

[2] 王聯(lián)國(guó),洪 毅,施秋紅.全局版人工魚(yú)群算法[J].系統(tǒng)仿真學(xué)報(bào),2009,21(23):7483-7486.

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

[4] 劉彥君,江銘炎.自適應(yīng)視野和步長(zhǎng)的改進(jìn)人工魚(yú)群算法[J].計(jì)算機(jī)工程與應(yīng)用,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] 黃光球,王西鄧,劉 冠.基于網(wǎng)格劃分策略的改進(jìn)人工魚(yú)群算法[J].微電子學(xué)與計(jì)算機(jī),2007,24(7):83-86.

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

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

[11] 王聯(lián)國(guó),施秋紅.人工魚(yú)群算法的參數(shù)分析[J].計(jì)算機(jī)工程,2010,36(24):169-171.

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

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

[14] 陳廣洲,汪家權(quán),李傳軍,等.一種改進(jìn)的人工魚(yú)群算法及其應(yīng)用[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

時(shí)間：2016-10-24

全國(guó)統(tǒng)計(jì)科學(xué)研究計(jì)劃重點(diǎn)項(xiàng)目(2013LZ45)

唐 莉(1993-)，女，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘與分析；張正軍，博士，副教授，研究方向?yàn)閿?shù)據(jù)挖掘與分析。

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