高校智能排课系统问题研究及算法改进策略
来源:用户上传
作者:张芸芸
摘 要：排课是高校教学管理的重要工作，其本质是在学校现有的软、硬件环境下，合理地安排教师、学生、课程、教室等，使教学规划有计划、有秩序地进行。本文在对高校的学生、教师和教务管理员进行认真的调研、访谈的基础上，通过汇总分析得出：为更好地提高教室利用效率、确保教学有序进行，通过某种智能策略算法来建立智能排课系统尤为重要。
关键词：遗传算法 智能排课系统 群体策略
排课是高校教学管理的重要工作，其本质是在学校现有的软、硬件环境下，合理地安排教师、学生、课程、教室等，使学校的教学规划有计划、有秩序地进行。随着高校学生人数的增多，院系开设课程的规模大幅上升，排课已经成为一项极其复杂的工作，现在使用人工排课已经无法满足学校教学管理的需求，因此利用计算机来实现自动化排课，已经成为计算机应用学科的一项重要任务。
1 高校排课工作现状研究
排课任务实质上是根据学校的教学环境，包括教师数量、教学地点、教室数量和教学时间的限制下，能够促使整个学校的所有课程正常有序地开展教学工作。高校排课问题是一个非常复杂的组合规划问题，需要满足各种约束条件，以保证在上课过程中，教师、学生和教室不会产生任何的冲突，也即不同级两个或者多个班级在同一时间被安排在同一个教室，或者是同一个教师在同一时间被安排上了多门课程，导致教学无法正常进行。前期，国内的部分院校在进行排课时，使用人工排课的方法，人工排课工作的主要方法是实施摆牌，就是将印有课程名字的小纸牌在画有空的课程表的版面上进行初排、调整，一边依据排课经验进行设置，一边观察每门课程所在的位置是否合理，以便能够形成一个有效的正常课程表。由于人工排课没有任何的理论指导，也没有进行数学建模，主要依靠排课者的经验，具有很大的弊端，这种方法适合于规模较小、课程少的学校，但是随着高等院校规模的扩大，对上万名学生需要在一年中完成上万节课程的设置，如果仅仅依靠人工进行排课，那么将会花费大量的人力、物力和财力，工作量非常的大，并且无法排除易于调整的课程表。
2 高校智能排课系统传统算法的局限性
随着计算机技术的迅速发展，其拥有更强更快的数据处理能力，并且拥有高速运算的特点，通过对排课实施建模，能够在满足时间、教师、教室、课程、学生等约束条件的同时，通过排课算法进行求解，能够有效的实现自动化排课，提高排课的正确性和排课效率，节省人力、物力和财力，使教务管理人员从繁琐、复杂的排课任务中解脱出来，推动了排课工作的管理与发展，也间接地推动了教学管理的信息化，具有非常重要的意义。
在排课过程中，系统涉及的约束条件非常多，主要包括教师、课程、教室、班级等，排课表实施编排过程中，要对上述主要约束条件进行合理的规划，不能够产生任何的冲突，比如同一个教师在同一时间不能被安排多门课程，同一个班级在同一时间不能有两个教师上课，并且满足用户需求资源，满足教师的要求和限制。
目前，智能排课系统在进行课程表排设过程中，通常采用的算法有蟻群算法、模拟退火算法、回溯法、基于规则的推理算法、遗传算法等，随着试题的增多，试题难度等级的逐渐加大，使用现有的算法进行智能组卷，存在陷入局部最优、组卷成功几率较低的问题。虽然许多专家和学者为了解决排课问题，已经提出了很多算法，比如分组优化、分支定界、专家系统等。但是，上述算法总是存在以下问题：
一是专家系统可以依据排课的经验知识，组织排课的规则，但是排课过程约束条件较多，每个学校的实际情况各不相同，经验知识较难获取，排课结果也不好。
二是排课表的优劣判定标准较少，针对一个问题求解，无法从多个角度实施优化。
3 传统遗传算法在进行智能排课时遇到的问题
排课问题的约束条件分为软约束、硬约束两种类别，学生、教师、教室等硬件资源是硬约束，这些条件在排课过程中必须满足，该约束度量一个排课算法的可行性;软约束既可以满足也可以不用满足，其度量一个排课算法的优劣。
遗传算法能够有效的模拟达尔文的自然淘汰和遗传变异选择的生物进化过程，通过搜索最优的模拟进化算法。该算法可以针对一串描述字符的位串进行操作，不同位串在实际的应用环境中代表不同的问题。遗传算法可以从若干个初始的种群开始搜索，根据当前的种群成员，模仿生物的遗传进化过程，选择基因优良的下一代作为进化的目标。遗传算法的主要目的是针对相关的问题进行建模分析，寻求相关问题的最优解。也就是根据问题的背景和性质，构建一个合适的适应度函数，迭代执行，然后在求解空间中选择较优的种群进行评估、遗传变换、变异和选择等交叉选择操作，将满足目标函数的个体选为最优解。
目前，传统的遗传算法已经在很多领域得到了广泛的应用，比如自动组卷过程中、基因序列预测过程中、数据库连接优化过程中，均得到了良好的效果。但是传统的遗传算法在使用过程中，存在以下问题：
第一，传统遗传算法在排课应用过程中，由于排课软硬约束条件较多，约束比较复杂，遗传算法选择优势个体遗传到下一代，遗传算法在排课过程中，非常容易陷入到局部最优化，无法求得全局最优解。
第二，排课过程中，排课存在硬件约束（教师、教室）和软件约束（时间），因此，如果同时考虑这两种约束模式，遗传算法则成为一个多约束和多目标的组合优化问题，无法求解。
4 基于群体策略的遗传算法在高校排课系统中的应用
遗传算法通过应用和改进，已经出现了许多改进后的遗传算法，比如并行遗传算法、网格遗传算法等。为了寻求一个排课问题的最优解，作者通过对相关的遗传算法进行对比研究，将随机数理论其引入到遗传算法中，通过实施自然的选择、变异等发生机制，提高每一个个体的适应度，充分体现物竞天择、适者生存的基本思想和原理，并且提出了一种改进的遗传算法——基于群体策略的遗传算法，该策略能够促进每一代的平均适应度逐代提高，直到寻求到最优解，可以较好地解决传统算法寻求最优解时容易产生的收敛速度慢、陷入局部最优等问题，尽可能地满足“实用、合理、有特色”的需求，形成最优化的排课方案。
基于群体策略遗传算法的基本操作流程包括以下6个步骤：
第一步：生成初始种群：随机生成包含所有解空间的初始种群，种群中的每个解都使用一个个体表示;第二步：计算适应度函数：根据目标函数，计算种群中个体的适应度函数;第三步：执行选择操作：根据适应度函数值和选择操作方法，淘汰含有劣势基因个体，选择优势个体，即逐步向最优解靠近;第四步：交叉操作：对种群中的个体实施交叉操作，产生新的个体;第五步：变异操作：对种群中的个体实施变异操作;第六步：判断是否满足终止条件或求得最优解。如果满足终止条件或求得最优解，即可停止算法;否则，跳转到第二步。
基于群体策略的遗传算法使用概率策略设置选择操作算子，促进适应度较高的个体遗传到下一代，增加种群的平均适应度，该策略能够逐代提高每一代的平均适应度，直到寻求到最优解，从而解决无法从多个约束条件实施优化的问题。实验结果表明，基于群体策略的改进遗传算法能够有效地寻求满足“实用、合理、有特色”的需求的排课方案，具有较好的效果。
参考文献
[1] 郭彤.人工智能算法在排课系统中的研究与应用[J].天津职业院校联合学报，2012，22（2）：14-18.
[2] 崇阳.遗传算法在高职院校排课系统中的应用研究[J].电脑编程技巧与维护，2016（1）：23-24，30.
[3] 马小姝，李海芸.遗传算法在高校排课系统中的应用研究[J].信息与电脑：理论版，2018（8）.
转载注明来源:https://www.xzbu.com/1/view-15273089.htm
