利用强化学习的改进遗传算法求解柔性作业车间调度问题

Improved Genetic Algorithm Using Reinforcement Learning to Solve Flexible Job Shop Scheduling Problem

针对传统遗传算法在解决柔性作业车间调度问题时易陷入局部最优解、参数不能智能调整、局部搜索能力差的问题,建立以最大完工时间最小为目标的柔性作业车间调度模型,并提出一种基于强化学习的改进遗传算法(reinforcement learning improved genetic algorithm,RLIGA)求解该模型。首先,在遗传算法迭代过程中,利用强化学习动态调整关键参数。其次,引入基于工序编码距离的离散莱维飞行机制,改进求解空间。最后,引入变邻域搜索机制,提升算法的局部开发能力。使用PyCharm运行Brandimarte算例,验证算法的求解性能,实验证明所提算法求解效率较高,跳出局部最优能力更强,求解结果更好。

Aiming at the problems that traditional genetic algorithm is prone to fall into local optimal solution,parameters cannot be adjusted intelligently,and local search ability is poor when solving flexible job-shop scheduling problems,a flexible job-shop scheduling model with the goal of minimizing the maximum completion time was established.A reinforcement learning improved genetic algorithm(RLIGA)based on reinforcement learning was proposed to solve the model.Firstly,in the iterative process of genetic algorithm,reinforcement learning was used to dynamically adjust key parameters.Secondly,the discrete Lévy flight mechanism based on process coding distance was introduced to improve the solution space.Finally,the variable neighborhood search mechanism was introduced to improve the local development ability of the algorithm.PyCharm was used to run Brandimarte examples to verify the solving performance of the proposed algorithm.The experiment proves that the proposed algorithm has higher solving efficiency,stronger ability to jump out of the local optimal,and better solving results.