基于遗传算法的多目标拆卸线平衡问题

李 勇，王 雅 君，王 耐 东，李 焜

(大连工业大学 机械工程与自动化学院,辽宁 大连 116034)

0 引 言

拆卸是产品回收的基本动作，提取有用部件，回收有害部件，做到循环经济和绿色制造。拆卸线平衡问题(disassembly line balancing problem，DLBP)成为近年的研究热点。Gungor等[1]分析了DLBP问题，指出与装配线平衡问题的区别；Avikal等[2]采用一种启发式算法求解DLBP问题，但仅适用于解决小规模问题；Altekin等[3]采用线性规划方法优化DLBP，但无法解决大规模问题；Kalayci等[4]采用遗传算法处理DLBP问题，但算法较早收敛于局部最优解。文献[5-6]以AND/OR图规划和整数规划，以最大化利润来优化拆卸线问题；Kalayci等[7]采用模拟退火算法，局部搜索能力强，但耗时长，获得全局最优解能力弱。实际的拆卸线问题需要兼顾多个目标，单一的优化往往不能更好地协调拆卸线。文献[8-9]在实际生产中解决多目标条件下的DLBP问题；丁力平等[10]提出了基于Pareto的蚁群算法，通过支配关系寻找最优前沿，以拆卸线空闲时间、平滑系数、成本等为优化目标，但未考虑零件其他影响平衡的指标。

针对上述研究的不足，本研究提出一种改进的遗传算法，在均衡空闲时间、平滑系数基础上，结合零件拆卸时环境、资源，提出新优化目标，通过具体实例，分析并验证该算法对求解此类问题的优越性。

1 数学模型

1.1 基本参数

假设每个待拆零件作为一个拆卸任务，零件数为n(也叫拆卸任务数)；T={1，2，3，…，n}为所有任务的集合；N为工作站数；CT为生产节拍，tk为第k个工作站上分配的所有拆卸任务作业时间之和。

1.2 决策变量

拆卸线平衡优化不仅要考虑作业任务的均衡分配，还包括环境、资源等，待拆产品可能包含有害物质，如重金属、化学毒物，在拆卸作业中应优先考虑。拆卸主要是回收和利用有剩余价值的零件，拆解中应尽快拆除价值大的零件。为使待拆产品的分解作业时间最小化，拆卸动作方位的变换次数也纳入优化空间，缩短拆卸作业时间。

考虑拆卸线平衡的5个目标，并对其优化。5个目标包括最少工作站数F1，平衡各个工作站空闲时间F2，见式(1)和(2)。

minF1=k

(1)

(2)

将两个目标归纳合并，以式(3)和(4)同时优化均衡闲置时间与最小化工作站数两项任务。

(3)

(4)

优先拆卸高需求部件指标F3，优先拆卸危害大的部件指标F4；最少改变方向进行拆除F5。

(5)

(6)

(7)

引入方向指标用来评价解序列，该数值越小，即拆卸过程中方向改变量越少，则该解越优。式(8)表示拆卸过程相对零件与工作站的各个方向。

(8)

将方向指标用决策变量的形式进行表述为

(9)

综上，多目标拆卸线平衡表示为

minF=(F3，F4，F5，F6)

(10)

s.t.

(11)

(12)

(13)

约束条件式(11)为设置工作站数应不低于理论工作站数、不多于拆卸任务数，式(12)为各工作站内拆卸时间不超过生产节拍，式(13)表示拆卸顺序必须满足拆卸优先关系。

2 算法模型求解

2.1 编 码

常用的编码方式有二进制0-1编码、实数编码、浮点数编码等[11-12]。针对拆卸线作业任务的现实情况，使用一种基于作业顺序先后的染色体编码规则，将n个拆卸元素排列于一排，相应对应一个基因位，并按作业顺序优先图将这些元素分配到各工作站中，站中工序的加权时间值不得高于预定的生产节拍，按工作站中工序的排序进行编码。利用插零[13]方法来表示当前工作站的作业元素开始(或结束)位置，染色体中n个作业、k+1个0、n+k+1长，相邻两个0间的作业元素为同一个工作站。

2.2 初始种群生成

初始种群的好坏对进化过程优劣性影响明显，影响算法运行效率。采用拓扑排序随机搜索生成初始种群，确保初始种群中个体的多样性与解的多样性。根据作业优先顺序流程，在作业任务全集内(种群)寻找无任务前驱的任务i，并放入新集T1中，在作业顺序图中随即删除任务i及与其相关的紧后顺序；重复上述操作，直至任务集合为空集结束分配任务，每步选好的任务放到对应的基因位，所得序列即为初始可行拆卸序列。

2.3 解 码

编码采用的是基于任务的一维数组解序列，无法由其确定个体优劣性，需要将解序列分配到各工作站[14]，操作过程为开启第一个工作站j=1；初始化当前站内时间和剩余时间；寻找解序列上的任务i，当所分配的任务时间超过当前剩余时间，则分配失败，随机开启新工作站，初始化当前站内时间和剩余时间；反之，将任务i分配到当前站中，并更新站内时间和剩余时间，并循环直至遍历解序列。对每个个体的编码及工作站间插零，能确保种群中各工作站与任务分配，提高算法的可视化[15]。

2.4 适应度

适应度函数在GA搜索进化中起评价个体优劣的作用。仅利用目标函数即可在解空间内完成系统优化，在遗传算法空间中，按一定规则将目标函数转换成个体适应度，并评价适应度值以实现解空间中可行解优劣的判断。

2.5 遗传算子

2.5.1 选 择

最常用的选择方法是轮盘赌法，采样思路为经选择的个体后代遗传的概率与适应度值成正比，适应度函数评价越高，进入下一代的概率也就越大，个体进入下一代的概率为它的适应度值与整个种群中个体适应度和的比例，假设种群中个体数为M，个体被选择的概率为

2.5.2 交 叉

交叉操作是形成新个体的重要方式，从选择完成的种群中任取的两个染色体，采用特定规则互换部分基因，重组后形成新个体[16]。

由于传统常规方法中的随机交叉方式往往会得到大量重复且冲突的现象，产生不可行解，影响算法的运行效率，故采用两点映射交叉法，于父代染色体随机确定两个交叉点，对父代两染色体于交叉点间部分基因排序并采用部分映射，保存交叉点两侧的基因并放到新个体中，从而产生两个新的后代个体。假设随机选取第3、5基因位为交叉点，父代中两个交叉点前的序列{6，3，7}、{2，4，9}得以保留，两交叉点间的序列{8，5，1}在父代2中的顺序为{1，5，8}，具体过程如图1所示。

图1 交叉示意图Fig.1 The diagram of crossover

2.5.3 变异操作

类似于交叉操作，作业受优先关系的约束，变异也会产生不可行解。采用单点基本位变异，在父代染色体随机产生一变异点(图2中的4位置)，并根据作业优先顺序，找出变异点的前后工序，保留前驱任务与以前的基因位置、紧后任务与以后的基因位置，随机将变异元素4插入染色体中前驱、紧后工序间的最近基因位，再整合以上基因的3部分生成新的子代染色体。若选取的变异位置没有可选的插入位置，则重新选取变异点。

图2 变异操作示意图Fig.2 The diagram of mutation

2.6 结束准则

GA作为一种反复迭代的搜索工具，通过多次进化循环而无限逼近最优值，而非恰好计算出最优解，因此须确定终止条件，确定遗传迭代的代数。在算法的初始时，迭代次数设置要尽量小，视情况增加迭代，当迭代次数超过要求的最大代数时，算法停止。

2.7 算法实现流程

初始种群的个体虽然是可行的，但较难保证个体最优在运算初期产生，为提高这种寻优解性能，于算法初期增大交叉、变异的概率。而在迭代后期，要想保障适应度高的优良基因，可降低交叉、变异概率。采用一种自适应交叉概率Pc如式(1)，变异概率Pm如式(2)。

(1)

式中：m为迭代次数，Pcmax为最大交叉概率，Pcmin为最小交叉概率。

(2)

式中：M为最大迭代次数，Pmmax为最大变异概率，Pmmin为最小变异概率。

算法实现的步骤：

步骤1参数的确定：选定种群规模NP及Pc、Pm的值；

步骤2初始化种群：令t=0，满足节拍约束和作业优先顺序的前提下产生初始种群P(0)，个体数为NP；

步骤3适应度评估：计算第t代种群中每个个体的适应度值；

步骤4选择操作：从第t代种群中选择NP个个体并把它们复制到t+1代中；

步骤5交叉操作；

步骤6变异操作；

步骤7最优保存策略；

步骤8循环：令t←t+1，满足停止条件即结束；反之，转向步骤3。

3 实例验证

3.1 DLBP实例计算

一个零件数为8的计算机部件的拆卸信息如表1所示，同时，零件拆卸任务优先关系如图3所示，利用改进的遗传算法求解。参考文献[17]用MATLAB R2012b在Windows7系统平台实现上述算法程序，对上述实例求解，工作站均为最小站数4，危害指标H均为7，需求D=211，方向指标R=7。表2为求得的最优解。表3为最优拆卸系列解及平衡后的工作站。其中，拆卸任务1、5被分配到工作站1，工作站2主要负责拆卸任务3、6、2，以此类推。且最优解较早地将高需求零件3、6、2和危害零件7进行了拆除，允许有7个方向的改变，算法运算时间不到1s，所得解的平衡和危害目标与文献[9]相同，需求指标则优于文献[11]，方向指标比文献[11]多一个。因而所得解的总体性能优于文献[11]。

表1 8个零件的拆卸信息Tab.1 Disassembly information for eight components

图3 零件拆卸任务优先关系Fig.3 Work priority relationship of components

表2 改进GA与标准GA优化结果对比Tab.2 The comparison of optimization results between improved GA and standard GA

4种单目标求得的最优解如表2所示，并参考文献[9]中的参数设计结合DLBP问题，针对解的质量和算法效率经反复测试，将参数设置为NP=100，M=100，Pcmin=0.5，Pcmax=0.95，Pmmin=0.005，Pmmax=0.01，经计算后取最优值，并分析运算时间，最优序列结果见表3。将改进GA与文献中的标准GA进行对比，从中得出测试结果在处理该问题上与标准算法相比较突出，能起到平衡的作用，且运行时间更短。

表3 DLBP最优拆卸系列解Tab.3 Optimal disassembly series solution of DLBP

3.2 发动机拆卸实例应用

以文献[18]中的汽车发动机拆卸实例为研究对象，对发动机进行完全拆卸。原企业中未考虑拆卸危害与需求，可变性差，不能及时地适应拆卸任务的变化，现利用改进的遗传算法对发动机缸体拆卸线进行改进，相关数据如表4所示。

表4 汽车发动机作业零件及要素Tab.4 Working parts and elements of automobile engine

将拆卸线的汽车发动机作业顺序矩阵录入，在MATLAB2012b上进行编程，节拍CT=120 s，算法参数为NP=50，MaxGen=150，GAP=0.9。对多个目标函数进行优化，并取得了预测的结果，跳出局部最优解取得更优解，搜索能力明显提高，优化结果如图4所示。线平衡结果如图5所示，直线型布局优化结果中工作站数为15，而U型线布局站数为9，所以U型布局能做到最小化工作站数，具有一定经济性。

图4 优化结果Fig.4 The result of optimization

4 结 语

采用一种改进的遗传算法求解多目标拆卸线平衡问题，在保证平衡的前提下，兼顾其他目标对平衡的影响，如危害、需求、拆卸方向等指标。采用实数编码策略与拓扑排序和动态确定交叉、变异操作改进求得最优解。算例表明DLBP-GA具有解决实际问题的可行性，能完成作业时间均衡，在此基础上对多目标优化问题具有很好的适应性，可及时适应拆卸任务的变化，为企业带来更多的决策方案。

(a) 直线型