超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题

Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem

针对一类广泛存在的分布式流水线和车辆运输集成调度问题(Distributed Permutation Flow-shop and Vehicle Transportation Integrated Scheduling Problem,DPFVTISP),本文建立问题模型,并提出一种超启发式三维分布估计算法(Hyper-Heuristic three-Dimensional Estimation of Distribution Algorithm,HH3DEDA)进行求解.首先,根据DPFVTISP的问题特性,采用贪婪策略设计一种新颖的编解码规则.其次,为实现对DPFVTISP问题解空间中不同区域的深入搜索,设计10种低层启发式操作(即10种有效的邻域操作),并将其所构成的排列作为高层个体;同时在高层采用三维分布估计算法(three-Dimensional Estimation of Distribution Algorithm,3DEDA)学习和积累优质高层个体中块结构及其位置信息,再通过采样3DEDA中的概率模型生成新的高层个体或排列;进而在低层将高层所生成的每个新个体所表征的一系列有序的启发式操作作为一种新的启发式算法,对问题解空间执行较深入的邻域搜索.最后,通过仿真实验与算法对比验证HH3DEDA可有效求解DPFVTISP.

Aiming at a kind of widely existing distributed permutation flow-shop and vehicle transportation integrat⁃ed scheduling problem(DPFVTISP),this paper establishes the problem model and proposes a hyper-heuristic three-dimen⁃sional estimation of distribution algorithm(HH3DEDA)to solve it.Firstly,a novel coding and decoding rules adopting the greedy strategy is designed via analyzing the characteristics of DPFVTISP.Secondly,in order to search different regions in the solution space of DPFVTISP,ten kinds of low-layer heuristic operations,i.e.,ten kinds of effective neighborhood opera⁃tions,are designed,and their permutations are regarded as high-layer individuals.At the same time,the three-dimensional estimation of distribution algorithm(3DEDA)is used in the high layer to learn and accumulate the information of block structures and their positions in the high-quality high-layer individuals,and then new low-layer individuals or permutations are generated by sampling the probability model in 3DEDA.Furthermore,in the low layer,an ordered series of heuristic op⁃erations presenting by each new individual generated in the high layer is regarded as a new heuristic algorithm to execute further neighborhood search in the problem’s solution space.Finally,simulations and comparisons demonstrate that HH3DEDA can effectively solve the DPFVTISP.