自適應(yīng)高斯變異花授粉算法

李文超， 賀興時， 賀飛躍， 楊新社

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

人類在研究領(lǐng)域和工程領(lǐng)域面臨眾多亟待解決的優(yōu)化問題. 傳統(tǒng)優(yōu)化算法在解決這些問題時，求解精度和收斂速度等方面均不能滿足實際需求且耗時、耗力. 因此，學(xué)者們開發(fā)了大量的自然啟發(fā)式優(yōu)化算法，如粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）［1］、象群游牧算法（Elephant Herding Optimization）［2］等.

最近，英國學(xué)者Yang［3］受自然界植物花朵授粉過程的啟發(fā)提出了一種新穎的元啟發(fā)式算法——花授粉算法（Flower Pollination Algorithm，F(xiàn)PA）. 基于FPA的實現(xiàn)簡單、參數(shù)少、易調(diào)節(jié)等優(yōu)點，F(xiàn)PA已廣泛用于函數(shù)優(yōu)化［4］、移動機器人路徑規(guī)劃［5］、車間調(diào)度［6］等領(lǐng)域. 然而與其他仿生優(yōu)化算法類似，基本FPA也存在收斂精度低、速度慢、維數(shù)敏感等問題［7］. 為此，國內(nèi)外學(xué)者針對基本花授粉優(yōu)化算法進行諸多研究，主要體現(xiàn)在以下3個方面：①初始種群的改進. 由于群智能優(yōu)化算法的初始種群為以后進化過程提供了初始猜想，所以初始種群質(zhì)量的好壞影響了算法收斂速度和收斂精度等. 基本FPA算法采用隨機的方式對種群進行初始化，導(dǎo)致種群分布不均，算法容易早熟. 針對這種缺陷，張水平和高棟［8］利用霍爾頓序列生成更加均勻的初始種群；寧杰瓊和何慶［9］認為Logistic 混沌映射可以使種群分布更加均勻. ②轉(zhuǎn)換概率的改進. 轉(zhuǎn)換概率可以調(diào)整FPA算法中全局搜索和局部搜索之間平衡［10］；Valenzuela等［11］利用模糊推理系統(tǒng)動態(tài)調(diào)整轉(zhuǎn)換概率，有助于算法跳出局部最優(yōu)；Liu等［12］將韋伯分布函數(shù)與迭代次數(shù)結(jié)合用于控制轉(zhuǎn)換概率，有助于全局搜索和局部搜索之間平衡；田海梅和徐勝超［13］根據(jù)迭代次數(shù)和步長因子調(diào)整轉(zhuǎn)換概率. ③搜索策略的改進. 汪海等［14］為了使搜索方向不斷靠近最優(yōu)值，引入時滯調(diào)整算子；陸克中等［15］采用量子搜索機制，將個體吸引到可能出現(xiàn)的任意位置，個體的隨機性增強了算法的全局搜索能力；肖輝輝等［16］提出將慣性權(quán)重的三角變異機制和精英變異融合組成新的局部搜索機制.

雖然花授粉有一定的改進，如收斂速度明顯加快，解的精度明顯提高，但是在精度和維數(shù)敏感問題方面仍有提升空間. 本文引入佳點集初始化種群的方法，解決種群分布不均的問題；然后，提出一種根據(jù)迭代次數(shù)和振蕩函數(shù)調(diào)整轉(zhuǎn)化概率的策略；最后分析了基本花授粉算法中的自花授粉公式的搜索能力，提出用高斯變異自花授粉公式引導(dǎo)算法精細搜索. 實驗結(jié)果表明新算法的改進策略有效.

1 基本花授粉算法

在自然界中，花朵授粉過程紛繁復(fù)雜. 如果過多地考慮花朵授粉的各個細節(jié)，就會導(dǎo)致計算資源的浪費且實用價值不大. 為了使算法簡單易行，該算法做如下理想化假設(shè)：

1）生物異花授粉是帶花粉的傳播者通過Levy飛行進行全局授粉的過程；

2）生物自花授粉是一個局部授粉過程；

3）花的常性可以被認為是繁殖概率和參與的兩朵花的相似性成比例關(guān)系；

4）轉(zhuǎn)換概率p0∈[0,1]控制著全局授粉和局部授粉之間的轉(zhuǎn)換.

異花授粉過程定義如下：

其中：X、分別表示第t+1代、第t代的解；g*為全局最優(yōu)解；L為步長，L服從Levy 分布，即

其中：λ=1.5；Γ(λ)為標準的伽馬函數(shù)；s為移動步長.

自花授粉模擬自然界中同種花之間近距離接觸，授粉過程定義如下：

其中：α∈[0,1]服從均勻分布；、為同種植物的不同花朵的花粉.

2 自適應(yīng)高斯變異花授粉算法（AGFPA）

2.1 基于佳點集理論的種群初始化

FPA從隨機初始化花粉配子開始尋優(yōu)，若存在一些在最優(yōu)解附近的花粉配子，則能夠提高算法的收斂和尋優(yōu)能力，反之則很難或者無法找到最優(yōu)解. 因此，通過初始化均勻的種群，才能使實際問題得到更好的解決. 華羅庚和王元［17］提出了佳點集理論，其定義如下：

本文通過引入佳點集理論，創(chuàng)建初始化種群公式，公式如下：

其中：Xi表示第i個花粉配子的位置；ub，lb分別表示解的上界和下界.

圖1是分別采用隨機方法和佳點集方法生成規(guī)模為50的二維初始化種群分布圖. 由圖可知，在相同點數(shù)下，佳點集產(chǎn)生的點比隨機產(chǎn)生的點更加均勻.

圖1 初始化種群Fig.1 Initial population

2.2 自適應(yīng)調(diào)整的轉(zhuǎn)化概率

根據(jù)文獻［10］可知，在迭代前期FPA 算法偏重于異花授粉，在迭代后期算法偏重于自花授粉. 當轉(zhuǎn)換概率p0為固定值時，不利于自花授粉與異花授粉之間的平衡. 針對該問題，文獻［18］提出了IFPA算法，該算法將固定概率p0增強為動態(tài)概率p1，公式如下：

其中：p1_min為最小概率；p1_max為最大概率；t為當前迭代次數(shù).

由圖2可知，IFPA算法的動態(tài)概率p1在200次迭代左右，由于p1較小，花粉配子側(cè)重于自花授粉過程，導(dǎo)致該算法在解空間中搜索不充分，易陷入局部最優(yōu). 為此，定義動態(tài)轉(zhuǎn)化概率pa如下：

圖2 IFPA算法概率p1 曲線分布Fig.2 Curve distribution of probability p1 of IFPA algorithm

其中：τ ∈[0 ,1] 服從均勻分布的隨機數(shù)；t、Niter分別表示當前迭代次數(shù)、最大迭代次數(shù)；pa_min、pa_max分別表示pa的最小值和最大值. 根據(jù)文獻［3］提供的參數(shù)可知，當轉(zhuǎn)換概率為0.8 時，F(xiàn)PA 算法的性能較高；根據(jù)文獻［19］可知，當轉(zhuǎn)換概率為0.2時，算法性能較高. 經(jīng)過深入分析后，設(shè)置pa_min為0.2，設(shè)置pa_max為0.8. 由圖3可知，當it∈[0,600]時，pa取值較大，AGFPA算法偏重于全局搜索，使得該算法可以對解空間進行充分搜索.當it∈[600,1000]時，pa取值相對較小，AGFPA算法偏重于局部搜索，使得該算法在解空間中進行精細搜索.

圖3 AGFPA算法概率pa 曲線分布Fig.3 Curve distribution of probability pa of AGFPA algorithm

2.3 高斯變異自花授粉機制

在FPA 算法中，自花授粉更新公式采用隨機的搜索方式進行局部開發(fā). 當算法進入后期時，種群差異較小(-g*≈0)，導(dǎo)致個體很難找到更優(yōu)的位置，因此削弱了算法精細搜索的能力. 因此，將高斯變異算子作為自花授粉更新公式，不僅增加種群多樣性，而且提高了算法續(xù)航能力. 同時高斯變異能以較大的概率產(chǎn)生較小的變異值，使得其在小范圍內(nèi)不易陷入局部最優(yōu). 高斯變異自花授粉公式如下：

其中：X，分別表示第t+1 代、第t代的解；ε∈[0 ,1] 服從均勻分布，N(0,1)服從標準正態(tài)分布. 式（7）表

示在原有花粉配子運動的基礎(chǔ)上，加入正態(tài)分布擾動項，有利于跳出局部最優(yōu)解.

2.4 自適應(yīng)高斯變異花授粉算法

為了提高花授粉算法的尋優(yōu)精度和穩(wěn)定性，克服該算法易陷入局部最優(yōu)的缺陷，利用佳點集理論初始化的種群，通過自適應(yīng)轉(zhuǎn)化概率調(diào)整自花授粉與異花授粉，提出自適應(yīng)高斯變異花授粉算法. 算法偽代碼如下：

①初始化參數(shù)，設(shè)定花粉種群規(guī)模N、最大迭代次Niter、轉(zhuǎn)換概率最大值pa_max和最小值pa_min；

②利用佳點集初始化花粉的位置，并計算適應(yīng)度值；

③記錄當前的全局適應(yīng)度最小值和最優(yōu)解；

④依據(jù)式（6）計算轉(zhuǎn)換概率pa；

⑤若條件（rand＜pa）成立，轉(zhuǎn)步驟⑥；否則，轉(zhuǎn)步驟⑦；

⑥全局授粉：根據(jù)式（1）更新子代花粉位置，并計算適應(yīng)度值；

⑦局部授粉：根據(jù)式（7）更新子代花粉位置，并計算適應(yīng)度值；

⑧計算全局適應(yīng)度最小值，并更新最優(yōu)解；

⑨若滿足終止條件，輸出全局最優(yōu)解；否則，轉(zhuǎn)至步驟④.

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

3.1 實驗設(shè)計

為了檢驗算法的性能，選擇11個標準的測試算法，其中包括多峰非旋轉(zhuǎn)高維函數(shù)f1～f5、單峰多維函數(shù)f6～f10和2維多峰函數(shù)f11. 函數(shù)的具體描述如表1所示.

表1 測試函數(shù)Tab.1 Test function

續(xù)表

3.2 測試環(huán)境和算法參數(shù)

實驗環(huán)境如下：CPU 為i7-10750H 2.60 GHz，運行內(nèi)存8 GB，操作系統(tǒng)Windows10，編程環(huán)境Matlab R2021a. 所有的測試函數(shù)維數(shù)為10、50和100，種群規(guī)模為25，最大迭代次數(shù)Niter=1000 . 算法參數(shù)設(shè)置如表2.

表2 算法參數(shù)設(shè)置Tab.2 Algorithm parameter setting

3.3 算法求解精度比較分析

AGFPA、IFPA、FPA、EHO、PSO對11個測試函數(shù)的實驗結(jié)果如表3～13. 其中，std為解的標準差、best為最優(yōu)解、mean為解的平均值、worst為最差解.

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

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

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

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

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

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

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

表10 f8(x) Sum of Different Power函數(shù)仿真結(jié)果Tab.10 Simulation results of f8(x)Sum of Different Power function

表11 f9(x) Sum square 函數(shù)仿真結(jié)果Tab.11 Simulation results of f9(x)Sum square function

表12 f10(x) Zakharov函數(shù)仿真結(jié)果Tab.12 Simulation results of f10(x)Zakharov function

表13 f11(x) Schaffer函數(shù)仿真結(jié)果Tab.13 Simulation results of f11(x)Schaffer function

最優(yōu)解和平均值可以反映算法的收斂精度和搜索能力. 通過表3～7的結(jié)果對比分析可得，IFPA、FPA、EHO 和PSO在求解高維非旋轉(zhuǎn)多模態(tài)函數(shù)的時候，均陷入局部最優(yōu)，難以跳出局部最優(yōu)，導(dǎo)致優(yōu)化效果差.而改進的AGFPA算法，引入佳點集理論初始化種群，并使用振蕩的自適應(yīng)概率控制局部搜索和全局搜索的平衡，用高斯變異自花授粉公式替換隨機搜索公式，使算法的收斂精度大大提高. 特別是f2、f3和f5均達到理論值. 通過表8～12對比分析可得，AGFPA算法在高維單峰函數(shù)上均搜索到理論最優(yōu)值，而其他四種算法沒有獲取到理論最優(yōu)值，這說明AGFPA算法具有較強的搜索單峰函數(shù)的能力. 基于維度的增加，IFPA、FPA求解精度變差，這說明算法對維數(shù)比較敏感. 通過表13分析可得，AGFPA、IFPA、FPA、EHO和PSO算法均可以解決低維函數(shù)優(yōu)化問題.

算法的標準差和最差解反映算法的魯棒性和跳出局部最優(yōu)的能力. 與其他算法相比，AGFPA 算法在11個標準測試函數(shù)的標準差最小，這說明算法比較健壯.

3.4 算法收斂分析

為了更加直觀地分析AGFPA算法的性能，上述11個測試函數(shù)的收斂曲線圖如圖4～14所示.

圖4 Ackley函數(shù)收斂曲線Fig.4 Convergence curves of Ackley function

圖5 Rastrigin函數(shù)收斂曲線Fig.5 Convergence curves of Rastrigin function

圖6 Griewank函數(shù)收斂曲線Fig.6 Convergence curves of Griewank function

圖7 Alpine函數(shù)收斂曲線Fig.7 Convergence curves of Alpine function

圖8 Powell函數(shù)收斂曲線Fig.8 Convergence curves of Powell function

圖9 Rotated Hyper-Ellipsoid函數(shù)收斂曲線Fig.9 Convergence curves of Rotated Hyper-Ellipsoid function

圖10 Sphere函數(shù)收斂曲線Fig.10 Convergence curves of Sphere function

圖11 Sum of Difference Power函數(shù)收斂曲線Fig.11 Convergence curves of Sum of Difference Power function

圖12 Sum square函數(shù)收斂曲線Fig.12 Convergence curves of Sum square function

圖13 Zakharov函數(shù)收斂曲線Fig.13 Convergence curves of Zakharov function

圖14 Schaffer 函數(shù)收斂曲線Fig.14 Convergence curves of Schaffer function

在圖中，橫坐標為算法的迭代次數(shù)t，縱坐標為算法的適應(yīng)度值的對數(shù). 從圖的曲線可以看出，F(xiàn)PA算法的收斂速度比較慢，收斂精度一般. 改進的AGFPA 算法不但有較快的收斂速度，而且有較好的收斂精度.除了f1和f4沒有搜索到理論最優(yōu)解，其他函數(shù)均搜索到理論解，這說明算法具有較強的搜索能力. 從圖4可以看出，算法后期仍有不斷下降的趨勢，這說明AGFPA算法仍具有持續(xù)優(yōu)化的能力，避免類似FPA算法及其他算法存在的早熟現(xiàn)象.

3.5 時間復(fù)雜度比較

使用策略的時間復(fù)雜度來衡量AGFPA、IFPA和FPA算法的時間復(fù)雜度，時間復(fù)雜度結(jié)果如表14所示.

表14 時間復(fù)雜度結(jié)果Tab.14 Time complexity results

由表14可知，無論從初始化策略來看，還是從轉(zhuǎn)換概率更新策略或者授粉過程策略來看，AGFPA、IFPA和FPA算法之間的時間復(fù)雜度不存在差異. 通過分析可知，AGFPA算法沒有增加算法難度，進而表明算法的可行性.

3.6 統(tǒng)計檢驗

Wilcoxon檢驗是一種非參數(shù)檢驗，用于判斷AGFPA算法與其他算法是否有顯著性差異. Wilcoxon檢驗假設(shè)H0：AGFPA算法性能和另外一種算法性能相同；H1：AGFPA算法性能優(yōu)于另外一種算法性能. 其結(jié)果顯示在表15中，其中，P表示檢驗結(jié)果、S表示顯著性判斷結(jié)果. 當P＜0.05 時，S顯示為“+”，表示當P>0.05時，AGFPA 算法優(yōu)于另外一種算法；S 顯示為“-”，AGFPA 算法與另外一種算法無差異. 當P顯示維“NaN”時，S顯示為“～”，表示無法進行顯著性判斷.

表15 Wilcoxon檢驗結(jié)果Tab.15 Wilcoxon test results

取每種算法在10個10維測試函數(shù)和1個2維函數(shù)上獨立運行30次的平均值進行秩和檢驗，從表15可以看出，AGFPA算法與FPA算法在函數(shù)f2、f6和f11上無法進行顯著性判斷；AGFPA算法與IFPA算法在函數(shù)f11無法顯著性判斷；AGFPA算法與PSO算法在函數(shù)f11無法顯著性判斷；在函數(shù)AGFPA算法在函數(shù)f4上弱于PSO算法. 對于其他函數(shù)P值均遠遠小于0.05且S均顯示為“+”. 說明AGFPA算法比IFPA、FPA、EHO和PSO更有顯著優(yōu)勢.

4 結(jié)語

針對基本花授粉算法在求解函數(shù)優(yōu)化問題時，存在收斂速度慢，精度低和維度敏感等問題，本文提出了自適應(yīng)高斯變異花授粉算法. 該算法為增加種群多樣性，引入佳點集理論；為了增加自花授粉和異化授粉之間轉(zhuǎn)換的靈活性，構(gòu)建了振蕩的自適應(yīng)概率pa；為了避免在后期類似其他算法出現(xiàn)的早熟現(xiàn)象，構(gòu)建了高斯變異自花授粉公式. 通過對11 個測試函數(shù)的仿真，并與IFPA、FPA、EHO 和PSO 對比分析，AGFPA 在求解低、高維函數(shù)優(yōu)化問題時，具有較好的收斂精度、較快的收斂速度和健壯的魯棒性. 下一步將研究AGFPA算法在約束優(yōu)化問題中的應(yīng)用，使其具有更大潛能.