基于混沌映射和莱维飞行的黏菌优化算法*

2023-06-04 06:24施文娟朱振源
计算机与数字工程 2023年2期
关键词:黏菌莱维游动

龚 然 施文娟 朱振源

(1.盐城工学院信息工程学院 盐城 224000)(2.盐城师范学院物理与电子工程学院 盐城 224000)

1 引言

近年来,元启发式优化算法受到工程领域的广泛关注。研究者们提出了很多先进的元启发式优化算法来解决复杂的工程领域优化问题,如鲸鱼优化算法(Whale Optimization Algorithm,WOA)[1],灰狼优化算法(Grey Wolf Optimization Algorithm,GWO)[2],蜻蜓优化算法(Dragonfly Optimization Algorithm,DA)[3],蚁狮优化算法(Ant Lion Optimization Algorithm,ALO)[4],飞蛾优化算法(Moth Optimization Algorithm,MOA)[5]。2020 年Li 等[6]提出一种新型元启发式优化算法,称为黏菌算法(Slime Mould Algorithm,SMA)。该算法模拟了黏菌在不同浓度环境下的觅食过程以及状态变化,并且利用权值来模拟黏菌在觅食过程中产生的正负反馈,形成了黏菌发现食物、接近食物以及包裹食物三种不同的状态。

针对标准黏菌算法存在收敛精度较低、迭代后期易陷入局部最优等问题,学者们提出了改进SMA的方法[7~11]。贾鹤鸣等[7]将算术优化算法与黏菌算法两种算法结合,并加入随机反向学习策略,提出一种融合随机反向学习的黏菌与算术混合优化算法。郭雨鑫等[8]采取精英反向学习策略提高初始黏菌种群的多样性,利用二次插值方法增强算法局部开发能力,提出一种精英反向与二次插值改进的黏菌算法。刘成汉等[9]将人工蜂群算法与黏菌算法两种算法结合,并加入自适应可调节的反馈因子和交叉算子,提出了改进交叉算子的自适应人工蜂群黏菌算法。改进后的黏菌算法已成功应用于特征选择[10]、图像分割[11]等领域。

综上所述,虽然近年来一些学者对黏菌算法进行了改进研究,但其依然存在收敛速度过慢、稳定性较低、易陷入局部最优等问题。因此,本文提出一种基于混沌映射和莱维飞行的黏菌优化算法(Chaotic Map and Levy Flight based Slime Mould Optimization Algorithm,CLSMA)。

2 标准黏菌算法

黏菌算法主要模拟的是自然界中多头绒泡菌在不同食物浓度下的觅食行为以及状态变化。黏菌主要分泌酶来消化食物,黏菌的前端延伸成扇形,后端由相互连接的静脉网络包围。环境中不同浓度的食物影响着黏菌静脉网络中细胞质的流动,从而形成黏菌觅食的不同状态。

当黏菌接近食物时,黏菌算法的数学模型如式(1)表示:

其中,t为当前迭代次数,Xb(t)为第t次迭代时黏菌个体最优的位置,Xm(t)和Xn(t)为随机选择两个黏菌个体的位置,vb 作为控制参数范围是[-a,a],vc 是从1 线性下降到0 的参数,r 是[0,1]之间的随机值。W 为黏菌质量,代表适应度权重。控制变量p和参数vb的数学模型公式如下:

a的计算公式如式(4)所示:

其中,i∈1,2,3…,n,S(i)是第i个黏菌适应度值,DF为所有迭代中最佳适应度值。适应度权重W 如式(5)所示:

其中,condition 表示适应度值排在前一半的黏菌个体。fitness sequence 为黏菌的适应度值序列,当求解最小值问题时,其使用升序排列方法。其中,目前迭代次数中最优适应度值用OF 表示,最差适应度值用MF 表示。当黏菌包裹食物时,黏菌算法的数学模型如式(7)所示:

其中,UB 与LB 表示搜索范围的上下边界,rand 和r表示[0,1]之间的随机值。z 为自定义参数,设为0.03。

当黏菌抓取食物时,黏菌的静脉组织和生物振荡器产生变化。静脉接触的食物浓度越高,生物振荡器产生的波越强,依靠这种变化,黏菌会抓取更高浓度的食物。黏菌静脉宽度的变化采用W、vb和vc来实现。

W 模拟了不同食物浓度下黏菌在附近的振荡频率。vb在[-a,a]之间随机变化,随着迭代次数的增加,逐渐趋近于零。vc 的值在[-1,1]之间振荡,最终趋于0。当黏菌选择食物时,vb 和vc 之间的相互协同性发挥着重要的作用。

3 基于混沌映射和莱维飞行的黏菌优化算法

3.1 Circle混沌映射

大部分群智能优化算法的初始种群是由随机数法产生的[12],SMA算法也是如此。但是随机数法产生的初始种群个体有一定的偶然性,其产生的初始个体无法均匀的分布在搜索空间内,容易陷入局部最优。混沌映射所产生的的混沌序列能够丰富种群多样性,可使种群均匀分布在搜索空间内,避免算法陷入局部最小值。本文采用Circle 混沌映射初始化黏菌种群,作为混沌映射的代表,其产生的混沌序列分布比较均匀,能够提升初始黏菌种群的多样性。Circle映射数学模型如式(8)所示:

其中,k 表示映射次数,k=1,2,3,4…;Xk表示第k 次映射函数值;c,d 为混沌参数,当c=0.2,d=0.5 时,Cirle 混沌映射产生的混沌序列更均匀。由图1 可知Cirle 混沌映射值在[0,1]间较均匀分布,能够改进黏菌初始种群的多样性。

图1 Cirle混沌映射值在[0,1]间的分布

3.2 莱维飞行策略(Levy Flight Strategy)

2008年Ghaemi等[13]提出了莱维飞行策略模拟自然界中随机行走的现象,包括土壤中的变形虫、白蚁、陆地上的苍蝇等。根据这种现象所提出的莱维飞行策略在优化算法中得到了广泛的应用。作为一种随机运动,莱维飞行的步长采取了长距离和短距离结合的特性,这种分布特性一方面增强了算法跳出局部最优的能力,另一方面加快了算法的收敛速度。黏菌算法中位置更新公式里采用的是均匀分布产生随机数,收敛速度较慢,因此可以使用莱维分布的特性对黏菌算法在接近食物r<p时位置进行更新,其数学模型如式(9)所示:

其中,Xb(t)为第t次迭代时适应度最高的黏菌个体位置,Xm(t)和Xn(t)为随机选择两个黏菌个体的位置,vb作为控制参数范围是[-a,a],α表示莱维飞行随机步长,⊗表示点乘,Levy(λ)表示遵循莱维分布的路径方法,且满足Levy~u=t-λ。莱维分布一般使用正态分布求解随机数的算法来模拟,其步长计算方式为

其中,μ,v 服从标准正态分布,其定义如式(11)、式(12)和式(13)所示:

其中,σv=1,ε取值1.5[14]。

3.3 局部随机游动策略

2009 年Yang 等[15]提出了布谷鸟算法(Cuckoo Search Algorithm,CS)模拟了自然界中布谷鸟孵化寄生的一种行为,并且融合了莱维飞行全局随机游动和局部随机游动的机制。莱维飞行全局随机游动可以增强CLSMA 的全局寻优能力,而局部随机游动策略可以加强算法局部优化的能力。两种策略的结合能够优化算法的寻优性能。局部随机游动通过将算法经过混合变异的方式重新生成新的随机候选解。

由此可见,利用局部随机游动的策略加强黏菌算法的局部寻优能力,其数学模型如式(14)所示:

其中X(t+1) 是第t+1 次迭代时适应度最高的黏菌位置,X(t)是第t 次迭代时适应度最高的黏菌位置。τ为缩放因子,是0~1 之间的随机数,Xf(t)和Xg(t)是第t次迭代时两个随机解。

由于不能保证利用随机游动策略后适应度值是否更优,因此利用贪婪原则选择是否更新黏菌算法的最优位置,此时黏菌算法的最优位置公式如下。

3.4 CLSMA算法描述

针对标准黏菌算法收敛速度较慢、初始种群多样性低等问题,本文提出一种基于混沌映射和莱维飞行的黏菌优化算法(CLSMA),如算法1所示。

算法1 CLSMA算法流程

输入:算法种群规模N,最大迭代次数tmax,研究问题维度D,搜索上界UB,下界LB。

输出:黏菌位置最优解和最佳适应度值。

Step1:设置算法种群规模N,当前迭代t,最大迭代次数tmax,研究问题维度D,搜索上界UB,下界LB;

Step2:根据式(8),利用Circle 混沌映射初始化种群Xi(i=1,2,3,…,N);

Step3:While t<tmax时,计算适应度值,记录当前最优适应度OF和最差适应度MF;

Step4:利用式(5)更新适应度权重W,式(4)更新参数a;

Step5:for i=1 to N,if rand <z,利用式(7)更新黏菌位置;

Step6:利用式(2)和式(3)更新vc、vb和p;

Step7:if r <p,利用式(9)莱维飞行策略和式(14)局部随机游动策略更新黏菌位置,同时利用式(15)贪婪原则选择更新最优的黏菌位置;

Step8:if r ≥p,利用式(7)的第三个公式更新黏菌位置;

Step9:判断t是否大于tmax,若t>tmax,输出黏菌位置最优解和最佳适应度值;若t<tmax,转向步骤3。

4 仿真实验分析

4.1 仿真测试环境

本文仿真测试相关配置为Windows10、64bit操作系统,处理器为Intel(R)Core(TM)i5-10200H,内存16G,仿真测试软件为Matlab 2017b。

4.2 对比算法与初始参数设置

为了更好地验证CLSMA 的算法性能,论文选取了鲸鱼算法(Whale Optimization Algorithm,WOA)[1]、灰狼算法(Grey Wolf Optimization,GWO)[2]、蜻蜓算法(Dragonfly Optimization,DA)[3]、蚁狮算法(Ant Lion Optimization,ALO)[4]、标准黏菌算法(SMA)[6]与CLSMA 进行对比。选取12 个不同的测试函数进行仿真实验,充分研究该算法对不同类型问题的有效性。其中F1~F5 为单峰测试函数,F6~F10为多峰测试函数,F11~F12为固定维多峰测试函数。不同函数的测试目的不同,单峰测试函数由于全局最优解只有一个,可以在同等条件下对比算法的收敛速度。多峰测试函数具有多个局部最优解和一个全局最优解,往往可以使所测算法陷入局部最优,所以其可以检验算法跳出局部最优的能力。为了实现公平性,所有算法均在相同的条件下执行,所有算法在每个函数下分别运行30 次。初始参数统一设置为最大迭代次数tmax=500,种群规模N=30,维度D=30。各个算法初始内部参数如表1所示[6];基准测试函数具体信息如表2所示。

表1 各算法参数设置

表2 基准测试函数

4.3 算法对比分析

CLSMA 算法与对比算法在基准测试函数上的测试结果如表3所示,记录所测算法在30次运行中所得的最佳平均适应度值(mean)以及标准差(Std),其中数据加粗表示算法在所在函数的测试结果中最优。平均值与标准差的值越小表示算法的性能越好。在F1~F12 函数的求解结果中,CLSMA 的求解结果最优,且F1、F3 和F7 都达到理论最优值,其中在F1、F7 和F8 函数上,CLSMA 和SMA的求解结果相同,说明在这两个函数上,两个算法的寻优能力相当。对于F2、F4~F6 以及F8~F12 函数,CLSMA 算法和其余几种算法都没有达到理论最优值,但CLSMA 算法的求解精度最好,可以证明CLSMA 算法比其余几种算法具有更好的勘探能力。在多峰函数的测试结果发现,CLSMA 的平均值和标准差最小或并列最小,其中在F7 上达到了理论最优值。对于F8 和F11,CLSMA 和SMA 的求解结果相同,但在F11 函数上CLSMA 的标准差更好。在固定维多峰测试函数F11 至F12 的求解结果中,CLSMA 接近理论最优值,且平均值和标准差都优于其余几种算法。综上所述,对于单峰函数和多峰函数的测试结果中,CLSMA 都有较好的求解结果,证明了CLSMA 在与其余元启发式算法比较中有更好的寻优精度和稳定性。

表3 不同算法的函数测试结果

4.4 收敛曲线分析

改进后的CLSMA 算法在收敛速度以及收敛精度上得到了明显的改善。图2 给出了各算法在12个不同测试函数下的收敛曲线。整体收敛曲线的趋势表明,CLSMA 的收敛速度和收敛精度优于其它算法。对于测试函数F1~F5,CLSMA从迭代开始收敛曲线明显下降,收敛速度快,证明CLSMA 在单峰测试函数上具有一定的优势,算法的寻优性能较好。对于F2 和F4 函数,CLSMA 算法没有达到理论最优值,但相较于其它算法,其更接近理论最优值,证明SMA 算法在引入Circle 混沌映射和莱维飞行策略后,CLSMA 算法能够更快地达到最优解,增强了SMA 算法的有效勘探能力和收敛速度。对于多峰测试函数F6~F10,CLSMA 的收敛效果明显优于其它算法,其中对于F6 和F8 测试函数,CLSMA 在迭代初期便达到全局最优值,证明了改进后的算法有较好的全局探索能力。对于F7 和F9 函数,CLSMA 能够快速地跳出局部最优解,并且更接近最优值。对于固定维多峰函数F11 和F12,CLSMA 的收敛速度较优于其余算法。

图2 各算法在不同测试函数下的收敛曲线

5 结语

本文针对标准黏菌算法的不足,提出一种基于混沌映射和莱维飞行的黏菌优化算法(CLSMA)。引入Circle 混沌映射,利用其产生的混沌序列,丰富初始黏菌种群的多样性,使种群较均匀的分布在搜索空间内;采用莱维飞行策略,增强算法跳出局部最优的能力和提高算法的收敛速度;利用布谷鸟算法的局部随机游动策略增强算法的局部优化能力。最后在由单峰函数、多峰函数组成的12 个基准函数下进行测试,实验证明改进后的黏菌算法收敛精度、稳定性以及全局搜索能力都得到了增强。未来将进一步增强CLSMA 算法的寻优性能以及探索其在实际工程领域的应用价值。

猜你喜欢
黏菌莱维游动
永不停歇的鱼
Open Basic Science Needed for Significant and Fundamental Discoveries
基于莱维飞行蜉蝣优化算法的光伏阵列最大功率点跟踪研究
球轴承用浪型保持架径向游动量的测量
黏糊糊的生命
黏菌观察记
养群黏菌当宠物
把手放进袋子里
黏菌一点不简单
创意“入侵”