洪 露,賀興時(shí)，楊新社

(1.西安工程大學(xué) 理學(xué)院，陜西 西安 710048；2.密德薩斯大學(xué) 科學(xué)與技術(shù)學(xué)院,英國(guó) 倫敦 NW4 4BT)

0 引 言

為解決復(fù)雜的優(yōu)化問題以及更為合理和滿意的近似解，科研工作者們?cè)O(shè)計(jì)了大量的群智能算法，并在過去的幾十年中得到迅速發(fā)展，成為當(dāng)前最活躍的算法研究領(lǐng)域之一。群智能算法主要有布谷鳥算法[1](cuckoo search,CS)、蝙蝠算法[2](bat algorithm,BA)、螢火蟲算法[3](firefly algorithm,FA)、蟻群算法[4](ant algorithm,AA)等。為了使算法在解決復(fù)雜優(yōu)化問題時(shí)更加高效,諸多學(xué)者也提出相應(yīng)的改進(jìn)策略[5-7]。

花授粉算法(flower pollination algorithm,FPA)最早由劍橋大學(xué)學(xué)者楊新社提出。這種算法具有參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、穩(wěn)定性和執(zhí)行效率高等特點(diǎn),目前已經(jīng)應(yīng)用到了諸多領(lǐng)域；但該算法也存在收斂速度慢、易陷入局部最優(yōu)、收斂精度低等缺陷,所以諸多學(xué)者也對(duì)FPA算法進(jìn)行了改進(jìn)[8-11]。文獻(xiàn)[12]提出了將克隆技術(shù)和花授粉算法融合在一起的混合二進(jìn)制算法。但是，該算法也存在一定缺陷，如算法中涉及參數(shù)缺少一定的理論基礎(chǔ)、執(zhí)行到后期時(shí)算法收斂速度明顯變慢、算法在執(zhí)行過程中容易陷入局部最優(yōu)、整體收斂性的相關(guān)理論證明不夠充分等不足。針對(duì)該算法的這些缺陷，很多學(xué)者提出了改進(jìn)和應(yīng)用方案。YANG等提出在基本花授粉算法中存在的鷹策略(eagle strategy,ES)，是提升算法優(yōu)越性的根本原因，完善了算法理論[13]；EL-HENAWY等將混沌理論思想引入基本花授粉算法中，使得花粉配子離散化，提出的基于混沌思想花授粉算法應(yīng)用，解決了大整數(shù)規(guī)劃問題[14]；肖輝輝等則成功將模擬退火原理思想與花授粉算法相融合，在解決函數(shù)優(yōu)化問題中具有一定優(yōu)勢(shì)[15]；肖輝輝等還提出將Powell法和高斯變異機(jī)制引進(jìn)到基本花授粉算法中形成混合算法，并對(duì)其控制步長(zhǎng)的影響因子進(jìn)行了測(cè)試修改，改變種群多樣性的同時(shí)提升全局探索性能及局部開發(fā)機(jī)制[16]；HE等使用數(shù)學(xué)方法中馬爾可夫鏈理論證明了花授粉算法的收斂性，通過為花粉種群構(gòu)建適當(dāng)?shù)霓D(zhuǎn)換概率并使用同質(zhì)性,證明構(gòu)造的隨機(jī)序列可以收斂到最優(yōu)集合[17]；張超提出了分?jǐn)?shù)階擴(kuò)散方程參數(shù)反演的改進(jìn)花授粉算法，提升了算法的整體性能[18]。但是，對(duì)于花授粉算法收斂速度慢、易陷入局部最優(yōu)及收斂精度低等問題，上述改進(jìn)方法的效果是有限的。

針對(duì)FPA算法存在的諸多問題，本文提出了三重動(dòng)態(tài)調(diào)整花授粉算法(HLFPA)， 增加以下策略：將轉(zhuǎn)換概率動(dòng)態(tài)化；在異花授粉過程中引入新型動(dòng)態(tài)因子ω；在局部搜索更新過程中，引入了新型步長(zhǎng)因子μ。隨機(jī)選取7個(gè)基準(zhǔn)函數(shù)對(duì)改進(jìn)后的FPA算法進(jìn)行測(cè)試，并與基礎(chǔ)FPA算法、CS算法、ASCSA算法比較。

1 花授粉算法

花授粉算法是一種模擬自然界花朵授粉過程而設(shè)計(jì)出來的一種啟發(fā)式算法。異花授粉對(duì)應(yīng)全局搜索過程，自花授粉對(duì)應(yīng)局部搜索過程，并且通過切換概率P∈(0,1)平衡2種搜索行為的比例。為了使算法過程盡可能簡(jiǎn)化，不妨假設(shè)以下4條理想化原則：

1) 異花授粉可被視作花粉傳遞者使用Levy飛行進(jìn)行全局授粉過程；

2) 自花授粉可視作局部授粉過程；

3) 花的恒長(zhǎng)性可視作繁殖概率，其與授粉過程中兩朵花的相似度成正比；

4) 授粉方式通過切換概率p∈(0,1)，且當(dāng)隨機(jī)數(shù)rand(·)>p時(shí)，執(zhí)行自花授粉過程， 否則就執(zhí)行異花授粉過程。

異花授粉及全局搜索過程，更新公式為

(1)

(2)

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

2.1 動(dòng)態(tài)概率Pa

為了平衡FPA算法的全局搜索和局部搜索，使算法更加靈活，將固定轉(zhuǎn)換概率0.8更改為隨著迭代次數(shù)自適應(yīng)變化的動(dòng)態(tài)轉(zhuǎn)換概率Pα，即

Pa=wmax-(wmax-wmin)α

(3)

α由式(4)計(jì)算得到,即

(4)

式中：wmax與wmin分別為w的最大值與最小值;t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)。根據(jù)文獻(xiàn)[19]，wmax=0.9，wmin=0.2。在迭代初期，Pa的取值較大，所以算法側(cè)重于全局搜索，有效地增強(qiáng)了全局搜索能力，使得種群中的個(gè)體更靠近最優(yōu)解；隨著迭代深入，Pa的值越來越小，使算法更傾向局部精細(xì)的搜索，有利于算法后期快速找到最優(yōu)解。

2.2 新型動(dòng)態(tài)因子ω

為了提高FPA算法跳出局部最優(yōu)的能力，在式(1)給出的算法模型基礎(chǔ)上引入新型動(dòng)態(tài)因子ω[20]，調(diào)節(jié)種群迭代過程中搜索個(gè)體對(duì)當(dāng)前母系花粉位置信息的依賴性。新型動(dòng)態(tài)因子ω的計(jì)算公式如(5)式所示:

ω=ω1·?

(5)

式中：

(6)

計(jì)算得ω1的取值范圍為[0,0.367 9]，即

迭代前期動(dòng)態(tài)因子ω值較小，削弱母系花粉位置對(duì)算法的影響，讓花粉更自由地以Levy飛行在搜索空間內(nèi)大范圍地進(jìn)行搜索，增加全局搜索的能力。迭代后期，動(dòng)態(tài)因子ω減小，使跳出局部最優(yōu)的能力得到增強(qiáng)。改進(jìn)后的異花授粉公式為

(7)

2.3 正弦余弦步長(zhǎng)因子μ

花授粉算法局部搜索機(jī)制中步長(zhǎng)因子ε為(0，1)中的隨機(jī)數(shù)，算法迭代到后期容易導(dǎo)致求解精度低，易陷入局部最優(yōu)等問題，所以本文提出了正弦余弦步長(zhǎng)因子μ

(8)

r1由式(9)計(jì)算可得，即

(9)

式中:a=1;r2∈[0,2π];r3為[0,1]之間的隨機(jī)數(shù)。

圖1為步長(zhǎng)因子隨迭代時(shí)間t變化圖。由圖1可知:若迭代初期出現(xiàn)自花授粉的過程，較大的步長(zhǎng)因子，使得算法前期具有較好的跳出局部最優(yōu)的能力;隨著迭代次數(shù)增加，動(dòng)態(tài)概率Pa逐漸減小，使得算法后期主要進(jìn)行自花授粉過程；在算法后期，隨著迭代次數(shù)的增加，正余弦步長(zhǎng)因子的精度數(shù)量級(jí)也不斷增加，有效地提高了算法的求解精度。改進(jìn)后的自花授粉公式為

(10)

圖1 步長(zhǎng)因子變化圖Fig.1 Variation of step factor

2.4 實(shí)現(xiàn)步驟

1) 初始化算法中各個(gè)參數(shù)。初始化花粉種群規(guī)模N、最大迭代次數(shù)Tmax,根據(jù)式(3)定義異花授粉和自花授粉轉(zhuǎn)換概率Pa。

2) 初始化花粉種群。尋找當(dāng)前最優(yōu)花粉和其所處地位置gb，并計(jì)算出其適應(yīng)度值f(gb)。

3) 進(jìn)入主循環(huán)過程，隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)rand(·)，如果rand(·)>Pa,則按照式(7)進(jìn)行異花授粉，更新當(dāng)前花粉位置; 否則,根據(jù)式(10)進(jìn)行自花授粉，并更新花粉位置。

5) 與最優(yōu)花粉進(jìn)行比較，如果f(xn)

6) 若當(dāng)前花粉不是種群中最后一個(gè)花粉，則選擇下一個(gè)花粉，并返回步驟4)；否則，轉(zhuǎn)至步驟7)。

7) 滿足算法的終止條件(達(dá)到最大迭代次數(shù))，則進(jìn)行步驟8);否則進(jìn)入步驟3)，繼續(xù)進(jìn)入下一代搜索。

8) 輸出最優(yōu)的花粉個(gè)體xn和全局最優(yōu)解f(xn)。

3 實(shí)驗(yàn)仿真與分析

為了驗(yàn)證算法的有效性與可行性，從Benchmarks測(cè)試函數(shù)中選取了7個(gè)典型函數(shù)進(jìn)行測(cè)試，并從4個(gè)方面分析其性能。測(cè)試函數(shù)與算法參數(shù)見表1和表2，表1中測(cè)試函數(shù)最優(yōu)值均為0。

表1 測(cè)試函數(shù)Tab.1 Test functions

表2 算法參數(shù)Tab.2 Algorithm parameters

3.1 算法收斂曲線

圖2～8分別為4種算法在f1(x)～f7(x)函數(shù)中的收斂曲線圖，各函數(shù)維數(shù)均為10。

圖2 f1(x)函數(shù)收斂曲線Fig.2 Convergence curve of function f1(x)

圖3 f2(x)函數(shù)收斂曲線Fig.3 Convergence curve of function f2(x)

圖4 f3(x)函數(shù)收斂曲線Fig.4 Convergence curve of function f3(x)

圖5 f4(x)函數(shù)收斂曲線Fig.5 Convergence curve of function f4(x)

圖7 f6(x)函數(shù)收斂曲線Fig.7 Convergence curve of function f6(x)

圖8 f7(x)函數(shù)收斂曲線Fig.8 Convergence curve of function f7(x)

由圖2～8可知：HLFPA算法在收斂速度上明顯優(yōu)于CS算法、FPA算法和ASCSA算法，且在50代左右都可以收斂到全局最優(yōu)，表明HLFPA算法具有較快的收斂速度和較好的收斂精度。f1(x)～f3(x)為多峰函數(shù)，存在多個(gè)局部極小點(diǎn)，可用于測(cè)試算法的跳出局部最優(yōu)和尋優(yōu)能力。由圖2～4可以看出：HLFPA算法具有較強(qiáng)的尋優(yōu)能力，有效克服了易陷入局部最優(yōu)的缺點(diǎn)。f4(x)～f7(x)為單峰函數(shù)，用于測(cè)試算法的收斂速度。由圖5～8可以看出：HLFPA算法在50代左右可以收斂到全局最優(yōu)?？梢?，無論單峰還是多峰的高維函數(shù)，HLFPA算法都表現(xiàn)出了較好的尋優(yōu)能力和較快的收斂速度。

3.2 算法求解精度比較

在維數(shù)分別為50、100的條件下，用4種算法對(duì)f1(x)～f7(x)函數(shù)進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如表3～9。

表3 f1(x)函數(shù)仿真結(jié)果Tab.3 Simulation resutls of f1(x)

表4 f2(x)函數(shù)仿真結(jié)果Tab.4 Simulation resutls of f2(x)

表5 f3(x)函數(shù)仿真結(jié)果Tab.5 Simulation results of f3(x)

表6 f4(x)函數(shù)仿真結(jié)果Tab.6 Simulation results of f4(x)

表7 f5(x)函數(shù)仿真結(jié)果Tab.7 Simulation results of f5(x)

表8 f6(x)函數(shù)仿真結(jié)果Tab.8 Simulation results of f6(x)

表9 f7(x)函數(shù)仿真結(jié)果Tab.9 Simulation results of f7(x)

f1(x)為復(fù)雜的多峰函數(shù)，常常導(dǎo)致算法在求解時(shí)陷入局部最優(yōu)。由表3可見，HLFPA算法在求解精度上和穩(wěn)定性上遠(yuǎn)遠(yuǎn)高于其他3種算法,但是在后期求解時(shí)也陷入了局部最優(yōu)8.88×10-6。f2(x)為典型的非線性多模態(tài)函數(shù),且圖像跌宕起伏不定。由表4可見，其他3種算法隨著維度的增加，尋優(yōu)能力逐漸減弱，但HLFPA算法均可以收斂到全局最優(yōu)位置，表現(xiàn)出卓越的尋優(yōu)能力。

f3(x)為典型的多模態(tài)函數(shù)，不僅搜索區(qū)域大，而且存在許多局部極小點(diǎn)，通常被用來測(cè)試智能算法跳出局部最優(yōu)的能力。由表5可見，HLFPA算法可以收斂到全局最優(yōu)，表現(xiàn)出了較好的搜索性能和跳出局部最優(yōu)的能力。f4(x)～f7(x)均為高維單峰函數(shù)，常用于評(píng)價(jià)算法后期的搜索性能和尋優(yōu)能力。HLFPA算法在維數(shù)為50、100的情況下，均可以收斂到全局最優(yōu)，HLFPA算法的標(biāo)準(zhǔn)差也遠(yuǎn)遠(yuǎn)優(yōu)于其他3種算法(表6～9)，說明HLFPA算法具有更強(qiáng)的穩(wěn)定性。

4 結(jié) 語(yǔ)

HLFPA算法是針對(duì)FPA存在的不足進(jìn)行的優(yōu)化改進(jìn)。將固定轉(zhuǎn)換概率改為隨迭代減小的動(dòng)態(tài)轉(zhuǎn)換概率，更好地平衡了2種搜索機(jī)制的轉(zhuǎn)換；在異花授粉母系花粉位置引入新型變化因子，提升了算法跳出局部最優(yōu)的能力；在局部搜索更新公式中引入新型正余弦步長(zhǎng)因子，提高了算法的收斂精度。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的 FPA算法具有較快的收斂速度、較高的尋優(yōu)精度，且適用于高維復(fù)雜函數(shù)求解問題。改進(jìn)后的花授粉算法對(duì)二維函數(shù)的優(yōu)化效果一般，下一步將在花授粉算法的參數(shù)設(shè)置和應(yīng)用方面做進(jìn)一步研究。