段艷明，肖輝輝，林 芳

河池學院 計算機與信息工程學院，廣西 河池 546300

1 引言

花授粉算法（Flower Pollination Algorithm，F(xiàn)PA）[1]是由Yang提出的一種源于顯花植物花授粉的群體隨機優(yōu)化技術。其主要由全局授粉（全局搜索）和局部授粉（局部搜索）構成，且通過轉換概率 p能夠較好地解決探索和開發(fā)之間的平衡問題。由于花授粉算法概念簡單、容易實現(xiàn)及尋優(yōu)效率較高等優(yōu)點，從提出之日起，該算法得到眾多學者的關注，使其在許多領域獲得廣泛的應用[2-12]。FPA的尋優(yōu)性能主要受其授粉方式、進化策略以及參數(shù)p值的選擇影響。為了提高FPA的全局優(yōu)化能力，諸多學者對其進行了改進研究，對目前已出版的有關文獻梳理可知，當前國內外學者對其改進研究主要可以歸納為以下幾個方面。

一方面是對轉換概率 p調整策略和參數(shù)設置。在FPA算法中，關鍵參數(shù)p對該算法的尋優(yōu)性能具有較大的影響。為此，Valenzuela等[13]提出一種模糊邏輯花授粉算法，該算法通過模糊推理系統(tǒng)來調整轉換概率p的值，實驗結果顯示該策略能提高FPA算法解的質量，且其性能要優(yōu)于對比算法。Draa[14]對基本FPA算法中的轉換概率參數(shù)p的不同取值進行了豐富的定量分析實驗，得出當 p=0.2時，在絕大部分測試函數(shù)上，傳統(tǒng)的FPA算法性能表現(xiàn)最優(yōu)。Mahdad等[15]提出了一種新的自適應分割授粉算法來解決帶安全約束的安全優(yōu)化功率流問題，并取得較好的效果。在該算法中，作者把迭代過程分為3個階段，每個階段轉換概率p采用不同的計算公式，使其在進化過程中隨機地進行動態(tài)調整，采用此策略改善了FPA算法的性能。?ukasik等[16]對花授粉算法進行了詳細闡述并對關鍵參數(shù) p的取值進行了討論；算法在優(yōu)化單模態(tài)函數(shù)時，p的取值對優(yōu)化結果影響不大；而在求解復雜的多模態(tài)函數(shù)時，p在[0.5，0.8]之間取值比較好；最后針對FPA與PSO算法的尋優(yōu)性能進行了對比分析，實驗結果表明，PSO算法進化前期的收斂速度要優(yōu)于FPA算法，后期其收斂速度和個體差異性要差于FPA算法。

基上述可知，當前對參數(shù)p的研究，并沒有對其取值范圍進行探討，而p的取值范圍在運用自適應調整機制時，對算法的性能具有較大的影響。同時，目前雖已有文獻對p的取值進行動態(tài)調整策略研究，但在其動態(tài)調整過程中，沒有考慮適應度值的影響。在進化過程中，考慮種群個體的位置信息，有利于提高算法的優(yōu)化性能。針對上述存在的這些問題，本文將對p的有效取值范圍和自適應調整策略進行研究。

另一方面是融入其他機制的改進花授粉算法：在現(xiàn)有的眾多群智能算法中，各種算法都存在各自的優(yōu)缺點。如何把這些算法融合在一起，使其取長補短，構造超大規(guī)模的優(yōu)秀群智能算法，這是當前群智能算法研究的熱點。Zhou等[17]把精英反向學習機制引入到FPA算法全局搜索部分，增加種群的多樣性，擴展算法的探索領域；在局部搜索引入自適應貪婪策略，改善算法的局部搜索能力；同時采用了動態(tài)轉換概率方法。算法在收斂速度和計算精度等方面獲得了較好的改進。Chakraborty等[18]把差分算法（Differential Evolution，DE）融合到FPA算法中，首先利用DE算法優(yōu)化初始種群，優(yōu)化后的種群作為FPA算法的初始解；其次，為了增加算法的穩(wěn)定性，消除參數(shù)p對算法性能的影響，受粒子群的啟發(fā)，作者通過兩個動態(tài)權重參數(shù)把全局搜索和局部搜索進行整合。改進算法的全局優(yōu)化能力要優(yōu)于基本FPA算法。Draa[14]利用反向學習策略對FPA算法進行改進，提高FPA算法的求解精度，實驗結果表明該方法改善了FPA算法解的質量。

Kerta等[19]把蟻群算法與FPA算法進行融合，并用于實現(xiàn)電力追蹤以解決電力系統(tǒng)超載的監(jiān)視問題，識別出引起超載的主要原因；在IEEE 14路系統(tǒng)上驗證了該算法的有效性和可行性。Xu等[20]針對帶萊維飛行策略的FPA算法具有良好的探測能力，但存在較弱的開采能力的問題，把單純形法融入到FPA算法的局部搜索中以增強FPA算法的局部搜索性能；利用改進算法對混沌系統(tǒng)的參數(shù)進行優(yōu)化，取得較好的結果，與對比算法相比也具有一定的競爭力。

上述改進策略雖然在一定程度上改善了基本FPA算法的優(yōu)化性能，但這些改進措施在解決高維多峰復雜優(yōu)化問題時效果仍然不太理想，而且一些改進舉措改變了FPA算法的進化思想，一些改進機制較大地增加了算法的時間復雜度。

通過對FPA深入分析發(fā)現(xiàn)，F(xiàn)PA的優(yōu)化性能主要取決于以下3個方面：（1）探測未知領域的能力；（2）防止早熟的能力；（3）快速收斂的能力。同時，由于FPA的全局搜索策略中的Lévy機制和最優(yōu)個體策略相互制約，削弱了其全局搜索能力；p取固定值，影響了FPA的性能；在局部授粉部分，F(xiàn)PA利用隨機變異策略隨機產生新的個體，使得其收斂速度慢。

為此，本文提出一種新授粉方式的花授粉算法（Flower Pollination Algorithm with New pollination Methods，NMFPA）。NMFPA采用慣性權重、兩組隨機個體差異矢量和Lévy機制構建新的全局搜索策略，提高算法的全局探索能力；利用信息共享機制、FPA/rand/1和FPA/best/2融合的局部搜索策略，增強算法的局部開發(fā)能力；運用基于高斯變異的最優(yōu)個體引導策略，提高算法的搜索速度和精度。利用非均勻變異機制增加種群的多樣性，有效防止算法早熟，提升算法的全局優(yōu)化性能。同時，為了增強算法更具靈活性和健壯性等性能，本文對參數(shù)p的取值采用一種新的動態(tài)調整策略。

通過NMFPA算法對4類經典測試函數(shù)的求解，實驗結果驗證了其具有良好的收斂能力和競爭力。同時，為了進一步檢驗NMFPA算法求解實際工程問題時，其優(yōu)化能力是否同樣表現(xiàn)良好，利用NMFPA算法對置換流水車間調度問題進行求解，仿真實驗結果顯示，NMFPA算法的優(yōu)化能力與對比算法相比，也具有一定的優(yōu)勢。

2 花授粉算法

2.1 FPA存在的不足

花授粉算法作為一種新型群智能優(yōu)化算法，運用參數(shù) p對算法進化過程中的全局授粉（全局搜索）和局部授粉（局部搜索）之間的相互轉換進行了動態(tài)控制，較好地解決了勘探與開采之間的平衡問題，且該算法的勘探部分利用了萊維飛行策略，使得其具有較強的探索能力。該算法的核心是由基于Lévy飛行的隨機游動（全局授粉）和偏好隨機游動（局部授粉）構成，其仿生機理闡述見文獻[21]。但由于其搜索方程等方面存在一些不足，使得該算法存在以下缺點：

缺點一：FPA算法在全局授粉部分利用超級花朵（最優(yōu)個體g*）信息來引導其他花朵的進化方向，加快算法的收斂速度。但在優(yōu)化具有多個局部最優(yōu)值的高維復雜多模態(tài)問題時，如果最優(yōu)個體一旦陷入搜索空間中的一些局部最優(yōu)，則其他個體因最優(yōu)個體的吸引迅速移向最優(yōu)個體所在的局部最優(yōu)位置，的值趨近于0，這使得，造成種群中的個體位置無法得到更新，所有個體都將停滯進化而無法跳出局部最優(yōu)，算法的全局搜索能力嚴重削弱，以至于算法無法找到全局最優(yōu)解。

缺點二：從FPA局部授粉方式可知，新個體的產生是在現(xiàn)有個體的基礎上加上兩個隨機個體的差分向量。在算法進化過程中，隨著演化不斷深入，種群收斂到一個小范圍內，個體之間的差異性越來越小，并且由于和是隨機選取的兩個個體，如果兩個個體的位置非常近，則的值接近于0，這使得種群很難再探索到更好的個體位置，算法的局部搜索能力下降，尤其在求解復雜的高維多模態(tài)問題時，這種情況更為突出。另外，F(xiàn)PA算法的局部授粉部分采用了標準差分進化（DE/rand/1）算法的隨機變異思想，這導致算法的收斂速度慢。

缺點三：依據(jù)FPA算法思想，算法的每次迭代都是根據(jù)轉換概率 p的值隨機地選取全局搜索或者局部搜索，這導致算法丟失了進化方向和遠離全局最優(yōu)解，影響了算法的優(yōu)化性能。

2.2 參數(shù)p對FPA性能影響分析

參數(shù) p是FPA算法的關鍵參數(shù)，為了研究 p的取值范圍對FPA性能影響的敏感性，本文取表1中的部分測試函數(shù)進行實驗，實驗結果如圖1所示，限于篇幅，僅給出了四個代表性函數(shù)（分別來自四類不同的函數(shù)）的取值變化圖。

表1 本文使用的實驗測試函數(shù)

圖1 p在4個函數(shù)上的取值變化圖

實驗參數(shù)設置：p初值0.0，步長0.01，終值1.0，函數(shù)維數(shù)D=30，種群50，迭代次數(shù)1 000；為防止偶然性帶來的實驗誤差，對每個 p值，獨立運行30次，并計算其平均值。

從圖1中可知：

（1）在優(yōu)化四類不同的函數(shù)時，F(xiàn)PA的性能對 p的取值是敏感的。

（2）p=0.0或1.0時，對于大部分函數(shù)而言，其對應的適應度值是最差的。

（3）p在[0.2，0.9]之間取值，F(xiàn)PA的性能較好。

（4）p的取值依賴于不同的優(yōu)化問題，p取固定的值，不利于提高FPA算法解的質量。

3 新授粉方式的花授粉算法

從花授粉算法的仿生原理可以發(fā)現(xiàn)，該算法的收斂能力受到其搜索方程、演化策略和參數(shù)設置的影響。本文對其搜索方程和進化機制進行分析，挖掘其存在的不足，為其改進提供理論依據(jù)；同時分析參數(shù)p的取值是否對算法的性能具有敏感性，為今后求解優(yōu)化問題時，參數(shù)的設置和調整策略提供參考。下面從轉換概率p、搜索方程和進化策略三個方面對FPA算法進行改進，提高其優(yōu)化性能。

3.1 自適應調整的轉換概率p

從2.2節(jié)可知，參數(shù) p對FPA性能的影響較大，且其取值依賴于求解問題。同時，依據(jù)FPA算法的仿生原理可知，若算法中的參數(shù)p在優(yōu)化過程中取固定的值，如果 p取值較大，算法側重于全局搜索，導致算法收斂速度慢，如果p取值較小，算法容易陷入局部極值，甚至找不到最優(yōu)值，從而影響算法的全局優(yōu)化能力。針對該問題，本文對p采用自適應調整策略，其計算公式為：

其中，轉換概率 p的取值范圍為 p∈[0.2，0.9]，fmin,t和fmax,t分別為第t代種群中最小適應度值和最大適應度值，fi,t為當前個體的適應度值，N_iter為最大迭代次數(shù)，t為當前迭代次數(shù)，pmin是參數(shù) p的最小值，pmax是參數(shù)p的最大值。

從公式（1）可知：

（1）p的取值是動態(tài)自適應變化的，且其取值同時考慮了迭代次數(shù)和種群個體的適應度值的作用。

（2）在進化初期，p的值較大，算法側重于全局搜索，擴大算法搜索范圍，使種群中的個體更靠近最優(yōu)解，隨著演化的深入，p的值越來越小，使算法傾向局部精細化搜索，有利于算法找到最優(yōu)值。

3.2 帶慣性權重的新全局授粉方式

依據(jù)FPA算法的仿生原理，F(xiàn)PA算法在全局授粉時，利用Lévy飛行和最優(yōu)個體策略對種群中的個體同時施加影響，通過最優(yōu)個體引導種群中的其他個體進行探索，有利于提高算法的性能，但在進化后期，由于最優(yōu)個體對其他個體的吸引，使得種群個體具有強烈的趨同性，即減弱了種群個體的差異性。同時，智能算法中通常是利用最優(yōu)個體策略提高算法的局部搜索能力[22]，采用Lévy飛行機制改善算法的全局搜索能力，而將兩種策略融入到一起，勢必引起相互抵觸，影響算法的全局優(yōu)化能力。另外，在FPA算法演化后期，由于種群個體的多樣性快速喪失而使得FPA易陷入局部最優(yōu)，影響了算法全局搜索能力。為了解決上述存在的問題，通過融入帶慣性權重的思想對FPA算法的全局授粉方式進行改進，具體如下：

其中，rand∈[0，1]是服從均勻分布的隨機數(shù)；i,i1,i2,i3,i4分別是從當前種群中隨機選取的5個不同個體的下標；分別是第t+1代、第t代的解；γ是控制步長的縮放因子；L是對應于花粉傳播者的Lévy飛行隨機搜索步長；λ=3/2。θ和ω的計算公式分別為公式（4）和公式（5）：

其中，fmax,t為第t代種群中最大適應度值，fi,t為當前個體的適應度值，N_iter為最大迭代次數(shù)，t為當前迭代次數(shù)。

從NMFPA算法的設計思想可知，算法的演化初期，種群個體的差異性比較大，算法的探測能力較強，無需對個體進行大幅度擾動，而隨著進化的不斷深入，個體的多樣性越來越小，算法的勘探能力被削弱了，影響了算法的優(yōu)化性能。依據(jù)上述公式（5）可知，在算法的進化初期，變量t的值較小，則慣性權重ω的取值較小，對種群的擾動性較弱；當算法進入演化后期，變量t的值越來越大，慣性權重ω的值越來越大，對種群的擾動性較強，有利于增加種群的多樣性，以增強算法的全局優(yōu)化能力。公式（5）中的系數(shù)0.01，是經過大量實驗獲得的經驗值。

帶慣性權重的新全局授粉方式，在保留Lévy飛行機制的同時利用了兩組隨機個體的差異矢量，增加了算法的擾動性和算法在多維空間的探索能力。在進化后期，全局授粉部分采用帶慣性權重的搜索機制，增加種群個體的多樣性，有效避免算法早熟，提高算法優(yōu)化性能。

3.3 融入精英與信息共享機制的新局部授粉方式

從花授粉算法的局部搜索方程可知：

（1）產生的新個體是在個體的原狀態(tài)基礎上加上一個擾動項，該擾動項是由一個均勻分布的隨機數(shù)和兩個隨機個體差分矢量的乘積。雖然隨機產生的子代能夠較好地保持算法種群個體之間的差異性，使算法能夠維持良好的持續(xù)優(yōu)化能力，但也降低了算法的收斂速度。

（2）搜索策略沒有充分利用種群信息，使算法在進化過程中種群個體之間的差異性過早地丟失，不能較好地解決“早熟”問題，影響了算法解的質量。

針對上述存在的問題，采用精英策略和信息共享機制對標準FPA算法的局部授粉方式進行改進，新的變異策略如下：

①FPA/rand/1變異策略：

②FPA/best/2變異策略：

其中，i∈(1,2,…,NP（種群數(shù)））為當前個體的下標，r1，r2,r3和r4為4個不同的隨機個體的下標，xbest,t為第t代種群中最優(yōu)個體。δ,α,β是均值為0.5、標準偏差為0.1的高斯分布，通過縮放因子δ、α和β對算法的進化速度進行調節(jié)。

在新的局部搜索方法中，“FPA/rand/1”變異策略增加了算法種群個體的差異性，提高了算法優(yōu)化能力，但算法的收斂速度在一定程度上降低了；“FPA/best/2”變異機制通過最優(yōu)個體引導種群中其他個體的搜索方向，最優(yōu)個體的有用信息有利于開發(fā)最優(yōu)個體的搜索范圍，提高算法的尋優(yōu)效率，使其收斂速度與開發(fā)能力獲得提升，但也容易導致算法陷入局部最優(yōu)。因此，為了使其取長補短，更好提升算法的收斂能力，本文通過公式（4）的非線性遞減概率規(guī)則來融合這兩種變異策略。依據(jù)θ的表達式可知，在算法的進化初期，算法偏重于全局搜索；在進化后期，側重于局部搜索，有利于提高算法的尋優(yōu)性能。

另外，在FPA算法中個體之間缺乏信息交流，使其容易陷入局部極值，本文把信息共享機制融入到FPA的局部搜索中，即利用公式（8）來進行個體間的學習[23]，從而達到改善解的質量。

其中，f(xi)和 f(xj)分別表示個體xi和xj的目標函數(shù)適應度值，s=rand為學習步長，分別是個體i的最新狀態(tài)和原始狀態(tài)。

基于上述思想，構建FPA具有信息共享機制的新局部授粉方式：

通過公式（8）實現(xiàn)個體之間的信息交流；

if rand≥θthen

依據(jù)公式（7）執(zhí)行變異，產生新的個體；

else

依據(jù)公式（6）執(zhí)行變異，產生新的個體；

endif

其中θ的計算公式為公式（4）。

3.4 基于變異的改進策略

從FPA的構成可知，F(xiàn)PA是依據(jù)參數(shù) p的值隨機地選取全局搜索或者局部搜索，這容易導致產生的新個體偏離全局最優(yōu)解的方向，影響FPA的收斂能力。為了解決該問題，本文在進入下一次迭代之前，利用基于高斯變異的最優(yōu)個體對種群中的其他個體的進化方向進行引導，以達到提高算法的收斂性能。但是，由于在上述多個位置運用了最優(yōu)個體策略，增加了FPA算法在收斂后期容易陷入局部極值風險，因此在個體進入下次演化之前，對個體進行非均勻變異，因為非均勻變異是一種能有效避免算法早熟的算子[24]。改進策略定義如下：

（1）基于高斯變異的最優(yōu)個體改進策略：

其中，xbest為當前種群中最優(yōu)個體；是第i個個體的新狀態(tài)；t為當前迭代次數(shù)，N_iter為最大迭代次數(shù)；k∈(1,0]為遞減變量，N(0,1)為高斯變異隨機向量。

（2）非均勻變異。變異是種群個體能夠持續(xù)進化的關鍵操作，而非均勻變異是對原有個體進行不同幅度的變異而產生新的個體。定義如下：

其中，t是當前迭代次數(shù)，Ub和Lb是解的上界和下界，r是[0，1]之間的隨機數(shù)，b是決定非均勻度的系統(tǒng)參數(shù)，N_iter為最大迭代次數(shù)，是第i個個體的原始狀態(tài)，是第i個個體的新狀態(tài)。

3.5 NMFPA算法流程

根據(jù)3.1～3.4節(jié)描述的算法改進思想，提出NMFPA算法，算法的流程圖如圖2所示，具體步驟如下：

步驟1初始化參數(shù)，包括花朵種群數(shù)n、轉換概率p、維數(shù)D、最大迭代次數(shù)N_iter等參數(shù)。

步驟2隨機產生種群并計算出其對應的適應度值，同時記錄種群中最好的適應度值及其對應的解。

圖2 NMFPA流程圖

步驟3采用公式（1）產生一個p值，若轉換概率p＞rand，進行全局搜索，按公式（2）或（3）對個體位置進行更新，并對新解越界處理，計算種群個體的適應度值，并記錄最優(yōu)值和最優(yōu)位置。

步驟4若轉換概率 p＜rand，先利用個體信息共享策略，即公式（8）更新個體位置，并對新解越界處理，計算花朵個體的適應度值，并記錄最優(yōu)值和最優(yōu)位置；再采用公式（6）或（7）對個體位置更新，且對新解進行越界處理，并計算花朵個體的適應度值，并記錄最優(yōu)值和最優(yōu)位置。

步驟5按公式（9）和（10）進行個體位置更新，并對新解越界處理。

步驟6計算步驟5花朵個體的適應度值，并記錄最優(yōu)值和最優(yōu)位置。

步驟7按公式（11）和（12）進行個體位置更新，并對新解越界處理；

步驟8計算步驟7花朵個體的適應度值，并記錄最優(yōu)值和最優(yōu)位置。

步驟9判斷結束條件，若滿足，退出程序并輸出最優(yōu)值及最優(yōu)解，否則，轉步驟步驟3。

3.6 NMFPA時間復雜度分析

對改進算法的有效性和可行性進行衡量，除了算法的優(yōu)化能力要有較大的提升，另一方面算法的時間復雜度也要低。與標準算法相比，運行的CPU時間應該不能太長。在元啟發(fā)式算法中，其運行時間主要用在算法找到問題最優(yōu)解或接近問題最優(yōu)解所需要的迭代次數(shù)。

假設優(yōu)化問題函數(shù)為 f(x)，解空間的維數(shù)為D，則根據(jù)FPA算法的描述和時間復雜度符號O的運算規(guī)則，F(xiàn)PA的時間復雜度為：T(FPA)=O(D+f(D))。

從NMFPA算法思想可知，公式（1）、公式（2）、公式（3）、公式（6）、公式（7）、公式（8）、公式（9）及公式（11）是改進的步驟，根據(jù)上文對這幾個公式的描述和時間復雜度符號O的運算規(guī)則，可以推導出NMFPA算法時間復雜度：T（NMFPA）=T（FPA）+T（公式（1））+T（公式（2））+T（公式（3））+T（公式（6））+T（公式（7））+T（公式（8））+T（公式（9））+T（公式（11））=O(D+f(D))+O(D+f(D))+O(1)+O(1)+O(1)+O(1)+O(1)+O(D+f(D))+O(D+f(D))=O(D+f(D))，與FPA算法的時間復雜度屬于同一數(shù)量級，說明改進策略對算法的時間復雜度影響較小。

3.7 NMFPA收斂性分析

依據(jù)NMFPA算法的思想可知，NMFPA算法屬于隨機優(yōu)化算法，則其全局收斂性可利用隨機優(yōu)化算法的收斂準則進行判斷。Solis等學者[25]對隨機優(yōu)化算法的收斂性進行了深入研究，提出了判斷隨機優(yōu)化算法是否收斂的兩條準則，其具體描述如下：

對于求解的最小優(yōu)化問題 ＜S,f＞，算法A經過迭代k次后獲得的解為xk，則下一次迭代后產生的新解為。其中，S是優(yōu)化問題的可行解空間，f為求解問題對應的目標函數(shù)，ξ為算法A進化過程中已獲得的解。

在Lebesgue測度空間定義搜索的下確界：

其中，ν(Χ)表示為在集合X上的Lebesgue測度，則其對應的最優(yōu)解區(qū)域定義為：

其中，ε＞0，M 為充分大的正數(shù)，若算法A在最優(yōu)解區(qū)域找到了一個點，則稱算法A找到了誤差為ε的可接受點。

準則H1 如果 f(A(x,ξ))≤f(x),ξ∈S ，則

準則H2如果對?B∈S,s.t.v(B)＞0，則

其中，uk(B)是算法A第k次解在集合B上的概率測度。

定理1設 f是可測函數(shù)，且S為Rn上的可測度子集，是算法A產生的解序列，若算法A滿足準則1和準則2，則有，即算法 A全局收斂。

定理2當花朵群體迭代次數(shù)趨于無窮，則花朵群體狀態(tài)序列必將進入最優(yōu)狀態(tài)集G。

定理3 NMFPA算法收斂于全局最優(yōu)解。

證明NMFPA算法在迭代過程中，算法A可描述為：

從上述描述可知NMFPA算法滿足準則1。

其次，如果要使定理1中的準則2成立，則要求算法A持續(xù)無窮次未搜尋到B中的元素的概率為0。由Rε,M?S和定理2可知，NMFPA算法滿足準則2。

為此，依據(jù)定理1可知，NMFPA算法全局收斂。

4 數(shù)值實驗及分析

4.1 測試函數(shù)

為了驗證NMFPA算法的優(yōu)化能力，本文選取了22個經典測試函數(shù)進行仿真實驗。在這22個測試函數(shù)[26-27]中，包括單峰多維函數(shù)(f1～f7)、多峰非旋轉的高維函數(shù)(f8～f12)、帶旋轉的多峰高維函數(shù)(f13～f17)、偏移的單峰函數(shù)或偏移且旋轉的多峰函數(shù)(f18～f22)，表1列出了本文所使用的測試函數(shù)的名稱、搜索范圍、維數(shù)和最優(yōu)值。

4.2 實驗設置

為了驗證NMFPA算法在性能上的優(yōu)勢，除了與FPA算法進行對比，還將與目前有代表性的4種改進FPA算法從收斂精度和收斂速度、Friedman和Wilcoxon檢驗、魯棒性及CPU運行時間四個方面進行實驗對比分析。

（1）混合差分進化花授粉算法（hybrid Differential Evolution-Flower Pollination Algorithm，DE-FPA）[18]。

（2）基于精英反向學習花授粉算法（Elite Oppositionbased Flower Pollination Algorithm，EOFPA）[17]。

（3）改進花授粉算法（Modified Flower Pollination Algorithm，MFPA）[14]。

（4）基于廣義反向學習的改進花授粉算法（Modified Generalised Oppsition-based Flower Pollination Algorithm，MGOFPA）[14]。

實驗參數(shù)設置為：對于 f1～f17函數(shù)，所有算法的種群數(shù)設置為50，最大迭代次數(shù)設置為500；f18～f22測試函數(shù)最大迭代次數(shù)設置為3 000，算法的種群規(guī)模設置為100，所有測試函數(shù)的維數(shù)D=30。為了降低實驗差錯，每種算法在每個測試函數(shù)上獨立運行30次。其余參數(shù)，對于EOFPA算法、MGOFPA算法和MFPA算法，取自于對應文獻中，DE-FPA算法中的F=0.5、CR=0.9，其他參數(shù)來自其文獻。FPA算法的轉換概率p=0.8。

4.3 算法性能評價指標

本文采用優(yōu)化均值誤差(Mean_error)和標準方差(Std.Dev)評價算法的優(yōu)化能力，其中優(yōu)化均值誤差計算公式如下：

其中，Mean_error表示優(yōu)化均值誤差，x表示算法得到的解，x*表示的是每個測試函數(shù)的理論最優(yōu)解。從公式（13）可知，Mean_error的值越小，則解的質量越好。

同時，為了公平客觀地對參與對比算法的收斂能力進行評價，利用Wilcoxon秩和檢驗（顯著性水平a=0.05）分別對22個函數(shù)的實驗結果進行統(tǒng)計分析。

4.4 與FPA以及改進FPA算法比較

4.4.1 算法的收斂精度和速度對比分析

實驗結果如表2所示，表2中符號?、≈和?分別表示NMFPA算法的實驗結果優(yōu)于、相當于和劣于對比算法，其中最優(yōu)結果用加粗凸顯。

對表2進行分析發(fā)現(xiàn)：NMFPA算法取得20個最優(yōu)結果，DE-FPA、EOFPA、MFPA、MGOFPA與FPA分別獲得2、12、0、1和0個最優(yōu)結果。NMFPA與DE-FPA、EOFPA、MFPA、MGOFPA和FPA相比，分別多出18、8、20、19和20個最優(yōu)結果，這證明NMFPA算法的優(yōu)化性能顯著優(yōu)于對比算法。具體分析如下：

表2 6種算法的優(yōu)化均值誤差和標準差

（1）在單峰多維函數(shù) (f1～f7)中，NMFPA、DE-FPA、EOFPA、MFPA、MGOFPA和FPA各自取得7、1、3、0、1和0個最佳結果，NMFPA獲得的最優(yōu)結果個數(shù)是所有算法中最多的，比對比算法中獲得最好結果的EOFPA多4個，這說明NMFPA解決單峰多維問題的能力強于其他5種對比算法。

（2）對于多峰非旋轉的高維函數(shù)(f8～f12)，在6個對比算法中，NMFPA在5個函數(shù)上取得的結果全部最優(yōu)，而EOFPA獲得3個，其余4種對比算法沒有獲得最優(yōu)結果，NMFPA比EOFPA多2個最好結果，優(yōu)勢不明顯，但從圖3中函數(shù) f9的收斂曲線可知，NMFPA算法的收斂速度要明顯快于EOFPA算法；與其他4種算法相比，NMFPA在所有測試函數(shù)上的結果均優(yōu)，優(yōu)勢非常顯著，這表明新算法的收斂能力具有一定的競爭力。

（3）在帶旋轉的多峰高維函數(shù)(f13～f17)中，除了函數(shù) f13和 f17外，NMFPA和EOFPA都能找到理論最優(yōu)解，但對于函數(shù) f13和 f17，NMFPA的收斂精度顯著優(yōu)于EOFPA，其精度高于EOFPA至少3個數(shù)量級；對于其他4種算法，在這5個函數(shù)上都沒找理論最優(yōu)解，且收斂精度遠遠遜色于NMFPA，證明NMFPA算法的優(yōu)化能力比其他5種算法強。

（4）最后，在最復雜的帶偏移的單峰函數(shù)或帶偏移且旋轉的多峰函數(shù)(f18～f22)中，對于函數(shù) f21和 f22，NMFPA取得了最好的結果；對于函數(shù) f18，NMFPA、DEFPA和EOFPA都取得了理論最優(yōu)解，但NMFPA的結果明顯好于其余3種算法；對于函數(shù) f19，NMFPA遜色于DE-FPA和EOFPA，但優(yōu)于其他3種算法；在函數(shù) f20上，NMFPA稍差于EOFPA，但好于其他4種算法。這說明NMFPA更適合求解更復雜的優(yōu)化問題。

同時借助表2中wilcoxon秩和檢驗“?”的數(shù)學統(tǒng)計結果，從表2的倒數(shù)第三行可知，NMFPA在22個測試函數(shù)上顯著優(yōu)于DE-FPA、MFPA、MGOFPA和FPA，分別在19、22、21和21個函數(shù)上表現(xiàn)更優(yōu)。與EOFPA相比，NMFPA取得10個最優(yōu)結果，10個結果兩者相當，2個結果稍遜色于EOFPA。

綜上分析，NMFPA算法的收斂精度總體上要顯著好于對比算法，展示出良好的競爭力。

為了直觀地進一步驗證NMFPA算法的求精能力和收斂速度是否優(yōu)于基本FPA和已有改進的FPA算法，限于篇幅，本節(jié)通過部分函數(shù)的收斂曲線圖（如圖3所示）和全局最優(yōu)值方差分析對比圖（如圖4所示）進行檢驗。為了更好地觀察和顯示各種算法在各個函數(shù)上的收斂趨勢，圖3是對每個函數(shù)的優(yōu)化均值誤差取了以10為底的對數(shù)的收斂曲線圖。圖4是部分函數(shù)在固定迭代次數(shù)下，6種算法的全局最優(yōu)值方差分析對比圖。

圖3 6種FPA算法在部分函數(shù)上的收斂曲線圖

圖4 6種FPA算法在部分函數(shù)上的全局最優(yōu)值方差分析

從圖3可以看出：NMFPA在4類函數(shù)上的收斂速度明顯快于其他5種算法，特別在函數(shù) f1上，NMFPA在迭代不到200次時，就已找到全局最優(yōu)解，這表明本文提出的新算法的收斂速度和精度與其他算法相比，具有較好的競爭力。同時，從圖4可知，對于多模函數(shù) f13、f17和 f21，NMFPA的收斂精度顯著優(yōu)于其他5種算法，這也驗證了表2的實驗結果。

4.4.2 算法的Friedman和Wilcoxon檢驗

為了公平公正地對比各種算法的收斂性能，對多個算法的整體性能從數(shù)學統(tǒng)計意義上進行比較分析，采用Friedman檢驗對實驗結果進行分析，算法秩均值越小，性能越好，排名越高。表3是6種算法在22個函數(shù)上的Friedman的檢驗結果，NMFPA算法的秩均值為1.61，排名第一，比FPA算法的秩均值小3.63，這表明本文采用的改進策略能有效地提高FPA算法的性能。

為判別NMFPA算法與對比算法之間是否存在顯著性差異，采用Wilcoxon檢驗進行分析，實驗結果如表4所示。從表4可知，NMFPA算法與其他算法的顯著性差異較大，這證實運用本文提出的改進策略，能夠有效提高FPA算法的全局優(yōu)化能力。

表3 6種FPA的Friedman檢驗（D=30）

表4 NMFPA與其他5種FPA的Wilcoxon’s test（D=30）

從上述的實驗結果表明，通過多種策略對FPA進行改進而構建的新算法與標準的FPA和現(xiàn)有改進的FPA算法相比，具有較強的競爭力。

4.4.3 算法的魯棒性對比分析

衡量一個算法的優(yōu)劣，算法的魯棒性是其中一個重要的指標，本節(jié)對NMFPA算法的魯棒性進行檢驗分析。在收斂精度固定下，檢驗其魯棒性的優(yōu)越性。

在表5中，對每個函數(shù)都設定了一個優(yōu)化精度閾值，如果每種算法在迭代次數(shù)超過500(f1～f17)或3 000(f18～f22)次還沒找到精度閾值，則認定本次尋優(yōu)不成功，其余參數(shù)同上，SR=找到精度閾值的次數(shù)/總的運行次數(shù)，所有算法在每個函數(shù)上獨立運行30次，計算其運行成功率(SR)和平均迭代次數(shù)(mean_iter)，實驗結果如表5所示，其中“NA”表示尋優(yōu)失利，最佳效果用加粗凸顯。

對表5分析可知：

（1）在7個單峰函數(shù)(f1～f7)上，NMFPA的優(yōu)化成功率明顯優(yōu)于DE-FPA、MFPA、MGOFPA和FPA；與EOFPA相比，本文算法在28.57%函數(shù)上表現(xiàn)更優(yōu)，在71.43%函數(shù)上兩者的優(yōu)化成功率相當，NMFPA的優(yōu)勢不顯著，但從其平均迭代次數(shù)，NMFPA在7個函數(shù)上均優(yōu)于EOFPA，進一步驗證了本文算法的收斂速度顯著快于EOFPA。尤其對于經典的非凸病態(tài)單峰測試函數(shù) f5，算法在進化過程中易陷入局部最優(yōu)，求解難度非常大，本文算法的優(yōu)化成功率達到76.67%，而其余算法為0，這表明NMFPA算法穩(wěn)定性最好。

（2）對于多峰函數(shù)(f8～f12)，NMFPA在所有函數(shù)上均好于MFPA和FPA，與DE-FPA、EOFPA和MGOFPA相比，NMFPA取得最優(yōu)結果分別多3、1和2個。尤其對于函數(shù) f11而言，只有本文算法的收斂成功率達到100%，而其他算法都沒有。這說明本文算法在優(yōu)化多模態(tài)函數(shù)時，其魯棒性表現(xiàn)最突出。

（3）對5個旋轉函數(shù)(f13～f17)而言，NMFPA算法的魯棒性優(yōu)勢更顯著，其尋優(yōu)成功率是所有對比算法中最好的，均獲得最優(yōu)結果，這證明本文算法在解決旋轉問題時，其魯棒性更優(yōu)。

（4）在第4類更復雜的帶偏移或帶偏移且旋轉的函數(shù)(f18～f22)中，NMFPA的優(yōu)化成功率優(yōu)于MFPA和MGOFPA；與DE-FPA和EOFPA相比，三者的尋優(yōu)成功率優(yōu)勢相當；與FPA對比，NMFPA的魯棒性與FPA相當，但其平均迭代次數(shù)要好于FPA。這說明NMFPA在解決更復雜的問題時，其穩(wěn)定性也具有一定的優(yōu)勢。

從表5的最后一行可知，NMFPA的總的平均收斂成功率達到92.58%，是6種算法中最高的，其余5種算法中，尋優(yōu)成功率最好的是EOFPA，其優(yōu)化成功率為74.55%，NMFPA比其高出18.03%。FPA算法的總的平均尋優(yōu)成功率只有18.64%，NMFPA與其相比，提高了73.94%，與其他4種算法相比，也至少高出53.34%，這表明NMFPA算法的魯棒性最優(yōu)。

表5 6種算法的尋優(yōu)成功率及平均迭代次數(shù)

圖5 6種FPA算法在部分函數(shù)上的最優(yōu)適應度值比較圖

為進一步直觀地驗證NMFPA算法的魯棒性優(yōu)于對比算法，由于篇幅所限，圖5給出了部分函數(shù)的最優(yōu)適應度值變化對比圖，是對比算法在每個函數(shù)上獨立運行30次下的最優(yōu)適應度值變化對比圖。

從圖5可知，在6個測試函數(shù)上，除 f21外，NMFPA算法在每個函數(shù)上都沒出現(xiàn)過波動現(xiàn)象，魯棒性明顯好于對比算法，尤其對于函數(shù) f13和 f17函數(shù)，除NMFPA算法外，其他算法波動得非常厲害，這表明其他算法的穩(wěn)定性要比NMFPA差，這也進一步佐證了表5的結果。對于函數(shù) f21，所有函數(shù)都出現(xiàn)了一定程度的波動性，但NMFPA的計算精度是最優(yōu)的。

綜上述，NMFPA算法在4類測試函數(shù)上，魯棒性明顯好于對比算法，佐證了本文的改進策略是行之有效的。

4.4.4 算法的CPU運行時間比較分析

本節(jié)驗證改進策略對FPA運行時間的影響。參與比較的算法同4.2節(jié)，其中，所有算法在每個函數(shù)上的最大迭代次數(shù)都是500，其他實驗參數(shù)的設置同4.2節(jié)。實驗環(huán)境是：處理器為Intel?Core? i7-4790 CPU 3.6 GHz，內存為4.00 GB；在MATLAB R2014a進行仿真。表6給出了7種算法在部分函數(shù)上的平均CPU運行時間結果，其中表中MT為總的平均時間。

表6給出了6種算法在部分函數(shù)上的平均CPU運行時間結果，其中表中MT為總的平均時間。

對表6分析可知：

（1）NMFPA算法總的平均CPU時間要比EOFPA少1.921 9 s，這表明NMFPA算法與該算法相比，簡單且高效。

表6 6種算法在函數(shù)上的平均CPU運行時間 s

（2）與其他4種算法相比，NMFPA算法總的平均CPU時間要稍多一些，但都在同一數(shù)量級上，且增加的時間在可承受的范圍之內。NMFPA相對FPA而言，CPU的運行時間在一定程度上增加了一些。這是因為NMFPA在進入下次迭代之前，增加了最優(yōu)個體引導策略和非均勻變異算子，使得NMFPA算法增加了時間消耗，但兩者都屬于同一數(shù)量級，實驗結果驗證了上述3.6節(jié)的理論分析結果。

4.5 策略分析

為了驗證本文采用的各種策略的有效性，把各種主要的改進策略獨立出來進行測試，以檢驗其是否行之有效。IFPA表示對基本FPA的全局搜索策和局部搜索進行改進后的算法；PIFPA表示是在IFPA基礎上對參數(shù)p進行自適應調整的算法；WPIFPA表示是在PIFPA基礎上對全局授粉部分增加了慣性權重的算法；NMFPA表示是在WPIFPA基礎增加了變異策略后改進的算法。本節(jié)的實驗參數(shù)設置為：FPA和IFPA的轉換概率 p=0.8，PIFPA、WPIFPA和NMFPA中的 p均采用動態(tài)調整策略，所有算法的其他參數(shù)設置同4.2節(jié)。實驗結果如表7所示，其中，最優(yōu)結果用加粗凸顯，rank表示每個算法在每個函數(shù)上優(yōu)化性能的排序，sumrank表示每個算法在所有函數(shù)上收斂能力的排序和，其值反映該算法的綜合性能，值越小，其對應的算法整體性能越優(yōu)。

表7 5種算法的優(yōu)化均值誤差和標準差（D=30）

從表7可以看出，NMFPA、WPIFIPA、PIFPA、IFPA和FPA在22個函數(shù)上，分別獲得21、9、3、1和0個最優(yōu)結果，這表明本文提出的策略相互協(xié)作優(yōu)化可以更好平衡算法的探測和開采，表現(xiàn)出良好的全局優(yōu)化性能。

各策略的性能表現(xiàn)具體如下：

（1）IFPA與FPA相比，除 f8、f15和 f19～f22外，IFPA在16個函數(shù)上取得了更好的結果，這說明IFPA具有更優(yōu)的全局搜索性能。由sumrank（IFPA）=67＜sumrank（FPA）=81可知，IFPA的綜合性能比FPA更優(yōu)。

（2）PIFPA在22個函數(shù)上，與IFPA相比，PIFPA在單模、多模、旋轉和偏移或偏移且旋轉的函數(shù)上分別取得5、4、4和3個最佳效果，這表明對參數(shù) p進行自適應調整改進的PIFPA具有更好的收斂能力，且由sumrank（PIFPA）=49＜sumrank（IFPA）=67可知，PIFPA的整體性能更好。

（3）WPIFPA在單模、多模、旋轉函數(shù)上明顯優(yōu)于PIFPA。對于偏移或帶偏移且旋轉的 f18、f20和 f22函數(shù)，兩者的性能相當；在f19和 f21函數(shù)上，WPIFPA要比PIFPA遜色些；同時sumrank（WPIFPA）=37＜sumrank（PIFPA）=49。從上述分析可知，WPIFPA優(yōu)化能力要優(yōu)于PIFPA。

（4）對于單峰和偏移或帶偏移且旋轉函數(shù)，NMFPA分別獲得6個和3個最優(yōu)結果，明顯好于WPIFPA。在其余2類函數(shù)上稍好于WPIPFA；同時，sumrank（NMFPA）=23＜sumrank（WPIFPA）=37。從上述分析可知，NMFPA的尋優(yōu)性能要表現(xiàn)得更好。

綜上述分析可知，NMFPA的尋優(yōu)性能表現(xiàn)最突出，即本文提出的改進策略能在一定程度上提高算法的優(yōu)化性能。同時，由表7中的wilcoxon秩和檢驗“?”的數(shù)學統(tǒng)計結果可知，NMFPA與FPA、IFPA、PIFPA和WPIFPA相比，分別在21、20、19和12個函數(shù)上表現(xiàn)更優(yōu)。這表明本文提出的各種策略能相互協(xié)調優(yōu)化可提升算法的全局優(yōu)化能力。

4.6 NMFPA算法求解PFSP工程優(yōu)化問題

為了檢驗NMFPA算法求解經典的置換流水車間調度（Permutation Flow Shop Scheduling Problem，PFSP）問題是否行之有效，本文采用了解決PFSP優(yōu)化問題時，廣泛利用的標準測試案例Car類[28]和Taillard類[29]中的部分測試案例進行實驗仿真，并與傳統(tǒng)的花授粉算法、慣性權重線性遞減的粒子群算法（LWPSO）的實驗結果進行對比分析。本節(jié)實驗的參數(shù)設置為：對比算法的迭代次數(shù)和種群都設置為50，NMFPA和FPA算法的其他參數(shù)設置同4.2節(jié)，粒子群算法的慣性權重運用線性減少策略，且Wmax=0.9，Wmin=0.4，學習因子c1=c2=1.496 2。

實驗結果如表8所示，其中Car1_11*5表示測試算例Car1在5臺加工機器上有11個工件進行加工處理，C*表示所有工件加工完成所需時間的最小值。為了比較算法的優(yōu)化能力，運用相對誤差的最優(yōu)值（Best Relative Error，BRE）、相對誤差的平均值（Average Relative Error，ARE）、相對誤差的最壞值（Worst Relative Error，WRE）三個性能指標對算法的優(yōu)化能力進行度量[30]。

從表8中可知，在Car類測試實例上，NMFPA算法的性能在7個算例上要顯著優(yōu)于對比算法且都能找到理論最優(yōu)解，只有在Car3_12*5算例上，NMFPA的ARE比LWPSO略差一些，但其他2項指標要好于LWPSO，且所有指標要優(yōu)于標準的FPA算法；對于Taillard類，所有對比算法雖然都不能找到理論最優(yōu)解，但NMFPA的整體性能明顯好于其他2種比較算法。上述實驗分析驗證了用NMFPA解決實際工程優(yōu)化問題時，是可行的且具有一定的優(yōu)勢。進一步說明本文提出的改進策略是可行且有效的。

為了更直觀地證明NMFPA算法對PFSP問題的求解能力，圖6顯示了3種對比算法在部分測試算例上的收斂曲線圖，從圖6中可以直觀清楚地看出，改進算法的尋優(yōu)精度和收斂速度都要優(yōu)于其他兩種對比算法。這表明NMFPA算法比對比算法更適合解決PFSP問題，也進一步驗證了改進策略的有效性。

表8 3種算法的測試算例結果

5 結束語

本文提出了一種新授粉方式的花授粉算法（NMFPA），其改進的策略包括了對基本FPA授粉方式的改進，轉換概率 p自適應調整策略及進化策略的改進。對標準FPA授粉方式的改進，擴展探索范圍和增加種群的多樣性，提高FPA的全局優(yōu)化能力，局部開發(fā)能力和搜索速度；轉換概率 p采用動態(tài)調整策略，增強FPA的靈活性和健壯性等性能；基于高斯變異的最優(yōu)個體策略用于引導其他個體的進化方向，提高FPA的收斂速度；利用非均勻變異策略防止FPA早熟，提高FPA的尋優(yōu)性能。本文采用4類共22個測試函數(shù)進行仿真實驗，將NMFPA與FPA、4種改進的FPA算法進行對比分析，實驗結果表明NMFPA在解的質量，收斂速度和穩(wěn)定性上表現(xiàn)出更優(yōu)，是一種富有競爭力的新算法。同時，對本文提出的各種策略在4類不同函數(shù)上進行了性能分析，對比結果驗證了不同策略均能在一定程度上提升算法的性能，且各種策略能夠協(xié)調優(yōu)化，更好地平衡算法的收斂精度和速度，提高了FPA的綜合優(yōu)化性能。最后，利用改進算法對PFSP問題進行求解，實驗結果顯示，新算法用來解決實際工程優(yōu)化問題是可行的且也具有一定的優(yōu)勢。