基于深度强化学习的自学习排课遗传算法研究

doi:10.11896/jsjkx.230600062

摘要/Abstract

摘要： 排课是教学活动中一项常规而重要的事项,传统的人工排课方式费时费力,且容易出现错误,无法满足大规模排课的需求,而经典排课遗传算法存在收敛速度过快、排课效率随约束因素的增加而下降等问题。针对已有排课遗传算法存在的问题,提出一种基于深度强化学习的自学习排课遗传算法(GA-DRL)。GA-DRL算法利用Q-learning算法,实现了交叉参数和变异参数的自适应调整,增强了遗传算法的搜索能力,通过建立马尔可夫决策过程(MDP)的参数动态调整模型,对种群适应度函数进行状态集合的分析,实现对种群的整体性能的综合评价。同时将深度Q-网络算法(DQN)引入调度问题中,以解决排课中种群状态多、Q表数据量大的问题。实验结果表明,与经典排课遗传算法和改进的遗传算法相比,GA-DRL算法在正确率和寻优能力上有所提升。所提算法还可以应用于考场安排、电影院的排座和航空航线规划等问题。

关键词: 排课问题, 遗传算法, Q-学习, 深度Q-网络

Abstract: 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.

Key words: Scheduling questions, Genetic algorithm, Q-Learning, DQN

中图分类号:

TP312

徐海涛, 程海燕, 童名文. 基于深度强化学习的自学习排课遗传算法研究[J]. 计算机科学, 2024, 51(6A): 230600062-8. https://doi.org/10.11896/jsjkx.230600062

XU Haitao, CHENG Haiyan, TONG Mingwen. Study on Genetic Algorithm of Course Scheduling Based on Deep Reinforcement Learning[J]. Computer Science, 2024, 51(6A): 230600062-8. https://doi.org/10.11896/jsjkx.230600062

参考文献

[1]WANG W H,LI W Q.Timetabling algorithm of high school optional class system based on improved genetic algorithm[J].Journal of Zhejiang University Tf technology,2016,44(6):601-607,670.
[2]ZHANG Z F.Design of an intelligent timetabling algorithm[J].Electronic Design Engineering,2022,30(9):134-138.
[3]JIANG J,BAI S X.Improvement of Genetic Algorithm and Its Application in Course Scheduling[J].Journal of Nanchang University(Natural Science),2018,42(4):388-392.
[4]SUN Y,HU J H.Course Schedule System Based on Genetic-Ant Colony Hybrid Algorithm[J].Computer Systems & Applications,2019,28(2):81-86.
[5]CAO Z C,LIN C R,ZHOUM C.A knowledge-based cuckoosearch algorithm to schedule a flexible job shop with sequencing flexibility[J].IEEE Transactions on Automation Science and Engineering,2019,18(1):56-69.
[6]JIAN Z,LIU S,ZHOU M,et al.Modified cuckoo search algo-rithm to solve economic power dispatch optimization problems[J].IEEE/CAA Journal of Automatica Sinica,2018,5(4):794-806.
[7]ZHANG Y,ZHONG H C,ZHANG C J,et al.Multi-strategyparallel genetic algorithm based on machine learning[J].Computer Integrated Manufacturing Systems,2021,27(10):2921-2928.
[8]YANG W,ZHI B C,WU Z R,et al.Review of Reinforcement Learning for Combinatorial Optimization Problem[J].Journal of Frontiers of Computer Science & Technology,2022,16(2):261.
[9]DENG Q L,LU J,CHEN Y H,et al.Optimiza tion method of CNC milling parameters based on deep reinforcement learning[J].Journal of Zhejiang University(Engineering),2022,56(11):2145-2155.
[10]WANG Y C,ZHOU C H,CHEN C X,et al.Extensible Intelligent Scheduling System Based on Two Fork Knowledge Tree Reasoning[J].Computer Engineering and Applications,2021,57(5):251-257.
[11]SONG T,CHEN M,WU C,et al.Automated course arrangement algorithm based on multi-class iterated local search[J].Comput Appl,2019,39(6):1760-1765.
[12]ZHANG Y.Design and application of course scheduling system based on tabu search method[J].Electronic Design Engineering,2018,26(16):40-44.
[13]CHEN L,XIU W.Solution to course-timetabling problem ofmobile learning system based on improved genetic algorithm[J].Comput Eng Appl,2019,55(6):224-230.
[14]JIANG Z F,QIN H,PEI-PEIL U,et al.Research on the application of ant colony algorithms to course scheduling in colleges and universities[J].Modern Computer,2019,10(45):23-33.
[15]LUO Y,CHEN Z,SCIENCE F O.Optimization of universitycourse scheduling problem based on improved pso algorithm[J].Computer Applications and Software,2018,35(6):241-247,303.
[16]LONG Z,AI J,ZOU H,et al.Network traffic predicting model based on improved grey wolf optimization algorithm[J].Application Research of Computers,2018,35(6):1845-1848.
[17]MA Y F,ZHANG H N,JIE S.Research and Implementation of Genetic Algorithm in Curriculum Arrangement System in Colleges and Universities[J].Computer Systems & Applications,2014,23(5):112-115.
[18]CHEN L,XIU W.Solution to course-timetabling problem ofmobile learning system based on improved genetic algorithm[J].Comput Eng Appl,2019,55(6):224-230.
[19]ZHANG H,LUO Y,ZHANG L,et al.Cultivated land changeforecast based on genetic algorithm and least squares support vector machines[J].Transactions of the Chinese Society of Agricultural Engineering,2009,25(7):226-231.
[20]MA X Z,LI F R.Application Research of course scheduling System based on improved Genetic Algorithm[J].Journal of Qingdao University(Engineering Technology Edition),2020,35(3):15-20,55.
[21]SHAHRABI J,ADIBI M A,MAHOOTCHI M.A reinforcement learning approach to parameter estimation in dynamic job shop scheduling[J].Computers & Industrial Engineering,2017,110(8):75-82.
[22]BI W J,ZHOU Y B.Research on inventory control and dynamic pricing of fresh produce based on deep reinforcement learning[J].Application Research of Computers,2022,39(9):2660-2664.
[23]LI B S,YEC M.Job shop scheduling problem based on deep reinforcement learning[J].Computer Engineering and Applications,2021,23:248-254.
[24]LIU Y,ZHANG C,LI T.Modeling and application of reinforcement learning A3C in elevator scheduling algorithm[J].Computer Engineering and Design,2022,43(1):196-202.
[25]FAN Y.Genetic algorithm for solving linear bilevel program-ming with interval coefficients[J].Journal of Computer Applications,2014,34(1):185.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed