多模函數(shù)優(yōu)化的改進(jìn)花朵授粉算法

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

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

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

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

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

1 花朵授粉算法及其尋優(yōu)分析

1.1 花朵授粉算法

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

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

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

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

4) 花朵的全局授粉與局部授粉通過轉(zhuǎn)換概率p∈[0,1]進(jìn)行調(diào)節(jié)。由于物理上的鄰近性和風(fēng)等因素的影響，在整個(gè)授粉活動(dòng)中，轉(zhuǎn)換概率p是一個(gè)非常重要的參數(shù)。文獻(xiàn)[1]中對該參數(shù)的試驗(yàn)研究認(rèn)為，取p=0.8更利于算法尋優(yōu)。

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

Code：FPA()

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

Input：N,Kmax,p,λ

計(jì)算最優(yōu)解xbest、最優(yōu)值ybest；

while(t

fori=1, 2,…,Ndo

if rand

依據(jù)式(1)執(zhí)行全局授粉；

else

依據(jù)式(2)執(zhí)行局部授粉；

endif

計(jì)算子代花粉的函數(shù)值；

更新花粉的位置；

endfor

更新最優(yōu)解xbest、 最優(yōu)值ybest；

endwhile

Output：xbest,ybest

(1)

(2)

(3)

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

1.2 尋優(yōu)分析

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

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

(4)

(5)

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

(6)

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

在FPA尋優(yōu)過程中，通過對花粉多樣性Div與差異性Dif的聯(lián)合刻畫以分析花粉種群多樣性的動(dòng)態(tài)變化，再結(jié)合尋優(yōu)迭代過程中花粉位置的動(dòng)態(tài)變化分析FPA的尋優(yōu)特點(diǎn)。

首先，從單峰函數(shù)尋優(yōu)入手。圖1為二維Sphere函數(shù)的3D圖，該函數(shù)是典型的單峰函數(shù)。

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

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

圖1 Sphere函數(shù)3D圖Fig.1 3D figure of Sphere function

圖2 Sphere函數(shù)FPA尋優(yōu)參數(shù)變化曲線Fig.2 Parameter variation curves of Sphere function using FPA optimization

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

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

圖3 Sphere函數(shù)FPA尋優(yōu)花粉分布Fig.3 Pollen distribution of Sphere function using FPA optimization

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

圖5 Bridge函數(shù)3D圖Fig.5 3D figure of Bridge function

圖6 Bridge函數(shù)FPA尋優(yōu)參數(shù)變化曲線Fig.6 Parameter variation curves of Bridge function using FPA optimization

圖7 Bridge函數(shù)FPA尋優(yōu)花粉分布Fig.7 Pollen distribution of Bridge function using FPA optimization

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

2 改進(jìn)策略及改進(jìn)的花朵授粉算法

2.1 改進(jìn)策略

針對FPA在多模復(fù)雜函數(shù)尋優(yōu)的缺點(diǎn)，對算法進(jìn)行改進(jìn)。在全局授粉過程中引入模擬退火的思想，采取Metropolis準(zhǔn)則對新狀態(tài)進(jìn)行更新。模擬退火的Metropolis準(zhǔn)則[16]是依概率的形式對新狀態(tài)進(jìn)行更新，在FPA的全局授粉中引入該準(zhǔn)則，將改善算法的過度貪婪情況，從而提高全局勘探能力。另外，為了進(jìn)一步提高FPA的局部開采能力，結(jié)合改進(jìn)的Nelder-Mead單純形法對FPA的局部授粉行為進(jìn)行重構(gòu)。

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

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

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

(7)

(8)

2.2 改進(jìn)的花朵授粉算法

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

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

步驟1初始參數(shù)，設(shè)定花粉種群規(guī)模N、最大迭代次數(shù)Kmax、轉(zhuǎn)換概率p、初溫概率p0、溫度衰減系數(shù)γ等。

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

(9)

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

步驟3計(jì)算當(dāng)前的全局目標(biāo)函數(shù)最小值，并記錄對應(yīng)得最優(yōu)解xbest。

步驟4若條件(rand

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

(10)

步驟6局部授粉：依據(jù)2.1節(jié)中重構(gòu)的局部授粉過程進(jìn)行。

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

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

(11)

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

步驟8計(jì)算全局目標(biāo)函數(shù)值的最小值，并更新最優(yōu)解xbest。

步驟9若滿足終止條件，則輸出全局最優(yōu)解；否則，轉(zhuǎn)至步驟4。

3 仿真計(jì)算

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

3.1 定性仿真分析

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

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

圖10 Sphere函數(shù)NS-FPA尋優(yōu)參數(shù)變化曲線Fig.10 Parameter variation curves of Sphere function using NS-FPA optimization

圖11 Sphere函數(shù)NS-FPA尋優(yōu)花粉分布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函數(shù)NS-FPA尋優(yōu)參數(shù)變化曲線Fig.13 Parameter variation curves of Bridge function using NS-FPA optimization

圖14 Bridge函數(shù)NS-FPA尋優(yōu)花粉分布Fig.14 Pollen distribution of Bridge function using NS-FPA optimization

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

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

3.2 定量仿真分析

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

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

表1 4個(gè)算法的參數(shù)設(shè)置

注：公共參數(shù):種群規(guī)模N=50；最大迭代次數(shù)Kmax，F(xiàn)1～F13

取100，F(xiàn)14～F16取10 000。

表2 16個(gè)標(biāo)準(zhǔn)測試函數(shù)

圖15 二維函數(shù)3D圖Fig.15 3D figures of 2D functions

函數(shù)代號FPACS最優(yōu)值平均值標(biāo)準(zhǔn)差最優(yōu)值平均值標(biāo)準(zhǔn)差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函數(shù)代號FANS?FPA最優(yōu)值平均值標(biāo)準(zhǔn)差最優(yōu)值平均值標(biāo)準(zhǔn)差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

首先,分別從多模、超多模函數(shù)的尋優(yōu)結(jié)果中對比FPA與NS-FPA的尋優(yōu)特性。表3中，從多模函數(shù)F2～F8的尋優(yōu)對比結(jié)果中可以看出，F(xiàn)2函數(shù)：FPA 50次尋優(yōu)的最優(yōu)值能夠達(dá)到精確解，而平均值卻只能夠達(dá)到小數(shù)點(diǎn)后2位；NS-FPA的最優(yōu)值及平均值都能夠達(dá)到精確解；再看標(biāo)準(zhǔn)差，F(xiàn)PA值達(dá)到10-3，而NS-FPA達(dá)到10-6，比FPA高3個(gè)數(shù)量級，這說明NS-FPA要更穩(wěn)定。F3函數(shù)：FPA的最優(yōu)值精度達(dá)到10-3，平均值精度達(dá)到10-2；而NS-FPA的最優(yōu)值為精確解，平均值精度達(dá)到10-4，標(biāo)準(zhǔn)差比FPA高2個(gè)數(shù)量級。F4函數(shù)：FPA的最優(yōu)值精度達(dá)到10-5，平均值精度達(dá)到10-2；而NS-FPA的最優(yōu)值精度達(dá)到10-9，平均值精度達(dá)到10-5，標(biāo)準(zhǔn)差比FPA高3個(gè)數(shù)量級。F5函數(shù)：FPA的最優(yōu)值精度達(dá)到10-6，平均值精度達(dá)到10-3；而NS-FPA的最優(yōu)值精度達(dá)到10-9，平均值精度達(dá)到10-7，標(biāo)準(zhǔn)差比FPA高4個(gè)數(shù)量級。F6函數(shù)：FPA的最優(yōu)值能夠達(dá)到精確解，平均值精度達(dá)到10-3；而NS-FPA的最優(yōu)值及平均值都達(dá)到精確解，標(biāo)準(zhǔn)差比FPA高2個(gè)數(shù)量級。F7函數(shù)：FPA的最優(yōu)值能夠達(dá)到精確解，平均值精度達(dá)到10-3；而NS-FPA的最優(yōu)值及平均值都達(dá)到精確解，標(biāo)準(zhǔn)差比FPA高3個(gè)數(shù)量級。F8函數(shù)：FPA的最優(yōu)值能夠達(dá)到精確解，平均值精度達(dá)到10-3；而NS-FPA的最優(yōu)值及平均值都達(dá)到精確解，標(biāo)準(zhǔn)差比FPA高6個(gè)數(shù)量級。

在超多模函數(shù)F9～F16的尋優(yōu)對比結(jié)果中，F(xiàn)9函數(shù)：FPA的最優(yōu)值精度達(dá)到10-2，平均值精度達(dá)到10-1；而NS-FPA的最優(yōu)值達(dá)到精確解，平均值精度達(dá)到10-4，標(biāo)準(zhǔn)差比FPA高2個(gè)數(shù)量級。F10函數(shù)：FPA的最優(yōu)值精度達(dá)到10-5，平均值精度達(dá)到10-2；而NS-FPA的最優(yōu)值精度達(dá)到10-10，平均值精度達(dá)到10-9，標(biāo)準(zhǔn)差比FPA高7個(gè)數(shù)量級。F11函數(shù)：FPA的最優(yōu)值精度達(dá)到10-2，平均值精度較差；而NS-FPA的最優(yōu)值達(dá)到精確解，平均值精度達(dá)到10-3，標(biāo)準(zhǔn)差比FPA高2個(gè)數(shù)量級。F12函數(shù)：FPA的最優(yōu)值精度達(dá)到10-3，平均值精度為10-1；而NS-FPA的最優(yōu)值達(dá)到精確解，平均值精度達(dá)到10-4，標(biāo)準(zhǔn)差比FPA高2個(gè)數(shù)量級。對于高維超多模函數(shù)F13～F16，F(xiàn)PA基本失去了尋優(yōu)精度，而NS-FPA依舊能夠?qū)?yōu)且平均尋優(yōu)精度均達(dá)到10-3以上，標(biāo)準(zhǔn)差也達(dá)到10-4以上,這驗(yàn)證了改進(jìn)方案的有效性。

從整體上看，NS-FPA的尋優(yōu)精度要比FPA至少高出2個(gè)數(shù)量級，尋優(yōu)穩(wěn)定性(標(biāo)準(zhǔn)差)高出2～7個(gè)數(shù)量級，這說明相對于FPA，NS-FPA能夠更好的處理多峰尋優(yōu)，且具有較高的穩(wěn)定性。

其次，與Yang等[20-21]近幾年提出的布谷鳥算法、螢火蟲算法進(jìn)行對比。表3中，對于多模函數(shù)F2～F8的尋優(yōu)，可以看出FPA與CS的最優(yōu)值、平均值、標(biāo)準(zhǔn)差幾乎相當(dāng)。除F2函數(shù)外，F(xiàn)A的最優(yōu)值、平均值、標(biāo)準(zhǔn)差要略微優(yōu)于FPA與CS,但NS-FPA的評價(jià)指標(biāo)都要優(yōu)于FPA、CS、FA，至少高2個(gè)數(shù)量級的計(jì)算精度。對于超多模函數(shù)F9～F16，F(xiàn)PA與CS的尋優(yōu)效果相當(dāng)；F8～F9，F(xiàn)A的尋優(yōu)效果要劣于CS與FPA；F10～F16，F(xiàn)A的尋優(yōu)效果要優(yōu)于CS與FPA；但NS-FPA的尋優(yōu)效果都要明顯優(yōu)于FPA、CS、FA。綜合來看，NS-FPA對多模尋優(yōu)的處理要更優(yōu)于FPA、CS、FA。

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

圖16 F11函數(shù)50次尋優(yōu)結(jié)果對比Fig.16 Comparison of 50 times’ optimization results of F11 function

圖17 F11函數(shù)尋優(yōu)進(jìn)化曲線 Fig.17 Optimization evolution curves of F11 function

圖18 F13函數(shù)尋優(yōu)進(jìn)化曲線Fig.18 Optimization evolution curves of F13 function

3.3 NS-FPA的參數(shù)分析

盡管NS-FPA的尋優(yōu)效果較好，與FPA相比，NS-FPA多了2個(gè)基本參數(shù)初溫概率p0、溫度衰減系數(shù)γ。為了討論其對NS-FPA尋優(yōu)性能的影響，本節(jié)以超多模函數(shù)F9為例，進(jìn)行仿真計(jì)算實(shí)驗(yàn)。

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

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

表4 不同p0、γ參數(shù)下的NS-FPA尋優(yōu)結(jié)果

3.4 NS-FPA的時(shí)間復(fù)雜度分析

與FPA相比，NS-FPA的局部授粉較為復(fù)雜，在算法復(fù)雜度上要大于FPA。為直觀地對比2種算法的時(shí)間復(fù)雜度，本節(jié)從3.2節(jié)選擇6個(gè)測試函數(shù)分別用FPA、NS-FPA在同一平臺上單獨(dú)進(jìn)行50次尋優(yōu)實(shí)驗(yàn)，統(tǒng)計(jì)50次實(shí)驗(yàn)的平均耗時(shí)，結(jié)果如表5所示。

表5中，NS-FPA的平均耗時(shí)要大于FPA，且平均高出32.49%。再考慮到3.2節(jié)中，對于FPA不能求解的多模函數(shù)，NS-FPA卻具有較好的尋優(yōu)性能，筆者認(rèn)為在時(shí)間上多出32.49%的消耗是值得的，它增強(qiáng)了算法的求解性能。

表5 NS-FPA與FPA的平均消耗時(shí)間對比

4 結(jié) 論

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

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

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

3) NS-FPA可以用來解決多模復(fù)雜優(yōu)化問題。

4) NS-FPA在尋優(yōu)時(shí)需要比FPA多消耗32.49%的時(shí)間。

參考文獻(xiàn) (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] 傅文淵，凌朝東.布朗運(yùn)動(dòng)模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào)，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.