多目标拆卸线平衡问题的Pareto人工鱼群算法
2017-02-10汪开普张则强毛丽丽李六柯
汪开普 张则强 毛丽丽 李六柯
西南交通大学机械工程学院，成都，610031
多目标拆卸线平衡问题的Pareto人工鱼群算法
汪开普 张则强 毛丽丽 李六柯
西南交通大学机械工程学院，成都，610031
针对拆卸线平衡问题的复杂性，提出了一种改进的基于Pareto解集的多目标人工鱼群算法进行求解。为提高人工鱼觅食时的寻优能力，引入遗传算法的随机交叉操作，指导人工鱼向全局最优拆卸方向觅食。通过拥挤距离不断筛选人工鱼觅食、聚群和追尾过程中的非劣解，实现了各行为结果的多样性。采用精英保留策略，将外部档案中的非劣解添加到算法下次迭代的种群中，加快了算法的收敛。通过对不同规模的拆卸实例进行求解，并将其与已有算法进行对比，验证了所提算法的有效性和优越性。
拆卸线平衡问题；多目标优化；Pareto解集；人工鱼群算法
0 引言
随着经济的高速增长、物质财富的极大丰富化，资源与环境问题日趋严峻。实现废旧机电产品的拆卸处理能够提高资源利用率，减少环境污染，因此废旧产品的拆卸回收再利用日益得到重视。拆卸线具有生产效率高、成本低等优点，是规模化拆卸产品的最有效途径之一。然而实际拆卸线各工作站间普遍存在着作业不均衡现象，影响着生产效率的提升。
针对拆卸线所面临的问题，国内外开展了广泛探索和研究。GUNGOR等[1]首先提出拆卸线平衡问题 (disassembly line balancing problem，DLBP)。启发式方法[2]和数学规划法[3]在求解小规模DLBP上能够得到最优解，但难以求解大规模问题。由于DLBP是NP完全问题[4]，随着任务规模数的增大，难以在有效时间内求得最优解。McGOVERN等[5]提出了一种蚁群算法来求解以平衡率和工作站数为优化目标的DLBP，并与现有的几种启发式算法的求解性能进行对比，结果表明群智能算法较启发式算法更具优越性[6]。KALAYCI等用遗传算法[7]、模拟退火算法[8]、粒子群算法[9]、人工蜂群算法[10]、变邻域搜索算法[11]、禁忌搜索算法[12]求解不同规模任务的DLBP，都能够快速得到较优解。
上述文献采用群智能算法求解多目标DLBP时均是将其转化为单目标问题进行求解，只能求得一个解，但DLBP各优化目标间存在着相互博弈的关系，导致求得的平衡方案无法实现各优化目标间的均衡，并且使求解结果丧失了多样性。朱兴涛等[13]提出一种改进蚁群算法求解多目标DLBP，按顺序处理各目标，其本质还是将多目标问题转化为单目标问题求解。丁力平等[14]利用基于Pareto解集的蚁群算法对多目标DLBP进行优化，能够得到多种优化方案，实现了各目标间的均衡，但各平衡方案的性能指标还有进一步提升的空间。
人工鱼群算法(artificial fish swarm algorithm，AFSA)具有收敛速度高、全局搜索能力强、鲁棒性强等优点[15]，在求解组合优化问题[16-17]时表现出优良的求解性能。参考已有文献，尚未发现有将人工鱼群算法用于求解DLBP的公开报道。
鉴于现有研究的不足，本文结合Pareto解集求解多目标问题思想以及人工鱼群算法求解组合优化问题的优势，提出一种求解DLBP的Pareto人工鱼群算法。通过对不同规模任务的问题进行测试对比，验证了所提算法求解多目标DLBP的求解性能。
1 多目标拆卸线平衡问题
1.1 问题描述
拆卸线是实现大规模拆卸作业的最佳选择，面对日益增多的待拆卸废旧机电产品，拆卸线越来越多地被采用，图1为一个拆卸线示意图。在废旧产品完全拆卸的情况下，需综合考虑拆卸线工作任务分配、拆卸线开启工作站数、拆卸线节拍时间安排、拆卸危害度等多种因素。针对多目标拆卸线平衡问题，寻求满足拆卸任务间优先关系的可行拆卸序列，且该序列需满足多个拆卸目标的优化，包括最小化工作站数目、平衡各个工作站间的负荷、尽早拆卸有危害以及需求高的零件。
图1 拆卸线示意图Fig.1 Diagram of dissembly line
1.2 数学模型
针对拆卸线平衡问题的特点，建立如下多目标模型[4]：
min f1=M
(1)
(2)
(3)
(4)
(5)
Tm≤TC∀m∈{1,2,…,M}
(6)
(7)
(8)
目标函数中，式(1)表示最小化拆卸线开启的工作站数。当拆卸线节拍固定时，开启的工作站越多，所需的作业工人和拆卸设备也越多，将导致拆卸成本增大。式(2)表示均衡每个工作站的空闲时间。每个拆卸工作站的空闲时间与拆卸线的效率正相关，工作站间工位时间的均衡有利于提高拆卸线的作业效率。式(3)表示尽可能早地拆卸需求高的零部件。需求指标越高的零件，带来的经济效益越大，故在同等条件下优先考虑拆卸。式(4)表示尽可能早地拆卸有危害的零部件。考虑到产品拆卸任务的特殊性，一些携带有毒或有害化学物质的零部件需尽早作业。
2 Pareto人工鱼群算法
人工鱼群算法在求解组合优化问题中表现出良好的性能，该算法具有较强的搜索能力，已在旅行商问题[15]、冗余分配问题[16]、多维0-1背包问题[17]等诸多组合优化问题中得到了成功应用。本文针对拆卸线平衡问题的特点，借鉴文献[18]中的多目标处理方式，结合人工鱼群算法的优势，提出一种求解多目标拆卸线平衡问题的Pareto人工鱼群算法。
2.1 可行解的构造
根据拆卸任务间的优先关系图构造优先关系矩阵Y，为保证初始解的多样性，每次挑选任务均为随机挑选。此过程无需考虑工作站节拍的影响，解码时才需考虑节拍对目标函数的影响。生成初始可行解的具体步骤如下：
Step1 从拆卸优先关系矩阵Y中随机挑选未分配的任务i，且任务i无紧前任务或紧前任务已分配(即Y中每列全部为零的任务)，将其作为当前位置n处的拆卸任务；
Step2 将与任务i有优先关系的约束从Y中删除：∀a∈{1,2,…,N}，令yia=0，yai=0；
Step3 寻找下一位置处的任务，令n←n+1；
Step4 重复Step1～Step3，直至所有任务分配完成，得到的序列即为初始可行拆卸序列。
2.2 Pareto解集的更新
现有求解多目标拆卸线平衡问题的文献一般采用线性加权法和顺序处理法[4-13]，其本质是将多目标问题转化为单目标问题进行求解，不能很好地平衡存在冲突关系的多个目标函数。Pareto解集思想能很好地兼顾多个优化目标间的均衡，求解结果更符合问题实际情况，可以作为该问题的求解思想。
满足拆卸优先关系的拆卸序列称为多目标拆卸线的可行解，所有可行解组成的集合称为可行解集。给定两个可行拆卸序列X1、X2，若X1、X2满足
(9)
式中，D为目标函数个数；fd为第d个目标函数值。
则称X1Pareto占优于X2，或X1支配X2，记为X1X2。
若可行解X*满足：不存在拆卸序列X使得XX*，则称序列X*为Pareto最优解或非劣解。所有Pareto最优解的集合构成Pareto最优解集，对应拆卸序列的多目标函数值组成的集合称为Pareto最优前沿。
利用外部档案Q记录已找到的Pareto最优拆卸序列的目标函数值，算法每迭代一次就将种群P中的每一个新解pi与外部档案Q中每一个非劣解qj进行比较：若piqj，则将pi置于Q中，同时将qj从Q中删除；若qjpi，则Q保持不变；若pi和qj互不支配，则将pi、qj都置于Q中，实现外部档案Q的更新，得到最优非劣解。
2.3 个体评价
在算法的每一次迭代过程中，将更新后的外部档案中的Pareto最优解作为下一次迭代的种群。为避免外部档案Q的容量过大对种群产生不利影响，需要对外部档案中的非劣解进行评价筛选。引入NSGA-Ⅱ拥挤距离机制[18]评价每个非劣解，将每个目标函数fd按升序排列，其中d∈{1,2,…,D}，定义目标函数fd的两个边界个体的拥挤距离L1=Lk→∞，其他非劣解个体的拥挤距离为
(10)
g∈{2,3,…,k-1}
式中，k为非劣解的个数；fd,k、fd,1分别为第d个目标函数值的最大值和最小值。
2.4 觅食行为
觅食行为中人工鱼是通过视觉或嗅觉感知水中食物浓度来选择趋向的，设人工鱼当前状态为Xcurrent，人工鱼感知视野范围为V，在V内经过ntry次尝试后若找到食物浓度较高的位置，则向该位置移动一步。离散问题中，不设置人工鱼的步长，人工鱼直接从食物浓度低的位置跳到浓度较高的位置。基本人工鱼群算法中当前状态人工鱼Xcurrent执行随机搜索，搜索方向是不确定的，无法指导人工鱼向最优方向收敛，鉴于此引入遗传算法的交叉算子，指导人工鱼觅食，对Xcurrent进行随机顺序交叉操作，如图2所示。
图2 交叉操作示意图Fig.2 Diagram of cross operation
在Xcurrent中随机选取2个交叉点，则交叉点1之前的序列和交叉点2之后的序列必然满足拆卸优先关系，保持不变；交叉点1和交叉点2之间的序列通过随机生成的参考人工鱼Xreference映射得到，组成新的人工鱼Xnew。交叉部分在Xreference中满足拆卸优先关系，则生成的Xnew也必然满足拆卸优先关系。通过随机选择Xcurrent中交叉点并与随机生成的参考人工鱼Xreference交叉映射得到新的人工鱼Xnew，增强了觅食鱼群跳出局部最优的能力。
将Xcurrent置于觅食行为外部档案Qprey中，作为非劣解。人工鱼每执行一次交叉操作，即完成一次觅食尝试。将每一次交叉后的解与Qprey中的每一个非劣解进行比较，不断筛选非劣解，实现Qprey的更新，直至完成ntry次尝试，Qprey中非劣解为Xcurrent觅食后得到的可移动状态。若执行ntry次尝试后，Qprey中非劣解保持Xcurrent不变，则表明觅食失败，执行随机行为，即随机选择一种可行解。觅食行为过程如图3所示。
图3 觅食行为过程Fig.3 Flow of prey
2.5 聚群行为
聚群行为是Xcurrent探索视野范围V内伙伴数目Ns及中心位置Xcenter是否满足移动条件。设有两条人工鱼X1=(a1，a2，…，an)和X2=(b1，b2，…，bn)，在常见的连续性问题中，两条人工鱼的距离采用欧几里得法表示为
(11)
离散问题并不适用于该方法。离散问题中两条人工鱼之间的距离可表示为
(12)
(13)
式中，argmaxfreq(A)表示集合A中出现次数最多的元素。
Xcenter由视野范围内伙伴矩阵中每列出现次数最多的元素组成，且Xcenter的序列必须满足拆卸任务优先关系。
若Xcurrent在视野范围V内看不到伙伴或Ns/ Nfish>δ，其中，Nfish为种群数目，δ为拥挤度，则表明聚群失败，执行觅食行为。当Ns/Nfish≤δ时，则需将Xcenter与Xcurrent进行比较：若XcenterXcurrent，则用Xcenter替换Xcurrent，表明聚群成功；若XcurrentXcenter，表明聚群失败，则执行觅食行为；若Xcenter、Xcurrent互不支配，则将Xcenter、Xcurrent都保留下来，聚群成功。聚群行为过程如图4所示。
图4 聚群行为过程Fig.4 Flow of swarm
2.6 追尾行为
追尾行为是Xcurrent探索视野范围V内伙伴数目Nf及每个伙伴的食物浓度是否满足移动条件。Nf=0表示Xcurrent探索视野范围V内无伙伴，表明追尾失败，执行觅食行为。将Xcurrent置于追尾行为外部档案Qfollow中，将其与Qfollow中其他非劣解进行比较，实现Qfollow中非劣解的筛选与更新。若Qfollow中只有Xcurrent，则表明追尾失败，执行觅食行为；若Qfollow中除Xcurrent外还有Nq个非劣解且Nq/Nfish≤ δ，则追尾成功，否则执行觅食行为。追尾行为过程如图5所示。
图5 追尾行为过程Fig.5 Flow of follow
2.7 更新种群
基本人工鱼群算法中的种群是随机生成的，且在迭代过程中保持不变，算法结果的优劣依赖于初始解。为获得较好最终解，可对种群进行更新。
针对多目标问题，采用Pareto占优筛选外部档案中的非劣解，可以考虑将外部档案Q中的非劣解作为下次迭代的种群。该操作保留了每次迭代的较优解，并在此基础上寻找更优的解，有利于算法快速收敛。为保证种群数目不变，需要对外部档案中的非劣解进行筛选。
设定种群数目Nfish，当外部档案中非劣解数目NQ
2.8 算法步骤
Step1 设定算法参数，包括种群规模Nfish、觅食行为最大尝试次数ntry、拥挤度δ、视野V、最大迭代次数gmax、节拍TC等；
Step2 根据优先关系矩阵Y生成初始种群，设外部档案Q=∅；
Step3 计算目标函数值f1、f2、f3、f4，按照2.2节内容筛选种群非劣解，更新外部档案；
Step4 开始迭代，分别按照2.5节、2.6节内容执行聚群行为和追尾行为；
Step5 将Step4的结果与种群非劣解进行比较筛选，更新种群外部档案；
Step6 将Step5外部档案中的非劣解作为种群，按照2.7节内容更新种群；
Step7 判断是否达到最大迭代次数gmax，若达到，则转下一步；否则转Step4；
Step8 输出外部档案中的非劣解，得到最优拆卸序列。
多目标Pareto人工鱼群算法流程如图6所示。
图6 Pareto人工鱼群算法流程图Fig.6 Flow of Pareto AFSA
3 算法验证与实例应用
为验证所提算法的有效性，针对不同规模的拆卸线平衡问题，应用所提算法进行测试。算法实验采用的计算机硬件配置为Intel Core i3-2100 M，3.10 GHz，2 GB内存，在Windows7系统下使用MATLAB R2010b软件开发了算法的实验程序。
3.1 算法验证
文献[7-11]分别采用遗传算法(genetic algorithm，GA)、模拟退火 (simulated annealing，SA) 算法、粒子群优化 (particle swarm optimization，PSO) 算法、人工蜂群 (artificial bee colony，ABC) 算法、变邻域搜索 (variable neighborhood search，VNS) 算法求解了包含25项任务的SCH-3500移动电话拆卸案例，该案例的零件拆卸优先关系、拆卸时间参数、危害参数、需求参数等详见文献[9]，现将5种单目标算法求解到的最优方案结果列于表1。
表1 文献[7-11]求解P25的解Tab.1 Solution of P25 in reference [7-11]
测试时兼顾求解质量与求解效率，并结合实际拆卸情况，将Pareto AFSA的参数设置为：Nfish=25，ntry=16，δ=0.8，V=20，gmax=20，TC=18。实验运行20次，计算平均运行时间为34.05 s，取其中一次求解结果的平衡方案列于表2，共求得8个非劣解。
表2 Pareto AFSA求解P25的非劣解Tab.2 Noninferior solution of P25 of Pareto AFSA
分析表1可知：按Pareto支配关系的定义，VNS结果方案支配GA、SA、PSO、ABC4种算法结果方案；SA、PSO、ABC结果方案相同，3种算法方案支配GA结果方案。对比表1、表2可知：Pareto AFSA方案1与VNS方案相同，其他7种方案与VNS方案互不占优。Pareto AFSA方案1、方案2支配GA、SA、PSO与ABC的方案，方案3～方案8与GA、SA、PSO与ABC的方案互不占优，方案5～方案8在f1、f2上差于GA、SA、PSO与ABC的方案，但在f3、f4上明显优于4种算法方案。
通过对比可知，所提Pareto AFSA不仅能够求得比GA、SA、PSO、ABC更优的方案，还能求得与4种算法互不占优的方案，表明Pareto AFSA较GA、SA、PSO、ABC有明显优势。Pareto AFSA结果方案个数明显多于VNS求得的单一方案，验证了Pareto AFSA求解多目标拆卸线平衡问题的结果具有多样性。
文献[7-11]中，GA、SA、PSO、ABC、VNS等5种算法均只求得一个单解，这些算法均是将多目标拆卸线平衡问题转化为单目标问题进行求解，求解过程中只侧重于某几个目标而忽略其他目标。多目标拆卸线优化问题中，各目标之间存在相互冲突的关系，其结果是解的某几个目标较好(如f1、f2)而其他目标较差(如f3、f4)，并且使求解结果丧失了多样性。Pareto AFSA能很好地兼顾多目标间的均衡性，求得8种可选平衡方案，每种方案结果各有侧重，实现了求解结果的多样性。
综上所述，Pareto AFSA能有效求解多目标拆卸线平衡问题，且在求解性能上优于文献[7-11]的单目标算法GA、SA、PSO、ABC、VNS。
3.2 实例应用
以文献[14]中的高速电子套结机拆卸线实例为研究对象，阐述所提算法在实例应用中的性能。实例对机壳的52个零件进行完全拆卸，机壳零件爆炸图、零件的拆卸任务优先关系图、拆卸时间和拆卸成本等数据详见文献[14]，此处不再给出。文献方案的优化目标为最小化平均闲置率Fidle、最大化负荷均衡指标Fsmooth、最小化拆卸成本Fcost。为方便对比，引入该文献的这3个目标函数：
(14)
(15)
(16)
minF=min(Fidle,1-Fsmooth,Fcost)
(17)
式中，Un为拆卸任务n的单位时间拆卸成本。
根据52项拆卸任务的实际拆卸情况，综合考虑算法的求解性能与求解时间，将Pareto AFSA的参数设置为：Nfish=30，ntry=10，δ=0.8，V=40，gmax=20，TC=600。采用所提Pareto AFSA对实例进行求解，共求得8个非劣解的Pareto解集，Pareto前沿空间分布如图7所示。将求得的Pareto前沿与文献[14]的Pareto ACO结果在3个目标上进行对比，如图8、图9所示。
图7 AFSA求解P52的Pareto前沿Fig.7 Pareto front edge of P52 of AFSA
图8 AFSA与ACO在Fidle上对比Fig.8 Comparison of Fidle on AFSA and ACO
图9 AFSA与ACO在Fcost、Fsmooth上对比Fig.9 Comparison of Fcost and Fsmooth on AFSA and ACO
由图8可知：在Fidle指标上，所提AFSA的8种方案均求得最优解0.0597，ACO有6种方案求得最优解0.0597，其他4种方案为0.1757。由图9可知：在Fsmooth指标上，AFSA求解结果中除了方案6劣于ACO的方案10外，其他方案均优于ACO的方案；在Fcost指标上，AFSA的8种方案都优于ACO的10种方案。综合对比3个目标可知：所提AFSA的方案6与ACO的方案10互不支配，方案6支配ACO的其他9种方案；AFSA的其他7种方案中，每一种方案都支配ACO的10种方案。由此可知，在求解质量上所提Pareto AFSA较文献[14]的Pareto ACO有明显优势。
分析表3可知，本文算法求得的8种方案闲置率都相同，因此在方案选择上只需考虑负荷均衡指标和拆卸成本指标。由图7可知：若要求负荷均衡率最高，可选方案2；若要求拆卸成本最低，可选方案6；若既要负荷均衡率高，又要拆卸成本低，可选方案1或方案4。8种方案的负荷均衡率均在96.9%～99.8%之间，各种方案的负荷率已经非常均衡，拆卸成本在129～151之间，拆卸成本也得到进一步降低，实现了平衡方案性能指标的大幅提升，为决策者提供了多种可选方案。
表3 Pareto AFSA求解P52的非劣解Tab.2 Noninferior solution of P52 of Pareto AFSA
4 结论
(1)针对传统方法求解多目标拆卸线平衡问题时将其转化为单目标问题求解的不足，本文设计了一种Pareto多目标人工鱼群算法，得到多种兼顾各个目标偏好程度的平衡方案，实现了求解结果的有效性与多样性。
(2)在人工鱼觅食过程中，通过引入遗传算法的随机交叉操作，指导鱼群向全局最优方向收敛，避免鱼群陷入局部最优。在人工鱼觅食行为、聚群行为与追尾行为过程中均采用拥挤距离机制来筛选非劣解，保留了各行为结果的多样性。将算法迭代过程中外部档案的非劣解作为下次迭代的种群，实现了种群的更新，提升了鱼群的全局寻优能力，加快了算法的收敛速度。
(3) 基于25项拆卸任务算例，求得8种可选平衡方案，并与现有5种单目标算法进行对比，验证了所提算法的有效性。进而将所提算法应用于52项拆卸任务实例中，对比Pareto蚁群算法，结果证实了所提算法的优越性。
[1] GUNGOR A, GUPTA S M. Disassembly Line in Product Recovery[J]. International Journal of Production Research, 2002, 40(11): 2569-2589.
[2] AVIKAL S, MISHRA P K, JAIN R. A Fuzzy AHP and PROMETHEE Method-based Heuristic for Disassembly Line Balancing Problems[J]. International Journal of Production Research, 2014, 52(5): 1306-1317.
[3] ALTEKIN F T, AKKAN C. Task-failure-driven Rebalancing of Disassembly Lines[J]. International Journal of Production Research, 2012, 50(18): 4955-4976.
[4] McGOVERN S M, GUPTA S M. A Balancing Method and Genetic Algorithm for Disassembly Line Balancing [J]. European Journal of Operational Research, 2007, 179(3): 692-708.
[5] McGOVERN S M, GUPTA S M. Ant Colony Optimization for Disassembly Sequencing with Multiple Objectives[J]. The International Journal of Advanced Manufacturing Technology, 2006, 30(5/6): 481-496.
[6] McGOVERN S M, GUPTA S M. Combinatorial Optimization Analysis of the Unary NP-complete Disassembly Line Balancing Problem[J]. International Journal of Production Research, 2007, 45(18/19): 4485-4511.
[7] KALAYCI C B, GUPTA S M. A Hybrid Genetic Algorithm Approach for Disassembly Line Balancing [C]//Proceedings of the 42nd Annual Meeting of Decision Science Institute. Boston, 2011: 2142-2148.
[8] KALAYCI C B, GUPTA S M, NAKASHIMA K. A Simulated Annealing Algorithm for Balancing a Disassembly Line[C]//Proceedings of the Seventh International Symposium on Environmentally Conscious Design and Inverse Manufacturing. Kyoto, Japan, 2011: 713-718.
[9] KALAYCI C B, GUPTA S M. A Particle Swarm Optimization Algorithm for Solving Disassembly Line Balancing Problem[C]//Proceedings of Northeast Decision Sciences Institute 2012 Annual Conference. Newport, Rhode Island, USA, 2012: 347-357.
[10] KALAYCI C B, GUPTA S M. Artificial Bee Colony Algorithm for Solving Sequence-dependent Disassembly Line Balancing Problem[J]. Expert Systems with Applications, 2013, 40(18): 7231-7241.
[11] KALAYCI C B, POLAT O, GUPTA S M. A Variable Neighbourhood Search Algorithm for Disassembly Lines [J]. Journal of Manufacturing Technology Management, 2015, 26(2): 182-194.
[12] KALAYCI C B, GUPTA S M. Tabu Search for Disassembly Line Balancing with Multiple Objectives[C]//41st International Conference on Computers and Industrial Engineering. Los Angeles, 2011: 477-482.
[13] 朱兴涛, 张则强, 朱勋梦, 等. 求解多目标拆卸线平衡问题的一种蚁群算法[J]. 中国机械工程, 2014, 25(8): 1075-1079. ZHU Xingtao, ZHANG Zeqaing, ZHU Xunmeng, et al. An Ant Colony Optimization Algorithm for Multi-objective Disassembly Line Balancing Problem [J]. China Mechanical Engineering, 2014, 25(8): 1075-1079.
[14] 丁力平, 谭建荣, 冯毅雄, 等. 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统, 2009, 15(7): 1406-1413. DING Liping, TAN Jianrong, FENG Yixiong, et al. Multiobjective Optimization for Disassembly Line Balancing Based on Pareto Ant Colony Algorithm [J].Computer Integrated Manufacturing Systems, 2009, 15(7)：1406-1413.
[15] CHENG C, LI H F, BAO C H. Hybrid Artificial Fish Algorithm to Solve TSP Problem[C]//Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation. Tianjin, 2016: 275-285.
[16] He Q, Hu X, Ren H, et al. A Novel Artificial Fish Swarm Algorithm for Solving Large-scale Reliability-redundancy Application Problem[J]. ISA Transactions, 2015, 59: 105-113.
[17] AZAD M A K, ROCHA A M A C, Fernandes E M G P. Solving Large 0-1 Multidimensional Knapsack Problems by a New Simplified Binary Artificial Fish Swarm Algorithm[J]. Journal of Mathematical Modelling and Algorithms in Operations Research, 2015, 14(3): 313-330.
[18] DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
(编辑 张 洋)
Pareto Artificial Fish Swarm Algorithm for Multi-objective Disassembly Line Balancing Problems
WANG Kaipu ZHANG Zeqiang MAO Lili LI Liuke
School of Mechanical Engineering，Southwest Jiaotong University，Chengdu，610031
In view of complexity of disassembly line balancing problems, an improved multi-objective artificial fish swarm algorithm was proposed based on Pareto set. In order to improve the searching ability of artificial fish, a random crossover operation of genetic algorithm was introduced to guide the artificial fish to the direction of global optimal disassembly directions. The crowding distance was adopted to filter the non-inferior solutions in the prey, swarm and follow processes of the artificial fish to realize the diversity of each behavior solution results. By employing the strategy of elite reservation, the non-inferior solutions in external file were added to the next iteration of the algorithm, which speeded up the convergence rate of the algorithm. Finally, the proposed algorithm was applied to the disassembly instances of different scales, and the results confirm the effectiveness and superiority of the proposed algorithm by comparing with the existing algorithms.
disassembly line balancing problem; multi-objective optimization; Pareto set; artificial fish swarm algorithm
2016-04-12
国家自然科学基金资助项目(51205328，51405403)；教育部人文社会科学研究青年基金资助项目(12YJCZH296)；四川省应用基础研究计划资助项目(2014JY0232)
TH122
10.3969/j.issn.1004-132X.2017.02.010
汪开普，男，1991年生。西南交通大学机械工程学院硕士研究生。主要研究方向为生产线平衡与智能优化。E-mail:wkp2010698@163.com。张则强(通信作者)，男，1978年生。西南交通大学机械工程学院教授、博士研究生导师。毛丽丽，女，1992年生。西南交通大学机械工程学院硕士研究生。李六柯，男，1993年生。西南交通大学机械工程学院硕士研究生。
