An improved genetic algorithm to solve the course scheduling problem in the context of new college entrance examinations
-
摘要: 我国提出新高考改革政策后, 越来越多地区和高中开始采用走班制教学模式. 相对于传统的行政班教学模式, 走班制教学模式使排课问题的约束条件进一步增多, 学校教育资源匮乏的现象进一步凸显. 传统的排课算法不适于求解走班制教学模式下的排课问题, 而纯粹的手动编排课表不仅费时费力, 排出的课表还可能存在大量冲突, 难以保证课表的可行性和合理性. 根据走班制教学模式的特点，设计了一种获取优质可行解的方法: 首先针对走班课程提出了一种自动生成教学班组合的方法; 然后运用改进的遗传算法高效合理地求解排课问题. 实验结果表明, 该算法可获得优质的课表安排, 并且已经加入到实际应用中.Abstract: After the new policy for college entrance examination reform was put forward in China, an increasing number of regions and senior high schools began to adopt the mobile teaching system. Compared with traditional teaching schedules, which use an executive class, this pattern further increased the challenges of scheduling, and the lack of school education resources has become more prominent. The traditional algorithm for curriculum arrangement is not suitable for solving the scheduling problem that exists with the mobile teaching system. Pure manual scheduling is not only time-consuming and laborious, but there may also be unforeseen conflicts; it is difficult to guarantee the feasibility and rationality of a curriculum. Given the characteristics of a mobile teaching system pattern, this paper presents a method for obtaining high-quality feasible solutions to deal with course scheduling. First, a method for automatically generating combinations of mobile teaching classes is proposed. Second, the improved genetic algorithm is used to solve the scheduling problem efficiently and reasonably. Experiments show that the proposed algorithm can achieve a high-quality curriculum, and the method has been applied in practical applications.
-
图 13 使用本文的适应度函数对图12的数据进行转换
Fig. 13 Evolutionary effect diagram of transforming the data from Fig. 12 using the fitness function of this paper
表 1 针对不同参数的实验结果
Tab. 1 Experimental results for different parameters
交叉概率 变异概率 惩罚因子α1 惩罚因子α2 最佳个体适应度 0.5 0.01 0.80 0.90 0.663 27 0.5 0.01 0.88 0.94 0.707 42 0.5 0.01 0.96 0.98 0.676 61 0.5 0.05 0.80 0.90 0.783 58 0.5 0.05 0.88 0.94 0.785 00 0.5 0.05 0.96 0.98 0.768 70 0.5 0.10 0.80 0.90 0.812 35 0.5 0.10 0.88 0.94 0.801 39 0.5 0.10 0.96 0.98 0.820 73 0.6 0.01 0.80 0.90 0.710 95 0.6 0.01 0.88 0.94 0.692 25 0.6 0.01 0.96 0.98 0.706 95 0.6 0.05 0.80 0.90 0.774 28 0.6 0.05 0.88 0.94 0.821 56 0.6 0.05 0.96 0.98 0.766 33 0.6 0.10 0.80 0.90 0.792 31 0.6 0.10 0.88 0.94 0.829 27 0.6 0.10 0.96 0.98 0.785 96 0.7 0.01 0.80 0.90 0.685 24 0.7 0.01 0.88 0.94 0.685 08 0.7 0.01 0.96 0.98 0.669 02 0.7 0.05 0.80 0.90 0.776 15 0.7 0.05 0.88 0.94 0.742 72 0.7 0.05 0.96 0.98 0.766 42 0.7 0.10 0.80 0.90 0.804 59 0.7 0.10 0.88 0.94 0.821 31 0.7 0.10 0.96 0.98 0.776 53 
下载: 导出CSV
表 2 针对不同规模的实验结果
Tab. 2 Experimental results for different scales
教学规模/个班级 排课耗时/s 最佳个体适应度 12 391 0.877 65 24 786 0.826 18 36 1 172 0.789 17 48 1 586 0.738 95
下载: 导出CSV
-
[1] 夏永庚, 朱琴. 走班制背景下高中班主任德育工作的挑战与应对 [J]. 现代基础教育研究, 2019, 33(1): 215-220. [2] GOTLIEB C C. The construction of class-teacher timetables [J]. Communications of the ACM, 1962, 5(6): 73-77. [3] EVEN S, ITAI A, SHAMIR A. On the complexity of time table and multi-commodity flow problems [C]//16th Annual Symposium on Foundations of Computer Science (SFCS 1975). IEEE, 1975: 184-193. DOI: 10.1109/SFCS.1975.21. [4] 张艳红, 王玲玲, 腾东兴. 基于空间模型和遗传算法的高校排课系统 [J]. 计算机系统应用, 2015, 24(9): 49-55. DOI: 10.3969/j.issn.1003-3254.2015.09.008. [5] 袁俊毅. 基于遗传算法的高校教务排课系统设计与实现 [D]. 长沙: 湖南大学, 2017. [6] 姜婧, 白似雪. 遗传算法的改进及其在排课问题中的应用 [J]. 南昌大学学报(理科版), 2018, 42(4): 388-392. [7] 唐环, 高健. 在中学排课问题中实用的模拟退火算法应用 [J]. 计算机系统应用, 2017, 26(10): 225-230. [8] THEPPHAKORN T, PONGCHAROEN P, HICKS C. An ant colony based timetabling tool [J]. International Journal of Production Economics, 2014, 149: 131-144. DOI: 10.1016/j.ijpe.2013.04.026. [9] 张媛, 祁兰. 基于禁忌搜索的排课系统的设计 [J]. 电子设计工程, 2016, 24(22): 71-73. [10] FONG C W, ASMUNI H, LAM W S, et al. A novel hybrid swarm based approach for curriculum based course timetabling problem [C]//2014 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2014: 544-550. [11] 王卫红, 李文琼. 基于改进遗传算法的高中走班制排课算法 [J]. 浙江工业大学学报, 2016, 44(6): 601-607, 670. DOI: 10.3969/j.issn.1006-4303.2016.06.002. [12] 陈璐, 王秀. 改进遗传算法求解走班制下的排课问题 [J]. 计算机工程与应用, 2019, 55(6): 218-224. [13] 马辉辉. 走班制的实施与注意问题 [J]. 教育与教学研究, 2016, 30(2): 99-103. DOI: 10.3969/j.issn.1674-6120.2016.02.019. [14] 张贵军, 陈安, 胡俊. 基于蒙特卡洛遗传算法的排课问题研究 [J]. 实验技术与管理, 2019, 36(3): 170-174. [15] 冯智莉, 易国洪, 李普山, 等. 并行化遗传算法研究综述 [J]. 计算机应用与软件, 2018, 35(11): 1-7, 80. [16] 葛继科, 邱玉辉, 吴春明, 等. 遗传算法研究综述 [J]. 计算机应用研究, 2008, 10: 2911-2916. DOI: 10.3969/j.issn.1001-3695.2008.10.008. [17] 王赞, 樊向宇, 邹雨果, 等. 一种基于遗传算法的多缺陷定位方法 [J]. 软件学报, 2016, 27(4): 879-900. [18] 雷英杰, 张善文. MATLAB遗传算法工具箱及应用 [M]. 西安: 西安电子科技大学出版社, 2014. [19] 董玉锁, 贺波, 尹迎, 等. 利用改进遗传算法破解排课难题 [J]. 中国教育技术装备, 2018(1): 16-19. DOI: 10.3969/j.issn.1671-489X.2018.01.016. -
点击查看大图
图(14) / 表(2)
计量
- 文章访问数: 342
- HTML全文浏览量: 255
- PDF下载量: 27
- 被引次数: 0