摘要
排课是教学活动中一项常规而重要的事项,传统的人工排课方式费时费力,且容易出现错误,无法满足大规模排课的需求,而经典排课遗传算法存在收敛速度过快、排课效率随约束因素的增加而下降等问题。针对已有排课遗传算法存在的问题,提出一种基于深度强化学习的自学习排课遗传算法(GA-DRL)。GA-DRL算法利用Q-learning算法,实现了交叉参数和变异参数的自适应调整,增强了遗传算法的搜索能力,通过建立马尔可夫决策过程(MDP)的参数动态调整模型,对种群适应度函数进行状态集合的分析,实现对种群的整体性能的综合评价。同时将深度Q-网络算法(DQN)引入调度问题中,以解决排课中种群状态多、Q表数据量大的问题。实验结果表明,与经典排课遗传算法和改进的遗传算法相比,GA-DRL算法在正确率和寻优能力上有所提升。所提算法还可以应用于考场安排、电影院的排座和航空航线规划等问题。
Course scheduling is a routine and important matter in teaching activities.The traditional manual course scheduling method is time-consuming and laborious,and prone to errors,which cannot meet the needs of large-scale course scheduling.However,the classical course scheduling genetic algorithm has problems such as too fast convergence speed and the efficiency of course scheduling decreases with the increase of constraint factors.Aiming at the problems of existing course scheduling genetic algorithms,a self-learning course scheduling genetic algorithm(GA-DRL)based on deep reinforcement learning is proposed.GA-DRL algorithm uses Q-learning algorithm to realize the adaptive adjustment of cross parameter and variation parameter,and enhances the searching ability of genetic algorithm.By establishing a dynamic parameter adjustment model of Markov decision process(MDP),the state set of fitness function is analyzed,and the overall performance of the population is evaluated comprehensively.At the same time,the deep Q-network algorithm(DQN)is introduced into the scheduling problem to solve the problem of multiple population states and large amount of Q-table data.Experimental results show that GA-DRL algorithm improves accuracy and optimization ability compared with the classical course scheduling genetic algorithm and improved genetic algorithm.The proposed algorithm can also be applied to problems such as examination room arrangement,cinema seating and airline route planning.
作者
徐海涛
程海燕
童名文
XU Haitao;CHENG Haiyan;TONG Mingwen(Faculty of Artificial Intelligence in Education,Central China Normal University,Wuhan 430079,China)
出处
《计算机科学》
CSCD
北大核心
2024年第S01期229-236,共8页
Computer Science
