李 航, 韓 祺

(沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034)

煙花算法與布谷鳥算法求解優(yōu)化問題的對比分析研究

李 航, 韓 祺

(沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034)

近年來,人工智能算法發(fā)展十分迅速,而且在很多領(lǐng)域都得到了廣泛的應(yīng)用,如系統(tǒng)控制、模式識別、生產(chǎn)調(diào)度、VLSI技術(shù)和計算機(jī)工程等。鑒于實(shí)際問題的復(fù)雜性、約束性、非線性、多極小、建模困難等特點(diǎn),提出了許多優(yōu)化算法。煙花算法和布谷鳥算法作為2種新型的進(jìn)化計算方法被廣泛的應(yīng)用在函數(shù)優(yōu)化方面。通過實(shí)驗(yàn)對這2種算法在求解不同問題時的性能進(jìn)行了系統(tǒng)的對比和分析,比較了2種算法在求解單峰和多峰問題上的性能差異。最后,又對其健壯性進(jìn)行分析,研究了不同參數(shù)對二者的影響,對煙花算法和布谷鳥算法的原理特點(diǎn)做了一個總結(jié),并討論算法的一些改進(jìn)方法,提高算法在以后實(shí)際工程中的應(yīng)用價值。

人工智能; 煙花算法; 布谷鳥算法; 性能對比

0 引 言

群體智能優(yōu)化算法[1-2]本質(zhì)是建立在生物智能或物理現(xiàn)象基礎(chǔ)上的隨機(jī)搜索算法, 群體智能優(yōu)化算法的基本信息是不同于傳統(tǒng)優(yōu)化算法,表現(xiàn)在4個方面[3-4]:1)在群體中的個體具有相互作用,呈分布式分布, 沒有中心控制主要點(diǎn), 個別個體出現(xiàn)故障并不能影響群體對優(yōu)化問題的求解, 具有較強(qiáng)的魯棒性;2)每個個體有局部搜素能力,按部就班的去做自己的工作, 所以群體智能的實(shí)現(xiàn)簡單、方便;3)群體智能占用資源較少,開銷較少, 易于擴(kuò)充;4)自組織性較強(qiáng), 即群體表現(xiàn)出的復(fù)雜性是通過簡單個體的交互表現(xiàn)出高度的智能。

群體智能優(yōu)化算法的基本理論是模擬實(shí)際生物群體生活中個體與個體之間的互相交流與合作, 用簡單、有限的個體行為與智能, 通過相互作用形成整個群體難以估量的整體能力。目前,有很多種群體智能算法,如人工神經(jīng)網(wǎng)絡(luò)、混沌、遺傳算法、進(jìn)化規(guī)劃、模擬退火、禁忌搜索及其混合優(yōu)化策略等,還有最近提出的頭腦風(fēng)暴算法[5]、智能水滴算法[6]、貓群算法[7]等。在群體智能優(yōu)化算法中的各個生物體都經(jīng)過人工處理, 個體不具有實(shí)際生物的體積和質(zhì)量, 其行為方式也是根據(jù)人們?yōu)榱私鉀Q問題的需要而進(jìn)行必要的加工處理。群體智能優(yōu)化算法的理論研究主要是研究算法特性, 改進(jìn)其不足, 提高性能。包括2方面的研究:一是從群體智能優(yōu)化算法的自身特性加以研究,改進(jìn)其性能;二是將群體智能優(yōu)化算法之間或與其他算法進(jìn)行結(jié)合, 通過算法之間的融合對算法加以改進(jìn), 產(chǎn)生新的混合智能算法。

1 煙花算法

根據(jù)群體行為的算法建模對于多維全局優(yōu)化問題是一個非常強(qiáng)大的計算工具,這些智能算法都是從生物,社會現(xiàn)象或其他自然法則衍生而來[8-9]。煙花算法是煙花在夜空爆炸中獲取的靈感,這種新型的算法被提出用來解決復(fù)雜函數(shù)的全局優(yōu)化問題。當(dāng)一個煙花爆炸時,圍繞著煙花充滿了一片火花。煙花的爆炸過程可以看成在局部空間圍繞一個特殊點(diǎn)的搜索,煙花從這個點(diǎn)爆炸發(fā)出火花。在煙花算法中,目標(biāo)就是尋找一個點(diǎn)xj來滿足f(xj)=y,且煙花在這個潛在空間中不斷地爆炸直到有一個目標(biāo)火花出現(xiàn)在點(diǎn)xj附近。

(a)—理想的爆炸; (b)—不理想的爆炸圖1 煙花爆炸類型Fig.1 Types of fireworks explosion

如果煙花爆炸設(shè)計的非常完美,對于位置的選擇有一個非常適合的方法,那么煙花算法一定是有效的。如果仔細(xì)觀察爆炸的煙花,會看到有2個不同的煙花行為。在一個好的爆炸中,無數(shù)的煙花碎片聚集且這些碎片集中在爆炸中心;不好的爆炸,很少一部分火花聚集,在空間中散亂分布。如圖1所示[10-11]。

最優(yōu)化問題的煙花算法如下:

最小化f(x)∈R,xmin≤x≤xmax,其中x=x1,x2,…,xd代表在潛在空間中的一個位置,f(x)是一個目標(biāo)函數(shù),xmin和xmax代表空間的上下界。

煙花算法流程如下:

1) 隨機(jī)選取n個煙花位置。

2) 在這n個位置分別隨機(jī)釋放n個煙花。

3) 對于每個煙花xj執(zhí)行:

a) 隨機(jī)選擇一個煙花xj。

b) 使用如下公式在爆炸的煙花中產(chǎn)生一個特定的碎片。

位置xi的選擇概率定義為:

5) 選擇最好的位置,保持迭代到下一次爆炸。

6) 結(jié)束。

獲得一個隨機(jī)爆炸碎片的位置偽代碼:

2)z=round(drand(0,1))。

4) 計算位移:h=Airand(-1,1)。其中Ai是每一個煙花爆炸的振幅。

7) 結(jié)束。

獲得一個特定爆炸碎片的位置偽代碼:

2) z=round(drand(0,1))。

4) 計算高斯爆炸的系數(shù):g=Gaussian(1,1)。

7) 結(jié)束。

2 布谷鳥搜索算法

布谷鳥算法[12-13]是一種新的元啟發(fā)優(yōu)化算法,靈感來自布谷鳥的繁殖行為,布谷鳥的育種習(xí)性對于研究這個算法非常的有必要。布谷鳥有很多不同于其他鳥類的特性,但是最主要的習(xí)性是具有侵略性的繁殖策略。一些布谷鳥把后代養(yǎng)育在公共的鳥巢中,甚至把其他的鳥蛋給移走來增加自己蛋的孵化概率。布谷鳥孵育寄生,把蛋寄生在其他鳥類的巢中。一些宿主做出不好的行為來反對入侵者或者直接參與斗爭。在這種情況下,宿主會把那些入侵者的蛋給扔掉;在一些其他情況下,友好的宿主會簡單的放棄它們的鳥巢并另建一個新的鳥巢。另外一些布谷鳥類,進(jìn)化成一種先進(jìn)的方式,雌性的布谷鳥會專業(yè)的模仿選擇宿主的蛋的樣式及顏色。這種做法降低了它們的蛋被扔掉的概率并且增加了孵化的幾率。

基于布谷鳥的這些習(xí)性,算法流程如圖2所示。盡管布谷鳥算法極力模仿布谷鳥孵育習(xí)性,但是用計算機(jī)來實(shí)現(xiàn)或多或少有一些困難,因此在布谷鳥算法中引入了Levy飛行隨機(jī)搜索方法。根據(jù)重尾分布概率分布,Levy飛行搜索的步長也被分布,步長分布遵循冪次法則y=x-α,1<α<3,因此,步長有一個無限的變量。

根據(jù)一些研究,許多飛行動物和昆蟲的覓食行為表現(xiàn)出一種特殊的特性。使用3個規(guī)則來簡化布谷鳥算法:1)一個布谷鳥一次只生一個蛋,布谷鳥隨機(jī)的把蛋存在一個鳥巢中;2)只有能存高質(zhì)量的蛋的最好鳥巢能傳遞到下一代;3)可用宿主的鳥巢數(shù)量是固定的,宿主發(fā)現(xiàn)布谷鳥的蛋的概率為pd。

布谷鳥的算法流程如下:

1) 開始。

2) 設(shè)置目標(biāo)函數(shù)f(x),其中x=(x1,x2,…,xd)T。

3) 初始化n個宿主xi個鳥巢的種群,i=1,2,…,n。

4) 當(dāng)t小于最大代或者沒有達(dá)到停止條件。

5) 隨機(jī)獲得一個布谷鳥i,由Levy飛行搜索產(chǎn)生一個新的解。

6) 評估它的適應(yīng)度Fi。

7) 在n個宿主中隨機(jī)選擇一個鳥巢j。

8) 如果Fi>Fj。

9) 新解代替j。

10) 拋棄差鳥巢中的一部分pd,在新的解位置通過Levy飛行搜索建立一個鳥巢。

11) 保持最優(yōu)解。

12) 把解分類,并選出當(dāng)前最優(yōu)解。

13) 后期處理和可視化表示。

14) 結(jié)束。

圖2 布谷鳥搜索流程圖

3 仿真實(shí)驗(yàn)及分析

為了對比說明煙花算法和布谷鳥算法的性能,選取6個標(biāo)準(zhǔn)測試函數(shù)[14-15]在MATLAB平臺下進(jìn)行實(shí)驗(yàn),函數(shù)分別是Ackley、Sphere、Griewank、Rotated hyper-ellipsoid、Zakharow和Exponential(具體參數(shù)如表1所示)。其中Ackley 和Griewank是高峰函數(shù),剩下的是單峰函數(shù)。試驗(yàn)參數(shù)設(shè)置為:規(guī)模n=200,pd=0.2,T=500,平均獨(dú)立運(yùn)行50次。

表1 測試函數(shù)

通過評價其在固定迭代次數(shù)時,算法的收斂速度、其尋優(yōu)精度以及穩(wěn)定性來對比分析二者的性能。表2表明了布谷鳥與煙花算法對上述6個函數(shù)的測試結(jié)果。其中布谷鳥算法(CS),煙花算法(FA)。

表2 使用不同算法的6個函數(shù)測試結(jié)果

從表2可以看出,煙花算法和布谷鳥算法非常接近,但是對于高峰函數(shù),煙花算法比布谷鳥算法精度更高。

圖3～圖8顯示了最優(yōu)的搜索結(jié)果圖,結(jié)果表明煙花算法收斂速度較快,能夠及時跳出局部最優(yōu)解,提高了搜索的準(zhǔn)確度。同時煙花算法的收斂時間也大大優(yōu)于布谷鳥算法,但是二者在解決優(yōu)化問題上都有著很大的優(yōu)勢。

圖3 Ackley函數(shù)對比曲線

圖4 Sphere函數(shù)對比曲線

圖5 Griewank函數(shù)對比曲線

圖6 Rotated hyper-ellipsoid函數(shù)對比曲線

圖7 Zakharow函數(shù)對比曲線

圖8 Exponential函數(shù)對比曲線

4 結(jié)論及展望

文章通過介紹2種新型的智能優(yōu)化算法----煙花算法與布谷鳥算法,很多學(xué)者都對其進(jìn)行了深入的研究,而且也提出了很多的改進(jìn)算法。本文就二者的特性給出了詳細(xì)的說明,最后通過6個基準(zhǔn)函數(shù)做出實(shí)驗(yàn),通過實(shí)驗(yàn)說明了二者的區(qū)別以及在解決優(yōu)化函數(shù)時的情況,對二者的對比分析旨在進(jìn)一步提高在實(shí)際工程中的布谷鳥算法或者煙花算法的使用價值。在以后工作中,將進(jìn)一步研究二者的改良之處,實(shí)現(xiàn)其應(yīng)用價值。

[ 1 ]MONICAS,FERRARIG.Swarmintelligentapproachestoauto-localizationofnodesinstaticUWBnetworks[J].AppliedSoftComputing, 2014,25:426-434.

[ 2 ]RODZINSI.Smartdispatchingandmetaheuristicswarmflowalgorithm[J].JComputSystemsSciInternational, 2014,53(1):109-115.

[ 3 ]吳虎勝,張鳳鳴,吳廬山. 一種新的群體智能算法----狼群算法[J]. 系統(tǒng)工程與電子技術(shù), 2013,11:2430-2438.

[ 4 ]周晨航,田力威,趙宏偉. 基于改進(jìn)螢火蟲算法的二維Otsu圖像分割法[J]. 沈陽大學(xué)學(xué)報(自然科學(xué)版), 2016,28(1):45-50.

[ 5 ]SHIY.AnOptimizationAlgorithmBasedonBrainstormingProcess[J].InternationalJSwarmIntelligenceResearch, 2011,2(4):35-62.

[ 6 ]DADANEHBZ,MARKIDHY,ZAKEROLHOSSEIEIA.GraphcoloringusingIntelligentWaterDropsalgorithm[C]∥ElectricalEngineering.IEEE, 2015:595-600.

[ 7 ]YANL,XINGYQ,WANGLH.HyperspectralDimensionalityReductionofForestTypesBasedonCatSwarmAlgorithm[J].OpenAutomation&ControlSystemsJournal, 2015,7(1):226-233.

[ 8 ]RUSSELLSJ,NORVIGP.Instructor’sManual:ExerciseSolutionsforArtificialIntelligenceAModernApproachSecondEdition[J].ArtificialIntelligenceAModernApproach, 2015,15(96):217-218.

[ 9 ]BONETB,CAVAZZAM,DESJARDINSM,etal.ASummaryoftheTwenty-NinthAAAIConferenceonArtificialIntelligence[J].AiMagazine, 2015,36(3):99-106.

[10]TANY,YUC,ZHENGS,etal.IntroductiontoFireworksAlgorithm[J].InternationalJournalofSwarmIntelligenceResearch, 2015,4(4):39-70.

[11]TANY.AdaptiveFireworksAlgorithm[M].Berlin:Springer, 2015.

[12]DINGB,WUZJ,SOM.ProcessModelClusteringBasedonK-meansandCuckooAlgorithm[J].ValueEngineering, 2015(10):210-212.

[13]WANGJS,SHENNN.HybridMultipleSoft-SensorModelsofGrindingGranularityBasedonCuckooSearchingAlgorithmandHysteresisSwitchingStrategy[J].ScientificProgramming, 2015,2015(5):1-11.

[14]吳斌,史忠植. 一種基于蟻群算法的TSP問題分段求解算法[J]. 計算機(jī)學(xué)報, 2001,24(12):1328-1333.

[15]高海昌,馮博琴,朱利. 智能優(yōu)化算法求解TSP問題[J]. 控制與決策, 2006,21(3):241-247.

Comparisonandanalysisoffireworksalgorithmandcuckooalgorithmforsolvingoptimizationproblem

LI Hang, HAN Qi

(SoftwareCollege,ShenyangNormalUniversity,Shenyang110034,China)

Currently,intelligenceartificialalgorithmdevelopsrapidlyandhasbeenusedinmanyfields,suchassystemcontrol,patternrecognition,productionscheduling,VLSItechnologyandcomputerengineeringetc.Therearemanyoptimalalgorithmstoimprovetheproblemsofcomplexity,binding,nonlinear,moreremote,difficultymodelinginrealengineering.FireworksalgorithmandCuckooalgorithmastwonewevolutionarycomputationmethodshavebeenappliedinfunctionoptimization.Theexperimentresultsofperformanceforsolvingdifferentquestionsandperformancedifferencesinsolvingunimodalandmulti-peakproblemswerecomparedandanalyzed.Finally,therobustnessandtheeffectsofparametersonthealgorithmsofthemethodsareanalyzed.Asaconclusion,thecharacteristicsoffireworksalgorithmandcuckooalgorithmandsomeimprovedalgorithmstoimproveitsvalueinpracticalengineeringapplicationarediscussed.

artificialintelligence;fireworksalgorithm;cuckooalgorithm;performancecomparison

2016-08-18。

國家自然科學(xué)基金資助項(xiàng)目(60970112)。

李 航(1976-),男,遼寧鐵嶺人,沈陽師范大學(xué)教授,博士。

1673-5862(2017)01-0087-06

TP

A

10.3969/j.issn.1673-5862.2017.01.017