(西南交通大學(xué)數(shù)學(xué)學(xué)院，四川 成都 611731)

·計算機(jī)軟件理論、技術(shù)與應(yīng)用·

一種新的小生境魚群優(yōu)化算法

徐翔燕，黃天民

(西南交通大學(xué)數(shù)學(xué)學(xué)院，四川 成都 611731)

針對魚群算法后期收斂速度慢和難以找到精確最優(yōu)解的缺點，結(jié)合進(jìn)化論中的小生境技術(shù)，提出一種新的小生境魚群優(yōu)化算法。通過魚群個體之間的距離找到具有相似距離的個體組成小生境種群，在該種群內(nèi)執(zhí)行魚群算法的聚群、追尾及覓食行為，所有個體經(jīng)過其小生境群體的進(jìn)化后，找到最優(yōu)的個體存到下一代的魚群中，直到找到滿意的適應(yīng)值。通過幾個典型的多峰測試函數(shù)驗證算法的性能。仿真結(jié)果表明，算法的收斂性、尋優(yōu)性均達(dá)到良好的效果。

魚群算法；小生境技術(shù)；多峰測試函數(shù)

人工魚群算法(artificial fish—swarm algorithm，AFSA)，是2002年由李曉磊等[1]提出的一種新型自適應(yīng)尋優(yōu)算法。AFSA算法具有對初值選擇不敏感、魯棒性強(qiáng)、全局收斂性好、簡單易實現(xiàn)和使用靈活等優(yōu)良性能。目前，人工魚群算法已應(yīng)用于組合優(yōu)化[2-3]、數(shù)據(jù)挖掘[4]、神經(jīng)網(wǎng)絡(luò)優(yōu)化[5]、信號處理[6]、水庫優(yōu)化調(diào)度[7]、圖象分割[8]等諸多領(lǐng)域，然而，隨著優(yōu)化問題的復(fù)雜化，基本人工魚群算法也存在不足:1)對于局部極值非常突出或收斂十分平緩的情況，人工魚易在局部極值或全局極值點附近過早的聚集，導(dǎo)致后期精度改善明顯變緩；2)視野和步長的隨機(jī)性和隨機(jī)行為的存在，使得尋優(yōu)難以得到很高的精度。針對魚群算法的不足，AFSA的改進(jìn)算法主要有以下幾個方面：1)引入生存機(jī)制和競爭機(jī)制[9]；2)動態(tài)調(diào)整人工魚的視野和步長[10]；3)與其他智能優(yōu)化算法融合[11-13]。

進(jìn)化論中，生物總是選擇與自己形狀、特征相近的物種聚在一起，并在同類中交配繁衍后代，“人以群分，物以類聚”是一種很常見的現(xiàn)象，而物種賴以生存的資源環(huán)境，我們稱之為小生境(niches)[14]。小生境技術(shù)中最著名且用得最多的就是1987年Goldberg等提出的基于共享機(jī)制(fitness sharing)的小生境實現(xiàn)方法(簡稱FSGA)[15]。該小生境技術(shù)的基本理論思想為：利用反映群體中個體之間的相似程度的共享函數(shù)調(diào)整群體中個體的適應(yīng)值，以保證群體多樣性，因而在以后的小生境群體的進(jìn)化過程中，算法能根據(jù)調(diào)整后的新的適應(yīng)值進(jìn)行選擇運算。

近年來，人們將小生境技術(shù)引入到遺傳算法、粒子群算法等智能優(yōu)化算法中，提高了算法的性能。為了避免魚群算法出現(xiàn)早熟現(xiàn)象，算法后期收斂速度慢，收斂精度低等缺點，本文提出一種新的小生境魚群算法優(yōu)化算法，其基本思想為：在每一代進(jìn)化前，根據(jù)魚群個體之間的距離劃分小生境種群，每個小生境種群由具有相似距離的個體組成，利用魚群算法更新小生境內(nèi)個體狀態(tài)。實驗仿真說明，該算法提高了收斂速度和精度。

1 基本人工魚群算法(AFSA)

在一片水域中，魚往往能通過視覺或嗅覺自行或尾隨其他魚找到食物濃度高的地方，所以魚聚集多的地方一般都是食物濃度高的地方。人工魚群算法就是根據(jù)魚的這一特性，模擬魚的覓食、聚群及追尾行為，從而實現(xiàn)尋優(yōu)。其數(shù)學(xué)模型描述如下：

1.1覓食行為

設(shè)人工魚當(dāng)前狀態(tài)為Xi，在其視野感知范圍內(nèi)隨機(jī)選擇一個狀態(tài)Xj，如果Yi

(1)

反之，則在其視野范圍內(nèi)重新選擇隨機(jī)狀態(tài)，判斷是否滿足前進(jìn)條件，反復(fù)嘗試Try-number次后，若仍不滿足前進(jìn)條件，則隨機(jī)移動一步：

Xi=Xi+Rand() 。

(2)

1.2聚群行為

設(shè)人工魚當(dāng)前狀態(tài)為Xi，搜索其視野感知范圍內(nèi)的伙伴數(shù)目nf及中心位置Xc，如果Yc>δ·Yi·nf(0<δ<1)，表明中心位置不太擁擠且中心位置狀態(tài)優(yōu)于當(dāng)前人工魚狀態(tài)，則向中心位置前進(jìn)一步：

(3)

否則，執(zhí)行覓食行為。

1.3追尾行為

設(shè)人工魚當(dāng)前狀態(tài)為Xi，搜索其視野感知范圍內(nèi)的伙伴數(shù)目nf及Ym最大的狀態(tài)Xm，若此時Ym>δ·Yi·nf(0<δ<1)，則狀態(tài)Xm優(yōu)于人工魚的當(dāng)前位置狀態(tài)，向Xm的位置前進(jìn)一步：

(4)

否則，執(zhí)行覓食行為。

2 小生境魚群優(yōu)化算法

小生境技術(shù)源于生物學(xué)中的小生境(Niche)概念，是指生物界中相同種類的個體生活在一起，共同繁衍后代，而不同種類的個體相互分離。小生境技術(shù)中最著名及用得最多的可能是1987年Goldberg等提出的基于共享機(jī)制(fitness sharing)的小生境實現(xiàn)方法(簡稱FSGA)[14]。所謂“共享”是指在特定環(huán)境中共同生存的同種生物分享有限的資源，生物之間通過協(xié)調(diào)達(dá)到共同進(jìn)化，對于適應(yīng)能力弱的生物，在資源不足的前提下，將會被逐漸淘汰。該小生境技術(shù)的基本理論思想為：利用反映群體中個體之間的相似程度的共享函數(shù)調(diào)整群體中個體的適應(yīng)值，以保證群體多樣性，因而在以后的小生境群體的進(jìn)化過程中，算法能根據(jù)調(diào)整后的新的適應(yīng)值進(jìn)行選擇運算。

新的小生境魚群優(yōu)化算法基本思想為：首先根據(jù)小生境技術(shù)確定小生境群體；然后在小生境群體中執(zhí)行魚群優(yōu)化算法對魚群進(jìn)行更新(其中魚群的群體最優(yōu)值僅在該小生境群體中起作用)；最后對于更新后的群體，利用共享機(jī)制提高個體的適應(yīng)度, 對于適應(yīng)度最低的個體，利用罰函數(shù)對相應(yīng)的魚群個體進(jìn)行處罰，保留每個魚群的群體最優(yōu)個體，直到滿足終止條件。

1)小生境群體的劃分。

對于人工魚個體Xi=(xi1,xi2,…,xin),i=1,2,…N, 它的小生境群體確定方式為：對于給定的σsh，若滿足dikσsh，則將該個體加入到小生境群體Xpi中。

其中，σsh為小生境半徑，

dik=‖Xi-Xk‖,k=1,2,…N。

(5)

2)魚群個體之間的共享函數(shù)。

個體i與個體j之間的共享函數(shù)sh(dij) 表達(dá)式如下：

(6)

其中，λ為控制函數(shù)的參數(shù)。

3)適應(yīng)值函數(shù)的更新。

經(jīng)調(diào)整后個體的適應(yīng)值為

(7)

算法流程如下：

步驟1 初始化人工魚群規(guī)模N、人工魚的初始位置X、視野Visual和步長Step、擁擠度因子δ、人工魚覓食的最大試探次數(shù)Try-number、最大迭代次數(shù)Lmax、小生境半徑σsh。

步驟2 確定小生境種群個體：

(2.1)置i=1；

(2.2)由公式(5)計算個體之間的距離；

(2.3)根據(jù)dik<σsh,k=i,i+1,…,N，確定小生境子群Xpi，其中pi為Xpi中元素的個數(shù)。

步驟3 根據(jù)魚群優(yōu)化算法對小生境群體進(jìn)行更新：

(3.1)人工魚通過執(zhí)行聚群、追尾、覓食行為更新自己的狀態(tài)，計算個體的食物濃度，其中群體最優(yōu)值是小生境群體的最優(yōu)值，不再是整個群體的最優(yōu)值；

(3.3)利用更新后的適應(yīng)值fj′及處罰函數(shù)對子群體中適應(yīng)度值低的個體進(jìn)行處罰；

(3.4)當(dāng)i+pi

步驟4 計算每條人工魚的適應(yīng)值，保留最優(yōu)的適應(yīng)值和個體，檢查是否達(dá)到優(yōu)化條件，如果達(dá)到最大迭代次數(shù)，則結(jié)束。否則，進(jìn)入下一個魚群的小生境群體進(jìn)行優(yōu)化。

步驟5 若沒有找到最優(yōu)值，則讓每條人工魚的小生境群體保留的最優(yōu)個體組成新的群體空間，重復(fù)步驟 2。

以上算法利用魚群個體的距離與小生境半徑的關(guān)系劃分人工魚的小生境群體，然后在小生境群體內(nèi)根據(jù)魚群算法對每條人工魚進(jìn)行狀態(tài)更新。對于更新后的群體，利用共享算法對適應(yīng)值進(jìn)行更新，對于適應(yīng)度最低的粒子利用處罰函數(shù)進(jìn)行處罰，最終得到最優(yōu)解。

3 算法的性能測試

為了驗證算法的有效性，將這種算法用于如下多峰函數(shù)進(jìn)行測試：

1)F1(schaffer’s function)

-10≤xi≤10。

此函數(shù)是極為困難的多峰值函數(shù)，雖然該函數(shù)僅在(0,0)處取得最小值，但此解附近有無窮多個局部極小值的解;因此，算法搜索極為困難。圖1為schaffer函數(shù)在-10≤xi≤10范圍內(nèi)的函數(shù)圖像。

圖1 schaffer函數(shù)圖像

2)F2(needle-in-a-haystack)

-5.12≤xi≤5.12。

此函數(shù)為典型的大海撈針類問題，在定義域范圍內(nèi)僅在(0,0)點處取得全局最優(yōu)解，而在點(-5.12,5.12)、(-5.12,-5.12)、(5.12,-5.12)、(5.12,5.12)處均能取得局部最優(yōu)解。圖2為函數(shù)在-5.12≤xi≤5.12范圍內(nèi)的函數(shù)圖像，由圖可以看出全局最優(yōu)解被次優(yōu)解包圍。

圖2 needle-in-a-haystack函數(shù)圖像

為了測試算法的性能，這里分別用AFSA算法和NAFSA算法求解上述測試函數(shù)，表1為所得的尋優(yōu)結(jié)果和平均運行時間。參數(shù)設(shè)置如下：魚群規(guī)模N=100，視野Visual=7，步長Step=0.8，擁擠度因子δ=0.5，最大試探次數(shù)Try-number=3，最大迭代次數(shù)Lmax=20，小生境半徑σsh=0.2。實驗結(jié)果如表1所示。

表1 AFSA算法和NAFSA算法計算結(jié)果

由表1可以看出，NAFSA算法的尋優(yōu)結(jié)果明顯好于AFSA算法，同時平均運行時間也比AFSA算法少。

4 結(jié)論

針對人工魚群算法優(yōu)化精度低和后期收斂速度慢等缺點，對其進(jìn)行改進(jìn)。與小生境技術(shù)結(jié)合，提出了一種新的小生境魚群優(yōu)化算法。該算法通過魚群個體之間的距離找到小生境群體，然后在小生境種群里執(zhí)行聚群、追尾及覓食行為，個體經(jīng)過進(jìn)化后最優(yōu)個體保存到下一代，最終找到滿意解。仿真結(jié)果表明，該算法有效可行。

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

[2]朱孔村.人工魚群算法在組合優(yōu)化問題中的應(yīng)用[D].濟(jì)南:山東大學(xué),2008.

[3]李曉磊,路飛,田國會,等.組合優(yōu)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報:工學(xué)版,2004,34(5):64-67.

[4]Zhang M F,Shao C,Li M J,et al.Mining Classification Rule with Artificial Fish Swarm[C]//Proceedings of the Sixth Word Congress on Intelligent Control and Automation.Dalian：[s.n.]，2006：5877-5881.

[5]劉耀年,李迎紅,劉俊峰,等.基于人工魚群算法的徑向基神經(jīng)網(wǎng)絡(luò)的研究[J].東北電力大學(xué)學(xué)報:自然科學(xué)版,2006,26(4):23-27.

[6]舒維杰,袁志剛,尹忠科.利用人工魚群算法實現(xiàn)基于MP的信號稀疏分解[J].計算機(jī)應(yīng)用研究,2009,26(1):66-73.

[7]白小勇,蘇華英,舒凱,等.人工魚群算法在水庫優(yōu)化調(diào)度中的應(yīng)用[J].水電能源科學(xué),2008,26(5):51-53.

[8]Ma M,Liang J H,Sun L,et al.SAR Image Segmentation Based on SWT and Improved AFSA[C]//Proceedings of the Third International Symposium on Intelligent Information Technology and Security Informatics.Jianggangshan:[s.n.],2010：146-149.

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

[10]王聯(lián)國,洪毅,趙付青,等.一種改進(jìn)的人工魚群算法[J].計算機(jī)工程,2008,34(19):192-194.

[11]修春波,張雨虹.基于蟻群與魚群的混合優(yōu)化算法[J].計算機(jī)工程,2008,34(14):206-208.

[12]張梅鳳,邵誠.多峰函數(shù)優(yōu)化的生境人工魚群算法[J].控制理論與應(yīng)用,2008,25(4):773-776.

[13]宋瀟瀟.求解大規(guī)模0-1背包問題的改進(jìn)人工魚群算法[J].西華大學(xué)學(xué)報：自然科學(xué)版,2013,32(4):5-9.

[14]Horn J. The Nature of Niching: Genetic Algorithms And The Evolution of Optimal, Cooperative Populations[D]. Urbana-Champaign:University of Illinois ,1997.

[15]Goldberg D E, Richardson J J. Genetic Algorithms with Sharing for Multimodal Function Optimization[C]// Proceedings of the Second International Conference.Genetic Algorithms:[s.n.] 1987: 41-49.

(編校：葉超)

NicheFishSwarmOptimizationAlgorithm

XU Xiang-yan,HUANG Tian-min

(DevelopmentofMathematic,SouthwestJiaotongUniversity,Chengdu611731China)

In order to deal with the problem of slow convergence speed and difficult to find the accurate optimal solutions, combined with the theory of niche technology, Niche Artificial Fish Swarm Algorithm(NAFSA) is proposed. Niche population is consisted by individual fishes which has similar distance. The algorithm performs swarm first and then follow and prey behavior of Artificial Fish Swarm Algorithm(AFSA) in this population, and find the best one deposit to the next generation until a satisfactory value is searched. Finally, the performance of the algorithm is verified through several multimodal function. The simulation results show that the convergence and the optimization of algorithm are achieved good effect.

artificial fish swarm algorithm(AFSA); niche; multimodal function

2014-06-28

徐翔燕(1990—)，女，碩士研究生，主要研究方向為優(yōu)化與決策。

TP183

：A

：1673-159X(2015)06-0064-03

10.3969/j.issn.1673-159X.2015.06.013