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

Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem

作　　者：张闻强 邢征 杨卫东 ZHANG Wenqiang;XING Zheng;YANG Weidong(Key Laboratory of Grain Information Processing and Control,Ministry of Education(Henan University of Technology),Zhengzhou Henan 450001,China;College of Information Science and Engineering,Henan University of Technology,Zhengzhou Henan 450001,China)

机构地区：[1]粮食信息处理与控制教育部重点实验室(河南工业大学),郑州450001 [2]河南工业大学信息科学与工程学院,郑州450001

出　　处：《计算机应用》2021年第8期2249-2257,共9页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61772173);河南省高校科技创新人才支持计划项目(19HASTIT027);河南省科技攻关项目(202102210131)。

摘　　要：柔性作业车间调度问题(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显著优于对比算法,且均不存在所提算法显著差于对比算法的情况。可见相较于对比算法,所提出的算法具备较好的收敛与分布性能。Flexible Job-shop Scheduling Problem(FJSP)is a widely applied combinatorial optimization problem.Aiming at the problems of multi-objective FJSP that the solution process is complex and the algorithm is easy to fall into the local optimum,a Hybrid Particle Swarm Optimization algorithm with Multi-Region Sampling strategy(HPSO-MRS)was proposed to optimize both the makespan and total machine delay time.The multi-region sampling strategy was able to reorganize the positions of the Pareto frontiers that the particles belonging to,and guide the corresponding moving directions for the particles in multiple regions of the Pareto frontiers after sampling.Thus,the convergence ability of particles in multiple directions was adjusted,and the ability of uniform distribution was improved to a certain extent.In addition,in the encoding and decoding aspect,the decoding strategy with interpolation mechanism was used to eliminate the potential local left shift;in the particle updating aspect,the particle update method of traditional Particle Swarm Optimization(PSO)algorithm was combined with the crossover and mutation operators of Genetic Algorithm(GA),which improved the diversity of search process and avoid the algorithm from falling into the local optimum.The proposed algorithm was tested on benchmark problems Mk01-Mk10 and compared with Hybrid Particle Swarm Optimization algorithm(HPSO),Nondominated Sorting Genetic Algorithm Ⅱ(NSGA-Ⅱ),Strength Pareto Evolutionary Algorithm 2(SPEA2)and Multi-Objective Evolutionary Algorithm based on Decomposition(MOEA/D)on algorithm effectiveness and operation efficiency.Experimental results of significance analysis showed that,HPSO-MRS was significantly better than the comparison algorithms on the convergence evaluation indexes Hyper Volume(HV)and Inverted Generational Distance(IGD)in 85% and 77.5% of the control groups,respectively.In 35% of the control groups,the distribution index Spacing of the algorithm was significantly better than those of the comparison algorithms.And there was no si

关 键 词：粒子群优化 多区域采样 多目标优化问题 柔性作业车间调度问题 遗传算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP18[自动化与计算机技术—计算机科学与技术]