分層協(xié)同進化的果蠅優(yōu)化算法

樂 天，陸慧娟，崔振東，張 威

（1.浙江海洋學(xué)院數(shù)理與信息學(xué)院，浙江舟山 316022；2.浙江省海洋大數(shù)據(jù)挖掘與應(yīng)用重點實驗室，浙江舟山 316022；3.中國計量學(xué)院信息工程學(xué)院，浙江杭州 310018）

分層協(xié)同進化的果蠅優(yōu)化算法

樂 天1，2，陸慧娟3，崔振東1，2，張 威1，2

（1.浙江海洋學(xué)院數(shù)理與信息學(xué)院，浙江舟山 316022；2.浙江省海洋大數(shù)據(jù)挖掘與應(yīng)用重點實驗室，浙江舟山 316022；3.中國計量學(xué)院信息工程學(xué)院，浙江杭州 310018）

果蠅優(yōu)化算法（FOA）是較新的群智能算法，其應(yīng)用領(lǐng)域越來越廣泛。但該算法在求解問題時存在早熟收斂，收斂速度慢和收斂精度低的缺點，為改善算法性能本文提出了分層協(xié)調(diào)進化的果蠅優(yōu)化算法(HCFOA)。根據(jù)味道濃度值將果蠅種群分層，并結(jié)合果蠅個體的進化信息及精英個體對種群位置的影響，進行分層協(xié)同進化。HCFOA和FOA分別求解4個測試函數(shù)，仿真結(jié)果表明，HCFOA算法有效改善了局部搜索能力，提高了收斂精度。

果蠅優(yōu)化算法；分層協(xié)同進化；收斂精度

群智能算法是模擬生物為求生存所具有的本能和方法發(fā)展而來的算法，包括遺傳算法，蟻群算法，粒子群算法，免疫算法，魚群算法，螢火蟲算法，果蠅優(yōu)化算法等。其中的果蠅優(yōu)化算法是一種模擬果蠅覓食行為的全新的全局優(yōu)化算法，在2011年6月由潘文超提出。FOA已成功應(yīng)用于求取函數(shù)極值[1]，自動化倉庫揀選作業(yè)調(diào)度問題[2]和船舶操縱響應(yīng)模型的辨識[3]與語音信號盲分離[4]等。但因FOA發(fā)展時間較短，目前還處于研究的初級階段，迫切需要更多的研究者展開關(guān)于FOA的相關(guān)研究。

相比其他群智能算法，F(xiàn)OA算法描述簡單，容易實現(xiàn)，需調(diào)參數(shù)較少、有較強的全局搜索能力和魯棒性，但同時與其他群智能算法一樣標(biāo)準(zhǔn)果蠅優(yōu)化算法存在易陷入局部解，收斂精度低，收斂速度慢等缺點，許多學(xué)者已進行了相關(guān)的研究。文獻[5]提出不僅要向優(yōu)秀果蠅學(xué)習(xí)，同時要向最差果蠅學(xué)習(xí)的改進策略。文獻[6]在果蠅算法中融入Logistic映射改進初值選取來改善算法搜索性能。文獻[7]利用元胞自動機有效克服果蠅優(yōu)化算法陷入局部解的缺點。

針對果蠅優(yōu)化算法存在早熟收斂，不易跳出局部最優(yōu)，且收斂精度低和收斂速度慢的缺點，本文受種群存在階層現(xiàn)象，且不同階層間可以協(xié)同發(fā)展的啟發(fā)，提出分層協(xié)同進化的果蠅優(yōu)化算法。將果蠅種群按其味道濃度值分成兩層，形成高味道濃度值種群和低味道濃度值種群。高味道濃度值種群充分考慮個體的進化信息，加強其局部勘探能力；低味道濃度值種群利用雙精英個體對種群位置的影響，提高算法的收斂速度和精度。將FOA和HCFOA應(yīng)用于4個基準(zhǔn)測試函數(shù)進行比較，仿真結(jié)果說明本文所提出的HCFOA有效改善了算法性能。

1 標(biāo)準(zhǔn)果蠅優(yōu)化算法

果蠅的嗅覺和視覺器官功能強大，利用嗅覺器官能搜索到40 km以外的食物源，利用視覺器官可以找到食物以及果蠅群聚集的位置，并飛向該位置。果蠅優(yōu)化算法是依照果蠅的嗅覺和視覺搜尋食物的特性推演出的一種全局優(yōu)化算法[1]。該算法通過一定量的代表問題解的果蠅個體組成果蠅種群，并依據(jù)最優(yōu)果蠅個體的位置，使種群中的其它個體按隨機設(shè)定的方向和距離匯集到該位置，如此一代代迭代，搜尋到食物。算法流程如圖1所示，具體步驟如下：

step1：給定種群規(guī)模POPSIZE和最大迭代次數(shù)MAXGEN，根據(jù)搜索范圍隨機給出果蠅種群初始位置：X’，Y’；

step2：模擬果蠅個體利用嗅覺搜尋食物：以種群所在位置為中心，以隨機給定的飛行方向和距離VALUE值確定個體搜索食物新的位置：

step3：為計算果蠅個體嗅到的食物味道濃度，因不知食物位置，故需先計算個體和原點之間的距離DISi，再設(shè)置味道濃度判定值，距離越短，味道濃度判定值越大，因此將距離倒數(shù)作為味道濃度判定值SSi:

step4：求取果蠅個體所在位置的味道濃度值SEMLLi（味道濃度判定值SSi代入適應(yīng)度函數(shù)）:

step5：找到最優(yōu)個體BEST，味道濃度最大的果蠅（當(dāng)前代最優(yōu)個體）將是同伴聚集的位置；

step6：模擬果蠅種群利用視覺飛向聚集位置，即保存?zhèn)€體BEST的味道濃度值及其坐標(biāo)：

step7：在未迭代到MAXGEN時，循環(huán)運行step（2）～step（5），若當(dāng)前代最優(yōu)個體優(yōu)于前一代最優(yōu)個體則執(zhí)行step（6）。

圖1 FOA算法流程圖Fig.1 FOA flow chart

圖2 HCFOA算法流程圖Fig.2 HCFOA flow chart

2 分層協(xié)同進化的果蠅優(yōu)化算法

理論上，F(xiàn)OA中的果蠅種群憑借果蠅的視覺和嗅覺能夠搜索到問題的全局最優(yōu)解，但整個算法中有以下兩個步驟值得關(guān)注：一是在步驟（6）中，因果蠅種群集體飛向味道濃度值最大的個體，若當(dāng)前最優(yōu)果蠅個體指引出錯，算法極容易陷入局部最優(yōu)；并且只依靠最優(yōu)果蠅個體而完全舍棄個體本身的進化信息，造成對潛在優(yōu)秀個體的勘探不足，算法不易跳出局部最優(yōu)。二是算法步驟（2）中VALUE取值的隨機性未能體現(xiàn)果蠅個體存在的差異性。VALUE取值過大，果蠅個體飛出最優(yōu)解的范圍而使算法陷入局部解；VALUE取值過小，果蠅個體雖在最優(yōu)解的范圍，但算法收斂速度緩慢。

HCFOA算法充分考慮個體進化信息及其差異性，以克服算法局部搜索能力不足，加快收斂速度，提高收斂精度。該算法在標(biāo)準(zhǔn)果蠅優(yōu)化算法的基礎(chǔ)上，對種群進行了分層，不同層按不同的策略進行尋優(yōu)，利用果蠅個體信息，增強果蠅個體勘探全局最優(yōu)解的方向性和能力性。

定義1（種群分層）：設(shè)果蠅種群表示為P(t)={at1,at2,...,atn},其中t為迭代數(shù)，n為種群規(guī)模，s(x)為果蠅個體的味道濃度值。令做集合則集合SMELL_Lt= P(t)-SMELL-Ht。

按定義1進行果蠅種群分層，分別形成高味道濃度值種群SMELL_H和低味道濃度值種群SEMLL_L。針對SMELL_H種群，因個體具有良好的進化信息，在充分利用果蠅自身所在的位置信息的基礎(chǔ)上，對設(shè)置果蠅搜索食物的方向與距離的VALUE值進行了自適應(yīng)的調(diào)整，自適應(yīng)調(diào)整如下：

其中DISiH表示果蠅個體離最高味道濃度值果蠅個體的距離，DISavg表示SMELL_H種群的平均距離，DISmax表示SMELL_H種群中距離最高味道濃度值果蠅個體的最大距離。DISavg反應(yīng)SMELL_H種群的密集程度，其值越小表示果蠅種群越集中在最高味道濃度值個體周圍。當(dāng)DISiH＞=DISavg時，對VALUE以一定的比例進行調(diào)整，DISiH愈大，調(diào)整比例愈大，確保果蠅個體對最高味道濃度值果蠅個體周邊區(qū)域的勘探能力，使其能更有效地跳出局部解；DISiH＜DISavg時，按FOA算法進行全局搜索。

針對SEMLL_L種群，受到生物進化過程中不同種群其最優(yōu)個體對種群的推動作用和層間個體相互協(xié)作的啟發(fā)，新的飛行位置不僅受SMELL_H種群中最高濃度值個體的影響，同時也受到SEMLL_L種群中最高濃度值個體的控制，具體如下：

采用兩層雙精英個體協(xié)同來確定種群將要飛向的位置，引導(dǎo)SEMLL_L種群朝最優(yōu)解方向飛行，確保其更好的全局搜索方向，提高全局搜索能力。

合并由SEMLL_H種群和SEMLL_L種群產(chǎn)生的個體作為新的種群，兩層種群協(xié)同進化，不僅有利于算法跳出局部解，同時也進一步提高其收斂速度和求解問題的精度。

遵循標(biāo)準(zhǔn)果蠅優(yōu)化算法的算法框架，本文提出的HCFOA算法流程如圖2所示，具體步驟如下：

step1：給定種群規(guī)模POPSIZE和最大進化代數(shù)MAXGEN，隨機給出果蠅種群初始位置：X’，Y’；并設(shè)置果蠅個體飛行的位置Xi和Yi；

step2：執(zhí)行FOA中的步驟（3）～（4）；

step3：根據(jù)定義1將果蠅種群分為兩層SMELL_H和SEMLL_L；

step4：分別記錄并保存SMELL_H和SEMLL_L中最優(yōu)果蠅個體位置及濃度值：

step5：對于SMELL_H種群，計算果蠅個體i與SMELLBEST_H之間的距離轉(zhuǎn)

step6；

step6：計算果蠅個體的新位置:

step7：對于SMELL_H種群，按式（10）和（11）得到XH’’和YH’’，個體飛行位置如下：

step8：循環(huán)迭代step2～step7，直到滿足結(jié)束條件（最大進化代數(shù)，進化精度等）。

3 實驗

3.1 實驗內(nèi)容

為驗證本文提出的算法的有效性，將其應(yīng)用于4個常用的性能測試函數(shù)，并與FOA仿真結(jié)果進行對比。函數(shù)信息見表1。測試函數(shù)的優(yōu)化難度隨著其維數(shù)的增大，搜索范圍的擴大和目標(biāo)精度的提高而加大。本文選用的維數(shù)和搜索范圍都是比較嚴(yán)苛的。實驗在win 7操作系統(tǒng)和vc++6.0，機器主頻為3.4GHz，內(nèi)存為4G環(huán)境下仿真實現(xiàn)。

3.2 實驗結(jié)果分析

實驗具體參數(shù)設(shè)置為：popsize=15，maxgen=2000，X’，Y’為表1中所列搜索范圍，VALUE取值區(qū)間[-1，1]。由于算法中的果蠅種群初始位置和搜索范圍取值具有一定的隨機性，HCFOA和FOA分別運行20次，取每代中最優(yōu)果蠅個體的味道濃度值的算術(shù)平均值。

圖1是HCFOA和FOA求解函數(shù)最優(yōu)值的對數(shù)值進化曲線，本文對最大味道濃度值進行了取對數(shù)處理，主要是為了方便查看曲線，同時考慮若真數(shù)為0，對數(shù)取值直接設(shè)置為-40。從圖1的進化曲線可以看出，不管是對于單峰值函數(shù)（f1和f3）還是對于多峰值函數(shù)（f2和f4），HCFOA的搜索能力，收斂速度和精度均明顯優(yōu)于FOA。

表1 優(yōu)化函數(shù)Tab.1 Optimized function

圖3 f1～f4最大味道濃度值進化曲線Fig.3 Maximum fitness volutionary curves of f1～f4

表2是HCFOA與參考文獻算法的性能比較。參考文獻算法對應(yīng)的搜索范圍，種群規(guī)模和最大進化的取值見表3。相對于參考文獻中的算法，HCFOA在較大的搜索范圍和較小的種群規(guī)模和迭代次數(shù)取值下，除f3在GAFSA求解中優(yōu)化均值稍優(yōu)于HCFOA，其他均比參考文獻具有更優(yōu)的收斂精度。f2，f4表現(xiàn)尤其突出，能夠很好的跳出局部最優(yōu)，搜索到全局最優(yōu)解。

表2 優(yōu)化均值比較Tab.2 Comparison of optimization mean

表3 各函數(shù)相關(guān)數(shù)據(jù)設(shè)置Tab.3 Function parameters setting

4 結(jié)束語

本文分析了標(biāo)準(zhǔn)果蠅優(yōu)化算法在優(yōu)化過程中因只考慮飛向最優(yōu)果蠅個體和VALUE取值的隨機性，引起算法陷入局部最優(yōu)，收斂速度慢和收斂精度低等問題，提出一種分層協(xié)同進化的果蠅優(yōu)化算法。并用HCFOA算法求解4個性能測試函數(shù)，和FOA求解結(jié)果對比表明，本文提出的HCFOA算法具有更好的勘探最優(yōu)解的能力，其收斂速度和收斂精度都有明顯地提高。

[1]PAN Wen-Tsao.A New Evolutionary Computation Approach:Fruit Fly Optimization Algorithm[C]//Proc.of the 11th Con-ference on Digital Technology and Innovation Manage-ment.Taipei,China:[s.n.],2011.

[2]劉志雄,王雅芬,張 煜.多種群果蠅優(yōu)化算法求解自動化倉庫揀選作業(yè)調(diào)度問題[J].武漢理工大學(xué)學(xué)報,2014,36(3):71-77.

[3]韓俊英,劉成忠.基于果蠅優(yōu)化算法的船舶操縱響應(yīng)模型的辨識[J].大連海事大學(xué)學(xué)報,2012,38(3):1-4.

[4]肖正安.改進FOA算法在語音信號盲分離中的應(yīng)用[J].計算機工程與應(yīng)用,2013,49(16):201-204.

[5]韓俊英,劉成忠.反向認知的高效果蠅優(yōu)化算法[J].計算機工程,2013,39(11):223-225.

[6]程 慧,劉成忠.基于混沌映射的混合果蠅優(yōu)化算法[J].計算機工程,2013,39(5):218-221.

[7]賀智明,宋建國,梅宏標(biāo).結(jié)合元胞自動機的果蠅優(yōu)化算法[J].計算機應(yīng)用,2014,34(8):2 295-2 298.

[8]王 凌.智能優(yōu)化算法及其應(yīng)用［M］.北京:清華大學(xué)出版社，2001:148－149.

[9]林 川，馮全源.一種新的自適應(yīng)粒子群優(yōu)化算法[J].計算機工程，2008，34(7):181－183.

[10]王聯(lián)國，洪 毅，施秋紅.全局版人工魚群算法[J].系統(tǒng)仿真學(xué)報，2009，21(23):7483－7486.

Hierarchical Coevolutionary Fruit Fly Optimization Algorithm

LE Tian1,2,LU Hui-juan3,CUI Zhen-dong1,2,et al
(1.School of Mathematics,Physics and Information Science,Zhejiang Ocean University,Zhoushan 316022; 2.Key Laboratory of Oceanographic Big Data Mining&Application of Zhejiang Province,Zhoushan 316022; 3.College of Information Engineering,China Jiliang University,Hangzhou 310018,China)

Fruit Fly Optimization Algorithm(FOA)is a relatively new Swarm intelligence algorithm,its application field is more and more widely.In solving the problem using this algorithm,low convergence precision and easily relapsing into local optimum,there are the faults of Premature convergence,slow convergence speed and low convergence precision.Hierarchical Coevolutionary Fruit Fly Optimization Algorithm (HCFOA)is proposed in order to improve the algorithm performance in this paper.Fruit fly population is layered according to smell,and coevolutioned with the evolution information and the effects of elite individual on population location.The simulation results of four test functions show that HCFOA has the advantages of better local searching ability,and more precise convergence than FOA.

fruit fly optimization algorithm(FOA);fierarchical coevolutionary;convergence precision

TP18

A

1008－830X(2015)05－0491－06

2015-02-10

浙江省科技廳公益技術(shù)研究社會發(fā)展項目（2015C33082）

樂天（1978-），女，浙江舟山人，講師，碩士，研究方向：智能計算.E-mail:103405954@qq.com