改进的蛙跳算法在库存匹配中的研究

曾伟渊

(厦门软件职业技术学院)

0 引言

当前库存匹配问题主要集中在钢铁等流程行业，在钢铁、石化等流程行业的生产经营主要面临两方面的问题:一方面要在复杂的工艺条件下实现生产的连续性，第二客户对最终产品在规格、种类、数量和交货期上的各种要求需要满足［1］.与钢铁、石化等行业类似，在磁性材料生产管理过程中，为了实现非订单库存产品的有效利用，需要将其与客户下达的生产订单进行匹配.针对钢铁企业生产过程中订单与库存之间的匹配问题Trumbo等人对其做了重要的贡献，他们主要针对工艺路线和生产组织等特殊的约束条件的库存匹配问题进行研究，并提出了解决方法［2］.库存匹配问题可以与多背包问题(MKP)进行类比，均属于被证明为NP难的组合优化问题［3－4］.

针对基本混洗蛙跳算法(SFLA)收敛速度慢、优化精度低且易于陷入局部最优的问题，对其进行多项改进.采用随机分组策略，平衡各子群的寻优能力，保持种群多样性;打破最差蛙只向最优蛙学习的模式，引入Minkowski距离，使最差蛙借助更多同伴信息选择进化方向，增强种群适应性;针对最优蛙进化机会少，引入精英策略和变异思想更新其位置，避免陷入局部极小，加快收敛速度，最后选取合适的目标函数，将改进前后混洗蛙跳算法(ISFLA)用于冷轧液压伺服位置(APC)系统的PID参数整定，并将整定结果进行西门子PLC实验验证，结果表明改进后算法的有效性和高效性.

1 库存匹配问题描述

库存匹配的流程图如图1所示.

人工库存匹配工作量大，库存匹配时间长，生产订单拖期严重，同时，选取的最终匹配结果，不一定是最优的或近似最优的.因此该文采用改进的蛙跳算法进行库存匹配问题的研究的.

2 库存匹配数学模型

针对库存匹配问题，首先给出了参数与变量的符号定义.i:订单序号;l:库存微粉编号;IS:生产订单集合;LS:库存微粉集合;ai:计划员给定的生产订单i库存匹配的优先级系数;di:订单i的交货日期;gi:生产订单i的牌号编码;bl:库存微粉l的桶号;rl:库存微粉l是否为预留微粉，若rl=1，则为预留微粉;否则，非预留微粉;Ωi:满足生产订单i要求的库存微粉集合，;Ωi⊆LS:Ψl库存微粉l能够匹配的生产订单集合，φl⊆IS;ωi:实际匹配生产订单i库存微粉集合，ωi⊆Ωi;xl(i):若库存微粉l被匹配给生产订单i，则为1;否则为0;Wl(i):若库存微粉l被匹配给生产订单i的重量.

图1 库存匹配流程图

(2)目标函数和约束

目标函数(1)最大化库存匹配的微粉重量;目标函数(2)最大化匹配出的微粉的入库时间;目标函数(3)最大化匹配出的微粉的氧含量;目标函数(4)最小化匹配出的微粉的平均粒度.约束(5)库存微粉的牌号与生产订单的牌号属于同一性能序列且不低于订单要求;约束(6)一个生产订单最多与三个库存编号的微粉匹配;约束(7)与一个生产订单匹配的多个微粉的入库时间偏差不超过30 d;约束(8)生产订单匹配的库存粉重不能超过生产订单的需求量.

3 改进的蛙跳算法

3.1 基本混洗蛙跳算法存在的问题

(1)对于基本的混洗蛙跳算法，有序的分组方法使得越靠前的子种群，其平均适应度值越高，全局最优解往往存在于这样的分组里，因此，即使每一组每代更新最差蛙，也是这样的分组得到新的全局最优解的概率最大，寻优能力强于其他分组，这为整个种群容易陷入局部极值埋下了隐患.

(2)根据基本的混洗蛙跳算法，最差蛙可能的新位置被限制在当前位置和最优蛙位置的线性区域，最差蛙永远跳不出最优蛙.即使当最差蛙的新位置无法得到改善而产生随机解，然而并不能保证随机解一定会更优.结果，这种蛙跳规则限制了本组进化的搜索空间.同时，最差蛙仅仅被最优蛙影响，并没有做到个体间充分的思想交流，降低了种群的适应性.除此之外，最优蛙在跳跃过程中很少有机会进化，这造成算法的学习机制不充分，种群多样性减少，从而导致早熟收敛［7］.

3.2 随机分组策略

为解决基本混洗蛙跳算法的第一个缺陷，从改进全局搜索方式的角度出发该文提出了对青蛙进行随机分组的策略.

随机分组策略的主要思想是:首先，按照适应度值由大到小将N只青蛙进行排序;其次，将整个种群划分成n个独立的子种群;第三，实现每个子种群包含解的个数是m个，并且在算法迭代过程中，前n个解需要随机进入不同的n个子种群，同时实现每个解只能进入一个子种群，依此类推，直到所有解分配完毕.

采用上述的随机分组策略，使得各个子种群通过不断的更新以得到新的全局最优解的机会均等.该策略强化了子种群的寻优能力，实现了种群的多样性，避免了蛙跳算法陷入局部最优［5］.

3.3 最差蛙改进策略

考虑原算法各子群中最差蛙的进化仅仅利用到最优蛙的信息，于是在此基础上引入Minkowski距离，使其不仅仅向最优蛙学习，而且向该子群中其他个体学习，使得最差蛙能充分利用所得到的信息来判断向哪个方向进化，而不是局限在和最优蛙的单一的直线方向上，从而加快进化速度，并且当该系统突发扰动时，由于集体的力量，使得适应能力提高，鲁棒性增强.最差蛙位置更新公式如式(9)所示.

其中，Xi表示子种群中的第i只青蛙，S(i)表示子种群中最差蛙受第i只青蛙影响后得到的实际步长，c1表示同一种群中最差青蛙和另外随机选取的一只青蛙的学习因子，取值范围是(0，1)之间的随机数.c2表示整个种群的全局最优蛙与该种群中的最差蛙的学习因子，其中范围为(0，1)之间的随机数.M(Xi，Xw)表示Minkowski距离，即子种群中的最差解与第i个解之间的实际距离.

3.4 次优蛙改进策略

在基本混洗蛙跳算法中，最优蛙几乎不进化，大量仿真实验证实最优蛙的地位一般会被保持很多代，造成算法寻优速度慢，易出现早熟收敛，不能真正寻到目标函数的最小值.

该文借鉴精英策略，保留每个种群中的最优蛙，以防最优蛙向较坏方向变异后造成没有全局最优解的局面，出现解的退化现象.因此次优蛙的改进策略如下:首先，选择每个子种群中的次优蛙在小概率事件时出现变异;其次，让其以自身所在的位置为中心，以到该种群中最优蛙的距离作为最大半径进行全方位的搜索，若适应度值无变化，则需要在种群中最优蛙邻域范围内产生一个新解，方式是采用随机的方法［6，8］.其中，次优蛙的变异公式如式(11)所示.其中，Xg'为每组次优蛙变异完后的候选解，rmax为自身到本组最优蛙之间的最大半径，θ为(0，360°)之间的随机数.

4 仿真研究

为了实现对算法的有效性的进一步验证，将该文提出的改进蛙跳算法与人工库存匹配的排序搜索(largest first fit，LFF)规则进行比较，具体比较结果如下.

根据上文提出的LFF算法对应的规则以及两种算法实际执行过程中的策略，将其与该文提出的改进蛙跳算法进行了对比实验，实验结果见表1.针对磁性材料实际现场的中等规模问题，以计算时间、“以好充次”的比例和最终匹配的生产订单总重量等三个作为评价指标的具体数值实验结果.

表1 100桶微粉20个生产订单的仿真结果

通过上面的仿真实验可以得到以下的比较结果:

(1)与“LFF规则+策略A”的算法相比，该文提出的改进蛙跳算法虽然在匹配生产订单总重量方面略差，但是在库存微粉“以好充次”的比例方面有着非常大的优势，说明了算法的有效性.

(2)与“LFF规则+策略B”的算法相比，该文提出的改进蛙跳算法仅仅用少量的库存微粉“以好充次”为代价，便获得了在匹配生产订单总重量方面非常好的效果，说明了算法的有效性.

(3)在计算时间方面，该文提出的改进蛙跳算法较LFF规则的算法略高.但是根据该实验的仿真结果，该文提出算法的计算时间也在可接受的范围内，算法的效率是完全满足实际现场要求的.

5 结束语

该文从基本混洗蛙跳算法的原理出发分析了其存在的问题，进而有针对性地提出了相关的改进策略;使得该文提出的混洗蛙跳算法能以更加接近生产实际的方式实现磁性材料库存匹配问题的求解.通过该文仿真结果可以看出，改进后的混洗蛙跳算法优化精度高、收敛速度快、适应性和鲁棒性强，并有效克服了原算法早熟、易陷入局部最优的缺陷，并且可以在较短的时间内解决较大规模的生产订单库存匹配问题，并获得完全满足实际现场要求的可行解.

［1］Rajagopalan S.Make to order or make to stock:Model and application［J］.Management Science，2002，48(2):241–256.

［2］Tnunbo M，Kalagnanam J，Lee H.IBM Research Report:A Solution Architecture for Inventory Application Problems in the Steel Industry.Unpublished Results，1998.

［3］Pisinger D.An Exact Algorithm for Large Multiple Knapsack Problems.European Journal of Operational Research，1999，114(3):528–541.

［4］Martello S，Toth P.Knapsack Problems:Algorithms and Computer Implementations.Wiley，Chichester U K，1990.

［5］Pan Q K，Wang L，Gao L，et al.An effective shuffled frogleaping algorithm for lot－streaming flow shop scheduling problem［J］.Int J of Advanced Manufacturing Technology，2011，52(5/6/7/8):699－713.

［6］Rahimi－Vahed A，Mirzaei AH.A hybrid multi－objective shuffled frog－leaping algorithm for a mixed－model assembly line sequencing problem.Computers and Industrial Engineering，2007，53(4):642–66.

［7］王介生，高宪文.基于改进混合蛙跳算法的电渣重熔过程多变量 PID控制器设计［J］.控制与决策，2011，26(11):1731－1734.

［8］Huynh T H.A modified shuffled frog leaping algorithm for optimal tuning of multivariable PID controllers［C］.IEEE Int Conf on Industrial Technology.Perth:IEEE Press，2008.1–6.