鲜奶采购计划的改进自适应罚函数遗传算法

钟金宏 黄 玲

1.合肥工业大学，合肥，230009

2.过程优化与智能决策教育部重点实验室，合肥，230009

0 引言

本文研究一个实际奶制品企业的经济批量问题。奶制品企业为迅速进入某地市场，在当地设立加工分厂，分厂鲜奶主要来自总部的自有规模化养殖场，每天由奶罐车循环运奶，分厂独立经营需付费给总部；总部的鲜奶产量和奶罐车数量有限，而客户的需求是变动的，因此分厂有时需要从当地采购鲜奶；但为了保障品质，将优先考虑自产鲜奶。根据客户订单或市场预测，分厂可以计算出自己的鲜奶需求；但由于奶制品销售受天气和节假日等影响较大，在春节等销售旺季，经常出现断货和延期交货的现象。该问题可建模为动态离散经济批量模型，从总部运奶可看做是生产，从本地采购鲜奶可看作是外包，分厂的鲜奶需求可综合考虑生产、外包、库存和延期交货等策略来满足。

Wagner等［1］最先研究了该问题，但未考虑外包和生产能力限制。生产能力受限的经济批量问题是 NP难题［2－3］，仅在一些特殊情况下是多项式可解的［3－8］。外包是企业间协作的常见形式，也是企业应对复杂多变需求的主要手段。目前，考虑外包（或失去销售）的经济批量问题研究很少，文献［9－13］中关于外包、转包和失去销售方面的经济批量研究可归为此类研究，因为它们从建模的角度来说是一样的。现有研究可分为三类：无能力限制情况［9］、库存有界情况［10］和生产能力受限情况［11－13］。Sandbothe等［11］分别研究了恒定和时变生产能力的情况，但成本参数是常量，且未考虑失去销售量限制。Sandbothe等［12］又研究了有时变库存和生产能力限制的同样问题，但模型参数仍为常量。Atamtürk等［13］考虑了恒定生产能力约束情况，但未考虑外包量的限制，分别研究了一般凹成本和非投机性成本函数情况。文献［11－13］均没有考虑延期交货策略。

根据问题实际情况，本文同时考虑时变成本参数、时变生产能力约束、外包量受限于当前周期需求和允许延期交货情况，提出了一个新的基于群体可行状况和个体约束违背程度的自适应罚函数，开发了相应的遗传算法，并通过大量仿真实验验证了所提自适应罚函数的有效性，比较了自适应罚函数相对其他罚函数的优势。

1 问题模型

通过推算，分厂可获知在未来T周期规划时段上的需求dt，dt＞0，t＝1，2，…，T。令xt和Lt分别表示周期t的生产量和外包量；It表示周期结束时的库存；Ct表示周期t的生产能力；pt（xt）、λt（Lt）、ht（It）分别表示生产、外包和库存/延期交货成本函数，它们为一般凹函数，则引言中描述的问题（P1）可表示为

目标函数（1）用来最小化规划时段内的总体生产、外包、库存及延期成本；状态等式（2）为物料平衡公式；不等式（3）表示每周期生产量是非负的，且不超过当前周期生产能力；约束（4）要求每周期外包量非负，且不超过当周期需求；等式（5）表示规划期开始和结束时库存为0。显然，该问题为NP难题。

2 自适应罚函数遗传算法

遗传算法是求解优化问题的有力工具，但其自身有较多参数需要确定，合理设定这些参数需根据问题具体处理，主观性较强。根据当前和前面的搜索情况，自适应调整算法参数是一个很好的选择，在文献［14－19］中都有报道。其中，报道最多的是交叉及变异概率自适应和罚函数参数自适应。本文设计了一种新的能根据搜索过程反馈信息调整罚函数系数的自适应遗传算法，图1为算法流程图。

图1 自适应遗传算法流程图

遗传算法本质上只能求解无约束规划问题，对约束规划问题，常用处理方法有：罚函数方法；设计不可行解修正算法；设计特殊的编码和遗传算子。问题（P1）是约束规划问题，存在两类约束：每周期存在生产和外包能力约束；要求规划期开始和结束时库存为零。

2.1 生产和外包能力约束处理方案

在二进制编码的遗传算法中，可行解是针对显型空间来说的，在基因型层次，并没有可行和不可行说法，因此，可通过设计特殊的解码算子，直接将基因空间的基因型映射为显型空间的可行显型，从而解决不可行问题。在处理第一类约束时使用了该思想，有效地降低了需处理约束的个数，减小了算法在获取可行解方面的代价。对n位二进制编码的基因段，假定它对应的十进制数为value，其在十进制显型空间的可行范围为［fmin，fmax］，则可采用下式将它映射入可行区域：

式中，fvalue为映射的可行显型值。

2.2 零库存约束处理方案

问题假定规划期开始时库存为零，如不为零则可通过修正初始周期约束来转换，成为开始库存为零的等价问题。规划期结束时库存为零，这是所研究规划问题的要求，但遗传算法是一种有导向的随机搜索过程，得到的解不一定能保证最终库存为零，因此，它是算法需要处理的约束。但如因管理需要，在规划期结束要保有库存，这部分库存在研究上可处理成最后周期需求。这里，规划期结束库存不为零是因算法本身造成的，而非管理策略要求的。

静态罚函数法易导致算法早熟或收敛缓慢，动态罚函数法未根据算法的实际运算情况动态调整惩罚系数，自适应惩罚［14－16］利用迭代过程的反馈信息动态调整惩罚系数，避免了上述问题，在一些文献的报道中均取得了较好效果。文献［14－15］中的自适应惩罚函数方法均不同程度地需要人工确定附加参数，影响了算法的可扩展性。文献［16］设计了一个基于当前群体中不可行的状况来改变惩罚程度的方案，避免了确定附加参数。该方法有利于避免算法早熟，但由于它过于强调不可行个体参与遗传操作，经常无法收敛至可行解，或搜索过程过于缓慢。特别是当群体中可行个体很少或没有可行个体时，由于惩罚微不足道，会使搜索发散。本文测试了该方法的可用性，在12周期、24周期、36周期和48周期规划问题上，对选择、交叉和定标算子的120种组合分别进行实验，每个组合运行10次，没有一次收敛至可行解。因此，无法使用该惩罚方案解决本文问题。

为此，本文基于当前群体中可行的状况来确定惩罚系数。在当前群体中，可行个体多时，说明搜索是收敛的，应降低惩罚程度，鼓励不可行个体参与遗传操作，扩大搜索区域，避免早熟收敛；反之，可行个体少时，说明搜索是发散的，应加大对可行个体惩罚，促其收敛。因此，本惩罚方法利用了群体特定信息（可行和不可行区域的比例）和染色体特定信息（不可行解距离可行区域的距离）。引入自适应惩罚后的目标函数为

其中，pop＿size为群体尺寸；feasibles为当前群体中可行解个数，随GA迭代动态变化，取值范围为0～pop＿size，feasibles为0时惩罚系数取一大数，最低惩罚系数是1。

3 算法仿真实验

下面通过仿真实验，测试本文所提自适应罚函数的有效性。问题实例随机生成，采用文献［8］中的季节性需求模式，其他参数由定义在某区间上的均匀分布随机生成（具体设定区间见表1），其中生产能力和需求取整数，其他参数为实数。实例参数设定区间见表1。

表1 问题参数设定区间

3.1 算子组合与罚函数的组合实验

在12周期、24周期、36周期及48周期规划问题上，针对不同算子组合进行静态惩罚（SPF）［17］、动 态 惩 罚 1（DPF1）［18］、动 态 惩 罚 2（DPF2）［19］、自适应惩罚1（APF1）［15］和本文所提自适应惩罚方案2（APF2）的对比实验，从而验证APF2的有效性，同时可确定最好的算子组合。实验中也比较了退火惩罚［14］，但其不能得到可行解，故没有列出。

令＝｛单点，两点，均匀，奇偶｝表示交叉算子集合，c′i（i＝1，2，3，4）表示第i个交叉算子。类似地，R′＝｛赌轮，联赛，排序，随机均匀采样，确定性采样，剩余随机抽样｝表示选择算子集合，r′j（j＝1，2，…，6）表示第j个选择算子，Š＝ ｛无定标，线性，幂函数，σ截断，适应度值共享｝表示定标方法的集合，šk（k＝1，2，…，5）为第k个定标方法。c′ir′jšk表 示一个算 子 组 合，共 有120种 组合，按从左向右、深度优先原则编号。与5种惩罚方法结合，共有600种组合，每个组合运行10次，共运行6000次。实验中，最大迭代代数为800，群体尺寸为50，交叉概率为0.9，变异概率为0.01。分别测试了12周期、24周期、36周期及48周期规划问题。为全面反映实验情况，实验结果以图形形式提供，见图2。图中，横坐标为算子组合标号（1～120）；纵坐标为10次运行的最终解的成本平均值；“○”代表该算子组合的10次运行最终解均不可行的情况。

由图2可得：①在5种罚函数中，本文提出的自适应惩罚方法（APF2）效果最好，在4个规划问题上对所有算子组合都获得了最低平均成本。②总体上，采用联赛和排序选择的组合效果较好，这两类组合在4个规划问题上都优于其他组合，且对不同惩罚方法该结论基本上都成立；具体来说，对于12周期和24周期规划问题，联赛选择的最终解均值要低于排序选择；对于36周期规划问题，排序选择的最终解均值略好于联赛选择或基本相当；对于48周期问题，排序选择的最终解均值低于联赛选择。

图2 算子和惩罚方法的组合实验结果

表2为表现较好的算子组合c′2r′2š4和c′1r′3š4的运算结果展示，从表2中可看出，本文提出的自适应惩罚方法效果最好，10次运行的最终解均值小于其他惩罚方案。

表2 不同惩罚方法在4个规划问题上的表现

3.2 遗传算子概率对算法性能的影响

交叉和变异概率对GA的性能和行为有重要影响，常见的算子概率处理方式有：①选择算子概率的指导规则，它未必适合所要解决的问题；②自主自适应调整方案，对算子概率进行编码，进行同步优化，其计算代价较大；③自适应动态调节研究，自适应动态调节在无约束优化问题中有很多报道，在约束优化问题上有针对可行群体的概率调整报道，但保证群体可行需要采用特殊的约束处理方法，这比较困难。本文提出的惩罚函数处理约束方法不能保证每代群体中的所有个体都可行，因此，本文采用实验尝试法选择适合的算子概率，同时也观察算法对算子概率的敏感性。

组合实验条件为：交叉概率变动范围为0.5～1.0，步长为0.05；变异概率变动范围为0～0.475，步长为0.025，每个组合运行10次。实验中，采用两点交叉、排序选择和适应度共享定标。图3所示为在12周期问题上的实验结果。图中，横坐标为交叉概率Pc和变异概率Pm，在间隔［b，b＋0.05）内，Pc＝b，Pm从 0 开 始 以 步 长0.025增至0.475；纵坐标分别为10次运行可行最终解的次数、收敛代数和成本的均值；“○”代表该组合的10次运行最终解均不可行的情况。从图3可看出，交叉概率在0.5～1.0之间变化，算法对其不敏感；变异概率应大于零且小于0.025，在该范围外会出现问题解不可行情况。后续实验中取交叉概率为0.9，变异概率为0.01。

图3 概率组合对最终解可行的影响

3.3 最终实验结果

对12周期、24周期、36周期和48周期规划问题和5种惩罚方法，算法分别运行50次。根据前面实验，采用两点交叉、排序选择和适应度共享定标，交叉概率为0.9，变异概率为0.01。由于惩罚方法APF1在36周期和48周期问题上出现了不可行最终解，对这2个问题仅给出4种惩罚方法的运行结果。

数据表适合少量数据的比较，但对于大量数据比较，则显得杂乱和不直观。由于实验中数据比较多，故采用雷达图显示实验结果，见图4。图中，极轴标号1～50代表算法50次运行的序号；每次运行的最终解对应成本作为极径，标注在相应的极轴上，构成一个极坐标点，将50次运行的极坐标点连起来形成一个不规则闭环，描述了某种惩罚方法50次运行中最终解对应成本的变化。不同惩罚方法对应颜色深浅不同的不规则闭环。位于最内部的不规则闭环不会被其他闭环覆盖，表示采用该惩罚方法，最好染色体的成本最低。从图4可看出，在4个不同周期的规划问题上，本文提出的惩罚方法APF2对应的不规则闭环位于罗盘图的最内部，性能最好。

运用本文设计的自适应惩罚遗传算法，可得到奶制品加工厂的鲜奶采购计划，限于篇幅，这里以12周期规划问题为例给出优化结果，见表3。

图4 不同惩罚方法的50次运行结果的雷达图比较

表3 12周期规划问题的运行结果（总成本为11862.5）

4 结语

本文研究了生产能力受限的动态经济批量问题，该问题抽象于一个实际奶制品加工厂的鲜奶采购问题，涉及企业如何合理运用内购（生产）、外购（外包）和延期交货等策略来最优地满足客户需求。提出了一个新的自适应罚函数，设计了相应的遗传算法。与其他自适应罚函数相比，本惩罚方案不需人工设定附加参数，且综合考虑了当前群体可行状况和个体距离可行的距离。设计了大量仿真实验，验证了本惩罚方案的有效性和优势。

［1］Wagner H M，Whitin T M.Dynamic Version of the Economic Lot－size Model［J］.Management Science，1958，5（1）：89－96.

［2］Florian M，Lenstra J，Kan A R.Deterministic Production Planning：Algorithms and Complexity［J］.Management Science，1980，26（7）：669－679.

［3］Bitran G，Yanasse H.Computational Complexity of the Capacitated Lot Size Problem［J］.Management Science，1982，28（10）：1174－1186.

［4］Florian M，Klein M.Deterministic Production Planning with Concave Costs and Capacity Constraints［J］.Management Science，1971，18（1）：12－20.

［5］Janannathan R，Rao M.A Class of Deterministic Production Planning Problems［J］.Management Science，1973，19（11）：1295－1300.

［6］Hoesel C P，Wagelmans A P.An O（T3）Algorithm for the Economic Lot－sizing Problem with Constant Capacities［J］.Management Science，1996，42（1）：142－150.

［7］Chung C，Lin C.An O（T2）Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem［J］.Management Science，1988，34（2）：420－426.

［8］Heuvel W，Wagelmans A P.An Efficient Dynamic Programming Algorithm for a Special Case of the Capacitated Lot－sizing Problem［J］.Computers ＆Operations Research，2006，33（12）：3583－3599.

［9］Aksen D，Altinkemer K，Chand S.The Single－item Lot－sizing Problem with Immediate Lost Sales［J］.Eur.J.Oper.Res.，2003，147（3）：558－566.

［10］Chu F，Chu C.Single－item Dynamic Lot Sizing Models with Bounded Inventory and Outsourcing［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2008，30（1）：70－77.

［11］Sandbothe R A，Thompson G L.A Forward Algorithm for the Capacitated Lot Size Model with Stockouts［J］.Operation Research，1990，38（3）：474－486.

［12］Sandbothe R A，Thompson G L.Decision Horizons for the Capacitated Lot Size Model with Inventory Bounds and Stockouts［J］.Computers ＆ Operations Research，1993，20（5）：455－465.

［13］Atamtürk A，Hochbaum D S.Capacity Acquisition，Subcontracting，and Lot Sizing［J］.Management Science，2001，47（8）：1081－1100.

［14］Coello C A.Theoretical and Numerical Constraint－Handling Techniques Used with Evolutionary Algorithms：a Survey of the State of the Art［J］.Computer Methods in Applied Mechanics and Engineering，2002，191（11/12）：1245－1287.

［15］Hadj－Alouane A B，Bean J C.A Genetic Algorithm for the Multiple－Choice Integer Program［J］.Operations Research，1997，45（1）：92－101.

［16］Dadios E P，Ashraf J.Genetic Algorithm with Adaptive and Dynamic Penalty Functions for the Selection of Cleaner Production Measures：A Constrained Optimization Problem［J］.Clean Tech.Environ Policy，2006，8（2）：85－95.

［17］Homaifar A，Qi C X，Lai S H.Constrained Optimization Via Genetic Algorithms［J］.Simulation 1994，62（4）：242－254.

［18］Joines J，Houck C R.On the Use of Non－stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems with Gas［C］//Proceedings of the First IEEE International Conference on Evolutionary Computation.Orlando，1994：579－584.

［19］Kazarlis S，Petridis V.Varying Fitness Functions in Genetic Algorithms：Studying the Rate of Increase in the Dynamic Penalty Terms［C］//Proceedings of the 5th Int.Conf.on Parallel Problem Solving from Nature.Berlin，1998：211－220.