改进蚁群算法在大学排课问题中的研究与应用

随着大学招生规模的扩大, 大学排课问题 (University Timetable Problem, UTP) 越来越受关注。学生数量的大幅增长和教育资源的相对稀缺, 使得大学课程表的编排成了各高校教务处每年最棘手和最费时的工作之一。UTP属于时间表问题, 它需要为学校或各学院设置的课程结合学校的硬件配置安排一组适当的 (当然最好是最优的) 教学时间和教学空间, 使得整个教学能够有序的进行。排出高质量的课表有利于教学活动的和谐开展, 有利于教师教学效果的充分优化, 有利于学生学习效果的大幅提高。

排课问题早在70年代就证明是一个NP完全问题, 即排课算法的计算时间是呈指数增长的。排课问题很早以前就成为众多科研人员的研究课题, 其中算法的选择是最关键的一个问题, 众多研究者提出了多种排课算法, 如遗传算法、专家系统、二分图及着色理论、模拟退火算法及蚁群算法等。其中, 蚁群算法是很有效的求解最优解的算法。然而传统蚁群算法在处理排课问题时易陷入局部最优解, 从而影响求解质量。本文结合江南大学排课问题的自身特点提出一种适于排课问题的改进蚁群算法。实验结果表明改进后的算法可以明显改善排课问题的求解速度, 提高解的质量。

1 蚁群算法

蚂蚁在寻食过程中总能找到一条食源和栖息地之间的最短路径, 研究发现蚂蚁之间是通过一种体外激素来相互传递信息, 从而相互协作, 完成复杂的任务。蚁群算法正是仿照蚁群的集体行为而构造的一种智能算法。蚁群算法由意大利学者Macro Dorigo首先提出[1], 并成功的用于解决旅行商问题 (TSP) 、作业调度问题 (JOP) 等组合优化问题, 取得了较好的实验数据。

为了便于说明, 我们将结合具有N (0, 1, …N-1表示城市代号) 个城市的TSP问题来说明蚁群算法。dij (i, j=0, 1, 2, …N-1) 表示城市i与j之间的距离, τij (t) 表示t时刻边i与j之间的信息量, τij (0) =C (C为常数) 表示各边信息量初始值为一常数, 蚁群共有n只蚂蚁。pki j (t) 表示第k只蚂蚁在t时刻由i转移到j的概率,

其中allowedk表示蚂蚁k还没有访问过的城市。α表示路径上的信息量对蚂蚁选择路径所起的影响程度, ηi j表示有城市i转移到j的期望程度, β表示ηi j对蚂蚁选择路径的影响程度。一般可取ηi j=1/dij。各蚂蚁将依据: (1) 式进行搜索前进。经过N个时刻后当所有蚂蚁走遍了所有城市, 将依据 (2) 式对各条路径上的信息量进行信息更新。

其中ρ∈ (0, 1) 表示路径上信息量的损耗程度, △τij表示在一次遍历结束后路径i到j的信息增量。

∆τikj表示第k只蚂蚁在路径ij上留下的信息量, 根据不同的蚁群算法其取值不同, 在ant system中其取值如 (4) 所示。Lk表示第k只蚂蚁本次遍历所走路程长度, Q为常数。最后可以根据适当条件来终止迭代运算, 求得解。

2 排课问题

编排课表的整个过程充满着矛盾运动的过程, 即所开课程、上课班级、任课教师、上课时间、上课地点这五个方面在排列组合中所发生的冲突和矛盾现象。在排课中除需要考虑跨校区、教师、学生、课程、场地、时间等制约因素外, 还必须解决多种矛盾冲突。本文采用学分制选课的方式组成教学班上课, 传统的按班级上课不在考虑之列。要科学合理地编排高校课表必须解决的问题如下: (1) 编排好的课表教师、教室不能冲突; (2) 要合理利用现有资源; (3) 排课顺序必须科学和合理。

3 改进蚁群算法在排课问题中的应用

3.1 课表问题的数学表示

课表的编排是给教学班分配时间和教室。课表编排最重要的是使时间、课程、教师、教室不发生冲突。可见, 在排课问题中存在四个因素, 设

课程集合:L={L1, L2, L3, …, L nl}

教师集合:T={T1, T2, T3, …, T n t}

排课之前, 先落实教学任务书, 排课之前就明确<课程一教师>的关系, 在这把落实好任务的<课程一教师>的关系用一个课号G来表示, 同一门课程同一个老师上不同的教学班就用顺序号来区分。

时间集合:P={P1, P2, P3, …, P n p}

Pi表示可排课的第i个时间段, 每天分5个时间段, 每周就分25个时间段, 如P1表示周一上午1～2节, P25表示周五晚10～12节。

教室集合:R={R1, R2, R3, …, R n r}

因每个教学时间段、每个教室都可以安排课程, 所以<时间-教室>可以看成是P×R的满映射。

排课问题可表示为映射:f:G→P×R。即为每个课号G寻找一个合适的时间和教室, 其中G是实体, 与课程、教师实体有关, P×R表示时间和教室的笛卡尔积。

3.2 课表问题的二部图模型

从对排课问题的数学描述看, 为了将蚁群算法应用到排课问题中, 排课问题可以转化为二部图的匹配问题。所谓二部图, 就是对于一个无向图, 顶点集可分割成两个互不相交的子集, 并且图中每条边依附的两个顶点都分属这两个不同的子集。

如 (图1) 所示, 任何属于GLT集合的两个顶点之间是独立的, 同样, 任何属于GPR集合的两个顶点之间也是独立的。连接所要求的所有左右顶点形成边集, 再为所有边设置合适的权值。这样, 二部图模型一旦确定, 就可以使用蚁群算法帮助解决此排课问题了。

排课的目的是将课号安排在一周内相应的时间和教室内且不发生冲突。可见, 排课的实质就是要在GPR中为属于GLT的每个顶点寻找一个合适的顶点进行匹配, 而且必须保证两部分顶点的映射是一对一的关系 (如图2- (1) ) , 否则就会出现教室冲突 (如图2- (2) 中和两门课在同一时间使用同一间教室) 。由此, 排课问题转化为二部图的最大匹配问题, 而蚁群算法可以用来完成这种匹配工作。

3.3 改进蚁群算法在排课问题中的应用

3.3.1 改进的蚁群算法

针对传统蚁群算法在处理大学排课问题时存在的不足, 提出了一种改进蚁群算法, 该算法的主要思想是:通过引入具有多行为的混合蚂蚁来扩大搜索解空间, 避免局部最优解、早熟和停滞现象。

混合蚂蚁是一种具有多行为的蚂蚁, 它包括如下二种类型的蚂蚁行为:

行为1:蚂蚁具有信息感知能力, 其搜索前进策略是在尚未走过的路径上选择信息量大的路径前进, 在走完全部路径后对所走路径进行一次全局信息更新, 此蚂蚁称为智能蚂蚁。

对于智能蚁群, 其搜索前进策略及信息更新策略与基本蚁群算法是一致的, 公式如 (1) , (2) , (3) , (4) 所示。

行为2:蚂蚁不具有信息感知能力, 其将随机选择一个本次遍历中尚未走过的路径前进, 以保证算法搜索更大的解空间, 此蚂蚁称为随机蚂蚁。

对于随机蚁群, 其搜索前进策略是在尚未走过的路径中随机的选择一条路径前进, 而不考虑任何的启发信息, 其前进策略如 (5) 所示:

随机蚂蚁的信息更新策略与智能蚂蚁一致。

混合蚂蚁以σ1概率成为智能蚂蚁, 以σ2概率成为随机蚂蚁 (其中σ1+σ2=1) 。

3.3.2 改进蚁群算法在排课问题中的应用

(1) 初始化。

算法在初始设置时, 设共有m只混合蚂蚁, n个课号, σ1=1, σ2=0, 各路径信息量初始值设为常量。

(2) 迭代过程。

While not结束条件

d o

{将各蚂蚁随机置<时间一教室>GPR;

for s=1 to n do

fo r k=1 t o m do

(1) 如果是智能蚂蚁。

依据 (1) 式选择下一个<时间-教室>GPR访问;

将所选<时间-教室>GPR置为访问过;

更新所走路径长度;

(2) 如果是随机蚂蚁。

依据 (5) 式选择下一个<时间-教室>G P R;

将所选<时间-教室>GPR置为访问过;

更新所走路径长度;

End for k

End for s

依据 (2) 式对所有路径进行全局信息更新;

If (出现停滞状态) //引入随机蚂蚁来扩大解搜索空间, 避免早熟和停滞现象

σ1=0.6;

σ2=0.4;

else//可通过调整num来控制算法的收敛速度

σ1=σ1+num;

σ2=σ2-num;

endif

}

(3) 输出最短路径, 找到最合适的<时间一教室>GPR, 终止整个程序。

该改进蚁群算法己在我校课表编排中得到应用, 我校的教学资源有普通教室183个, 多媒体教室136个, 机房计算机数610台, 语音室21个, 制图室5个, 各类实验室若干。在校学生班级数705个, 任课教师1050人。从应用本算法编排结果看, 排课时间短, 效率高, 且生成的课表质量有一定提高, 冲突现象明显减少。

4 结语

针对传统蚁群算法在处理排课问题时易陷入局部最优解的不足, 提出了一种改进蚁群算法, 该算法实际应用效果良好, 较好的提高了我校课表编排的质量及教务管理人员的工作效率。

摘要：针对传统蚁群算法在处理大学排课问题时易陷入局部最优的不足, 提出了一种改进蚁群算法, 该算法通过引入具有混合行为的蚂蚁来扩大解搜索空间, 避免早熟和停滞现象。实验结果表明, 改进后的算法可以明显改善排课问题的求解质量。

关键词：大学排课问题,蚁群算法,混合行为,二部图

参考文献

[1] M.Dorigo, V.Maniezzo, A.Colorni.The Ant system:Optimization by a colony of coorperating agents[J].IEEE Trans-actions on Systems, Man, and Cyber-netics-Part B, 1996, 26 (1) :29～41.

[2] 赵惠怡, 傅英亮.基于蚁群算法的排课问题的研究[D].大连海事大学, 2007.

[3] 张献.蚁群算法在排课问题中的应用研究[J].长春大学学报, 2007, 17 (5) :80～82.