烟花算法与布谷鸟算法求解优化问题的对比分析研究

李 航, 韩 祺

(沈阳师范大学 科信软件学院, 沈阳 110034)

烟花算法与布谷鸟算法求解优化问题的对比分析研究

李 航, 韩 祺

(沈阳师范大学 科信软件学院, 沈阳 110034)

近年来,人工智能算法发展十分迅速,而且在很多领域都得到了广泛的应用,如系统控制、模式识别、生产调度、VLSI技术和计算机工程等。鉴于实际问题的复杂性、约束性、非线性、多极小、建模困难等特点,提出了许多优化算法。烟花算法和布谷鸟算法作为2种新型的进化计算方法被广泛的应用在函数优化方面。通过实验对这2种算法在求解不同问题时的性能进行了系统的对比和分析,比较了2种算法在求解单峰和多峰问题上的性能差异。最后,又对其健壮性进行分析,研究了不同参数对二者的影响,对烟花算法和布谷鸟算法的原理特点做了一个总结,并讨论算法的一些改进方法,提高算法在以后实际工程中的应用价值。

人工智能; 烟花算法; 布谷鸟算法; 性能对比

0 引 言

群体智能优化算法[1-2]本质是建立在生物智能或物理现象基础上的随机搜索算法, 群体智能优化算法的基本信息是不同于传统优化算法,表现在4个方面[3-4]:1)在群体中的个体具有相互作用,呈分布式分布, 没有中心控制主要点, 个别个体出现故障并不能影响群体对优化问题的求解, 具有较强的鲁棒性;2)每个个体有局部搜素能力,按部就班的去做自己的工作, 所以群体智能的实现简单、方便;3)群体智能占用资源较少,开销较少, 易于扩充;4)自组织性较强, 即群体表现出的复杂性是通过简单个体的交互表现出高度的智能。

群体智能优化算法的基本理论是模拟实际生物群体生活中个体与个体之间的互相交流与合作, 用简单、有限的个体行为与智能, 通过相互作用形成整个群体难以估量的整体能力。目前,有很多种群体智能算法,如人工神经网络、混沌、遗传算法、进化规划、模拟退火、禁忌搜索及其混合优化策略等,还有最近提出的头脑风暴算法[5]、智能水滴算法[6]、猫群算法[7]等。在群体智能优化算法中的各个生物体都经过人工处理, 个体不具有实际生物的体积和质量, 其行为方式也是根据人们为了解决问题的需要而进行必要的加工处理。群体智能优化算法的理论研究主要是研究算法特性, 改进其不足, 提高性能。包括2方面的研究:一是从群体智能优化算法的自身特性加以研究,改进其性能;二是将群体智能优化算法之间或与其他算法进行结合, 通过算法之间的融合对算法加以改进, 产生新的混合智能算法。

1 烟花算法

根据群体行为的算法建模对于多维全局优化问题是一个非常强大的计算工具,这些智能算法都是从生物,社会现象或其他自然法则衍生而来[8-9]。烟花算法是烟花在夜空爆炸中获取的灵感,这种新型的算法被提出用来解决复杂函数的全局优化问题。当一个烟花爆炸时,围绕着烟花充满了一片火花。烟花的爆炸过程可以看成在局部空间围绕一个特殊点的搜索,烟花从这个点爆炸发出火花。在烟花算法中,目标就是寻找一个点xj来满足f(xj)=y,且烟花在这个潜在空间中不断地爆炸直到有一个目标火花出现在点xj附近。

(a)—理想的爆炸; (b)—不理想的爆炸图1 烟花爆炸类型Fig.1 Types of fireworks explosion

如果烟花爆炸设计的非常完美,对于位置的选择有一个非常适合的方法,那么烟花算法一定是有效的。如果仔细观察爆炸的烟花,会看到有2个不同的烟花行为。在一个好的爆炸中,无数的烟花碎片聚集且这些碎片集中在爆炸中心;不好的爆炸,很少一部分火花聚集,在空间中散乱分布。如图1所示[10-11]。

最优化问题的烟花算法如下:

最小化f(x)∈R,xmin≤x≤xmax,其中x=x1,x2,…,xd代表在潜在空间中的一个位置,f(x)是一个目标函数,xmin和xmax代表空间的上下界。

烟花算法流程如下:

1) 随机选取n个烟花位置。

2) 在这n个位置分别随机释放n个烟花。

3) 对于每个烟花xj执行:

a) 随机选择一个烟花xj。

b) 使用如下公式在爆炸的烟花中产生一个特定的碎片。

位置xi的选择概率定义为:

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

6) 结束。

获得一个随机爆炸碎片的位置伪代码:

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

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

7) 结束。

获得一个特定爆炸碎片的位置伪代码:

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

4) 计算高斯爆炸的系数:g=Gaussian(1,1)。

7) 结束。

2 布谷鸟搜索算法

布谷鸟算法[12-13]是一种新的元启发优化算法,灵感来自布谷鸟的繁殖行为,布谷鸟的育种习性对于研究这个算法非常的有必要。布谷鸟有很多不同于其他鸟类的特性,但是最主要的习性是具有侵略性的繁殖策略。一些布谷鸟把后代养育在公共的鸟巢中,甚至把其他的鸟蛋给移走来增加自己蛋的孵化概率。布谷鸟孵育寄生,把蛋寄生在其他鸟类的巢中。一些宿主做出不好的行为来反对入侵者或者直接参与斗争。在这种情况下,宿主会把那些入侵者的蛋给扔掉;在一些其他情况下,友好的宿主会简单的放弃它们的鸟巢并另建一个新的鸟巢。另外一些布谷鸟类,进化成一种先进的方式,雌性的布谷鸟会专业的模仿选择宿主的蛋的样式及颜色。这种做法降低了它们的蛋被扔掉的概率并且增加了孵化的几率。

基于布谷鸟的这些习性,算法流程如图2所示。尽管布谷鸟算法极力模仿布谷鸟孵育习性,但是用计算机来实现或多或少有一些困难,因此在布谷鸟算法中引入了Levy飞行随机搜索方法。根据重尾分布概率分布,Levy飞行搜索的步长也被分布,步长分布遵循幂次法则y=x-α,1<α<3,因此,步长有一个无限的变量。

根据一些研究,许多飞行动物和昆虫的觅食行为表现出一种特殊的特性。使用3个规则来简化布谷鸟算法:1)一个布谷鸟一次只生一个蛋,布谷鸟随机的把蛋存在一个鸟巢中;2)只有能存高质量的蛋的最好鸟巢能传递到下一代;3)可用宿主的鸟巢数量是固定的,宿主发现布谷鸟的蛋的概率为pd。

布谷鸟的算法流程如下:

1) 开始。

2) 设置目标函数f(x),其中x=(x1,x2,…,xd)T。

3) 初始化n个宿主xi个鸟巢的种群,i=1,2,…,n。

4) 当t小于最大代或者没有达到停止条件。

5) 随机获得一个布谷鸟i,由Levy飞行搜索产生一个新的解。

6) 评估它的适应度Fi。

7) 在n个宿主中随机选择一个鸟巢j。

8) 如果Fi>Fj。

9) 新解代替j。

10) 抛弃差鸟巢中的一部分pd,在新的解位置通过Levy飞行搜索建立一个鸟巢。

11) 保持最优解。

12) 把解分类,并选出当前最优解。

13) 后期处理和可视化表示。

14) 结束。

图2 布谷鸟搜索流程图

3 仿真实验及分析

为了对比说明烟花算法和布谷鸟算法的性能,选取6个标准测试函数[14-15]在MATLAB平台下进行实验,函数分别是Ackley、Sphere、Griewank、Rotated hyper-ellipsoid、Zakharow和Exponential(具体参数如表1所示)。其中Ackley 和Griewank是高峰函数,剩下的是单峰函数。试验参数设置为:规模n=200,pd=0.2,T=500,平均独立运行50次。

表1 测试函数

通过评价其在固定迭代次数时,算法的收敛速度、其寻优精度以及稳定性来对比分析二者的性能。表2表明了布谷鸟与烟花算法对上述6个函数的测试结果。其中布谷鸟算法(CS),烟花算法(FA)。

表2 使用不同算法的6个函数测试结果

从表2可以看出,烟花算法和布谷鸟算法非常接近,但是对于高峰函数,烟花算法比布谷鸟算法精度更高。

图3～图8显示了最优的搜索结果图,结果表明烟花算法收敛速度较快,能够及时跳出局部最优解,提高了搜索的准确度。同时烟花算法的收敛时间也大大优于布谷鸟算法,但是二者在解决优化问题上都有着很大的优势。

图3 Ackley函数对比曲线

图4 Sphere函数对比曲线

图5 Griewank函数对比曲线

图6 Rotated hyper-ellipsoid函数对比曲线

图7 Zakharow函数对比曲线

图8 Exponential函数对比曲线

4 结论及展望

文章通过介绍2种新型的智能优化算法----烟花算法与布谷鸟算法,很多学者都对其进行了深入的研究,而且也提出了很多的改进算法。本文就二者的特性给出了详细的说明,最后通过6个基准函数做出实验,通过实验说明了二者的区别以及在解决优化函数时的情况,对二者的对比分析旨在进一步提高在实际工程中的布谷鸟算法或者烟花算法的使用价值。在以后工作中,将进一步研究二者的改良之处,实现其应用价值。

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

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

[ 3 ]吴虎胜,张凤鸣,吴庐山. 一种新的群体智能算法----狼群算法[J]. 系统工程与电子技术, 2013,11:2430-2438.

[ 4 ]周晨航,田力威,赵宏伟. 基于改进萤火虫算法的二维Otsu图像分割法[J]. 沈阳大学学报(自然科学版), 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]. 计算机学报, 2001,24(12):1328-1333.

[15]高海昌,冯博琴,朱利. 智能优化算法求解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。

国家自然科学基金资助项目(60970112)。

李 航(1976-),男,辽宁铁岭人,沈阳师范大学教授,博士。

1673-5862(2017)01-0087-06

TP

A

10.3969/j.issn.1673-5862.2017.01.017