Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop Scheduling
针对遗传编程在动态柔性作业车间调度中种群多样性不足导致早熟收敛的问题，提出一种结合词法选择的新算法，通过多案例适应度方案平衡案例数量与评估效率，实验表明其优于现有遗传编程方法和深度强化学习方法。
Dynamic flexible job shop scheduling is a prominent combinatorial optimisation problem with many real-world applications. Genetic programming has been widely used to automatically evolve effective scheduling heuristics for dynamic flexible job shop scheduling. A limitation of genetic programming is the premature convergence due to the loss of population diversity. To overcome this limitation, this work considers using lexicase selection to improve population diversity, which has achieved success on regression and program synthesis problems. However, it is not trivial to apply lexicase selection to genetic programming for dynamic flexible job shop scheduling, since a fitness case (training scheduling simulation) is often large-scale, making the fitness evaluation very time-consuming. To address this issue, we propose a new multi-case fitness scheme, which creates multiple cases from a single scheduling simulation. Based on the multi-case fitness, we develop a new genetic programming algorithm with lexicase selection, which uses a single simulation for fitness evaluation, thus achieving a better balance between the number of cases for lexicase selection and evaluation efficiency. The experiments on a wide range of dynamic scheduling scenarios show that the proposed algorithm can achieve better population diversity and final performance than the current genetic programming parent selection methods and a state-of-the-art deep reinforcement learning method.