﻿ 基于遗传-蚁群混合算法的排课系统
 计算机系统应用  2019, Vol. 28 Issue (2): 81-86 PDF

Course Schedule System Based on Genetic-Ant Colony Hybrid Algorithm
SUN Yi, HU Ju-Hui
College of Communication and Information Engineering, Xi’an University of Science and Technology, Xi’an 710054, China
Abstract: In the administrative management of colleges and universities, the scheduling is a complex and critical task. The number of subjects and the limited teaching resources all restrict the complexity and results of class scheduling. The essence of class scheduling is to arrange the course and class to the appropriate teaching location at the appropriate time. It is a solution to the NP problem. As the scale continues expanding, the difficulty of solving problems increases exponentially. When the scale reaches a certain level, it is difficult to find the optimal solution in a short time. In view of this, this study proposes a genetic-ant colony hybrid algorithm, which uses a mixture of two algorithms, relies on genetic algorithm to generate pheromone distribution, and uses ant colony algorithm to find the optimal solution. The experimental results show that the hybrid algorithm improves the efficiency of class scheduling and the rationality of the class schedule.
Key words: course arranging     NP problem     genetic algorithm     colony algorithm     hybrid algorithm

1 排课问题的分析

1.1 硬约束条件

(1) 同一个教师在同一时间段内只能够上一门课, 并且教室的性质要和课程要求相吻合;

(2) 同一个班级在同一时间段内只能够接受一门课;

(3) 一门课程安排的教室座位数量要大于或等于本门课程上课的人数.

1.2 软约束条件

(1) 尽量将专业课或者难度较大的课程安排在学生思维活跃的时间段;

(2) 体育课应安排在下午或者上午的第二大节, 因为体育课后人体疲惫不适宜安排专业性过强的课程.

2 算法概述 2.1 遗传算法

(1) 随机产生一定数量的初始种群, 数量由业务需求定义.

(2) 对全部个体进行适应度的评估, 如果某个个体的适应度已经满足最优化的要求, 则输出此个体, 并结束计算. 否则转向第(3)步.

(3) 从所有个体中取出适应度较强的个体成为再生个体.

(4) 依据交叉概率, 变异概率生成新的个体.

(5) 由上述两步交叉和变异产生新一代种群, 然后返回第(2)步.

2.2 蚁群算法

2.3 遗传-蚁群混合算法

3 遗传-蚁群混合算法解决排课问题 3.1 遗传算法在排课问题中的应用 3.1.1 构造基因编码和染色体

3.1.2 适应度函数

(1) 课程离散程度期望

 ${F_{cs}} = \sum {{F_{cs}}\left( i \right)}$ (1)

(2) 节次优化度期望值

 ${F_{so}} = \sum {{F_{s{\rm{o}}}}\left( i \right)}$ (2)

(3) 特殊课程的期望值

 ${F_t}\left( i \right) = \sum {{F_t}\left( i \right)}$ (3)

 ${F_{{\rm{ts}}}} = \sum {\left( {{F_t}\left( i \right) + {F_z}\left( i \right)} \right)}$ (4)

 $F = \frac{{{K_1} \times {F_{cs}} + {K_2} \times {F_{{\rm{so}}}}{\rm{ + }}{{\rm{K}}_3} \times {F_{ts}}}}{3}$ (5)

3.1.3 种群操作

(1) 选择操作

(2) 交叉操作

(3) 变异操作

3.2 蚁群算法在排课问题中的应用

m为蚁群中的蚂蚁数量; n为问题的规模大小(有食物地方的个数); ${{{b}}_i}\left( t \right)$ t时刻位于i地区的蚂蚁数量, 故蚂蚁数量为:

 ${{m}} = \sum\limits_{i = 1}^n {{{{b}}_i}\left( t \right)}$ (6)

 {{p}}_{{{ij}}}^k\left( t \right) = \left\{ {\begin{aligned} & {\dfrac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\mu _{ij}}\left( t \right)} \right]}^\beta }}}{{\sum\nolimits_{s \in allowe{d_k}} {{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\mu _{ij}}\left( t \right)} \right]}^\beta }} }},\;\;{\text{若}}\;{{j}} \in allowe{d_k}}\\ & {0,\;\;{\text{否则}}} \end{aligned}} \right. (7)

 ${\tau _{ij}}\left( {t + n} \right) = \left( {1 - p} \right) \times {\tau _{ij}}\left( t \right) + \Delta {\tau _{ij}}\left( t \right)$ (8)
 $\Delta {\tau _{ij}}\left( t \right) = \sum\limits_{k = 1}^{{m}} {\Delta \tau _{ij}^k\left( t \right)}$ (9)
 \Delta \tau _{{\rm{ij}}}^k\left( t \right) = \left\{ {\begin{aligned} & {{Q / {{L_k}}}} \\ & 0 \end{aligned}} \right. (10)

3.2.1 蚁群算法的二分图模型

 $G=(N,S,C)$

(1) 二分图的顶点集定义

(2) 二分图的边集定义

(3) 二分图中边的权值

3.2.2 二分图模型

 图 1 二分图模型

A1→(B1→A2)→(B4→A3)→B5

3.3 遗传-蚁群混合算法在排课问题中的应用

3.4 实验结果及分析

 图 2 遗传-蚁群混合算法流程图

(1) 实验参数设置

(2) 排课效果的比较

(3) 实验结果分析

4 结论

 [1] 薛冬梅. 充分利用资源 科学合理排课. 中原工学院学报, 2002, 13(S1): 97-98. [2] 杜立智, 陈和平, 符海东. NP完全问题研究及前景剖析. 武汉工程大学学报, 2015, 37(10): 73-78. [3] 朱剑冰, 李战怀, 赵娜. 基于混合遗传算法的自动组卷问题的研究. 计算机仿真, 2009, 26(5): 328-331, 352. DOI:10.3969/j.issn.1006-9348.2009.05.084 [4] 许秀林, 胡克瑾. 基于约束满足和遗传算法的排课算法. 计算机工程, 2010, 36(14): 281-284. DOI:10.3969/j.issn.1000-3428.2010.14.102 [5] 李俊, 周虎, 李波. 基于虚拟蚂蚁的局部优化蚁群算法. 控制与决策, 1–10. [6] 史文. 基于遗传算法的自动排课系统设计与实现[硕士学位论文]. 成都: 电子科技大学, 2013. [7] 宗薇. 高校智能排课系统算法的研究与实现. 计算机仿真, 2011, 28(12): 389-392. DOI:10.3969/j.issn.1006-9348.2011.12.095