Instance-Rotation-Based Surrogate in Genetic Programming With Brood Recombination for Dynamic Job-Shop Scheduling
针对动态作业车间调度中遗传编程子代重组耗时问题，提出一种基于实例旋转的代理模型，通过跨代样本和适应度映射策略提高估计精度，显著提升调度启发式质量。
Genetic programming (GP) has achieved great success for learning scheduling heuristics in dynamic job-shop scheduling (JSS). In theory, generating a large number of offspring for GP, known as brood recombination, can improve its heuristic generation ability. However, it is time consuming to evaluate extra individuals. Phenotypic characterization-based surrogates with K-nearest neighbors have been successfully used for GP to preselect only promising individuals for real fitness evaluations in dynamic JSS. However, sample individuals used by surrogate are from only the current generation, since the fitness of individuals across generations is not comparable due to the rotation of training instances. The surrogate cannot accurately estimate the fitness of an offspring that is far away from all the limited sample individuals at the current generation. This article proposes an effective instance-rotation-based surrogate to address the above issue. Specifically, the surrogate uses the samples extracted from individuals across multiple generations with different instances. More importantly, we propose a fitness mapping strategy to make the fitness evaluated by different instances comparable. The results show that the GP with brood recombination and the proposed surrogate can significantly improve the quality of scheduling heuristics. The results also reveal that the proposed algorithm has successfully reduced the number of omitted promising offspring due to the higher accuracy of the surrogate. The samples in the new surrogate spread better in the phenotypic space, and the nearest neighbor tends to be closer to the predicted offspring. This makes the estimated fitness more accurate.