分類(lèi)覓食人工魚(yú)群算法

李　輝

(福建水利電力職業(yè)技術(shù)學(xué)院數(shù)學(xué)教研室， 福建 永安　366000)

?

分類(lèi)覓食人工魚(yú)群算法

李輝

(福建水利電力職業(yè)技術(shù)學(xué)院數(shù)學(xué)教研室， 福建 永安366000)

摘要：針對(duì)人工魚(yú)群算法搜索速度和搜索精度不高，且對(duì)高維問(wèn)題尋優(yōu)能力較差等缺點(diǎn)，提出了一種改進(jìn)的人工魚(yú)群算法——分類(lèi)覓食人工魚(yú)群算法(Assorted Foraging Artificial Fish Swarm Algorithm-AFAFSA)。該算法對(duì)執(zhí)行覓食行為的個(gè)體分類(lèi)進(jìn)行更新，既保持種群的多樣性又通過(guò)覓食行為加快算法的搜索速度，同時(shí)加入禁忌的思想幫助算法跳出局部最優(yōu)，提高算法的性能。通過(guò)一系列的測(cè)試試驗(yàn)，發(fā)現(xiàn)改進(jìn)算法在收斂速度和精度方面都有了明顯的提高，對(duì)于高維問(wèn)題有也具有較好的尋優(yōu)能力。

關(guān)鍵詞：人工魚(yú)算法；覓食行為；收斂速度；收斂精度

0引言

智能優(yōu)化算法由于其廣泛的適用性和良好的搜索效果，受到學(xué)者的廣泛關(guān)注。人工魚(yú)群算法是由李曉磊等[1,2]學(xué)者模擬魚(yú)類(lèi)行為提出的一種新的智能優(yōu)化算法，該算法模擬魚(yú)群的覓食、追尾等行為，實(shí)現(xiàn)全局優(yōu)化，是群體智能思想的一個(gè)具體應(yīng)用?；镜娜斯~(yú)群算法包括覓食、聚群、追尾3種行為，通過(guò)魚(yú)群選擇不同的行為搜索全局最優(yōu)值。文獻(xiàn)[1-3]的研究表明：對(duì)于較低維的問(wèn)題，該算法可以很好的跳出局部極值、快速搜索到全局極值，并且該算法有很多的優(yōu)點(diǎn)，比如對(duì)初始值和參數(shù)的選取要求不高，算法穩(wěn)定性比較高，而且算法更新機(jī)制簡(jiǎn)單、易操作也方便改進(jìn)以應(yīng)用于實(shí)際問(wèn)題。目前，該算法已經(jīng)應(yīng)用到許多領(lǐng)域。李曉磊[2]將其應(yīng)用于求解連續(xù)函數(shù)的優(yōu)化和組合優(yōu)化問(wèn)題；馬建偉等[4]將其應(yīng)用于神經(jīng)網(wǎng)絡(luò)的優(yōu)化，取得較好的效果；王正初等[5]將人工魚(yú)群算法應(yīng)用于水庫(kù)調(diào)度優(yōu)化；王會(huì)穎等[6]將該算法應(yīng)用于多維背包問(wèn)題的求解，取得較好的結(jié)果。但是人工魚(yú)群算法在實(shí)際應(yīng)用中也存在著以下幾點(diǎn)不足：1)當(dāng)尋優(yōu)區(qū)域較大或魚(yú)群處于較集中的區(qū)域時(shí)，算法的全局收斂速度減慢、精度降低；2)算法在優(yōu)化早期收斂速度較快，但是在優(yōu)化后期搜索結(jié)果改善較慢，搜索速度較低；3)算法對(duì)于高維問(wèn)題很難求得精確的最優(yōu)解；4)相對(duì)粒子群等算法而言，計(jì)算復(fù)雜度有待進(jìn)一步改善。

為了不斷改善基本算法的性能，擴(kuò)大算法的應(yīng)用范圍，很多學(xué)者對(duì)基本算法進(jìn)行了改進(jìn)，比如劉佳、劉麗娜、李靖等[7]將模擬退火算法融入魚(yú)群算法進(jìn)行改進(jìn)；許恒迎、孫偉斌、張霞等[8]通過(guò)調(diào)整人工魚(yú)的視野和步長(zhǎng)改善魚(yú)群算法的性能；祁俊、趙慧雅、李明等[9]通過(guò)混沌映射對(duì)魚(yú)群進(jìn)行初始化和擾動(dòng)，增強(qiáng)群體的多樣性；張嚴(yán)、楚曉麗[10]對(duì)魚(yú)群算法的覓食行為和擁擠因子進(jìn)行調(diào)整提高算法的性能。

1人工魚(yú)群算法

1.1行為描述

1.1.1覓食行為

設(shè)個(gè)體魚(yú)目前的位置為Xi，在其視野范圍內(nèi)隨機(jī)選擇一個(gè)位置Xj，若為求極小值優(yōu)化問(wèn)題，如果Yj

(1)

其中，rand(s)為個(gè)體移動(dòng)的步長(zhǎng)。否則，重新選擇一個(gè)位置Xj，判斷是否滿(mǎn)足移動(dòng)條件；重復(fù)幾次后，如果仍然不滿(mǎn)足移動(dòng)條件，則隨機(jī)移動(dòng)一步。

1.1.2聚群行為

設(shè)個(gè)體魚(yú)當(dāng)前所處的位置為Xi，尋找當(dāng)前鄰域內(nèi)(即dij

(2)

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

1.1.3追尾行為

設(shè)人工魚(yú)當(dāng)前的狀態(tài)為Xi，探索當(dāng)前鄰域內(nèi)(即dij

(3)

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

1.2行為選擇

按照需處理的問(wèn)題的特征，對(duì)人工魚(yú)當(dāng)前的情況進(jìn)行評(píng)估，經(jīng)分析后選取其中的一種行為執(zhí)行。比如求解最小值優(yōu)化問(wèn)題，最簡(jiǎn)單的評(píng)估方法就是試探法，即每次迭代中都分別試執(zhí)行聚群行為和追尾行為，然后比較不同行為的結(jié)果，選擇結(jié)果較好的、即目標(biāo)函數(shù)值更小的行為來(lái)實(shí)際執(zhí)行，缺省時(shí)即執(zhí)行覓食行為。

2分類(lèi)覓食人工魚(yú)群算法

基本人工魚(yú)群算法的覓食行為中，個(gè)體Xi在感知范圍內(nèi)隨機(jī)走一步，若更好就向該方向前進(jìn)一步，否則重新選擇一個(gè)狀態(tài)，嘗試幾次仍然不好，則隨機(jī)移動(dòng)一步，覓食行為是人工魚(yú)群算法中非常重要的行為，直接影響了算法的搜索速度和精度，但基本算法中覓食行為機(jī)制較簡(jiǎn)單，個(gè)體移動(dòng)速度較慢，會(huì)使算法性能受到影響。為了充分提高算法性能，在覓食行為中，對(duì)不同個(gè)體進(jìn)行不同處理，并進(jìn)一步提高個(gè)體移動(dòng)速度，即個(gè)體Xi在感知范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，若效果更好，則個(gè)體直接移動(dòng)到該新位置，否則，若該個(gè)體Xi不是當(dāng)前全局最優(yōu)個(gè)體Pb，則根據(jù)個(gè)體自身信息和當(dāng)前全局最優(yōu)個(gè)體信息按式(4)更新該個(gè)體位置，即：

Xi=rand()×Xi+rand()×(Pb-Xi)

(4)

其中，rand()為(0,1)之間的隨機(jī)數(shù)。對(duì)于全局最優(yōu)個(gè)體，在覓食行為中，隨機(jī)移動(dòng)一步，保持算法的多樣性。

在行為選擇中，缺省時(shí)執(zhí)行的是覓食行為，算法不能較好的跳出局部極值，因此，當(dāng)算法陷入局部極值，即算法的全局最優(yōu)值連續(xù)T次沒(méi)有發(fā)生變化時(shí)，則不執(zhí)行追尾行為和聚群行為，而是連續(xù)N次執(zhí)行覓食行為，讓人工魚(yú)自由游動(dòng)，避免過(guò)于集中，幫助算法盡快跳出局部極值。

該算法的計(jì)算流程如下：

Step1：初始化。在可行域內(nèi)隨機(jī)產(chǎn)生m個(gè)個(gè)體魚(yú)，選取個(gè)體魚(yú)之間的最大允許距離V，移動(dòng)步長(zhǎng)S，鄰域內(nèi)個(gè)體魚(yú)數(shù)目nf，擁擠度因子δ；設(shè)定全局最優(yōu)值連續(xù)未改變次數(shù)T和覓食行為執(zhí)行次數(shù)N。

Step2：若全局最優(yōu)解連續(xù)未改變次數(shù)小于或等于T，按式(2)和式(3)對(duì)魚(yú)群個(gè)體進(jìn)行聚群行為和追尾行為，選擇兩者效果好的最終執(zhí)行，否則按式(4)執(zhí)行覓食行為；若全局最優(yōu)解連續(xù)未改變次數(shù)大于T，則連續(xù)N次執(zhí)行覓食行為。記錄當(dāng)前全局最優(yōu)值。

Step3：判斷是否達(dá)到停機(jī)條件，若是，則停，輸出最優(yōu)解，否則轉(zhuǎn)Step2。

3仿真實(shí)驗(yàn)

3.1試驗(yàn)設(shè)計(jì)

為了測(cè)試分類(lèi)覓食人工魚(yú)群算法的性能，研究選取4個(gè)常用的測(cè)試函數(shù)(如下表1所示)，對(duì)基本人工魚(yú)群算法和改進(jìn)人工魚(yú)群算法進(jìn)行比較。其中：第一個(gè)和第二個(gè)函數(shù)為單極值函數(shù)，第三和第四個(gè)函數(shù)為多極值函數(shù)。它們的理論全局最優(yōu)值都是0。

基本人工魚(yú)群算法和改進(jìn)人工魚(yú)群算法都采用20個(gè)個(gè)體種群，最大全局迭代次數(shù)為200，參數(shù)設(shè)置如下：步長(zhǎng)S=0.2，最大允許距離V=0.52，鄰域內(nèi)個(gè)體魚(yú)數(shù)目nf=5，擁擠度因子δ=0.1，T=5，N=3。試驗(yàn)結(jié)果為獨(dú)立運(yùn)行20次后的平均值。

研究嘗試從以下幾方面對(duì)算法性能加以分析：(1)比較算法在收斂精度一定時(shí)的收斂速度；(2)比較算法在迭代次數(shù)一定時(shí)的收斂精度；(3)將本文算法的結(jié)果與相關(guān)文獻(xiàn)中的結(jié)果進(jìn)行對(duì)比。

表1　用于測(cè)試改進(jìn)算法的函數(shù)

3.2試驗(yàn)結(jié)果及分析

3.2.1收斂精度固定時(shí)的搜索次數(shù)

根據(jù)表1中的收斂精度，將算法獨(dú)立運(yùn)行20次，記錄每次運(yùn)行達(dá)到要求精度的迭代次數(shù)，比較不同算法對(duì)4個(gè)測(cè)試函數(shù)尋優(yōu)時(shí)的迭代次數(shù)如表2所示，其中min為最少迭代次數(shù)，max為最大迭代次數(shù)，mean為20次運(yùn)行中迭代次數(shù)的平均值；Success rate為成功率，即達(dá)到目標(biāo)精度的運(yùn)行次數(shù)占實(shí)驗(yàn)總次數(shù)的比率。

從表2的數(shù)據(jù)可以看出，基本人工魚(yú)算法對(duì)4個(gè)測(cè)試函數(shù)的搜索都無(wú)法達(dá)到表1給定的精度，即基本算法對(duì)于高維問(wèn)題的尋優(yōu)能力較差；文獻(xiàn)[8]中的算法雖然對(duì)4個(gè)測(cè)試函數(shù)都可以成功搜索到目標(biāo)精度下的最優(yōu)值，但所需的迭代次數(shù)非常多；文獻(xiàn)[11]中的算法對(duì)于4個(gè)測(cè)試函數(shù)的搜索成功率也較理想，但所需的迭代次數(shù)同樣很大；而改進(jìn)的分類(lèi)覓食人工魚(yú)算法對(duì)4個(gè)測(cè)試函數(shù)都有較高的搜索成功率，且所需的迭代次數(shù)相比較其它算法有了較大的減少。從總體上說(shuō)，改進(jìn)后的人工魚(yú)群算法(AFAFSA)在收斂速度上有很大的提高。

表2　在目標(biāo)精度下獨(dú)立運(yùn)行20次的迭代次數(shù)

3.2.2迭代次數(shù)固定時(shí)的收斂速度和精度

迭代次數(shù)固定為100次，4個(gè)測(cè)試函數(shù)的進(jìn)化曲線如圖1所示，為了方便觀察，對(duì)函數(shù)f1，f2的適應(yīng)度取對(duì)數(shù)后繪制進(jìn)化圖，為了防止產(chǎn)生對(duì)數(shù)無(wú)意義的現(xiàn)象，以10-6為最小值來(lái)限制適應(yīng)度的對(duì)數(shù)值，繪制結(jié)果如圖 (a)，(b)所示；函數(shù)f3和f4 直接繪制100次迭代的進(jìn)化圖如圖(c)，(d) 所示。其中橫軸為迭代次數(shù)，縱軸為適應(yīng)度值(或適應(yīng)度的對(duì)數(shù)值)，2支曲線分別表示AFSA和AFAFSA對(duì)4個(gè)測(cè)試函數(shù)的進(jìn)化曲線。

在上面(a)，(b)兩圖中，由于函數(shù)f1和f2的適應(yīng)度值數(shù)據(jù)跨度比較大，因此對(duì)適應(yīng)度取以10為底的對(duì)數(shù)，方便觀察。由圖中的曲線可以看出，AFAFSA比AFSA在收斂精度和收斂速度上都有非常大的提高，AFSA對(duì)4個(gè)測(cè)試函數(shù)在30維下都搜索不到最優(yōu)解，而AFAFSA對(duì)4個(gè)函數(shù)的搜索精度和搜索速度都非常好，說(shuō)明AFAFSA算法搜索速度快且精度高，而且對(duì)于很多優(yōu)化算法不能處理的高維問(wèn)題也有非常好的搜索速度和精度。

圖1　迭代100次時(shí)的收斂速度和精度Fig.1　The convergence speed and accuracy of 100 times'iteration

3.2.3與文獻(xiàn)報(bào)道的數(shù)據(jù)比較分析

表3是本文中的算法在進(jìn)化200次下，同文獻(xiàn)[12]和[13]中提出的改進(jìn)算法在30維下搜索到的平均最優(yōu)值的比較，由表3可以看出，AFAFSA比文獻(xiàn)中的算法有更高的收斂精度，且對(duì)函數(shù)3和4甚至可以搜索到理論最優(yōu)值。

表3　一些改進(jìn)粒子群算法性能比較

4結(jié)論

研究提出的改進(jìn)人工魚(yú)群算法，對(duì)魚(yú)群算法中的覓食行為進(jìn)行改進(jìn)，充分利用覓食行為的自由性，加快個(gè)體移動(dòng)速度，同時(shí)通過(guò)加強(qiáng)自由游動(dòng)增強(qiáng)種群多樣性，以提高算法搜索速度和精度。從實(shí)驗(yàn)結(jié)果可以看出：改進(jìn)人工魚(yú)群算法相對(duì)于基本人工魚(yú)群算法和一些文獻(xiàn)中的提出的算法，在搜索精度和速度上都有很大的提高。不論是對(duì)單極值函數(shù)還是對(duì)多極值函數(shù)，甚至高維問(wèn)題，算法都有很好的尋優(yōu)能力，并且該改進(jìn)算法搜索機(jī)制簡(jiǎn)單，穩(wěn)定性強(qiáng)，便于操作應(yīng)用，總體來(lái)說(shuō)，該算法性能較好、實(shí)用性很強(qiáng)。

參考文獻(xiàn)：

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

[2] 李曉磊.一種新型的智能優(yōu)化算法——人工魚(yú)群算法[D/OL].杭州:浙江大學(xué), 2003:35-62[2013-11-12].http://www.cnki.net/KCMS/detail/detail.aspx?QueryID=1&CurRec=1&recid=&filename=2003051212.nh&dbname=CDFD9908&dbcode=CDFD&pr=&urlid=&yx=&v=MDA0OTFOclpFYlBJUjhlWDFMdXhZUzdEaDFUM3FUcldNMUZyQ1VSTHlmWnVkdEZ5N2dVTHpMVjEyN0hiTzlIOVA=.

[3] 高尚,楊靜宇.群智能算法及其應(yīng)用[M].北京：中國(guó)水利水電出版社,2006.

[4] 馬建偉,張國(guó)立,謝宏，等.利用人工魚(yú)群算法優(yōu)化向前神經(jīng)網(wǎng)絡(luò)[J].計(jì)算機(jī)應(yīng)用,2004,24(10):21-23.

[5] 王正初,周慕遜,李軍，等.基于人工魚(yú)群算法的水庫(kù)優(yōu)化調(diào)度研究[J].繼電器,2007，35,11(21):43-47.

[6] 王會(huì)穎,倪志偉,陳祥生.基于魚(yú)群算法的多維背包問(wèn)題研究[J].安徽農(nóng)業(yè)科學(xué), 2011，39(10):6114-6117.

[7] 劉佳,劉麗娜,李靖,等.基于模擬退火算法的改進(jìn)人工魚(yú)群算法研究[J].計(jì)算機(jī)仿真,2011,28(10):195-198.

[8] 許恒迎,孫偉斌,張霞,等.自適應(yīng)視野和步長(zhǎng)的局部鄰域人工魚(yú)群算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(7):2815-2821.

[9] 祁俊,趙慧雅,李明.基于雙混沌映射改進(jìn)的人工魚(yú)群算法[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(9):230-233.

[10]張嚴(yán),楚曉麗.一種改進(jìn)的人工魚(yú)群算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2011，20(5):199-201

[11]王國(guó)聯(lián),洪毅,趙付青,等.一種簡(jiǎn)化的人工魚(yú)群算法[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30(8):1663-1667.

[12]WANG L G,HONG Y,SHI Q H.Global edition artificial fish swarm algorithm[J].Journal of System Simulation，2009,21,12(23):7483-7502.

[13]ZHAO P J,LIU S Y.Shuffled frog leaping algorithm for solving complex functions[J].Application Research of Computers,2009,26(7):2435-2437.

文章編號(hào)：1004—5570(2016)01-0093-05

收稿日期：2015-06-15

作者簡(jiǎn)介：李輝(1981-)，女，講師，碩士，研究方向：基礎(chǔ)數(shù)學(xué)教學(xué)及智能優(yōu)化算法方面的研究，E-mail：huili_0102@163.com.

中圖分類(lèi)號(hào)：O224

文獻(xiàn)標(biāo)識(shí)碼：A

Assorted foraging artificial fish swarm algorithm

LI Hui

(Fujian College of Water Conservancy and Electric Power，Yong’an， Fujian 366000，China)

Abstract:As the search speed and accuracy of the basic artificial fish swarm algorithm is not high and the optimization for high-dimensional problems is poor, a new improved artificial fish swarm algorithm which is called assorted foraging artificial fish swarm algorithm is proposed. The algorithm updates individuals which implement the foraging behavior assorted. This can maintain the diversity of the population and accelerate the search speed of the algorithm. The taboo idea is also added to help the algorithm escape from local optima and to improve the performance of the algorithm. A series of tests reveal that the assorted foraging artificial fish swarm algorithm is better than basic artificial fish swarm algorithm in convergence velocity and convergence precision. It also has high optimization ability for high-dimensional problems.

Key words:AFSA; foraging behavior; convergence velocity; convergence precision