t-分布擾動策略和變異策略的花授粉算法

寧杰瓊，何 慶

(貴州大學 大數(shù)據(jù)與信息工程學院，貴陽 550025) (貴州大學 貴州省公共大數(shù)據(jù)重點實驗室，貴陽 550025)

1 引 言

近年來許多學者越來越重視元啟發(fā)式群智能算法，通過不斷地研究提出了一系列的群智能優(yōu)化算法，常用的包括粒子群優(yōu)化算法(PSO)[1]、螢火蟲算法(FA)[2]、蝙蝠算法(BA)[3]、布谷鳥算法(CS)[4]等.花授粉算法(Flower pollination algorithm，F(xiàn)PA)是英國劍橋大學學者Yang于2012年提出的一種新型元啟發(fā)式群智能優(yōu)化算法[5].該算法模擬了顯花植物的異花授粉和自花授粉這兩個過程，與算法中的全局搜索機制和局部搜索機制相對應.由于該算法超參數(shù)少，結構簡單，易于實現(xiàn)，從而受到學者的廣泛關注.目前花授粉算法已經(jīng)成功應用于多目標優(yōu)化、函數(shù)優(yōu)化等問題中.但是，與其他群智能算法類似，F(xiàn)PA算法存在易陷入局部最優(yōu)、迭代后期收斂速度慢、尋優(yōu)精度差等缺點.

為了解決這些問題，使FPA算法的性能進一步提高，近年來國內外出現(xiàn)了很多對此算法的改進.邵良杉等[6]提出了一種基于天牛須搜索的花授粉算法，將天牛須搜索引入到全局搜索階段，在局部搜索階段加入變異策略使算法能夠跳出局部最優(yōu)，結果表明算法在低維和高維下收斂速度和精度都得到了提高.陳西成等[7]將小生境策略和混沌優(yōu)化策略應用到花授粉算法中，結果表明在兩種策略的結合下，避免了算法早熟收斂，提升了全局尋優(yōu)能力，同時算法的搜索精度也得到了顯著提高.肖輝輝等[8]在迭代前期只將高斯變異引入到花授粉算法的全局尋優(yōu)部分，迭代后期在引入高斯變異的同時，將Powell搜索法引入到局部搜索過程中，結果表明GMPFPA算法相比于FPA算法，收斂精度有了明顯提高.劉景森等人[9]將模擬退火機制融入花授粉算法中，并且將全局步長和局部繁衍概率結合迭代次數(shù)來進行改進，結果表明算法的尋優(yōu)精度和收斂速度均有較大提升.Shambour[10]等人在全局尋優(yōu)部分利用進化過程中隨機選取的兩個解信息，將算法的探測部分調整到特定的搜索區(qū)域，結果表明所提出的mgFPA算法與FPA算法相比，解的質量得到進一步地提高.Nabil[11]將基本花授粉算法與克隆選擇算法(CSA)融合，實驗結果表明該算法的尋優(yōu)精度和收斂速度有了一定程度的提高.

以上文獻對基本花授粉算法都有一定程度的改進，大部分算法相較于FPA算法，收斂速度明顯加快，解的質量得到一定程度的提高，但在尋優(yōu)精度、收斂性能等方面還有很大的提升空間，而且Shambour[10]等人和Nabil[11]只是在低維情況下對改進花授粉算法的性能進行了測試，沒有在高維情況下對算法的性能進行測試.由于大部分的群智能算法存在容易陷入局部最優(yōu)這一缺點，有學者加入了變異因子進行擾動，例如，賀智明等人將柯西變異引入到傳統(tǒng)花授粉算法中[12]，沈鑫等人在差分進化算法的變異操作中加入柯西擾動[13]，王越等人將變異算子加入二進制粒子群優(yōu)化算法[14]，而t-分布擾動算子很少被使用到.因此，本文提出t-分布擾動策略和變異策略的花授粉算法(tMFPA).該算法將t-分布擾動策略和差分變異策略分別引入到全局授粉過程和局部授粉過程，最終選取7個基本測試函數(shù)進行實驗，驗證了tMFPA算法在收斂能力和搜索能力上的有效性和優(yōu)越性.

2 相關工作

2.1 花授粉算法

花授粉算法模擬了自然界中顯花植物的花朵授粉過程.為了簡化問題，使算法更加高效，同時考慮到優(yōu)化問題僅有一個解，Yang假設每株顯花植物都只能孕育出一朵花，并且每朵花只能產(chǎn)生一個花粉配子.根據(jù)文獻[5]的描述，花朵授粉過程可以總結為以下4條規(guī)律：

a)生物異花授粉被視為全局授粉過程，花粉載體攜帶花粉執(zhí)行Levy飛行.

b)非生物自花授粉被視為局部授粉過程.

c)繁衍概率即為花的恒常性，繁衍概率的取值大小與兩朵花的相似性成正比.

d)利用轉換概率p∈[0,1]來控制局部授粉和全局授粉的轉換.

通過以上規(guī)則，建立如下的數(shù)學模型：

定義1.在全局授粉過程中，花粉的位置更新公式為：

(1)

(2)

其中，Γ(λ)是標準伽馬函數(shù)；λ=1.5.

定義2.局部授粉階段的位置更新公式如下：

(3)

定義3.通過轉換概率p∈[0,1]取值來控制全局授粉和局部授粉之間的轉換，經(jīng)過大量仿真實驗表明，當p=0.8時，算法可以得到最好的尋優(yōu)性能.

2.2 差分變異

差分進化算法(Differential evolution algorithm，DE)是由Storn等人提出的一種啟發(fā)式算法[15]，該算法包括3種算子：差分變異算子、交叉算子和選擇算子.在這3種算子中，差分變異算子有著核心地位，起著至關重要的作用.差分進化變異策略最基本的變異策略如下：

(4)

差分進化變異策略還有其他變種[16]，如：

(5)

Zheng等[17]在研究了差分進化算法后，提出了一種新的差分進化策略：

(6)

3 t-分布擾動策略和變異策略的花授粉算法

3.1 混沌映射初始化花朵個體位置

由于傳統(tǒng)花授粉算法采用隨機方式對花朵個體的位置進行初始化，這就可能導致花朵個體的初始位置分布不均勻.混沌具有隨機性、對初值敏感等特點，可以在一定范圍內按照自己的規(guī)律遍歷所有狀態(tài)而不重復[18]，因此本文利用混沌映射來初始化花朵個體的位置，使花朵個體的初始位置分布地更加均勻.針對n個花朵個體(d維空間)，本文采用混沌映射初始化種群的步驟如下:

a)首先隨機產(chǎn)生一個在[0,1]區(qū)間內的d維向量c1(第一個花粉個體).

b)利用logistic映射[19]迭代產(chǎn)生其余的n-1個向量，logistic映射公式如下：

ci+1=μci(1-ci)

(7)

其中，μ為控制參數(shù)，當μ=4時，logistic映射分布最均勻，ci為花朵個體經(jīng)過混沌映射后的位置，i=1,2,3,…,n-1.

c)將混沌映射后的值再映射到解的搜索空間中，公式如下：

xi=L+ci(U-L)

(8)

其中，L和U分別是搜索空間的上下限，xi是花朵個體在搜索空間中的初始位置.

3.2 基于t-分布擾動策略的全局搜索

在基本花授粉算法中，全局搜索是在當前最優(yōu)的花朵個體的基礎上，使用萊維飛行函數(shù)來反映昆蟲等授粉者的飛行軌跡，更新當前花朵個體的位置生成新解.由于萊維飛行具有步長長短相間和跳躍方向多變的特點，算法可以在相應范圍對花朵進行全局搜索，但也可能會因跳躍太大導致最優(yōu)花朵個體信息的丟失.而且每一代花朵位置的更新都是通過當前一代的位置和最優(yōu)位置利用萊維飛行機制更新，不能有效地拓展搜索空間.因此，tMFPA在保留萊維飛行特征的同時，將種群中其他個體的信息引入到全局搜索更新機制中，通過在個體之間交換信息來調整位置更新機制，增強了搜索空間的多樣性.為了使其他花朵個體能夠盡可能地被遍歷到，引入t-分布擾動算子對隨機花朵個體進行擾動.改進后的全局搜索位置更新公式為:

(9)

其中，m∈[0,1]，步長γ的表達式如下：

γ=0.01+0.49(t/N_iter)

(10)

公式(9)對隨機花朵個體進行t-分布擾動，t-分布的自由度隨著迭代次數(shù)的變化而變化.隨著自由度參數(shù)t值的增長，數(shù)值分布狀態(tài)逐漸由Cauchy分布趨近于Gaussian分布.算法迭代前期，t-分布表現(xiàn)出的特征與Cauchy分布特征一致，幫助開采新的搜索空間，提高算法的全局搜索能力；在中后期時，t-分布表現(xiàn)出的特征與Gaussian分布特征一致，有助于算法在當前解鄰域范圍內進行搜索.在改進的位置更新公式中，將全局搜索策略分為兩部分，在每次迭代時評估rand和m的關系以確定使用哪種方法.當rand

3.3 基于變異策略的局部搜索

相對于單個差分向量的策略，具有兩個差分向量的變異策略可以提高種群的多樣性，并且僅使用單個差分向量策略仍有可能使算法陷入局部最優(yōu)，而算法可以得到全局最優(yōu)的關鍵是算法能否跳出局部最優(yōu).因此將原始差分變異策略根據(jù)式(5)和式(6)進行改進，將改進后的差分變異策略引入到局部搜索，在全局最優(yōu)解的基礎上，保持了差分向量確定性與隨機性的平衡，提高了種群的多樣性，在此基礎上，將小概率變異策略引入局部搜索，通過判斷rand和q之間的關系來決定使用哪種更新方式，最終通過兩種策略的結合提高算法跳出局部最優(yōu)的能力.改進后的局部搜索位置更新公式為：

(11)

3.4 算法實現(xiàn)

針對花授粉算法的局限性，本文提出了t-分布擾動策略和變異策略的花授粉算法(tMFPA)，將t-分布擾動策略和差分變異策略分別引入到全局授粉過程和局部授粉過程中，tMFPA算法的具體實施步驟如下：

a)初始化.

初始化算法的參數(shù)：種群數(shù)n，轉換概率p，最大迭代次數(shù)N_iter等參數(shù).利用混沌映射初始化種群的位置，計算每個花朵個體的適應度值，并求解出當前的全局最優(yōu)值.

b)個體位置更新、全局最優(yōu)值更新.

若rand

c)判斷算法是否結束.

如果算法滿足結束條件就輸出最優(yōu)花朵個體位置和全局最優(yōu)目標函數(shù)值；如果不滿足，轉到步驟b)，直到滿足結束條件.

tMFPA算法的具體流程圖見圖1.

圖1 tMFPA算法流程Fig.1 Schematic diagram of tMFPA

3.5 tMFPA算法復雜度分析

假設優(yōu)化的目標函數(shù)為f(x)，解空間的維數(shù)為d，根據(jù)FPA算法的步驟，F(xiàn)PA的時間復雜度為O(d+f(d)).根據(jù)tMFPA算法步驟，假設種群規(guī)模為n，利用混沌映射產(chǎn)生花朵個體初始位置的時間復雜度為O(nd)，根據(jù)初始位置生成適應度值的時間為f(d)，基于t-分布擾動策略的全局搜索：Levy飛行生成步長的時間為ξ2，產(chǎn)生t-分布隨機數(shù)的時間為ξ3，根據(jù)當前位置產(chǎn)生下一代的時間為ξ4；基于變異策略的局部搜索：產(chǎn)生隨機數(shù)的時間為ξ5，計算隨機變異算子的時間為ξ6，根據(jù)當前位置產(chǎn)生下一代的時間為ξ7.由新位置生成新適應度值的時間為f(d).

全局尋優(yōu)過程的時間復雜度為:

(12)

局部尋優(yōu)過程的時間復雜度為:

(13)

假設所得到的新適應度值與當前適應度值進行比較的時間為μ2，經(jīng)過比較，如果新適應度值更好，需要替換當前適應度所需時間為μ3，所得到的新適應度值與當前最優(yōu)值進行比較的時間為μ4，如果需要替換當前最優(yōu)值所需時間為μ5，則算法總的時間復雜度為:

(14)

4 實驗仿真與結果分析

4.1 實驗設計

為了驗證本文所提出的tMFPA算法的有效性，以求最小值為例，用7個經(jīng)典性能測試函數(shù)對基本花授粉算法、粒子群算法、蝙蝠算法和本文改進的算法進行MATLAB實驗仿真對比.表1列出了7個函數(shù)的空間維度、搜索范圍、最優(yōu)解.為了降低算法隨機性對實驗性能的影響，以30次獨立實驗的平均值作為評估算法尋優(yōu)性能和收斂性能的最終結果.實驗時各種算法的參數(shù)為：FPA算法參數(shù)：轉換概率p=0.8，λ=1.5；PSO算法參數(shù)：c1=c2=2，w=0.9，vmax=1；BA參數(shù)：A=0.25，r=0.5，alf=0.95；本文改進tMFPA算法參數(shù)：轉換概率p=0.8，λ=1.5.

表1 測試函數(shù)Table 1 Test functions

4.2 實驗結果與分析

為了驗證本文提出的tMFPA算法的性能，分析算法在低維、高維情況下的尋優(yōu)能力和收斂速度，同時排除實驗結果的偶然性，仿真實驗的每種算法獨立運行30次，最大迭代次數(shù)設為2000次.

4.2.1 低維下的性能測試

通過在7種測試函數(shù)上進行仿真實驗，比較4種算法的收斂能力和尋優(yōu)能力.仿真測試中，種群數(shù)量統(tǒng)一設置為40，維度設為30.表2給出了4種算法在不同測試函數(shù)下的平均值和標準差.同時，為了更直觀地了解算法的有效性，對比4種算法的尋優(yōu)性能，圖2給出了它們在不同函數(shù)上的收斂曲線對比圖，同時為了便于觀察，橫坐標為普通坐標軸，縱坐標為對數(shù)坐標軸.

表2 4種算法的迭代尋優(yōu)結果Table 2 Iterative optimization results of 4 algorithms

根據(jù)表2中的實驗數(shù)據(jù)和圖2的迭代曲線，分析如下：

由表2數(shù)據(jù)可以看出，在規(guī)定迭代次數(shù)下，tMFPA算法能找到Sphere、Rastrigin、Rosenbrock、Griewank、Schwefel 2.22和Alpine函數(shù)的理論最優(yōu)值，找到的平均值為全局最優(yōu)值，而FPA、PSO和BA對這些函數(shù)尋優(yōu)的效果都不明顯.Ackley函數(shù)較復雜，很難找到其理論最優(yōu)值，從表2的實驗數(shù)據(jù)看出，tMFPA最終收斂到10-16的精度，與其他3種算法相比，提升了14個左右的數(shù)量級.從圖2(a)-圖2(e)和圖2(g)可以看出其他3種算法會較早的陷入局部最優(yōu)，例如，在對Griewank函數(shù)尋優(yōu)時，由圖2(d)可以看出，PSO和BA與FPA相比具有一定的優(yōu)越性，能夠逐漸跳出局部最優(yōu)，但是出現(xiàn)了尋優(yōu)停滯的現(xiàn)象；在對Alpine函數(shù)進行尋優(yōu)時，其他3種算法在200代左右陷入局部最優(yōu)之后，一直無法跳出.而從圖2(a)-圖2(e)和圖2(g)可以看出tMFPA算法能夠以更快的速度收斂找到全局最優(yōu)值，其中，對Sphere函數(shù)尋優(yōu)時在300代左右找到了理論最優(yōu)值；對Rastrigin函數(shù)進行尋優(yōu)時，tMFPA表現(xiàn)出了良好的競爭優(yōu)勢，收斂速度明顯加快，并能在30代以內找到理論最優(yōu)值；對Rosenbrock函數(shù)尋優(yōu)時，tMFPA能夠朝向正確的方向以很快的速度收斂到全局最優(yōu)值，并且在250代左右找到理論最優(yōu)值；對Griewank函數(shù)尋優(yōu)時，在20代左右找到理論最優(yōu)值；對Schwefel 2.22函數(shù)和Alpine函數(shù)尋優(yōu)時，tMFPA算法即使陷入局部最優(yōu)值，也能迅速跳出，并在600代左右找到了全局最優(yōu)值.但是在對Ackley函數(shù)尋優(yōu)時，從圖2(f)可以看出，F(xiàn)PA、PSO和BA較早的陷入局部最優(yōu)，而tMFPA在迭代初期能夠迅速跳出局部最優(yōu)，但是還是在50代左右陷入局部最優(yōu)值.

圖2 4種算法的尋優(yōu)迭代曲線Fig.2 Optimal iteration curves of four algorithms

從上述分析可以看出，在兩種策略的共同作用下，tMFPA算法的尋優(yōu)精度明顯高于FPA、PSO和BA這3種對比算法，而且收斂速度和穩(wěn)定性更好.

4.2.2 高維下的性能測試

通過在7種測試函數(shù)上進行仿真實驗，比較tMFPA算法和FPA算法的收斂能力和尋優(yōu)能力.仿真測試中，維度分別設為50和100.表3給出了2 種算法在不同維度、不同測試函數(shù)下的平均值及標準差.根據(jù)表3可知，除Ackley函數(shù)外，其他函數(shù)在高維下仍可以尋優(yōu)成功，證明tMFPA算法在對高維測試函數(shù)進行優(yōu)化時同樣具有良好的效果.

由表3的高維實驗數(shù)據(jù)可以看出，維度從50維變化到100維時，除Ackley函數(shù)外，對于其他函數(shù)的尋優(yōu)，tMFPA算法總能找到理論最優(yōu)值，而且找到的平均值是理論最優(yōu)值，但是FPA在這7個測試函數(shù)中都無法求解到理論最優(yōu)值，表現(xiàn)出改進算法tMFPA在高維條件下優(yōu)越的尋優(yōu)性能.

表3 不同維度下的尋優(yōu)精度結果Table 3 Optimization accuracy values in different dimensions

從分析中可知，tMFPA算法在高維條件下的尋優(yōu)精度和收斂速度明顯優(yōu)于FPA算法，這主要是因為在全局搜索過程中加入了t-分布擾動策略，擴大了搜索空間，幫助算法跳出局部最優(yōu)，加快收斂速度，同時在局部搜索過程中加入了差分變異策略，并引入小概率策略，增強了種群的多樣性，使得解的多樣性得到提高.

綜上，tMFPA算法在30、50和100維條件下，整體上都表現(xiàn)出較好的尋優(yōu)性能，而且隨著維度的增加，tMFPA不受其影響，在高維條件下，也能表現(xiàn)出較好的收斂性能和尋優(yōu)性能.

4.2.3 本文改進算法與其他文獻中改進算法進行比較

為了進一步體現(xiàn)tMFPA算法的優(yōu)越性，本文利用tMFPA算法和文獻[10]的mgFPA算法、文獻[11]的MFPA算法對5個測試函數(shù)尋優(yōu)，并對尋優(yōu)結果進行對比，結果見表4.表4列出了3種算法在5個測試函數(shù)下的平均值、最優(yōu)值和標準差.其中，維度統(tǒng)一設為30，種群規(guī)模n=40，最大迭代次數(shù)為1000次，轉換概率p=0.8，其他改進算法的參數(shù)設置與參考文獻相同，每種算法獨立運行30次，實驗數(shù)據(jù)取小數(shù)點后2位.圖3為tMFPA算法與其他改進FPA算法的尋優(yōu)迭代曲線，其中縱坐標為適應度值取以10為底的對數(shù).

表4 3種改進算法的迭代尋優(yōu)結果對比Table 4 Comparison of iterative optimization results of three improved FPA algorithms

圖3 tMFPA與其他改進算法的尋優(yōu)迭代曲線Fig.3 Optimal iteration curves of tMFPA and other improved FPA

由表4可知，在對選取的5個測試函數(shù)尋優(yōu)時，tMFPA算法與mgFPA、MFPA相比，都有更好的尋優(yōu)精度.對比mgFPA和MFPA，除函數(shù)Ackley外，tMFPA算法在其他函數(shù)上找到的平均值、最優(yōu)值都為理論最優(yōu)值.mgFPA在函數(shù)Rastrigin和Griewank上找到的最優(yōu)值為理論最優(yōu)值，但是其找到的平均值與tMFPA相差較大，沒有找到理論最優(yōu)；在函數(shù)Ackley上找到的最優(yōu)值與tMFPA相同，但是找到的平均值比tMFPA算法低12個數(shù)量級.MFPA在函數(shù)Rastrigin、Rosenbrock和Griewank上找到的最優(yōu)值為理論最優(yōu)值，但是找到的平均值都不是理論最優(yōu)值.由此可證明，改進后的tMFPA算法具有更好的尋優(yōu)精度.

通過圖3(a)-圖3(e)可以直觀地看出，縱向觀察，在100次迭代內，tMFPA算法的收斂曲線始終位于mgFPA算法和MFPA算法收斂曲線的下方，說明在相同的迭代次數(shù)下，tMFPA算法具有更高的收斂精度；橫向觀察，在收斂精度相同的情況下，tMFPA算法具有更快的收斂速度.由圖3(a)-圖3(d)可以看出，tMFPA算法從迭代開始一直到結束都能快速跳出局部最優(yōu)，并最終找到了理論最優(yōu)值，而mgFPA算法和MFPA算法尋優(yōu)速度緩慢，最終陷入局部最優(yōu).由圖3(e)可以看出，tMFPA算法在迭代初期能夠迅速跳出局部最優(yōu)，但是還是在50代左右陷入局部最優(yōu)值，而且從表4可以得到，tMFPA最終收斂到10-16的精度，與其他兩種改進算法相比，提升了12個數(shù)量級.

5 結束語

針對FPA算法的缺點，本文在傳統(tǒng)花授粉算法的基礎上進行改進，將t-分布擾動策略、差分變異策略分別引入到全局尋優(yōu)機制和局部尋優(yōu)機制中，提出了t-分布擾動策略和變異策略的花授粉算法.全局尋優(yōu)過程中，在保留萊維飛行特征的同時，將種群中其他個體的信息引入到全局搜索更新機制中；局部尋優(yōu)過程中，引入具有兩個差分向量的變異策略和小概率策略.通過進行tMFPA算法低維情況下性能測試、高維情況下性能測試、3種改進算法對比3項實驗，結果證明，本文tMFPA算法相比于其他算法具有更強的競爭優(yōu)勢.