分組進(jìn)化人工魚群算法

李輝

（福建水利電力職業(yè)技術(shù)學(xué)院 公共基礎(chǔ)部數(shù)學(xué)教研室，福建 永安 366000）

分組進(jìn)化人工魚群算法

李輝

（福建水利電力職業(yè)技術(shù)學(xué)院 公共基礎(chǔ)部數(shù)學(xué)教研室，福建 永安 366000）

針對(duì)人工魚群算法搜索性能較差的缺陷，結(jié)合粒子群、蛙跳和人工魚群算法的優(yōu)點(diǎn)，文章提出了一種分組進(jìn)化人工魚群算法，該算法將人工魚群算法簡(jiǎn)化后，仿照蛙跳算法進(jìn)行分組進(jìn)化，并加入粒子群算法的更新機(jī)制對(duì)個(gè)體位置進(jìn)行更新，以便充分利用種群信息.實(shí)驗(yàn)證明，該算法有較強(qiáng)的尋優(yōu)能力，且穩(wěn)定性好，實(shí)用性強(qiáng).

分組進(jìn)化；擁擠度；覓食行為；尋優(yōu)性能

優(yōu)化算法是一種以數(shù)學(xué)為基礎(chǔ)，求解各類實(shí)際問題最優(yōu)值的技術(shù).隨著計(jì)算機(jī)技術(shù)的不斷進(jìn)步，優(yōu)化技術(shù)得到了長(zhǎng)足發(fā)展，已被廣泛地應(yīng)用到了眾多領(lǐng)域.近年來，模擬生物行為的智能優(yōu)化算法漸漸被眾多學(xué)者所關(guān)注，智能優(yōu)化算法較多，如粒子群算法、蛙跳算法、人工魚群算法、蟻群算法、遺傳算法等等.智能優(yōu)化算法作為一種隨機(jī)搜索算法，由于對(duì)初始值、梯度等信息沒有過多要求，因而可以較好地解決具有復(fù)雜性、約束性、非線性、多極值等特點(diǎn)的工程問題，且這類算法容易與實(shí)際問題結(jié)合，應(yīng)用領(lǐng)域非常廣泛，如生產(chǎn)調(diào)度、系統(tǒng)控制、人工智能、模式識(shí)別和計(jì)算機(jī)工程等多種領(lǐng)域，如林智華[1]等利用粒子群算法研究數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度，楊薪冉等[2]將蛙跳算法應(yīng)用于船舶電力系統(tǒng)勵(lì)磁控制，取得了良好的效果.

粒子群算法是Kennedy和Eberhart[3]于1995年提出的，它在每次迭代時(shí)記錄群體最優(yōu)和當(dāng)前種群極優(yōu)，并結(jié)合個(gè)體自身信息、歷史最優(yōu)個(gè)體信息和當(dāng)前迭代中極優(yōu)個(gè)體的信息對(duì)個(gè)體進(jìn)行位置更新.算法在搜索過程中有極高的搜索速度，但算法在搜索后期容易陷入局部極值，特別是對(duì)于高維問題容易陷入“維度災(zāi)難”，無法搜索到最優(yōu)值.針對(duì)該算法，很多學(xué)者進(jìn)行了改進(jìn)和應(yīng)用研究：李勝等[4]將軌跡擾動(dòng)因子引入粒子群算法，提高了算法的性能；馮浩等[5]采用自適應(yīng)的慣性權(quán)重，改善了粒子群算法的搜索性能.粒子群算法是目前優(yōu)化算法的研究熱點(diǎn)之一.

人工魚群算法是由李曉磊等[6]學(xué)者模擬魚類行為提出的一種智能優(yōu)化算法，它是群體智能思想的一個(gè)具體應(yīng)用.人工魚群算法模擬魚群覓食行為，通過追尾行為、聚群行為和覓食行為對(duì)問題進(jìn)行尋優(yōu)，并利用擁擠度因子選擇其中一種行為對(duì)個(gè)體進(jìn)行位置更新，這種有針對(duì)性地選擇個(gè)體行為的機(jī)制，有效地避免了算法陷入局部極值的缺陷.該算法由于其新穎的尋優(yōu)機(jī)制，在提出后受到了很多學(xué)者的關(guān)注，但基本算法搜索機(jī)制相對(duì)復(fù)雜，搜索性能較差，特別對(duì)高維問題，尋優(yōu)效果非常差，因而很多學(xué)者對(duì)算法的改進(jìn)進(jìn)行了研究：李小培等[7]在覓食、聚群、追尾行為中用歷史全局最優(yōu)人工魚的位置和感知區(qū)域內(nèi)較優(yōu)位置的和向量，代替感知區(qū)域內(nèi)較優(yōu)位置，提高了算法的全局尋優(yōu)能力；易新兵[8]采用具遍歷性的組合映射產(chǎn)生復(fù)合混沌的局部搜索方法來跳出局部最優(yōu)，取得了較好的效果；吳昌友[9]引入自適應(yīng)步長(zhǎng)和變異策略幫助算法跳出局部最優(yōu)，提高了算法的性能；黃美華等[10]使用自適應(yīng)步長(zhǎng)代替原算法中的固定步長(zhǎng)，提高了算法的收斂速度，并將改進(jìn)算法應(yīng)用到多目標(biāo)背包問題中，取得了良好的效果；王麗等[11]通過引入視野遞減反饋策略改進(jìn)人工魚群算法，平衡了算法的全局搜索和局部搜索能力，提高了算法的搜索精度；易正俊等[12]在算法每次迭代中不斷加入新個(gè)體，并動(dòng)態(tài)調(diào)整擁擠度因子的上限值，提高了算法的整體性能，等等.

蛙跳算法是由Eusuff和Lansey[13]在2003年提出的，它是模擬青蛙覓食的一種基于群體智能的啟發(fā)式算法，它根據(jù)群體中個(gè)體的適應(yīng)度大小，將種群分為若干小組，每個(gè)小組中的個(gè)體都按照從優(yōu)到劣的順序排列，每次迭代時(shí)，只對(duì)組內(nèi)最差個(gè)體進(jìn)行位置更新.由于蛙跳算法的搜索分組進(jìn)行，相當(dāng)于引入了并行搜索機(jī)制，因而有較高的搜索效率；同時(shí)經(jīng)過若干次搜索后又將所有個(gè)體重新分組，整合了各小組之間的信息，體現(xiàn)了群體的協(xié)同工作性，因而有較快的搜索速度；但蛙跳算法每次只更新組內(nèi)最差個(gè)體，未充分體現(xiàn)群體中每個(gè)個(gè)體的價(jià)值，也沒有充分利用群體信息，因而容易陷入局部最優(yōu)，同時(shí)在算法陷入局部最優(yōu)的時(shí)候，沒有跳出機(jī)制，影響了算法的性能.另外，對(duì)于多極值函數(shù)，蛙跳算法搜索精度也不高.該算法由于其機(jī)制簡(jiǎn)單、容易改造，方便與其它算法結(jié)合，也較容易應(yīng)用到實(shí)際問題中去，因此，也成為目前關(guān)注的熱點(diǎn).

本文將粒子群算法、蛙跳算法和人工魚群算法相結(jié)合，形成了一種新的優(yōu)化算法——分組進(jìn)化人工魚群算法（grouping evolutionary artificial fish swarm algorithm，GEAFSA），這種組合算法充分利用了粒子群、蛙跳和人工魚群算法的優(yōu)點(diǎn)，避免了各算法的一些缺陷.實(shí)驗(yàn)證明，結(jié)合后的算法性能得到了很大的提高.

1 分組進(jìn)化人工魚群算法

分組進(jìn)化人工魚群算法仿照蛙跳算法，讓種群分組進(jìn)化，并將人工魚群算法的思想簡(jiǎn)化為在個(gè)體不擁擠時(shí)執(zhí)行追尾行為，在個(gè)體擁擠時(shí)執(zhí)行覓食行為，同時(shí)，為了充分利用個(gè)體和各小組的信息，對(duì)人工魚群算法中的追尾行為和覓食行為進(jìn)行了改進(jìn)：在追尾行為中，組內(nèi)最優(yōu)個(gè)體參照自身信息和全局最優(yōu)個(gè)體信息進(jìn)行位置更新，其余個(gè)體則仿照粒子群算法個(gè)體更新機(jī)制，參照自身信息、組內(nèi)最優(yōu)個(gè)體和全局最優(yōu)個(gè)體信息進(jìn)行位置更新，以保證充分利用群體信息，提高搜索性能；在覓食行為中，隨機(jī)產(chǎn)生新個(gè)體，若新個(gè)體更優(yōu)，則替代原個(gè)體，嘗試若干次仍沒有改進(jìn)時(shí)，隨機(jī)產(chǎn)生一個(gè)新的個(gè)體代替原個(gè)體.改進(jìn)算法中的擁擠度是具體到組內(nèi)的，組內(nèi)的擁擠度用下式來計(jì)算，

其中，δ是組內(nèi)擁擠度，fb為組內(nèi)最優(yōu)個(gè)體的適應(yīng)度，fi為組內(nèi)第i個(gè)個(gè)體的適應(yīng)度，n為組內(nèi)個(gè)體數(shù).當(dāng)組內(nèi)過于擁擠時(shí)，組內(nèi)所有個(gè)體執(zhí)行覓食行為.組內(nèi)進(jìn)化若干次后，再將所有個(gè)體按適應(yīng)度重新分組進(jìn)行位置更新，直到找到最優(yōu)解.

組內(nèi)個(gè)體的位置更新由下述賦值表達(dá)式給出：

其中，xb為組內(nèi)最優(yōu)個(gè)體，g為種群全局最優(yōu)個(gè)體，xi（i＝1，2，…，n，i≠b）為組內(nèi)非最優(yōu)個(gè)體，r1,r2,r3∈rand[0,1]，即，最優(yōu)個(gè)體根據(jù)式（2）進(jìn)行位置更新，而組內(nèi)其余個(gè)體根據(jù)式（3）進(jìn)行更新.

該算法的基本步驟如下：

Step1：初始化.在定義域內(nèi)產(chǎn)生F＝m×n個(gè)可行解作為初始個(gè)體，其中m為子族群數(shù)，每個(gè)子族群中有n個(gè)個(gè)體；定義擁擠度δ0，嘗試次數(shù)try number，全局搜索代數(shù)K和局部搜索代數(shù)L；

Step2：計(jì)算每個(gè)個(gè)體的適應(yīng)度，按適應(yīng)度從小到大排序，記錄排在第一位的個(gè)體為全局最優(yōu)個(gè)體，并將所有個(gè)體分為m組，即第km+i（k＝0，1，…，n-1；i＝1，2，…，m）個(gè)個(gè)體分配到第i組，循環(huán)分配直到所有個(gè)體都分配完畢；

Step3：判斷局部搜索次數(shù)是否已經(jīng)達(dá)到，若未達(dá)到，轉(zhuǎn)Step4，否則，轉(zhuǎn)Step5；

Step4：用式（1）計(jì)算組內(nèi)個(gè)體的擁擠度，若擁擠度大于δ0，則說明組內(nèi)不擁擠，按（2）更新組內(nèi)最優(yōu)個(gè)體，按式（3）更新組內(nèi)其它個(gè)體；否則，針對(duì)每個(gè)個(gè)體，隨機(jī)產(chǎn)生新解xnew，若xnew優(yōu)于原個(gè)體，則用xnew代替原個(gè)體，否則不替換，嘗試try number次后，若仍然沒有找到更優(yōu)個(gè)體，則隨機(jī)產(chǎn)生新個(gè)體代替原個(gè)體.轉(zhuǎn)step3；

Step5：判斷全局搜索次數(shù)是否已經(jīng)達(dá)到或全局最優(yōu)解是否已達(dá)到要求的精度，若是，則停止，輸出最優(yōu)解；否則，轉(zhuǎn)Step2.

分組進(jìn)化人工魚群算法的流程圖見圖1.

圖1 分組進(jìn)化人工魚群算法的流程圖Fig.1The flow chart of GEAFSA

2 實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)設(shè)計(jì)

為了對(duì)分組進(jìn)化人工魚群算法的尋優(yōu)性能進(jìn)行檢驗(yàn)，本文選取四個(gè)測(cè)試函數(shù)，其中兩個(gè)為單極值函數(shù)，兩個(gè)為多極值函數(shù).讓本文算法及文獻(xiàn)中的各種算法對(duì)這四個(gè)函數(shù)的全局最優(yōu)值進(jìn)行搜索，將它們的搜索速度和精度進(jìn)行比較分析，以判斷各算法尋優(yōu)性能的優(yōu)劣.四個(gè)測(cè)試函數(shù)由表1給出，其中“目標(biāo)精度”按經(jīng)驗(yàn)值取，函數(shù) f2的全局最優(yōu)點(diǎn)位于一個(gè)平滑、狹長(zhǎng)的拋物線形山谷內(nèi)，較難尋找，因而設(shè)置的搜索精度較低.

表1 用于測(cè)試各算法性能的函數(shù)Tab.1 The functions used to test the performances of various algorithms

本文嘗試從以下幾個(gè)方面對(duì)算法性能進(jìn)行比較、分析：（1）比較本文算法（GEAFSA）與人工魚群算法、粒子群算法、蛙跳算法和文獻(xiàn)中的各改進(jìn)算法在收斂精度固定時(shí)的搜索次數(shù)；（2）比較本文算法與人工魚群算法在迭代次數(shù)一定時(shí)的搜索速度；（3）與參考文獻(xiàn)中的改進(jìn)算法的搜索精度進(jìn)行比較；（4）分析各參數(shù)對(duì)本文算法的影響.

2.2 實(shí)驗(yàn)結(jié)果及分析

2.2.1 迭代次數(shù)的比較

各算法都選取30個(gè)個(gè)體種群，四種函數(shù)的維度和收斂精度的設(shè)定見表1，根據(jù)經(jīng)驗(yàn)，設(shè)定參數(shù)為：局部搜索次數(shù)為5次，嘗試次數(shù)try number為3次，擁擠度δ0為1.5，個(gè)體共分為5組.對(duì)于每個(gè)函數(shù)每個(gè)算法都獨(dú)立運(yùn)行20次搜索，記錄每次搜索的相關(guān)數(shù)據(jù)，統(tǒng)計(jì)結(jié)果見表2.表2中“改進(jìn)人工魚群算法”為文獻(xiàn)[10]提供的改進(jìn)算法，“改進(jìn)蛙跳算法1”為文獻(xiàn)[11]提供的改進(jìn)算法，“GEAFSA”為本文算法.表2中各算法的迭代次數(shù)均為算法全局搜索次數(shù)與局部搜索次數(shù)的乘積；成功率為達(dá)到目標(biāo)精度的運(yùn)行次數(shù)占實(shí)驗(yàn)總次數(shù)的比率；期望迭代次數(shù)＝粒子種群數(shù)×平均迭代次數(shù)÷成功率，相同參數(shù)下，成功率越接近1，算法穩(wěn)定性越好，期望迭代次數(shù)越低，算法整體性能越好；表2中的“---”表示算法未搜索到要求精度下的最優(yōu)值，“∞”表示無窮大.

表2 在目標(biāo)精度下獨(dú)立運(yùn)行20次的統(tǒng)計(jì)結(jié)果Tab.2 The statistical results of 20 times independent runs under the target accuracy

從表2可以看出，本文算法可以在較少的迭代次數(shù)下，成功搜索到所有四個(gè)測(cè)試函數(shù)的全局最優(yōu)解，期望迭代次數(shù)也比較低，整體性能比文獻(xiàn)中的各種算法及其改進(jìn)算法都有提高.

2.2.2 收斂速度的比較

將迭代次數(shù)固定為100次，人工魚群算法和本文算法的收斂速度和精度如圖1所示，AFSA曲線表示人工魚群算法對(duì)四個(gè)函數(shù)的優(yōu)化曲線，GEAFSA曲線表示本文算法對(duì)四個(gè)函數(shù)的優(yōu)化曲線.為了便于觀察，四幅圖中橫軸均為迭代次數(shù)，而縱軸均為算法適應(yīng)度取以10為底的對(duì)數(shù)值.從中可以清楚地看出，本文算法搜索速度非?？欤踔猎?00步以內(nèi)就搜索到了函數(shù) f3和函數(shù) f4的理論最優(yōu)值，從GEAFSA曲線走勢(shì)來看，曲線下降速度較快，函數(shù) f3的曲線在平滑一段時(shí)間后，又有較快的下降速度，說明算法有跳出局部最優(yōu)的能力.

圖2 人工魚群算法和本文算法對(duì)四個(gè)函數(shù)的進(jìn)化曲線圖Fig.2The evolution curves of four functions for the AFSA and GEAFSA

2.2.3 搜索精度的比較

在200次進(jìn)化后，本文算法的收斂精度同文獻(xiàn)中的改進(jìn)算法的收斂精度的比較數(shù)據(jù)見表3，其中“改進(jìn)蛙跳算法2”為文獻(xiàn)[12]提供的改進(jìn)蛙跳算法.由表3可以看出，本文算法對(duì)函數(shù) f1、函數(shù) f3和函數(shù) f4搜索精度比相關(guān)算法都高，甚至可以搜索到理論最優(yōu)值，對(duì)函數(shù) f2的搜索結(jié)果較差，但比兩種改進(jìn)蛙跳算法的搜索結(jié)果要好些.

2.2.4 參數(shù)分析

本文算法中，擁擠度δ0和嘗試次數(shù)try number這兩個(gè)參數(shù)對(duì)算法性能有比較大的影響.擁擠度參數(shù)主要決定算法是否執(zhí)行覓食行為，而具有隨機(jī)性的覓食行為是本文算法跳出局部最優(yōu)的主要機(jī)制.當(dāng)擁擠度參數(shù)較小時(shí)，算法跳出局部最優(yōu)能力很強(qiáng)，但是因?yàn)閳?zhí)行覓食行為過于頻繁，算法穩(wěn)定性比較差，很難向最優(yōu)解靠攏，影響尋優(yōu)速度；如果擁擠度參數(shù)值比較大，算法非常容易陷入局部最優(yōu)，這是因?yàn)樗惴ê茈y達(dá)到擁擠的要求而進(jìn)行覓食行為，大量實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，擁擠度參數(shù)一般取值為1.5左右時(shí)效果較好.嘗試次數(shù)決定覓食行為中是否有更多的機(jī)會(huì)搜索到較優(yōu)新解，當(dāng)它的值比較大的時(shí)候，搜索速度會(huì)加快，但不易跳出局部最優(yōu)，太小的取值又很難尋找到較優(yōu)解，大量實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)一般取值3到5時(shí)較好.

表3 幾種算法的精度比較Tab.3The accuracy comparison of several algorithms

3 結(jié)論

本文提出的分組進(jìn)化人工魚群算法，充分地結(jié)合了目前較流行的幾種智能算法的優(yōu)點(diǎn)，在迭代時(shí)仿照蛙跳算法進(jìn)行分組進(jìn)化，采用并行機(jī)制提高了算法的搜索速度，同時(shí)在更新個(gè)體位置時(shí)，仿照粒子群算法的更新機(jī)制，充分利用群體信息，并且利用人工魚群算法的機(jī)制，通過擁擠度控制覓食行為，跳出局部最優(yōu).實(shí)驗(yàn)發(fā)現(xiàn)，該算法有較強(qiáng)的跳出局部最優(yōu)和整體尋優(yōu)能力，它的尋優(yōu)性能比一些文獻(xiàn)中提出的改進(jìn)算法更好，尋優(yōu)機(jī)制比基本魚群算法更加簡(jiǎn)化，且參數(shù)少，易操作，魯棒性強(qiáng)，具有很強(qiáng)的應(yīng)用價(jià)值.但對(duì)某些函數(shù)，搜索效果較差，主要原因是算法在搜索后期，受到函數(shù)本身性態(tài)的影響，容易陷入局部最優(yōu)，這需要更有效的跳出局部最優(yōu)的機(jī)制，同時(shí)，研究更快速有效的搜索機(jī)制才能進(jìn)一步提高算法的性能和實(shí)用性.

[1]林智華，高文，吳春明，等.基于離散粒子群算法的數(shù)據(jù)中心網(wǎng)絡(luò)流量調(diào)度研究[J].電子學(xué)報(bào)，2016，44（9）：2197-2202.

[2]楊薪冉，楊鳴，侯慶偉.基于混合蛙跳算法的船舶電力系統(tǒng)勵(lì)磁控制[J].船電技術(shù)，2016，36（8）：44-47.

[3]Kennedy J，Eberhart R C.Particle swarm optimization[C].In:Proc.of the IEEE Conf.on Neural Networks,IV.Perth:IEEE Press，1995：1942-1948.

[4]李勝，何明輝，李建林，等.嵌入層疊混沌策略的隨機(jī)粒子群算法[J].模式識(shí)別與人工智能，2015，28（10）：953-960.

[5]馮浩，李現(xiàn)偉.帶自適應(yīng)變異的粒子群優(yōu)化算法改進(jìn)研究[J].洛陽(yáng)師范學(xué)院學(xué)報(bào)，2015，34（11）：9-12.

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

[7]李小培，張洪偉，鄒書蓉.基于全局人工魚群算法的函數(shù)優(yōu)化[J].成都信息工程學(xué)院學(xué)報(bào)，2014，29（S1）：5-9.

[8]易新兵，楊凱.復(fù)合混沌-人工魚群混合算法的改進(jìn)及性能研究[J].計(jì)算機(jī)工程與科學(xué)，2013，35（8）：89-95.

[9]吳昌友.一種新的改進(jìn)人工魚群優(yōu)化算法[J].智能系統(tǒng)學(xué)報(bào)，2015，10（3）：1-6.

[10]黃美華，溫潔嫦，何勇.求解多目標(biāo)背包問題的改進(jìn)人工魚群算法[J].廣東工業(yè)大學(xué)學(xué)報(bào)，2016，33（5）：44-48.

[11]王麗，蘆彩林，宮建平.一種求解路徑優(yōu)化問題的新型人工魚群算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2016，46（20）：199-207.

[12]易正俊，韋磊鵬，袁玉興.自適應(yīng)重生魚群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件，2016，33（6）：227-230；276.

[13]Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Water Resources Planning and Management，2003，129（3）：210-225.

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

[15]林娟，鐘一文，馬森林.改進(jìn)的反向蛙跳算法求解函數(shù)優(yōu)化問題[J].計(jì)算機(jī)應(yīng)用研究，2013，30（3）：760-763.

[16]趙鵬軍，邵澤軍.一種新的改進(jìn)的混合蛙跳算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（8）：48-50.

責(zé)任編輯：吳興華

Grouping Evolutionary Artificial Fish Swarm Algorithm

LI Hui
（Department of public foundation，F(xiàn)ujian College of Water Conservancy and Electric Power，Yong’an366000，China）

In view of the poor searching performance of the basic artificial fish swarm algorithm（AFSA）,we combine the advantages of particle swarm algorithm,leapfrog algorithm and artificial fish swarm algorithm to propose a grouping evolu?tionary AFSA（GEAFSA）.This algorithm is a simplified version of the AFSA.It takes grouping evolution after leapfrog algo?rithm and makes use of the updating mechanism of particle swarm algorithm to update the individuals’positions with com?plete group information.Experiments show that the GEAFSA has good optimization,stability and practicality.

grouping evolution；congestion；foraging behavior；optimization

O 224

：A

：1674-4942（2016）04-0373-06

10.12051/j.issn.1674-4942.2016.04.004

2016-09-14