李文超， 賀興時(shí)， 賀飛躍， 楊新社

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

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

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

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

1 基本花授粉算法

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

1）生物異花授粉是帶花粉的傳播者通過(guò)Levy飛行進(jìn)行全局授粉的過(guò)程；

2）生物自花授粉是一個(gè)局部授粉過(guò)程；

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

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

異花授粉過(guò)程定義如下：

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

其中：λ=1.5；Γ(λ)為標(biāo)準(zhǔn)的伽馬函數(shù)；s為移動(dòng)步長(zhǎng).

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

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

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

2.1 基于佳點(diǎn)集理論的種群初始化

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

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

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

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

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

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

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

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

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

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

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

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

2.3 高斯變異自花授粉機(jī)制

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

續(xù)表

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

實(shí)驗(yàn)環(huán)境如下：CPU 為i7-10750H 2.60 GHz，運(yùn)行內(nèi)存8 GB，操作系統(tǒng)Windows10，編程環(huán)境Matlab R2021a. 所有的測(cè)試函數(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對(duì)11個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果如表3～13. 其中，std為解的標(biāo)準(zhǔn)差、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)解和平均值可以反映算法的收斂精度和搜索能力. 通過(guò)表3～7的結(jié)果對(duì)比分析可得，IFPA、FPA、EHO 和PSO在求解高維非旋轉(zhuǎn)多模態(tài)函數(shù)的時(shí)候，均陷入局部最優(yōu)，難以跳出局部最優(yōu)，導(dǎo)致優(yōu)化效果差.而改進(jìn)的AGFPA算法，引入佳點(diǎn)集理論初始化種群，并使用振蕩的自適應(yīng)概率控制局部搜索和全局搜索的平衡，用高斯變異自花授粉公式替換隨機(jī)搜索公式，使算法的收斂精度大大提高. 特別是f2、f3和f5均達(dá)到理論值. 通過(guò)表8～12對(duì)比分析可得，AGFPA算法在高維單峰函數(shù)上均搜索到理論最優(yōu)值，而其他四種算法沒(méi)有獲取到理論最優(yōu)值，這說(shuō)明AGFPA算法具有較強(qiáng)的搜索單峰函數(shù)的能力. 基于維度的增加，IFPA、FPA求解精度變差，這說(shuō)明算法對(duì)維數(shù)比較敏感. 通過(guò)表13分析可得，AGFPA、IFPA、FPA、EHO和PSO算法均可以解決低維函數(shù)優(yōu)化問(wèn)題.

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

3.4 算法收斂分析

為了更加直觀地分析AGFPA算法的性能，上述11個(gè)測(cè)試函數(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

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

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

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

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

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

3.6 統(tǒng)計(jì)檢驗(yàn)

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

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

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

4 結(jié)語(yǔ)

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