基于准时化生产要求下改进型粒子群算法研究

(浙江工业大学 信息工程学院，浙江 杭州 310023)

在这个日新月异的市场环境下，竞争日益加剧，人们对个性化产品的追求与日俱增，越来越多的企业面临升级转型。由传统粗放型、大规模批量生产转向面对客户个性化需求的小规模、多批次的以市场和客户为导向的新型生产模式[1]。以下主要研究在此种新模式下，企业如何能按照订单要求准时将产品送达客户手中。为达到这一目标，企业生产过程中原材料、半成品的准时化配送就显得十分重要。传统的“领料式”配送方式，配送周期全凭经验，以生产要料为主导，缺乏主动配送思想，配送效率低[2]。为实现对多目标条件下的准时化配送，通过研究改进型粒子群算法[3]，合理地安排物料配送方式，并将此算法与粒子群算法、遗传算法和三段启发式算法[4]进行比较验证，分析算法的有效性。

1 多目标材料配送模型

1.1 配送时间点选取

生产制造工程中，材料的配送时间点选取至关重要，以往常由生产线工人的经验决定，但在多样化、面向订单、个性化生产模式下，产品的种类变化多样，经验效应的可靠性受到很大影响，容易造成材料被过早或过迟配送到工位的情况，从而造成生产线旁材料的堆积或生产待料的情形[5]。因此为保证制造型企业准时化生产，合理地选择配送点是先决条件。

现实生产中不能等到工位库存消耗完毕才请求配送，因为材料的运输、装卸都需要时间，而此时工位处于闲置状态，因此必须考虑到材料运输的提前量。就此提出一个优化后的时间惩罚函数模型为

BTi=min(ZTi)+(NLi+KLi-SSi+S0)/Vi

(1)

LTi=min(ZTi)+(NLi+S0)/Vi

(2)

(3)

RTi=(Qi-S)/Vi

(4)

STi=BTi-RTi=min[(S-SSi)/Vi]

(5)

式中：S0为最初生产线旁库存量；SSi为安全库存量；min(ZTi)为最短配送提前量；KLi为工位边的材料保有量；NLi为发送给管控中心的材料需求量；Vi为I材料的消耗速度[6]；Tα为材料的装卸所消耗的时间；RTi为生产线发出材料需求的时间点；STi为最佳送达点的提前量；S为运送量；Tij为运输时间。

对每次配送时间点进行分析，如图1所示，根据优化后的时间惩罚函数进行分析，可较为准确地判定理想材料配送点。

图1 材料配送时间点Fig.1 Material distribution point of time analysis

1.2 配送模型建立

传统一对一或者定点式配送方式，成本高、周期长，缺点明显。在一个制造型企业车间，需要的物料种类繁多，工位与工位之间变换频繁，单一的配送方式极大影响生产。通过引入多目标配送概念，将配送方式优化，求解最优集，并根据实际要求从最优集中选择配送方案[7]。

令目标函数F(x)为

F(x) =G{min[C(x),L(x),T(x)]}

(6)

(7)

(8)

minL(x)=Xi+Yi

(9)

(10)

(11)

minT(x)=ZTi+(NLi+
KLi-SSi+S0)/Vi

(12)

(13)

RTi=(Qi-S)/Vi

(14)

2 改进型粒子群算法的设计与优化

2.1 改进型粒子群算法的设计思路

粒子群算法最初来自于人工生命理论和复杂演化算法，其特点是利用在群体生活中个体间通过一定的交流且共享信息，通过运算反复迭代[8]在短时间内进行全局搜索，寻找出最优解的技术[9]。目前很多国内外专家为改进粒子群算法，常引入惯性权重、修正系数等方式改变初始粒子的速度和位置，以优化公式[10]。但在实际应用时，单一的粒子群算法不足以满足需求，该算法收敛精度较差，容易陷入局部最优，为此提出将遗传算法和模拟退火算法中利于寻优的部分揉合进粒子群算法中，以便提升算法优化准确性，提高搜索效率。

对粒子群算法优化如下：

1) 因为遗传算法依照生物遗传理论对算法中的决策变量进行编码，能够有效应对组合中的2 次分配问题，所以利用此特点将例子采用此方式进行编码。

2) 为防止算法早熟，引入遗传算法中的交叉策略和变异策略，以解决粒子初始位置和速度的不合理选择产生的一系列问题。

3) 为避免在整体寻优过程中出现局部最优的情况，可以运用模拟退火算法中的Meteropolis准则[11]即重复对当前解进行迭代计算，以得到近似最优解。

2.2 改进型粒子群算法设计

根据设计思路，改进型粒子群算法针对实际生产过程中需要多目标工位实现准时材料配送过程的建模过程如下：

1) 以运送材料所需的花费、运送次数、运送所需消耗的时长为目标建立适应函数，并引入权重的系数进行优化评价，其表达式为

(15)

ωC+ωL+ωT=1

(16)

式中：x为个体粒子可行解；ωC，ωL，ωT分别为运送花费的权重、运送次数的权重和运送时长的权重，且3个权重系数之和为1。根据实际生产情况可按照需求分配权重，紧急情况下可侧重时长，一般生产可侧重成本。

2) 编码。因为生产实际中考虑的多个因素作用的共同结果，所以在编码时采用优化运算为

第1 次优化运算：

(17)

第2 次优化运算：

(18)

第S次优化运算：

(19)

式中：T1为第1 次材料运送到的时间；X11为1 号材料运送到1 号工位的数量；Y11为1 号材料运送到1 号位置所需要的车次。式(17～19)分别为改进型粒子群算法运算时第1 次、第2 次和第S次的粒子。

4) 交叉、变异策略。通过对遗传算法中交叉变异策略的研究，采用单点交叉策略，并使用“父对染色体分段—比较选择—复制替换—形成新粒子”的方法形成具有可行解的新粒子。具体操作如图2所示。

图2 交叉、变异策略框图Fig.2 Cross, mutation strategy diagram

该变异策略通过基因突变的方法，使得粒子中的染色体部分片段得以改变，增强了粒子群算法从局部寻优的能力，通过此策略既改变了染色体的基因片段,增加了粒子群的多样性,又可以防止算法早熟现象的出现。

此改进型粒子群算法是基于对全局最优解P的优化，其中新的初始粒子的产生是通过将变异操作前选取的随机数与变异概率ρ进行比较，若随机数大于等于ρ时，P不变，否则就改变P。此时全局最优解P就可以用变异策略产生的随机初始种群粒子来代替。

如图3所示，改进型粒子群算法具体流程如下：

步骤1选取初始粒子位置P和初速度V。

步骤2建立适应函数f(x)，选取合适权重并计算f(x)。

步骤3设计初始种群，确定C(x)，L(x)，T(x)。

步骤4更新个体极值Pi和群体极值Pg。

步骤5更新速度V和位置。

步骤6通过交叉与变异策略寻找全局最优解P。

步骤7计算适应度函数f(x)，得到最优的(C，L，T)。

步骤8判断是否满足终止条件，如满足则迭代终止，输出解，否则返回步骤3。

图3 改进型粒子群算法流程框图Fig.3 Improved particle swarm optimization flowchart

3 实验仿真

通过选取湖州某重型机械公司的履带式起重机的主臂生产线为加工实例，运用提出的改进型粒子群算法模型，并基于Matlab2014a仿真平台来验证其有效性。其中电脑主频为2.30 GHz，内存为4.00 GB，CPU为i5-2410M。

表1 改进型粒子群算法、标准遗传算法和三段启发式算法计算结果

Table 1 Improved particle swarm optimization, standard genetic algorithm, three-section heuristic algorithm results

算法配送花费C/元 运送次数L/次 运送时长T/s改进型粒子群算法2719173标准遗传算法36616341三段启发式算法35614362

通过计算可以清楚地发现：相比于标准遗传算法与三段启发式算法，利用改进型粒子群算法能够在配送花费C、运送次数L和运送时长T等3 个方面得到显著改善。之后通过图4比对改进型粒子群算法、粒子群算法和标准遗传算法的收敛性，得出结论：改进型粒子群算法的收敛速度明显优于粒子群算法和遗传算法，且改进型粒子群算法相较于粒子群算法，它的收敛精度得到明显改善。

图4 改进型粒子群算法、粒子群算法和遗传算法收敛性比较Fig.4 Improved particle swarm optimization, particle swarm optimization and genetic algorithm convergence comparison

通过计算：当ωC=1时，所对应的C=258，L=14，T=194；当ωL=1时，C=314，L=8，T=166；当ωT=1时，C=283，L=11，T=151。可以发现：3 项数据中任何1 项达到最优时，另外2 项都不能达到最优。对应在实际生产中，企业根据订单状况，对解(C，L，T)要求不一样，因此可以相对应调整惯性权重的值来指导生产。

4 结 论

针对制造型企业在新形势下面向订单准时化生产问题，提出了一种改进型的粒子群算法，该算法采用遗传算法的编码方式和交叉变异策略，又通过模拟退火算法中的Meteropolis准则即重复对当前解进行迭代计算得到近似最优解。通过实验发现改进型的粒子群算法增加了算法收敛速度和精度，能较快得到全局最优解，同时通过改变适应函数的惯性权重可以按照实际生产要求安排生产，由此证明了该改进型粒子群算法的有效性。