0 引言

资源短缺与环境污染已成为可持续发展面临的两大难题.以家电、汽车为主的机电产品销量不断提高，产品更新换代步伐加快，由此产生大量废旧机电产品.对其回收和利用是解决上述两大问题的有效途径，而拆卸过程是废旧产品资源化的关键环节.面对大批量生产方式下的废旧机电产品，拆卸生产线是实现标准化、自动化、高效化拆卸作业的最佳方式，有着巨大的经济效益.但拆卸生产线与装配生产线类似，同样存在线平衡问题.

Gungor等^[1]首次正式提出拆卸线平衡问题(disassembly line balancing problem，DLBP)，以最小化总空闲时间、优先拆卸有危害、高需求的零件和最小化拆卸方向改变次数为优化目标，建立了完全拆卸条件下的多目标模型.此后，求解方法由启发式方法、精确方法扩展到智能算法.其中启发式方法包括2-opt算法^[2]、禁忌搜索算法^[3]、新启发式方法^[4]和模糊层次分析法^[5]等，结构简单，依据启发式规则生成可行解，但难以保证求解质量，加之DLBP是多目标优化问题，各子目标间存在博弈关系，难以制定协同优化多个目标的启发式规则. McGovern等^[6]用数学方法证明了DLBP是NP完全问题，随着问题规模的增大，可行解的数量呈几何级增长.精确方法包括拉格朗日松弛法^[7]、混合整数规划法^[8]等，针对单目标小规模DLBP能在有效时间内求得精确解，但不适用于求解大规模问题.

针对上述方法在求解多目标大规模DLBP时的不足，目前主要采用智能算法进行求解. McGovern和Gupta等提出一种通过禁忌表减少蚁群搜索空间，并结合问题特征改进信息素更新方法的蚁群算法^[9].人工蜂群算法^[10-11]、改进蚁群算法^[12]、混合遗传算法^[13]等对算法操作进行离散化处理，在求解大规模DLBP时表现良好.但上述方法在面对多目标问题时，均采用线性加权法或字典顺序法将其转化为单目标问题，而目标间存在相互冲突的情况，各子目标不能同时达到最优.这种处理方式存在主观性，求解结果单一，难以满足不同偏好决策者的需求.丁力平等^[14]针对DLBP的多目标属性，提出一种基于Pareto解集的多目标蚁群算法，通过评价各方案的支配关系，保留互不占优的多种方案.随后Pareto细菌觅食算法^[15]、Pareto人工鱼群算法^[16]相继被用于求解多目标大规模DLBP.上述三种多目标算法能够求得侧重点不同的多种拆卸方案，但在求解质量上仍有改善空间.

遗传算法在种群进化过程中缺乏问题特征信息的指导，具有随机性和盲目性，故引入免疫机制中的接种疫苗、免疫检测、免疫平衡和免疫选择等操作，引导个体向最优解靠拢，维持种群的多样性，有效避免算法的退化和早熟.该混合算法能很好地平衡深度搜索和广度搜索，全局寻优能力强，已成功应用于旅行商问题^[20]、装配序列规划^[21]等离散问题.

针对启发式方法、精确方法在求解多目标DLBP时受限于问题的NP完全属性，只适用于求解小规模问题，同时现有的智能算法存在搜索过于盲目、难以跳出局部最优等不足，综合考虑最小化工作站数目、空闲时间均衡、危害指标和需求指标等4个目标，提出了一种带问题特征的基于Pareto解集的多目标免疫机制协作遗传算法(Multi-objective Immune mechanism cooperative Genetic Algorithm，MIGA).

1 DLBP数学模型 1.1 问题描述

拆卸线平衡问题是典型的多目标组合优化问题，在完全拆卸要求下，综合考虑拆卸任务的分配、开启的工作站数目、空闲时间均衡、拆卸线的平衡率、需求指标和危害指标等因素，同时优化多个目标.假设某废旧产品包含n个零件，规定每个零件对应一项拆卸任务，现已知任务i的作业时间t_i、危害性h_i、需求量d_i、节拍时间T_c，在满足优先关系约束下完成拆卸线设计.为降低模型的复杂性，现作如下假设：

1) 拆卸单一产品的全部零件；

2) 废旧产品足够多，适合流水线作业方式；

3) 零件数量齐全，不存在缺失、改造等情况；

4) 零部件联接可靠，能够正常拆卸；

5) 标准化拆卸，作业时间已知；

6) 拆卸线采用直线型布局.

1.2 数学模型

多目标拆卸线平衡问题的数学模型^{[6, 16]}如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式中，M为工作站数目；x_im为0-1变量，若任务i分配到工作站m，则x_im=1，否则x_im=0；p_i为任务i分配到拆卸序列中的位置；F表示目标函数，工作站数目f₁、空闲时间均衡指标f₂、危害指标f₃和需求指标f₄；优先关系矩阵A=(a_ij)_n×n，若任务i是任务j的紧前工作，则a_ij=1，否则a_ij=0.式(6)为任务分配约束，表示任务能且仅能分配到一个工作站；式(7)为优先关系约束，表示任务的紧前工作优先分配；式(8)为节拍时间约束，表示工作站作业时间不超过节拍时间.

2 免疫机制协作遗传算法 2.1 多目标处理方法

多个目标间往往量纲不同、互相冲突，导致无法比较某些解的优劣，本文借鉴文[22]中采用Pareto占优思想处理多目标问题.假设可行域中任意两个解X₁、X₂的任意子目标f(X)满足

(9)

则称X₁支配X₂，X₂为受支配解，若X₁不被所有可行解支配，则称X₁为非劣解，Pareto最优解集指可行域中所有非劣解的集合，其对应目标值的集合称为Pareto最优前沿.

2.2 可行解构造规则

DLBP具有强约束性，拆卸方案必须满足优先关系约束.采用基于任务的编码方式，结合式(8)节拍时间约束的启发式规则，尽可能开启最少的工作站，以提高随机解的质量.可行解构造的步骤为：

步骤1  根据拆卸任务的优先关系矩阵A，搜索无紧前工作的拆卸任务，作为可选任务集V₁.

步骤2  计算工作站未分配的作业时间，选取V₁中作业时间小于未分配作业时间的任务，构成可分配任务集V₂.

步骤3  判断V₂=∅，若成立，开启新的工作站，执行步骤2；否则执行步骤4.

步骤4  随机在V₂中选择一个任务分配到拆卸序列.

步骤5  修改优先关系矩阵A，剔除已分配的拆卸任务，更新可选任务集V₁.

步骤6  判断V₁=∅，若成立，程序终止，输出可行解；否则执行步骤1.

2.3 带问题特征的疫苗库

加权值反映了拆卸任务的时间特征，将其作为疫苗库的提取规则，通过接种疫苗操作实现疫苗中局部优良特性的遗传.该疫苗库保留了问题的局部优良特性，是对所求问题最优解的一种估计，为个体趋近最优解提供了指导.加权值计算公式为

(10)

式中，w_i为任务i的加权值，E_i为任务i的前序任务集.

建立疫苗库的步骤如下：

步骤1  采用式(10)计算任务i的加权值w_i.

步骤2  判断w_i=w_j，∀i，j∈{1，2，…，n}，i≠j，若成立，作业时间长的任务必须优先分配，否则按加权值降序排列.

步骤3  确定任务i在疫苗库中的位置，排序在该位置前对应的任务即为疫苗.

2.4 遗传操作

交叉操作采用两点交叉方式，从父代X₁、X₂继承局部信息，不改变父代任务间的相对位置，以此保证交叉操作产生的子代X_new1、X_new2均为可行解.

变异操作对交叉子代X进行局部搜索，避免子代过分依赖初始种群，更好地跳出局部最优.变异位置在所有紧前任务位置与所有紧后任务位置之间，从而保证变异操作后产生的子代X_new为可行解.具体步骤如下：

步骤1  选择个体X的一个基因位，产生随机概率P.

步骤2  判断P < P_m，若成立，将变异元素随机插入可行变异位置，执行步骤3；否则，执行步骤1.

步骤3  保持其余任务的相对位置不变，得到变异个体X_new.

2.5 免疫机制

1) 接种疫苗操作.随机选择抗体X的一个基因位，将该基因位的疫苗与抗体X中的后续基因进行对比，构成候选疫苗库.随机将候选疫苗库任务插入到拆卸序列其紧前工作的后一位置，得到新个体X_c.接种疫苗操作如图 1所示.

2) 免疫检测操作.免疫检测操作的目的是判断接种疫苗操作是否有效.若子代X_c支配父代X，则表明接种疫苗操作有效，保留子代X_c；若X支配X_c或两者互不占优，则表明此次接种疫苗操作无效，若接种疫苗次数在最大尝试次数L=⌈n/2⌉范围内，则执行接种疫苗操作；否则，保留父代X.

3) 免疫平衡操作.为避免算法过早陷入局部最优，引入抗体浓度，并结合抗体的适应值，为种群更新提供了一种新方式.该方式不仅要求抗体具有较高的适应值，同时能根据抗体浓度进行自我调节，使得种群兼具高适应值和浓度均衡.

(11)

(12)

(13)

(14)

式中，J_ij为抗体i、j的相似度，R为相似度半径，C_i为第i个抗体的浓度，N为种群规模，K为抗体浓度超过种群浓度极值平均数的抗体数目，P_d¹为高浓度抗体的浓度概率，P_d²为低浓度抗体的浓度概率.

4) 免疫选择操作.免疫选择操作根据个体的选择概率P_s，采用轮盘赌方式构造新种群. P_s与适应度概率P_f、浓度概率P_d相关，计算公式见式(15)，其中α为免疫选择系数.高浓度抗体数目多，则浓度概率降低，选择概率随之减小，起到抑制作用，保证种群的多样性；高浓度抗体数目少，则浓度概率增大，选择概率随之增大，起到促进作用.体现了免疫机制的自我调节能力，保证种群在收敛性和多样性方面的平衡.

(15)

2.6 算法流程

免疫机制协作遗传算法求解多目标DLBP的步骤为：

步骤1  输入问题参数：优先关系矩阵A、节拍时间T_c、作业时间t、任务数目n、零件危害性h和需求量d.

步骤2  设定算法参数：种群规模N、最大迭代次数M_gen、最大尝试次数L、交叉概率P_c、变异概率P_m、抗体相似度半径R，外部档案Q=∅.

步骤3  采用节拍时间约束下的启发式规则初始化种群，建立疫苗库，令迭代次数gen=1.

步骤4  执行交叉、变异操作.

步骤5  接种疫苗次数l=1.

步骤6  执行接种疫苗操作.

步骤7  执行免疫检测操作，若子代Pareto占优，则保留子代，否则判断尝试次数是否满足要求l < L：若满足令l=l+1，转至步骤6，否则保留父代，转至步骤8.

步骤8  按照2.1节Pareto解集定义筛选非劣解，更新Q.

步骤9  执行免疫平衡操作、免疫选择操作，更新初始种群.

步骤10  判断迭代次数gen < M_gen，若成立，令gen=gen+1，转至步骤4；否则，终止算法，输出Q.

3 算法验证

MIGA采用Matlab R2010b编程实现，在Intel Pentium 2.90 GHz双核，2.00 GB内存环境下运行，设置算法通用参数：最大尝试次数L=⌈n/2⌉，相似度半径R=0.1，免疫选择系数α=0.7.为验证启发式规则构造的初始解具有较高的质量，设计了种群初始化规则对比实验，分析两种规则下初始种群的支配关系以及对算法结果的影响.通过求解不同规模的多目标拆卸线平衡问题，并与多种现有算法对比，验证所提MIGA的可行性和有效性.

3.1 种群初始化规则对比

初始种群对算法的收敛性能有一定的影响，一般使用随机规则生成初始种群，但随机解的质量较差，收敛速度慢.本文使用结合式(8)节拍时间约束的启发式规则提高初始解的质量.以文[14]提出的52项任务拆卸实例为测试对象，在两种初始化规则下分别生成种群规模为40的20个初始种群，计算种群非劣解的个数以验证初始种群的质量如图 2(a)所示.以第3次求得的初始种群为例，算法迭代100次，计算拆卸成本F_Cost的最小值，验证初始种群解的质量对算法结果的影响，如图 2(b)所示.

由图 2(a)可知，在两种规则下生成的20个初始种群中，有16组试验启发式规则生成的非劣解个数多于随机规则生成的非劣解个数，启发式规则下的非劣解个数不少于随机规则下的非劣解个数占比为95%，结果表明了启发式规则构造的解的质量优于随机解. 图 2(b)表明启发规则下的初始解的质量较高，收敛速度快.

3.2 小规模问题

文[9]研究了10项任务的拆卸实例(P10问题)，已知拆卸任务的作业时间、零件的危害性和需求量，以拆卸工作站数目f₁、空闲时间均衡指标f₂、危害指标f₃和需求指标f₄为优化目标.现有求解P10问题的算法有：Greed/2-Opt^[2]、禁忌算法(Tabu search，TS)^[3]、新启发式算法(new heuristic，NH)^[4]、模糊层次分析法(fuzzy analytic hierarchy process，FAHP)^[5]、蚁群算法(ant colony optimization，ACO)^[9]、人工蜂群算法(artificial bee colony algorithm，ABC)^[10]、改进人工蜂群算法(improve artificial bee colony algorithm，IABC)^[11]和改进蚁群算法(improve ant colony optimization，IACO)^[12]，上述8种单目标算法均只求得一个解见表 1.为兼顾求解质量和求解时间，设置算法参数：种群规模N=80、迭代次数M_gen=40、交叉概率P_c=0.9、变异概率P_m=0.3，考虑到随机性的影响，重复运行10次均求得7个非劣解见表 2，平均计算时间为3.131 0 s.所提MIGA计算耗时均长于8种对比算法，主要原因是对比算法均为单目标算法，而MIGA求得的Pareto最优解集包含多个互不占优的非劣解，最优解与种群进行信息交互的执行次数多，因而计算耗时较长.

根据Pareto解集的定义，对比8种单目标算法所求结果的优劣，由表 1可知：Greed/2-Opt、NH的危害指标f₃=3最小，但Greed/2-Opt在其它3个目标上较优，因此方案1为非劣解；FAHP的需求指标f₄=7 150最小，方案4为非劣解；ACO、IABC、IACO的空闲时间均衡指标f₂=211最小，但ACO的需求指标要差于IABC和IACO，方案7、8为非劣解，虽然两者的目标值相同，但任务分配情况不同.综上所述，Greed/2-Opt、FAHP、IABC和IACO都得到了非劣解，提供了4种任务分配方案，上述8种单目标算法在求解多目标问题时，考虑各目标的优先权重，将多目标问题转化为单目标问题，难以平衡多个优化目标.

MIGA同时优化4个目标，得到包含7个非劣解的Pareto最优解集.对比表 1与表 2：MIGA方案1与Greed/2-Opt方案相同，危害指标最小为3，并支配TS、NH、ACO、ABC方案；方案2、4、6均能支配TS、ABC方案；方案3与IABC、IACO方案相同，并支配ACO方案；方案5与各算法方案均互不占优；方案7在f₁、f₃、f₄与FAHP方案相同，需求指标最小为7 150，但在空闲时间均衡指标f₂上占优，故方案7支配FAHP方案.在求解多目标问题时，难以得到各子目标均最优的结果，当某一子目标最优时，其它子目标可能最差，各目标间相互冲突，难以比较优劣.由表 1与表 2的分析可知：MIGA求解P10问题得到7个非劣解，而其它8种算法只求得单一解，在决策者偏好未知情况下，MIGA能提供多样性的方案；在求解效果方面，MIGA能够求得上述8种算法的方案，甚至更优的方案，不存在比其它算法差的方案.因此验证了所提MIGA求解多目标DLBP的有效性.

3.3 大规模问题

文[14]以52项任务的高速电子套结机机壳拆卸线为研究对象(P52问题)，以此分析所提MIGA在大规模实例的求解性能，已知拆卸线的节拍时间T_c=600 s.出于可比性的考虑，引入该文献的闲置率F_Idle、平滑率F′_Smooth及拆卸成本F_Cost等3个目标，如式(16)~式(18)所示.

文[14]中式(17)平滑率公式在工作站作业时间等于节拍时间的情形下失效，但平滑率为最优值0时，各工作站作业时间均等于节拍时间，因此需要修正平滑率公式，如式(19)、式(20)所示.为统一最小化优化方向，令不平滑率F_NSmooth=1-F_Smooth，以式(16)、式(18)~式(20)构建优化目标.式(18)中U_i表示任务i的单位时间拆卸成本.文[14-16]分别采用多目标蚁群算法(ant colony optimization，ACO)、细菌觅食算法(bacteria foraging optimization，BFO)、人工鱼群算法(artificial fish swarm algorithm，AFSA)求解P52问题.为兼顾求解质量和求解时间，算法参数设置为N=140、M_gen=100、P_c=0.5、P_m=0.3，重复运行10次，所提MIGA求解P52问题的结果见表 3，共求得9个非劣解，平均计算耗时为79.139 s.

(16)

(17)

(18)

(19)

(20)

分析表 3可知：所提MIGA求得9个拆卸方案，闲置率F_Idle=0.057 9，工作站数目均为7个，平滑率F_Smooth的取值范围在0.877 1~0.999 2，拆卸成本F_Cost的取值范围在126.624元~140.094元. 图 3为4种算法求解P52问题的Pareto最优前沿，其中方框表示MIGA的Pareto最优前沿.鉴于ACO中4个解的F_Idle=0.175 7，开启8个工作站，其余拆卸方案均为F_Idle=0.057 9，为直观地对比4种算法的结果，只考虑在F_Cost、F_NSmooth上对比，如图 4(a)所示. ACO结果的闲置率有两个取值，故Pareto最优前沿为两条线段；BFO和AFSA均求得8个非劣解；MIGA求得9个非劣解，将ACO、BFO和AFSA的Pareto最优前沿向前推进.结合表 3、图 3与图 4(a)可知，随着工作站负荷越来越均衡，拆卸成本随之增加，F_Smooth与F_Idle存在博弈关系，难以同时达到最优.

4种算法在闲置率、平滑率和拆卸成本上的最大值和最小值对比，如图 4(b)~图 4(c)所示.在F_Idle指标上，BFO、AFSA和MIGA均为0.057 9，开启7个工作站；在F_Smooth指标上，ACO、BFO、AFSA和MIGA的最大F_Smooth值逐步提升，表明所提MIGA优化了F_Smooth指标，AFSA的F_Smooth指标极差最小，MIGA的F_Smooth指标极差最大，表明了MIGA能求得多样性的解；在F_Cost指标上，MIGA的最小F_Cost=126.624元，表明MIGA优化了F_Cost指标.综上所述，当求解大规模DLBP时，本文算法与现有ACO、BFO、AFSA进行对比，结果表明所提MIGA在F_Smooth、F_Cost指标上均有显著提升，运行一次能得到侧重点不同的多样性解，验证了所提MIGA求解大规模DLBP的有效性和优越性.

本文算法求得更优的Pareto最优前沿，解的分布较为均匀，为决策者提供多样的方案：若决策者要求拆卸成本最小，则方案1最佳；若只要求平滑率最大，则方案9最佳；若要求平滑率不低于99%，同时拆卸成本最小，则选择方案5.

3.4 基准算例

文[9]与文[12]通过测试19个基准算例以验证ACO、IACO的搜索能力，算例的构造规则以及具体数据见文[9].基准算例的Pareto最优解集包含两个非劣解(n/4，0，1，2)、(n/4，0，2，1)，各目标的均值分别为n/4、0、1.5、1.5.参考IACO求解该基准算例的算法参数，MIGA的参数设置为{80，40，0.9，0.3}，三种算法求解基准算例的性能对比如图 5所示.

分析图 5可知，所提MIGA求得4个算例的最优值，ACO的搜索能力最差，IACO只求出3个算例的最优值；对比单目标均值，f₁指标上，MIGA求得4个最优值，而ACO的结果均比最优值大1，IACO求得3个最优值；f₂指标上，MIGA求解第5个算例的f₂均值最差，但优于两种对比算法，最大优化了62.64%；f₃、f₄指标上，ACO的f₃、f₄均值波动较大，表明算法搜索能力较差，而IACO求解某些算例时的f₃均值为1，表明该算法仅能求得一个解，所提MIGA在f₃、f₄指标上的寻优率高达94.74%、89.47%；图 5(e)表明所提MIGA在求解小规模问题时，三种算法的求解时间相差不大，但对于大规模问题，MIGA的计算耗时介于ACO和IACO之间.综上所述，所提MIGA在求解DLBP时耗时长于对比算法，但运行一次能求得多样性、高质量的拆卸方案.

4 结论

拆卸线平衡问题是典型的多目标组合优化问题，针对以往研究中将多目标问题处理为单目标问题，求解结果单一、性能不佳等不足，提出了一种基于Pareto解集的多目标免疫机制协作遗传算法.考虑到遗传算法中个体进化的随机性和盲目性、群体进化容易陷入局部最优等不足，将带问题特征信息的加权值作为疫苗库的构造规则，引入免疫机制，采用加权值作为疫苗提取的规则，通过接种疫苗、免疫检测、免疫平衡和免疫选择等操作，引导个体向最优解靠拢，并维持种群的多样性.为提高初始种群解的质量，设计了节拍时间约束下的启发式种群初始化规则，通过与随机种群的解进行对比，验证了该启发式规则的有效性.通过求解P10问题、P52问题以及19个基准算例的多目标DLBP，对比多种已有算法，结果表明了所提MIGA能求得侧重点不同的高质量、多样性的拆卸方案，验证了算法的有效性和优越性. DLBP涉及多种不确定性因素，基于确定条件设计的产品拆卸线在扰动环境下运行时，工作站的平衡状态可能被打破，如何将不确定性因素考虑到拆卸线平衡模型中以提高拆卸方案的柔性，仍有待进一步研究.