流水车间调度问题的快速多目标混合进化算法

来源：计算机应用杂志2016年第4期北京时间：

作者：张闻强, 卢佳明, 张红梅

单位：河南工业大学 信息科学与工程学院, 郑州 450000

摘要：针对最大完工时间最小和总流经时间最小的双目标流水车间调度问题,提出一种快速多目标混合进化算法。算法将矢量评价遗传算法的采样策略与一种新的基于Pareto支配与被支配关系的适应度函数的采样策略进行了融合。新的采样策略弥补了矢量评价遗传算法(VEGA)采样策略的不足。VEGA善于搜索Pareto前沿面的边缘区域,但却忽略了Pareto前沿面的中心区域,而新的采样策略则倾向于Pareto前沿面的中心区域。这两种机制的融合保证了混合算法能够快速平稳地向Pareto前沿区域收敛。此外,由于混合采样策略不需要考虑距离,使得算法效率也得到了很大的提升。在对Taillard基准测试集进行的仿真实验结果显示,相对于非支配排序遗传算法(NSGA-Ⅱ)和强度Pareto进化算法(SPEA2),该快速多目标混合进化算法在收敛性和分布性两方面都有所提高,并且算法的效率也得到了改进。所提出的混合算法能够更好地解决双目标的流水车间调度问题。

关键词：流水车间调度,混合进化算法,采样策略,矢量评价遗传算法,多目标优化

基金资助：国家自然科学基金资助项目(U1304609);河南工业大学自然科学基础研究重点培育计划项目(2012JCYJ04);河南省省属高校基本科研业务费专项资金资助项目(2014YWQQ12)。