張 超

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

自然界中的很多生物種群涌現(xiàn)出不同形式的群體行為特征。學(xué)者們對這些智能涌現(xiàn)的群體行為模式進(jìn)行研究，仿生設(shè)計(jì)了各種元啟發(fā)式群智能優(yōu)化算法，如粒子群算法、蝙蝠算法、遺傳算法、和聲算法、蟻群算法等。這些算法因其設(shè)計(jì)簡單、結(jié)構(gòu)靈活，已在自然科學(xué)和工程等領(lǐng)域被廣泛應(yīng)用[1]?；ǘ涫诜鬯惴╗2-3](Flower Pollination Algorithm，F(xiàn)PA)是基于自然界中的花授粉過程，設(shè)計(jì)的一種智能優(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)外學(xué)者對花朵授粉算法進(jìn)行了優(yōu)化和改進(jìn)研究工作。文獻(xiàn)[11]等利用logsig函數(shù)對解進(jìn)行變換，映射到0-1空間中，提出了二進(jìn)制花朵授粉算法。文獻(xiàn)[12-13]分別對花朵授粉算法的兩個(gè)控制參數(shù)：轉(zhuǎn)換概率p和全局搜索時(shí)的移動(dòng)步長縮放因子γ做取值對比試驗(yàn)，得出p=0.2，γ=16時(shí)花授粉算法對大多數(shù)測試函數(shù)的尋優(yōu)能力更好。文獻(xiàn)[14-15]認(rèn)為初始解的質(zhì)量影響花朵授粉算法的尋優(yōu)能力，為此分別通過螢火蟲算法、粒子群算法、和聲算法獲得待優(yōu)化問題的最優(yōu)解，并將該最優(yōu)解作為花朵授粉算法的初始解，以期提高花朵授粉算法的尋優(yōu)精度和速度。文獻(xiàn)[16-17]中分別把雜草算法和差分進(jìn)化算法的思想融入到花朵授粉算法中，通過擴(kuò)展種群的多樣性提高算法的全局搜索能力。文獻(xiàn)[18-19]將量子行為引入到花朵授粉算法中，分別利用量子的隨機(jī)性搜索、態(tài)疊加特性增強(qiáng)花朵授粉算法的全局搜索能力。文獻(xiàn)[20]等使用精英混沌搜索對種群中部分花朵個(gè)體進(jìn)行變異，提高了花朵授粉算法的尋優(yōu)速度。文獻(xiàn)[21]等將精英保留機(jī)制引入到花朵授粉算法中，使用外部存檔法對個(gè)體的適應(yīng)度進(jìn)行排序，按一定比例選擇適應(yīng)度好的個(gè)體進(jìn)入下一迭代，通過精英個(gè)體的引導(dǎo)，提高算法的收斂速度。文獻(xiàn)[22]將引力搜索機(jī)制添加到基本花朵授粉算法的全局搜索部分，使用萬有引力牽制Levy飛行的隨機(jī)游走，提高了算法的收斂精度。

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

1 花朵授粉算法

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

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

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

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

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

(1)

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

(2)

式中：λ=3/2，Γ(λ)為標(biāo)準(zhǔn)伽瑪函數(shù)。

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

(3)

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

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

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

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

2.1 全局搜索改進(jìn)策略

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

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

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

(4)

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

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

(5)

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

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

2.2 局部搜索改進(jìn)策略

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

(5)

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

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

改進(jìn)的算法記為TFPA，其算法流程如下：

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)方案和測試函數(shù)

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

仿真實(shí)驗(yàn)選擇12個(gè)標(biāo)準(zhǔn)測試函數(shù)，函數(shù)的名稱、表達(dá)式、類型、變量范圍、理論極值和目標(biāo)精度設(shè)定如表1所示。文獻(xiàn)[23]指出，維度越大、目標(biāo)精度越高、變量取值范圍越大，尋優(yōu)難度就越大。為此，12個(gè)標(biāo)準(zhǔn)測試函數(shù)均使用比較嚴(yán)格苛刻的參數(shù)設(shè)置。部署仿真實(shí)驗(yàn)的機(jī)器配置：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 標(biāo)準(zhǔn)測試函數(shù)

3.2 實(shí)驗(yàn)結(jié)果分析與比較

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

使用基本FPA算法和本文改進(jìn)的TFPA算法，對表1中的12個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行函數(shù)尋優(yōu)。比較兩種算法在最差值、最優(yōu)值、優(yōu)化平均值、標(biāo)準(zhǔn)差4個(gè)指標(biāo)上的性能優(yōu)劣。為了防止偶然性帶來的誤差，仿真程序分別隨機(jī)獨(dú)立運(yùn)行50次，表2為實(shí)驗(yàn)結(jié)果。表2中TFPA算法在Sphere、Schwefelf、Chung Reynolds、Griewank、Ackley、Rastrigin、Exponential、Csendes、Shubert、Schaffer F6十個(gè)函數(shù)上，在30維的情況下，每次均能收斂到函數(shù)的理論極值，而FPA算法的收斂情況與函數(shù)的理論極值相差甚遠(yuǎn)。Shubert、Schaffer F6是低維多局部極值函數(shù)，TFPA算法每次均能收斂到函數(shù)的理論極值，而FPA算法均不能收斂到函數(shù)的理論極值。Rosenbrock函數(shù)被稱為香蕉函數(shù)，不易獲得理論極值，在30維時(shí)，TFPA算法在四個(gè)指標(biāo)上均優(yōu)于FPA算法，且FPA算法的收斂精度誤差偏大。Zakharov函數(shù)的理論極值為0，TFPA算法在四個(gè)指標(biāo)上均優(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個(gè)數(shù)量級(jí)。

表2 實(shí)驗(yàn)結(jié)果

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

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

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

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

按照表1中設(shè)定的目標(biāo)精度，比較FPA和TFPA算法的平均迭代次數(shù)和尋優(yōu)成功率。FPA算法在預(yù)設(shè)目標(biāo)精度下，均不能成功收斂到固定精度，而改進(jìn)的TFPA算法在較高目標(biāo)精度設(shè)定下，均能百分百成功收斂到固定精度。TFPA算法在12個(gè)函數(shù)上，收斂到目標(biāo)精度使用的迭代次數(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ù)達(dá)到846.4，而在其他11個(gè)函數(shù)上均能使用比較少的迭代次數(shù)收斂到固定精度，從而說明改進(jìn)的TFPA算法在收斂速度上有顯著提升。

3)在高維上的實(shí)驗(yàn)結(jié)果

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

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

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

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

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

表4 TFPA和FPA平均運(yùn)行時(shí)間

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

4 結(jié)論

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