陳 強(qiáng),解成能,刑繼剛,趙 航
(長(zhǎng)春工業(yè)大學(xué)機(jī)械工程系,長(zhǎng)春 130012)
傳統(tǒng)的優(yōu)化求解方法有共軛梯度法[1]、動(dòng)態(tài)規(guī)劃法[2]、牛頓法、Powell方法等數(shù)值計(jì)算方法。近年來(lái),一些新興元啟發(fā)式算法不斷涌現(xiàn),如通過(guò)螞蟻找尋食物的行為受到啟發(fā)提出的蟻群算法(ACO)[3];由螢火蟲(chóng)特殊求偶方式受到啟發(fā)得到的螢火蟲(chóng)算法(FA,GSO)[4];通過(guò)大自然降雨過(guò)程模擬的水循環(huán)算法(WCA)等。英國(guó)的Yang[5]在2012 年根據(jù)花朵授粉過(guò)程提出花朵授粉優(yōu)化算法(Flower Pollination Algorithm,F(xiàn)PA),并成功應(yīng)用到函數(shù)問(wèn)題優(yōu)化中。通過(guò)不斷地應(yīng)用,該算法表現(xiàn)出顯著的尋優(yōu)性能。由于花朵授粉算法具有一系列優(yōu)點(diǎn),使得該算法在被提出之后引起了很多關(guān)注,成為了目前智能優(yōu)化領(lǐng)域的熱點(diǎn)研究算法之一。2015 年,Zhou Yongquan等[6]提出了一種基于精英對(duì)立的花朵授粉算法(EOFPA),提高了開(kāi)發(fā)和探索能力。2016 年,Zhang Mingxin[7]提出了一種基于混沌理論(IFPCH)的花朵授粉算法求解定積分的新方法。2017 年,Dao Thi-Kien 等[8]提出了一種新的緊湊型花朵授粉算法,用于求解受限硬件條件下的一類優(yōu)化問(wèn)題。2018年,Zhang Xinming等[9]將小生境策略與花朵授粉算法相結(jié)合,提出了一種新的小生境花朵授粉算法。2019年,Chen Yang等[10]采用混沌映射方法對(duì)算法探索階段的方程進(jìn)行了改進(jìn),提出了一種改進(jìn)的全局花朵授粉算法(GFPA),用于混沌和超混沌系統(tǒng)的參數(shù)辨識(shí)。花朵授粉算法雖然具有魯棒性強(qiáng)、參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、穩(wěn)定性和執(zhí)行效率高等諸多優(yōu)點(diǎn),但也存在一定的缺點(diǎn),例如該算法中涉及參數(shù)少、缺少一定的理論基礎(chǔ)、執(zhí)行到后期時(shí)算法收斂速度明顯變慢、在執(zhí)行過(guò)程中容易陷入局部最優(yōu)無(wú)法自動(dòng)跳出、整體收斂性的相關(guān)理論證明不夠充分等。所以,花朵授粉算法在充實(shí)完善相關(guān)理論和拓展應(yīng)用范圍等方面還有待研究。本文提出將線性權(quán)重和優(yōu)質(zhì)解隨機(jī)游走策略融入到花朵授粉算法中,以提高花朵授粉算法的性能。
自然界開(kāi)花植物的授粉過(guò)程大概分為自花授粉和異花授粉兩大類。自花授粉是指基于風(fēng)媒、水媒授粉的植物;異花授粉是指基于蟲(chóng)媒、鳥(niǎo)媒授粉的植物。同一植物個(gè)體上的不同花朵之間的授粉是自花授粉;同一植物的不同個(gè)體花朵之間的授粉是異花授粉。因?yàn)樽曰ㄊ诜墼谕恢参飩€(gè)體的不同花朵之間傳粉,花粉的移動(dòng)范圍較小,抽象到花朵授粉算法中,就是搜索范圍較小的局部搜索;異花授粉需要蟲(chóng)媒或者鳥(niǎo)媒來(lái)攜帶花粉進(jìn)行授粉,而這些蟲(chóng)類或者傳粉者通常采用Levy飛行機(jī)制移動(dòng)[5],Levy飛行是一種特殊的隨機(jī)游走,因?yàn)槠淠軌蜻M(jìn)行較大步長(zhǎng)的移動(dòng),所以異花授粉抽象到花朵授粉算法中,即為搜索較大的全局搜索。
在現(xiàn)實(shí)中,大部分植物都開(kāi)許多花,每朵花包含上萬(wàn)個(gè)花粉。為了簡(jiǎn)化研究,假設(shè)每株植物只有一朵花,每朵花只產(chǎn)生一個(gè)花粉,每個(gè)花粉對(duì)應(yīng)優(yōu)化問(wèn)題的一個(gè)解。根據(jù)以上原理,將花朵授粉過(guò)程抽象為以下模型:
(1)把生物授粉和異花授粉看作全局授粉過(guò)程,并且傳粉者的移動(dòng)路徑遵循Levy飛行;
(2)自花授粉視為局部授粉;
(3)花粉的恒常性被看作花朵的繁衍概率,這個(gè)概率體現(xiàn)了花朵之間的相似性;
(4)算法的局部尋優(yōu)和全局尋優(yōu)之間的轉(zhuǎn)換由轉(zhuǎn)換概率p控制。
(1)自花授粉過(guò)程
自花授粉是指來(lái)自同一開(kāi)花植物的花粉通過(guò)風(fēng)進(jìn)行傳播花粉的過(guò)程,這個(gè)過(guò)程看作是局部搜索過(guò)程。當(dāng)進(jìn)行局部搜索時(shí),花粉的位置公式(1)更新:
(2)異花授粉過(guò)程
異花授粉過(guò)程中,傳粉者遵從Levy飛行規(guī)律,飛行相對(duì)較遠(yuǎn)的路程進(jìn)行授粉?;ǚ鄣奈恢霉剑?)更新:
昆蟲(chóng)在攜帶花粉時(shí)可以用不同的運(yùn)動(dòng)方式移動(dòng)一大段距離,其移動(dòng)的步長(zhǎng)符合Levy 分布。L(λ)>0,其表達(dá)式如下:
式中:Γ(λ)為標(biāo)準(zhǔn)的伽馬函數(shù)。
本文提出應(yīng)用線性權(quán)重來(lái)逐步提高算法的局部搜索能力,即:
式中:wmax為最大權(quán)重;wmin為最小權(quán)重;itermax為最大迭代次數(shù);iter為當(dāng)前迭代次數(shù)。
異花授粉過(guò)程中,花粉的位置公式更改為:
本文提出一種優(yōu)質(zhì)解隨機(jī)游走策略,進(jìn)一步提高算法的搜索能力。
式中:xbest、xsbest、xtbest分別為當(dāng)前迭代排在前三位的最優(yōu)解;c1、c2、c3為隨機(jī)游走參數(shù)。
Step 1:設(shè)置種群規(guī)模N,維數(shù)d,最大迭代次數(shù)itermax,轉(zhuǎn)換概率p。
Step 2:計(jì)算適應(yīng)度值xi,并得到g*。
Step 3:若rand <p,則按照式(3)、式(5)更新。
Step 4:若rand ≥p,則按照式(1)更新。
Step 5:執(zhí)行優(yōu)質(zhì)解隨機(jī)游走策略。
Step 6:判斷是否滿足需要,滿足則結(jié)束;不滿足則返回步驟3。
改進(jìn)的花朵授粉算法的偽代碼如下所示。
輸入:種群規(guī)模N,維數(shù)d,最大迭代次數(shù)itermax,轉(zhuǎn)換概率p等參數(shù)。
輸出:最優(yōu)解。
算法描述:
(1)產(chǎn)生初始種群
(2)計(jì)算適應(yīng)度值xi,并得到g*
(3)while (t < itermax)
(4)計(jì)算權(quán)重
(5)fori=1∶N
(6)if 若rand < p,則按照式(3)、式(5)更新
(7)else 依據(jù)式(1)局部搜索
(8)end if
end for
(9)if f(xnew)< f(g*),則替換當(dāng)前最優(yōu)位置g*為xnew否則放棄
(10)執(zhí)行優(yōu)質(zhì)解隨機(jī)游走策略
end while
為驗(yàn)證改進(jìn)花朵授粉算法的性能,選擇5 個(gè)測(cè)試函數(shù)進(jìn)行對(duì)比試驗(yàn)[11],并與遺傳算法[12]、引力粒子群算法[13]和基本的花朵授粉算法[5]進(jìn)行比較。具體測(cè)試函數(shù)如下。
(1)Sphere函數(shù)
該函數(shù)在(0,…,0)處取得最小值0。
(2)Schwefel2.22函數(shù)
該函數(shù)在(0,…,0)處取得最小值0。
(3)Schwefel1.2函數(shù)
該函數(shù)在(0,…,0)處取得最小值0。
(4)Schwefel2.21函數(shù)
該函數(shù)在(0,…,0)處取得最小值0。
(5)Rosenbrock函數(shù)
該函數(shù)在(1,…,1)處取得最小值0。
以上優(yōu)化函數(shù),維度為30,每個(gè)算法獨(dú)立運(yùn)行30次。算法參數(shù):種群規(guī)模n =20;轉(zhuǎn)移概率p =0.8;最大迭代次數(shù)itermax=300。5個(gè)函數(shù)的結(jié)果對(duì)比分別如表1~5所示。
表1 在Sphere函數(shù)上優(yōu)化結(jié)果對(duì)比
表2 在Schwefel2.22 函數(shù)上優(yōu)化結(jié)果對(duì)比
表3 在Schwefel1.2 函數(shù)上優(yōu)化結(jié)果對(duì)比
表4 在Schwefel2.21 函數(shù)上優(yōu)化結(jié)果對(duì)比
表5 在Rosenbrock函數(shù)上優(yōu)化結(jié)果對(duì)比
算法收斂的速度是算法性能的重要指標(biāo)。不同函數(shù)的收斂曲線圖分別如圖1~5所示。
圖1 Sphere函數(shù)收斂曲線
圖2 Schwefel2.22 函數(shù)收斂曲線
圖3 Schwefel1.2 函數(shù)收斂曲
圖4 Schwefel2.21 函數(shù)收斂曲線
圖5 Rosenbrock函數(shù)收斂曲線
由表1~5和圖1~5可以看出,本文提出的改進(jìn)FPA算法比基本FPA算法在全局尋優(yōu)方面具有更快的收斂速度和更高的精度,可以提高算法找到全局最優(yōu)解的概率。
本文采用線性權(quán)重和優(yōu)質(zhì)解隨機(jī)游走策略,改進(jìn)花朵授粉算法。將該改進(jìn)型花朵授粉算法用于Sphere 函數(shù)、Schwefel2.22 函數(shù)、Schwefel1.2 函數(shù)、Schwefel2.21 函數(shù)、Rosenbrock函數(shù)。仿真實(shí)驗(yàn)結(jié)果表明,所提出的算法在收斂精度和收斂速度方面有明顯優(yōu)勢(shì)。