一種新的小生境魚群優化算法

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

·計算機軟件理論、技術與應用·

一種新的小生境魚群優化算法

徐翔燕，黃天民

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

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

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

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

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

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

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

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

1.1覓食行為

設人工魚當前狀態為Xi，在其視野感知范圍內隨機選擇一個狀態Xj，如果Yi

(1)

反之，則在其視野范圍內重新選擇隨機狀態，判斷是否滿足前進條件，反復嘗試Try-number次后，若仍不滿足前進條件，則隨機移動一步：

Xi=Xi+Rand() 。

(2)

1.2聚群行為

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

(3)

否則，執行覓食行為。

1.3追尾行為

設人工魚當前狀態為Xi，搜索其視野感知范圍內的伙伴數目nf及Ym最大的狀態Xm，若此時Ym>δ·Yi·nf(0<δ<1)，則狀態Xm優于人工魚的當前位置狀態，向Xm的位置前進一步：

(4)

否則，執行覓食行為。

2 小生境魚群優化算法

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

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

1)小生境群體的劃分。

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

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

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

(5)

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

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

(6)

其中，λ為控制函數的參數。

3)適應值函數的更新。

經調整后個體的適應值為

(7)

算法流程如下：

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

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

(2.1)置i=1；

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

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

步驟3 根據魚群優化算法對小生境群體進行更新：

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

(3.3)利用更新后的適應值fj′及處罰函數對子群體中適應度值低的個體進行處罰；

(3.4)當i+pi

步驟4 計算每條人工魚的適應值，保留最優的適應值和個體，檢查是否達到優化條件，如果達到最大迭代次數，則結束。否則，進入下一個魚群的小生境群體進行優化。

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

以上算法利用魚群個體的距離與小生境半徑的關系劃分人工魚的小生境群體，然后在小生境群體內根據魚群算法對每條人工魚進行狀態更新。對于更新后的群體，利用共享算法對適應值進行更新，對于適應度最低的粒子利用處罰函數進行處罰，最終得到最優解。

3 算法的性能測試

為了驗證算法的有效性，將這種算法用于如下多峰函數進行測試：

1)F1(schaffer’s function)

-10≤xi≤10。

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

圖1 schaffer函數圖像

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

-5.12≤xi≤5.12。

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

圖2 needle-in-a-haystack函數圖像

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

表1 AFSA算法和NAFSA算法計算結果

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

4 結論

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

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

[2]朱孔村.人工魚群算法在組合優化問題中的應用[D].濟南:山東大學,2008.

[3]李曉磊,路飛,田國會,等.組合優化問題的人工魚群算法應用[J].山東大學學報:工學版,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].東北電力大學學報:自然科學版,2006,26(4):23-27.

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

[7]白小勇,蘇華英,舒凱,等.人工魚群算法在水庫優化調度中的應用[J].水電能源科學,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]李曉磊,邵之江,錢積新.一種基于動物自治體的尋優模式：魚群算法[J].系統工程理論與實踐,2002,22(11):32-38.

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

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

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

[13]宋瀟瀟.求解大規模0-1背包問題的改進人工魚群算法[J].西華大學學報：自然科學版,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—)，女，碩士研究生，主要研究方向為優化與決策。

TP183

：A

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

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