基于遗传算法的排课系统研究

《基于遗传算法的排课系统研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法的排课系统的研宄谷冰（沈阳建筑大学信息学院）摘要：排课问题是一个有约束的、多目标的组合优化问题，并且已经被证明为一个NP完全问题。本文主要基于遗传算法，结合排课系统的一些具体需求，研究并实现一个排课系统。【关键词】排课问题；遗传算法；组合优化一、背景近年來随着大学扩招，大学生人数的增加，每学期的排课问题一直是学校一项巨大的工作任务，使用人工手动排课对于这样一个庞大的课程体系来说简直是天方夜谭。其屮，最突出的问题就是班级多、课程多、教师少、教室少，从而导致传统的手工排课方法，由于工作量巨大、效率低下，容易山错己经不能满足需求；因此，研究计算机排课系统有重大的现实意义。

2、二、遗传算法遗传算法（GeneticAlgorithms,GA）見根1K•自然界的选择和进化原来发展起来的岛度并行、随机、自适应的随机搜索算法。苒模拟达尔文的适者生存原理，每个种群所而临的问题是寻找一种对复杂和变化着的环境最有利的适应方式。遗传算法维持一个潜在的群体（染色体、变量），定义一个函数为：P（t）={Xli,Xln}染色体通常形成是一申的数组，近年来基于实数编码的遗传算法也得到广泛的应用。每个解用其“适应值”进行评价其优劣程度。然后通过选择更新（t+1次迭代）个新的群体。新群体的成员通过杂交和变异进行变换，以形成新的解。杂交组合了两个亲体染色体的特征,并通过交换父代相

3、应的片段形成了两个相似的后代。例如，如果父代用五维向量来表示，如下：（ai,bi,Ci,di,ei），（a2,b2,c2,d2,e2）在第二个基因后杂交，染色将产生后代（ai,bi,c2,d2,e2）杂交算子的意图是在不同潜在解之间进行信息交换。变异是通过用一个等于变异率的概率随机地改变染色体上的一个或多个基因。变异算子的意图是向群体加入一些额外的变化性。我们可以把遗传算法简化以下步骤：1）产生初始遗传群体的方法。2）川“适应值”评价解的适应度的评价函数。3）改变后代组成的遗传算子。4）遗传算子所使用的各种参数：流程罔如图1。实际问题集编码形成染色体产生初始种群1<计算其适应度

4、选择一个个体选择两个个体选择两个个体复制新种群杂交操作产生种群2经过优化的种群解决实际问题三、排课问题高校排课涉及到教师、班级、课程、教室和吋段各个复杂的因素，衡量一个课表的好坏通常有硬约束和软约束两大类，硬约束有：1.一个教师或者一个班级或者一个教室在同一时间段内只能安排一门课程；2.分配的教室可容纳人数应该大于学生数。软约束有：1.在对于一个教师、班级、教室每天安排尽fi均匀。2.不同类型的课程能按不同的优度安排相对较好吋段。四、排课系统设计遗传算法首先要考虑的是如何表现其问题，即如何对染色体编码，使之适用于遗传算法操作。1.编码：考虑到程序的可操作性，用十进制编码方式来表

5、示。(1)教师ID编码格式，用6位表示为：1-51-90-91-90-91-9职称系/学院教研室教师编号(2)班级1D编码，于教师W形式，用6位表示:0-90-91-90-90-90-9入学年份系/学院专业班号(3)课程TD编码，用10位表示【2】：2或31-91-91-50-91-30-90-90-90-9—次2或上课班课程上课人课程性每周有几课程原始编号3节课级数类型数等级质次课其中课程类型：1-9分别可以用來代表普通课、体育课、实验课、实践课等等；上课人数等级：1代表50人以内,2代表50到100，3代表100到150,4代表150到200,5代表200以上；课程性质：1

6、为专业课、2为非专业课如每周4节的“网络基础”课程表示为2151322512(4)教室编码，用6位表示：0-90-91-90-90-90-9教室类型楼号楼內编号2.种群操作(1)初始化种群。初始化的目的是为了以后的遗传操作产生种群。在此，本文采川以教师作为染色体：首先根裾教学任务书屮教师、班级和课程的对应关系，对染色体的教师1D、班级ID和课程ID进行编码并组合。根裾课程1D中课程类型的要求以及教室分类表随机分配教室；再根据课程ID中上课次数和上课节数随机安排时段；扱后根据染色体编码方案产生初始化种群。(2)选择操作，本文采用按比例的适应度分配法。(3)交叉操作。交叉是根据选择

7、操作的结果，选取一对染色体作为父个体，再取一随机值(设为H与系统预设的交叉率值(设为t)比较，若Kt则进行交换基因。按染色体编码方案，我们选择最简单的单点交叉方式，交叉点为第23位，也即交换两个染色体的教室编码和时段编码，这样不会影响到每位教师所教授的课程，也不会造成教师课表A含其他教师的教授课程或每代演化后染色体结构不合理等问题。五、结论本设计以matlab实现排课系统，并以某高校2009-2010年第二学期的实际数据进行测试，样例数据结果无教室冲突、无吋段冲突、无教师冲突，课程安排间隔比