基于蚁群算法的高校排课系统设计

黄阿新

（漳州科技职业学院，福建 漳州 363202）

随着高等教育的改革发展，高校专业建设加快、培养模式多元化、学生规模扩大。同时，课程也在拓宽，但是高校的教室、公共机房、专业实训室等硬件条件却无法满足，从而产生了一个非常突出的问题。因此，将高校有限的资源进行合理的配置是当前迫切需要解决的难题。

高校日常教学工作的顺利开展，取决于一份科学、合理、规范的课程表，它可以提高教学质量。传统的排课模式无法满足实际需求，因教室数量有限、师生配比不足导致每一位老师要承担较多的教学任务，从而导致排课难度越来越大[1]。

一、排课问题

高校排课问题归纳起来就是对教师、班级、课程、教室、时间等资源的优化配置，每学期的排课都是排课人员非常头痛的事情，即使他们多么的努力，还是无法满足所有人员的需求。

为了使资源的配置尽可能优化，必须满足以下两个条件：

（一）硬性条件：

1.一个时间点，学生只能去上一门课，不可能同时上两门课；

2.一个时间点，教师只能讲一门课，不可能同时教多门课；

3.一个时间点，教室只能安排一门合适的课程；

4.给学生安排的教室，必须考虑每一个学生都有座位；

5.体育课之后学生体力透支，不再安排其他课程；

6.前两节课与后两节课不能安排学生在距离较远的教室；

7.根据课程性质安排教室类型。

（二）软性条件：

1.尽量满足教师集中上课，但一天的课程最好不超过8节课；

2.学生的课程尽量安排在白天，并且课程要安排均匀；

3.教师和学生的两次上课地点不宜太远；

4.同一个班级相同课程的多次课要有时间间隔；

5.较为难理解的课程尽量安排在上午[2]。

二、蚁群算法

（一）蚁群算法描述

蚁群算法是机率型算法，旨在寻找优化路径。1992年，学者就提出一种模拟优化算法，模拟蚁群寻找食物，求出从某一点开始，经过若干个地址，最后返回出发点的最短路径[3]。

早期的蚁群算法是解决TSP（旅行商问题），许多问题都可以像旅行商问题一样求解，随着研究的不断深入，现在该算法已经用于生活的方方面面[4]。

（二）基本原理

当蚂蚁移动时，会释放一种叫做信息素的物质，释放的信息素会随着它爬行距离越来越远而减少。另外，信息素浓度是蚂蚁选择路径的依据，而信息素本身就是易挥发的[5]。蚂蚁的移动可以简单归纳为：

1.当蚂蚁没有发现信息素时，它的移动是随机的，而且具有创新性，当遇到障碍时马上会选择新的路径移动；

2.当蚂蚁发现信息素时，它的移动根据信息素浓度进行选择，浓度越强越容易被选上；

3.蚂蚁可以释放两种以上的信息素，“食物”信息素和“家”信息素，然而随着爬行距离越来越远，释放的信息素会越来越少[6]；

4.信息素具有挥发性。

（三）建蚁群算法的数学模型

蚂蚁a从城市i走到城市j的过程中都会释放信息素，并且蚂蚁选择下一个城市的依据是一个概率公式，表示如下：

dij指的是两个城市之间的距离；τij指的是城市i到城市j的路径上的信息素的量；τij（t）指的是t时刻两个城市间残留的信息素，α和β是启发式因子；ηij（t）指的是t时刻两个城市间路径（i，j）上的启发信息素，ηij（t）=1/dij。

tabua指的是蚂蚁a的禁忌列表，为了避免蚂蚁a多次进入同一个城市，当蚂蚁a进入城市j之后，j就被列入禁忌列表里；Paij（t）指的是蚂蚁a从城市i走到城市j的概率。

当所有的蚂蚁完成一次路径循环后，才更新信息素。因此，路径上的信息素分为两部分：未挥发所残留的信息素和经过当前循环所有蚂蚁在经过该路径后所留下的信息素。用公式表述如下：

ρ指的是信息素挥发因子，ρ∈[0,1)；△τij(t)指的是t时刻路径（i,j）上增加的信息素；△ταij(t)指的是t时刻蚂蚁a在路径（i,j）上增加的信息素；Q指的是蚂蚁释放的信息素量；Lα指的是蚂蚁a经过所有城市的总路径长度。

三、蚁群算法在排课系统中的应用ρ

将排课问题空间通过另外一种方式进行描述，采用图形结构，就能使得排课系统模型嵌入蚁群算法，这种图结构即二分图[7]，如图1所示。一般情况，<教师,课程,班级>和<教室,时间>的笛卡尔积即为排课问题解空间，其中，C表示课程、教师和班级所构成的排课结点，T表示可用的时间、教室的结点集合[8]。

图1 二分图

蚁群算法在排课系统的应用流程图，如图2所示。

图2 蚁群算法流程图

蚁群算法在排课问题的解决当中，优点很突出，具有正反馈性、通用性、启发性、并行性等特点。刚开始蚁群算法信息素生成较慢，影响到搜索能力，然而随着信息素的增加，搜索能力越强，能很快搜索到最优解。很多的研究都发现，蚁群算法很容易发现最优解，它是一种特殊的强化算法。

四、排课管理系统的设计

（一）需求分析

高校排课系统四大功能，分别为：

1.系统管理：按照同一类型的用户进行权限组管理，权限管理关系到整个系统的安全。

2.教学资源：设置班级、教师、教室、课程、时间片段等基本信息，从而进行系统排课，管理员对设置的基本信息进行维护。

3.教学计划：根据各专业人才培养方案，设置所开设的课程；

4.课表编排：该功能是使各因素获得最优的组合，实现自动排课。

（二）系统功能模块设计

该排课系统共开发四个模块，其排课系统功能结构图如图3所示。

图3 排课系统功能结构图

（三）数据库设计

1.教师表，主要是对教师信息的增、查、删、改。如表1所示。

表1 教师表

2.班级表，主要是对班级信息的增、查、删、改。如表2所示。

表2 班级表

3.课程表，主要是对课程信息的增、查、删、改。如表3所示。

表3 课程表

4.教室表，主要是对教师信息的增、查、删、改。如表4所示。

表4 教室表

5.排课表，系统根据排课要求排出新学期课程表，也可以作手动辅助修改。如表5所示。

表5 排课表

五、结语

排课问题实质上是一个组合优化问题，其复杂度较高。本排课系统采用B/S结构，前端使用Client/Server、SOA等技术，后端使用SSH框架技术。基于计算机网络，实现了高校教务管理和排课管理的功能需求分析。运用蚁群算法设计的排课系统，能够满足各方面因素，找出最优解，大大提高了排课效率，使高校教学资源得到合理的配置。