一種基于lévy飛行軌跡的果蠅優(yōu)化算法

郭德龍 楊 楠 周永權

(1.黔南民族師范學院數(shù)學與統(tǒng)計學院 都勻 558000)(2.廣西民族大學信息科學與工程學院 南寧 530006)

一種基于lévy飛行軌跡的果蠅優(yōu)化算法

郭德龍1楊 楠1周永權2

(1.黔南民族師范學院數(shù)學與統(tǒng)計學院 都勻 558000)(2.廣西民族大學信息科學與工程學院 南寧 530006)

針對果蠅優(yōu)化算法是模仿果蠅尋找食物行為而進行全局搜索最優(yōu)解的新算法,該算法存在容易陷入局部最優(yōu)解和收斂速度慢的缺點,提出一種基于lévy飛行軌跡的改進果蠅優(yōu)化算法。 引入lévy飛行軌跡隨機性,將它應用在果蠅算法中的個體嗅覺尋找食物的隨機方向上增加搜索的多樣性和搜索的范圍。最后通過數(shù)值仿真實驗對8個標準測試函數(shù)來進行作對比檢驗,結果表明該算法在求解高維函數(shù)優(yōu)化問題更好。

果蠅優(yōu)化算法; 函數(shù)優(yōu)化; lévy飛行; 多維函數(shù)優(yōu)化

Class Number TP18

1 引言

群智能優(yōu)化算法越來越受到學者重視,2011年臺灣學者潘文超針對果蠅的覓食行為展開研究和總結,在此基礎上提出了果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm,FOA)[1],這一算法最大特點在于它的群體智能性。雖然,FOA算法已成為數(shù)學函數(shù)極值、微調(diào)Z-SCORE模型系數(shù)等問題的可選方法之一[2]。關于果蠅優(yōu)化算法的改進與應用發(fā)展主要有韓俊英等提出的動態(tài)雙子群協(xié)同進化果蠅優(yōu)化算法[3]、基于細菌趨化的果蠅優(yōu)化算法[4]、自適應變異的果蠅優(yōu)化算法[5]、以歷史認知為基礎的果蠅優(yōu)化算法[6]、自動改變參數(shù)的果蠅優(yōu)化算法[7]、王雪剛及其研究小組發(fā)明的基于優(yōu)化算法的支持向量機參數(shù)優(yōu)化在船舶操縱預報中的應用[8]、馬超等提出的果蠅優(yōu)化算法(FOA)步長改進及其多元函數(shù)最優(yōu)化方法[9]、程慧等提出的基于混沌映射的混合果蠅優(yōu)化算法[10]、侯越等提出的基于螢火蟲優(yōu)化的BP神經(jīng)網(wǎng)絡算法研究[11]、胡能發(fā)等提出的演化式果蠅算法及其應用研究[12],但仍有缺點,主要在算法求解的精確度和收斂速度方面。所以本文針對以上提出了一種基于lévy飛行軌跡改進果蠅優(yōu)化算法,利用lévy飛行軌跡具有隨機性的特點將應用在果蠅行軌跡具有隨機性的特點將應用在果蠅個體尋找食物的方向上,從而使果蠅優(yōu)化算法的性能有所提高。

2 基本果蠅優(yōu)化算法和lévy飛行

2.1 基本果蠅優(yōu)化算法

作為一種具有智能特點的優(yōu)化算法,果蠅優(yōu)化算法的應用條件并不高,在實踐應用中只需改變很少的參數(shù)。

這是因為果蠅具有不同于別的生物的感官特征,特別是它獨特的嗅覺和視覺。研究人員發(fā)現(xiàn),當食物和果蠅之間相隔40km時,它也能夠根據(jù)嗅覺找到食物,一旦靠近食物后,就會利用視覺器官去尋找食物和同伴,直至精確地找到食物。以上述果蠅覓食行為為基礎的標準果蠅優(yōu)化算法的計算流程為[8～10]

1) 首先根據(jù)給定初始尋優(yōu)的范圍隨機生成初始群體并且位置矢量用X_axis,Y_axis給出果蠅的初始群體的規(guī)模popsize,最大迭代次數(shù)maxgen。

2) 采用隨機的方法,設定食物位于果蠅的某個方向和某段距離上,RandomValue代表距離。

Xi=X_axis+RandomValue

Yi=Y_axis+RandomValue

(1)

3) 考慮到食物的準確地點是未知的,首先預測它和原點的距離是Dist,然后通過計算得到味道濃度判定值S,它和距離之間的關系互為倒數(shù)。

(2)

(3)

4) 聯(lián)立式(3)以及味道濃度判定函數(shù),那么就能夠得到果蠅所處地方的味道濃度(Smelli)

Smelli=Fuction(Si)

(4)

5) 計算所有果蠅的味道濃度,進而確定擁有最大值的果蠅(當前最優(yōu)的個體)

[bestSmell,bestindex]=max(Smell)

(5)

6) 記錄并保存最佳味道濃度值bestSmell和位置信息X及Y,在這一時刻,果蠅會依賴視覺器官去接近這一位置。

Smellbest=bestSmell

X_axis=X(bestindex)

Y_axis=Y(bestindex)

(6)

7) 開始迭代計算,反復操作2)～5)步驟,一旦味道濃度超過了前一迭代結果,啟動步驟6)程序執(zhí)行已達到預先設定最大迭代次數(shù)maxgen或是已達到目標要求的精度或理論最優(yōu)值。

2.2 lévy飛行軌跡

這種軌跡是由lévy發(fā)明出來的具有穩(wěn)定性特征的分布[13]。從本質(zhì)上看,lévy飛行是隨機的游走過程,其步長屬于不間斷的重尾分布,它的性能主要體現(xiàn)在這些方面:

1) 從分布的角度來看,隨機變量及隨機變量的和是完全一致的,也就是呈現(xiàn)出具有統(tǒng)計的自相似性和隨機分形的特征。

3) 符合廣義中心極限定理。從隨機變量及分布的角度來看,lévy飛行屬于極限的范疇,它會對鄰域產(chǎn)生吸引力,一旦系統(tǒng)發(fā)生進化,或是實現(xiàn)結果完全取決于很多隨機數(shù)的和時,這種力量就會顯露出來。

4) 均值以及方差都是無限的。

研究結果顯示,很多能夠飛行的生物在飛行時,都符合lévy的特征。通過研究發(fā)現(xiàn)果蠅尋找食物的飛行行為具有l(wèi)évy飛行的隨機游走性的典型特征。本文將lévy飛行軌跡的所具有特點應用到果蠅優(yōu)化算法中每個果蠅個體在搜尋食物時搜索方向上,這樣可以增加搜索的多樣性和避免陷入局部最優(yōu)解的,對算法的性能有所提高。

3 基于lévy飛行軌跡的果蠅優(yōu)化算法

3.1 基本果蠅優(yōu)化算法分析

該算法在尋找最優(yōu)解過程中僅僅針對目前最優(yōu)個體進行學習,但在此次迭代中找到最優(yōu)的個體,相應的其它個體都將聚集到次位置。如果該個體并不是全局最優(yōu),因此很容易使算法陷入局部最優(yōu),降低搜索速度和求解的精度,從而帶來早熟收斂的問題。未了克服早熟收斂問題,有必要提供一種機制,使此算法避免發(fā)生早熟收斂,才使其跳出局部最優(yōu),獲得進入該解空間其他區(qū)域來繼續(xù)搜索,直到找到全局最優(yōu)解[10]。本文介紹的lévy飛行具有更好的隨機性,將其作為果蠅位置的迭代更新公式中,從而可以提高算法收斂的速度。這是因為lévy飛行過程中可以是先進性一系列較小的步長向前飛行,然后突然獲得一個較大步長,這樣可以是求解的過程容易跳出局部最優(yōu)解。

圖1 lévy分布的概率密度函數(shù)曲線

圖2 另外兩種α穩(wěn)定分布的概率密度函數(shù)曲線

由圖1和圖2可以看到lévy分布概率密度函數(shù)曲線并不是關于對稱的,而另外兩個α穩(wěn)定分布概率密度函數(shù)曲線(高斯分布、柯西分布)是對稱的。這也說明lévy飛行軌跡在隨機性方面表現(xiàn)優(yōu)異。

3.2 基于lévy飛行軌跡的果蠅優(yōu)化算法一般步驟

1) 首先根據(jù)給定初始尋優(yōu)的范圍隨機生成初始群體并且位置矢量用X_axis,Y_axis,給出果蠅的初始群體的規(guī)模popsize,最大迭代次數(shù)maxgen。

2) 執(zhí)行FOA算法流程(2)～(5)。

3) 記錄并保存最佳味道濃度值bestSmell和位置信息X及Y,在這一時刻,果蠅會依賴視覺器官去接近這一位置。

Smellbest=bestSmell

X_axis=X(bestindex)

Y_axis=Y(bestindex)

(7)

4) 在本文定義在n維空間中,第i個果蠅位置更新的公式中為

(8)

(9)

(10)

Si′=1/di′

(11)

6) 聯(lián)立式(11)以及味道濃度判定函數(shù),能夠得到新位置的味道濃度Smelli′。

Smelli′=Fuction(Si′)

(12)

7) 如果Smelli′

(13)

8) 進入到迭代尋優(yōu),重復執(zhí)行步驟2)～7),程序執(zhí)行終止條件是已達到預先設定最大迭代次數(shù)maxgen或是已達到目標要求的精度或理論最優(yōu)值。

4 數(shù)值仿真實驗與分析

4.1 數(shù)值仿真實驗

為了驗證本文給出的新算法的性能,采用對于智能算法通用的方法,選用8個標準測試函數(shù)中包括了單峰、多峰、線性、非線性、低維、高維等特征[10]。測試實驗平臺為Windows7和Matlab2010B,機器主頻為2.0GHz,內(nèi)存為2.00GB。

f3(x,y)=x2+y2+25(sin2x+sin2y),

x,y∈[-2π,2π]

-30≤xi≤30

-600≤xi≤600

-5≤xi≤5

-5.12≤xi≤5.12

-10≤xi≤10

測試實驗中的參數(shù)設置如下,果蠅種群的規(guī)模為Sizepop=40,最大迭代次數(shù)為Maxgen=10000。

表1 用于測試算法的標準函數(shù)的參數(shù)

4.2 實驗結果分析

4.2.1 固定進化迭代次數(shù)的收斂和精度

圖3～圖18是8個標準測試函數(shù)分別用標準果蠅優(yōu)化算法和基于lévy飛行軌跡的改進果蠅優(yōu)化算法運行求解的適應度函數(shù)變化曲線以及求解精度的圖。從圖中可以看出本文算法的收斂速度和收斂精度明顯要優(yōu)于標準果蠅優(yōu)化算法的,有效地消除了后者只能得到局部最優(yōu)解的可能性,總體來說LFOA算法的全局搜索能力、收斂速度求解精度是優(yōu)于FOA算法。

圖3 FOA算法求Sphere函數(shù)適應度進化曲線

圖4 本文算法求Sphere函數(shù)適應度進化曲線

圖5 FOA算法求Sehwegel函數(shù)適應度進化曲線

圖6 本文算法求Schwegel函數(shù)適應度進化曲線

圖7 FOA算法求Eggcrate函數(shù)適應度進化曲線

圖8 本文算法求Eggcrate函數(shù)適應度進化曲線

圖9 FOA算法求Ackely函數(shù)適應度進化曲線

圖10 本文算法求Ackely函數(shù)適應度進化曲線

圖11 FOA算法求Griewangk函數(shù)適應度進化曲線

圖12 本文算法求Griewangk函數(shù)適應度進化曲線

圖13 FOA算法求Salomon函數(shù)適應度進化曲線

圖14 本文算法求Salomon函數(shù)適應度進化曲線

圖15 FOA算法求Rastrign函數(shù)適應度進化曲線

圖16 本文算法求Rastrign函數(shù)適應度進化曲線

圖17 FOA算法求Zakharov函數(shù)適應度進化曲線

圖18 本文算法求Zakharov函數(shù)適應度進化曲線

4.2.2 兩種果蠅算法及參考文獻算法測試結果分析

表2給出了LFOA與FOA算法比較結果,從表中可以看出本文算法優(yōu)化均值和標準差均優(yōu)于FOA算法。表3給出了LFOA、FOA算法與參考文獻[13]中算法計算結果進行比較,結果顯示本文算法計算結果要優(yōu)于FOA和參考文獻[13]中的算法計算結果,所以本文算法優(yōu)化性能更好和實用性更強

表2 本文算法與參考文獻計算結果比較

表3 兩種算法計算結果比較

5 結語

針對標準果蠅優(yōu)化算法在尋優(yōu)的過程中容易陷入局部最優(yōu)解和求解精度不高等缺點,基于以上的問題引入了具有l(wèi)évy飛行軌跡分布的算子與標準果蠅算法相結合,讓它來指導果蠅迷失的飛行取得很好的效果,從而提高和跳出了陷入局最優(yōu)的缺點,也大大提高了求解精度,最后通過仿真實驗測試的標準函數(shù),結果表明求解的精度是比果蠅算法,從而說明LFOA在同樣維數(shù)的條件下搜索能力和求解精度更高些。

[1] 潘文超.應用果蠅優(yōu)化算法優(yōu)化廣義回歸神經(jīng)網(wǎng)絡進行企業(yè)經(jīng)營績效評估[J].太原理工大學學報,29(4):2011,29(4):1-5. PAN Wenchao, Fruit Fly Optimization Algorithm to Optimize the Opplication of generalized Regression Neural Network Business Performance Evaluation[J]. Journal of taiyuan university of Technology,29(4):2011,29(4):1-5.

[2] 潘文超.果蠅最佳化演算法[M].臺北:滄海書局,2011,10-12. PAN Wenchao, Fruit Flies Optimization Algorithms[M]. Taipei: Sea press,2011,10-12.

[3] 韓俊英,劉成忠,王聯(lián)國.動態(tài)雙子群協(xié)同進化果蠅優(yōu)化算法[J].模式識別與人工智能,2013,26(11):1057-1067. HAN Junying, LIU Chengzhong, WANG Lianguo. Dynamic Double Subgroups Cooperative Fruit Fly Optimization Algorithm[J]. Pattern recognition and artificial intelligence,2013,26(11):1057-1067.

[4] 韓俊英,劉成忠.基于細菌趨化的果蠅優(yōu)化算法[J].計算機應用,2013,33(4):964-966,1038. HAN Junying, LIU Chengzhong, Fruit Flies Optimization Algorithms Based on Bacterial Chemotaxis[J]. Computer application,2013,33(4):964-966,1038.

[5] 韓俊英,劉成忠.自適應變異的果蠅優(yōu)化算法[J].計算機應用研究,2013,30(9):2641-2644. HAN Junying, LIU Chengzhong. Fruit Flies Optimization Algorithms with Adaptive Mutation[J]. Computer application research,2013,30(9):2641-2644.

[6] 韓俊英,劉成忠.基于歷史認知的果蠅優(yōu)化算法[J].計算機科學與探索,2014,8(3):368-375. HAN Junying, LIU Chengzhong. Fruit Flies Optimization Algorithms Based on History cognition[J]. Computer science and exploration,2014,8(3):368-375.

[7] 韓俊英,劉成忠.自適應調(diào)整參數(shù)的果蠅優(yōu)化算法[J].計算機工程與應用,2014,50(7):50-55. HAN Junying, LIU Chengzhong. Fruit Flies Optimization Algorithms with Adaptive Parameter[J]. Computer engineering and application,2014,50(7):50-55.

[8] 王雪剛,鄒早建.基于果蠅優(yōu)化算法的支持向量機參數(shù)優(yōu)化在船舶操縱預報中的應用[J].上海交通大學學報,2013,47(6):884-888. WANG Xuegang, ZOU Zaojian. Fruit Fly Optimization Algorithm Based SVM Parameter Optimization and Its Application in Ship Manoeuvring Predictio[J]. Journal of Shanghai jiaotong university,2013,47(6):884-888.

[9] 馬超,董玲.果蠅優(yōu)化算法(FOA)步長改進及其多元函數(shù)最優(yōu)化方法[J].專題研究,2013,26(13):90-93. MA Cahao, DONG Ling, Fruit Flies Optimization Algorithm (FOA) Improved step Length and Its Multiple Function Optimization Method[J]. Special subject research,2013,26(13):90-93.

[10] 程慧,劉成忠.基于混沌映射的混合果蠅優(yōu)化算法[J].計算機工程,2013,39(5):218-221. CHENG Hui, LIU Chengzhong. Mixed Fruit Flies Optimization Algorithm Based on Chaotic Maps[J]. Computer Engineering,2013,39(5):218-221.

[11] 侯越,趙賀,路小娟.基于螢火蟲優(yōu)化的BP神經(jīng)網(wǎng)絡算法研究[J].蘭州交通大學學報,2013,32(6):24-27. HOU Yue, ZHAO He, LUO Xiaojuan. Study on Glowworm Swarm Optimized BP Neural Network Algorithm[J]. Journal of lanzhou jiaotong university,2013,32(6):24-27.

[12] 胡能發(fā).演化式果蠅算法及其應用研究[J].計算機技術與發(fā)展,2013,23(7):131-137. HU Faneng. Evolutionary Fruit Algorithm and Its Application Research[J]. Computer technology and development,2013,23(7):131-137.

[13] 謝健,周永權,陳歡.一種基于lévy飛行軌跡的蝙蝠算法[J].模式識別與人工智能,2013,26(9):829-837. XIE Jian, ZHOU Yongquan, CHEN Huan. A Bat Algorithm Based on lévy Flights Trajectory[J]. Pattern recognition and artificial intelligence ,2013,26(9):829-837.

A Fruit Fly Optimzation Algorithm Based on lévy Flights Trajectory

GUO Delong1YANG Nan1ZHOU Yongquan2

(1. School of Mathematics and Statistics, Qiannan Normal University for Nationalities, Duyun 558000) (2. College of Information Science and Engineering, Guangxi University for Nationalities, Nanning 530006)

Based on the shortcomings of fruit fly optimization Algorithm, which imitates the behavior of flies looking for food, such as low precision, slow convergence rate, and easily falling into local optimal solution, an improvement about the fruit fly optimization algorithm based on lévy flight path is put forward. This method applies the randomness of lévy flight path into the random directions of the individual sense of smell while looking for food, thus increasing the search diversity as well as the search range. At last, a contrast test is conducted to compare the eight standard test functions, the results show that this algorithm is much better in solving the high-dimensional function optimization problems.

fruit fly optimization algorithm, function optimization, lévy flight, multidimensional function optimization

2016年8月12日,

2016年9月30日

國家自然科學基金項目：本體的解釋診斷理論研究(編號:61463044)；國家自然科學基金項目:泛函網(wǎng)絡代數(shù)理論與學習算法及泛化能力研究(編號：61165015);國家民委科研基金項目:泛函網(wǎng)絡新模型及學習算法與應用研究(編號：0832082); 貴州省科技廳聯(lián)合基金(編號：黔科LH[2014]7436)；廣西復雜系統(tǒng)與智能計算重點實驗室開放課題(編號:15CI04Y)資助。

郭德龍,男,碩士,副教授,研究方向:智能優(yōu)化算法。楊楠,男,碩士,副教授，研究方向:自動機及其應用。周永權,男,博士,教授，研究方向:計算智能。

TP18

10.3969/j.issn.1672-9722.2017.02.020