動態搜索協同進化的果蠅優化算法

張水平,陳 陽,丁小軍

(江西理工大學 信息工程學院,江西 贛州 341000)

1 引 言

果蠅優化算法(Fruit fly optimization algorithm,FOA)是由中國臺灣潘文超教授于2011年提出并發表于國際期刊Knowledge-Based Systems,是一種新型全局優化的智能演化算法[1].該算法提出時間不久,研究尚處于發展階段,但已應用于各類工程領域.潘教授應用該算法成功優化以財務預警為例的Z-SCORE模型,廣義回歸神經網絡,在優化支持向量回歸參數上同樣取得不錯的效果[1-3].果蠅算法作為最新的群智能算法,繼承了粒子群,遺傳等算法的優點,以自組織自適應的優化形式有效求解復雜問題.相比較而言,該算法易于理解且實現更容易,其簡潔的代碼,較少的調解參數使其具有更好的執行效率.

作為一種智能演化算法,果蠅優化算法也不可避免易陷入局部最優,優化后期收斂速度低等問題.針對這些缺點,諸多學者對該算法進行改進,盡可能避免早熟現象,提高收斂精度.如融合細菌遷移[4],禁忌搜索[5]的優點拓展果蠅算法提高收斂精度.文獻[6]以最優的種群方向引導種群更新,改善算法執行效率.改進算法自身迭代公式以自適應的步長搜索最佳位置[7-9]以增強全局優化能力.文獻[10]中定義一種控制種群范圍的參數V[10],以種群歷史軌跡的變化動態調整V,使種群保持多樣性.對于局部最優的限制,引入一種協作變異機制幫助群體跳出局部最優[11].以上改進的果蠅算法在連續優化問題上都有更好的效果.此外通過改進果蠅算法已成功求解了聯合補充[12],多維背包[13],旅行商問題[14].

本文在學習總結前人改進的思路后,為提高FOA早熟收斂,求解精度低等問題,提出一種動態搜索協同進化的果蠅優化算法(Dynamic search and Cooperative learning for Fruit fly optimization algorithm,DCFOA),該算法引入一種精英個體,增強種群多目標學習概率,并以一種遞減的牽引因子誘導精英果蠅尋優,使算法后期逐漸向最優解收斂.增強算法全優化能力的同時保證了后期收斂的可靠性.此外果蠅算法隨著迭代次數的增加其多樣性是逐步遞減,后期種群聚集度較大時果蠅便會陷入一個局部最優區域,算法基本處于停滯狀態.設置判斷果蠅聚集度參數,當進入局部最優時,以空間壓縮理論將求解問題的空間域設置為一種線性遞減的步長搜索影響因子,幫助算法跳出局部最優進行二次搜索.經過6個經典測試函數的仿真實驗證明本文改進思路的有效性.

2 基本果蠅算法介紹

果蠅優化算法是模擬果蠅覓食而演化來的一種新的群體智能優化算法.果蠅廣泛生活在熱帶地區,主要以腐爛的水果植物為食,具有強于其他物種的嗅覺,可以嗅到 40km以外的食物源,然后飛近食物位置后利用敏銳的視覺發現食物和同伴聚集的位置,并且迅速往該向飛去.這種特點下,認為每個果蠅個體的味道濃度值為一個優化問題的可行解.算法執行步驟如下:

Step1.初始化果蠅群體規模SizePop和最大迭代次數MaxSize,果蠅群體位置X_axis,Y_axis.

Step2.設定果蠅個體搜尋食物的隨機方向及距離.公式中隨機數R為搜索距離.

(1)

Step3.果蠅群體未知食物源的位置,需先計算個體與原點之間的距離Disti,再計算味道濃度判定值Si.與食物源距離越近,則味道濃度判定值越大,算法設定Disti的倒數為味道濃度判定值Si.

(2)

(3)

Step4.將味道濃度判定值Si代入味道濃度判定函數中(亦稱為適應度函數),求出果蠅個體位置的味道濃度Smelli.

Smelli=Function(Si)

(4)

Step5.記錄果蠅群體中味道濃度最大的果蠅(適用于最小化問題).

[bestSmellbestindex]=min(Smelli)

(5)

Step6.記錄并保存最佳味道濃度值bestSmell與該果蠅位置的X,Y坐標,此時果蠅群體利用視覺搜索向這個最優位置收斂靠近.

(6)

Step7.進入迭代尋優,重復執行步驟Step2到Step5,并判斷最佳味道濃度是否優于上一代的最佳味道濃度.是則執行Step6.若當前迭代次數未達到最大迭代數MaxSize則重復上述步驟.

3 動態搜索協同進化的果蠅優化算法設計與實現

3.1 算法分析與設計

從自身優化的整體進程分析基本果蠅優化算法,果蠅種群是單純的向最優個體的位置靠攏.若最優個體陷入一個局部最優解,整個種群會進入早熟收斂,從而優化效果變差,解的精度大大降低.在算法迭代到一定階段,種群多樣性降低,算法也極易收斂到一個局部點而停滯不前.這里引入精英個體協同最優果蠅協調全局優化,如此設計使算法優化過程一直處于一個平衡態,增強全局優化能力.以一種牽引因子δ誘導種群向精英個體學習,由于算法最終要收斂于全局最優位置,因而公式(8)中的牽引因子對精英個體擾動牽制采用線性遞減策略[15].種群陷入局部最優必然是群體向最優個體位置靠攏的某一刻最優個體得到了一個局部最優解而引起的,根據生物群體的社會性可知最優的解往往就在最優個體位置的鄰域內.因此所引進的精英個體并非是種群中的某一個單一個體,而是僅次于最優個體味道濃度的兩只次優果蠅個體.X_axis和Y_axis更新方式見公式(7),其中Xe,Ye分別取這兩只次優個體X,Y坐標的算數平均值.公式(8)中T表示當前迭代數.

(7)

δ=δend·(δstart/δend)(1/(1+10T)/maxsize)

(8)

群智能算法的特性限制了其不可能一次就在解空間上達到一個完美的優化.當果蠅算法后期種群多樣性喪失,精英果蠅牽引全局效果變弱,果蠅群體將收斂于一個局部極值,因此設置一診斷機制,即判斷每次迭代果蠅濃度的方差是否小于設定的閥值甚至于方差為0,保存上代最佳果蠅味道濃度與本代最優果蠅味道濃度做一個對比.診斷機制若診斷出果蠅已經陷入局部最優則停止對解空間搜索,引入搜空間壓縮理論幫助算法跳出限制進行二次尋優.將空間壓縮原理融合進果蠅優化算法具體是以不同問題的搜索空間為限定值,將原果蠅算法的固定步長變為一種適應求解具體問題的動態空間搜索步長.X_axis和Y_axis存儲的是最優果蠅和精英果蠅協同優化的最佳位置,果蠅群體在滿足診斷值時以公式(9)進行迭代尋優.參數k是一種遞減[15]影響搜索步長的調解參數.公式(10)中k的start和end值根據求解問題的空間域不同而具體設定(本文測試的連續性函數問題在4.1節實驗設計中有介紹).基于引進協調精英個體學習和壓縮搜索空間動態步長的兩點改進可以有效克服的算法早熟收斂問題,一定程度上提高解的精度值,使算法實際應用價值更高.

(9)

k=-(kstart-kend)·(T/max size)2+kstart

(10)

3.2 算法的實現

經過上一節對FOA存在問題的闡述和對改進后的新算法的分析設計,DCFOA的具體實現步驟如下:

步驟1.初始化參數:最大迭代次數:MaxSize.種群規模:SizePop,問題維度Dim,果蠅初始位置X_axis,Y_axis.

步驟2.執行FOA基本步驟2-5.

步驟3.將第一次執行的最佳味道濃度值以公式(11)保存于smellbest和存放上代最價值的prebestsmell.xb和yb分別保存本代最優果蠅的位置信息.

(11)

步驟4.對本代搜尋完成的果蠅味道濃度值smell進行排序,拿出僅次于bestsmell最優果蠅的兩個果蠅個體,分別計算其X,Y坐標的位置并求算術平均值得到Xe,Ye.

步驟5.根據公式(7)計算果蠅群體收斂方向的目標位置.

步驟6.以公式(12)公式(13)計算種群的味道濃度方差,判斷果蠅種群的聚集程度.

(12)

(13)

步驟7.若smellvar值為0或者prebestsmell與本代bestsmell值相同,斷定果蠅種群多樣性喪失且陷入局部最優,則利用公式(9)進行更新果蠅種群位置.否則依舊按照原算法的公式(1)進行更新.

步驟8.將本代的bestsmell賦予prebestsmell后進入迭代循環.重復執行步驟2-步驟7,保存每代smellbest值.當算法達到MaxSize的設定值時結束循環.

需要補充一點,在實際應用中為節省算法執行時間提高效率往往算法達到目標誤差精度即可終止算法執行.即步驟8中最后一步為:算法達到MaxSize設定值或達到預設的目標誤差精度時終止算法運行.

4 實驗與仿真

4.1 實驗設計

為驗證本文提出改進算法DCFOA的有效性,采用經典的6個測試函數進行仿真測試.測試函數表達式,測試維度,搜索空間等信息見表1.由于智能優化算法是模擬現實生物進化過程,具有一定的隨機性,為降低隨機因素的影響,本次實驗分別對兩種算法獨立進行20次運行,以其平均值比較兩個算法的優化速度和收斂精度.

為了更好測試改進后算法的性能,本次仿真實驗設置參數如下:

MaxSize=1000;SizePop=30;δstart=0.04;δend=0.01(δstart與δend的取值是在100次測試實驗中取效果較好的值,讀者亦可在此改進根據其他策略來選擇δstart與δend的取值);維度Dim分別取表1中6中不同問題的維度值.kstart和kend是取表1中不同測試問題的搜索空間值,k的start值取搜索空間的最大值,k的end值為搜索空間的最小值.

4.2 實驗結果分析

通過對兩種算法20次獨立運行,表2 中給出FOA和DCFOA分別測試6個測試函數的最優值,最差值,平均值,標準差.總體上,除函數F3外,其他幾個函數的求解精度基本都提高10個數量級以上,DCFOA相比FOA不同程度提高了算法魯棒性.圖1～圖6給出兩種算法的尋優迭代曲線對比(為了便于觀察兩種迭代曲線,對果蠅最佳味道濃度值取以10為底的對數),下面結合表2中的實驗數據具體分析兩種算法尋優性能.F1函數為一種簡單的單峰函數,尋優難度不大,FOA算法可以輕易的搜尋到最優解,改進后的DCFOA在精度上提高了12個數量級且具有良好的穩定性.F2函數為一種具有無數局部極小值點的可變維高峰函數,從圖2中看出FOA在第200代之前有三次跳出局部最優解,200代之后算法停滯.DCFOA在前期化進程中以牽引因子誘導的精英果蠅幫助整個種群更新,因此具有極強持續性的全局尋優能力.在FOA停滯時DCFOA依然在迭代工程中進行優化搜索,在多次重復實驗中,無論是搜索的最優解還是最差解DCFOA都能提高11個精度值且保持良好的穩定性.

表1 測試函數信息表
Table 1 Test function information

函數名表達式維度搜索空間理論極值峰值Spheref1(x)=∑ni=1x2i30[-100，100]0單峰Griewankf2(x)=14000∑ni=1(xi)2-Πni=1cos(xi/i)+130[-600，600]0多峰Rosenbrockf3(x)=∑n-1i=1(100(xi+1-x2i)2+(xi-1)2)30[-100，100]0單峰Rastriginf4(x)=∑ni=1(x2i-10cos(2πxi)+10)30[-5．12，5．12]0多峰Ackleyf5(x)=-20exp[-0．2130∑ni=1x2i]-exp[130∑ni=1cos(2πxi)]+20+e30[-100，100]0多峰Schafferf6(x)=sin2x21+x22-0．5(1+0．001(x21+x22))2+0．52[-100，100]0多峰

表2 兩種算法性能對比
Table 2 Performance comparison of two algorithms

函數最優值最差值均值標準差FOADCFOAFOADCFOAFOADCFOAFOADCFOAF12．4494e-051．3190e-172．5506e-051．0615e-162．4892e-053．6437e-171．1000e-032．5381e-17F23．7530e-043．6637e-156．9128e-044．4409e-156．6327e-043．8525e-156．8050e-051．9762e-16F325．685029．696945．474429．696936．745029．69695．86183．7372e-06F4164．90461．0125e-12284．59505．8051e-12235．58322．8793e-1225．76341．5169e-12F53．700e-032．6889e-093．700e-036．9363e-093．7000e-033．9515e-091．4938e-051．1444e-09F62．3958e-061．8874e-152．9163e-062．1094e-152．6266e-061．9901e-151．2654e-078．3072e-17

在本文的6種不同測試問題中F3函數測試性能表現最差,DCFOA相比FOA,優化此類問題求解精度雖略有提高但相比其他優化問題表現不盡如人意.從F3函數本身來分析,它是一種非凹形態的病態二次函數,其仿真圖形中全局最優值位于一個狹長的類似于甬道的位置.算法尋找最優解過程中,在平滑的甬道上難以得到更多信息,從而使算法陷入局部最優.DCFOA由于在陷入局部最優時,會跳出停滯過程進行二次優化,所以在優化精度上DCFOA比FOA有所提高.

01002003004005006007008009001000-16-14-12-10-8-6-4-2024DCFOAFOAinteration numbersmellbest(lg(f))Iterative curves of different algorithms圖1 F1函數進化曲線Fig．1 Function1evolutioncurve01002003004005006007008009001000-15-10-50DCFOAFOAinteration numbersmellbest(lg(f))Iterative curves of different algorithms圖2 F2函數進化曲線Fig．2 Function2evolutioncurve010020030040050060070080090010001.01.52.02.53.03.54.04.5DCFOAFOAinteration numbersmellbest(lg(f))Iterative curves of different algorithms圖3 F3函數進化曲線Fig．3 Function3evolutioncurve

F4函數可以看成是在F1函數的基礎之上利用余弦波產生很多局部峰值的一種多峰函數,此類函數可以驗證一個算法避免陷入局部最優解的能力,FOA單純的以最優果蠅的位置為收斂目標,由圖4可以看出在50代左右算法已陷入局部最優,優化精度極低且穩定性差.DCFOA設計本身就是平衡全局與局部的搜索能力,使種群多樣性增強而不至于在迭代初期就在局部擾動而停滯不前,即使陷入局部極值點也能通過設置的診斷機制逃離困象而進行以空間壓縮為基礎的二次尋優.表2所示,DCFOA在20次獨立運行中無論最優解還是最差解收斂精度都可以提高14個數量級,比FOA具體更好的可靠性.

01002003004005006007008009001000-12-10-8-6-4-2024DCFOAFOAinteration numbersmellbest(lg(f))Iterative curves of different algorithms圖4 F4函數進化曲線Fig．4 Function4evolutioncurve01002003004005006007008009001000-10-8-6-4-202DCFOAFOAinteration numbersmellbest(lg(f))Iterative curves of different algorithms圖5 F5函數進化曲線Fig．5 Function5evolutioncurve01002003004005006007008009001000-16-14-12-10-8-6-4-2DCFOAFOAinteration numbersmellbest(lg(f))Iterative curves of different algorithms圖6 F6函數進化曲線Fig．6 Function6evolutioncurve

F5函數是一種極難尋找全局最優的爬山形態的多峰函數.FOA在搜尋全局最優解時需要避免很多形如小山峰的局部地區,如圖5所示,在FOA迭代初期尚具有一定的尋優能力,大約300代之后,果蠅種群更新速度放緩,陷入早熟收斂.DCFOA相比FOA明顯不易早熟,在迭代后期依舊保持多樣性,具有極強的持續搜索能力,求解精度可以提高6個數量級,算法穩定性亦提高4個數量級.

F6函數雖然是一個二維函數,但是也是一種具有強震蕩性的多峰值函數.全局最優點附近包裹的無數次優點為算法尋優增加了極大的難度.圖6中FOA的震蕩曲線從迭代開始便陷入局部最優的范圍之中.DCFOA在700代時達到搜索的最優解.表2所示DCFOA在此函數上收斂精度提高約9個數量級.

經上述分析,本文提出的算法DCFOA有效的克服了FOA易陷入局部最優等不足,提高了收斂精度.表3中給出本文算法和部分參考文獻的改進算法在高維函數優化中的均值對比(維度統一為30維).除F3函數收斂精度較弱外,DCFOA對其他4個函數都有優于其他算法的求解效果,亦證明了本文算法的正確性和高效性.

表4給出3.2節中補充的步驟8增加目標誤差精度后算法執行的平均迭代次數與成功率比較結果.表4中“——”表示相關參考文獻未給出實驗結果.“()”中數據表示該實驗所采用的目標精度.測試本文提出的算法DCFOA與FOA都采用幾種對比算法中最為嚴苛的精度值.表4中成功率=達到目標誤差精度次數/總試驗次數.經實驗證明在所設目標精度的條件下,本文算法DCFOA對6種測試函數在20次獨立實驗中都可以成功尋優.相比參考文獻[8]在函數尋優成功率上不但提升,而且在函數F1與F4上平均迭代次數也大大縮短.相比較文獻[7],本文算法在函數F1,F2,F5目標精度要求更高的條件下依然縮短的算法的迭代次數,證明了算法DCFOA具有較高的優化效率和尋優可信性.

表3 不同算法均值比較
Table 3 Comparison of several algorithms mean

函數DCFOAAFOABM[5]FOAMR[8]IFFO[9]F13．6437e-173．1540e-63．9334E-84．96e-13F23．8525e-151．0355e-72．5887e-91．23e-2F329．696928．683928．7043———F42．8793e-129．7825e-6———6．34e-11F53．9515e-91．68454．2839e-55．13e-7

表4 幾種算法平均迭代次數與成功率比較
Table 4 Comparisons on the iteration numbers and the success rate of several algorithms

函數FOA平均迭代次數/成功率TSFOA[4]平均迭代次數/成功率AFOABM[6]平均迭代次數/成功率FOAMR[8]平均迭代次數/成功率DCFOA平均迭代數/成功率F10/0(10-06)1/1(10-5)532/1(10-5)232/0．95(10-6)205．65/1(10-06)F20/0(10-07)1/1(10-6)98/1(10-6)90/0．85(10-7)94．45/1(10-07)F315．2/0．65(30)1/1(30)1/1(30)20/0．90(30)3．3/1(30)F40/0(10-04)1/1(10-4)313/1(10-4)———/———208．6/1(10-04)F5125．8/0．3(10-03)———/——————/0(10-1)49/0．90(10-3)17．85/1(10-03)F686．9/1(10-05)35．78/1(10-5)51/1(10-5)———/———5．5/1(10-05)

5 總 結

本文分析了基本果蠅優化算法只向最優個體收斂且全局過程步長固定的特性,引入向以牽引因子誘導的精英果蠅協同學習,在陷入局部最優時以空間壓縮策略設定具體問題的空間域為步長影響因子,而提出一種動態搜索協同進化的果蠅優化算法.工程科學領域的諸多問題都可以轉化為函數優化問題,文中采用6種典型的測試函數進行仿真,實驗結果表明本文算法可有效避免FOA的早熟收斂現象,提高了全局搜索能力,在收斂精度和穩定性方面都優于FOA,可以更好的適應于解決實際問題.

[1] Pan Wen-tsao.A new fruit fly optimization algorithm:taking the financial distress model as an example[J].Knowledge-Based Systems,2012,26(2):69-74.

[2] Pan Wen-tao.Fruit fly optimization algorithm[M].Taibei:Tsang Hai Book Publishing Co,2011:10-12.

[3] Pan Wen-tao.Using fruit fly optimization algorithm optimized general regression neural network to construct the operating performance of enterprises model [J].Journal of Taiyuan University of Technology:Social Sciences Edition,2011,29(4):1-5.

[4] Zhang Cai-hong,Pan Guang-zhen.Fruit fly optimization algorithm based on Tabu search[J].Computer Engineering And Design,2016,37(4):907-913.

[5] Liu Cheng-zhong,Han Ying-jun.Adaptive fruit fly optimization algorithm based on bacterial migration[J].Computer Engineering and Science,2014,36(4):690-696.

[6] Wu L,Xiao W,Zhang L,et al.An improved fruit fly optimization algorithm based on selecting evolutionary direction intelligently[J].International Journal of Computational Intelligence Systems,2016,9(1):80-90.

[7] Wu L,Xiao W,Wang J.An improved fruit fly optimization algorithm based on changing iteration step values adaptively[J].Journal of Computational and Theoretical Nanoscience,2016,13(1):259-264.

[8] Chang Peng,Li Shu-rong,Ge Yu-lei,et al.Fruit fly optimization algorithm with self-adapting adjustment of iteration step value[J].Computer Engineering and Application,2016,52 (3):32-36.

[9] Pan Q K,Sang H Y,Duan J H,et al.An improved fruit fly optimization algorithm for continuous function optimization problems[J].Knowledge-Based Systems,2014,62(5):69-83.

[10] Zhang Y,Cui G,Zhu E,et al.AFOA:an adaptive fruit fly optimization algorithm with global optimizing ability[J].International Journal on Artificial Intelligence Tools,2016,25(6):1-30.

[11] Zhang Yi-wen,Cui Guang-ming,Wu Jin-tao,et al.A novel multi-scale cooperative mutation fruit fly optimization algorithm[J].Knowledge-Based Systems,2016,114(12):24-35.

[12] Wang L,Shi Y,Liu S.An improved fruit fly optimization algorithm and its application to joint replenishment problems[J].Expert Systems with Applications,2015,42(9):4310-4323.

[13] Meng T,Pan Q K.An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Applied Soft Computing,2017,50(1):79-93.

[14] Jiang Z,Yang Q.A discrete fruit fly optimization algorithm for the traveling salesman problem[J].PloS one,2016,11(11):1-15.

[15] Chen Gui-ming,Jia Jian-yuan,Han Qi.Study on the strategy of decreasing inertia weight in particle swarm optimization algorithm[J].Journal of Xi′an Jiaotong University,2006,40(1):53-56.

附中文參考文獻：

[2] 潘文超,果蠅最佳化演算法[M].臺北:滄海書局,2011:10-12.

[3] 潘文超,應用果蠅優化算法優化廣義回歸神經網絡進行企業經營績效評估[J].太原理工大學學報(社會科學版),2011,29(4):1-5.

[4] 張彩宏,潘廣貞.融合禁忌搜索的混合果蠅優化算法[J].計算機工程與設計,2016,37(4):907-913.

[5] 劉成忠,韓英俊.基于細菌遷移的自適應果蠅優化算法[J].計算機工程與科學,2014,36(4):690-696.

[8] 常 鵬,李樹榮,葛玉磊,等.迭代步進值自適應調整的果蠅優化算法[J].計算機工程與應用,2016,52 (3):32-36.

[15] 陳貴敏,賈建援,韓 琪.粒子群優化算法的慣性權值遞減策略研究[J].西安交通大學學報,2006,40(1):53-56.