论文部分内容阅读
[摘要]提出并实现一种高校自动排课算法，利用遗传算法建立数据模型，定义一个包含教师编号、班级编号、课程编号、教室编号、上课时间段的染色体编码方案和适应度函数，通过初始化种群、选择、交叉、变异等过程不断进化，最后得到最优解。利用该算法对某高校的真实数据进行实验，结果显示无一例教室、教师、班级冲突，算法具有合理性和可行性。
[关键词]遗传算法 排课系统 适应度函数
中图分类号：TP3 文献标识码：A 文章编号：1671－7597(2008)1110073－01
高校排课问题很早以前就成为众多科研人员和软件公司的研究课题，其中算法的选择是最关键的一个问题，即若是用“穷举法”之外的算法找出最佳解是不可能的。然而由于穷举法根本无法在计算机上实现。因为假设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制的情况下，能够推出的可能组合就有nm*k种，如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法，如模拟退火,列表寻优搜索,约束满意等。其中，遗传算法(Genetic Algorithm, 简称GA)是很有效的求解最优解的算法。
一、遗传算法
遗传算法采用类似基因演化的循环过程，其演算过程如下：①随机产生一定数目的初始种群。②对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第3步。③依据适应度选择再生个体④按照一定的交叉概率和交叉方法生成新的个体。⑤按照一定的变异概率和变异方法生成新的个体。⑥由交叉和变异产生新一代的种群，然后返回第2步。以下是遗传算法的伪代码。
BEGIN:
I = 0;
Initialize P(I);
Fitness P(I);
While(not Terminate-Condition)
{
I ++;
GA-Operation P(I);
Fitness P(I);
}
END.
二、设计
（一）染色体编码。GA中首要考虑的是如何表现其问题，即如何对染色体编码，使之适用于GA操作。在经典的遗传算法中，常采用浮点数或二进制的编码方法，而研究中，每条染色体代表每位教师的课表，染色体在程序中可用十进制数编码，随机产生上课时间，随机选择大于两班总人数的教室。适应度函数。遗传算法在进化中是以每个个体的适应度值为依据来选取下一代种群的。适应度函数设定的好坏直接影响到遗传算法的收敛速度和能否找到最优解。在本系统中，适应度函数的设计思想是对每条染色体中存在的冲突类型进行加权求和，其中权值Wi代表的是第i条规则的重要程度，若某条染色体违反了某条规则i，则将其值Pi置为1（若没有违反规则i，则Pi值为0），其受到的惩罚值为Wi*Pi，对染色体中存在的冲突进行加权求和并加上1后，再求其倒数，如以下公式所示。染色体适应度函数值越大，则表示其拥有较好的授课时段和教室，其在下一代的演化中的生存概率就较大。
（二）遗传操作。初始化[Initialize]。初始化的目的在于为后面的遗传操作提供初始种群。在我们的算法中，由于每次对一位教师进行遗传操作，初始化时就需要考虑到教室及时间的设定，这其中包括教室可容人数的最优逼近（即避免一个30人的班级占用可容200人的教室这种情况），以及上课时间安排的合理性，这在排课问题描述中已有解释。
选择[Select]。选择运算用于模拟生物界去劣存优的自然选择现象。它从旧种群中选择出适应度高的某种染色体，放入配对集合中，为染色体交叉和变异运算产生新种群做准备。适应度越高的染色体被选择的可能性越大，选择操作的方法有许多，如轮盘赌选择法（roulette wheel selection）。研究中，我们选用了局部选择法中的一种：截断选择法（truncation selection）。
在截断选择法中，染色体按适应度函数值由高到低排序，只有最优秀的个体才能被选作父个体。其中，用于决定染色体被选作父个体的百分比的参数称为截断阀值Trunc，其取值范围为50%~10%。在该阀值之外的个体不能产生子个体。选择强度表示为：
SelIntTrunc(Trunc) =
式中fc为下列高斯分布的积分下限：
Trunc =
交叉[Crossover]。交叉是根据选择操作的结果，选取两条染色体作为父个体，再取一随机值（设为r）与系统预设的交叉率值（设为t）比较，若r 变异[Mutate]。变异是随机改变染色体中任一授课时段，将时段随机抽取一点在设定范围内改变。变异运算模仿了生物在自然遗传环境中由于各种偶然因素引起的基因突变，通过变异，染色体适应度有可能加强也有可能降低，但它确保了种群中遗传基因类型的多样性，使搜索能在尽可能大的空间中进行，获得最优解的可能性大大加强。
三、冲突问题解决与结果评估
排课问题是一个NP-Complete问题，无论采用哪种方法都无法避免各种冲突问题的出现，同一位教师在同一时段内排了两门课是冲突问题中最明显的一个。为了避免这种冲突产生，在本系统开发中引进了一个冲突检测函数fConflict()，当排完一位教师的所有课程之后，系统就会用该函数对此教师课程安排的冲突情况进行检测并作修正。
四、结论
本文论述了利用遗传算法求解高校课表的安排问题，实验证明文中提出的染色体编码方案和适应度函数是可行的，适应度函数值能够随着进化代数的增加而呈不断上升趋势，实验结果令人满意。在染色体编码方案方面，今后还准备考虑更复杂的课程安排要求。
参考文献：
[1]业宁、梁作鹏、董逸生，一种基于遗传算法的ＴＴＰ问题求解算法，东南大学学报(自然科学版).2003(1):41-44.
[2]唐勇、唐雪飞、王玲，基于遗传算法的排课系统. 计算机应用. 2002(1):93-94.97.
[3]王小平、曹立明，遗传算法理论、应用与软件实现.西安：西安交通大学出版社，2002:31-33.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词]遗传算法 排课系统 适应度函数
中图分类号：TP3 文献标识码：A 文章编号：1671－7597(2008)1110073－01
高校排课问题很早以前就成为众多科研人员和软件公司的研究课题，其中算法的选择是最关键的一个问题，即若是用“穷举法”之外的算法找出最佳解是不可能的。然而由于穷举法根本无法在计算机上实现。因为假设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制的情况下，能够推出的可能组合就有nm*k种，如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法，如模拟退火,列表寻优搜索,约束满意等。其中，遗传算法(Genetic Algorithm, 简称GA)是很有效的求解最优解的算法。
一、遗传算法
遗传算法采用类似基因演化的循环过程，其演算过程如下：①随机产生一定数目的初始种群。②对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第3步。③依据适应度选择再生个体④按照一定的交叉概率和交叉方法生成新的个体。⑤按照一定的变异概率和变异方法生成新的个体。⑥由交叉和变异产生新一代的种群，然后返回第2步。以下是遗传算法的伪代码。
BEGIN:
I = 0;
Initialize P(I);
Fitness P(I);
While(not Terminate-Condition)
{
I ++;
GA-Operation P(I);
Fitness P(I);
}
END.
二、设计
（一）染色体编码。GA中首要考虑的是如何表现其问题，即如何对染色体编码，使之适用于GA操作。在经典的遗传算法中，常采用浮点数或二进制的编码方法，而研究中，每条染色体代表每位教师的课表，染色体在程序中可用十进制数编码，随机产生上课时间，随机选择大于两班总人数的教室。适应度函数。遗传算法在进化中是以每个个体的适应度值为依据来选取下一代种群的。适应度函数设定的好坏直接影响到遗传算法的收敛速度和能否找到最优解。在本系统中，适应度函数的设计思想是对每条染色体中存在的冲突类型进行加权求和，其中权值Wi代表的是第i条规则的重要程度，若某条染色体违反了某条规则i，则将其值Pi置为1（若没有违反规则i，则Pi值为0），其受到的惩罚值为Wi*Pi，对染色体中存在的冲突进行加权求和并加上1后，再求其倒数，如以下公式所示。染色体适应度函数值越大，则表示其拥有较好的授课时段和教室，其在下一代的演化中的生存概率就较大。
（二）遗传操作。初始化[Initialize]。初始化的目的在于为后面的遗传操作提供初始种群。在我们的算法中，由于每次对一位教师进行遗传操作，初始化时就需要考虑到教室及时间的设定，这其中包括教室可容人数的最优逼近（即避免一个30人的班级占用可容200人的教室这种情况），以及上课时间安排的合理性，这在排课问题描述中已有解释。
选择[Select]。选择运算用于模拟生物界去劣存优的自然选择现象。它从旧种群中选择出适应度高的某种染色体，放入配对集合中，为染色体交叉和变异运算产生新种群做准备。适应度越高的染色体被选择的可能性越大，选择操作的方法有许多，如轮盘赌选择法（roulette wheel selection）。研究中，我们选用了局部选择法中的一种：截断选择法（truncation selection）。
在截断选择法中，染色体按适应度函数值由高到低排序，只有最优秀的个体才能被选作父个体。其中，用于决定染色体被选作父个体的百分比的参数称为截断阀值Trunc，其取值范围为50%~10%。在该阀值之外的个体不能产生子个体。选择强度表示为：
SelIntTrunc(Trunc) =
式中fc为下列高斯分布的积分下限：
Trunc =
交叉[Crossover]。交叉是根据选择操作的结果，选取两条染色体作为父个体，再取一随机值（设为r）与系统预设的交叉率值（设为t）比较，若r
三、冲突问题解决与结果评估
排课问题是一个NP-Complete问题，无论采用哪种方法都无法避免各种冲突问题的出现，同一位教师在同一时段内排了两门课是冲突问题中最明显的一个。为了避免这种冲突产生，在本系统开发中引进了一个冲突检测函数fConflict()，当排完一位教师的所有课程之后，系统就会用该函数对此教师课程安排的冲突情况进行检测并作修正。
四、结论
本文论述了利用遗传算法求解高校课表的安排问题，实验证明文中提出的染色体编码方案和适应度函数是可行的，适应度函数值能够随着进化代数的增加而呈不断上升趋势，实验结果令人满意。在染色体编码方案方面，今后还准备考虑更复杂的课程安排要求。
参考文献：
[1]业宁、梁作鹏、董逸生，一种基于遗传算法的ＴＴＰ问题求解算法，东南大学学报(自然科学版).2003(1):41-44.
[2]唐勇、唐雪飞、王玲，基于遗传算法的排课系统. 计算机应用. 2002(1):93-94.97.
[3]王小平、曹立明，遗传算法理论、应用与软件实现.西安：西安交通大学出版社，2002:31-33.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”