基于遗传算法的高校在线排课系统的设计与实现

樊伟宏 ，杨文婷 ，王 昊 ，刘 文

（1.新疆农业大学科学技术学院，新疆乌鲁木齐830052；2.新疆农业大学思想理论教研部，新疆乌鲁木齐830052）

基于遗传算法的高校在线排课系统的设计与实现

樊伟宏1，杨文婷2，王 昊1，刘 文1

（1.新疆农业大学科学技术学院，新疆乌鲁木齐830052；2.新疆农业大学思想理论教研部，新疆乌鲁木齐830052）

高校排课工作作为教学管理中一个很重要的环节，影响因素较多，是一种典型的组合优化问题。群体智能算法的研究发展，为自动排课问题解决提供了可能。通过分析研究高校排课过程，选用遗传算法设计在线排课系统，并基于PHP+MYSQL平台，利用ThinkPHP框架实现高校在线排课系统。系统经过测试，取得良好效果。有效解决了排课问题。减轻了教务管理人员工作压力，提升了教学服务质量。为相关研究提供一定的借鉴。

在线排课；组合优化；遗传算法；智能排课

随着网络技术和计算机技术的迅猛发展，在线排所需的外部条件以完全具备，很多学者也在智能排课领域进行探索研究。有一定的理论和实践基础。高校排课工作要兼顾多个方面，且人工排课过程中出现的问题越来越多，人工排课耗时长，效率低。且随着扩招政策实施，学生人数，专业开设及开班数量不断增加，排课过程越来越复杂。智能排课问题称为一个研究课题。通过分析和查阅文献，排课过程中的各种影响因素，组合起来其实是一种典型的组合优化问题[1]。目前智能算法的研究为组合优化问题的解决提供了有力的工具。有很多算法都可解决这样的问题。本文通过研究遗传算法[2]，和分析排课过程。提出利用遗传算法设计高校在线排课系统的思路和具体的实现过程。

1 问题的描述

1.1 排课问题说明

排课过程有多约束、多目标的组合优化特点，为了找到问题解决最优解，避免课程安排结果在时间、教室、教师、班级等方面的相互冲突，须有相应的约束条件来实现。而在实际的排课过程中，时间均匀、老师满意度、教室利用率、教室类型相符、教室座位数、班级上课冲突、老师上课冲突等方面，是衡量课程安排是否达到最佳效果的主要依据。

1.2 排课约束条件

排课过程中的约束条件有两类:硬约束和软约束[3-5]。硬性约束条件是一定要满足的条件，直接影响着排课结果的正确性。因此硬性约束条件对于各个高校都是相近的，这些约束条件直接在系统设计时，直接在程序中进行限制，是系统不可修改的部分。一张正确的排课结果应至少满足以下硬约束条件:

1）同一上课时间段内的约束:教师和教授课程是1:1关系；班级和所学课程是1:1关系；教室必须容下上课的学生数，即Ks＜Xr（Ks:教室座位数，Xr:上课学生人数）；教师和使用的教室1:1关系；教室和所排课程1:1关系。

2）所安排的教室类型和课程中制定的类型一致。

……

相对硬性约束而言，软约束条件不具备强制性。在实际教学当中为了教学效果更好，在可能的情况下尽量满足这些软约束条件。因此软约束条件对于各个高校可能是不相同的，这也是排课系统设计的难点，这些约束条件不能直接设计到系统中，需要根据不同高校的情况设计相应的策略。软约束条件策略设定应考虑到以下方面:

1）老师的满意度:尽量在重复利用资源和注意时间分布的情况下，满足老师对排课的需求。

2）学生接受知识的规律:课程的学时安排尽量均匀，不能集中的安排同一课程。

3）生物规律:学生经过一夜休息，上午注意了比较集中尽量安排理论课，下午尽量安排试验或实践性课程。

4）学生的满意度:在重复利用资源和注意时间分布的情况下，晚上和周末尽量不安排课程。

2 遗传算法在排课过程中的应用

2.1 染色体编码

利用遗传算法实现自动排课首要解决的问题是将基础信息（教师，教室，课程，班级，时间）转化成虚拟的编码，也就是转化成染色体，染色体目前设计方法有两种二进制和十进制[6-9]，染色体设计成二进制，虽然有利于杂交和变异，但使用的数据串较长，而且二进制转换较为复杂，本系统设计采用十进制数进行编码形式，如图1所示，例如:教师编码为1002，所教授课程为“C语言程序设计”，课程的编号为1078，在编号为7224的教室上课，上课时间是随机产生，每周上课时间段标示方法设计为:每天分为5个时间段（含晚上的课，正常每天4个时间段），每周7天，每周共35个时间段，从周一第1节标示为01，第5节课标示为05，周二第1节就是06，直到星期日第5节标示为35，共有01～35，35个时间段。假如随机产生三个时间段“02”、“12”、“22”即代表的上课时间为周一第二节，周三第二节，周五第三节，则生成的染色体编码为:“100210787224021222”，之后需要对后10位编码“7224021222”即对教室和3个时间段进行交叉，变异操作，而教师，课程，班级保持不变，从而演化出的染色体编码更加合理。根据染色体编码生成的课程表，进而利用适应度函数进行判断，适应度满足一定的取值范围时，生成的课表才能达到最终要求，标示获得最优解。

图1 染色体编码示意图

2.2 适应度函数概述

在排课系统中，为了满足遗传算法，而把约束条件转化成数字，也就是适应度，我们设置了适应度函数来判断该个体是否满足最优解，适应度函数如下:

value=first_value+award_value-restrain_value

其中value表示为最终适应度，first_value表示为初始化适应度，初始值为100，restrain_value为硬约束条件，当不满足一个硬约束条件时restrain_value就会加10，award_value为软约束条件，当满足一个软约束条件时award_value就会加1，最终得到的value大于或等于100时表示得到一个解，而大于100的值越大表示离最优解越近。

2.3 冲突检测函数概述

在排课系统中，总有一些无法满足条件的数据，因此在遗传算法排课之后，使用冲突检测函数，对那些无法满足条件的数据进行扫描查询最优解，使用改进后的电梯调度算法进行结果选优[11-13]，排课的时间段有周六和周日，为了尽量避免周六和周日，扫描会先记录当前时间段后向周一的第一节进行扫描，为了避免无解，扫描时加入晚上的时间段，如扫描到周一第一节课时还是无解后恢复原点向后扫描，这里加入周六和周日，避免完全无解。

2.4 遗传算法的操作

2.4.1 初始化种群

选中需要排课的班级组成一个集合记做R（nn∈正整数），选中的班级已经完成课程安排，且任课教师已进行选课，课程所需的教室类型已确定，这里课程教室类型记做C，随机生成几个时间段记做为Tn（n∈正整数且n≤5），且任意的时间段Ti满足Ti-5≥0。随机产生的教室号记做cn满足cn∈C，且学生人数≤教室座位数。在本阶段不能满足教师在同一时间内只能教一门课程，这需要其他操作来解决。

2.4.2 选择操作

在排课系统中，每个班级代表一个独立的个体，遗传算法的操作在每个个体内进行，选择操作是每一代只有两条染色体进行操作，默认进行500代遗传，每代按一定的概率出现两条染色体。

2.4.3 遗传操作

遗传操作是将两条染色体进行交换，主要交换的是时间和教室产生新的染色体，将该染色体和父代染色体进行适应度对比，产生不同的适应度。进行适应度选择，适应度较高者被选中，反之被放弃。

2.4.4 变异操作

在遗传操作后新生的两条染色体按一定的概率发生变异，变异主要是针对时间段染色体编码，变异只在原点的上下4个时间段改变，存在排课时间段在晚上的可能性。通过变异操作可以得到更多的解。

2.4.5 自动定位与消除冲突操作

通过自动定位与消除冲突操作，对无法满足条件的数据进行扫描求解，可能求出的解不是想要的结果，但能排除条件苛刻的染色体[14]。

3 系统设计

3.1 系统的设计思路

系统的设计充分利用软件工程的方法，经可行性研究，需求分析、概要设计、详细设计编码测试，交付使用等步骤完成系统的设计和开发。系统总体工作流程如图2所示。

图2 系统的总体工作流程

教务管理人员录入基础信息。系统管理员设定遗传算法排课参数（多次试验得出结论）教师选择本学期所授课程，录入上课条件。系统进行自动排课。排课过程中首先满足硬约束策略。进而满足软约束策略。排课结束生成课表。教务人员根据不同的条件查询需要的课表。

3.2 系统的总体设计

系统的总体设计功能图，如图3所示。

图3 系统总体功能模块图

3.3 系统自动排课

自动排课首先批量选择要排课的班级，利用遗传算法对选中班级进行排课操作。结果产生的是最优解。需将结果转化为课表。方便进行后期的查询和其他操作。遗传算法自动排课流程如图4所示，实现自动排课过程代码中类的调用关系如图5所示。经自动排课操作，没有获得最优解得班级信息，系统自动导出数据，需手动进行简单调整[16]。

图4 遗传算法自动排课流程图

图5 自动排课过程及其类的调用关系

3.4 人工排课

系统设计中考虑到个别特殊情况需要教务人员手动排课。主要对个别班级排课，或对自动排课结果进行局部的修正。在人工排课过程中对于不满足硬约束的情况系统会及时作出提示。

4 系统测试

系统在硬件环境为:内存6G，i7CPU，操作系统为:window7 64位系统。使用有25个教室，20个班级，每个班级7门课，49门课程，20位教师为数据，并为个别教师设计特殊时间约束。并建立排课策略。在代失数、交叉率、变异率不同的情况下测试结果如表1所示。

7个测试都通过了，可以看出，代失数越少，运行速度较快，在相同的环境和代失数下，交叉率和变异率越低，运行速度较快，但得到解越少，通过上述测试发现代失数为50，交叉率为0.2，变异率为0.05时得到了最多解，取得较好效果。但也要根据实际的运行环境，配置较高的计算机可以相对应的增加代失数，同样选择要排课的班级数越多，所用时间越长，建议每次排课选择一定数量的班级。通过5次排课的数据进行分析，发现排出的课程表有一些细节问题，单双周课程划分不到位，针对需要特殊教室的课程排课不理想，排课时应先排需要特殊教室的课程，而针对基础信息的录入较为麻烦，不能一次性导入。

表1 遗传算法代失数、交叉率、变异率与排课效果、用时对照表

5 结 论

通过分析高校在线排课问题，该问题属于典型的组合优化问题。提出利用遗传算法解决排课问题的思路。并采用软件工程的思想通过需求分析、总体设计、详细设计、系统编码测试等环节，基于PHP+MYSQL平台，利用ThinkPHP框架开发MVC模式的高校在线排课系统。系统实现了在线录入课程计划、老师选课、教室信息管理、自动排课、手动排课、系统管理，可设置查询条件如:班级，教室、教师等进行查询并打印生成的课表等功能。系统中采用了RBAC权限控制，实现了不同角色操作人员登录，所拥有不同的权限，提高系统的安全性。系统在PC机上经过测试取得较好效果，取得一定的测试数据。系统的运行缓解了教务管理人员的工作压力，节省了一定的人力物力。但对计算机硬件资源消耗较大，在后期还需要在算法上进行优化，在系统设计方面进行改进。

[1]屈正庚.一种逻辑决策的排课算法[J].电子设计工程，2012（7）:13-15.

[2]叶碧虾.遗传算法在排课系统中的优化研究[J].吉林师范大学学报：自然科学版，2014（2）:134-139.

[3]王璐，杨亚伟.一种改进的遗传算法在年度排课问题中的应用[J].计算机与数字工程，2016（8）:1619-1624.

[4]梁慧娜，周劲桦.基于遗传算法的实训室多重优先排课方法研究[J].微型机与应用，2014（19）:91-93，101.

[5]钱海军，郭泽睿.开放教育排课问题约束分析与数学建模[J].软件工程，2016（9）:26-29.

[6]王瀚韬，李强，郑永康.基于鱼群算法的电梯群控调度算法[J].机电工程，2013（7）:888-892.

[7]严宏.教学资源配置优化中遗传算法的应用与改进[J].计算机技术与发展，2016（3）:130-134，139.

[8]靖靖，杨梅.基于满意度的最优排课方案[J].西南师范大学学报：自然科学版，2016（1）:185-188.

[9]杨彦明，岳翠翠，李其申.军队任职院校排课问题的数学建模[J].计算机与现代化，2012（11）:14-17.

[10]张赫男，张绍文.采用改进的混合遗传算法求解高校排课问题[J].计算机工程与应用，2015（5）:240-246.

[11]余久久.基于探索性测试思想的可复用测试用例设计过程研究[J].计算机技术与发展，2015（9）:187.

[12]谢宗霖，刘亚君，霍伟敬，等.基于整数规划的排课优化问题[J].计算机与现代化，2015（7）:15-19.

[13]张艳红，王玲玲，腾东兴.基于空间模型和遗传算法的高校排课系统[J].计算机系统应用，2015（9）:49-55.

[14]杨博凯，李晓瑜，黄一鸣，等.基于遗传算法的高考志愿填报排序问题的研究[J].计算机科学，2016（S1）:390-394.

[15]樊伟宏，刘文，孙士鹤，等.基于B/S模式的高校试卷档案管理系统设计[J].软件导刊，2015（9）:134-136.

[16]杨彬彬.继续教育学院综合管理系统的设计与实现[D].成都：电子科技大学，2014.

Design and implementation of online course scheduling system based on genetic algorithm in colleges and universities

FAN Wei-hong1，YANG Wen-ting2，WANG Hao1，LIU Wen1
（1.Academy of Science and Technology of Xinjiang Agricultural University，Urumqi830052，China；2.Department of Ideological and Theoretical Teaching Research of Xinjiang Agricultural University，Urumqi830052，China）

As a very important part of the teaching management，the course arrangement of the university is a kind of typical combinatorial optimization problem，which has many affecting factors.The research and development of swarm intelligence algorithm provides the possibility to solve the problem of automatic course scheduling.Through the analysis of the course scheduling process，the genetic algorithm is used to design online course scheduling system，based on the PHP+MYSQL platform，use framework of ThinkPHP to achieve online course scheduling system.The system has been tested，and good results have been achieved.Effectively it solves the problem of course arrangement.The work pressure of the educational administration staff is reduced，and the teaching service quality is improved，which provides some reference for the related research.

online course arrangement；combination optimization；genetic algorithm；intelligentized course arrangement

TN302

A

1674-6236（2017）23-0019-05

2016-11-22稿件编号：201611178

新疆农业大学科学技术学院青年科研启动基金项目（2016KJKY007）；新疆维吾尔自治区高校科研计划（XJEDU2016I049）

樊伟宏（1985—），男，陕西洛南人，助教。研究方向:计算机技术、数据分析。