（1）初始化[Initialize]
初始化的目的在于为后面的遗传操作提供初始种群。
在我们的算法中，由于每次对一位教师进行遗传操作，初始化时就需要考虑到教室及时间的设定，这其中包括教室可容人数的最优逼近（即避免一个30人的班级占用可容200人的教室这种情况），以及上课时间安排的合理性，这在排课问题描述中已有解释。
（2）选择[Select]
选择运算用于模拟生物界去劣存优的自然选择现象。它从旧种群中选择出适应度高的某种染色体，放入配对集合中，为染色体交叉和变异运算产生新种群做准备。适应度越高的染色体被选择的可能性越大，
选择操作的方法有许多，如轮盘赌选择法（roulette wheel selection），局部选择法（local selection），锦标赛选择法（tournament selection）等。
研究中，我们选用了局部选择法中的一种：截断选择法（truncation selection）。
在截断选择法中，染色体按适应度函数值由高到低排序，只有最优秀的个体才能被选作父个体。其中，用于决定染色体被选作父个体的百分比的参数称为截断阀值Trunc，其取值范围为50%~10%。在该阀值之外的个体不能产生子个体。算法中选择强度与截断阀值的关系如表1所示。
表1 选择强度与截断阀值的关系[5]
|
截断阀值 |
1% 10% 20% 40% 50% |
80% |
|
选择强度 |
2.66 1.76 1.2 0.97 0.8 |
0.34 |
其中选择强度是将正规高斯分布应用于选择方法，期望平均适应度。
选择强度表示为：
SelIntTrunc(Trunc) = 
式中fc为下列高斯分布的积分下限：
Trunc = 
（3）交叉[Crossover]
交叉是根据选择操作的结果，选取两条染色体作为父个体，再取一随机值（设为r）与系统预设的交叉率值（设为t）比较，若r<t则进行交换基因。
（4）变异[Mutate]
变异是随机改变染色体中任一授课时段，将时段随机抽取一点在设定范围内改变。变异运算模仿了生物在自然遗传环境中由于各种偶然因素引起的基因突变，通过变异，染色体适应度有可能加强也有可能降低，但它确保了种群中遗传基因类型的多样性，使搜索能在尽可能大的空间中进行，获得最优解的可能性大大加强。
变异操作与交叉操作类似，即定义一个变异概率pm，在变异时先产生一个随机数r，当r<pm时，执行变异操作，否则不执行。
例如：有一染色体编码为：“0872’01211’1005’04201’ 2122”，它表示星期二的第一、二教学单元节有编号为“1005”的课程，经变异，该染色体变成：“0872’01211’1005’04201’ 2152”，染色体的适应度大大提高。
5 冲突问题解决
排课问题是一个NP-Complete问题，无论采用哪种方法都无法避免各种冲突问题的出现，同一位教师在同一时段内排了两门课是冲突问题中最明显的一个。为了避免这种冲突产生，在本系统开发中引进了一个冲突检测函数fConflict()，当排完一位教师的所有课程之后，系统就会用该函数对此教师课程安排的冲突情况进行检测并作修正。
6 结果评估
本系统用Visual C++ 6.0软件实现上述遗传排课算法，并对某高校的真实数据作了测试。该校2002—2003学年上学期共有686个排课单元，上课教师356名，共有160间教室，412个行政班。图2显示了一代染色体在演化过程中最高适应值和平均适应值的变化情况，其中染色体为30条，交叉率为0.8，变异率为0.02，演化的代数为1000代。
图2算例最高适应值-平均适应值曲线
由适应值曲线图可以看出，该算法具有较好的收敛性，也说明了本文中提到的染色体编码方案和适应度函数能够较好地反映排课要求，染色体经过世代进化后可以得到令人满意的最优解。图3是利用遗传算法排出的01811,01812两个班级某个学期的课表，从课表中可以看出该课表不存在教师、教室、班级冲突，同一门课程两次上课时间间隔都达到一天以上，并且没有课程被安排在晚上，因此不管是硬约束条件还是软约束条件都得到较好的满足。
7 结论 本文论述了利用遗传算法求解高校课表的安排问题，实验证明文中提出的染色体编码方案和适应度函数是可行的，适应度函数值能够随着进化代数的增加而呈不断上升趋势，实验结果令人满意。在染色体编码方案方面，今后还准备考虑更复杂的课程安排要求。
图3 基于遗传算法的排课结果示例
参考文献
[1]业宁,梁作鹏,董逸生. 一种基于遗传算法的ＴＴＰ问题求解算法. 东南大学学报(自然科学版).2003(1):41-44
[2]唐 勇,唐雪飞,王 玲.基于遗传算法的排课系统. 计算机应用.2002(1):93-94,97
[3]H.L.Fang,”Genetic Algorithms in Timetabling and Scheduling”,Ph.D. Thesis,Department of Artificial Intelligence, University of Edinburgh, UK,1994.
[4] E.K. Burke, D.G. Elliman, R.F. Weare, "A Genetic Algorithm Based University Timetabling System", East-West Conference on Computer Technologies in Education, Crimea, Ukraine, 1994, pp. 35-40.
[5] 王小平,曹立明.遗传算法——理论、应用与软件实现.西安：西安交通大学出版社，2002:31-33
个性化推荐服务中用户兴趣模型研究
基于MVC设计模式的WEB应用框架研究