基于混沌初始化和高斯变异的飞蛾火焰优化算法

刘 倩1, 冯艳红1,2, 陈嶷瑛1

(1.河北地质大学 信息工程学院,河北 石家庄 050031; 2.河北地质大学 河北省智能传感物联网技术工程研究中心,河北 石家庄 050031 )

摘 要: 针对飞蛾火焰优化算法(moth-flame optimization algorithm, MFO)在求解最优化问题时存在寻优精度低、易陷入局部最优等问题,提出一种基于混沌初始化和高斯变异的改进飞蛾火焰优化算法。首先,采用立方混沌映射对飞蛾种群进行初始化操作,使飞蛾更均匀地分布于搜索空间;其次,应用高斯变异对种群中少数较差个体进行扰动以增强算法跳出局部最优的能力;最后,通过阿基米德曲线扩大搜索范围,提高算法对未知领域的探索能力。在CEC14测试函数及21个可扩展Benchmark函数上进行了一系列实验,与标准飞蛾火焰优化算法、遗传算法、人工蜂群算法、粒子群算法、差分进化算法、花授粉算法和蝴蝶优化算法进行比较,结果表明,该算法能明显提高解的精度和算法的收敛速度。

关键词: 混沌初始化; 高斯变异; 阿基米德曲线; 飞蛾火焰优化算法; 群体智能

0 引言

飞蛾火焰优化算法(moth-flame optimization algorithm,MFO)[1]是一种新颖的群体智能算法。该算法由飞蛾和火焰2部分构成,通过横向定位导航机制来解决探索和利用之间的平衡问题。MFO具有参数简单、容易实现且鲁棒性好等优点,因此,自提出以来,便受到国内外学者的广泛关注,使其在诸多领域得到应用[2-5]。当前,国内外学者对其改进研究主要分为对飞蛾飞行方式的优化和对进化机制的优化。

尽管已有文献对MFO算法的改进在一定程度上提高了算法的性能,但是这些改进措施在解决高维多峰复杂问题时效果不尽如人意。

基于此,本文提出一种基于混沌初始化和高斯变异的飞蛾火焰优化算法(moth-flame optimization algorithm based on chaotic initialization and Gaussian mutation, CGMFO)。CGMFO采用立方混沌映射初始化种群以增强飞蛾勘探未知空间的能力,从而提高求解精度;采用高斯变异对部分较差个体进行局部扰动以提高算法的收敛速度;采用阿基米德曲线飞行机制以增强种群的多样性,并抑制算法的早熟收敛,进而实现全局最优化。CGMFO对CEC14经典测试函数[6]和21个可扩展Benchmark函数[7]进行求解,实验结果验证了该算法具有良好的收敛能力和竞争实力。

1 飞蛾火焰优化算法的基本原理

在MFO算法中,用式(1)表示飞蛾种群规模为n,维数为d的飞蛾所处空间位置,且用式(2)矩阵存储飞蛾个体的适应度值。火焰是算法的另一个核心,其在空间的位置矩阵与飞蛾的空间矩阵类似,用式(3)表示,使用式(4)矩阵存储相应火焰的适应度值。

(1)

OM=[om1,om2,…,omn]T

(2)

(3)

(4)

火焰减少过程如下式所示:

(5)

式中:tT分别为当前迭代次数和最大迭代次数;N为最大火焰数量。

Di=|Fj-Mi|。

(6)

式中:Di为飞蛾Mi到火焰Fj的距离。

假设飞蛾Mi会朝着距离自己最近的火焰Fj移动,移动的路径选取了对数螺线曲线,并将该曲线作为飞蛾的主要更新机制,算法的对数螺旋曲线定义如下:

S(Mi,Fj)=Di·ebt·cos 2πt+Fj

(7)

式中:S(Mi,Fj)为更新后的飞蛾位置;Di表示第i个飞蛾与第j个火焰的距离;b为与螺旋形状相关的常量;t为随机数,取值区间为[-1,1];ebt ·cos 2πt为对数螺旋曲线表达式。

总结前文所述,飞蛾火焰优化算法的一般步骤如下:

步骤1 初始化算法参数:飞蛾数量n、维数d、最大迭代次数T等,随机初始化种群;

步骤2 计算种群中飞蛾的适应度值,并按适应度值升序排序;

步骤3 利用式(5)更新火焰数量;

步骤4 利用式(6)计算飞蛾到火焰的距离;

步骤5 利用式(7)更新飞蛾位置;

步骤6 若满足给定的迭代次数,算法结束,获得最优解;否则,返回步骤2。

2 CGMFO原理

2.1 混沌初始化

在原始MFO中,飞蛾的位置通过随机初始化的方式产生,会造成飞蛾的位置分布不均匀,进而降低求解精度。而基于混沌理论的混沌序列具有伪随机性和边界性等特点,故许多学者提出了嵌入混沌序列的多种算法[8-9]。在诸多混沌映射中,立方映射的性能较优[10],因此,本文采用立方混沌映射对MFO进行初始化:

(8)

利用立方混沌映射初始化飞蛾种群的3个步骤如下:

步骤1 按照式(8)随机产生d维空间中的n只飞蛾,即Y=(y1,y2,y3,…,yd),yi∈[-1,1],i=1,2,…,d

步骤2 将每只飞蛾的每一维迭代n次,从而产生n只飞蛾;

步骤3 在所有的飞蛾迭代完成后,按照式(9)映射到解空间中。

(9)

式中:UdLd 为搜索空间的上、下界;yid 是利用式(8)产生的第i只飞蛾的第d维坐标;xid是第i只飞蛾在搜索空间第d维的坐标。

本文将基于立方混沌映射初始化的飞蛾火焰优化算法记为CMFO。

2.2 高斯变异机制

观察MFO算法中解的更新公式(式(5)和式(7)),可以发现每只飞蛾空间矢量位置的更新与离其最近的火焰空间位置有直接的关系。而此火焰空间位置仅靠适应度值来确定,这就导致对当前全局最优飞蛾的有效利用能力不强。

因此,在对飞蛾按适应度值进行排序后,选取适应度值最差的n×ω个个体,并对其应用高斯变异Gaussian(μ,σ2),其中,n是飞蛾种群规模;ω是变异的比例;μ 表示均值;σ2表示方差。根据经验,本文ω取值为1/6,便于控制和缩小更新范围,并适度地提高算法的种群多样性。改进后的飞蛾产生公式描述如下:

(10)

式中:分别表示变异前和变异后的飞蛾。

本文将基于CMFO,对种群每一代中少数较差个体用高斯变异进行微小扰动的飞蛾火焰优化算法记为GCMFO。

2.3 基于阿基米德曲线的飞行机制

由于MFO中飞蛾的飞行机制会影响算法的性能,与对数螺旋曲线相比,阿基米德螺旋曲线使飞蛾扩大了搜索范围,且阿基米德螺旋曲线在诸多优化领域得以应用[11-12]。为了增强MFO算法的种群多样性,加快算法的收敛速度,本文将原MFO算法中的对数螺旋曲线替换为阿基米德螺旋曲线。其平面笛卡尔坐标方程式为

(11)

其中,当θ=0时,α为起点到极坐标原点的距离,β为螺旋线每增加单位角度随之对应增加的数值。当θ>0时,α相当于旋转螺线,而β则控制相邻两条曲线之间的距离。

则飞蛾位置的移动如下式所示:

S(Mi,Fj)=Di·ebt·(α×γ)·sin 2πβ(γ-α)+Fj

(12)

其中, b=1,β=10,αγ定义如下:

(13)

γ=(α-1)×rand+1。

(14)

式中:rand为随机数,取值区间为[-1, 1]。

本文将基于GCMFO,应用阿基米德螺旋曲线的飞行方式的飞蛾火焰优化算法记为CGMFO。

2.4 CGMFO算法流程

根据2.1~2.3节描述的算法改进思想,提出的CGMFO算法步骤如下:

步骤1 按式(8)和式(9)初始化种群;

步骤2 计算种群中飞蛾的适应度值,按适应度值升序排序;

步骤3 选择排序后适应度较差的1/6飞蛾,按式(10)进行高斯变异,然后求解飞蛾和火焰的适应度值,选择其中最好飞蛾个体的位置并将其保存为火焰适应度值矩阵;

步骤4 利用式(5)更新火焰数量;

步骤5 利用式(6)计算飞蛾到火焰的距离;

步骤6 利用式(13)和式(14)初始化螺旋曲线的相关参数,按式(12)更新飞蛾位置;

步骤7 若满足给定的迭代次数,算法结束,获得最优解;否则,返回步骤2。

3 数值实验及分析

3.1 环境与参数

为了比较不同改进策略对MFO的影响程度,本文进行了2组实验。第1组实验对CGMFO、GCMFO、CMFO与MFO这4种算法,选用CEC14测试集[6]f1 f6进行仿真实验比较。第2组实验对CGMFO、MFO、GA[13]、ABC[14]、PSO[15]、DE[16]、FPA[17]和BOA[18]这8种算法,利用21个可扩展Benchmark函数[7]进行仿真实验比较。

仿真硬件环境为LENOVO Intel i7-8750H CPU 2.21 GHz,8.00 GB RAM,操作系统为Windows 10,利用MATLAB R2018b编程实现。

所有算法均采用相同的种群规模n=30,最大迭代次数T=1 000,第1组实验中,维数d=100,第2组实验中,d=10,重复实验次数RepeatCount=30。各算法的其余参数设置如表1所示。

表1 8种算法的参数设置
Table 1 Parameter settings for 8 algorithms

算法参数名称参数含义取值CGMFOMFOGAABCPSODEFPABOAμ均值0b螺旋形状常量1β螺旋形状常量10b螺旋形状常量1a选择概率0.3b交叉概率0.3c变异概率0.1limit限度15fn食物的数量15c1学习因子0.9c2学习因子0.3f缩放因子0.5cr交叉概率0.3p转换概率0.8p转换概率0.8a强度增加指数0.1

3.2 算法性能评价指标

本文的2组实验都采用优化均值误差(Average)和标准方差(Std.Dev)评价算法的优化能力,其中

优化均值误差计算如下:

Average=f(x)-f(x*)。

(15)

式中:x表示算法得到的解;x*表示每个测试函数的理论最优解。Average越小,则解的质量越好。

第2组实验中增加了Best最优解和Worst最差解的比较,这2个值越小,说明解的精度越高。

同时,为了比较算法在统计意义上的差异性,利用Wilcoxon秩和检验(显著水平 α =0.05)分别对21个函数的实验结果进行统计分析。

3.3 实验结果分析

3.3.1 第1组实验结果分析

由于篇幅有限,表2给出了4种算法对CEC14中每个函数进行30次独立实验的部分计算结果, 由表2的计算结果可以得出如下结论:

表2 4种算法对于CEC14测试函数的实验结果比较
Table 2 Comparison of the experimental results of the 4 algorithms for the CEC14 test function

算法f1f2f3AverageStd.DevAverageStd.DevAverageStd.DevMFOCMFOGCMFOCGMFO1.52E+061.24E+061.40E+069.17E+061.46E+069.13E+053.63E+053.00E+053.20E+052.50E+053.84E+053.39E+055.01E+031.92E+015.01E+032.63E+015.01E+032.25E+019.80E+012.04E+009.74E+012.21E+009.84E+011.32E+00算法f4f5f6AverageStd.DevAverageStd.DevAverageStd.DevMFOCMFOGCMFOCGMFO1.23E+069.12E+051.39E+061.15E+061.37E+061.00E+063.36E+052.85E+052.74E+051.85E+052.00E+051.50E+055.01E+032.15E+015.00E+032.55E+015.00E+032.15E+019.82E+011.70E+009.83E+011.96E+009.80E+012.05E+00

(1)3种改进算法对于CEC14中的测试集函数f1f6,无论是优化均值误差还是标准方差均优于原始的MFO。

(2)CMFO只使用立方混沌映射产生混沌序列,保证了飞蛾个体初始化位置在整个搜索空间的均匀分布,优化均值误差和标准方差在绝大多数测试函数上均有提高。

(3)GCMFO的改进效果优于CMFO,这是由于GCMFO不仅采用了立方混沌映射初始化,而且通过高斯变异对每代中少数较差的个体进行扰动,帮助算法跳出局部极值区域,提高了算法收敛速度。

(4)CGMFO的改进效果明显优于其他2种改进算法,多个函数的误差均值和标准方差都接近理论最优。

3.3.2 第2组实验结果分析

表3为8种算法对21个可扩展Benchmark函数进行30次独立实验的计算结果,其中Best为最优解,Worst为最差解,AverageStd.Dev定义与第1组实验相同。表3中的符号†、≈、分别表示CGMFO算法的实验结果优于、相当于和劣于对比算法,其中结果加粗表示最优。为了进一步比较CGMFO与其他7种算法的收敛趋势,图1给出了8种算法求解Benchmark函数f1 f3f9 f11各30次的平均进化曲线。经多次实验发现,当>设定每种算法的迭代次数均为T=160时,进化曲线的效果明显,故这里将T设置为160。

由以上实验结果可知:

(1)由表3可以看出,对于21个Benchmark函数,针对4种评价指标,CGMFO在求解几乎全部问题上均优于其他7种比较算法。其中14个函数求解结果达到了理论最优(f1~f8、f11~f13、 f18、 f20、f21)。其余未达到理论最优值的7个函数,与其他算法相比,CGMFO也最接近理论最优。

表3 8种算法对于测试函数f1f21的部分实验结果比较
Table 3 Comparisons of some experimental results of 8 algorithms for test functions f1 to f21

算法f1f4f7BestWorstAverageStd.DevBestWorstAverageStd.DevBestWorstAverageStd.DevCGMFO 0 0 0 0 0 0 0 0 0 0 0 0MFO4.91E-36 3.63E-30 3.24E-31 8.06E-31†5.84E-67 1.00E+00 1.34E+01 3.27E+01† 0 0 0 0GA3.58E-06 4.32E-05 1.79E-05 1.00E-05†7.51E-10 6.44E-06 8.00E-07 1.52E-06† 0 0 0 0ABC9.52E-17 5.85E-14 1.97E-14 3.36E-14† 0 0 0 09.12E-02 4.73E-01 2.50E-01 1.99E-01†PSO2.18E-18 1.12E-05 3.75E-07 2.05E-06†4.96E-16 5.85E-08 3.97E-08 9.49E-08† 01.00E+00 3.33E-02 1.83E-01≈DE6.97E-43 8.89E-41 1.48E-41 1.72E-41†5.99E-92 2.66E-85 2.33E-86 6.66E-86† 0 0 0 0FPA2.31E-02 2.46E-01 8.22E-02 5.64E-02†4.64E-09 8.41E-06 1.11E-06 1.77E-06† 0 0 0 0BOA2.16E-14 3.90E-14 2.91E-14 4.69E-15†5.93E-15 2.69E-14 2.07E-14 4.66E-15† 0 0 0 0算法f10f16f19BestWorstAverageStd.DevBestWorstAverageStd.DevBestWorstAverageStd.DevCGMFO4.35E+00 6.77E+00 6.00E+00 5.83E-042.30E-17 5.76E-09 2.74E-10 1.09E-093.13E-34 1.10E-32 7.33E-33 2.79E-52MFO 3.43E-02 9.96E+02 1.12E+02 3.00E+02†4.71E-32 7.75E+01 5.08E+00 1.43E+01†1.35E-31 1.00E+01 3.74E-01 1.82E+00†GA3.41E-02 7.39E+00 4.68E+00 2.57E+00†8.69E-01 1.09E+00 1.06E+00 5.61E-02†3.25E-05 5.54E-03 1.21E-03 1.29E-03†ABC7.40E-03 2.47E-02 1.82E-02 9.42E-03†4.79E-13 3.98E-10 1.34E-10 2.89E-09†7.83E-01 7.54E+00 7.21E-03 3.91E-12†PSO6.70E-01 1.01E+02 1.38E+01 2.32E+01†3.20E-06 2.36E-00 2.02E-01 4.94E-01†3.69E-08 6.62E-01 3.38E-02 1.22E-01†DE1.43E+00 7.02E+00 4.59E+00 1.56E+00†4.71E-32 4.71E-32 4.71E-32 1.67E-47■1.35E-31 1.35E-30 1.34E-31 8.20E-43†FPA4.29E+00 1.84E+01 9.09E+00 2.30E+00†1.96E-01 1.81E+00 7.50E-01 4.40E-01†2.16E-02 2.56E-01 1.11E-01 5.76E-02†BOA8.97E+00 9.00E+00 1.00E+01 6.43E-03†1.08E+00 2.10E+01 5.21E+00 5.37E+00†5.78E+00 1.64E+01 1.15E+01 2.48E+00†

(2)由图1的平均迭代进化曲线可以看出,在21个可扩展Benchmark函数中,CGMFO对应的目标函数下降曲线比其他7种算法的下降曲线具有更快的下降速度,并很快达到了最优值。这再次表明,CGMFO在函数全局优化方面具有更好的有效性,收敛速度更快。

图1 部分平均迭代进化曲线
Figure 1 Some average iterative evolution curves

4 结论

针对MFO求解精度不高及易陷入局部最优等缺陷,本文从3个方面对算法进行改进:立方混沌映射初始化,有效地防止飞蛾的位置分布不均匀;高斯变异对较差个体的扰动,减少了算法陷入局部最优的可能;阿基米德曲线飞行机制的应用使种群的多样性有所增加。从实验结果看出,CGMFO在搜索性能上均优于CMFO和GCMFO,且CGMFO在求解精度和收敛速度上与文中的其他进化算法相比,均表现优秀。由于MFO提出时间不长,故算法的参数分析和在工程问题中的应用将是下一步的研究课题。

参考文献:

[1] MIRJALILI S.Moth-flame optimization algorithm:a novel nature-inspired heuristic paradigm[J].Knowledge-based systems,2015,89:228-249.

[2] 李佳华,马连博,王兴伟,等.基于多目标蜂群进化优化的微电网能量调度方法[J].郑州大学学报(工学版),2018,39(6):50-58.

[3] 程适,王锐,伍国华,等.群体智能优化算法[J].郑州大学学报(工学版),2018,39(6):1-2.

[4] LIU D,ZHANG G D,LI H,et al.Projection pursuit evaluation model of a regional surface water environment based on an Ameliorative Moth-Flame Optimization algorithm[J].Ecological indicators,2019,107:105674.

[5] 李志明,莫愿斌.基于Lévy飞行的飞蛾扑火优化算法[J].计算机工程与设计,2017,38(3):807-813.

[6] GARG V,DEEP K.Performance of Laplacian biogeography-based optimization algorithm on CEC 2014 continuous optimization benchmarks and camera calibration problem[J].Swarm and evolutionary computation,2016,27:132-144.

[7] KIRAN M S,HAKLI H,GUNDUZ M,et al.Artificial bee colony algorithm with variable search strategy for continuous optimization[J].Information sciences,2015,300:140-157.

[8] 冯艳红,刘建芹,贺毅朝.基于混沌理论的动态种群萤火虫算法[J].计算机应用,2013,33(3):796-799,805.

[9] YU H L,ZHAO N N,WANG P J,et al.Chaos-enhanced synchronized bat optimizer[J].Applied mathematical modelling,2020,77:1201-1215.

[10] CHEN G,WU X D,ZHU X Q,et al.Efficient string matching with wildcards and length constraints[J].Knowledge and information systems,2006,10(4):399-419.

[11] CHEN Y D,WEI T H,GONG T X.Research on optimal layout of cutter-head system of rock tunnel-boring machine based on Archimedes spiral theory[J].Advances in mechanical engineering,2018,10(2):151-160.

[12] ZHANG B F,HU C B,TANG B J,et al.Chiral plasmonic lens with Archimedes-spiral distributed nanoslits[J].Journal of nanophotonics,2019,13(2):026008.

[13] KOZA J R.Genetic programming as a means for programming computers by natural selection[J].Statistics and computing,1994,4(2):87-112.

[14] KARABOGA D,AKAY B.A comparative study of artificial bee colony algorithm[J].Applied mathematics and computation,2009,214(1):108-132.

[15] CHUANG L Y,TSAI S W,YANG C H.Chaotic catfish particle swarm optimization for solving global numerical optimization problems[J].Applied mathematics and computation,2011,217(16):6900-6916.

[16] SIVANANAITHAPERUMAL S,AMALI S M J,BASKAR S,et al.Constrained self-adaptive differential evolution based design of robust optimal fixed structure controller[J].Engineering applications of artificial intelligence,2011,24(6):1084-1093.

[17] NABIL E.A modified flower pollination algorithm for global optimization[J].Expert systems with applications,2016,57:192-203.

[18] ARORA S,SINGH S.Butterfly optimization algorithm:a novel approach for global optimization[J].Soft computing,2019,23(3):715-734.

Moth-flame Optimization Algorithm Based on Chaotic Initialization and Gaussian Mutation

LIU Qian1, FENG Yanhong1,2, CHEN Yiying1

(1.School of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China; 2. Intelligent Sensor Network Engineering Research Center of Hebei Province, Hebei GEO University, Shijiazhuang 050031, China)

Abstract: Moth-flame optimization algorithm (MFO) has some drawbacks in solving optimization problems, such as low precision and high possibility of being trapped in local optimum. A modified MFO algorithm based on chaotic initialization and Gaussian mutation is proposed. Firstly, the cube chaotic map is used to initialize the moth population, which makes the moth more evenly distributed in the search space. Then, Gaussian mutation is adopted to disturb a few poor individuals to enhance the ability of escaping the local optimum. Finally, Archimedes curve is introduced to expand the search scope and strength the exploration ability in the unknown field. A series of experiments are carried out on CEC14 test function set and 21 extensible Benchmark functions. Compared with standard moth-flame optimization algorithm, genetic algorithm, artificial bee colony algorithm, particle swarm algorithm, differential evolution algorithm, flower pollination algorithm, and butterfly optimization algorithm, the results demonstrate that the proposed algorithm is strengthened in obtaining solutions with better quality and convergence.

Key words: chaotic initialization; Gaussian mutation; Archimedes curve; moth-flame optimization algorithm; swarm intelligence

收稿日期:2020-10-21;修订日期:2020-12-11

基金项目:国家自然科学基金资助项目(61806069)

通信作者:冯艳红(1978— ),女,河北卢龙人,河北地质大学副教授,硕士,主要从事人工智能、进化算法的研究,E-mail:qinfyh@163.com。

文章编号:1671-6833(2021)03-0053-06

中图分类号: TP301

文献标志码:A

doi:10.13705/j.issn.1671-6833.2021.03.009