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

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

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

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

徐翔燕，黃天民

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

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

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

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

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

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

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

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

1.1覓食行為

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

(1)

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

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

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

1)小生境群體的劃分。

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

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

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

(5)

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

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

(6)

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

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

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

(7)

算法流程如下：

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

步驟2 確定小生境種群個(gè)體：

(2.1)置i=1；

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

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

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

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

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

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

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

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

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

3 算法的性能測(cè)試

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

1)F1(schaffer’s function)

-10≤xi≤10。

此函數(shù)是極為困難的多峰值函數(shù)，雖然該函數(shù)僅在(0,0)處取得最小值，但此解附近有無窮多個(gè)局部極小值的解;因此，算法搜索極為困難。圖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)點(diǎn)處取得全局最優(yōu)解，而在點(diǎn)(-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ù)圖像

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

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

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

4 結(jié)論

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

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

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

[3]李曉磊,路飛,田國會(huì),等.組合優(yōu)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報(bào):工學(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é)報(bào):自然科學(xué)版,2006,26(4):23-27.

[6]舒維杰,袁志剛,尹忠科.利用人工魚群算法實(shí)現(xiàn)基于MP的信號(hào)稀疏分解[J].計(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]李曉磊,邵之江,錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22(11):32-38.

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

[11]修春波,張雨虹.基于蟻群與魚群的混合優(yōu)化算法[J].計(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é)報(bào)：自然科學(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àn)閮?yōu)化與決策。

TP183

：A

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

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