井福榮，　郭肇祿， 羅會(huì)蘭（江西理工大學(xué)，.信息工程學(xué)院；.理學(xué)院，江西 贛州341000）

一種應(yīng)用精英混沌搜索的函數(shù)優(yōu)化算法

井福榮a，郭肇祿b， 羅會(huì)蘭a
（江西理工大學(xué)，a.信息工程學(xué)院；b.理學(xué)院，江西 贛州341000）

針對基本FPA算法在求解復(fù)雜工程優(yōu)化問題時(shí)存在收斂速度慢的缺點(diǎn)，提出應(yīng)用精英混沌搜索的花粉授粉算法（CSFPA）.CSFPA算法在搜索過程中從當(dāng)前種群中隨機(jī)選擇出一個(gè)個(gè)體，對其執(zhí)行精英混沌搜索操作，從而加快算法的收斂速度.將提出的CSFPA算法與基本FPA算法在幾個(gè)國際上常用的基準(zhǔn)測試問題上進(jìn)行了比較實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明CSFPA算法能夠在大多數(shù)測試問題上比基本FPA算法獲得更優(yōu)的結(jié)果.

優(yōu)化算法；演化算法；混沌搜索；花粉授粉算法

0　引言

函數(shù)優(yōu)化問題的優(yōu)劣直接影響科學(xué)研究的成敗，因此在現(xiàn)代科學(xué)研究中有著十分重要的地位.花粉授粉算法［1］（Flower pollination algorithm，F(xiàn)PA）是2012年由劍橋大學(xué)學(xué)者Yang提出的一種新的系統(tǒng)優(yōu)化算法，該算法基于模擬現(xiàn)實(shí)世界中植物花朵授粉過程而提出.一般而言，花粉授粉有異花授粉（cross-pollination）和自花授粉（self-pollination）兩種形式，異花授粉是通過昆蟲采粉作為傳播方式，實(shí)現(xiàn)雌性花朵和雄性花朵之間相對遠(yuǎn)距離的授粉，也即交叉授粉.由于昆蟲飛行距離相對較遠(yuǎn)，因此異花授粉可以在較遠(yuǎn)距離發(fā)生，這種方式也稱之為全局授粉.自花授粉是植物成熟的花粉粒傳到自身的柱頭上或同一種植物的不同花朵上進(jìn)行授粉的過程.相對而言自花授粉也稱之為局部授粉.基于上述思想，F(xiàn)PA算法對以上兩種授粉方式分別設(shè)計(jì)了交叉授粉算子和自花授粉算子來求解優(yōu)化問題，同時(shí)得到廣大學(xué)者、研究人員的關(guān)注.

由于花粉授粉算法在求解優(yōu)化問題過程中，也存在一些收斂速度慢等缺點(diǎn)，研究人員提出了許多改進(jìn)的FPA算法，并在相關(guān)研究領(lǐng)域的應(yīng)用中取得了很好的效果.Yang等應(yīng)用FPA算法（MOFPA）［2］進(jìn)行多目標(biāo)問題的求解，其做法是通過隨機(jī)權(quán)數(shù)把多個(gè)優(yōu)化問題變換成單一問題來進(jìn)行求解，在4組及以上優(yōu)化問題基準(zhǔn)測試的實(shí)驗(yàn)結(jié)果表明提出的MOFPA算法能夠很好解決多目標(biāo)優(yōu)化問題.Wang等［3］為了提高FPA的運(yùn)算效率及性能提出了一種優(yōu)化FPA算法 （DDIFPA）.DDIFPA結(jié)合逐維搜索策略和鄰域搜索策略，提高了算法在搜索最優(yōu)解的速度和解的質(zhì)量.標(biāo)準(zhǔn)測試函數(shù)的實(shí)驗(yàn)表明DDIFPA具有明顯的搜索性能優(yōu)勢.Prathiba等［4］成功將FPA算法應(yīng)用于求解經(jīng)濟(jì)負(fù)荷分配問題中，取得了良好的效果.Abdel-Raouf等［5］將FPA融合到粒子群優(yōu)化算法（PSO）中，提出了一種混合FPA算法 （FPPSO），并應(yīng)用于求解約束優(yōu)化問題中；Chakraborty等［6］將FPA融合到差分進(jìn)化算法中，提出了一種花粉授粉混合算法（DE-FPA）；Rodrigues等［7］提出了二進(jìn)制FPA算法（BFPA），并有效地解決了求解特征選擇問題；Dubey等［8］為了求解經(jīng)濟(jì)調(diào)度問題，提出了一種生物學(xué)啟發(fā)的改進(jìn)FPA算法（MFPA），在MFPA算法中，通過使用一個(gè)參數(shù)進(jìn)行搜索步長的調(diào)節(jié)，該參數(shù)可大可小以便提高搜索效率和精確度.同時(shí)引入了一個(gè)可在全局范圍內(nèi)進(jìn)行最優(yōu)解局部搜索的搜索參數(shù).肖輝輝等［9］為了減少FPA算法陷入局部最優(yōu)值的概念，將模擬退火的思考融合到FPA算法.接著，肖輝輝等［10］為了提高FPA算法的局部搜索能力，將復(fù)合形法引入到花粉授粉算法中.井福榮等［11］將反向?qū)W習(xí)策略融合到FPA算法，以此提FPA算法的搜索性能.

綜上所述，F(xiàn)PA是一種性能優(yōu)越的智能優(yōu)化算法，在工程優(yōu)化問題的求解中具有一定優(yōu)勢.但國內(nèi)外對FPA的研究還剛剛興起，F(xiàn)PA算法的性能提高還有很大的空間，本文針對基本FPA算法在解決復(fù)雜優(yōu)化工程實(shí)踐問題時(shí)存在著收斂速度慢的缺點(diǎn)［8］，將精英混沌搜索策略引入到FPA算法中，提出了一種應(yīng)用精英混沌搜索的花粉授粉算法（CSFPA）.在CSFPA算法的搜索過程中，從當(dāng)前種群中隨機(jī)選擇出一個(gè)個(gè)體，對其執(zhí)行精英混沌搜索操作，從而加快算法的收斂速度.在數(shù)值實(shí)驗(yàn)中，利用一些演化計(jì)算領(lǐng)域中廣泛使用的基準(zhǔn)測試函數(shù)做了比較實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了CSFPA算法的有效性.

1　花粉授粉算法

由于現(xiàn)實(shí)世界中的花粉授粉過程是一個(gè)極其復(fù)雜的生理過程.使用計(jì)算機(jī)完全實(shí)現(xiàn)花粉授粉過程將導(dǎo)致非常高的時(shí)間復(fù)雜度，因此FPA算法只是對花粉授粉過程的核心思想進(jìn)行模擬.

首先花粉授粉算法隨機(jī)產(chǎn)生一個(gè)含有NP個(gè)個(gè)體的種群P（t）=｛Xti｝用于算法的初始化，其中Xti=［xti，1，xti，2，…，xti，j，…，xti，D］，j=1，2，…，D；i=1，2，…，NP，NP為種群大小，D表示求解問題的維數(shù)，t代表當(dāng)前進(jìn)化代數(shù)［1］.其次，該算法一直循環(huán)執(zhí)行交叉授粉和自花授粉兩個(gè)過程直到達(dá)退出條件為止.

在算法的執(zhí)行過程中，F(xiàn)PA以初始值Pc大小計(jì)算異花授粉過程，之后以1-Pc的大小計(jì)算自花授粉過程［1］.其中異花授粉按照如下公式計(jì)算［2］：

其中γ為縮放參數(shù)，一般建議設(shè)定其值為0.1［2］；L是一個(gè)隨機(jī)值，它服從指數(shù)為λ的Levy分布，一般建議設(shè)定其值為1.5［2］，XtBest代表局部最優(yōu)解.

自花授粉按照如下公式計(jì)算［2］：

其中ε∈［0，1］，并服從均勻分布，隨機(jī)整數(shù)j，k∈［1，NP］，并且滿足i≠j≠k.

FPA算法流程描述如圖1所示.在該算法中，首先隨機(jī)產(chǎn)生初始種群，評(píng)價(jià)每個(gè)個(gè)體的適應(yīng)值，然后循環(huán)執(zhí)行演化操作直到滿足終止條件.在演化操作循環(huán)中，首先定義隨機(jī)實(shí)數(shù)rp∈［0，1］并服從均勻分布，當(dāng)rp＜Pc時(shí)，則按公式（1）執(zhí)行交叉授粉操作算子，否則按公式（2）執(zhí)行自花授粉操作算子，然后再執(zhí)行選擇算子選擇出優(yōu)勝個(gè)體進(jìn)入下一代種群.

2　CSFPA算法

FPA已經(jīng)成功應(yīng)用到了一系列復(fù)雜工程優(yōu)化問題的求解中，并且獲得了滿足實(shí)際工程需求的優(yōu)化結(jié)果.然而在工程實(shí)踐中，研究人員發(fā)現(xiàn)基本FPA在求解高維、非線性等特性的復(fù)雜工程優(yōu)化問題時(shí)往往容易出現(xiàn)收斂速度慢的缺點(diǎn)，其主要原因是復(fù)雜工程優(yōu)化問題的搜索空間隨著問題維數(shù)的增長呈指數(shù)規(guī)模增長，面對著這種情形，基本FPA算法的局部搜索能力往往表現(xiàn)不足，從而導(dǎo)致算法很難有效地朝著全局最優(yōu)解的方向進(jìn)行搜索，無法逼近全局最優(yōu)解［10］.為了進(jìn)一步提高基本FPA算法的局部搜索能力，加快求解高維、非線性等特性的復(fù)雜工程優(yōu)化問題的收斂速度，將精英混沌局部搜索策略融合到基本FPA算法中，形成一種應(yīng)用精英混沌搜索的花粉授粉算法（CSFPA），在搜索過程中從當(dāng)前種群中隨機(jī)選擇出一個(gè)個(gè)體，對其執(zhí)行精英混沌局部搜索操作，從而有效地增強(qiáng)算法的開采能力，加快收斂速度.

圖1　　基本FPA算法的流程圖

2.1CSFPA的精英混沌搜索

混沌現(xiàn)象是自然界中廣泛存在的一種非線性系統(tǒng)，它具有遍歷性和初始值敏感性的特點(diǎn)［12］.利用混沌系統(tǒng)的這些特點(diǎn)，給定一個(gè)隨機(jī)初始值，設(shè)定足夠長的時(shí)間，混沌系統(tǒng)可以按照自身的運(yùn)動(dòng)規(guī)律，隨機(jī)遍歷系統(tǒng)內(nèi)的所有狀態(tài)［13］.許多研究人員將混沌系統(tǒng)的這種特性融合到智能優(yōu)化算法中，利用混沌運(yùn)動(dòng)規(guī)律來進(jìn)行局部搜索，從而加快算法的收斂速度，其中文獻(xiàn)［14］提出了一種帶有收縮機(jī)制的混沌搜索算子，該混沌搜索策略一方面利用混沌系統(tǒng)的遍歷性和初始值敏感性的特點(diǎn)，在當(dāng)前種群的搜索區(qū)域內(nèi)混沌采樣產(chǎn)生新個(gè)體，然后再將新個(gè)體與最優(yōu)個(gè)體進(jìn)行線性組合生成一個(gè)試驗(yàn)個(gè)體，然后將試驗(yàn)個(gè)體與最優(yōu)個(gè)體進(jìn)行競爭，淘汰兩者中的較差個(gè)體，保留優(yōu)勝個(gè)體.在傳統(tǒng)混沌搜索算子［14］的基礎(chǔ)上，進(jìn)一步提高其局部搜索能力，提出精英混沌搜索策略，利用種群中的優(yōu)質(zhì)個(gè)體所含的經(jīng)驗(yàn)信息來引導(dǎo)搜索方向，進(jìn)而加快算法的收斂效果及速度.

就具體精英混沌搜索算法的操作過程而言，通過隨機(jī)選擇確定一個(gè)個(gè)體Xr，再根據(jù)巴特萊法則［15］從當(dāng)前種群中選擇出前20%的精英個(gè)體，并計(jì)算出所選擇的精英個(gè)體的搜索區(qū)域的上界CA和CB下界:

在計(jì)算出當(dāng)種群中的精英個(gè)體的搜索上下界后，隨機(jī)產(chǎn)生一個(gè)混沌初始值K1，如果混沌初始值等于0.25，0.5或0.75，則重新產(chǎn)生直到它不等于0.25，0.5或0.75［14］：

在以后的每一次混沌搜索迭代中，混沌因子按Logsig混沌映射計(jì)算［14］：

其中n為本次混沌搜索的當(dāng)前迭代次數(shù)，在得到混沌因子后Kn，則按以下公式產(chǎn)生一個(gè)新個(gè)體：

其中a為［0，1］之間的隨機(jī)數(shù)，它決定著Xr個(gè)體與精英混沌搜索個(gè)體之間的權(quán)值；在計(jì)算出個(gè)體Un后，如果Un比Xr更優(yōu)，則用Un替換Xr，并停止執(zhí)行精英混沌搜索操作，否則保持Xr不變成，并一直執(zhí)行精英混沌搜索操作直至迭代次數(shù)達(dá)到預(yù)先設(shè)定的最大次數(shù).

2.2CSFPA的總體流程

為了提高基本FPA算法在求解復(fù)雜工程優(yōu)化問題時(shí)的收斂速度，將精英混沌局部搜索策略融合到基本FPA算法中，增強(qiáng)基本FPA的局部搜索能力.在CSFPA的搜索過程中，首先隨機(jī)選擇出一個(gè)個(gè)體，再找出當(dāng)前種群中的精英個(gè)體，并計(jì)算所找到的精英個(gè)體的搜索上下界，然后利用精英個(gè)體的有益信息以及混沌系統(tǒng)的遍歷性和初始值敏感性的特點(diǎn)在搜索空間中不斷產(chǎn)生新個(gè)體，從而在一定程度上提高算法的收斂速度.下面給出CSFPA算法具體實(shí)現(xiàn)過程，如下面算法所示.

算法：應(yīng)用精英混沌搜索的FPA算法（CSFPA）.

Step1:設(shè)置D，NP，Pc；Step2:當(dāng)前迭代初始值t=0，評(píng)判初始值FEs=0；Step3:對種群進(jìn)行初始化，對個(gè)體的適應(yīng)值進(jìn)行評(píng)判，設(shè)FEs=NP；

Step4:是否滿足終止條件？Step16：Step5；Step5:執(zhí)行基本FPA的計(jì)算步驟；Step6:隨機(jī)選擇出一個(gè)個(gè)體Xr；

Step7:從當(dāng)前種群中選擇出前20%的精英個(gè)體，并按公式（3）計(jì)算選擇的精英個(gè)體的搜索區(qū)域的上界和下界；

Step8:n=1；

Step9:按公式（4）產(chǎn)生混沌因子初始值；

Step10:按公式（6）對Xr執(zhí)行精英混沌搜索得到個(gè)體Un，并計(jì)算Un的適應(yīng)值；

Step11:如果Un比Xr更優(yōu)，則用Un替換Xr，并轉(zhuǎn)到Step15；否則轉(zhuǎn)到Step12；

Step12:n=n+1；

Step13:按公式（5）計(jì)算新的混沌因子；

Step14:如果n小于D/5，則轉(zhuǎn)到Step 10；否則轉(zhuǎn)到Step 15；

Step15:t=t+1，轉(zhuǎn)到Step4；

Step16:輸出最優(yōu)解，CSFPA算法結(jié)束.

3　數(shù)值實(shí)驗(yàn)

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

為了檢驗(yàn)CSFPA算法是否有效，本文選擇了10個(gè)Benchmark測試函數(shù)對算法CSFPA進(jìn)行性能分析.10個(gè)Benchmark測試函數(shù)的特性在表1中給出了詳細(xì)描述［16，17］.其中f1-f4為單峰函數(shù)，f5-f10為多峰函數(shù)，10個(gè)測試函數(shù)的維數(shù) D都為30維.

表1　Benchmark測試函數(shù)

在實(shí)驗(yàn)中，將CSFPA與FPA［1］進(jìn)行性能比較，在CSFPA中設(shè)置了與文獻(xiàn)［2］關(guān)于FPA算法相同的參數(shù).此外，對上述兩種算法的每次測試中，關(guān)于測試函數(shù)的結(jié)束條件設(shè)置上以400000作為評(píng)價(jià)次數(shù)，同時(shí)獨(dú)立進(jìn)行30次的實(shí)驗(yàn)驗(yàn)證，并把各算法所求解的實(shí)際最優(yōu)值與理論最優(yōu)值之間誤差進(jìn)行平均計(jì)算，將其結(jié)果和標(biāo)準(zhǔn)差作為評(píng)判算法優(yōu)劣的指標(biāo).

3.2實(shí)驗(yàn)結(jié)果

FPA和CSFPA兩種算法之間的對比實(shí)驗(yàn)結(jié)果圖2所示，其中FPA的實(shí)驗(yàn)結(jié)果來自文獻(xiàn)［11］，并對實(shí)驗(yàn)結(jié)果按照文獻(xiàn)［18］的方法進(jìn)行統(tǒng)計(jì)分析，設(shè)顯著性雙尾t的水平值為0.05，其中在統(tǒng)計(jì)意義上，“+”代表CSFPA算法優(yōu)于FPA，“-”表示FPA算法優(yōu)于CSFPA算尖，“≈”表示兩種算法無顯著性差別.根據(jù)表2中的結(jié)果可以得出，在大部分測試函數(shù)上CSFPA算法比FPA算法更優(yōu).具體而言，CSFPA在4個(gè)單峰測試函數(shù)f1-f4上都獲得了比FPA更優(yōu)的解；在6個(gè)多峰測試函數(shù)上，CSFPA在測試函數(shù)上f5，f6，f7，f8，f10獲得了比FPA更優(yōu)的解.實(shí)驗(yàn)結(jié)果表明精英混沌局部搜索操作加快了算法的收斂速度，從而有限的計(jì)算開銷下獲得更優(yōu)的解.

圖2　FPA和CSFPA的收斂狀態(tài)圖

表2　實(shí)驗(yàn)結(jié)果

為了進(jìn)一步比較FPA和CSFPA的收斂效率，圖2給出了FPA和CSFPA在幾個(gè)典型測試函數(shù)上的收斂曲線.從圖2中可知，CSFPA比FPA具有更快的收斂速度，這是由于精英混沌局部搜索操作加快了算法的收斂速度.

4　結(jié)束語

FPA是一種新近提出的函數(shù)優(yōu)化算法，它在求解許多復(fù)雜工程優(yōu)化問題中獲得了滿足實(shí)際工程需求的優(yōu)化結(jié)果，但許多研究人員發(fā)現(xiàn)基本FPA容易出現(xiàn)收斂速度慢的缺點(diǎn)，為了進(jìn)一步提高基本FPA的收斂速度，本文提出應(yīng)用精英混沌搜索的函數(shù)優(yōu)化算法（CSFPA）.在CSFPA的搜索過程中，隨機(jī)選擇出一個(gè)個(gè)體并對其執(zhí)行精英混沌搜索操作增強(qiáng)算法的局部搜索能力，從而加快收斂速度.通過10個(gè)基準(zhǔn)測試函數(shù)對CSFPA與基本FPA進(jìn)行對比測試實(shí)驗(yàn)，結(jié)果表明CSFPA算法能夠有效地改善FPA算法的收斂效率，同時(shí)CSFPA在大部分測試函數(shù)上解精度高于基本FPA的精度.

［1］Yang X S.Flower pollination algorithm for global optimization［M］.Unconventional Computation and Natural Computation，Lecture Notes in Computer Science，2012:240-249.

［2］Yang X S，Karamanoglu M，He X.Flower pollination algorithm:a novel approach for multiobjective optimization［J］.Engineering Optimization，2014，46（9）:1222-1237.

［3］Wang R，Zhou Y.Flower Pollination Algorithm with Dimension by Dimension Improvement［J］.Mathematical Problems in Engineering，2014:481791.

［4］Prathiba R，Moses M B，Sakthivel S.Flower pollination algorithm appliedfor different economicloaddispatchproblems［J］. International Journal of Engineering and Technology，2014，6（2）: 1009-1016.

［5］Abdel-Raouf O，Abdel-Baset M，El-henawy I.A new hybrid flowerpollinationalgorithmforsolvingconstrainedglobal optimizationproblems［J］.International Journal of Applied Operational Research，2014，4（2）:1-13.

［6］Chakraborty D，Saha S，Dutta O.DE-FPA:A hybrid differential evolution-flower pollination algorithm for function minimization［C］//International Conference on High Performance Computing and Applications，Bhubaneswar，India，2014.

［7］Rodrigues D，Yang X S，de Souza A N，et al.Binary flower pollination algorithm and its application to feature selection［M］. Recent AdvancesinSwarmIntelligenceandEvolutionary Computation.Springer，2015:85-100.

［8］Dubey H M，Pandit M，Panigrahi B K.A biologically inspired modifiedflower pollinationalgorithmforsolvingeconomic dispatchproblems inmodernpower systems［J］.Cognitive Computation，2015，7（5）：594-608.

［9］肖輝輝，萬常選，段艷明，等.基于模擬退火的花朵授粉優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2015，35（4）:1062-1066.

［10］肖輝輝，萬常選，段艷明.一種基于復(fù)合形法的花朵授粉算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2015，36（6）:1373-1378.

［11］井福榮，郭肇祿，羅會(huì)蘭.一種使用反向?qū)W習(xí)策略的改進(jìn)花粉授粉算法［J］.江西理工大學(xué)學(xué)報(bào)，2015，36（3）:101-106.

［12］徐丈星，耿志強(qiáng)，朱群雄，等.基于SQP局部搜索的混沌粒子群優(yōu)化算法［J］.控制與決策，2012，27（4）:557-561.

［13］龔安，呂倩，胡長軍，等.基于混沌萬有引力搜索算法的SVM參數(shù)優(yōu)化及應(yīng)用［J］.計(jì)算機(jī)科學(xué)，2015，42（4）:240-243.

［14］Jia D，Zheng G，Khan M K.An effective memetic differential evolution algorithm based on chaotic local search［J］.Information Sciences，2011，181（15）:3175-3187.

［15］田也壯.巴特萊法則二八定律與管理思想 ［J］.中國軟科學(xué)，1995，7:80-81.

［16］郭肇祿，吳志健，汪靖，等.一種基于精英云變異的差分演化算法［J］.武漢大學(xué)學(xué)報(bào)（理學(xué)版），2013，59（2）:117-122.

［17］Yao X，Liu Y，Lin G.Evolutionary programmingmade faster［J］. IEEE Transactions on Evolutionary Computation，1999，3（2）:82-102.

［18］Guo Z，Yue X，Zhang K，Deng C，Liu S.Enhanced social emotional optimisation algorithm with generalised oppositionbased learning［J］.International Journal of Computing Science and Mathematics，2015，6（1）:59-68.

An enhanced function optimization algorithm based on elite chaotic search

JING Furonga，GUO Zhaolub，LUO Huilana
（a.School of Information Engineering；b.Faculty of Science，JiangxiUniversity of Science and Technology，Ganzhou 341000，China）

Flower pollination algorithm（FPA）is an emerging function optimization algorithm.However，the traditional FPA tends to suffer from slow convergence when solving complex engineering optimization problems. Aiming at this weakness of the basic FPA，an enhanced flower pollination algorithm based on elite chaotic search（CSFPA）is proposed in this paper.In the evolution process，CSFPA randomly selects an individual to execute the elite chaotic search strategy，which can accelerate the convergence speed.In the experiments，the proposed CSFPA is compared with the basic FPA on several benchmark test problems.The experimental results validate the effectiveness of the proposed CSFPA.

optimization algorithm；evolutionary algorithm；chaotic search；flower pollination algorithm

TP181

A

2095-3046（2015）05-0074-06

10.13265/j.cnki.jxlgdxxb.2015.05.013

2015-09-10

江西省青年科學(xué)家（井岡之星）培養(yǎng)對象資助項(xiàng)目（20153BCB23010）

井福榮（1977-），男，講師，主要從事智能計(jì)算、數(shù)據(jù)挖掘等方面的研究，E-mail:jephirus@126.com.