段艷明，肖輝輝，林 芳

河池學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，廣西 河池 546300

1 引言

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

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

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

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

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

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

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

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

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

2 花授粉算法

2.1 FPA存在的不足

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

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

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

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

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

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

表1 本文使用的實(shí)驗(yàn)測(cè)試函數(shù)

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

實(shí)驗(yàn)參數(shù)設(shè)置：p初值0.0，步長(zhǎng)0.01，終值1.0，函數(shù)維數(shù)D=30，種群50，迭代次數(shù)1 000；為防止偶然性帶來(lái)的實(shí)驗(yàn)誤差，對(duì)每個(gè) p值，獨(dú)立運(yùn)行30次，并計(jì)算其平均值。

從圖1中可知：

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

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

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

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

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

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

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

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

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

從公式（1）可知：

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

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

3.2 帶慣性權(quán)重的新全局授粉方式

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

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

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

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

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

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

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

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

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

針對(duì)上述存在的問(wèn)題，采用精英策略和信息共享機(jī)制對(duì)標(biāo)準(zhǔn)FPA算法的局部授粉方式進(jìn)行改進(jìn)，新的變異策略如下：

①FPA/rand/1變異策略：

②FPA/best/2變異策略：

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

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

另外，在FPA算法中個(gè)體之間缺乏信息交流，使其容易陷入局部極值，本文把信息共享機(jī)制融入到FPA的局部搜索中，即利用公式（8）來(lái)進(jìn)行個(gè)體間的學(xué)習(xí)[23]，從而達(dá)到改善解的質(zhì)量。

其中，f(xi)和 f(xj)分別表示個(gè)體xi和xj的目標(biāo)函數(shù)適應(yīng)度值，s=rand為學(xué)習(xí)步長(zhǎng)，分別是個(gè)體i的最新?tīng)顟B(tài)和原始狀態(tài)。

基于上述思想，構(gòu)建FPA具有信息共享機(jī)制的新局部授粉方式：

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

if rand≥θthen

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

else

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

endif

其中θ的計(jì)算公式為公式（4）。

3.4 基于變異的改進(jìn)策略

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

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

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

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

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

3.5 NMFPA算法流程

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

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

步驟2隨機(jī)產(chǎn)生種群并計(jì)算出其對(duì)應(yīng)的適應(yīng)度值，同時(shí)記錄種群中最好的適應(yīng)度值及其對(duì)應(yīng)的解。

圖2 NMFPA流程圖

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

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

步驟5按公式（9）和（10）進(jìn)行個(gè)體位置更新，并對(duì)新解越界處理。

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

步驟7按公式（11）和（12）進(jìn)行個(gè)體位置更新，并對(duì)新解越界處理；

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

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

3.6 NMFPA時(shí)間復(fù)雜度分析

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

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

從NMFPA算法思想可知，公式（1）、公式（2）、公式（3）、公式（6）、公式（7）、公式（8）、公式（9）及公式（11）是改進(jìn)的步驟，根據(jù)上文對(duì)這幾個(gè)公式的描述和時(shí)間復(fù)雜度符號(hào)O的運(yùn)算規(guī)則，可以推導(dǎo)出NMFPA算法時(shí)間復(fù)雜度：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í)間復(fù)雜度屬于同一數(shù)量級(jí)，說(shuō)明改進(jìn)策略對(duì)算法的時(shí)間復(fù)雜度影響較小。

3.7 NMFPA收斂性分析

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

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

在Lebesgue測(cè)度空間定義搜索的下確界：

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

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

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

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

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

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

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

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

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

從上述描述可知NMFPA算法滿足準(zhǔn)則1。

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

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

4 數(shù)值實(shí)驗(yàn)及分析

4.1 測(cè)試函數(shù)

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

4.2 實(shí)驗(yàn)設(shè)置

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

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

（2）基于精英反向?qū)W習(xí)花授粉算法（Elite Oppositionbased Flower Pollination Algorithm，EOFPA）[17]。

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

（4）基于廣義反向?qū)W習(xí)的改進(jìn)花授粉算法（Modified Generalised Oppsition-based Flower Pollination Algorithm，MGOFPA）[14]。

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

4.3 算法性能評(píng)價(jià)指標(biāo)

本文采用優(yōu)化均值誤差(Mean_error)和標(biāo)準(zhǔn)方差(Std.Dev)評(píng)價(jià)算法的優(yōu)化能力，其中優(yōu)化均值誤差計(jì)算公式如下：

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

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

4.4 與FPA以及改進(jìn)FPA算法比較

4.4.1 算法的收斂精度和速度對(duì)比分析

實(shí)驗(yàn)結(jié)果如表2所示，表2中符號(hào)?、≈和?分別表示NMFPA算法的實(shí)驗(yàn)結(jié)果優(yōu)于、相當(dāng)于和劣于對(duì)比算法，其中最優(yōu)結(jié)果用加粗凸顯。

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

表2 6種算法的優(yōu)化均值誤差和標(biāo)準(zhǔn)差

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

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

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

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

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

綜上分析，NMFPA算法的收斂精度總體上要顯著好于對(duì)比算法，展示出良好的競(jìng)爭(zhēng)力。

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

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

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

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

4.4.2 算法的Friedman和Wilcoxon檢驗(yàn)

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

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

表3 6種FPA的Friedman檢驗(yàn)（D=30）

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

從上述的實(shí)驗(yàn)結(jié)果表明，通過(guò)多種策略對(duì)FPA進(jìn)行改進(jìn)而構(gòu)建的新算法與標(biāo)準(zhǔn)的FPA和現(xiàn)有改進(jìn)的FPA算法相比，具有較強(qiáng)的競(jìng)爭(zhēng)力。

4.4.3 算法的魯棒性對(duì)比分析

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

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

對(duì)表5分析可知：

（1）在7個(gè)單峰函數(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)化成功率相當(dāng)，NMFPA的優(yōu)勢(shì)不顯著，但從其平均迭代次數(shù)，NMFPA在7個(gè)函數(shù)上均優(yōu)于EOFPA，進(jìn)一步驗(yàn)證了本文算法的收斂速度顯著快于EOFPA。尤其對(duì)于經(jīng)典的非凸病態(tài)單峰測(cè)試函數(shù) f5，算法在進(jìn)化過(guò)程中易陷入局部最優(yōu)，求解難度非常大，本文算法的優(yōu)化成功率達(dá)到76.67%，而其余算法為0，這表明NMFPA算法穩(wěn)定性最好。

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

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

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

從表5的最后一行可知，NMFPA的總的平均收斂成功率達(dá)到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)適應(yīng)度值比較圖

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

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

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

4.4.4 算法的CPU運(yùn)行時(shí)間比較分析

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

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

對(duì)表6分析可知：

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

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

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

4.5 策略分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表8 3種算法的測(cè)試算例結(jié)果

5 結(jié)束語(yǔ)

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