蜉蝣算法在供应链库存优化中的应用

赵文丹, 韩雪

(沈阳化工大学信息工程学院, 沈阳 110142)

随着经济和技术的快速发展,科学研究和工业生产中出现了大量的优化问题,针对解决生产中优化问题,许多群智能算法被提出。蜉蝣算法是由Zervoudakis等[1]在2020年提出的一种新型元启发式算法,该算法以蜉蝣交配繁殖产生下一代的方式在空间中搜索,结构简单。与其他元启发式算法一样,蜉蝣算法本身容易陷入局部最优,寻优精度不高、求解结果过差的特点。通常有两种方法可以提高蜉蝣算法的性能,第一类将蜉蝣算法与其他优化理论和方法相结合。如王义等[2-3]引入融合Lévy飞行策略飞行轨迹来更新雄性蜉蝣速度,增加了蜉蝣种群多样性,提高了全局搜索能力和收敛能力;Yi等[4]引入了可变步长的Lévy飞行策略和自适应算法,提高收敛速度和搜索精度;Shaheen等[5]、徐焕增等[6]采用混沌映射和蜉蝣之间的交配来寻找目标函数的最优解,增加种群多样性同时提高种群密度;薛健侗等[7]、高新成等[8]将蜉蝣优化算法引入K-means聚类分析中作为特征点提取,提出一种改进的蜉蝣优化算法。第二类为多个算法相结合来弥补单个算法的不足,提高算法的性能。刘书山等[9]将遗传算法与模拟退火算法相结合提高收敛速度。

这些算法在各自的应用领域中求解性能得到了改善,针对蜉蝣算法还有进一步改善的空间。提出以下3种策略提升算法总体性能指标:一是引入自适应惯性权重因子并提出改进吸引力系数,平衡搜索能力和局部开发能力。二是提出中值策略,加强种群间信息交流。Appiah等[10]将基于中值方法与动态规划结合在一起应用于图像降噪问题的研究。三是采用正弦余弦策略,增强全局搜索能力。Zhao等[11]将黄金正弦与交叉策略组合来处理优化问题;正弦方法也被引入到其他优化算法中,如差分进化算法[12]、混沌优化[13]与麻雀算法[14]。因此,正弦策略在蜉蝣算法(mayfly algorithm,MA)中的应用也可以提高其探索和收敛性能。许多专家和学者相继将不同的群智能优化算法引入比例-积分-微分(proportion-integration-differentiation,PID)参数优化中[15-17]。此外,这些方法有其优点,但也存在陷入局部最优解和过早收敛等常见问题,因此,将改进的算法用于供应链库存系统模型中,整定PID参数,使系统达到更优的指标。

现提出多策略自适应蜉蝣算法,在迭代前期执行中值策略,为了弥补中值策略的不足,增加收敛速度,在迭代后期执行正弦余弦策略,并改进自适应惯性权重因子。

1 基本的蜉蝣算法

蜉蝣算法的灵感来自蜉蝣交配过程,每只蜉蝣在空间位置上代表了问题的可行解,算法的工作原理如下:先产生两组蜉蝣,分别代表雄性和雌性种群,每只蜉蝣的位置为x,在d维空间中表示为x=(x1,x2,…,xd),根据目标函数f(x)对其性能进行评价。设蜉蝣的速度v=(v1,v2,…,vd),蜉蝣的飞行方向是个体和社会经验的交互作用,而每只蜉蝣会调整自己的轨迹,朝着个体最优以及全局最优位置移动。

1.1 雄性蜉蝣的运动更新

(1)

雄性蜉蝣在水面上表演舞蹈,考虑到没有很快的速度,蜉蝣不断的移动,速度更新为

(2)

(3)

为了得到更好的位置,团队中最好的蜉蝣继续表演舞蹈,更新它的速度,即

(4)

式(4)中:d为舞蹈系数,设为5;r为取值[-1,1]的随机系数。

1.2 雌性蜉蝣的运动更新

雄性蜉蝣容易聚集而雌性蜉蝣不会群体聚集,但是雌性蜉蝣会飞来与雄性蜉蝣交配繁殖。雌性蜉蝣的位置通过增加速度来更新,位置更新为

(5)

(6)

(7)

1.3 蜉蝣交配

雄性蜉蝣根据适应度函数选择雌性蜉蝣进行交配。此外,具有最佳适应度的雄性和最优适应度雌性进行交配,交配的结果是产生适应度最优个体off1、适应度次优个体off2,公式如下。

off1=Lmale+(1-L)female

(8)

off2=Lfemale+(1-L)male

(9)

式中:L为[-1,1] 内的随机值;后代的初始速度被设定为0;male为父本;female为母本。

2 改进蜉蝣算法

2.1 策略一:非线性重力系数和吸引力增强因子

蜉蝣优化算法的重力系数类似于粒子群算法中的重力,有助于实现开采和勘探之间的平衡。采用的非线性重力系数,使重力系数在开始迭代时缓慢减小,具有更好的探索开发能力,避免陷入局部最优,并能快速达到收敛精度,在迭代后期,重力系数减小,提高寻找最优解的能力,引进非线性重力系数公式,但随着距离的增加,吸引力值开始迅速下降。为防止对远处的蜉蝣几乎没有吸引力,增加算法无效迭代的次数,引进吸引力增强因子K。

(10)

(11)

式中:g(t)为重力系数;t为迭代次数;Maxt为最大迭代次数;h、b为常数,初始值设为10、100。将重力系数及吸引力增强因子引入蜉蝣算法,雄性蜉蝣速度更新公式为

(12)

雌性蜉蝣速度更新公式为

(13)

2.2 策略二:引入中值策略

在统计学中,中值和平均值通常用于反映总体平均水平。在群体智能算法中,在空间搜索的初始阶段,群体中个体的分布相对分散,并且有些个体的位置非常差。因此,提出了基于中值概念的群体中值位置,根据目标函数值对所有蜉蝣个体进行排序,在迭代前期,将蜉蝣的中值位置作为群体的中值位置,小组的每个成员,无论好坏,都可以贡献自己的信息来影响整个运动,增加种群多样性,使其能够跳出局部最优解。

(14)

式(14)中:n为组数,个体中值位置用作组的平均位置,加强信息交流,雄性蜉蝣速度更新表达式为

(15)

2.3 策略三:正弦余弦策略

由式(1)的位置更新公式可知,第i只蜉蝣位置会根据i只和第i-1只蜉蝣位置的中点进行更新。在此过程中并没有判断xi是否优于原来位置,这种单方向根据第i只蜉蝣更新位置,使种群收敛速度变慢。为使种群间信息利用率提高,提高收敛速度与精度,引入正弦余弦算法嵌入到蜉蝣算法中,一方面弥补蜉蝣算法位置更新的依赖性,无论正弦还是余弦都促使最优信息在种群间传递,另一方面加强蜉蝣个体在不同搜索空间的全局搜索和局部开发。位置更新为

(16)

r1=a-ta/Maxt

(17)

引入正弦余弦算法作为局部优化算子嵌入蜉蝣算法中,在迭代后期,交配繁殖中产生子代off1、off2,对全部蜉蝣个体采用正弦余弦操作,更新位置公式为

(18)

(19)

2.4 算法的步骤

该算法将整个种群分为雌性和雄性两个种群,两个种群分别执行不同的策略,并在种群间相互学习,以兼顾全局搜索能力和局部收敛能力。对于雄性,前期为N1;对于雌性,前期为N2。在算法的后期全体种群执行正弦余弦策略,流程图如图1所示。

图1 蜉蝣算法流程图Fig.1 Flowchart of the mayfly algorithm

N1=α1Maxt

(20)

N2=α2Maxt

(21)

式中:α1=0.3;α2=0.5。

3 工程算例

为保证函数多样性,选取20种测试函数由于篇幅有限展示8种,名称分别为:Sphere、Schwefel 2.22、Schwefel 2.21、Rosenbrock、Rastrigin、Ackley、Griewank、Hartman 3。为了测试改进蜉蝣算法的性能,选取特定的几种流行智能算法进行比较,并采用粒子群算法(particle swarm optimization,PSO)、蜉蝣算法(MA)、改进后蜉蝣算法(improved mayfly algorithm,IMA)、萤火虫算法(firefly algorithm,FA),实验结果基于30次独立运行的这些性能指标的分析,包括30次独立测试的平均值、标准偏差、最佳函数值,最好的优化结果用粗体表示,如表1所示。不同函数的平均收敛曲线如图2所示。

表1 不同基准函数结果比较Table 1 Comparison of results of different reference functions

图2 F1～F4函数平均收敛曲线Fig.2 Average convergence curve of function F1 to function F4

3.1 基准函数测试

从精度上看:F1、F2、F4、F8上,MOA均达到精度最高,F1、F2、F4、F8中MOA达到收敛速度最快。对于F3来说,PSO算法精度最高,MOA算法精度第二,收敛速度方面MA达到最优;MOA其次;对F5、F8来说,FA的收敛效率最高,MOA其次;其中,对于F1、F2、F4、F6来说,MOA在收敛精度上具有显著的优势,在F1、F2、F4、F6上,MOA在收敛效率上具有显著优势。因此,MOA算法在大多数函数上精度最高,在绝大多数函数上,收敛速度最快。

3.2 工程算例

蜉蝣算法优化PID参数用于供应链系统,三级供应链由客户、零售商、分销商和供应商组成,运作方式是由客户订单拉动的,零售商根据自身库存判断是否向上级订货,其中订货策略设为信息流用虚线表示,发货策略表示为物料流用实线表示,如图3、图4所示。

图3 三级供应链中物料流与信息流Fig.3 Material flow and information flow in three-level supply chain

图4 供应链系统组成图Fig.4 Supply chain system composition diagram

在MATLAB2018b中,用正弦信号模拟客户三种产品的订单,按照控制率零售商向上级订货,控制率为

ui=KP1(ukl-Invi)

(22)

Ui=KP1uln+KP2unm+KP3um

(23)

式中:u为下级向上级的订单;i为节点,i=o、l、n、m分别为客户、零售商、分销商、供应商节点;Inv为固定库存;U为总订单;KP1、KP2、KP3为库存基本控制对应的参数。

(24)

式(24)中:TC为供应链总成本;k为节点,分别表示供应商、分销商、零售商的节点;p为客户的数量;PCi为各节点生产成本;SCi为各节点单位存储成本;TRCi为各节点单位运输成本;Wi为产品该节点生产单价;Mi为该节点储存单价;ui为客户向零售商订货量;τ为时间常数。

3.3 算法的流程

根据上述蜉蝣算法在供应链PID参数优化中的算法流程,具体步骤如下。

步骤1设置雄性蜉蝣、雌性蜉蝣以及后代的数量,设置学习因子、能见度系数和舞蹈系数等参数;根据上述参数,初始化种群的速度和位置,将供应链的成本TC作为优化算法的适应度函数。

步骤2使用Simulink工具建立供应链系统仿真模型,如图4所示,然后开始迭代,计算每个蜉蝣的适应度函数值,对值进行排序,同时计算gbest、pbest和pm。

步骤3更新雄性蜉蝣和雌性蜉蝣的速度和位置,以及雄性蜉蝣和雌性蜉蝣之间的交配。

步骤4计算后代的适应度函数值以及变异的适应度函数值,更新个体适应度和全局适应度更新全局最优值。

步骤5判断迭代次数是否达到最大值,达到最大迭代次数则输出结果,若没有,则返回步骤2。

在确保参数优化结果正确情况下,为了更加符合现实情况,把三级订货策略中KP的边界设置为[0.1,10]、[0.1,5]、[0.1,5],周期运行时间Ts设为300 s,最大迭代次数Tmax为100。每个算法独立运行30次,改进后的蜉蝣算法与基本蜉蝣算法、粒子群算法、萤火虫算法进行比较,每个算法的参数设置如表2所示。优化后供应链成本如图5所示。

表2 算法初始设定值Table 2 The initial setting of the algorithm

图5 不同算法优化供应链成本结果对比Fig.5 Comparison of supply chain cost optimization results by different algorithms

将改进后的蜉蝣算法应用于三级供应链库存模型中,FA算法易陷入局部最优解,MA算法收敛速度慢,PSO算法收敛精度没有达到。MOA能够避免陷入局部最优解,同时成本减少9.5%,证明MOA用于供应链库存模型中有更快的收敛速度,更高的收敛精度。

4 结论

针对基本蜉蝣算法全局搜索能力不足、局部容易陷入最优的现状提出了多策略混合优化的蜉蝣算法。一方面,受粒子群算法中惯性权重因子改进的启发,引入了先慢后快的非线性惯性权重因子,在此基础上又提出改进种群间吸引力系数。另一方面,提出了组中值位置概念,并将其应用于蜉蝣算法的速度更新中。通过8组测试函数进行实验验证,证明改进后的蜉蝣算法MOA在搜索速度、收敛精度上要优于其他算法,并且优势明显。同时,将改进后的MOA应用在供应链PID参数优化上,通过优化各节点订货策略降低供应链总成本9.5%,通过MOA整定的PID参数可以使供应链库存系统有更好的性能。证明了MOA在实际应用上的适用性。