遗传算法在多校区排课系统中的研究和应用

凌敏

摘 要 本文分析了造成多校区高校排课困难的各种因素，研究了如何应用遗传算法来解决多校区高校排课困难的问题，并对该算法进行详细设计，给出了一个基于该算法的排课模型。

关键词 遗传算法 排课系统 教务管理

中图分类号：G71 文献标识码：A

排课问题是一个多约束、多目标的优化问题，是教务管理工作的一个重点和难点。尤其是多校区同时运行的高校格局增加了更多的约束条件，问题的复杂度也增加了许多。多校区排课是一个典型的多因素的优化决策问题，是组合规划中的NP完全类问题，涉及信息较多且求解复杂性为课表规模的指数量级。遗传算法被证明解决该类问题是最合适的。

1排课问题描述

课表要有利于教学设备的充分利用，要符合教学规律。将这个原则进行细化、清晰化，一般可以归纳为以下具体要求。

（1）课表中没有硬性冲突，在排课过程中必须遵守如下约束条件：

①每位教师在同一时间段内只能安排一门课程；

②一个教室在某一时间只能安排一门课；

③教室的位置数量与每个自然班的人数应尽量匹配；

④必须根据核定的教学计划所规定的学时数排课，不得任意增减；

⑤一个教师两节课间路程不超过10分钟，半天的工作必须安排在同一个校区。

（2）课表要求有较高质量，为了使排出的课表更优化、合理、排课还应考虑以下因素：

①一门课程在每个班的每两天只能安排一次；

②专业必修课尽量安排在上午；

③同一门课的上课地点尽量安排在同一教室；

④体育课必须排在下午或者上午3-4节，体育课后避免安排讲授课；

⑤实验、操作、训练、演示等课应排在下午；

⑥满足个别教师的特殊上课时间要求；

⑦编排课表时，先排公共课，后排专业课；先排合班课，后排单班课；

先排多头课（一个教师有多门课），后排独头课；先排多时课，后排少时课。

2排课问题的遗传算法设计

首先，人工安排或计算机根据条件自动生成，集中安排实验、实习、社会实践等有固定时间和地点的课程。

其次，剩余课程按照院系为单位分为若干个子块，用遗传算法对每个子块进行排课操作。

2.1染色体编码

遗传算法中首要考虑的是如何表现问题，即如何对其进行染色体编码，使之适用于GA操作。一条染色体中应包含课程、老师、教室、学生、时间和校区等相关信息。但由于某一门课程信息里面已经包含了老师、学生和校区信息，故染色体中仅需要对课程、教室和节次采用可拼接的二进制编码。若某院系一学期有40门课程，可编为X1=（a1，a2，a3，a4，a5，a6），ai∈{0，1}。每个院系一般有20 个教室不等，可编为X2=（b1，b2，b3，b4，b5），bi∈{0，1}。每周上五天课，每天4次，共20次，可编为X3=（c1，c2，c3，c4，c5……，c19，c20），ci∈{0，1}。所有课程的DNA分子拼接形成一条染色体。

2.2初始化群体

群体初始化的规模数n应取适中。一般，n取值为染色体长度的两倍左右。根据上述的染色体编码，一个DNA分子长度为31，40门课程的一个染色体码长为1240，故n可取2480。每条染色体中的DNA分子之间由于教室、时间、学生、老师、校区等因素会产生冲突，比如一个老师不能在同一时间安排两门或两门以上的课程。产生初始群体时，在不产生冲突的情况下（满足上述5条硬约束条件），随机为基因块赋0或1，直到满足群体规模。

2.3适应度函数设计

遗传算法根据适应度群体中个体的优良程度，适应度较高的个体遗传到下一代的概率较大。因此，遗传算法是在适应度函数的引导下运行的，适应度函数选择的好坏直接影响算法的优劣。在适应度函数设计中，我们主要考虑以下冲突；

（1）教师冲突，教师安排是否冲突，同一时间段是否安排两次课。

（2）教室冲突，同一教室同一时间段不能安排两门课。

（3）班级冲突，同一班级同一时间的段不能安排两门课。

（4）交通冲突：对于多校区或单校区教学楼分散情况，教师或学生相邻时的教室间距不应超过10分钟；

（5）教室大小与学生人数的冲突。

以上约束条件Pi∈{0，1}，0表示有冲突，1表示没有冲突首先对一条染色体中的每个DNA分子（一门课程）计算适应度，然后计算一条染色体所有DNA分子适应度之和，将该值作为个体适应度，数学表达式如下：

fi=（P1譖2譖3譖4譖5？f譗1+j譗2+h譗3）

F=40i=1 %Lfi

f表示节次优先度，j表示课程类别优先度，h表示组合优先度。Q1、Q2、Q3代表相应权值，F为个体适应度。

2.4选择算子

采用截断选择法，染色体按适应度函数值从高到低排序，只有最优秀的个体才能被选作父个体。其中，用于决定染色体被选作父个体的百分比的参数称为截断阀值，范围取90%～80%。在该阀值之外的个体不能产生子个体。

2.5交叉算子

交叉只对复制产生的85%的个体进行，此时适当的选择交换概率p，p过大或过小都不易收敛到最优解，设p为0.95（保留的15%不参加交换）。采用一点交换方式，在排课问题中，每周某一课程上课节次是固定的，随机选择第n个DNA分子时间节次码中第m个基因位为1的基因。

2.6变异算子

排课系统中由于课表合法性问题，如果采用简单的随机变异，会出现大量的冲突，导致需要消耗大量精力去纠错。因此，我们在研究中采用有条件的基因变异。变异操作的作用是防止丢失有用的可能解，保证搜索到空间的重要点，使算法具有全局收敛性，变异的概率较小，在本文中取0.01。和交叉算子一样仅是时间节次码参与交换，教室和课程码保持不变。选择两个点进行变异，具体操作是：随机选择第n个DNA分子，再随机选DNA分子中的时间码第p、q个点进行变异。

2.7终止条件

采用迭代次数来决定，取2500。

参考文献

[1] 肖俊.遗传算法的工程应用[J].计算机科学，2005，11（32）：247-250