大規模優化問題的改進花朵授粉算法*

李 煜，鄭 娟，劉景森

1.河南大學 管理科學與工程研究所，河南 開封 475004

2.河南大學 商學院，河南 開封 475004

3.河南大學 智能網絡系統研究所，河南 開封 475004

1 引言

越來越多科學和工程應用問題由低維發展成高維，決策變量增多，計算量大，具有不確定性且一般為多目標復雜優化問題[1]。一般情況下，決策變量超過100個的函數優化問題被定義為大規模優化問題[2]，如大型電力系統、視頻數據處理、輸電網擴展規劃、大規模交通網絡的車輛路徑規劃等。優化問題的求解難度和維度息息相關，搜索空間和問題復雜度隨維度增加呈指數趨勢增大，找到最優解的概率呈指數下降，極易陷入“維數災難”，而且這些決策變量之間相互關聯，使得計算復雜度和求解難度進一步加大。

大規模優化問題具有非線性、不可微的特點，傳統梯度下降方法無法求解，目前的求解方法主要有兩種[3]：一是將維度分組的協同進化策略，基于降維思想分組求解分解后的低維簡單問題，后將各組低維解結合成高維解[4]；另一種不分組方法是利用群智能算法對優化問題整體求解。群智能算法基于種群迭代機制進行優化計算，具有潛在的并行性和分布式特點[5]，全局搜索能力優異，能有效求解復雜優化問題[6-7]。這種整體求解方法能克服分組策略“兩步向前，合并向后”的缺點[1]，如：賀桂嬌等[8]提出的改進人工蜂群算法（artificial bee colony algorithm with at-tractor，BAABC）求解高維復雜優化問題的優勢明顯，魯棒性很好。Binh等[9]提出改進布谷鳥搜索算法（improved cuckoo search，ICS）和混沌花朵授粉算法（chaotic flower pollination optimization algorithm，CFPA）求解多個無線傳感器的網絡區域覆蓋優化問題。改進算法在解決傳感器節點部署這個NP-Hard 問題時較其他算法具有時間優勢。黃光球等[10]構造的可全局收斂蝙蝠算法（bat algorithm，BA）能求解不同類型的大規模優化問題，而且收斂速度快。

花朵授粉算法（flower pollination algorithm，FPA）[11]是Yang 于2012 年提出的一種新型群智能算法。該算法參數少，易實現，易調節，尋優結構新穎，尋優能力良好，已在函數優化[12]、無線傳感網[9]、電力系統[13]、作業車間調度[14]、形狀匹配[15]、背包問題[16]等領域得到廣泛應用。國內外已有不少學者對其易陷入局部最優、尋優精度低、后期收斂速度緩慢等缺點進行了改進。將該算法與其他智能優化算法融合取得了不錯的效果：如Abdel-Raouf 等[17]將粒子群優化算法融入到花朵授粉算法中；Lenin 等[18]將混沌和聲算法與花朵授粉算法進行融合；Salgotra 等[19]提出了融合蝙蝠算法的BFP（bat flower pollination）算法。另外，Wang 等[20]認為維間干擾會減緩算法的收斂速度，影響求解質量，對解進行逐維改進并引入局部鄰域搜索策略；肖輝輝等[21]融合高斯變異和Powell法改善了算法的尋優能力。

本文使用花朵授粉算法整體求解大規模優化問題。采用反向學習策略增加種群多樣性，提高初始種群質量；為降低大規模優化問題的求解難度，降低算法迭代代價，避免維間干擾對算法收斂精度和速度的影響，設計了新的局部更新公式，發揮當代最優位置牽引作用，逐維動態改變配子相對受擾動程度和繼承程度，并接受更優的結果作為下次迭代基礎。這種新的避免維間干擾的方法很好地彌補了算法易陷入“維度災難”的缺陷，且與逐維更新評價方法相比，這種方法的時間代價具有明顯優勢。最優位置的牽引作用使得改進算法僅需3～5 個種群個體即可達到滿意的優化效果。15 個測試函數在3 種高維狀態100、1 000 和5 000 的數值仿真結果表明：相比于FPA、PSO（particle swarm optimization）[22]和BA，IFPA（improved flower pollination algorithm）的尋優精度高、收斂速度快、魯棒性強且適應度高，求解不同類型大規模優化問題時優勢明顯。

2 大規模優化問題描述

大規模優化問題用公式表示如下：

其中，X=[x1,x2,…,xD]為決策變量，其取值不同對應著優化問題的不同決策方案，D表示決策變量的個數（即問題維度），本文維度設定為100、1 000和5 000。

F(x)表示優化問題的目標函數，xi∈[xmin,xmax]表示邊界約束，xmax、xmin分別表示問題上下邊界。

3 花朵授粉算法

FPA 是模仿顯花植物授粉過程而設計的隨機全局優化算法。因花朵授粉對象的不同存在自花和異花兩種授粉方式。異花授粉是指相對較遠距離的不同株植物之間的授粉，該方式一般需要傳粉者，傳粉者的行為具有萊維飛行的特征，FPA 的全局授粉（尋優）階段模擬了此授粉過程。自花授粉是指在較近的距離內，相鄰花朵依靠非生物手段實現成熟花粉粒成功傳遞并能正常受精結實的過程，FPA將這種授粉方式稱為局部授粉（尋優）。

一株植物能開好多花，每個花朵有百萬甚至上億的花粉配子。為簡單模擬授粉過程，假設每株植物僅有一朵花，每朵花獨有一個花粉配子。那么，一朵花或一個花粉配子的位置序列剛好是優化問題的一個解。算法假設條件如下：

（1）生物異花授粉被看作全局授粉過程，該規則的數學表達式為：

其中，λ=3/2，Γ(λ)是標準的伽馬函數。

（2）非生物自花授粉即花朵的局部授粉，該演化機制的數學公式為：

其中，ε是均勻分布在[0,1]間的隨機數；代表同類植物的不同花朵的花粉，即種群的兩個隨機解。

（3）花的繁衍概率與花朵間的類似程度存在比例關系。

（4）由p∈[0,1]來動態控制局部和全局授粉的轉換。物理上的接近和風等自然因素的作用使得相鄰花朵更容易授粉成功，故局部授粉在整個授粉活動中占比較大，文獻[23]中已通過大量實驗證明p值取0.2最為合適。

下面的偽代碼描述了FPA的基本步驟：

4 改進的花朵授粉算法

4.1 基于反向學習的種群初始化

反向學習（opposition-based learning，OBL）策略[24]自2005 年出現以來，就經常作為智能優化算法的改進策略出現[25-27]，并衍生出透鏡成像反向學習策略[28]、正交反向學習[29]等。

反向學習策略基于對立點的定義：

定義1（對立點（opposite point））[26]假設在[Lb,Ub]上存在數x，則x的對立點為x′=Lb+Ub-x。那么，若p=(x1,x2,…,xd)為d維空間中的一個點，其中xi∈[Lbi,Ubi],i=1,2,…,d，則其對立點為p′=(x′1,x′2,…,x′d)，其中x′i=Lbi+Ubi-xi。

為說明反向學習初始化對種群多樣性和種群質量的影響，圖1（a）和圖1（b）分別給出了IFPA 求解Sphere 函數時反向學習前后種群個體分布情況。其中，綠色圓圈代表花粉位置，紅色圓點代表全局最優點。問題維度為3維，變量搜索空間為[-100,100]，種群數為5。

Fig.1 Initial distribution of pollen圖1 花粉初始化分布圖

圖1清楚地顯示，反向學習使花粉個體探索了更多的位置，增加了種群多樣性，反向學習后有更多的花粉接近全局最優點，提高了初始種群質量，為算法奠定了更好的迭代基礎。

4.2 逐維隨機擾動的局部開發

FPA 在全局搜索中采用Lévy 飛行機制，它的較大跳躍和隨機步長的不均勻性一定程度上能規避配子陷入局部最優點，使其全局探索能力優異[30]。圖2展示了50步Lévy飛行的情況。

Fig.2 A series of 50 consecutive steps of Lévy flight圖2 50步Lévy飛行

但局部開發能力相對不足，原因有以下兩點：

（1）配子更新不受任何因素引導，過于隨機，雖能增強配子的多樣性，但難以滿足精準開發的要求，也抑制了優化過程的收斂速度。為提高算法的求解精度，將帶有隨機性信息的與帶有確定性信息的當前最優位置g*處理求得的差分向量代替原擾動中的，發揮當代最優位置的牽引作用，避免較大的隨機性所帶來的低搜索效率和較低收斂速度等問題[31]。

理論上，為達到相同的求解效果，搜索空間越大、種群規模越多，種群更新的代價越大，因此能較好地求解低維問題的智能算法在高維問題求解中表現一般。而這種改進僅需要3～5 個種群個體就可以達到滿意的優化效果，這是因為在種群數量較少的情況下，改進擾動中的差分算子能夠更容易地牽引整個種群朝當前最優位置靠近，有效解決了算法求解大規模優化問題迭代代價大的問題，而且能夠使算法在迭代后期局部開發更加精準。

（2）局部更新過程過于平緩，缺乏跳動，易陷入局部最優，這主要歸因于該算法的更新機制。算法靠轉換概率p實現異花授粉和自花授粉的動態轉換，簡單易懂，易于執行，也能通過合理設置p值大概率地進行局部搜索，更加貼合現實。但是p值越小，進行全局搜索的概率越小，即使某次迭代選擇全局搜索，也不能保證恰好發生遠距離Lévy跳躍，配子初期可能逗留初始化位置附近，這種情況嚴重影響算法尋優精度和收斂速度。而且多維優化問題尤其是大規模優化問題維數之間的干擾也很大程度上影響著算法性能和解的質量。

原花朵授粉算法采用整體更新和評價策略求解，不能規避維間干擾現象[20]。Wang 等人為解決此問題提出逐維更新評價策略[20]，但是該更新方式時間代價大，雖然對有些函數求解的精度較高，但魯棒性并不好。本文為打破維間干擾問題，提出局部開發的逐維隨機擾動策略，借鑒螢火蟲算法[32]相對熒光亮度公式，設計逐維隨機相對繼承程度m和逐維隨機相對受擾動程度2-m，m的公式表達為：

其中，k為花粉配子的最大繼承程度，與原花朵授粉算法保持一致取值為1，表示對上代花粉位置完全繼承；2π 是花粉粒子繼承系數；|L(j)|是花粉粒子在第j維上的Lévy飛行距離。

由于每一維的Lévy 飛行距離不同，使得花粉個體的每一維不同程度地繼承上代信息，受到不同程度的擾動，解決了維間干擾問題，增加了種群多樣性，在當代最優位置的牽引作用下，最終提出的第j維的更新公式為：

該更新方式不僅解決了維間干擾問題，而且使得算法不會錯失Lévy 飛行的良好機制，如果較大跳躍配合全局搜索執行，自然可以提升算法全局尋優能力，如果較大跳躍配合局部開發執行，就可以使花粉個體受到更大的擾動影響（Lévy 飛行距離越長，2-m的值越大）。在迭代初期種群差異較大時，花粉個體能受到更大的擾動影響，遍歷更大的范圍，因此不管進行全局搜索還是局部搜索，都能保證算法初期花粉個體的跳躍能力，提高算法初期的迭代質量和全局尋優能力，有效解決算法易陷入局部最優的問題。

被更新的花粉個體如果更優，就接受它并將它作為下代更新的基礎，否則就舍棄該更新解，保持之前的迭代基礎。局部開發的逐維隨機擾動策略具體如算法1所示。

綜上，IFPA優化流程如圖3所示。

Fig.3 Flow diagram of IFPA圖3 IFPA流程圖

4.3 花粉粒子多樣性分析

為模擬改進算法的尋優過程，仍以Sphere 函數為例，展示花粉粒子反向學習初始化、迭代10 次、50次、100次、200次和500次后的位置分布，如圖4所示。為便于分析花粉粒子的多樣性，設置種群規模為50。

從圖4 可以看出，隨著迭代次數的增加，花粉個體以較快的收斂速度朝全局最優解靠近。為分析全局最優解附近的花粉多樣性，將50代、100代、200代和500代的局部放大圖展示為圖5所示。

Fig.4 Pollen iteration graph圖4 花粉迭代分布圖

Fig.5 Partial enlarged detail圖5 局部放大圖

從圖4 和圖5 可以看出，隨著迭代次數的增加，花粉離全局最優解的距離越來越近，求解精度越來越高，但是花粉種群并沒有趨同，Lévy飛行的較大跳躍和隨機步長的不均勻性賦予決策變量的不同擾動，使得種群多樣性良好，花粉個體在迭代后期依然較為均勻地分布在全局最優解附近。

5 數值實驗與分析

5.1 測試函數與性能指標

為全面客觀地評價IFPA求解大規模復雜優化問題的性能，選取15 個不同類型的測試函數[5,33]在3 種高維狀態下進行測試。f1～f9為高維單峰函數，可測試算法的收斂速度和尋優精度，其中f5有非凸病態特點，算法在對其優化過程中很容易陷入局部極小；f10～f15是高維多峰函數，解空間中分布著大量局部極小點，尋優過程中極易陷入局部最優，極難找到全局最優解，可有效測試算法跳離局部極值的能力及全局收斂性能，f10和f13是典型代表。測試函數的具體特征如表1所示。

本文設定結果精確度（accuracy，AC）和尋優成功率（successful ratio，SR）來評價算法性能。AC反映算法迭代結果和測試函數理論最優值的接近程度。若一個測試函數的理論最優值是Xopt，迭代結果為Sbest，則精確度為AC=|f(Sbest)-f(Xopt)|，本文設定AC<0.000 1即稱此次運行尋優成功，收斂到全局最優解；SR 即多次實驗中算法收斂到問題全局最優解的比例，若總實驗次數為z，全局最優解被收斂到的實驗次數為z′，SR=z′/z×100%。

Table 1 Benchmark functions表1 基準測試函數

5.2 實驗環境及參數設置

為客觀評價IFPA 處理大規模優化問題的性能，將其與經典的PSO、BA 和FPA 進行對比。在每次運行中，將迭代1 000次作為這些算法的終止準則。為防止偶然性誤差，產生有統計學意義的結果，對每個函數獨立運行30 次，所有實驗都在相同的條件下進行，并記錄結果中的均值和標準差。種群數統一設為5，其他參數設置如表2所示。

基于上述參數設置，分3 種維度100、1 000 和5 000 進行仿真實驗，實驗筆記本操作系統為Win-dows10，主頻1.6 GHz，CPU 為Intel Core i5-8520，內存8 GB，使用Matlab R2014a實現編程。

Table 2 Parameter settings of each algorithm表2 各算法參數設置

5.3 尋優精度分析

15個測試函數100、1 000和5 000維的實驗結果如表3 所示，4 種算法中的最好結果加粗表示。從表3中的統計結果可知，除f14外，本文提出的IFPA在各個維度下的求解精度均優于其他3種算法，尋優精度大幅提高，以極高的尋優成功率收斂到了f1～f4、f6、f8、f10～f13這10 個函數的全局最優解，并能收斂到f3、f10和f13的理論最優值，而3種對比算法對15個函數的尋優成功率全為0。

Table 3 Simulation results of different functions表3 不同函數的仿真結果

續表

IFPA 在3 種高維狀態下次次都能收斂到f3、f10和f13的理論最優值。IFPA 對函數f1、f2、f4、f6、f8、f11、f12的尋優精度比對比算法中的最好結果提高了17～69個數量級。

3 種對比算法對f6的求解精度隨維度升高變化極大，特別是PSO 和BA，在1 000 和5 000 維時無法對解空間進行任何有效搜索的概率高達93.4%～100%，魯棒性很差，而IFPA 的收斂精度依然能達到10-24以上并且變化極小。

IFPA 對f7、f9和f15的求解結果已較接近理論最優值。IFPA對f7、f9的求解精度至少比對比算法提高了6、4個數量級。IFPA對f5的求解精度比對比算法提高了4～8 個數量級，對f14的求解精度也提高了0～16個數量級。

IFPA不但尋優精度高，魯棒性也強。除f14的標準差隨維度升高變化稍大以外，另14 個函數的標準差極小且基本不隨維度改變，求解結果穩定，證明了IFPA 的求解性能基本不受維度和函數類型的影響，與其他3 種算法相比優勢突出，成功克服了“維數災難”問題，適合處理大規模優化問題。

5.4 收斂曲線分析

算法跳出局部極值的能力和收斂速度都可通過適應度收斂曲線直觀顯現。圖6 給出了4 種算法1 000 維下優化8 個測試函數的適應度收斂曲線，所有收斂曲線都是對應算法30 次獨立運行的平均值。除f2、f11、f12和f13外，其他函數的目標函數值取以10為底的對數。

圖6 的收斂曲線清楚地顯示，較3 種對比算法，IFPA收斂速度更快，尋優精度更高，跳出局部極值的能力更強。從圖6（c）、圖6（e）和圖6（h）中可以看出，IFPA 可分別在100、400 和300 代左右收斂到f3、f10和f13的理論最優值。IFPA對f6的優化效果極好，無法看到圖6（d）中BA和PSO的收斂曲線，是因為這兩種算法對f6搜索不到任何有效解，而IFPA對此函數求解精度依然很高。從圖6（b）、圖6（f）～圖6（h）可以看出，4種算法均有陷入局部最優的情況，其中BA在迭代初期就易陷入局部最優，PSO和FPA幾次陷入局部最優，而IFPA的收斂曲線較為光滑，陷入局部最優的次數偏少，收斂速度也明顯快于其他算法。

Fig.6 Convergence curve of 4 algorithms for different functions in 1000 dimensions圖6 1 000維下求解不同函數的4種算法的收斂曲線

高維狀態下，4 種算法中FPA 收斂速度較快，但求解精度偏差；PSO算法的收斂精度雖然是3個對比函數中最好的，但其收斂速度卻是4 個算法中最慢的，且容易陷入局部最優；IFPA 的全局優化能力很強，不但收斂速度快，尋優精度高，而且不易陷入局部最優；BA表現最差。以f12的收斂曲線為例，IFPA迭代50 代左右求解精度已非常高，FPA 雖然前期收斂較快，但1 000次迭代后尋優結果僅在1 300左右，離函數的理論最優解相差很遠，雖然PSO 的最終求解結果比FPA 更優，但其收斂速度很慢，并且在70、130、200 代左右幾次陷入局部最優，BA 不管在求解精度上還是收斂速度上都是最差的。

5.5 兩種改進策略的有效性分析

為了分析兩種改進策略對算法性能的影響，從表1 中選取了7 個能代表尋優精度不同提高程度的測試函數在100 維下進行數值實驗，將IFPA 與僅采用反向學習策略的FPA算法（記為OFPA）、僅采用逐維隨機擾動的局部開發策略的FPA 算法（記為DFPA）和FPA 進行比較，算法的參數設置與5.2 節相同。表4給出了4種算法的測試結果比較，最好結果加粗表示，其中T是30 次獨立運行的總時間（單位：s），B、M、W、S分別表示最優值、優化均值、最差值和標準差。

Table 4 Comparison of test results of 4 algorithms(D=100)表4 4種算法的測試結果比較（D=100 維）

由表4 的比較結果可知，OFPA 提高了算法的求解精度和魯棒性，較FPA的求解精度更高，且不增加求解時間。例如，OFPA 在維持運行時間的前提下，僅通過反向學習初始化，對f6的求解精度就提高了4個數量級；對f9求得的最優值的精度只比IFPA低了2 個數量級。這說明反向學習初始化確實可以充分搜索解空間，保留更多的優良個體，為算法奠定高質量迭代基礎，而且IFPA 的求解精度普遍比DFPA 高也證實了反向學習初始化的作用。

采用逐維隨機擾動策略設計的局部更新方式是IFPA性能改進的有效算子，DFPA收斂到了f10和f13的理論最優值，使f1、f6、f9、f11、f12的求解精度分別提高了58、33、5、17、31 個數量級，且求解結果穩定，算法穩定性強。DFPA 求解單峰函數的時間代價大概為FPA 的1.5～2.1 倍，求解多峰函數的時間代價為FPA 的1.3 倍左右，很好地平衡了精度提高和時間代價兩方面。

6 結束語

為有效處理大規模優化問題，本文用反向學習策略提高FPA 初始種群質量，在局部開發階段采用逐維隨機擾動策略對花粉個體進行優化，打破了維間干擾，降低了大規模優化問題的求解難度，擴大了花粉受擾動的程度，提高了算法的全局尋優能力，并發揮當代最優位置的牽引作用，減少了算法迭代代價，有效解決了FPA收斂精度低、易陷入局部極值和“維數災難”等問題，大大提高了算法求解大規模優化問題的性能。在100、1 000 和5 000 的高維狀態下，IFPA的求解精度、收斂速度、魯棒性、對不同類型測試函數的適應性等都明顯優于FPA、PSO和BA，15個測試函數的最好結果基本全部由IFPA 求得，且求解精度基本不受維度影響。在今后的研究工作中，考慮將分組策略應用其中，進一步提高算法性能；細致研究參數p如何動態變化能使算法更優；將改進算法應用于實際工程問題。