基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题

• 作者: 张闻强 邢征 杨卫东
• 来源期刊: 计算机应用
• 关键词: 粒子群优化 多区域采样 多目标优化问题 柔性作业车间调度问题 遗传算法
• 年，卷（期）: 2021,（8）
• 所属期刊栏目: 先进计算|Advanced computing
• 页码范围: 2249-2257
• 页数: 9页
• 分类号: TP301.6|TP18
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2020101675

摘要

柔性作业车间调度问题(FJSP)是一类应用广泛的组合优化问题.针对多目标FJSP求解过程复杂、算法易陷入局部最优的问题,提出了一种基于多区域采样策略的混合粒子群优化算法(HPSO-MRS),以同时优化最大完工时间和总机器延迟时间这两个目标.多区域采样策略能够区分粒子所在Pareto前沿面的位置,根据不同区域进行采样重组,并为采样后位于Pareto前沿面多个区域的粒子规划相应的运动方向,从而有针对性地调整粒子在多个方向上的收敛能力,并带来一定程度的均匀分布能力的提升.此外,编解码方面使用带插空机制的解码策略来消除可能存在的局部左移;粒子更新方面将传统粒子群优化(PSO)算法的粒子更新方式与遗传算法(GA)的交叉变异算子相结合,提升了算法搜索过程的多样性并避免算法陷入局部最优.把所提算法在Benchmark问题Mk01～Mk10上进行测试,与传统的HPSO、NSGA-Ⅱ、基于适应度分配策略的多目标进化算法(SPEA2)和基于分解的多目标进化算法(MOEA/D)进行算法效力和运行效率对比.显著性分析的实验结果表明,HPSO-MRS在收敛性评价指标HV和IGD上分别在85％和77.5％的对照组中显著优于对比算法,而该算法在35％的对照组中的分布性指标Spacing显著优于对比算法,且均不存在所提算法显著差于对比算法的情况.可见相较于对比算法,所提出的算法具备较好的收敛与分布性能.