自適應(yīng)多策略花朵授粉算法

瞿博陽，李國森，焦岳超，柴旭朝，閆 李

(中原工學(xué)院 電子信息學(xué)院，河南 鄭州 450007)

0 引 言

花朵授粉算法(flower pollination algorithm，F(xiàn)PA)魯棒性好、實(shí)現(xiàn)簡(jiǎn)單和計(jì)算速度快，已在實(shí)際生活和工程領(lǐng)域中得到成功應(yīng)用[1-7]。然而，F(xiàn)PA算法極易陷入局部最優(yōu)解且尋優(yōu)精度不高。另外FPA的有關(guān)研究相當(dāng)欠缺，如何提升其性能具有一定的研究意義。

針對(duì)FPA存在的不足，國內(nèi)外學(xué)者在改進(jìn)其尋優(yōu)性能方面展開了研究。其中，一些學(xué)者采用增強(qiáng)多樣性的策略提高全局尋優(yōu)能力。李前等[8]使用萊維飛行以提高尋優(yōu)速度。崔麗群等[9]將折射原理引入花朵授粉算法，以跳出局部最優(yōu)。Zhou等[10]采用精英反向策略以平衡勘探和開采能力。王玉鑫等[11]使用均勻變異策略，以改善種群的探索能力。El-Shahat等[12]采用雜交策略提高種群多樣性。喬現(xiàn)偉等[13]使用混沌序列提升算法的尋優(yōu)效率。另外，通過結(jié)合其它算法也能求解到很好的結(jié)果。肖輝輝等[14]融合引力搜索算法，以改善花朵授粉算法的搜索效率。Nabil等[15]將克隆選擇算法引入花朵授粉算法，以改善種群多樣性。Wang等[16]融合人工蜂群算法，以提高算法的全局勘探能力。

為進(jìn)一步改善FPA的不足，本文提出自適應(yīng)多策略花朵授粉算法(SMFPA)，該算法采用錨點(diǎn)策略以提高種群的多樣性；使用攝動(dòng)策略以改善全局勘探能力；利用局部搜索策略以加強(qiáng)局部尋優(yōu)能力。

1 花朵授粉算法

花朵授粉算法包含兩個(gè)操作：全局授粉、局部授粉，并依賴轉(zhuǎn)換概率p(p=0.8)進(jìn)行授粉方式的選擇。其主要思想：先初始花粉種群，然后依據(jù)轉(zhuǎn)換概率p選擇其中的一個(gè)操作進(jìn)行位置更新，不斷重復(fù)此過程直至條件終止[17]。

(1)

(2)

2 自適應(yīng)多策略花朵授粉算法

2.1 錨點(diǎn)策略

在傳統(tǒng)花朵授粉算法中，每個(gè)花粉在全局授粉過程中采用全局最優(yōu)信息進(jìn)行位置的更新，這很難保持種群的多樣性。

圖1 錨點(diǎn)策略

為此，在全局授粉過程中，式(1)更新定義如下

(3)

2.2 攝動(dòng)策略

如果花粉個(gè)體在連續(xù)若干代內(nèi)總是訪問同一個(gè)錨點(diǎn)，那么在下一次迭代，該花粉個(gè)體仍有很高的概率訪問該錨點(diǎn)，這將導(dǎo)致花粉個(gè)體過度探索某一錨點(diǎn)所在的區(qū)域，而難以尋找更優(yōu)的解。因此，攝動(dòng)策略的基本思想是對(duì)這樣的花粉個(gè)體進(jìn)行一定的攝動(dòng)，使該花粉個(gè)體選擇新的錨點(diǎn)。首先為第i個(gè)花粉定義一個(gè)攝動(dòng)因子ζi， 其更新規(guī)則如下

(4)

式中：at,at-1分別是當(dāng)前和前一次迭代中第i個(gè)花粉所訪問的錨點(diǎn)。如果連續(xù)兩代，花粉個(gè)體總是訪問同一錨點(diǎn)，則花粉個(gè)體i的攝動(dòng)因子ζi增加1。

如果ζi>ζmean， 那么第i個(gè)花粉將進(jìn)行攝動(dòng)，即按式(5) 進(jìn)行更新

(5)

2.3 局部搜索增強(qiáng)策略

在標(biāo)準(zhǔn)FPA算法中，局部授粉采用隨機(jī)選擇兩個(gè)花粉的方式來實(shí)現(xiàn)花粉位置更新，導(dǎo)致尋優(yōu)過程具有盲目性。因此，式(2)重新定義如下

(6)

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

步驟1 設(shè)置SMFPA的參數(shù)：花粉種群規(guī)模NP，測(cè)試函數(shù)維數(shù)n，轉(zhuǎn)換概率p等。

步驟2 根據(jù)佳點(diǎn)集原理構(gòu)造錨點(diǎn)，并計(jì)算適應(yīng)度值，初始種群等于錨點(diǎn)，每個(gè)錨點(diǎn)中的最優(yōu)解等于其本身，每個(gè)花粉的攝動(dòng)因子初始化為0。

步驟3 對(duì)于每個(gè)錨點(diǎn)，計(jì)算種群中離其最近的個(gè)體，比較該個(gè)體和其錨點(diǎn)中解的適應(yīng)度。若個(gè)體優(yōu)于錨點(diǎn)中的解(a*)，則替換，否則，保持錨點(diǎn)中解不變。

步驟4 找出種群全局最優(yōu)(g*)。

步驟5 依據(jù)式(4)更新每個(gè)花粉的攝動(dòng)因子。

步驟6 判斷是否滿足 (p>rand)。 若滿足，則依據(jù)式(3)執(zhí)行全局授粉操作。

步驟7 判斷是否滿足 (p

步驟8 判斷是否滿足 (ζi>ζmean)。 若滿足，則按照公式(5)對(duì)花粉進(jìn)行攝動(dòng)策略。

步驟9 求出當(dāng)前最優(yōu)解，并更新對(duì)應(yīng)的適應(yīng)度值。

步驟10 判斷是否滿足實(shí)驗(yàn)設(shè)置的最大迭代次數(shù)。若滿足，輸出最優(yōu)花粉位置及其適應(yīng)度值并終止程序，否則執(zhí)行步驟3。

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

3.1 測(cè)試函數(shù)的選擇

為了測(cè)試SMFPA算法的性能，選擇12個(gè)測(cè)試問題進(jìn)行不同算法的對(duì)比[22,23]。其函數(shù)表達(dá)式等信息見表1。其中，f1～f7為單模問題，用于評(píng)估對(duì)比算法的尋優(yōu)精度。f8～f12為多模問題，具有多極值的特點(diǎn)[24]。因此，該類函數(shù)更難求解。

表1 基準(zhǔn)測(cè)試函數(shù)

3.2 實(shí)驗(yàn)參數(shù)設(shè)置與方法

將SMFPA與其它5種算法(FPA[1]、tMFPA[11]、MFPA[15]、EFPA[25]、PSO[26])進(jìn)行對(duì)比。其中，算法種群規(guī)模NP是30。其它對(duì)比算法的參數(shù)保持與相應(yīng)文獻(xiàn)一致。

3.3 結(jié)果與分析

3.3.1 固定迭代次數(shù)的性能分析

通過固定迭代次數(shù)，比較算法的最優(yōu)值、平均值、最差值及標(biāo)準(zhǔn)差。實(shí)驗(yàn)設(shè)置：算法獨(dú)立運(yùn)行30次；問題維度為30和100；最大迭代次數(shù)為500。結(jié)果見表2。

在30維和100維情況下，SMFPA算法的最優(yōu)值、平均值、最差值小于其它幾種算法，收斂精度相對(duì)高于其它算法，而且標(biāo)準(zhǔn)差最小，算法的搜索結(jié)果最穩(wěn)定，具有良好的魯棒性。對(duì)于函數(shù)f8和f10，SMFPA算法能夠收斂到理論最優(yōu)值。而且SMFPA算法在多模問題f8～f12表現(xiàn)良好，避免陷入了局部值，求解到了最優(yōu)解。而其它算法的性能較差，收斂緩慢，主要體現(xiàn)在其最優(yōu)值、平均值、最差值較大，甚至難以收斂到最優(yōu)值。這表明SMFPA采用錨點(diǎn)策略、攝動(dòng)策略、局部搜索增強(qiáng)策略不同程度的改善了勘探和開采能力。為直觀比較算法收斂性能，圖2為6個(gè)測(cè)試函數(shù)(f1～f6，30維)的適應(yīng)度值進(jìn)化曲線。

表2 固定迭代次數(shù)下不同算法結(jié)果對(duì)比(30維和100維)

表2(續(xù))

圖2 函數(shù)進(jìn)化曲線

在同一迭代次數(shù)下，SMFPA算法達(dá)到的適應(yīng)度值小于其它算法；在相同的適應(yīng)度值下，SMFPA算法達(dá)到的迭代次數(shù)小于其它算法。另外，SMFPA算法在100次迭代后基本能夠找到最優(yōu)解，而其它算法所需的迭代次數(shù)更多?？傮w上，SMFPA算法的尋優(yōu)性能更好。

3.3.2 固定收斂精度下的性能分析

通過固定收斂精度，比較算法的收斂性(最小收斂代數(shù)、平均收斂代數(shù)及收斂率)。實(shí)驗(yàn)設(shè)置：算法獨(dú)立運(yùn)行30次；收斂精度目標(biāo)為0.01；問題維度為30；最大迭代次數(shù)為10 000。在表3中，最小收斂代數(shù)表示算法優(yōu)化到收斂精度目標(biāo)的最小進(jìn)化代數(shù)；平均收斂代數(shù)表示算法優(yōu)化到收斂精度目標(biāo)所需代數(shù)的平均值；收斂率表示算法優(yōu)化到收斂精度目標(biāo)的運(yùn)行次數(shù)/總獨(dú)立運(yùn)行次數(shù)；“-”表示算法迭代次數(shù)超過最大迭代次數(shù)仍未達(dá)到收斂精度目標(biāo)。從實(shí)驗(yàn)結(jié)果可知，SMFPA算法的最小收斂代數(shù)、平均收斂代數(shù)及收斂率均優(yōu)于其它算法。而其它算法優(yōu)化到收斂精度目標(biāo)所需的迭代次數(shù)較大，甚至無法收斂最優(yōu)解?？傮w上，SMFPA的收斂速度更快。

表3 固定精度下不同算法結(jié)果對(duì)比

表3(續(xù))

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

以函數(shù)f1～f6為例，比較算法在時(shí)間復(fù)雜度上的可行性，實(shí)驗(yàn)參數(shù)設(shè)置與3.3.1節(jié)相同。從表4可知，PSO和FPA所需時(shí)間最短。其次是EFPA，tMFPA和SMFPA。對(duì)于FPA，時(shí)間復(fù)雜度：O(NP)；對(duì)于SMFPA，包含3個(gè)策略，分別為錨點(diǎn)策略、攝動(dòng)策略和局部搜索增強(qiáng)策略，各策略的時(shí)間復(fù)雜度：T(FPA基本操作)=O(NP)；T(錨點(diǎn)策略)=O(NP*NP)；T(攝動(dòng)策略)=O(NP)；T(局部搜索增強(qiáng)策略)=O(NP)。 因此，T(SMFPA)=T(FPA基本操作)+T(錨點(diǎn)策略)+T(攝動(dòng)策略)+T(局部搜索增強(qiáng)策略)， 化簡(jiǎn)后可以得到SMFPA算法的時(shí)間復(fù)雜度為O(NP*NP)。 相比FPA算法，SMFPA復(fù)雜度有所提高。總體上，SMFPA算法的時(shí)間復(fù)雜度相對(duì)較低。

表4 算法運(yùn)行時(shí)間對(duì)比

4 工程應(yīng)用

為驗(yàn)證SMFPA算法的性能，對(duì)管柱設(shè)計(jì)問題進(jìn)行了計(jì)算。管柱設(shè)計(jì)問題是在滿足約束g1,g2條件下，求解管柱直徑d和厚度t使其成本最小[27]。Yang[27]、Hsu[28]、Rao[29]采用不同的算法對(duì)其進(jìn)行求解。表5展示了SMFPA算法和其它算法的結(jié)果對(duì)比。可以看出，和其它算法相比，SMFPA算法的求解結(jié)果更優(yōu)。

表5 不同算法結(jié)果對(duì)比

5 結(jié)束語

本文提出自適應(yīng)多策略花朵授粉算法(SMFPA)，采用錨點(diǎn)策略使種群個(gè)體充分利用鄰域信息以改善算法收斂速度，提高花粉個(gè)體多樣性；利用攝動(dòng)策略對(duì)過度開采某一區(qū)域的花粉個(gè)體進(jìn)行攝動(dòng)以防止陷入局部極值，改善全局勘探能力；采用局部搜索增強(qiáng)策略使種群尋優(yōu)更具有方向性并提升開采最優(yōu)解的能力。對(duì)比算法在12個(gè)測(cè)試函數(shù)和管柱設(shè)計(jì)問題上的尋優(yōu)結(jié)果表明，SMFPA算法在尋優(yōu)速度以及尋優(yōu)精度方面表現(xiàn)更好。