一種改進(jìn)的花朵授粉優(yōu)化算法*

陳 強(qiáng)，解成能，刑繼剛，趙 航

（長春工業(yè)大學(xué)機(jī)械工程系，長春 130012）

0 引言

傳統(tǒng)的優(yōu)化求解方法有共軛梯度法［1］、動態(tài)規(guī)劃法［2］、牛頓法、Powell方法等數(shù)值計算方法。近年來，一些新興元啟發(fā)式算法不斷涌現(xiàn)，如通過螞蟻找尋食物的行為受到啟發(fā)提出的蟻群算法（ACO）［3］；由螢火蟲特殊求偶方式受到啟發(fā)得到的螢火蟲算法（FA，GSO）［4］；通過大自然降雨過程模擬的水循環(huán)算法（WCA）等。英國的Yang［5］在2012 年根據(jù)花朵授粉過程提出花朵授粉優(yōu)化算法（Flower Pollination Algorithm，F(xiàn)PA），并成功應(yīng)用到函數(shù)問題優(yōu)化中。通過不斷地應(yīng)用，該算法表現(xiàn)出顯著的尋優(yōu)性能。由于花朵授粉算法具有一系列優(yōu)點(diǎn)，使得該算法在被提出之后引起了很多關(guān)注，成為了目前智能優(yōu)化領(lǐng)域的熱點(diǎn)研究算法之一。2015 年，Zhou Yongquan等［6］提出了一種基于精英對立的花朵授粉算法（EOFPA），提高了開發(fā)和探索能力。2016 年，Zhang Mingxin［7］提出了一種基于混沌理論（IFPCH）的花朵授粉算法求解定積分的新方法。2017 年，Dao Thi-Kien 等［8］提出了一種新的緊湊型花朵授粉算法，用于求解受限硬件條件下的一類優(yōu)化問題。2018年，Zhang Xinming等［9］將小生境策略與花朵授粉算法相結(jié)合，提出了一種新的小生境花朵授粉算法。2019年，Chen Yang等［10］采用混沌映射方法對算法探索階段的方程進(jìn)行了改進(jìn)，提出了一種改進(jìn)的全局花朵授粉算法（GFPA），用于混沌和超混沌系統(tǒng)的參數(shù)辨識。花朵授粉算法雖然具有魯棒性強(qiáng)、參數(shù)少、結(jié)構(gòu)簡單、穩(wěn)定性和執(zhí)行效率高等諸多優(yōu)點(diǎn)，但也存在一定的缺點(diǎn)，例如該算法中涉及參數(shù)少、缺少一定的理論基礎(chǔ)、執(zhí)行到后期時算法收斂速度明顯變慢、在執(zhí)行過程中容易陷入局部最優(yōu)無法自動跳出、整體收斂性的相關(guān)理論證明不夠充分等。所以，花朵授粉算法在充實(shí)完善相關(guān)理論和拓展應(yīng)用范圍等方面還有待研究。本文提出將線性權(quán)重和優(yōu)質(zhì)解隨機(jī)游走策略融入到花朵授粉算法中，以提高花朵授粉算法的性能。

1 花朵授粉算法

1.1 基本概念

自然界開花植物的授粉過程大概分為自花授粉和異花授粉兩大類。自花授粉是指基于風(fēng)媒、水媒授粉的植物；異花授粉是指基于蟲媒、鳥媒授粉的植物。同一植物個體上的不同花朵之間的授粉是自花授粉；同一植物的不同個體花朵之間的授粉是異花授粉。因?yàn)樽曰ㄊ诜墼谕恢参飩€體的不同花朵之間傳粉，花粉的移動范圍較小，抽象到花朵授粉算法中，就是搜索范圍較小的局部搜索；異花授粉需要蟲媒或者鳥媒來攜帶花粉進(jìn)行授粉，而這些蟲類或者傳粉者通常采用Levy飛行機(jī)制移動［5］，Levy飛行是一種特殊的隨機(jī)游走，因?yàn)槠淠軌蜻M(jìn)行較大步長的移動，所以異花授粉抽象到花朵授粉算法中，即為搜索較大的全局搜索。

在現(xiàn)實(shí)中，大部分植物都開許多花，每朵花包含上萬個花粉。為了簡化研究，假設(shè)每株植物只有一朵花，每朵花只產(chǎn)生一個花粉，每個花粉對應(yīng)優(yōu)化問題的一個解。根據(jù)以上原理，將花朵授粉過程抽象為以下模型：

（1）把生物授粉和異花授粉看作全局授粉過程，并且傳粉者的移動路徑遵循Levy飛行；

（2）自花授粉視為局部授粉；

（3）花粉的恒常性被看作花朵的繁衍概率，這個概率體現(xiàn)了花朵之間的相似性；

（4）算法的局部尋優(yōu)和全局尋優(yōu)之間的轉(zhuǎn)換由轉(zhuǎn)換概率p控制。

1.2 原理

（1）自花授粉過程

自花授粉是指來自同一開花植物的花粉通過風(fēng)進(jìn)行傳播花粉的過程，這個過程看作是局部搜索過程。當(dāng)進(jìn)行局部搜索時，花粉的位置公式（1）更新：

（2）異花授粉過程

異花授粉過程中，傳粉者遵從Levy飛行規(guī)律，飛行相對較遠(yuǎn)的路程進(jìn)行授粉。花粉的位置公式（2）更新：

昆蟲在攜帶花粉時可以用不同的運(yùn)動方式移動一大段距離，其移動的步長符合Levy 分布。L（λ）＞0，其表達(dá)式如下：

式中：Γ（λ）為標(biāo)準(zhǔn)的伽馬函數(shù)。

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

2.1 線性權(quán)重

本文提出應(yīng)用線性權(quán)重來逐步提高算法的局部搜索能力，即：

式中：wmax為最大權(quán)重；wmin為最小權(quán)重；itermax為最大迭代次數(shù)；iter為當(dāng)前迭代次數(shù)。

異花授粉過程中，花粉的位置公式更改為：

2.2 優(yōu)質(zhì)解隨機(jī)游走策略

本文提出一種優(yōu)質(zhì)解隨機(jī)游走策略，進(jìn)一步提高算法的搜索能力。

式中：xbest、xsbest、xtbest分別為當(dāng)前迭代排在前三位的最優(yōu)解；c1、c2、c3為隨機(jī)游走參數(shù)。

2.3 改進(jìn)的花朵授粉算法流程

Step 1：設(shè)置種群規(guī)模N，維數(shù)d，最大迭代次數(shù)itermax，轉(zhuǎn)換概率p。

Step 2：計算適應(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）計算適應(yīng)度值xi，并得到g*

（3）while （t ＜ itermax）

（4）計算權(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

3 實(shí)驗(yàn)數(shù)據(jù)及分析

為驗(yàn)證改進(jìn)花朵授粉算法的性能，選擇5 個測試函數(shù)進(jìn)行對比試驗(yàn)［11］，并與遺傳算法［12］、引力粒子群算法［13］和基本的花朵授粉算法［5］進(jìn)行比較。具體測試函數(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，每個算法獨(dú)立運(yùn)行30次。算法參數(shù)：種群規(guī)模n ＝20；轉(zhuǎn)移概率p ＝0.8；最大迭代次數(shù)itermax＝300。5個函數(shù)的結(jié)果對比分別如表1～5所示。

表1 在Sphere函數(shù)上優(yōu)化結(jié)果對比

表2 在Schwefel2.22 函數(shù)上優(yōu)化結(jié)果對比

表3 在Schwefel1.2 函數(shù)上優(yōu)化結(jié)果對比

表4 在Schwefel2.21 函數(shù)上優(yōu)化結(jié)果對比

表5 在Rosenbrock函數(shù)上優(yōu)化結(jié)果對比

算法收斂的速度是算法性能的重要指標(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)解的概率。

4 結(jié)束語

本文采用線性權(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)勢。