肖輝輝，萬(wàn)常選，段艷明，喻 聰

1.江西財(cái)經(jīng)大學(xué) 信息管理學(xué)院，南昌 330013

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

融合高斯變異和Powell法的花朵授粉優(yōu)化算法*

肖輝輝1,2，萬(wàn)常選1+，段艷明2，喻 聰1

1.江西財(cái)經(jīng)大學(xué) 信息管理學(xué)院，南昌 330013

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

花朵授粉算法（flower pollination algorithm，F(xiàn)PA）是最近提出的一種新型群智能優(yōu)化算法，由于其較好地解決了全局搜索和局部搜索的平衡性問(wèn)題，且具有參數(shù)少，易實(shí)現(xiàn)等特點(diǎn)，已得到廣泛應(yīng)用和研究，但現(xiàn)有研究對(duì)其參數(shù)的研究較少，同時(shí)該算法也存在演化后期收斂速度慢且易陷入局部極小等缺陷，使其應(yīng)用范圍受到制約。為了提升FPA算法的整體性能，對(duì)其控制步長(zhǎng)的縮放因子的取值進(jìn)行了修正；提出了把高斯變異和Powell法融入到花朵授粉算法中的混合算法GMPFPA（flower pollination algorithm combination with Gauss mutation and Powell search method）。改進(jìn)算法首先利用高斯變異對(duì)全局搜索進(jìn)行擾動(dòng)，增強(qiáng)種群的多樣性，提高全局探測(cè)能力，然后引入局部尋優(yōu)能力強(qiáng)大的Powell法提升其局部開(kāi)發(fā)能力。通過(guò)12個(gè)高維經(jīng)典測(cè)試函數(shù)對(duì)比實(shí)驗(yàn)，驗(yàn)證了改進(jìn)算法的有效性和優(yōu)越性。

高斯變異；花朵授粉算法（FPA）；Powell法；最優(yōu)值；尋優(yōu)能力

1 引言

群智能優(yōu)化算法是受自然界進(jìn)化規(guī)律和自然界生物群體智能行為的啟發(fā)而提出的，由于其靈活、結(jié)構(gòu)直觀、適用性強(qiáng)等特點(diǎn)，已在社會(huì)、經(jīng)濟(jì)和自然科學(xué)等領(lǐng)域得到廣泛應(yīng)用，成為人工智能中一個(gè)非?；钴S的研究課題。花朵授粉算法（flower pollination algorithm，F(xiàn)PA）[1]是英國(guó)劍橋大學(xué)學(xué)者Yang提出，模擬花朵授粉過(guò)程的一種新型元啟發(fā)式群智能優(yōu)化算法。由于該算法參數(shù)少、容易實(shí)現(xiàn)、易調(diào)節(jié)，利用轉(zhuǎn)換概率參數(shù)p較好地解決了局部開(kāi)發(fā)和全局搜索平衡問(wèn)題，使其比粒子群算法（particle swarm optimization，PSO）[2]和遺傳算法（genetic algorithm，GA）[3]具有更好的尋優(yōu)能力[1]。目前，F(xiàn)PA算法已經(jīng)在函數(shù)優(yōu)化[4]、桁架結(jié)構(gòu)的尺寸優(yōu)化[5]、圖著色[6]、光伏系統(tǒng)[7]、經(jīng)濟(jì)調(diào)度[8]及產(chǎn)品裝配序列規(guī)劃[9]等眾多領(lǐng)域得到廣泛的應(yīng)用。然而，該算法與蝙蝠算法[10]、粒子群算法類似，也存在易陷入局部最優(yōu)且進(jìn)化后期收斂速度慢等不足。為此，眾多國(guó)內(nèi)外學(xué)者針對(duì)基本花朵授粉算法存在的缺陷進(jìn)行改進(jìn)：如Abdel-Raouf等人[11]把PSO算法融入到花朵授粉算法中，利用PSO算法來(lái)提高FPA算法初始解的質(zhì)量，從而提高算法的尋優(yōu)精度和收斂速度；Wang等人[12]認(rèn)為維數(shù)之間的相互影響，使得算法的收斂速度慢和解的質(zhì)量不高，提出對(duì)解進(jìn)行逐維改進(jìn)和引入局部鄰域搜索策略來(lái)對(duì)算法進(jìn)行改進(jìn)，改進(jìn)算法在尋優(yōu)速度和探索能力方面有所提高；Lenin等人[13]提出了基于混沌和聲算法的花朵授粉優(yōu)化算法，先采用混沌策略提高和聲算法種群的多樣性，再把和聲算法的最優(yōu)解作為花朵授粉算法的初始解，改進(jìn)算法的尋優(yōu)精度和解的質(zhì)量得到一定程度的提升。

上述這些方法雖在一定程度上改進(jìn)了FPA算法求解相關(guān)優(yōu)化問(wèn)題的解的質(zhì)量和收斂速度，提高了算法的尋優(yōu)能力，但在避免陷入局部極值、全局探測(cè)能力、收斂速度等方面仍存在不足。同時(shí)，從花朵授粉算法的優(yōu)化機(jī)制可以看出，花朵授粉算法主要依賴花朵個(gè)體之間的相互影響和作用來(lái)實(shí)現(xiàn)尋優(yōu)功能，而種群個(gè)體本身缺乏變異機(jī)能，如果種群中某個(gè)體一旦受到某個(gè)局部極小約束后，則該個(gè)體就很難逃脫局部極小的制約。并且在演化進(jìn)程中，種群中的少數(shù)超級(jí)花朵可能會(huì)把其他個(gè)體快速地吸引到其周圍，使得種群多樣性在進(jìn)化中急劇下降；同時(shí)隨著種群的不斷進(jìn)化，種群中的個(gè)體不斷向種群最優(yōu)個(gè)體靠近，其收斂速度變得非常緩慢甚至種群停滯進(jìn)化，造成種群向前演化的能力喪失。為此，在求解地形復(fù)雜、多峰及高維的復(fù)雜優(yōu)化問(wèn)題時(shí)，算法就很難尋找到全局最優(yōu)解。因此，提高花朵授粉算法進(jìn)化過(guò)程中種群的多樣性，從而達(dá)到提升算法的全局尋優(yōu)能力，是對(duì)該算法進(jìn)行改進(jìn)的一種正確思路。

花朵授粉算法作為一種新型群智能算法，雖提出時(shí)間短，但從上述的研究現(xiàn)狀的闡述得知，F(xiàn)PA算法是一種非常有前途的工程優(yōu)化算法。目前國(guó)外眾多學(xué)者對(duì)此算法掀起了研究熱潮，文獻(xiàn)[1]中作者聲稱花朵授粉算法的性能超過(guò)粒子群算法和遺傳算法。而國(guó)內(nèi)對(duì)其研究起步較晚，相關(guān)的文章報(bào)道不多。因此迫切需要對(duì)其理論進(jìn)行研究并擴(kuò)展其應(yīng)用領(lǐng)域，為今后的科學(xué)計(jì)算和工程實(shí)踐提供一定的參考。

同時(shí)，當(dāng)前從國(guó)內(nèi)外學(xué)者對(duì)花朵授粉算法研究現(xiàn)狀可知，很少學(xué)者對(duì)基本花朵授粉算法中的3個(gè)關(guān)鍵參數(shù)p、λ、γ進(jìn)行研究，而這3個(gè)參數(shù)的取值對(duì)算法性能具有重要的影響。從目前出版的文獻(xiàn)獲知，只有Draa[14]對(duì)3個(gè)參數(shù)中的p進(jìn)行了研究，獲知p=0.2比p=0.8/0.5[1]效果要好。然而對(duì)于參數(shù)γ，文獻(xiàn)[1]在全局搜索的數(shù)學(xué)公式中丟失了γ，甚至在文中沒(méi)有提及，在這種情況下相當(dāng)于γ=1；文獻(xiàn)[4]在全局搜索的數(shù)學(xué)公式中加入了參數(shù)γ，并建議γ取值為0.1，但并沒(méi)有對(duì)此參數(shù)進(jìn)一步地研究，同時(shí)在附錄中也沒(méi)提供此參數(shù)的任何信息。這促使本文對(duì)參數(shù)γ進(jìn)行研究，從實(shí)驗(yàn)分析中可知，對(duì)絕大部分測(cè)試函數(shù)γ取值為16是最好的。

針對(duì)上述改進(jìn)算法存在的缺陷和基本花朵授粉算法的局限性，本文提出了一種融合高斯變異和Powell法的花朵授粉算法的混合算法（flower pollination algorithm combination with Gauss mutation and Powell search method，GMPFPA）。通過(guò)對(duì)12個(gè)經(jīng)典函數(shù)進(jìn)行尋優(yōu)測(cè)試，結(jié)果表明改進(jìn)算法能夠有效地改善花朵授粉算法的尋優(yōu)能力，提高了其收斂速度和解的質(zhì)量，且能夠在一定程度上有效地避免早熟收斂。實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)算法的有效性和優(yōu)越性。

2 花朵授粉算法

花朵授粉算法是模擬自然界中顯花植物花朵授粉的過(guò)程，該算法遵循如下4條理想規(guī)則[4]。

規(guī)則1生物異花授粉是帶花粉的傳粉者通過(guò)萊維飛行進(jìn)行的全局授粉過(guò)程。該規(guī)則用數(shù)學(xué)公式表達(dá)如下：

其中，、分別是第t+1代、第t代的解；γ是步長(zhǎng)的縮放因子；g*是全局最優(yōu)解；L是步長(zhǎng)，L的計(jì)算如式（2）：

其中，λ=3/2，Γ(λ)是標(biāo)準(zhǔn)的伽馬函數(shù)。

規(guī)則2非生物自花授粉是局部授粉過(guò)程。該規(guī)則的數(shù)學(xué)表達(dá)式如下：

其中，∈是[0,1]上服從均勻分布的隨機(jī)數(shù)；、是相同植物種類的不同花朵的花粉。

規(guī)則3花的常性可以被認(rèn)為是繁衍概率，繁衍概率與參與的兩朵花的相似性成比例關(guān)系。

規(guī)則4轉(zhuǎn)換概率p∈[0,1]控制全局授粉和局部授粉之間的轉(zhuǎn)換，由于物理上的鄰近性和風(fēng)等其他因素的影響，在整個(gè)授粉活動(dòng)中，p是局部授粉的一個(gè)非常重要的部分。

然而，在現(xiàn)實(shí)自然界中，每一棵顯花植物可以開(kāi)好多朵花，每朵花產(chǎn)生數(shù)百萬(wàn)甚至數(shù)十億的花粉配子。為了把問(wèn)題簡(jiǎn)單化，假設(shè)每棵顯花植物僅僅只開(kāi)一朵花，且每朵花僅僅產(chǎn)生一個(gè)花粉配子。因此，問(wèn)題經(jīng)過(guò)簡(jiǎn)化后，意味著一朵花或一個(gè)配子就對(duì)應(yīng)于優(yōu)化問(wèn)題中的一個(gè)解。基于以上闡述，文獻(xiàn)[1]描述了基本的花朵授粉算法的實(shí)現(xiàn)步驟。

3 花朵授粉算法γ參數(shù)分析

任何群智能算法的參數(shù)取值對(duì)算法的性能影響是非常大的，在基本的花朵授粉算法中，有3個(gè)關(guān)鍵的參數(shù)p、λ、γ。參數(shù)p是全局搜索與局部搜索之間轉(zhuǎn)換的控制參數(shù)；參數(shù)λ是全局搜索萊維飛行中的控制參數(shù)；參數(shù)γ是控制步長(zhǎng)的縮放因子。如何合理調(diào)整這3個(gè)參數(shù)的值，提升FPA算法的性能，是值得研究的問(wèn)題。本文以下主要對(duì)參數(shù)γ的不同取值對(duì)FPA算法性能的影響進(jìn)行分析。

為了驗(yàn)證γ參數(shù)的不同取值對(duì)FPA算法的性能影響，通過(guò)12個(gè)測(cè)試函數(shù)[15]進(jìn)行測(cè)試，并取γ=16與γ=1和γ=0.1進(jìn)行比較。實(shí)驗(yàn)時(shí)，各種參數(shù)設(shè)置為：操作系統(tǒng)為Windows 7，CPU為Intel Core i5-3470，主頻為3.20 GHz，內(nèi)存為4 GB，編程語(yǔ)言為Matlab R2012b。基本FPA算法參數(shù)：轉(zhuǎn)換概率p=0.2，λ= 1.5，種群數(shù)sizepop=20，最大迭代次數(shù)為3 000。本文測(cè)試函數(shù)如表1所示，f1～f7為高維單峰函數(shù)（其中

f5是非凸病態(tài)且非常難找到全局最優(yōu)值的經(jīng)典高維單峰測(cè)試函數(shù)，算法在優(yōu)化過(guò)程中容易陷入局部極?。?，該類函數(shù)主要用于測(cè)試群智能算法的尋優(yōu)精度；f8～f12為高維多峰函數(shù)，此類函數(shù)具有大量局部極值點(diǎn)，在優(yōu)化時(shí)，很容易陷入局部最優(yōu)，全局最優(yōu)值較難找到，求解難度隨著維數(shù)的增加而增大，尤其是函數(shù)f8。

為了防止偶然性帶來(lái)的誤差，程序獨(dú)立運(yùn)行50次，分別取函數(shù)在不同維數(shù)（D=10，D=30，D=50）下的平均值（Mean）和標(biāo)準(zhǔn)差（Std）進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如表2～表4所示。表中“+”表示γ=16時(shí)FPA算法的尋優(yōu)能力優(yōu)于其他兩個(gè)取值，“-”表示γ=16時(shí)FPA算法的尋優(yōu)能力劣于其他兩個(gè)取值，“=”表示γ=16時(shí)FPA算法的尋優(yōu)能力與其他兩個(gè)取值相當(dāng)。從表2中可以看出，當(dāng)D=10時(shí)，有19個(gè)“+”，2個(gè)“-”，3個(gè)“=”；從表3中得知，當(dāng)D=30時(shí)，有21個(gè)“+”，2個(gè)“-”，1個(gè)“=”；從表4中可以獲得，當(dāng)D=50時(shí)，有20個(gè)“+”，4個(gè)“-”，0個(gè)“=”。為此，從表2～表4可以看出，γ=16時(shí)FPA算法在12個(gè)函數(shù)上的尋優(yōu)能力遠(yuǎn)遠(yuǎn)優(yōu)于其他兩個(gè)取值。

圖1是在γ不同取值（初始值0.1，步長(zhǎng)0.05，終止值100）下的12個(gè)函數(shù)（分別獨(dú)立運(yùn)行20次，每次迭代次數(shù)為3 000）平均值變化曲線圖。由圖1更直觀地觀察到，除函數(shù)f3和f8外，γ=16時(shí)FPA算法的尋優(yōu)能力顯著好于其他兩個(gè)取值；對(duì)于函數(shù)f3，γ=16時(shí)FPA算法的尋優(yōu)能力明顯比γ=0.1好，但比γ=1稍差一些；對(duì)于函數(shù)f8，γ=16時(shí)FPA算法的尋優(yōu)能力都差于其他兩個(gè)取值。文中γ的最大值取100，是因?yàn)槿R維飛行步長(zhǎng)乘了一個(gè)參數(shù)α（α取值為0.01），這樣相當(dāng)于把步長(zhǎng)的縮放因子控制在(0,1]之間，不至于步長(zhǎng)過(guò)大，使FPA算法容易跳離最優(yōu)值而出現(xiàn)震蕩現(xiàn)象。

Table 1 Benchmark test functions表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

Table 2 Performance comparison of FPAwith different values ofγ(D=10)表2 γ取不同值FPA算法的性能比較（D=10）

Table 3 Performance comparison of FPAwith different values ofγ(D=30)表3 γ取不同值FPA算法的性能比較（D=30）

綜合表2～表4和圖1可知，對(duì)于絕大部分測(cè)試函數(shù)，γ=16時(shí)FPA算法的尋優(yōu)能力要比γ=0.1和γ=1好。

4 GMPFPA算法設(shè)計(jì)及實(shí)現(xiàn)

4.1 高斯變異

在智能優(yōu)化算法中引入變異算子，既可以增強(qiáng)種群的多樣性，又可以使算法避免陷入局部極小。柯西變異和高斯變異是智能優(yōu)化算法中兩種較常用的變異算子，這兩種變異算子都有各自的優(yōu)缺點(diǎn)?？挛髯儺惖乃阉鞣秶雀咚棺儺惖乃阉鞣秶?，但其過(guò)大的步長(zhǎng)容易跳離最優(yōu)值而產(chǎn)生較差的后代；而高斯變異在小范圍內(nèi)具有良好的搜索能力，這是因?yàn)槠淠芤暂^大的概率產(chǎn)生較小的變異值。同時(shí)，基本的花朵授粉算法采用了Levy飛行機(jī)制，使得其能搜索的范圍很大。綜上所述，本文把高斯變異引入到FPA算法中，以提高FPA算法的尋優(yōu)能力。

高斯分布又名正態(tài)分布，是一種在工程、數(shù)學(xué)及

物理等領(lǐng)域都非常重要的概率分布，是在許多統(tǒng)計(jì)測(cè)試中應(yīng)用最廣泛的一類分布。例如各種各樣的醫(yī)學(xué)現(xiàn)象（紅血蛋白量、紅細(xì)胞數(shù)以及實(shí)驗(yàn)中的隨機(jī)誤差等）、物理現(xiàn)象（比如光子計(jì)數(shù)）、心理學(xué)測(cè)試分?jǐn)?shù)都被發(fā)現(xiàn)近似地服從正態(tài)分布。而高斯變異就是在原有的個(gè)體上加上一個(gè)服從高斯分布的隨機(jī)擾動(dòng)向量來(lái)取代原先的個(gè)體。本文對(duì)FPA算法的全局搜索狀態(tài)實(shí)施高斯變異，以增強(qiáng)種群的多樣性，定義如下：

Table 4 Performance comparison of FPAwith different values ofγ(D=50)表4 γ取不同值FPA算法的性能比較（D=50）

Fig.1 Change curves of average values of functions with different values ofγ(D=30)圖1 函數(shù)平均值隨γ不同取值的變化曲線圖（D=30）

式中，N_iter為最大迭代次數(shù)；t為當(dāng)前的迭代次數(shù)；b∈(1,0]為遞減變量；N(0,1)為服從均值為0方差為1的高斯分布的隨機(jī)向量；是第i個(gè)個(gè)體在迭代次數(shù)為t時(shí)的狀態(tài)。

由式（4）可知，具有高斯變異的FPA算法能夠充分利用當(dāng)前種群中的每個(gè)個(gè)體的已有信息進(jìn)行擾動(dòng)，種群的多樣性得到增強(qiáng)，使算法能夠較好地避免陷入局部最優(yōu)，提升了全局尋優(yōu)能力，同時(shí)也加快了收斂速度。在本文算法中，如果轉(zhuǎn)換概率p＞rand，算法轉(zhuǎn)入全局搜索，則對(duì)當(dāng)前解進(jìn)行高斯變異。

4.2 Powell搜索法

Powell法又稱鮑威爾共軛方向法或方向加速法，它不必求函數(shù)導(dǎo)數(shù)值而是計(jì)算目標(biāo)函數(shù)值來(lái)構(gòu)造共軛搜索方向的一種共軛搜索方向法，被公認(rèn)為目前直接搜索法（模式搜索法、單純形搜索法、Powell法等）中最有效的算法之一。Powell法在每一階段的搜索過(guò)程是：首先依次沿n個(gè)已知的方向搜索，得到下一次搜索的基點(diǎn)，然后沿相鄰兩個(gè)基點(diǎn)的連線方向搜索得到新的基點(diǎn)，并用這個(gè)方向取代前面的n個(gè)方向之一。其本質(zhì)是一種搜索—試探—前進(jìn)[16]的反復(fù)過(guò)程。Powell算法具體實(shí)現(xiàn)過(guò)程如下。

步驟1給定初始點(diǎn)x(0)，n個(gè)線性無(wú)關(guān)的初始搜索方向d(0),d(1),…,d(n-1)及精度ε>0，令k=0。

步驟2 從x(0)出發(fā)，依次沿d(0),d(1),…,d(n-1)進(jìn)行一維搜索：

步驟5調(diào)整搜索方向，求出tn，滿足f(x(n)+tnd(n))= minf(x(n)+td(n))，得到x(0)=x(n)+tnd(n)，k=0，返回步驟2。若j＜n-1，令j=j+1，轉(zhuǎn)向步驟2；否則轉(zhuǎn)向步驟3。

步驟3 令d(n)=x(n)-x(0)，如果||d(n)||<ε，停止迭代，輸出解x(n)，否則轉(zhuǎn)步驟4。

步驟4求整數(shù)m，使得：

4.3 GMPFPA算法思想

由于基本花朵授粉算法存在收斂精度低，后期收斂速度慢，易陷入局部極小等缺陷，同時(shí)鑒于高斯變異能夠增加種群的多樣性，Powell法具有強(qiáng)大的局部尋優(yōu)能力優(yōu)點(diǎn)，本文把高斯變異和Powell法融入到花朵授粉算法。改進(jìn)算法（GMPFPA）思想是：當(dāng)?shù)螖?shù)小于等于總迭代次數(shù)一半時(shí)，只執(zhí)行帶高斯變異的FPA算法進(jìn)行全局尋優(yōu)搜索，當(dāng)?shù)螖?shù)超過(guò)總迭代次數(shù)一半后，會(huì)得到一個(gè)更優(yōu)的種群。在算法的進(jìn)化后期，即[N_iter/2]+1（其中N_iter為總的迭代次數(shù)）至N_iter，將執(zhí)行帶有Powell法且具有高斯變異的PFA算法。在進(jìn)化過(guò)程中，先用帶高斯變異的PFA算法進(jìn)行全局搜索并得到一個(gè)新的進(jìn)化群體，然后對(duì)新種群中的每個(gè)個(gè)體分別產(chǎn)生一個(gè)隨機(jī)數(shù)r(r∈(0,1))，若r＜p1，則Powell法以該個(gè)體的位置為初始值，進(jìn)行局部尋優(yōu)。

4.4 GMPFPA算法流程

步驟1對(duì)GMPFPA算法的各個(gè)參數(shù)進(jìn)行初始化，包括花朵種群數(shù)sizepop、轉(zhuǎn)換概率p、縮放因子γ、維數(shù)D等參數(shù)。

步驟2對(duì)花朵（對(duì)應(yīng)目標(biāo)函數(shù)的解）所在目標(biāo)函數(shù)搜索空間的位置進(jìn)行隨機(jī)初始化，并計(jì)算每個(gè)解的適應(yīng)度值。

步驟3求解出當(dāng)前的全局最優(yōu)值和其對(duì)應(yīng)的最優(yōu)解。

步驟4由條件p＞rand來(lái)判斷是否按式（2）、（4）、（5）、（9）對(duì)解進(jìn)行更新，并對(duì)解進(jìn)行越界處理：

步驟5由判斷條件p＜rand來(lái)決定是否按式（3）對(duì)解進(jìn)行更新，并對(duì)解進(jìn)行越界處理。

步驟6對(duì)步驟4或者步驟5新解對(duì)應(yīng)的適應(yīng)度值進(jìn)行評(píng)估，若優(yōu)，則更新當(dāng)前解和當(dāng)前適應(yīng)度值，否則保留當(dāng)前解和當(dāng)前適應(yīng)度值。

步驟7若t＞[N_iter/2]，則轉(zhuǎn)步驟8，否則轉(zhuǎn)步驟4。

步驟8利用Powell法對(duì)新種群進(jìn)行局部尋優(yōu)，若當(dāng)前的最優(yōu)值和最優(yōu)解優(yōu)于以前的最優(yōu)值和最優(yōu)解，則用當(dāng)前的最優(yōu)值和最優(yōu)解替換以前的最優(yōu)值和最優(yōu)解，否則保留原有的最優(yōu)值和最優(yōu)解。

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

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

為了驗(yàn)證本文算法的有效性和優(yōu)越性，采用第3章同樣的12個(gè)經(jīng)典函數(shù)進(jìn)行測(cè)試，并與FPA、GMFPA（flower pollination algorithm combination with Gauss mutation）以及PFPA（flower pollination algorithm combination with Powell search method）進(jìn)行比較。實(shí)驗(yàn)測(cè)試環(huán)境同3.1節(jié)。算法中的參數(shù)設(shè)置為：縮放因子γ=16，轉(zhuǎn)換概率p=0.2[14]，λ=1.5，Powell法中的判斷概率p1=0.05。

下面從算法的收斂精度、收斂速度、時(shí)間復(fù)雜度與參考文獻(xiàn)進(jìn)行對(duì)比實(shí)驗(yàn)，從而驗(yàn)證本文算法的有效性和優(yōu)越性。

4.5.1 固定迭代次數(shù)的收斂精度對(duì)比

在實(shí)驗(yàn)中，為了防止偶然性帶來(lái)的誤差和確保評(píng)價(jià)的客觀性及公平性，4種算法都獨(dú)立運(yùn)行50次，算法的種群數(shù)都取20，最大迭代次數(shù)為3 000。

實(shí)驗(yàn)仿真結(jié)果如表5所示。從表5中可知，與FPA、GMFPA、PFPA相比，除函數(shù)f4外，GMPFPA算法的收斂精度明顯好于其他3種算法，且其中f8與f10兩個(gè)函數(shù)，GMPFPA算法能夠找到理論最優(yōu)值。雖然GMFPA算法也能找到理論最優(yōu)值，但對(duì)于函數(shù)f10，GMPFPA算法的平均值、最差值及標(biāo)準(zhǔn)差比GMFPA算法分別提高了1個(gè)數(shù)量級(jí)和2個(gè)數(shù)量級(jí)，而其他兩種算法沒(méi)找到理論最優(yōu)值。說(shuō)明本文把高斯變異和Powell法一起融入到FPA算法中，是行之有效的，也驗(yàn)證了本文算法的優(yōu)越性。另外從表5中可以看出，在12個(gè)測(cè)試函數(shù)中，其中有9個(gè)函數(shù)FPA算法的收斂精度排名最后，只有函數(shù)f6、f11及f12排名第三，從而說(shuō)明本文分別把高斯變異和Powell法引入到FPA算法中是可行的。對(duì)于函數(shù)f1～f3、f5～f12，GMPFPA算法的尋優(yōu)能力（最優(yōu)值、平均值、最差值及標(biāo)準(zhǔn)差）優(yōu)于其他3種算法。這表明無(wú)論從尋優(yōu)精度、收斂速度，還是魯棒性，GMPFPA算法都取得較大幅度的提高，同時(shí)也說(shuō)明GMPFPA算法在搜索過(guò)程中在一定程度上更能有效地避免陷入局部最優(yōu)，體現(xiàn)了本文算法的優(yōu)越性。

由于篇幅所限，為了直觀地反映4種算法的收斂精度和收斂速度，本文畫出了8個(gè)函數(shù)的收斂曲線圖。圖2（a）～（h）分別是4種算法在維數(shù)30時(shí)的不同測(cè)試函數(shù)收斂曲線。從圖2中可以獲得，GMPFPA算法具有更高的收斂精度和更快的收斂速度。尤其從圖2（f）、（h）中可以得知，GMPFPA算法以較少的迭代次數(shù)就找到了理論最優(yōu)值，雖然GMFPA算法也能找到理論最優(yōu)值，但迭代次數(shù)比GMPFPA算法多，其他兩種算法無(wú)法找到理論最優(yōu)值。這表明GMPFPA算法的尋優(yōu)精度提高了，優(yōu)化過(guò)程提速了。同時(shí)，從圖2（a）、（b）、（f）、（g）和（h）可以看出，PFPA算法明顯陷入了局部最優(yōu)，而GMPFPA算法能很好地跳出局部最優(yōu)。說(shuō)明引入高斯變異能夠有效地使算法較好地避免陷入局部最優(yōu)，提升了全局尋優(yōu)能力，同時(shí)也加快了收斂速度，從而佐證了GMPFPA算法的優(yōu)越性。

綜上所述，GMPFPA算法與FPA、GMFPA、PFPA算法相比，尋優(yōu)能力得到了明顯提高，也驗(yàn)證了GMPFPA算法是有效可行的。

4.5.2 固定收斂精度的收斂速度對(duì)比

為了進(jìn)一步驗(yàn)證本文算法的有效性和優(yōu)越性，下面每個(gè)函數(shù)在收斂精度固定的情況下，獨(dú)立運(yùn)行50次，取其收斂率、最小收斂代數(shù)及平均收斂代數(shù)與PFPA、GMFPA和FPA算法進(jìn)行比較，其仿真結(jié)果如表6所示。實(shí)驗(yàn)參數(shù)設(shè)置為：每種算法的種群數(shù)為20，函數(shù)維數(shù)為10，最大迭代次數(shù)設(shè)為2 500，在實(shí)驗(yàn)

中迭代次數(shù)超過(guò)這個(gè)值，認(rèn)為尋優(yōu)失敗。表中“—”表示尋優(yōu)失敗。

Table 5 Convergence accuracy comparison of 4 algorithms in a fixed number of iterations表5 4種算法在固定迭代次數(shù)的收斂精度對(duì)比

Fig.2 Convergence curves of 8 functions（D=30）圖2 8個(gè)函數(shù)的收斂曲線（D=30）

從表6中可知，對(duì)于函數(shù)f1～f2、f5～f12，GMPFPA算法的最小收斂代數(shù)、平均收斂代數(shù)及收斂率都優(yōu)于PFPA、GMFPA和FPA算法；對(duì)于函數(shù)f3，GMPFPA算法的最小收斂代數(shù)略差于GMFPA算法，但平均收斂代數(shù)好于GMFPA算法，且GMPFPA算法的最小收斂代數(shù)、平均收斂代數(shù)及收斂率都優(yōu)于PFPA和FPA算法；對(duì)于函數(shù)f4，GMPFPA算法的平均收斂代數(shù)略差于GMFPA算法，但最小收斂代數(shù)比GMFPA算法好，而PFPA和FPA算法無(wú)法收斂到目標(biāo)精度。綜合圖2和表6，實(shí)驗(yàn)結(jié)果表明，本文算法的收斂速度、魯棒性得到較好的提升，進(jìn)一步說(shuō)明了本文算法的優(yōu)越性和有效可行性。

4.5.3 算法的時(shí)間復(fù)雜度對(duì)比

對(duì)于一種改進(jìn)的群智能優(yōu)化算法，一方面尋優(yōu)性能上要求比基本算法有較大的提高，同時(shí)也要求時(shí)間復(fù)雜度不能太高。為了全面地反映本文算法在時(shí)間復(fù)雜度上的可行性，本文采用了上述12個(gè)測(cè)試函數(shù)在不同維數(shù)上進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)參數(shù)設(shè)置同4.5.1小節(jié)，實(shí)驗(yàn)結(jié)果如表7所示。從表7中可以獲得，GMPFPA算法的最小運(yùn)行時(shí)間、平均運(yùn)行時(shí)間都比較短，但比FPA算法稍長(zhǎng)一些，這表明本文算法是可行的。

Table 6 Convergence speed comparison of 4 algorithms in a fixed accuracy表6 4種算法在固定精度下的收斂速度對(duì)比

4.5.4 與新近參考文獻(xiàn)算法的尋優(yōu)能力比較

在實(shí)際工程應(yīng)用中，利用啟發(fā)式群智能算法對(duì)多峰、高維復(fù)雜優(yōu)化問(wèn)題進(jìn)行優(yōu)化時(shí)，普遍存在收斂精度低，優(yōu)化后期收斂速度慢，易陷入局部極小等問(wèn)題。為了進(jìn)一步驗(yàn)證本文算法在優(yōu)化高維單峰、高維多峰及低維函數(shù)時(shí)的優(yōu)越性，突出本文算法的尋優(yōu)性能，將GMPFPA算法和參考文獻(xiàn)算法的優(yōu)化性能進(jìn)行對(duì)比。鑒于篇幅限制，將GMPFPA算法分別與新近具有代表性的參考文獻(xiàn)[12，14]算法進(jìn)行比較，且比較函數(shù)是來(lái)自參考文獻(xiàn)中的部分函數(shù)。為了比較的公平性，本節(jié)的實(shí)驗(yàn)參數(shù)設(shè)置不同于第3章和第4.5.1小節(jié)，本節(jié)算法的實(shí)驗(yàn)參數(shù)設(shè)置（如種群數(shù)為50或30）跟參考文獻(xiàn)一致，且比較函數(shù)取自參考文獻(xiàn)。與文獻(xiàn)[12]對(duì)照時(shí)，其對(duì)比函數(shù)來(lái)自參考文獻(xiàn)[12]，其中f4～f5為高維單峰函數(shù)，f7～f10為高維多峰函數(shù)，f11～f12為低維函數(shù)，仿真實(shí)驗(yàn)結(jié)果如表8所示，其中DDIFPA（FPA with dimension by dimension improvement）的數(shù)據(jù)來(lái)源于參考文獻(xiàn)[12]。從表8中可以獲知，本文算法優(yōu)化能力要優(yōu)于DDIFPA算法，特別是函數(shù)f11～f12，本文算法能找到理論最優(yōu)值，而DDIFPA算法沒(méi)有，且本文算法的標(biāo)準(zhǔn)差分別高于DDIFPA算法3個(gè)數(shù)量級(jí)和10個(gè)數(shù)量級(jí)。和參考文獻(xiàn)[14]對(duì)比，其比較函數(shù)取自文獻(xiàn)[14]，f1、f6為高維單峰函數(shù)，f8、f10、f11為高維多峰函數(shù)，實(shí)驗(yàn)對(duì)比結(jié)果如表9所示，其中MGOFPA（modified generalised opposition-based FPA）的實(shí)驗(yàn)數(shù)據(jù)來(lái)自于參考文獻(xiàn)[14]。從表9中可知，對(duì)函數(shù)f8和f11，本文算法的標(biāo)準(zhǔn)差要略差于MGOFPA算法，但最優(yōu)值要好于MGOFPA算法，而其余3個(gè)函數(shù)，本文算法的尋優(yōu)性能顯著優(yōu)于MGOFPA算法。

Table 7 Comparison of running time between GMPFPAand FPA表7GMPFPA與FPA算法的運(yùn)行時(shí)間對(duì)比

綜上所述，本文算法不僅是在高維單峰函數(shù)，還是在高維多峰函數(shù)、低維函數(shù)上的優(yōu)化能力要優(yōu)于參考文獻(xiàn)[12,14]，進(jìn)一步佐證了本文算法的優(yōu)越性和可行性。

Table 8 Comparison of optimization performance between GMPFPAand DDIFPA表8GMPFPA與DDIFPA算法的優(yōu)化性能對(duì)比

Table 9 Comparison of optimization performance between GMPFPAand MGOFPA表9GMPFPA與MGOFPA算法的優(yōu)化性能對(duì)比

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

本文提出了一種融合高斯變異和Powell法的花朵授粉算法。主要?jiǎng)?chuàng)新點(diǎn)有：（1）對(duì)基本花朵授粉算法中的步長(zhǎng)縮放因子γ的取值進(jìn)行了修正，提高了算法的尋優(yōu)能力；（2）把高斯變異引入到基本花朵授粉算法中，增強(qiáng)了種群的多樣性，較好地使算法在一定程度上避免陷入局部極小，提高了算法的收斂精度，加快了算法的收斂速度；（3）在算法中融入了Powell法，提升了算法的局部開(kāi)發(fā)能力。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法的尋優(yōu)能力比基本的花朵授粉算法有較大的提高，也驗(yàn)證了改進(jìn)算法的有效性和優(yōu)越性。

在今后的研究中，討論p是否可以以更復(fù)雜的形式變化，并將花朵授粉算法應(yīng)用于組合優(yōu)化等領(lǐng)域，同時(shí)從理論上對(duì)其收斂性進(jìn)行論證。

[1]Yang Xinshe.Flower pollination algorithm for global optimization[C]//LNCS 7445:Proceedings of the 11th Internation Conference on Unconventional Computation and Natural Computation,Orléan,France,Sep 3-7,2012.Berlin,Heidelberg:Springer,2012:240-249.

[2]Kennedy J,Eberhart R.Particle swarm optimization[C]// Proceedings of the 1995 IEEE International Conference on Neural Networks,Perth,Nov 27-Dec 1,1995.Piscataway, USA:IEEE,1995:1942-1948.

[3]Holland J.Adaptation in natural and artificial systems[M]. Cambridge,USA:MIT Press,1992.

[4]Yang Xinshe,Mehmet K,He Xingshe.Multi-objective flower algorithm for optimization[J].Procedia Computer Science, 2013,18(1):861-868.

[5]Bekdas G,Nigdeli S,Yang Xinshe.Sizing optimization of truss structures using flower pollination algorithm[J].Applied Soft Computing,2015,37(C):322-331.

[6]Bensouyad M,Saidouni D.A discrete flower pollination algorithm for graph coloring problem[C]//Proceedings of the 2015 IEEE International Conference on Cybernetics,Gdynia,Poland, Jun 24-26,2015.Piscataway,USA:IEEE,2015:151-155.

[7]Alam D F,Yousri D A,Eteiba M B.Flower pollination algo-rithm based solar PV parameter estimation[J].Energy Conversion and Management,2015,101:410-422.

[8]Dubey H M,Pandit M,Panigrahi B K.Hybrid flower pollination algorithm with time-varying fuzzy selection mechanism for wind integrated multi-objective dynamic economic dispatch[J].Renewable Energy,2015,83:188-202.

[9]Jiao Qinglong,Xu Da,Li Chuang.Product assembly sequence planning based on flower pollination algorithm[J/OL].Computer Integrated Manufacturing Systems(2015-10-30)[2015-12-15].http://www.cnki.net/kcms/detail/11.3619.TP.20151030. 1647.012.html.

[10]Yang Xinshe,González J R,Pelta D A,et al.A new metaheuristic bat-inspired algorithm[C]//Studies in Computational Intelligence 284:Proceedings of the 2010 Nature Inspired Cooperative Strategies for Optimization,Granada,Spain,May 12-14,2010.Berlin,Heidelberg:Springer,2010:65-74.

[11]Abdel-Raouf O,Abdel-Baset M,El-Henawy I.A new hybrid flower pollination algorithm for solving constrained global optimization problems[J].International Journal of Applied Operational Research,2014,4(2):1-13.

[12]Wang Rui,Zhou Yongquan.Flower pollination algorithm with dimension by dimension improvement[J].Mathematical Problems in Engineering,2014(4):1-9.

[13]Lenin K,Reddy B R,Kalavathi M S.Shrinkage of active power loss by hybridization of flower pollination algorithm with chaotic harmony search algorithm[J].Control Theory and Informatics,2014,4(8):31-38.

[14]Draa A.On the performances of the flower pollination algorithm-qualitative and quantitative analyses[J].Applied Soft Computing,2015,34:349-371.

[15]Mirjalili S,Mirjalili S M,Lewis A.Grey wolf optimizer[J]. Advances in Engineering Software,2014,69(3):46-61.

[16]Gong Chun,Wang Zhenglin.Proficient in MATLAB optimization[M].Beijing:Electronic Industry Press,2009.

附中文參考文獻(xiàn)：

[9]焦慶龍,徐達(dá),李闖.基于花朵授粉算法的產(chǎn)品裝配序列規(guī)劃[J/OL].計(jì)算機(jī)集成制造系統(tǒng)(2015-10-30)[2015-12-15]. http://www.cnki.net/kcms/detail/11.3619.TP.20151030.1647.012.html.

[16]龔純,王正林.精通MATLAB最優(yōu)化計(jì)算[M].北京:電子工業(yè)出版社,2009.

XIAO Huihui was born in 1977.He is a Ph.D.candidate at Jiangxi University of Finance and Economics.Now he is an associate professor at Hechi University.His research interests include intelligent computing and sentiment analysis.

肖輝輝（1977—），男，江西吉安人，江西財(cái)經(jīng)大學(xué)博士研究生，河池學(xué)院副教授，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，情感分析。

WAN Changxuan was born in 1962.He received the Ph.D.degree from Huazhong University of Science and Technology in 2003.Now he is a professor and Ph.D.supervisor at Jiangxi University of Finance and Economics,and the senior member of CCF.His research interests include Web data management,information retrieval,data mining and sentiment analysis.

萬(wàn)常選（1962—），男，江西新建人，2003年于華中科技大學(xué)獲得博士學(xué)位，現(xiàn)為江西財(cái)經(jīng)大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)閃eb數(shù)據(jù)管理，信息檢索，數(shù)據(jù)挖掘，情感分析。

DUAN Yanming was born in 1978.She received the M.S.degree in computer application from Jiangxi University of Science and Technology in 2009.Now she is a lecturer at Hechi University.Her research interest is intelligent computing.

段艷明（1978—），女，江西吉安人，2009年于江西理工大學(xué)獲得碩士學(xué)位，現(xiàn)為河池學(xué)院講師，主要研究領(lǐng)域?yàn)橹悄苡?jì)算。

YU Cong was born in 1992.He is an M.S.candidate at Jiangxi University of Finance and Economics.His research interest is sentiment analysis.

喻聰（1992—），男，江西南昌人，江西財(cái)經(jīng)大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)榍楦蟹治觥?/p>

Flower Pollination Algorithm Combination with Gauss Mutation and Powell Search Method*

XIAO Huihui1,2,WAN Changxuan1+,DUAN Yanming2,YU Cong1
1.School of Information and Technology,Jiangxi University of Finance and Economics,Nanchang 330013,China
2.College of Computer and Information Engineering,Hechi University,Yizhou,Guangxi 546300,China
+Corresponding author:E-mail:wanchangxuan@263.net

Flower pollinate algorithm(FPA)is a novel swarm intelligence optimization algorithm which is proposed recently,and it has been widely researched and used because of its advantages of solving the balance problem of local search and global search,and having less parameters,being implemented easily and so on.However,there are less current researches on the parameter,and the speed of convergence in the later stage is slow,what is more,it is easy to fall into local optimizations,which incline to restrict the application of the FPA.In order to improve the overall perfor-mance of the FPA,firstly,this paper modifies the scaling factor of the control step size.Secondly,this paper proposes a hybrid algorithm GMPFPA(flower pollination algorithm combination with Gauss mutation and Powell search method). The Gauss mutation is utilized to perturb the global search of the GMPFPA,which enhances the diversity of population of the GMPFPA,and improves the global detection ability of the GMPFPA,and then the strong local search capability of the Powell search method is introduced to enhance the local development ability of the hybrid algorithm. Through the comparison experiment of 12 high dimensional classical test functions,the effectiveness and superiority of the improved algorithm are verified.

Gauss mutation;flower pollination algorithm(FPA);Powell method;optimum value;optimization ability

10.3778/j.issn.1673-9418.1601003

A

：TP301.6

*The National Natural Science Foundation of China under Grant No.F020204(國(guó)家自然科學(xué)基金);the Natural Science Foundation of Guangxi under Grant No.2013GXNSFBA019022(廣西自然科學(xué)基金);the University Science Foundation of Guangxi under Grant Nos.KY2015LX332,KY2015LX334(廣西高?？茖W(xué)技術(shù)研究項(xiàng)目);the Graduate Innovation Project of Jiangxi Province under Grant No.YC2015-B054(江西省研究生創(chuàng)新項(xiàng)目);the Project of Key Laboratory for Computer Network and New Technology of Software of Hechi University under Grant No.2013-03(河池學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)與軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目);the Education Reform Project of Hechi University under Grant No.2014EB022(河池學(xué)院教改項(xiàng)目);the Science Foundation of Hechi University under Grant No.XJ2015QN003(河池學(xué)院基金項(xiàng)目).

Received 2016-01,Accepted 2016-03.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-03-07,http://www.cnki.net/kcms/detail/11.5602.TP.20160307.1710.016.html

XIAO Huihui,WANG Changxuan,DUAN Yanming,et al.Flower pollination algorithm combination with Gauss mutation and Powell search method.Journal of Frontiers of Computer Science and Technology,2017, 11(3)：478-490.