计算机集成制造系统 ›› 2017, Vol. 23 ›› Issue (第6期): 1277-1285.DOI: 10.13196/j.cims.2017.06.013

• 产品创新开发技术 • 上一篇    下一篇

多目标拆卸线平衡问题的Pareto遗传模拟退火算法

汪开普,张则强,朱立夏,邹宾森   

  1. 西南交通大学机械工程学院
  • 出版日期:2017-06-30 发布日期:2017-06-30
  • 基金资助:
    国家自然科学基金资助项目(51205328,51405403);教育部人文社会科学研究青年基金资助项目(12YJCZH296);四川省应用基础研究计划资助项目(2014JY0232)。

Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem

  • Online:2017-06-30 Published:2017-06-30
  • Supported by:
    国家自然科学基金资助项目(51205328,51405403);教育部人文社会科学研究青年基金资助项目(12YJCZH296);四川省应用基础研究计划资助项目(2014JY0232)。

摘要: 针对传统方法求解多目标拆卸线平衡问题时求解结果单一、无法平衡各目标等不足,提出一种基于Pareto解集的多目标遗传模拟退火算法。该算法融合了遗传操作的快速全局搜索能力和模拟退火操作较强的局部搜索能力,对遗传操作的结果进行模拟退火操作,避免了算法陷入局部最优。结合多目标优化问题的特点,改进了模拟退火操作的Metropolis准则。根据拆卸序列之间的Pareto支配关系得到非劣解,并采用拥挤距离评价非劣解,实现了拆卸序列的精英保留,进而将非劣解添加到种群中,加快了算法的收敛速度。基于25项拆卸任务算例,通过与现有的6种单目标算法进行对比,验证了所提算法的有效性,并将所提算法应用于某拆卸线实例中,求得10种平衡方案,结果表明所提算法较Pareto蚁群算法更具优势。

关键词: 拆卸线平衡, 多目标优化, 遗传算法, 模拟退火算法, Pareto解集

Abstract: Aiming at the deficiencies of single solving result and failure to balance the optimization objectives of traditional method in solving multi-objective disassembly line balancing problem,a multi-objective genetic simulated annealing algorithm based on Pareto set was proposed,which combined rapid global search ability of genetic algorithm with strong local search capability of simulated annealing operation.The simulated annealing operation was performed on the solving results of genetic operation to avoid the local optimum.An improved Metropolis rule was employed by considering the characteristics of multi-objective optimization problems.The crowding distance as an evaluation mechanism was adopted to filter the non-inferior solutions acquired from Pareto dominance relationship,and the preserved non-inferior solutions were added in the population to speed up the convergence rate of the proposed algorithm.Based on a 25-task disassembly case,the effectiveness of proposed algorithm was verified by the comparison with other 6 single-objective algorithms.The proposed algorithm was applied to a disassembly instance and 10 task assignment schemes were obtained,and the solution results were compared with Pareto ant colony algorithm further indicating the superiority of proposed algorithm.

Key words: disassembly line balancing, multi-objective optimization, genetic algorithms, simulated annealing algorithm, Pareto set

中图分类号: