基于天牛須搜索的花朵授粉算法

2018-09-18 02:12:26邵良杉韓瑞達

計算機工程與應用 2018年18期

邵良杉，韓瑞達

遼寧工程技術大學系統工程研究所，遼寧葫蘆島 125105

1 引言

群智能算法是一種通過模擬或揭示某些自然現象或過程來解決優化問題的算法，如粒子群優化算法[1]、人工魚群算法[2]等?；ǘ涫诜鬯惴╗3]（Flower Pollination Algorithm，FPA）是由Yang等人在2012年提出的一種模擬自然界開花植物授粉過程的群智能算法，該算法不需要知道待優化函數的具體形式，參數少，易實現，但該算法也存在尋優精度低、后期收斂速度慢等問題。近年來很多學者對FPA算法進行了研究改進和應用：卞京紅等[4]將FPA與螢火蟲算結合，自適應調整轉換概率 p，并在局部授粉過程中引入自適應的變異因子；Zhou[5]等使用精英反向學習初始化種群，提高了初始種群的多樣性；肖輝輝在文獻[6]采用花朵個體間的萬有引力和算法本身的萊維飛行共同實現個體位置的更新，在文獻[7]中，在局部尋優部分對進入下一次迭代的較差個體采用單純形法的擴張、收縮/壓縮操作，提高局部尋優能力；段艷明等[8]通過引入量子系統的態疊加特性，用波函數描述種群個體的位置，提高算法的全局尋優能力；文獻[9]利用高斯變異對FPA算法的全局搜索進行擾動，增強種群的多樣性；文獻[10]通過入侵雜草的繁殖、空間擴散和競爭策略，動態生成種群，增加種群的多樣性和有效性。以上文獻對FPA算法的尋優能力有一定程度上的改進，但很多改進算法存在時間復雜度過高，運行速度慢等問題。

針對花朵授粉算法的收斂速度和精度的問題，本文將天牛須搜索算法（Beetle Antennae Search，BAS）[11]引入花朵授粉算法的全局尋優階段，天牛須搜索算法僅需一個個體，運算簡單且能快速收斂，可以提高FPA算法的收斂速度。將一種變異策略引入局部尋優階段，以提高算法跳出局部最優的能力。

2 花朵授粉算法

2.1 花朵授粉算法介紹

花朵授粉算法是一種模擬自然界開花植物授粉過程的群智能優化算法。在現實的自然界中，每一棵顯花植物可以開多朵花，每朵花產生數百萬甚至數十億的花粉配子。為了使該算法更為高效，FPA對花朵授粉過程進行簡化，每棵顯花植物只開一朵花，且每朵花只產生一個花粉配子。一朵花或一個配子對應于優化問題中的一個解，并且每朵花都是通過轉換概率p進行異花授粉操作，或以概率1-p進行自花授粉操作繁衍后代。異花授粉的范圍較大，可以視為全局搜索；自花授粉的范圍較小，可以視為局部搜索。

根據開花植物的授粉過程，花朵授粉算法總結出四條規律：

（1）異花授粉通過昆蟲或鳥類攜帶花粉來進行，是一種全局授粉過程。

（2）自花授粉通過自然因素進行，是一種局部授粉過程。

（3）花粉的繁殖概率與涉及的兩朵花的相似性成正比。

（4）轉換概率p控制著全局授粉和局部授粉的相互轉換。

2.2 花朵授粉算法流程及缺陷分析

2.2.1 算法流程

FPA的流程圖如圖1。

圖1中公式（1）、（2）分別為：

其中，Γ(λ)是標準的伽瑪函數，λ=1.5。

2.2.2 花朵授粉算法的缺陷分析

為驗證FPA算法各部分的尋優能力和缺陷，設計以下實驗驗證FPA算法的全局尋優能力，局部尋優能力和跳出局部最優的能力。

設置種群數為20，迭代次數為1 000，維度為10，選取具有一定代表性的單峰函數Sphere和多峰函數Rastrigin，求最優值。單峰函數能檢驗算法的收斂速度，多峰函數能檢驗算法是否容易陷入局部最優和跳出局部最優的能力。

圖1 FPA算法的流程

其中Sphere和Rastrigin函數的表達式如公式（4）、（5）所示：

每個函數運行50次，統計其收斂曲線，從圖2可以看出，FPA算法在前400次迭代收斂速度較快，而之后收斂速度很快降低，在900次迭代時收斂曲線幾乎平行于x軸，說明FPA算法后期收斂速度較慢。圖3中，經常有水平線段，說明算法陷入了局部最優，且跳出局部最優需要較多次迭代。說明FPA算法有時會陷入局部最優難以跳出。

圖2 Sphere函數收斂曲線

圖3 Rastrigin函數收斂曲線

為了解決FPA算法后期收斂速度較慢，容易陷入局部最優的問題，提出了基于天牛須搜索的花朵授粉算法。

3 基于天牛須搜索的花朵授粉算法

為了提高FPA算法的收斂速度，將BAS算法融入FPA算法的全局尋優部分。為了提高FPA跳出局部最優的能力，在局部尋優部分用新的差分策略代替原有策略，并加入小概率變異，從而實現BASFPA算法。具體實現如下：

（1）初始化算法參數。

（2）初始化種群，并計算所有解的適應度值。

（3）若 p＞rand，使用天牛須優化的全局搜索對解進行更新。

（4）若 p

（5）計算所有解的適應度值，更新全局最優解和全局最優解的適應度值。

（6）判斷是否滿足迭代結束條件，滿足退出迭代，并輸出最優解及其適應度值，不滿足返回（3）。

BASFPA算法流程圖如圖4所示。

3.1 天牛須搜索介紹

天牛須搜索（Beetle Antennae Search，BAS）是2017年提出的一種智能優化算法。類似于遺傳算法、粒子群算法、蟻群算法等智能優化算法，BAS不需要知道函數的具體形式，就可以實現高效尋優。與其他群智能優化算法不同，BAS只需要一個個體，運算量大大降低。

天牛須搜索的仿生原理如下：當天牛覓食時，天牛不知道食物在哪里，根據食物氣味的強弱來覓食。如果天牛左邊觸角收到的氣味強度比右邊大，那下一步天牛就往左飛，否則往右飛。食物的氣味就相當于一個函數，天牛的目的是找到全局氣味值最大的點。仿照天牛的行為，抽象出BAS算法：

（1）天牛在三維空間運動，為了能在任意維函數使用天牛須搜索，將天牛的覓食行為推廣至任意維空間。

（2）天牛抽象為一個質點，左右兩須位于質點兩邊。

（3）天牛的步長與兩須間的距離成固定比例。

（4）天牛前進一個步長后，頭的朝向是隨機的。

圖4 BASFPA算法的流程

BAS算法流程描述如下：

（1）對于k維優化問題，質心表示為x，左須xl，右須xr，兩須距離d，其中x,xl,xr都是k維向量。

（2）由于天牛頭的朝向隨機，所以生成隨機k維單位向量來表示天牛左須指向右須的向量：

其中，rands(k,1)表示生成k維的隨機向量。

所以左須可以表示為：

右須為：

其中dt表示在第t次迭代時兩須的距離，xt表示第t次迭代時天牛質心的位置。

（3）計算左右兩須xl和 xr的適應度值 fl和 fr，根據 fl和 fr的大小關系，判斷天牛的前進方向：

其中sign為符號函數，δt為第t次迭代時天牛的移動步長。

（4）計算天牛移動后的適應度值，并左右兩須距離和步長：

其中，dt為第t次迭代時兩須的距離，eta_d和eta_δ為兩須距離和步長的衰減系數，通常取0.95。

（5）判斷是否符合迭代結束條件，符合結束迭代，不符合重復（2）～（4）直到符合條件。

3.2 基于天牛須搜索的全局尋優

由文獻[12]可知，BAS算法有很強的全局搜索能力，故將BAS算法應用于FPA算法的全局尋優部分，幫助FPA快速收斂。

在全局搜索部分，在花粉個體按照基本FPA算法移動后，將個體視為天牛，計算其按照BAS算法移動后的適應度值，并與移動前的適應度值比較，若移動后的適應度值更優，則進行移動，否則不進行移動。

改進后的全局搜索為：

3.3 變異策略

由于FPA算法易陷入局部最優，故在其局部尋優部分加入擾動進化策略，以提高算法跳出局部最優的能力。

FPA算法在局部搜索的策略類似于差分進化算法的變異操作?；ǘ涫诜鬯惴ǖ木植克阉鞑呗詾椋?/p>

Zheng[13]等對差分進化算法進行研究后，提出了一種新的差分策略：

式（13）中，以全局最優解作為基向量，個體本身參與變異，能夠更好地平衡變異的隨機性和確定性，既能加快收斂速度，又能減慢算法陷入局部最優的速度。

僅采用單一的差分策略仍有可能導致算法陷入局部最優，而是否能夠跳出局部最優是算法解得全局最優的關鍵。為了增強算法跳出局部最優的能力，在新的差分策略的基礎上，加入了小概率變異策略，使算法跳出局部最優：

最終的局部尋優表達式為：

其中，pl∈[0,1]，一般選取為0.1。其中是解Xi迭代t次和t+1次后的值，為第t次迭代的全局最優解。

3.4 算法時間復雜度分析

基本花朵授粉算法存在兩層循環，其時間復雜度為O(n2)。在BASFPA中，沒有添加新的循環，故算法的時間復雜度仍為O(n2)。由于全局尋優在默認轉換概率0.8下只有20%的執行概率，且天牛須搜索僅需進行兩次適應度值計算，故在全局尋優加入了天牛須搜索對算法的運行時間影響較小。而變異策略添加一個運行概率為10%的向量加法，對算法的運行時間幾乎沒有影響。

4 仿真實驗及結果分析

本文選擇具有代表性的6個函數來驗證BASFPA算法的有效性和優越性，包括單峰、多峰函數，并將測試結果與FPA算法，其他改進的FPA算法進行比較。測試函數選取CEC2013 benchmark[14]測試函數的一部分：

4.1 測試方案

本文測試方案如下：

（1）固定迭代次數下，測試FPA、MFPA、tFPA、BASFPA在30維下的尋優性能。

（2）固定迭代次數下，測試FPA、MFPA、tFPA、BASFPA在100維下的尋優性能。

（3）相同種群數，迭代次數下，對比BASFPA與螢火蟲算法、布谷鳥算法的收斂精度。

（4）相同參數下，設置轉化概率 p=0，比較FPA和BASFPA的全局尋優性能。

（5）相同參數下，設置轉化概率 p=1，比較FPA和BASFPA的局部尋優性能。

4.2 低維下的性能分析

本實驗下，各算法種群數為20，迭代次數1 500次，函數維度均為30維，BASFPA的d0=1,δ0=2,eta_d和eta_δ均為0.95。每種算法獨立運行50次，統計各算法的最優值、平均值、最差值和尋優成功率。實驗結果如表1所示。

表1 低維下的性能分析

從表1可以看出，BASFPA算法的最優值、平均值、最差值均優于FPA、tFPA和MFPA算法。BASFPA算法相比FPA算法，在各函數下尋優結果均有7～20個數量級的提升。除F5的尋優成功率為90%外，其他函數的尋優成功率均為100%。

為了更直觀地比較BASFPA算法與其他三種算法尋優能力，將各算法的收斂曲線表示為圖5～圖10。可以看出，在F1～F6尋優中，BASFPA算法能夠快速收斂，并且只有在F6函數尋優時陷入局部最優，但很快跳出，說明在局部尋優引入新的變異策略能夠幫助算法跳出局部最優。

圖5 F1收斂曲線

圖6 F2收斂曲線

圖7 F3收斂曲線

圖8 F4收斂曲線

圖9 F5收斂曲線

圖10 F6收斂曲線

4.3 固定精度下性能分析

為了檢驗BASFPA達到固定精度所需的迭代次數，設置實驗如下：

各算法種群數為20，函數維度均為30維，BASFPA的d0=1,δ0=2,eta_d和eta_δ均為0.95。每種算法獨立運行50次，目標收斂精度為10-3，統計各算法達到收斂精度所需的迭代次數，如果在3 000次迭代后仍未達到目標精度，則認為尋優失敗。實驗結果如表2所示。

從表2可以看出，對于6個測試函數，BASFPA算法無論是最小收斂代數還是平均收斂代數均優于原算法，與其他花朵授粉改進算法相比，迭代次數明顯降低。由此可見BAS算法對FPA算法的改進是有效的。

4.4 BASFPA與其他優化算法對比

為了比較BASFPA和其他優化算法的尋優精度，設置實驗如下：

各算法種群為20，迭代次數為1 500次。螢火蟲算法[14]（Firefly Algorithm，FA）的參數為α=0.2，β=0.7，γ=2；布谷鳥算法[15]（Cuckoo Search，CS）的參數為：pc=0.1,p=0.25。BASFPA的參數同4.2節，每個算法在每個函數獨立運行50次。實驗結果如表3所示。

從表3可以看出，對于6個測試函數，BASFPA算法無論是最小收斂代數還是平均收斂代數均優于FA和CS算法，在F2、F3的尋優中，只有BASFPA能收斂到目標精度。