李輝

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

分組進化人工魚群算法

李輝

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

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

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

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

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

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

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

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

1 分組進化人工魚群算法

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

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

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

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

該算法的基本步驟如下：

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

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

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

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

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

分組進化人工魚群算法的流程圖見圖1.

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

2 實驗分析

2.1 實驗設(shè)計

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

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

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

2.2 實驗結(jié)果及分析

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

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

表2 在目標精度下獨立運行20次的統(tǒng)計結(jié)果Tab.2 The statistical results of 20 times independent runs under the target accuracy

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

2.2.2 收斂速度的比較

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

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

2.2.3 搜索精度的比較

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

2.2.4 參數(shù)分析

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

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

3 結(jié)論

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

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

[2]楊薪冉，楊鳴，侯慶偉.基于混合蛙跳算法的船舶電力系統(tǒng)勵磁控制[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].模式識別與人工智能，2015，28（10）：953-960.

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

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

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

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

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

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

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

[12]易正俊，韋磊鵬，袁玉興.自適應(yīng)重生魚群優(yōu)化算法[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)視野和步長的局部鄰域人工魚群算法[J].計算機工程與設(shè)計，2012，33（7）：2815-2821.

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

[16]趙鵬軍，邵澤軍.一種新的改進的混合蛙跳算法[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