论文导读：多校区排课是一个典型的多因素的优化决策问题，是组合规划中的NP完全类问题，涉及信息较多且求解复杂性为课表规模的指数量级。遗传算法被证明解决该类问题是最合适的。采用截断选择法，染色体按适应度函数值从高到低排序，只有最优秀的个体才能被选作父个体。
关键词：遗传算法，多校区排课，适应度函数
排课是教务管理工作的一个重点和难点。排课涉及教师、学生人数、教室容量、教室类型、教室间距等诸多因素。尤其是多校区同时运行的高校格局增加了更多的约束条件，问题的复杂度也增加了许多。多校区排课是一个典型的多因素的优化决策问题，是组合规划中的NP完全类问题，涉及信息较多且求解复杂性为课表规模的指数量级。遗传算法被证明解决该类问题是最合适的。
一、排课问题描述
编排课表的整个过程中充满了矛盾运动，其中包括上课班级、所开课程、任课教师、上课时间、上课地点等方面在排列组合中所发生的冲突和矛盾现象。课表的编排必须精心组织，准确无误，科学合理，充分发挥时间、空间、人力、物力，以保证教学过程的正常运转。课表要有利于教学设备的充分利用，要符合教学规律。将这个原则进行细化、清晰化，一般可以归纳为以下具体要求。
课表中没有硬性冲突，在排课过程中必须遵守如下约束条件：
1. 每位教师在同一时间段内只能安排一门课程
2. 一个教室在某一时间只能安排一门课
3. 教室的位置数量与每个自然班的人数应尽量匹配
4. 必须根据核定的教学计划所规定的学时数排课，不得任意增减
5. 一个教师两节课间路程不超过10分钟，半天的工作必须安排在同一个校区
课表要求有较高质量，为了使排出的课表更优化、合理、排课还应考虑以下因素：
1. 一门课程在每个班的每两天只能安排一次
2. 专业必修课尽量安排在上午
3. 同一门课的上课地点尽量安排在同一教室
4. 体育课必须排在下午或者上午3-4节，体育课后避免安排讲授课
5. 实验、操作、训练、演示等课应排在下午
6. 满足个别教师的特殊上课时间要求
7. 编排课表时，先排公共课，后排专业课；先排合班课，后排单班课；先排多头课（一个教师有多门课），后排独头课；先排多时课，后排少时课。
二、排课问题的遗传算法设计
根据高校现状，许多院系都有各自独立的教学楼，且实验、体育课等应有固定的教学场所，为此可以利用遗传算法固有的并行性将排课问题分为若干个子问题。
首先，人工安排或计算机根据条件自动生成，集中安排实验、实习、社会实践等有固定
时间和地点的课程。
其次，剩余课程按照院系为单位分为若干个子块，用遗传算法对每个子块进行排课操作。
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适应度函数设计
遗传算法根据适应度群体中个体的优良程度，适应度较高的个体遗传到下一代的概率较大。因此，遗传算法是在适应度函数的引导下运行的，适应度函数选择的好坏直接影响算法的优劣。在适应度函数设计中，我们主要考虑以下冲突；
P1：教师冲突，教师安排是否冲突，同一时间段是否安排两次课。
P2：教室冲突，同一教室同一时间段不能安排两门课。
P3：班级冲突，同一班级同一时间的段不能安排两门课。
P4：交通冲突：对于多校区或单校区教学楼分散情况，教师或学生相邻时的教室间距不应超过10分钟；
P5：教室大小与学生人数的冲突。
以上约束条件Pi∈{0,1},0表示有冲突,1表示没有冲突
首先对一条染色体中的每个DNA分子（一门课程）计算适应度，然后计算一条染色体所有DNA分子适应度之和，将该值作为个体适应度，数学表达式如下：
fi=(P1×P2×P3×P4×P5×(f×Q1+j×Q2+h×Q3)
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个点进行变异。具体操作时：
 个体A ……00000000……
新个体A ……10000000……
2.7终止条件
采用迭代次数来决定，取2500。
三、结论
本文提出的利用遗传算法解决多校区排课问题的方案，很好地解决了多约束下的排课问题。该方法具有很大的现实意义，对遗传算法求解组合优化问题也有一定的借鉴作用。
【参考文献】
[1]肖俊.遗传算法的工程应用[J].计算机科学，2005，11（32）：247~250
[2]徐宗本，张讲社，郑亚林.计算智能中的仿生学—理论和算法[M].科学出版社，2003
[3]业宁,梁作鹏,董逸生.一种基于遗传算法的TTP问题求解算法.东南大学学报.2003(1)：41-44
|
