基于t-分布精英保留機制的花朵授粉算法

張 超

(宿州職業(yè)技術(shù)學院計算機信息系，安徽 宿州 234101)

自然界中的很多生物種群涌現(xiàn)出不同形式的群體行為特征。學者們對這些智能涌現(xiàn)的群體行為模式進行研究，仿生設(shè)計了各種元啟發(fā)式群智能優(yōu)化算法，如粒子群算法、蝙蝠算法、遺傳算法、和聲算法、蟻群算法等。這些算法因其設(shè)計簡單、結(jié)構(gòu)靈活，已在自然科學和工程等領(lǐng)域被廣泛應(yīng)用[1]。花朵授粉算法[2-3](Flower Pollination Algorithm，F(xiàn)PA)是基于自然界中的花授粉過程，設(shè)計的一種智能優(yōu)化算法。算法結(jié)構(gòu)簡單，參數(shù)少，使用轉(zhuǎn)換概率參數(shù)P平衡全局搜索和局部搜索。目前花朵授粉算法已被成功應(yīng)用到交通流預(yù)測[4]、神經(jīng)網(wǎng)絡(luò)優(yōu)化[5-6]、大整數(shù)規(guī)劃[7]、產(chǎn)品拆卸序列規(guī)劃[8]等領(lǐng)域。

但花朵授粉算法也存在易陷入局部最優(yōu)，算法迭代后期收斂速度慢等不足[9]，特別，對于局部極值較多、較復(fù)雜的高維優(yōu)化問題，算法的收斂精度不高[10]。為此，國內(nèi)外學者對花朵授粉算法進行了優(yōu)化和改進研究工作。文獻[11]等利用logsig函數(shù)對解進行變換，映射到0-1空間中，提出了二進制花朵授粉算法。文獻[12-13]分別對花朵授粉算法的兩個控制參數(shù)：轉(zhuǎn)換概率p和全局搜索時的移動步長縮放因子γ做取值對比試驗，得出p=0.2，γ=16時花授粉算法對大多數(shù)測試函數(shù)的尋優(yōu)能力更好。文獻[14-15]認為初始解的質(zhì)量影響花朵授粉算法的尋優(yōu)能力，為此分別通過螢火蟲算法、粒子群算法、和聲算法獲得待優(yōu)化問題的最優(yōu)解，并將該最優(yōu)解作為花朵授粉算法的初始解，以期提高花朵授粉算法的尋優(yōu)精度和速度。文獻[16-17]中分別把雜草算法和差分進化算法的思想融入到花朵授粉算法中，通過擴展種群的多樣性提高算法的全局搜索能力。文獻[18-19]將量子行為引入到花朵授粉算法中，分別利用量子的隨機性搜索、態(tài)疊加特性增強花朵授粉算法的全局搜索能力。文獻[20]等使用精英混沌搜索對種群中部分花朵個體進行變異，提高了花朵授粉算法的尋優(yōu)速度。文獻[21]等將精英保留機制引入到花朵授粉算法中，使用外部存檔法對個體的適應(yīng)度進行排序，按一定比例選擇適應(yīng)度好的個體進入下一迭代，通過精英個體的引導(dǎo)，提高算法的收斂速度。文獻[22]將引力搜索機制添加到基本花朵授粉算法的全局搜索部分，使用萬有引力牽制Levy飛行的隨機游走，提高了算法的收斂精度。

以上改進策略取得了良好的效果，但花授粉算法的尋優(yōu)性能仍有待提高。鑒于此，本文提出一種基于t-分布算子的精英保留機制花朵授粉算法。改進算法在全局搜索時引入精英概率保留參數(shù)pe，通過pe將全局搜索時花朵個體位置更新分為兩種方式：一是基本算法自身的Levy飛行機制；二是將經(jīng)過t-分布變異的精英個體位置信息賦予花朵個體。該機制通過精英概率保留參數(shù)平衡種群的多樣性和集中性，提高算法的收斂精度。改進算法在進行局部搜索時，使用具有較好局部搜索能力的高斯變異，代替基本FPA算法的隨機數(shù)擾動因子，提升算法的局部開發(fā)能力。擬選用12個標準測試函數(shù)進行仿真實驗，12個函數(shù)包括高維單峰函數(shù)、高維多峰函數(shù)及低維局部極值較多函數(shù)，以驗證本文提出改進策略的有效性。

1 花朵授粉算法

花朵授粉算法(Flower Pollination Algorithm，F(xiàn)PA)假設(shè)一株花只開一朵花和繁衍一個花粉配子，并遵循以下四個理想原則：(1)異花授粉是蜜蜂、果蠅等傳播者遵循Levy飛行軌跡進行的全局搜索；(2)局部搜索過程通過模擬顯花植物自花授粉實現(xiàn)；(3)花的繁衍概率與兩朵花的相似性成比例關(guān)系；(4)轉(zhuǎn)換概率參數(shù)p∈[0，1]控制兩類授粉過程的轉(zhuǎn)換。整個授粉過程更傾向于自花授粉。

基于以上假設(shè)，花朵授粉算法基本步驟如下：

(1)初始化參數(shù)。對迭代次數(shù)、搜索變量的維度、轉(zhuǎn)換概率、種群規(guī)模、步長縮放因子等算法參數(shù)進行初始設(shè)置。

(2)花朵種群初始化。在搜素域內(nèi)生成n朵花，花朵個體位置記為xi，并記錄最佳花朵位置x*。

(3)算法迭代尋優(yōu)。生成一個隨機數(shù)γ，如果轉(zhuǎn)換概率p>γ，按公式(1)進入異花授粉的全局搜索過程。

(1)

式中：x*是當前迭代的最優(yōu)解，xit是第i個花朵在第t次迭代的解，γ為縮放因子，L為服從λ為指數(shù)的Levy分布的隨機數(shù)，L使用公式(2)計算。

(2)

式中：λ=3/2，Γ(λ)為標準伽瑪函數(shù)。

如果轉(zhuǎn)換概率p<γ，算法進入自花授粉的局部搜索過程，其計算公式如下：

(3)

式中：ε是[0，1]之間的隨機數(shù)，xjt、xkt是同類型植物不同花朵的花粉配子。

(4)適應(yīng)度值排序，記錄當前最優(yōu)花朵信息。

(5)重復(fù)步驟(3)至(4)，算法進入迭代尋優(yōu)搜索，直至滿足迭代結(jié)束條件為止。

2 改進花朵授粉算法

2.1 全局搜索改進策略

全局搜索是在當前最優(yōu)花朵個體引導(dǎo)下，使用能夠體現(xiàn)蜜蜂等昆蟲飛行軌跡的Levy飛行函數(shù)，對組成花朵位置的各維度進行變異生成新解。Levy飛行偶爾會以較大步長跳躍且方向多變的特點，一方面維持了種群的多樣性，使算法能夠跳出局部極值的束縛，但也可能因跳躍太大導(dǎo)致最優(yōu)花朵個體信息丟失，從而影響算法的收斂精度。精英個體是進化過程中性能表現(xiàn)較好的個體，對種群的進化起著關(guān)鍵的引導(dǎo)作用。維護種群的多樣性可以使算法在更大的可行空間內(nèi)搜索，提高全局探測能力，而充分利用精英個體的信息可以提高算法的全局收斂性。鑒于此種思想，為花朵授粉算法的全局搜索過程添加基于學生t-分布(簡稱t分布)的精英概率保留機制。

當花朵授粉算法的轉(zhuǎn)換概率p控制算法進入全局搜索時，設(shè)置一個精英概率保留參數(shù)pe∈[0，1]，并生成一個隨機數(shù)γ，如果pe>γ，使用公式(4)計算全局搜索生成新解方式，反之，仍按原算法公式(1)計算。這樣將花朵授粉算法的全局搜索，通過精英保留概率pe分為兩個部分進行：一是原算法通過Levy飛行進行的全局搜索，充分維護了種群的多樣性；二是通過保留最優(yōu)個體位置信息，并對最優(yōu)個體位置使用t-分布變異算子進行擾動計算，充分利用精英個體信息提高算法收斂精度。

xnew=xold-best+ω*t(Iteration)?xold-best

(4)

式中：xold-best為當前迭代的最優(yōu)解，Iteration是迭代次數(shù)計數(shù)參數(shù)，t(Iteration)是以Iteration為自由度的t-分布，?為點乘符號，ω為縮放因子，ω使用公式(5)計算。

ω=a+(b-a)*(T-t)/T

(5)

式中：a=0.1，b=1，ω的取值隨著迭代次數(shù)的增加逐漸減小，T為最大迭代次數(shù)。

公式(4)對最優(yōu)解進行t-分布變異，在最優(yōu)解附近生成新解，此種機制使精英個體信息得以保留到下一迭代中去，引導(dǎo)種群朝著最優(yōu)位置進化。為了防止算法在此過程中被局部極值吸引，導(dǎo)致算法早熟，迭代前期ω取較大值，在保留精英個體信息的同時，利用t-分布算子特性維護種群多樣性，防止算法被局部最優(yōu)值吸引；迭代后期ω取較小的值，可以使花朵精英個體的信息充分保留，從而提高算法的收斂精度。t-分布隨著自由度參數(shù)Iteration值的增長，數(shù)值分布狀態(tài)由柯西分布逐漸向高斯分布逼近，自由度為1時，t-分布與柯西分布曲線重合，當自由度大于30以后，t-分布曲線形態(tài)開始趨向于高斯分布曲線形態(tài)，直至趨于無窮大時，t-分布和高斯分布曲線無限重合。在智能優(yōu)化算法中引入高斯分布變異，已被證明能夠獲得良好的局部搜索能力，而引入柯西分布變異，能夠擴大搜索空間，維持種群的多樣性，增加算法跳出局部極值的能力。在花朵授粉算法迭代的早期階段，自由度參數(shù)Iteration取值較小，t-分布主要呈現(xiàn)柯西分布特征，有助于維護種群多樣性，提升算法的全局搜索能力；算法迭代進行到中后期，t-分布主要呈現(xiàn)高斯分布特征，有助于算法在最優(yōu)花朵周圍，進行更精細、穩(wěn)定的局部探測，提高收斂精度。

2.2 局部搜索改進策略

原算法在進行局部搜索時，使用公式(3)生成新解。公式(3)為同類型植物不同花朵的花粉位置各維度，添加隨機數(shù)擾動生成新解，因隨機數(shù)的生成分布不穩(wěn)定，為此本文使用高斯變異替代原算法的隨機數(shù)擾動生成局部新解的方式，即使用公式(5)代替原算法的公式(3)。利用高斯變異良好的局部搜索能力，提高算法的收斂速度。

(5)

式中：N(0，1)為μ=0，σ=1的高斯分布，xjt、xkt是同類型植物不同花朵的花粉配子。

2.3 TFPA算法的執(zhí)行流程

改進的算法記為TFPA，其算法流程如下：

1)初始化參數(shù)。對迭代次數(shù)、搜索變量的維度、轉(zhuǎn)換概率、精英保留概率、種群規(guī)模、步長縮放因子等算法參數(shù)進行初始設(shè)置。

2)花朵種群初始化。在搜素域內(nèi)生成n朵花，花朵個體位置記為xi，并記錄最佳花朵位置x*。

3)生成一個隨機數(shù)γ1，如果轉(zhuǎn)換概率p>γ1，算法進入全局搜索，再隨機生成一個隨機數(shù)γ2，如果精英保留概率pe>γ2，按公式(4)進行位置更新，反之，按公式(1)進行位置更新。

4)如果轉(zhuǎn)換概率p<γ1，算法進入局部搜索，按公式(5)進行位置更新。

5)適應(yīng)度值排序，記錄當前最優(yōu)花朵信息。

6)重復(fù)步驟3)至5)，算法進入迭代尋優(yōu)搜索，直至滿足迭代結(jié)束條件為止。

3 實驗與結(jié)果分析

3.1 實驗方案和測試函數(shù)

本節(jié)對基本花朵授粉算法FPA和改進的TFPA算法做對比實驗。分別從固定迭代次數(shù)下的收斂精度、固定精度下的收斂速度、在特別高維上的尋優(yōu)性能及時間復(fù)雜度四個方面，對實驗結(jié)果進行分析。

仿真實驗選擇12個標準測試函數(shù)，函數(shù)的名稱、表達式、類型、變量范圍、理論極值和目標精度設(shè)定如表1所示。文獻[23]指出，維度越大、目標精度越高、變量取值范圍越大，尋優(yōu)難度就越大。為此，12個標準測試函數(shù)均使用比較嚴格苛刻的參數(shù)設(shè)置。部署仿真實驗的機器配置：Win10系統(tǒng)(64位)，內(nèi)存：4GB，CPU主頻：2.50GHz。

算法參數(shù)設(shè)置：花朵種群規(guī)模設(shè)為20，最大迭代次數(shù)設(shè)為800，精英保留概率pe=0.1，轉(zhuǎn)換概率和步長縮放因子取值：p=0.2，γ=16。

表1 標準測試函數(shù)

3.2 實驗結(jié)果分析與比較

1)固定迭代次數(shù)下的收斂精度比較

使用基本FPA算法和本文改進的TFPA算法，對表1中的12個標準測試函數(shù)進行函數(shù)尋優(yōu)。比較兩種算法在最差值、最優(yōu)值、優(yōu)化平均值、標準差4個指標上的性能優(yōu)劣。為了防止偶然性帶來的誤差，仿真程序分別隨機獨立運行50次，表2為實驗結(jié)果。表2中TFPA算法在Sphere、Schwefelf、Chung Reynolds、Griewank、Ackley、Rastrigin、Exponential、Csendes、Shubert、Schaffer F6十個函數(shù)上，在30維的情況下，每次均能收斂到函數(shù)的理論極值，而FPA算法的收斂情況與函數(shù)的理論極值相差甚遠。Shubert、Schaffer F6是低維多局部極值函數(shù)，TFPA算法每次均能收斂到函數(shù)的理論極值，而FPA算法均不能收斂到函數(shù)的理論極值。Rosenbrock函數(shù)被稱為香蕉函數(shù)，不易獲得理論極值，在30維時，TFPA算法在四個指標上均優(yōu)于FPA算法，且FPA算法的收斂精度誤差偏大。Zakharov函數(shù)的理論極值為0，TFPA算法在四個指標上均優(yōu)于FPA算法，TFPA算法的尋優(yōu)平均值為1.197 1×10-64，F(xiàn)PA算法的尋優(yōu)平均值為8.977 5×101，TFPA算法的最差值為2.735 2×10-63也比FPA算法的最優(yōu)值3.878 0×101高出64個數(shù)量級。

表2 實驗結(jié)果

圖1為TFPA和FPA算法的適應(yīng)度收斂曲線比較圖，圖1中除了f9、f11、f12三個函數(shù)外，其他函數(shù)的適應(yīng)度值均做了10為底的對數(shù)處理。從圖1中可知，TFPA算法收斂到最優(yōu)值的速度明顯優(yōu)于FPA算法。TFPA算法在f1、f3～f7、f10七個函數(shù)上適應(yīng)度曲線出現(xiàn)間斷，表明算法已經(jīng)收斂到函數(shù)理論極值0(對數(shù)的真數(shù)為0時不顯示)。

綜上所述，改進的TFPA算法在高維多峰、高維單峰及低維多極值函數(shù)上均有優(yōu)越的尋優(yōu)性能，在10個函數(shù)上均能每次都收斂到函數(shù)的理論極值，在Zakharov、Rosenbrock函數(shù)上的收斂精度大幅提高，表明改進的TFPA算法有效的提升了花朵授粉算法的收斂精度。

圖1 TFPA和FPA算法的適應(yīng)度收斂趨勢比較圖

2)固定精度下的收斂速度比較

按照表1中設(shè)定的目標精度，比較FPA和TFPA算法的平均迭代次數(shù)和尋優(yōu)成功率。FPA算法在預(yù)設(shè)目標精度下，均不能成功收斂到固定精度，而改進的TFPA算法在較高目標精度設(shè)定下，均能百分百成功收斂到固定精度。TFPA算法在12個函數(shù)上，收斂到目標精度使用的迭代次數(shù)分別為：33.3、31.5、30.2、24.7、38、40.8、41.8、217.5、169.2、43.2、846.4、51.3。TFPA算法在Shubert函數(shù)上平均迭代次數(shù)達到846.4，而在其他11個函數(shù)上均能使用比較少的迭代次數(shù)收斂到固定精度，從而說明改進的TFPA算法在收斂速度上有顯著提升。

3)在高維上的實驗結(jié)果

為了驗證TFPA算法在高維函數(shù)上的優(yōu)越性能，做兩種算法在512維上的對比實驗，程序獨立運行50次，比較FPA和TFPA算法在最差值、最優(yōu)值、優(yōu)化平均值、標準差四個指標上的性能，實驗結(jié)果如表3所示。

選擇3個高維單峰函數(shù)，4個高維多峰函數(shù)做實驗，從表3中可知，TFPA算法在Sphere、Chung Reynolds、Griewank、Ackley、Rastrigin、Exponential六個函數(shù)上每次均能收斂到函數(shù)的理論極值，50次實驗尋優(yōu)結(jié)果的標準差均為0，而FPA算法的尋優(yōu)結(jié)果與函數(shù)的理論極值相差甚遠。以Sphere為例，其理論極值為0，而FPA算法50次實驗的尋優(yōu)平均值為7.544 7×106。對于Schwefelf函數(shù)，TFPA算法的優(yōu)化平均值為4.793 7×10-303，最差值也達到1.071 0×10-301的數(shù)量級，而FPA算法因為尋優(yōu)結(jié)果太大，結(jié)果顯示為inf。因此，從衡量算法性能的四個指標結(jié)果看，TFPA算法在高維函數(shù)上表現(xiàn)出了優(yōu)越的尋優(yōu)性能。

表3 TFPA和FPA在512維上的尋優(yōu)結(jié)果

4)時間復(fù)雜度分析

一個優(yōu)秀的智能優(yōu)化算法在表現(xiàn)卓越尋優(yōu)性能的同時又要兼顧低的時間復(fù)雜度。改進算法的時間復(fù)雜度應(yīng)該不比原算法更高，運行時間不宜過長。表4為TFPA算法和FPA算法在7個高維函數(shù)上維數(shù)在30維，200維，512維上的平均運行時間。從表4的結(jié)果可知，在30維時TFPA的運行時間略高于FPA，在200維、512維時TFPA運行時間少于FPA算法，且隨著維數(shù)增加TFPA相對于FPA所用時間大幅減少，而尋優(yōu)精度正如表3所示得到大幅提高。說明基于t-分布的精英概率保留機制，通過引入精英個體保留概率，對最優(yōu)個體位置使用t-分布變異算子進行擾動計算，使得最優(yōu)個體位置信息能夠引導(dǎo)算法快速朝著最優(yōu)解靠近，提高了算法收斂精度，利用高斯變異良好的局部搜索能力，提高了算法的收斂速度。

表4 TFPA和FPA平均運行時間

綜上可得出，本文基于t-分布精英保留機制的花朵授粉算法，在全局搜索時通過設(shè)置精英概率保留參數(shù)，使得算法在尋優(yōu)過程中一部分最優(yōu)解得到保留，并對保留的最優(yōu)解實施t-分布擾動變異，能夠引導(dǎo)算法快速朝著最優(yōu)解靠近，從而提高了算法的收斂精度。在局部搜索時使用高斯變異代替原算法隨機數(shù)擾動因子，高斯變異具有優(yōu)越的局部開發(fā)能力，從而有效提高了算法的收斂速度。因此，改進的TFPA算法具有良好的魯棒性和更高的收斂精度及速度。

4 結(jié)論

本文改進的TFPA算法在維度為30維時，在3個高維單峰和5個高維多峰測試函數(shù)上均能收斂到函數(shù)的理論極值。在2個低維多極值函數(shù)上也均能收斂到函數(shù)的理論極值。在固定精度下能夠使用很少的迭代次數(shù)達到目標精度。在512維高維情況下，TFPA在Sphere、Chung Reynolds、Griewank、Ackley、Rastrigin、Exponential六個函數(shù)上均能收斂到函數(shù)的理論極值，并且實驗的維數(shù)從30維遞增到512維時，TFPA尋優(yōu)結(jié)果的優(yōu)化均值不變，均值平均變化率為0。從而表明，基于t-分布精英概率保留機制的花朵授粉算法，具有良好的魯棒性，顯著提高了算法的收斂精度和速度。