崔京城 瞿慧

摘要：烟花算法作为一种新型群体智能优化算法，在众多领域得到成功应用。联合采购品种的不断扩大对算法性能提出了巨大挑战。针对联合补货问题设计了基于烟花算法的求解方案，并利用基础算例证明方案有效性。随机生成的大规模算例表明，烟花算法相较于混合差分进化算法，在求解大规模联合补货问题时可获得更优的近似最优解，具有更快的收敛速度和更高的稳定性，验证了烟花算法在混合整数规划方面的应用效果。

关键词：烟花算法;联合补货;资源整合

DOI：10.11907/rjdk.192329 开放科学（资源服务）标识码（OSID）：

中图分类号：TP319文献标识码：A 文章编号：1672-7800（2020）006-0176-06

0 引言

为响应国家节能减排的号召，顺应采购全球化发展趋势，众多大中型制造业、零售业企业逐步认识到资源整合利用是企业成本控制的关键，并在实际运作中联合同行或供应链合作者进行采購、运输资源的整合利用。例如，2016年苏宁和天猫首次对部分商品进行联合采购，以节约采购和管理成本;白云山等6家药企拟筹建联合采购平台。在这种运作模式下，联盟企业不仅能分摊采购、运输过程中的固定成本，还能达到采购、运输的规模效应。随着更多企业采用该模式，联合补货的品种规模越来越大，成本优化时产生的数据量大幅增加。由于联合补货问题（Joint Replenishment Problem，JRP）已被证实为非确定性多项式困难（Non-deterministic Polynomial Hard，NP-hard）问题，问题规模的扩大势必对求解算法的性能提出更高要求。

2010年了an&Zhutzl根据烟花爆炸产生火花这一自然现象提出烟花算法（Fireworks Algorithm，FWA）。作为一种新颖的群体智能算法，其被成功应用于众多领域的优化问题，如车间调度、设施选址、物流运输调度、路径优化问题、仓库系统布局、图像识别与处理、施肥问题等。从现有研究来看，尚无文献用FWA求解库存组合优化问题。

本文首次尝试应用FWA算法求解JRP问题，针对该问题设计基于FWA的JRP求解方案，通过已有文献中JRP的基本算例进行计算，验证求解方案和FWA有效性。为应对实践联合采购规模不断扩大的趋势，设计不同维度的JRP，生成随机算例，将FWA运行结果与目前广泛应用于联合补货问题的混合差分进化算法运行结果进行对比，证明FWA算法具有较强的寻优能力、鲁棒性和收敛速度。

1 联合补货问题概述

经典联合补货问题（Joint Replenishment Problem，JRP）的假设条件与经济订货批量模型比较相似，它假设每种物品的需求速度是均匀已知的，不允许缺货，没有数量折扣，订货后物品可立即得到补充，库存持有成本为线性。JRP的目标是使总年平均成本最小化，总年平均成本由固定订购费用、可变订购费用和库存持有费用3部分组成。联合补货策略主要通过将不同时期的采购物品按一定分组规则进行分组，对组内物品进行联合采购，以达到经济规模效益和分摊主要订货成本的目的，从而降低总采购成本。对联合补货策略而言，主要有两种分组策略，即直接分组（Direct Grouping Strategy，DGS）与间接分组（Indirect Grouping Strategy，IGS）。为方便后续描述，对模型中使用的符号进行说明，如表1所示。

1.1 基于间接分组的联合补货模型

在间接分组策略下，每类物品补货周期T_i是T的整数倍k_i，则物品i的补货周期为T_i=k_iT，物品t的补货量为Q_i=D_iT_i=D_ik_iT。

年库存持有成本为：

目标是确定各个k_i和T，使总成本最小。

1.2 基于直接分组的联合补货模型

直接分组是直接将n种物品分为m组，每组均确定一个固定的补货周期T_j（j=1，2，…，m），在每次订货时每组中的每个物品均需要进行补货。依据式（3），可以得出在直接分组策略下总年平均成本TC的公式。

Eijs等对这两种策略进行了对比，得出当主要准备费用比较高时，间接分组策略比直接分组策略更好。

综上可知，间接分组模式下，物品不是预先进行分组，而是根据各自补货周期乘子k_i动态分组。在循环周期内如果物品补货周期乘子众;具有倍数关系或相同公倍数（如1，2，3，2，1），则在其倍数或相同公倍数的补货时期，对应物品自动分配在一组进行补货（第2个时期——倍数关系，物品1、2、4、5一起补货;第6个周期——相同公倍数，所有物品一起补货），从而达到分组补货的目的。简而言之，间接分组是根据物品补货周期动态分组，而直接分组则是直接划分物品，划分在一组的物品具有相同补货周期。

2 烟花算法

研究者通过模拟烟花爆炸“由一到众”产生新生代火花并照亮周围区域的现象，提出烟花算法对种群个体进行多点同时爆炸式搜索，使其在求解复杂的优化问题时表现出非常优良的性能。这种区别于传统算法的新型搜索方法能够在全局搜索和局部搜索中达到一个平衡，以更高的概率跳出局部最优解的“坑”，避免出现“早熟”现象。烟花算法基本流程与其它群体智能优化算法类似，包括3个基本运算：烟花爆炸、烟花变异和下一代烟花的选择。烟花算法基本执行流程如图1所示。

2.1 爆炸运算

烟花算法爆炸运算中涉及两个主要爆炸算子：每个烟花爆炸产生的火花数和爆炸半径，前一个算子控制爆炸强度，后一个算子控制爆炸幅度。

（1）爆炸火花数。烟花算法通过该算子让适应度数值好的烟花产生的火花数较多，避免寻优时火花个体总在最优值附件摆动。反之，对于适应度值差的火花，减少其产生的火花数，适度进行其余空间探索。假设总共有N个烟花，则第i（i=1，2，…，N）个烟花x_i爆炸时产生的火花数量F_S_i计算公式为：

其中，SN为常数，用来限制产生的火花总数;Y_worst为当前种群中最差适应度值;f（x_i）为个体x_i的适应度值;ε为一个极小常数，避免出现除零运算。此外，为防止烟花爆炸产生的火花数过多或过少，对F_S_i进行修正运算。

其中，round（·）为取整函数;a、b为给定常数。

（2）爆炸半径。该爆炸算子基本思想是让适应度数值好的烟花爆炸幅度较小，以实现很好的开采性能;适应度数值差的烟花产生较大的爆炸幅度，对搜索空间有效勘探。第i（i=1，2，…，N）个烟花x_i爆炸半径由式（7）得到。

2.2变异运算

为了增加种群多样性，烟花算法利用高斯變异按照预设参数产生GN个高斯变异火花。第l（l=1，2，…，GN）个火花第k（k=1，2，…，z）维数值计算公式为：

x_l，k=x_l，k+Gaussian（1，1） （9）

其中，Gaussian（·）为高斯函数。

2.3 映射规则

烟花算法在执行爆炸和变异的过程中，所产生的火花有可能超过原有解空间范围，为了对超出边界范围的火花进行修正，采用式（10）的映射规则进行处理。

2.4 选择运算

执行爆炸运算和变异运算后，烟花、爆炸火花和高斯变异火花中的最优个体自动保留到下一代，采用轮盘赌的方式选择剩余N-1个个体，个体x_i被选择的概率为：

其中d（x_i，x_j）表示个体x_i和个体x_j之间的欧式距离，M为烟花、爆炸火花和变异火花总数。

3 基于烟花算法的联合补货模型求解方案设计

3.1 基于烟花算法的JRP问题编码解码

智能优化算法在进行应用之前，必须针对问题特点，对决策变量和目标函数进行分析，设计合理的编码解码机制，这是算法顺利实施的前提。

因此，在间接分组策略下JRP问题的编码解码设计思路为：编码时，随机生成n维0-1之间的随机数;再通过变量上下界，对n维随机数按式（14）进行解码得到补货周期乘子，即可将补货周期乘子带人式（13）得到对应的最优成本值。

假设决策变量k_i的上界为10，JRP问题编码解码如图2所示。

此时编码和解码方式同间接分组策略下的方式，由图3可知，通过解码，物品1分在第1组;物品2和物品3分在第2组，依次类推。

3.2 基于烟花算法的JRP求解流程

（1）初始化。对算法参数、问题参数进行初始化。同时，根据编码方式，结合求解算法初始化种群。

（2）计算初始烟花适应度。首先按式（14）对个体进行解码，解码过程中，按照文献和文献中的方法设置决策变量上下界。解码后，在间接分组策略下，根据式（13）计算总成本;直接分组策略下，根据式（15）先分别计算每组物品的JRP成本，再对每组物品JRP成本进行累加，得到总成本。

（3）按2.1节中的描述计算爆炸算子，执行爆炸运算，得到爆炸火花。

（4）按2.2节中的描述执行变异运算，得到高斯变异火花。

（5）合并爆炸火花和高斯变异火花，按2.3节的规则对出界火花进行处理。

（6）按2.4节的方式，采用轮盘赌的方式从初始烟花、爆炸火花和高斯变异火花中选择下一代烟花，并保存当前最好值。

（7）判断是否达到终止条件，如果迭代次数达到了既定的最大迭代次数或求解精度达到要求，则停止搜索操作，输出最优值;否则，对新烟花种群再次执行步骤（3）-（6）中的操作，直至满足条件为止。

4 仿真实验与结果分析

4.1 参数设置

为测试、分析FWA求解JRP问题的性能，本文选取文献中的问题参数（见表2），同时扩大问题维度，随机生成算例进行仿真实验。随机算例问题参数见表3。FWA求解结果与目前应用于JRP问题中表现良好的混合差分进化算法（Hybrid Differential Evolution Algorithm，HDE）、混合自适应差分进化算法（Hybrid Self-adaptive Differential Evolution Algorithm，HSDE）的计算结果进行比较，算法参数设置见表4。

由于FWA在迭代过程中，爆炸火花总数是动态的，如果直接以进化次数作为迭代终止条件，则可能导致FWA参与寻优个体远远多于HDE和HSDE，缺乏比较的公平性。当火花总量（即参与寻优的个体数量）达到问题维度dim*10000时，FWA算法停止。据此，对应地将HDE和HSDE算法进化代数设为round（dim*10000/Np）（Np为种群数量）。尽管该设置方式会使FWA参与迭代的个体数偏多，但可达到相对公平性。

4.2 算例分析

随机性算例在不同规模下分别随机生成5个问题，针对每个问题3种对比算法均在Matlab中分别运行20次，平均最好最优厂C见表5。图4和图5分别为在间接分组策略下和直接分组策略下，3种算法分别运行基础算例的收敛曲线。图6为问题规模扩大到100时，3种算法单次运行随机生成算例的收敛曲线。

结合表5、图4-图6可看出：

（1）在求解质量上，对于基础算例，FWA可得到与文献相同的最好最优解;当问题规模为10、50时，3种算法均能100%找到相同的最好最优解;当问题规模扩大到联合采购100种物品时，无论是采用间接分组策略还是直接分组策略，FWA计算的最好最优解质量优于其它两种算法。

（2）在收敛速度上，FWA可在偏离最好最优解最远的情况下，快速收敛到最好最优解，在直接分组策略下的优势更为明显。

5 结语

本文首次尝试采用烟花算法求解联合补货问题，设计了基于烟花算法的联合补货问题求解方案，通过已有文献中的基础算例验证了求解方案和算法有效性;为应对实践中联合采购规模不断扩大的趋势，将问题规模扩大到100，选取目前应用效果较好的HDE算法、HSDE算法与该算法进行对比分析，结果证明烟花算法在求解质量、收敛速度和鲁棒性方面表现更佳，可作为应对大规模JRP问题及其拓展优化问题的一个备选算法。本文是烟花算法在联合补货领域的探索性研究，针对扩展的联合补货问题，如何结合问题特点和算法机理，对算法进行改进，使之更好地应用于更复杂的现实问题是后续研究方向。