混合改進(jìn)的花朵授粉算法*

陶志勇, 崔新新

(遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院,遼寧 葫蘆島 125100)

0 引 言

花朵授粉優(yōu)化算法[1](flower pollination algorithm,FPA)是由Yang X S等人在2012年提出的一種模擬自然界中花粉授粉過程的群優(yōu)化算法,由于該算法不需要知道待優(yōu)化函數(shù)的具體形式、易實(shí)現(xiàn)、參數(shù)少、易調(diào)節(jié)等特點(diǎn),引起了很多學(xué)者的研究興趣,并廣泛應(yīng)用于自然科學(xué)研究領(lǐng)域。然而該算法和粒子群算法[2]、蟻群算法[3]、遺傳算法[4]等類似,都存在早熟收斂,容易陷入局部最優(yōu),收斂精度低,迭代次數(shù)多等問題。文獻(xiàn)[5]提出一種基于引力搜索機(jī)制的花朵授粉算法,采用花朵個體間的萬有引力和算法本身的萊維飛行共同實(shí)現(xiàn)個體位置的更新,使花朵受萊維飛行和萬有引力的雙重影響；文獻(xiàn)[6]通過定義種群多樣性及差異性指標(biāo),定性分析了花朵授粉算法在多模函數(shù)優(yōu)化中的尋優(yōu)缺點(diǎn),利用Nelder-Mead單純形搜索技術(shù)對花朵局部授粉進(jìn)行重構(gòu),提出一種新的花朵授粉尋優(yōu)架構(gòu)；Wang R等人[7]提出了一種逐維度計算的FPA算法,通過逐維度更新算子,保留各算子各維度的最優(yōu)信息；王玉鑫等人[8]將差分進(jìn)化和變異策略與花朵授粉算法結(jié)合,提高種群多樣性,從而提高算法的尋優(yōu)能力。肖輝輝等人[9]將模擬退火算法與花朵授粉算法相結(jié)合,提高了算法的全局尋優(yōu)和跳出局部最優(yōu)的能力。

以上文獻(xiàn)在一定程度上提高了FPA算法的尋優(yōu)能力,但大多是通過與其他智能算法進(jìn)行混合的方式以提升FPA算法的性能[10～13],但這樣增加了算法的復(fù)雜性,破壞了FPA算法簡單易實(shí)現(xiàn)的特點(diǎn)。

本文在不增加算法復(fù)雜度的前提下,針對FPA算法速度和精度不足的問題,將均勻初始化、正態(tài)分布縮放因子、擾動進(jìn)化和邊界變異引入花朵授粉算法中,提出利用共軛梯度法改進(jìn)的花朵授粉算法,并通過7種標(biāo)準(zhǔn)測試函數(shù)仿真實(shí)驗(yàn)測試HFPA算法的性能 。

1 花朵授粉算法

花朵授粉算法是一種模擬自然界開花植物授粉過程的群智能優(yōu)化算法。自然界的授粉過程非常復(fù)雜,很難通過算法完全真實(shí)地模擬花粉授粉的各個細(xì)節(jié),且實(shí)用價值不高。為了使該算法更為高效,FPA對花朵授粉過程進(jìn)行簡化。在FPA中,假設(shè)每朵花為優(yōu)化問題的一個解,并且每朵花都是通過轉(zhuǎn)換概率p進(jìn)行異花授粉操作,或以概率 1-p進(jìn)行自花授粉操作繁衍后代。異花授粉通過一些昆蟲或鳥類進(jìn)行,此類授粉的范圍較大,在優(yōu)化理論中可以視為全局搜索；自花授粉主要是在自然作用下兩朵花之間進(jìn)行小范圍授粉,此類授粉的范圍較小,在優(yōu)化理論中可以視為局部搜索。

2 混合改進(jìn)的花朵授粉算法

2.1 均勻種群初始化

為了使初始種群相對均勻的分布在搜索空間中,同時保持種群的多樣性,采用隨機(jī)均勻種群初始化,如式(1)所示

Xi=bL+(i-1)(bU-bL)/n+rand(1,d)

(1)

式中Xi為種群的第i個個體,bL為優(yōu)化問題的下界,bU為優(yōu)化問題的上界,n為種群規(guī)模,rand(1,d)為d維的隨機(jī)數(shù)。

2.2 正態(tài)分布縮放因子

原始FPA算法采用Levy飛行進(jìn)行全局搜索,Levy飛行屬于隨機(jī)游走的一種,其特征是小步長的移動很多,但有小概率進(jìn)行較大步長的移動。理論上Levy飛行能夠幫助算法脫離局部最優(yōu),但由于轉(zhuǎn)換概率p的限制,花朵授粉算法進(jìn)行的全局搜索較少,這就大概率導(dǎo)致Levy飛行是以較小步長進(jìn)行局部運(yùn)動,反而使算法不易脫離局部最優(yōu)。

本文算法采用式(2)進(jìn)行全局搜索

(2)

2.3 變異策略

花朵授粉算法的局部搜索策略為

(3)

在差分進(jìn)化算法中,常用的變異策略有兩種：

DE/rand/1：

(4)

DE/best/1：

(5)

Zheng W等人[14]對差分進(jìn)化算法進(jìn)行研究后,提出了一種新的變異策略

(6)

式(6)中,以全局最優(yōu)解作為基向量,算子本身參與變異,能夠更好地平衡變異的隨機(jī)性和方向性,既能加快收斂速度,又能減慢算法陷入局部最優(yōu)的速度。

僅采用單一的差分進(jìn)化仍有可能導(dǎo)致算法陷入局部最優(yōu)。為了增強(qiáng)算法跳出局部最優(yōu)的能力,HFPA算法在使用新的變異策略的基礎(chǔ)上,算子有較小概率發(fā)生變異,使算法跳出局部最優(yōu)

(7)

最終的局部尋優(yōu)表達(dá)式為

ifrand>pl

else

(8)

2.4 邊界變異

在原FPA算法中,對越界算子的處理是將越界的維度的值改為所超越的邊界

(9)

為了解決粒子群算法易在邊界上陷入局部最優(yōu)的缺陷,引入了邊界變異思想,使得種群多樣性得到提升,從而提高了算法的搜索能力。

本文將邊界變異思想引入到花朵授粉算法中,對算法中的越界個體依照式(10)進(jìn)行邊界變異：

(10)

式中xi(t,r)為第t次迭代中,第i個算子的第r維。越界個體變異后,可以使個體不在聚集在邊界處,提高算法的全局搜索能力。

2.5 算法流程

a.初始化算法的參數(shù),迭代次數(shù)N(或迭代停止精度),種群數(shù)量n,轉(zhuǎn)換概率p,變異概率pl；b.均勻初始化種群,并計算各個個體的適應(yīng)度值；c.若p>rand,按照式(2)對更新解,進(jìn)行全局尋優(yōu)；d.若p

3 仿真實(shí)驗(yàn)與結(jié)果分析

本文選擇具有代表性的4個函數(shù)來驗(yàn)證HFPA算法的有效性和優(yōu)越性,包括單峰、多峰函數(shù),并將測試結(jié)果與FPA算法,粒子群算法(PSO)等算法那進(jìn)行比較。測試函數(shù)選取CEC2013 benchmark[15]測試函數(shù)的一部分：

其中,f1,f2,f3為單峰函數(shù),f4～f7為多峰函數(shù),一般用來驗(yàn)證算法逃離局部極值的能力。

3.1 低維下的性能分析

此實(shí)驗(yàn)各算法種群數(shù)均為20,迭代次數(shù)為1500,維度為30。每種算法對每個測試函數(shù)運(yùn)行100次,對比各算法的最優(yōu)值、平均值就、最差值及尋優(yōu)成功率。若算法所得最優(yōu)值與理論最優(yōu)值相差小于0.001,則認(rèn)為尋優(yōu)成功。實(shí)驗(yàn)結(jié)果如表1所示。其中FPA算法的參數(shù)為：p=0.8,n=20;HFPA算法的參數(shù)為：p=0.8,n=20,pl=0.1;MFPA的參數(shù)為p=0.8,n=20,w=0.618;PSO算法參數(shù)為：c1=1.496 2,c2=1.496 2,w=0.729 8。實(shí)驗(yàn)結(jié)果如表1所示。

從表1可以看出,HFPA算法對各個函數(shù)求解的最優(yōu)值都遠(yuǎn)小于FPA和PSO算法。較同為FPA改進(jìn)算法的MFPA算法相比,HFPA解的精度有1～16個數(shù)量級的提升,同時解得最優(yōu)解的成功率和穩(wěn)定性有很大提高,對7種測試函數(shù)的求解均達(dá)到了100 %的尋優(yōu)成功率。圖1是其中四種算法在測試函數(shù)F1～F4的收斂曲線,其中橫坐標(biāo)代表迭代次數(shù),縱坐標(biāo)表示測試函數(shù)的適應(yīng)度值。

表1 HFPA在低維的性能分析

圖1 測試函數(shù)收斂曲線

從圖1可以看出,HFPA 算法不易陷入局部最優(yōu),且能在算法迭代初期快速收斂,有效提高了迭代速度和精度。

3.2 高維下的性能分析

實(shí)驗(yàn)中各算法種群數(shù)均為20,迭代次數(shù)為1500,維度為100。每種算法對每個測試函數(shù)運(yùn)行100次,對比各算法的實(shí)際最優(yōu)值、平均值就、最差值,如果理論最優(yōu)值與實(shí)際獲得的最優(yōu)值誤差小于0.001,認(rèn)為尋優(yōu)成功。實(shí)驗(yàn)結(jié)果如表2所示。

從表2可以得知,HFPA,在300維測試函數(shù)下,除F7函數(shù)外,都能達(dá)到都能夠達(dá)到70 %以上的收斂率,而FPA算法大部分情況下無法收斂。HFPA 與 FPA、PSO、MFPA 相比,對于函數(shù) ,HFPA 的最優(yōu)值、平均值、最差值和尋優(yōu)成功率均好于其他 3 種算法。這說明從尋優(yōu)精度、收斂速度和魯棒性上,HFPA相較原算法有較大幅度的提高。

3.3 固定精度下的性能分析

實(shí)驗(yàn)中各算法種群數(shù)均為20,最大迭代次數(shù)為3000,維度為30。每種算法對每個測試函數(shù)運(yùn)行100次,對比各算法達(dá)到10-3精度所需的最少迭代次數(shù),平均迭代次數(shù)和最大迭代次數(shù)。

表2 HFPA在高維的性能分析

表3 HFPA在固定精度下的性能分析

從表3可以看出,對于4個測試函數(shù),HFPA算法均能在1000次迭代內(nèi)達(dá)到目標(biāo)精度,且無論是最小收斂代數(shù)還是平均收斂代數(shù)均優(yōu)于原算法,與其他花朵授粉改進(jìn)算法相比,迭代次數(shù)明顯降低。說明HFPA有效提高了FPA算法的收斂速度。

3.4 運(yùn)行速度分析

針對4種測試函數(shù),維度30,算法種群數(shù)均為20,迭代次數(shù)1500次。每個算法運(yùn)行10次,比較FPA算法和HFPA算法的最小運(yùn)行時間和平均運(yùn)行時間。實(shí)驗(yàn)結(jié)果如表4所示。

表4 HFPA運(yùn)行速度分析 s

從表4可以看出,HFPA的在相同迭代次數(shù)下的運(yùn)行時間在各測試函數(shù)下相比FPA算法均有降低。說明HFPA的時間復(fù)雜度低于原FPA算法,結(jié)合HFPA達(dá)到目標(biāo)精度所需迭代次數(shù)較少的特點(diǎn),使得算法收斂到目標(biāo)精度所需的時間相比FPA算法大大縮短。

4 結(jié) 論

仿真實(shí)驗(yàn)結(jié)果表明：HFPA算法在收斂速度和精度,運(yùn)行速度相比原FPA算法有較大提升。HFPA算法在低維下尋優(yōu)精度較原FPA算法有5～20個數(shù)量級的提升,高維下有3～9個數(shù)量級的提升,達(dá)到相同精度所需的迭代次數(shù)大大減少,單次運(yùn)行時間的比FPA算法有0.4～0.5s的降低,證明本文算法具有一定的可行性。今后準(zhǔn)備將花朵授粉算法與其他領(lǐng)域結(jié)合,將算法應(yīng)用于實(shí)際當(dāng)中。