高校多校区排课的遗传算法的改进研究
杨秀玉 雷晶晶
摘 要：随着计算机技术的不断发展，教育现代化渐渐进入各大高校，计算机自动排课已经取代了传统的手工排课，但多校区办学模式的兴起，给排课带来了新的挑战。基于传统的遗传算法，结合部门的工作经验，充分考虑各方面的因素，对其进行改进，实现教务管理的科学化。
关键词：多校区;排课;遗传算法
Abstract：With the development of computer technology，the modernization of education has gradually entered major universities.Computer automatic scheduling has replaced the traditional manual scheduling，but the rise of the multi-campus mode of schooling has brought new challenges to the scheduling.Based on the traditional genetic algorithm，fully considered various factors，and improved it，to realize the scientific management of educational administration.
Key words：multi-campus;course scheduling;genetic algorithm
随着社会经济的不断发展和高等教育大众化进程的推进，高校招生规模不断扩大，越来越多的学生参加高考进入大学接受高等教育。由于大部分高校建校早，配套设施已经不能满足不断扩大的招生规模，形成了多校区办学新格局。目前要保证多校区协同排课，实现资源共享，寻求多校区排课对资源利用的最优化。
课表是各个学校组织与实施教学过程的主要依据，是学校教学工作有计划、有秩序进行的重要保证。科学合理地编排、调度、执行课表是顺利实施人才培养方案，建立良好教学秩序的基础。因此，排课是高校教务工作过程中必须面对的问题，科学、规范的排课是获得高水平教学质量的必要条件，也是教学管理中最为关键的一环。它涉及到的因素很多，是一个多约束、多目标的优化问题，已经被深入研究并被公认是NP完全问题。[1]目前，单校区的排课普遍采用传统的遗传算法，但多校区排课涉及老师在不同校区上课、教室分配等问题，复杂程度明显提升，传统的遗传算法不能满足需求。
一、排课问题的分析
随着各大高校的扩招，学生数量不断增长，教学资源也越发紧张，高校也纷纷扩建校区，使得多校区排课成为一项繁重而复杂的工作。多校区办学，一学期几百甚至上千门课程，课程的特殊性，老师的特殊要求，学校根据现状的特别指示等因素都要考虑在内，并合理地协调安排涉及的专业、老师、学生，同时要对几百甚至上千门课程进行合理地组织安排。
排课本身就是处理教学环节中的各种矛盾、解决教师与学生双边活动、推动教学工作向前发展的有效工作。排课的过程中出现的矛盾是班级、课程、教师、时间、教室、校区在排列组合中所发生的冲突和矛盾，它们也是排课过程中的约束。课表的编排必须准确无误、科学化、合理化，以保证教学过程的正常运转。排课涉及的因素很多，应坚持以“纲”为本，以“人”为本，以“校”为本的三原则。以“纲”为本中的“纲”是指培养方案和教学任务，两者都是排课工作的重要依据，是排课必须坚持的基本原则;以“人”为本是指考虑学生和老师在教学运行过程中的合理性，排课必须遵循教育教学规律，坚持“以人为本、以学为主”和“一切为了学生，为了学生一切”的教学理念，重视学生的身心健康，考虑学生的接受能力，保障课表编排的科学性、合理性;以“校”为本指考虑本校的校情，多校区排课需将不同的校区在系统中进行不同的设置，确保排课没有人为造成的低级错误。[2]
二、遗传算法的基本原理
遗传算法是计算数学中用于解决最佳化的搜索算法，其特点是搜索群体和种群中个体之间的信息交换，可以用于对传统方法非线性的、难以解决的、复杂问题的处理[3]。
遗传算法的基本思想是从问题可能潜在解集的一个初始种群开始，再逐代演化产生出越来越好的近似解。在每一代根据问题域中个体的适应度大小挑选，利用自然遗传学的遗传算子进行组合交叉和变异，产生出新的解集种群。这个过程将使得种群像自然进化一样的后代，比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。
基本遗传算法的构成要素：
（1）染色体编码。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体。初始群体中各个个体的基因值可用均匀分布的随机数来生成。
（2）适应度函数。基本遗传算法按与个体适应度成正比的概率来决定当前群体中个体遗传到下一代群体中的机会。遗传算法是以适应度函数为唯一反馈标准，也就是通过适应度函数值的大小来判断染色体的优劣，决定染色体是否保留到下一代。[4]
（3）遗传算子。基本遗传算法使用选择、交叉、变异三种遗传算子。
三、排课遗传算法的改进
（一）减小排课问题维度
多校区排课属于涉及课程、班级、教师、教室、时间、校区的六元组合问题，多校区课表就是将这些六种因素进行合理整合，在满足各种约束条件下，保证教学任务的顺利完成。以{K、C、L、R、T、U}表示六元组合。
考虑到六维变量的复杂性，即使处理小规模的问题也很繁杂，因此本文将六维变量简化为二维变量。任课老师教授哪些课程是由各二级学院相应的教研室主任在前一学期期末就在教学计划的落实里安排好了的，各个专业所对应的班级在某学期需要开设的课程也是由培养方案确定好的，因此，班級C、课程K、教师L的组合基本已经确定，由Q来表示，Q={C，K，L};教室R已经包含了校区U的信息，用时间与教室的笛卡尔积用N表示，N=T*R;进行Q与N的组合，则六元组合的排课问题简化为（Q，N）二元组问题。
（二）改进传统的二进制染色体编码方式
染色体的编码方式极大地影响着交叉、变异等遗传算子的运算方法和程序实现的时间复杂度。遗传算法的编码方式很多，传统的也是最常见的是二进制编码，由于二进制编码不太适用于多约束且复杂的高校课程编排，因此根据实际需求，改进遗传算法采用二维资源片十进制编码方式进行编码。它便于计算适应度函数，减小时间和程序复杂程度，方便生成初始种群，便于檢测交叉和变异中的冲突。
结合实际分析，采用二维资源片十进制编码代替传统的二进制编码形式进行编码。以某高校为例，由于该校两小节课由同一位老师授课，且教室不会改变，班级不会改变，把两小节课合并成一大节课，因此把两小节课作为一个时间片，允许排课的时间为周一至周五，每天不超过四大节课，一周总共20个时间片，把{11，12，13，14，21，22，…，52，53，54}作为时间片集合，其中集合{11}表示星期一的第1节课，集合{21}表示星期二的第1大节课。把{R1，R2，R3，…，Rn}作为教室集合，教室和时间的笛卡尔积共有20*n个资源片空间{（R1，11），（R2，11），（R3，11），…，（Rn，54）}。
采取此种编码方式进行排课可以确保一项信息只被分配到一个资源片，尽量避免了资源冲突，会更容易地产生初始种群，能缩短种群产生的时间，提升了实用性和排课效率。
（三）遗传算子的改进
1.选择算子
选择的目的是寻找进化过程中最好的个体，确保目前保留下来的个体是最优的。在此过程中若遇到更好的，就代替之前保留的，如果遇到没当前的个体好，就不选择遇到的这个。选择方法是计算染色体被选中的概率，保留概率大的。选中某一染色体的概率为：A/B。其中A代表该染色体的适应度值，B代表所有染色体的适应度值之和。
2.交叉算子
传统的遗传算法中有单点交叉和多点交叉两种，由于要将遗传算法应用于多校区排课的实际问题中，两种交叉都有增加冲突的可能，会降低进化效率，因此提出使用元素对交叉，找到染色体中的相同基因片，交叉其中的资源部分，以此得到更优的个体，减少冲突的概率。[5]
元素对交叉，交叉前检测有无冲突，若无冲突进行交叉，若有冲突再次选取交叉基因。随机取出1对染色体，采用分步交叉方式，产生交叉位，交换该课程中两个染色体基因中的资源，也就是改变上课的时间教室。该交叉方法，仅对部分交叉，避免了发生冲突。
3.变异算子
变异可以避免在选择时漏掉最优解，维护种群的多样性。变异和交叉一样，变异前检测有无冲突，若无冲突进行变异，若有冲突重新选择变异位。变异算子的采用与交叉算子相对应，依据变异概率选出染色体，变换资源。
参考文献：
[1]周芬.遗传算法在多校区排课系统中的应用[J].科技信息，2010（06）：234.
[2]李祥.多校区高校二级教学管理条件下的排课模式探讨[J].科教文汇（中旬刊），2016（02）：132-133.
[3]梁宇滔.基于遗传算法的多校区排课系统分析与设计[J].佛山科学技术学院学报（自然科学版），2011，29（06）：75-78.
[4]凌敏.基于遗传算法的多校区排课系统的设计与实现[D].湖南大学，2015.
[5]李琳.多校区高校自动排课系统的研究与设计[D].电子科技大学，2013.
基金项目：2019年中央高校建设世界一流大学（学科）和特色发展引导专项资金支持（D201903）
作者简介：杨秀玉（1993—），女，四川内江人，硕士，研究实习员，研究方向：教学管理。
