多模函數優化的改進花朵授粉算法

郭慶， 惠曉濱， 張賈奎， 李正欣

(空軍工程大學 裝備管理與安全工程學院， 西安 710051)

花朵授粉算法(Flower Pollination Algorithm，FPA)是由英國劍橋大學學者Yang于2012年提出的，其基本思想來源于對自然界花朵自花授粉、異花授粉的模擬，是一種新的元啟發式群智能隨機優化技術[1]。之后，Yang等[2-3]在FPA的基礎上模擬花朵多配子的形式提出了多目標的FPA (Multi-Objective Flower Pollination Algorithm，MOFPA)。該算法的尋優框架主要由Levy飛行的全局勘探機制、概率調控全局勘探與局部開采的平衡機制以及貪婪式的進化機制組成。FPA的參數相對較少、容易調控等優勢使得該算法在一些領域得到了廣泛的應用。在經濟領域，Al-Ma’Shumah等[4]應用該算法解決市場周期價值問題，Prathiba[5]和Dubey[6]等應用該算法解決經濟調度問題；在工程領域，Abdelaziz等應用該算法解決電力調度問題[7]，Sharawi等[8]應用該算法解決無線傳感器網絡優化問題；在醫學領域，Emary等[9]應用該算法解決視網膜血管分割問題等。

FPA與經典的粒子群優化(PSO)算法、人工蜂群算法、布谷鳥算法等仿生算法相同，也存在易陷入局部最優、易早熟和后期收斂速度慢等典型缺點。為了克服這些缺點，國外許多學者(中國當前研究較少)在FPA的基礎上進行一些針對性的研究與創新。如Wang和Zhou[10]引入鄰域搜索策略、維度評價及更改策略和動態切換概率策略對算法進行改進，提高算法在高維函數優化問題的全局勘探與開發能力；Abdel-Raouf等[11]針對定積分的求解問題結合混沌優化技術提出一種改進花朵授粉算法(IFPCH)，針對數獨問題并結合和聲搜索算法提出一種混合花朵授粉算法(FPCHS)[12]，從不同側面改善FPA的收斂性能；El-Henawy和Ismail[13]將粒子群優化算法與FPA相融合提出一種混合算法，并將其應用到求解整數規劃問題及帶約束的全局優化問題[14]；ukasik和Kowalski[15]對FPA進行更加詳盡的描述以及對其所涉及的參數進行了研究，并與經典的粒子群優化算法進行了對比，得出FPA前期收斂速度不如粒子群優化算法，但其后期種群的多樣性要優于粒子群優化算法的結論。

上述的各種研究改進算法，在某些方面提高了FPA的尋優性能，但FPA在其他領域仍存在一些不足，需要不斷地改進與創新。如在多模復雜函數尋優問題上，FPA的全局勘探與局部開采能力表現不是很理想。為此，本文針對這一問題進行研究，首先從單峰函數尋優入手探究FPA的尋優機理，再結合多峰函數尋優分析FPA在多模尋優時存在的問題，最后結合模擬退火(Simulated Annealing，SA)及Nelder-Mead單純形法提出一種改進的花朵授粉法——NS-FPA。

1 花朵授粉算法及其尋優分析

1.1 花朵授粉算法

Yang[1]通過對自然界顯性花朵授粉的分析與研究，將花朵授粉分為兩大基本形式：生物異花授粉與非生物自花授粉。并依據花朵的常性與授粉行為抽象出以下4條規則：

1) 生物異花授粉被考慮為算法的全局勘探行為，并由傳粉者攜帶花粉通過Levy飛行的機制實現全局授粉。

2) 非生物自花授粉被視為算法的局部開采行為，或稱局部授粉。

3) 花朵的常性可以被認為是繁衍概率，它與兩朵參與授粉花朵的相似性呈正比例關系。

4) 花朵的全局授粉與局部授粉通過轉換概率p∈[0,1]進行調節。由于物理上的鄰近性和風等因素的影響，在整個授粉活動中，轉換概率p是一個非常重要的參數。文獻[1]中對該參數的試驗研究認為，取p=0.8更利于算法尋優。

實際情況下，每棵顯花植物擁有許多花朵，并且每朵花都有成千上萬的花朵配子。為了算法的實現，Yang[1]假設每棵顯花植物僅有一朵花，每朵花僅包含一個配子，每個配子被視為解空間中的一個候選解。FPA尋優的偽代碼如下：

Code：FPA()

Objective：minf(x)/maxf(x)，x=(x1,x2,…,xd)

Input：N,Kmax,p,λ

計算最優解xbest、最優值ybest；

while(t

fori=1, 2,…,Ndo

if rand

依據式(1)執行全局授粉；

else

依據式(2)執行局部授粉；

endif

計算子代花粉的函數值；

更新花粉的位置；

endfor

更新最優解xbest、 最優值ybest；

endwhile

Output：xbest,ybest

(1)

(2)

(3)

其中:Γ(λ)為伽馬函數，λ=1.5；s為步長；s0為最小步長。文獻[1]中采用Mantegna’s算法生成Levy飛行步長L。

1.2 尋優分析

為了定性分析FPA在尋優過程中花粉種群多樣性的變化及尋優特性，本文針對FPA定義如下2個基本參數。

定義1多樣性(diversity)是指每一代花粉的離散程度，簡記為Div。則第t代離散程度Divt計算式為

(4)

(5)

定義2差異性(difference)是指花粉種群子代與父代的差異程度，簡記為Dif。則第t代差異程度Dift計算式為

(6)

式中：R為花粉最大移動半徑(即解空間的半徑)。

在FPA尋優過程中，通過對花粉多樣性Div與差異性Dif的聯合刻畫以分析花粉種群多樣性的動態變化，再結合尋優迭代過程中花粉位置的動態變化分析FPA的尋優特點。

首先，從單峰函數尋優入手。圖1為二維Sphere函數的3D圖，該函數是典型的單峰函數。

依據參考文獻[1，3]的算法流程及參數設定(花粉數量取30)對該Sphere函數進行100次迭代尋優，其多樣性Div與差異性Dif變化曲線如圖2所示。

圖3為FPA進化過程中花粉配子在解空間內的動態分布圖。圖中，從第1、10、30、50、80、100代花粉種群在解空間中分布，可以直觀的看出隨著種群的進化，花粉種群在解空間的分布趨于集中，直至全部集中在全局最優位置；而反映在圖2中的則是花粉種群的多樣性指標Div隨著進化代次的增加基本呈衰減走勢，這說明花粉的空間多樣性在不斷銳減。從圖3中還能夠看出，第50代以后，花粉種群基本都已聚集到全局最優值附近；表現在圖2中的則是差異性指標Dif在第50代之后波動較小且基本趨于0，這說明算法后期花粉在廣闊解空間區域的全局勘探能力基本喪失，這對多模復雜函數尋優是極其不利的，很可能會致使算法陷入局部最優。另外，單峰函數不會存在陷入到局部最優的情況，能夠集中體現算法的局部開采能力，將圖3中第100代的花粉分布圖進行局部放大，如圖4(紅星代表最小值點)所示。可以看出當x、y坐標放大到0.1等級時，花粉已經遠離最小值點，這說明FPA的局部開采能力較為薄弱。

圖1 Sphere函數3D圖Fig.1 3D figure of Sphere function

圖2 Sphere函數FPA尋優參數變化曲線Fig.2 Parameter variation curves of Sphere function using FPA optimization

其次，對多模函數進行尋優，分析FPA對多模復雜函數的尋優缺點。圖5為Bridge函數的3D圖，該函數峰值較多，是較為復雜的多模函數。同樣依據文獻[1，3]對該函數進行100次迭代尋優實驗，給出參數變化曲線(見圖6)及花粉種群的空間分布圖(見圖7)。

圖7中，單從第1、10、30、50、80、100代花粉種群在解空間中的分布看，每代的花粉種群分布都較為松散，沒有一部分花粉集中的現象。再對比第1、10、30、50、80、100代花粉的空間分布，可以看出第50、80、100代的花粉種群在解空間的位置分布基本一致。從圖6可以看出多樣性指標Div在第50代之后無波動、基本趨于平穩，差異性指標Dif在第50代之后基本為0、無明顯的波動。這說明50代之后大部分花粉已陷入到局部最優位置無法進行位置更新，這使得算法的全局勘探能力下降，以至于無法探索到全局最優位置，證實了上述的可能性。同時，也檢驗了2個參數指標(Div、Dif)聯合分析的合理性與有效性。

圖3 Sphere函數FPA尋優花粉分布Fig.3 Pollen distribution of Sphere function using FPA optimization

圖4 圖3第100代的局部放大Fig.4 Partial enlargement of Fig.3the 100th generation

圖5 Bridge函數3D圖Fig.5 3D figure of Bridge function

圖6 Bridge函數FPA尋優參數變化曲線Fig.6 Parameter variation curves of Bridge function using FPA optimization

圖7 Bridge函數FPA尋優花粉分布Fig.7 Pollen distribution of Bridge function using FPA optimization

最后結合FPA的具體流程，筆者認為造成FPA后期花粉差異性為0的主要原因在于FPA的貪婪式進化機制(子代的函數值比父代優才能進化)，使算法貪婪過度，長期無法進行位置更新，從而導致多數的花粉陷入到局部最優位置，致使FPA的全局開拓能力削弱。理想狀態的種群分布狀況應該是：部分種群在不斷聚集，即算法的局部開采性；而另一部分種群在全局空間內不斷的探索，即算法的全局勘探性。而表現在Div、Dif上應當是：種群多樣性的保持及算法后期差異性的延續(不為0)。

2 改進策略及改進的花朵授粉算法

2.1 改進策略

針對FPA在多模復雜函數尋優的缺點，對算法進行改進。在全局授粉過程中引入模擬退火的思想，采取Metropolis準則對新狀態進行更新。模擬退火的Metropolis準則[16]是依概率的形式對新狀態進行更新，在FPA的全局授粉中引入該準則，將改善算法的過度貪婪情況，從而提高全局勘探能力。另外，為了進一步提高FPA的局部開采能力，結合改進的Nelder-Mead單純形法對FPA的局部授粉行為進行重構。

Nelder-Mead單純形法是由Nelder和Mead[17]于1965年提出的一種用于優化多維無約束問題的搜索算法。此算法通過在D維空間中取D+1個點構成一個單純形，計算其頂點函數值；然后對最差點進行內部壓縮、外部壓縮、映射和擴展等操作，以獲得更好的點取代最差點，重構單純形，從而不斷的逼近最優點。此算法是一種直接的搜索算法，其尋優不受目標函數的連續性與可導性影響，具備精細的局部開采能力。為此，本文類比該算法的優勢對FPA的局部授粉進行重構，以增強FPA的收斂精度。重構的局部授粉過程如下：

首先，利用花粉i及其周圍最近的m-1個花粉的位置信息構建單純形(見圖8)，并根據式(7)計算單純形的中心：

圖8 Nelder-Mead單純形法Fig.8 Nelder-Mead simplex method

(7)

(8)

2.2 改進的花朵授粉算法

結合改進策略及基本FPA的計算流程，給出NS-FPA的基本實現步驟(以尋最小值為例)及其流程圖(見圖9)。

圖9 NS-FPA流程Fig.9 Flowchart of NS-FPA

步驟1初始參數，設定花粉種群規模N、最大迭代次數Kmax、轉換概率p、初溫概率p0、溫度衰減系數γ等。

步驟2在解空間里隨機初始化花粉位置x0，并計算目標函數值y0；初始溫度T0可由式(9)計算：

(9)

式中：p0通常取0.7～0.9[19]。

步驟3計算當前的全局目標函數最小值，并記錄對應得最優解xbest。

步驟4若條件(rand

步驟5全局授粉：依據式(1)計算子代花粉位置，并計算目標函數值；由式(10)計算可接受概率pr；若條件(rand

(10)

步驟6局部授粉：依據2.1節中重構的局部授粉過程進行。

步驟7降溫：按式(11)進行降溫操作：

T=T0γtt=1,2,…,Kmax

(11)

式中：γ通常取0.7～0.99[19]。

步驟8計算全局目標函數值的最小值，并更新最優解xbest。

步驟9若滿足終止條件，則輸出全局最優解；否則，轉至步驟4。

3 仿真計算

為了驗證NS-FPA的有效性，首先結合1.2節對NS-FPA進行定性仿真分析，驗證算法改進后的全局勘探能力；其次，選取多個多模復雜函數進行尋優仿真實驗，定量分析NS-FPA的收斂速度與收斂精度，從而分析NS-FPA的局部開采能力及綜合性能；然后，對NS-FPA中新增的2個參數p0、γ進行探討，以確定其取值范圍；最后，對比NS-FPA、FPA的時間復雜度，探討NS-FPA的缺失。

3.1 定性仿真分析

為了與1.2節形成鮮明對比，本節同樣針對二維Sphere函數及Bridge函數采用NS-FPA在同樣參數下進行100次迭代尋優，并給出尋優過程中花粉多樣性Div指標與差異性Dif指標變化曲線及花粉的動態分布圖(見圖10～圖14)以定性分析NS-FPA的尋優特性。

從圖11和圖14中可以直觀地看出：無論對Sphere函數還是Bridge函數尋優，第10、30、50、80、100代花粉種群在空間的分布均呈現一部分種群聚集、另一部分種群松散的特征(由于第1代是隨機初始化，因此整體較為松散、種群差異性最大)。另外，各代之間的種群分布除全局最優值附近的集中種群分布相似，這是說明部分花粉正在逐步向全局最優位置聚攏，體現了算法的導向性；分散的那部分種群分布有較大的差異，這是說明另外一部分花粉在不斷的開拓新區域，體現了種群的全局勘探性。而從圖10和圖13中則可以看出：種群的多樣性指標Div及差異性指標Dif在算法的1～10代(起始階段)有略微的下降，因為這是算法由完全的隨機性逐漸地向算法兼顧隨機性與導向性轉變的過程；第10代之后Div與Dif基本呈平穩的波動狀態，無整體的銳減趨勢。

圖10 Sphere函數NS-FPA尋優參數變化曲線Fig.10 Parameter variation curves of Sphere function using NS-FPA optimization

圖11 Sphere函數NS-FPA尋優花粉分布Fig.11 Pollen distribution of Sphere function using NS-FPA optimization

圖12 圖11第100代的局部放大Fig.12 Partial enlargement of Fig.11 the 100th generation

圖13 Bridge函數NS-FPA尋優參數變化曲線Fig.13 Parameter variation curves of Bridge function using NS-FPA optimization

圖14 Bridge函數NS-FPA尋優花粉分布Fig.14 Pollen distribution of Bridge function using NS-FPA optimization

這說明NS-FPA在算法運行的中后期能夠很好的保持花粉種群的多樣性與差異性，從而增加花粉跳出局部最優的幾率，這對多模函數尋優是有利的。

與圖2～圖4、圖6和圖7相對比，可以得出以下結論：改進的FPA在多模函數尋優過程中能夠保證花粉的多樣性及差異性，從而能夠避免算法陷入局部最優，有效地保證了FPA的全局勘探能力，基本達到了1.2節中所述的種群分布的理想狀態。最后，結合圖4和圖12可看出NS-FPA的局部開采能力得到了明顯的改善。

3.2 定量仿真分析

選擇15個多模復雜測試函數、1個單峰函數進行仿真實驗并與FPA、布谷鳥算法(CS)[20]、螢火蟲算法(FA)[21]進行對比(見表1)。16個標準測試函數的基本信息如表2所示。為了更加直觀地表現測試函數的復雜性，圖1(F1)、圖5(F11)和圖15給出了F1～F16的二維函數3D圖。

通過圖15再結合圖1和圖5，16個測試函數的多模復雜程度有所差異，但基本可以分為3類：F1(單峰)，F2～F8(多模)，F9～F16(超多模)。為了保證評價的客觀性，在測試中分別對16個函數進行50次仿真計算，用50次仿真結果的統計特性對對比結果進行分析。依據文獻[1,22]分別對4種尋優算法進行參數設定，如表1所示。其仿真對比結果如表3所示。

表1 4個算法的參數設置

注：公共參數:種群規模N=50；最大迭代次數Kmax，F1～F13

取100，F14～F16取10 000。

表2 16個標準測試函數

圖15 二維函數3D圖Fig.15 3D figures of 2D functions

函數代號FPACS最優值平均值標準差最優值平均值標準差F12．825．421．639．85×10-72．37×10-35．49×10-4F2-106．7645-106．76272．24×10-3-106．7645-106．75701．64×10-3F3-0．9998-0．99701．88×10-3-0．9997-0．99451．21×10-3F46．46×10-52．46×10-23．49×10-22．56×10-11．813．97×10-1F52．09×10-62．41×10-35．07×10-31．88×10-30．531．24×10-1F6-3．2539-3．25373．20×10-4-3．2539-3．25331．29×10-4F7-2．0626-2．06237．46×10-5-2．0626-2．06252．11×10-5F8-19．2085-19．20831．73×10-4-19．2085-19．20827．18×10-5F9-0．9933-0．94731．77×10-2-0．9865-0．93621．77×10-2F101．24×10-52．93×10-23．70×10-24．06×10-65．60×10-31．40×10-3F11-3．0041-2．87718．56×10-2-2．9280-2．65127．64×10-2F12-186．7307-186．71252．68×10-2-186．7308-186．70986．13×10-3F136．6015．365．012．938．051．46F143．876．341．174．668．350．92F154．6411．292．662．736．971．21F16-49．61-49．220．16-49．84-49．749．33×10-2函數代號FANS?FPA最優值平均值標準差最優值平均值標準差F18．63×10-115．79×10-95．66×10-93．88×10-91．82×10-52．89×10-5F2-106．7645-104．93935．23-106．7645-106．76454．76×10-6F3-1．0000-0．99981．06×10-4-1．0000-0．99997．81×10-5F46．70×10-74．88×10-48．66×10-48．32×10-95．00×10-53．94×10-5F58．34×10-83．59×10-65．29×10-65．15×10-91．88×10-71．70×10-7F6-3．2539-3．25318．20×10-4-3．2539-3．25395．93×10-6F7-2．0626-2．06261．77×10-4-2．0626-2．06261．30×10-8F8-19．2085-19．20799．73×10-4-19．2085-19．20854．50×10-10F9-1．0000-0．99491．75×10-2-1．0000-0．99991．99×10-4F104．68×10-91．41×10-72．10×10-71．26×10-106．79×10-97．70×10-9F11-3．0054-2．93360．20-3．0054-3．00513．18×10-4F12-186．7309-177．764813．30-186．7309-186．73085．50×10-4F132．38×10-61．331．4101．18×10-77．42×10-7F141．80×10-33．83×10-31．12×10-36．46×10-121．62×10-71．09×10-6F153．00×10-47．47×10-20．192．97×10-41．32×10-37．53×10-4F16-49．87-9．629．83×10-2-50．00-49．992．51×10-4

首先,分別從多模、超多模函數的尋優結果中對比FPA與NS-FPA的尋優特性。表3中，從多模函數F2～F8的尋優對比結果中可以看出，F2函數：FPA 50次尋優的最優值能夠達到精確解，而平均值卻只能夠達到小數點后2位；NS-FPA的最優值及平均值都能夠達到精確解；再看標準差，FPA值達到10-3，而NS-FPA達到10-6，比FPA高3個數量級，這說明NS-FPA要更穩定。F3函數：FPA的最優值精度達到10-3，平均值精度達到10-2；而NS-FPA的最優值為精確解，平均值精度達到10-4，標準差比FPA高2個數量級。F4函數：FPA的最優值精度達到10-5，平均值精度達到10-2；而NS-FPA的最優值精度達到10-9，平均值精度達到10-5，標準差比FPA高3個數量級。F5函數：FPA的最優值精度達到10-6，平均值精度達到10-3；而NS-FPA的最優值精度達到10-9，平均值精度達到10-7，標準差比FPA高4個數量級。F6函數：FPA的最優值能夠達到精確解，平均值精度達到10-3；而NS-FPA的最優值及平均值都達到精確解，標準差比FPA高2個數量級。F7函數：FPA的最優值能夠達到精確解，平均值精度達到10-3；而NS-FPA的最優值及平均值都達到精確解，標準差比FPA高3個數量級。F8函數：FPA的最優值能夠達到精確解，平均值精度達到10-3；而NS-FPA的最優值及平均值都達到精確解，標準差比FPA高6個數量級。

在超多模函數F9～F16的尋優對比結果中，F9函數：FPA的最優值精度達到10-2，平均值精度達到10-1；而NS-FPA的最優值達到精確解，平均值精度達到10-4，標準差比FPA高2個數量級。F10函數：FPA的最優值精度達到10-5，平均值精度達到10-2；而NS-FPA的最優值精度達到10-10，平均值精度達到10-9，標準差比FPA高7個數量級。F11函數：FPA的最優值精度達到10-2，平均值精度較差；而NS-FPA的最優值達到精確解，平均值精度達到10-3，標準差比FPA高2個數量級。F12函數：FPA的最優值精度達到10-3，平均值精度為10-1；而NS-FPA的最優值達到精確解，平均值精度達到10-4，標準差比FPA高2個數量級。對于高維超多模函數F13～F16，FPA基本失去了尋優精度，而NS-FPA依舊能夠尋優且平均尋優精度均達到10-3以上，標準差也達到10-4以上,這驗證了改進方案的有效性。

從整體上看，NS-FPA的尋優精度要比FPA至少高出2個數量級，尋優穩定性(標準差)高出2～7個數量級，這說明相對于FPA，NS-FPA能夠更好的處理多峰尋優，且具有較高的穩定性。

其次，與Yang等[20-21]近幾年提出的布谷鳥算法、螢火蟲算法進行對比。表3中，對于多模函數F2～F8的尋優，可以看出FPA與CS的最優值、平均值、標準差幾乎相當。除F2函數外，FA的最優值、平均值、標準差要略微優于FPA與CS,但NS-FPA的評價指標都要優于FPA、CS、FA，至少高2個數量級的計算精度。對于超多模函數F9～F16，FPA與CS的尋優效果相當；F8～F9，FA的尋優效果要劣于CS與FPA；F10～F16，FA的尋優效果要優于CS與FPA；但NS-FPA的尋優效果都要明顯優于FPA、CS、FA。綜合來看，NS-FPA對多模尋優的處理要更優于FPA、CS、FA。

最后，圖16給出F11函數50次優化結果對比，從圖中可以直觀地看出NS-FPA與FPA、CS、FA相比尋優結果波動性較小、更加穩定，這說明NS-FPA的魯棒性較好，也間接證實了模擬退火策略能夠使得FPA成功避免陷入局部最優，從而保證了算法的全局勘探性。圖17為F11函數優化過程進化曲線對比，從圖中可以看出NS-FPA的尋優結果更靠近理論值-3，并且收斂速度也要快于FPA、CS、FA。為了直觀地體現各個算法的收斂精度，圖18以對數坐標軸的形式給出F13函數優化過程進化曲線對比，從圖中可以看出NS-FPA的終止計算精度達到了10-15，并且仍有下降的趨勢，這體現NS-FPA優秀的局部開采能力，也進一步證實了NS-FPA的有效性。

圖16 F11函數50次尋優結果對比Fig.16 Comparison of 50 times’ optimization results of F11 function

圖17 F11函數尋優進化曲線 Fig.17 Optimization evolution curves of F11 function

圖18 F13函數尋優進化曲線Fig.18 Optimization evolution curves of F13 function

3.3 NS-FPA的參數分析

盡管NS-FPA的尋優效果較好，與FPA相比，NS-FPA多了2個基本參數初溫概率p0、溫度衰減系數γ。為了討論其對NS-FPA尋優性能的影響，本節以超多模函數F9為例，進行仿真計算實驗。

首先，討論初溫概率p0對算法性能的影響。實驗時其他參數不改變，設定不同的p0后, 分別對F9函數進行50次尋優計算，統計結果如表4所示(左側三欄)。從表4中可以看出隨著p0的增大，算法的平均值不斷逼近理論解，且標準差不斷變小(標準差越小，算法的魯棒性越好)，直至p0取0.7時，達到最優，之后有所下降。當p0取0.6～0.9時，平均值、標準差達到高于10-4的精度。因此，在尋優計算時建議p0取0.6～0.9。

其次，討論溫度衰減系數γ對算法性能的影響。同樣，在實驗時其他參數不改變，設定不同的γ后, 分別對F9函數進行50次尋優計算，統計結果如表4所示(右側三欄)。從表4中可以看出，隨著γ增大，算法的平均值和標準差逐漸變小，直至γ=0.8時，達到最小，之后有所增加。當γ取0.7～0.9時，平均值、標準差達到高于10-4的精度。因此，在尋優計算時建議γ取0.7～0.9。

表4 不同p0、γ參數下的NS-FPA尋優結果

3.4 NS-FPA的時間復雜度分析

與FPA相比，NS-FPA的局部授粉較為復雜，在算法復雜度上要大于FPA。為直觀地對比2種算法的時間復雜度，本節從3.2節選擇6個測試函數分別用FPA、NS-FPA在同一平臺上單獨進行50次尋優實驗，統計50次實驗的平均耗時，結果如表5所示。

表5中，NS-FPA的平均耗時要大于FPA，且平均高出32.49%。再考慮到3.2節中，對于FPA不能求解的多模函數，NS-FPA卻具有較好的尋優性能，筆者認為在時間上多出32.49%的消耗是值得的，它增強了算法的求解性能。

表5 NS-FPA與FPA的平均消耗時間對比

4 結 論

本文針對多模復雜函數優化問題對FPA進行研究，首先提出了種群多樣性指標與差異性指標，定性分析了基本FPA的尋優缺陷；然后，基于模擬退火的思想解決算法過度貪婪的問題，再結合Nelder-Mead單純形法對局部授粉過程進行重構，提出一種改進的花朵授粉算法——NS-FPA。通過定性、定量的方式對其進行仿真對比分析得出以下結論：

1) 基于模擬退火思想的全局授粉行為能夠避免FPA陷入局部最優，改善了FPA的全局勘探能力，解決了算法早熟的問題。

2) 重構的局部授粉行為改善了算法的局部開采能力，大大提升了算法的收斂速度與收斂精度。

3) NS-FPA可以用來解決多模復雜優化問題。

4) NS-FPA在尋優時需要比FPA多消耗32.49%的時間。

參考文獻 (References)

[1] YANG X S.Flower pollination algorithm for global optimization[C]∥International Conference on Unconventional Computation and Natural Computation.Berlin:Springer,2012:240-249.

[2] YANG X S,KARAMANOGLU M,HE X.Multi-objective flower algorithm for optimization[J].Procedia Computer Science,2014,18(1):861-868.

[3] YANG X S,KARAMANOGLU M,HE X.Flower pollination algorithm:A novel approach for multiobjective optimization[J].Engineering Optimization,2014,46(9):194-195.

[4] AL-MA’SHUMAH F,PERMANA D,SIDARTO K A.Solving inverse problem for Markov chain model of customer lifetime value using flower pollination algorithm[J].Journal of Molecular Structure,2015,1692(1):7-11.

[5] PRATHIBA R,MOSES M B,SAKTHIVEL S.Flower pollination algorithm applied for different economic load dispatch problems[J].International Journal of Engineering & Technology,2014,6(2):1009-1016.

[6] DUBEY H M,PANDIT M,PANIGRAHI B K.Hybrid flower pollination algorithm with time-varying fuzzy selection mechanism for wind integrated multi-objective dynamic economic dispatch[J].Renewable Energy,2015,83:188-202.

[7] ABDELAZIZ A Y,ALI E S,ELAZIM S M A.Implementation of flower pollination algorithm for solving economic load dispatch and combined economic emission dispatch problems in power systems[J].Energy,2016,101:506-518.

[8] SHARAWI M,EMARY E,IMANE A,et al.Flower pollination optimization algorithm for wireless sensor network lifetime global optimization[J].Applied Soft Computing,2014，4(3):2231-2307.

[9] EMARY E,ZAWBAA H M,HASSANIEN A E,et al.Retinal vessel segmentation based on flower pollination search algorithm[M].Berlin:Springer,2014:93-100.

[10] WANG R,ZHOU Y Q.Flower pollination algorithm with dimension by dimension improvement[J].Mathematical Problems in Engineering,2014,2014:481791.

[11] ABDEL-RAOUF O,ABDEL-BASET M,EL-HENAWY I.An improved flower pollination algorithm with chaos[J].International Journal of Education & Management Engineering,2014,4(2):1-8.

[12] ABDEL-RAOUF O,EL-HENAWY I,ABDEL-BASET M.A novel hybrid flower pollination algorithm with chaotic harmony search for solving sudoku puzzles[J].International Journal of Engineering Trends & Technology,2014,6(3):126-132.

[13] EL-HENAWY I,ISMAIL M.An improved chaotic flower pollination algorithm for solving large integer programming problems[J].International Journal of Digital Content Technology & Its Applic,2014,8(3):72-79.

[14] ABDEL-RAOUF O,ABDEL-BASET M,EL-HENAWY I.A new hybrid flower pollination algorithm for solving constrained global optimization problems[J].International Journal of Applied Operational Research,2014,3(2):21-28.

[16] 傅文淵，凌朝東.布朗運動模擬退火算法[J].計算機學報，2014,37(6):1301-1308.

FU W Y,LING C D.Brownian motion based simulated annealing algorithm[J].Chinese Journal of Computers,2014,37(6):1301-1308(in Chinese).

[17] NELDER J A,MEAD R A.A simplex method for function minimization[J].The Computer Journal,1965,7(4)：308-313.

[18] NAZARETH L,TSENG P.Gilding the lily:A variant of the Nelder-Mead algorithm based on golden-section search[J].Computational Optimization & Applications,2002,22(1):133-144.

[19] YANG X S.Nature-inspired optimization algorithms[M].Beckington：Luniver Press,2014:67-75.

[20] YANG X S,DEB S.Cuckoo search:Recent advances and applications[J].Neural Computing and Applications,2014,24(1):169-174.

[21] YANG X S,HE X.Firefly algorithm:Recent advances and applications[J].International Journal of Swarm Intelligence,2013,1(1):36-50.

[22] KAIPA K N,GHOSE D.Glowworm swarm optimization:Theory,algorithms,and applications[M].Berlin:Springer,2017:91-131.