资源描述：
《基于遗传算法的高校排课系统研究论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、基于遗传算法的高校排课系统研究论文摘要提出并实现了一种高校自动排课算法,利用遗传算法建立数据模型,定义一个包含教师编号、班级编号、课程编号、教室编号、上课时间段的染色体编码方案和适应度函数，通过初始化种群、选择、交叉、变异等过程不断进化，最后得到最优解。利用该算法对某高校的真实数据进行实验，结果显示无一例教室、教师、班级冲突，算法具有合理性和可行性。关键词遗传算法；排课问题；适应度函数1前言每个学期对本校教学任务进行合理安排是教务科的重要任务。其中排课是最为关键的环节。排课问题的本质是将课程、教师
2、和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题（TimetableProblem.freel位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制的情况下，能够推出的可能组合就有nm*k种，如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法，如模拟退火,列表寻优搜索,约束满意等1。其中，遗传算法(GeicAlgorithm,简称GA)是很有效的求解最优解的算法。遗传算法是一种通过模拟自然界生物进化
3、过程求解极值的自适应人工智能技术，是由美国芝加哥大学Holland教授于1962年首先提出的。遗传算法借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制来提高各个个体的适应性，体现了自然界中“物竞天择、适者生存”的进化过程。遗传算法也因此吸引了一大批的研究者，并广泛应用于函数优化、组合优化、生产调度、机器学习、图像处理、模式识别等多个领域。2排课问题描述在排课问题中，我们的主要任务是将班级、教室、课程、教师安排在一周内且不发生时间冲突2。据此，我们给出如下描述：学校有R间教室，C个班，S门
4、课程，T位教师，P个时间段。●教室集合R（R1,R2,…Rn），每间教室分别可容纳（X1,X2…Xr）人；●班级集合C（C1,C2,…Cn），每个班级分别有（K1,K2,…Kc）人，其中有x个班级上合班课；●课程集合S（S1,.freel门课，Cn个班，（1≤SmSn,1≤CnCn），在初始设置时设定教师的排课要求。●时间集合P(P1，P2，…，Pn)，假设一周上五天课，每天分为五个教学单元，每个单元为2个课时，即上午2个，下午2个,晚上1个，则时间集合包含25个时间段。如11代表周一第一个教学单
5、元，即周一1、2节，12代表周一第二个教学单元，即周一3、4节，以此类推，这些时间段构成一个时间集合P(11,12,13,….55)。一张正确的课表应至少满足以下硬约束条件：3⑴一个教师或者一个班级或者一个教室在同一时间段内只能安排一门课程；⑵分配的教室可容纳人数应该大于学生数。除了上述的硬性约束，还有些软约束，这些软约束有助于使得课表更加合理，更加人性化。这些软约束条件可能是4：⑴尽量在早上安排必修课，而下午安排选修课，晚上尽量不排课；⑵尽可能满足个别教师的特殊上课时间要求；⑶一门课尽量分散在一
6、个星期中，即某天上完某一门课后，要隔一天以上再上这门课，以使教师有充足的时间备课和批改作业，而学生也有足够的时间复习消化；(4)一个教师的课不能排满一整天；(5)学生课表中的上课时间不能过分集中，应避免一天课程很满而另一天却一整天没课的情况。这些软约束条件各院校有所不同，在我们的研究中，旨在我们定义的约束范围内给出一个遗传算法的解决方法，并对其进行优化操作。3遗传算法遗传算法采用类似基因演化的循环过程，其演算过程如下：1）随机产生一定数目的初始种群2）对个体适应度进行评估，如果个体的适应度符合优化
7、准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第3步。3）依据适应度选择再生个体4）按照一定的交叉概率和交叉方法生成新的个体5）按照一定的变异概率和变异方法生成新的个体6）由交叉和变异产生新一代的种群，然后返回第2步。如图1所示：图1遗传算法示意图以下是遗传算法的伪代码。BEGIN:I=0;InitializeP(I);FitnessP(I);utate变异是随机改变染色体中任一授课时段，将时段随机抽取一点在设定范围内改变。变异运算模仿了生物在自然遗传环境中由于各种偶然因素引起的基因突
8、变，通过变异，染色体适应度有可能加强也有可能降低，但它确保了种群中遗传基因类型的多样性，使搜索能在尽可能大的空间中进行，获得最优解的可能性大大加强。变异操作与交叉操作类似，即定义一个变异概率pm，在变异时先产生一个随机数r，当rpm时，执行变异操作，否则不执行。例如：有一染色体编码为：“0872’01211’1005’04201’2122”，它表示星期二的第一、二教学单元节有编号为“1005”的课程，经变异，该染色体变成：“0872’01211’1005’04201’2152”，染
