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

摘要

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