《基于遗传算法的高校网上排课系统.doc》由会员分享，可在线阅读，更多相关《基于遗传算法的高校网上排课系统.doc（11页珍藏版）》请在三一办公上搜索。
1、An Optimized Genetic Algorithm Based University Timetabling System基于遗传算法的高校网上排课系统目 录摘要1关键词1Abstract1Key words11 引言11.1 研究背景和意义11.2 国内外研究的现状12 课程表问题22.1 课程表问题简介22.2 课程表问题中的基本约束23 排课系统的具体设计实现23.1 模块划分23.2 课程表问题基本数据结构介绍23.3 遗传算法的设计与实现34 结果分析65 总结8致谢8参考文献8附录9基于遗传算法的高校网上排课系统摘要：大学排课问题是一种NP难的组合优化问题。在传统遗传算法
2、的基础上，首先把问题分解以减少算法的复杂度，然后提出了适合本问题的染色体编码方案和操作方法，以尽量减少非法个体，并采用冲突检测和消解策略，对种群进行优化，提高种群的适应度，并有效缩短了产生最优解的时间。最后使用ASP.NET和C#实现了一个网上自动排课系统，并使用本学院的真实数据进行测试，满足所用的约束条件，产生了满意的结果。关键词：大学排课问题 遗传算法 冲突检测 在线 An Optimized Genetic Algorithm Based University Timetabling SystemAbstract: University Course Timetable Problem
3、is NP-Hard combinatorial optimization problem. Based on the traditional Genetic Algorithm, we decompensate the problem to decrease the complexity, advance the problem-specific chromosome and operations to avoid generate illegal timetables, and use collision detection and resolution to optimize the p
4、opulation, increase the fitness and decrease the time needed. Finally, we implement the online timetabling system in ASP.NET and C#. The algorithm is tested with real date from our college, satisfies all the constraints of problem and yield promising result.Key words: University Timetabling; Genetic
5、 Algorithm; Collision Detection; Online;1 引言1.1 研究背景和意义长期以来，在高校的教务管理中通常使用手工或者辅助软件进行排课，手工排课相对更为常见，一般是对上一年的课表稍加修改然后予以沿用。然而随着专业的发展和高校的扩招，在不同年级之间，不论从人数、授课教师还是开设的课程，与原来相比都有较大的不同。因而往年的课表对于排课的借鉴作用逐步削弱，一种能满足各种排课约束条件的自动排课软件呼之欲出。尤其在网络不断发展的今天，在线的排课系统更能给教务人员带来更多的便利。1.2 国内外研究的现状排课问题，也称为课程表问题。目前，国内外已经有很多人对于这个课题进行
6、了研究，提出的解决方法也多种多样。1963年，C. C. Gotlieb在其The Construction of Class-Teacher Time-Tables1一文中第一次提出了课表编排的数学模型。1975年，Even. S证明了排课问题是一个NP完全问题,无法用计算机实现，从理论上对时间表问题有了全新的认识。因而，众多的研究者们又开始考虑用其他方法来解决这一问题，比如使用组合逻辑、禁忌搜索、决策系统、贪心算法、图论、模拟退火算法、遗传算法2,3、免疫网络4等。其中，遗传算法因为其良好的智能性、并行性、简单易用、鲁棒性强等特点，成为一种优秀的亚启发式算法，并成功的应用于例如TSP、地图
7、着色、卫星轨道控制等方面，在解决课程表问题方面也有着不俗的表现。在国内，虽然较国外起步较晚，80年代以来，清华大学、大连理工大学、原南京工学院、西安交通大学等国内高校都进行了相关的研究并研制了相应的软件。比如清华大学的TISER系统，西安交大自行开发的排课系统，中山大学基于智能规划的排课系统，华中科技大学的基于模糊专家系统的排课系统，武汉大学基于回溯算法的排课系统等。从实际情况来看，由于排课问题的复杂性和各个学校自身教学的特殊性，国内外研制开发的这些软件系统实用性仍然有待提高。排课问题作为NP问题，它的解决也有着典型的代表性。所以，对排课问题的研究无论从理论还是实践上都有着重要意义。2 课程表
8、问题2.1 课程表问题简介课程表问题是把教师、教室、班级、课程的组合安排到一天的各个时间段上。根据本院实际情况，一周中每一天分为4个时间段，上午两个，分别为两个小时，下午和晚上各一个，分别为三个小时。这样一周共有20个时间段。2.2 课程表问题中的基本约束课程表问题在实际安排中的约束条件有以下几个方面。2.2.1 硬性约束，即必须满足的约束1、教室不冲突：一个教室同一时间不能安排两门课程，且人数不能超过教室的最大容量；2、班级不冲突：一个班级不能在同一时间段安排两门课或两门以上的课程，同一班级不能同一时间在不同地点上课；3、教师不冲突：一个教师不能同一时间在不同地点上课。2.2.2 弹性约束，
9、即尽量满足的约束，满足此种约束更利于教学1、英语这类课程应尽量安排在上午进行；2、每周课时量较多的课程应在一周的五天中均匀安排；3、每周多次的课程尽量安排在同一间教室；4、时长为三个学时的课程应该安排在下午或晚上；5、学校规定有统一活动的时间不能安排课程。另外，学校已经安排公共课程的时间段是不能给相关班级安排课程的。3 排课系统的具体设计实现3.1 模块划分系统主要分为以下几个模块：1、 系统登录模块：作用是验证用户身份，并转入相应的界面。2、 信息管理模块：在左侧菜单栏显示的用户的权限，用户可以点击各菜单使用相应的功能。包括：添加教室、添加课程、添加教师、添加班级。3、 信息显示模块：包括显
10、示、查询和修改管理员信息、教室信息、教师信息、课程信息、班级信息。4、 自动排课模块：包括预排公共课、添加本学期课程安排、自动排课、显示排课结果、显示全系课表。3.2 课程表问题基本数据结构介绍Professor类：保存教师的基本信息和操作StudentGroups类：保存班级的基本信息和操作Room类：表示教室Course类：表示一门课程CourseClass类：表示一次课程安排，即某教师给某个班级上某节课PreCourseClass类：是CourseClass类的子类，表示一次预排课，即自动排课前已经确定的课程安排GAAutomatedTT类：本算法的核心类，定义了交叉、变异、计算适应度等
11、函数及其配套使用的数据结构3.3 遗传算法的设计与实现3.3.1 问题分解课程表问题虽然是教师、教室、班级、课程四者之间在时间上的组合和优化，在实际应用中我们发现，我们可以把教室根据容量进行分类，同一容量的教室在分配中的地位是平等的，所以可以统计出不同容量教室的个数，遗传算法进行求解时，无需考虑具体教室的分配，只要求每个时间段需要某类教室的个数在该类实际个数范围内即可。在求解完毕后再使用一个算法来完成教室的分配就可以得到最终的解。这样就把问题简化成为教师、班级和课程三者在安排课程时的组合优化。3.3.2 染色体设计在消去教室这一因素后，排课过程中对约束条件判断，除了关于教师的硬性约束条件外，所
12、有的弹性约束条件和预排课约束都是针对班级来说的。所以，我们在设计染色体时以班级为中心。染色体中班级的数据结构如下：Dictionaryint, ListList _slotsOfStudentGroupDictionary中的第一项表示班级ID，其后的ListList对应该班一周的课表，包括20个时间段。其中的List表示在某个时间段安排的课程。教师的数据结构与学生的相似：Dictionaryint, ListList _slotsOfProfessorIDListList 共20个时间段，表示一周的课表一个染色体.List图 31 染色体示意图染色体直接使用类对象，省去了编码和解码的过程，可
13、以直接使用类中的函数对类进行操作，获取相应的信息。染色体中辅助用的数据结构及作用如下：Dictionaryint, ListList _slotsOfProfessor 教师课表，记录每个教师每周的课表；Dictionaryint, ListList _slotsOfStudentGroup班级课表，记录每个班级每周课表；Dictionaryint, List _freetimeOfProfessor 教师空余时间表，记录每个教师的空余时间；Dictionaryint, List _freetimeOfStudentGroup 班级空余时间表，记录每个班级的空余时间；Dictionaryint
14、, List _preScheduleTime 班级预排课时间段表，班级已经预排课时间段；Dictionaryint, Dictionaryint, List _CourseScheduleOfStudentGroup课程所在时间段表，记录每个班级每门课程所在的时间段；Dictionaryint, List _recordsOfBadOnesForThree 记录未合理安排的每周三次的课程；Dictionaryint, List _recordsOfBadOnesForTwo记录未合理安排的每周两次的课程；Dictionaryint, Dictionaryint, List _recordsO
15、fBadOnesForProfessors 记录教师出现冲突的课程；Dictionaryint, List _recordsOfBadOnesForDurationOf3 记录未合理安排的三个课时的课程。3.3.3 种群初始化初始化是为种群中的每个个体根据本学期的课程安排随机产生一份课表。考虑到尽量减少遗传算法的进化压力，初始化的个体应该尽量满足所给出的约束条件。比较所给出的约束条件，应该先满足的是弹性约束的第1、2、4条。因为若在进化中出现此种冲突，只能选择上午（第1条）、隔一天或两天（第2条）、下午或晚上（第4条）的时间段来消解冲突，并且还要满足三项硬性约束，所以选择余地比较小。我们先把待
16、安排的课程进行分类，分别是：预排课程、每周三次每次两个课时的课程、每周两次每次两个课时的课程、每周一次每次三个课时的课程。在初始化时，先根据预排课表，把班级、教师、教室中的相应的空余时间段去掉，然后安排每周三次每次两个课时的课程，三次课分别安排在周一、周三、周五，然后安排每周一次每次三个课时的课程，安排在下午或晚上，再安排每周两次每次两个课时的课程。每次安排时，都尽量找教师和班级共同的空余时间，完毕后，把班级和教师中相应的空余时间段去掉。具体方法如下：1、 处理预排课信息，方法是只去掉班级和教师空余时间表中相应的时间段，但不添加课程至课程表，以免变异时变化；2、 根据课程的性质，包括课时数、每
17、周上课的次数、是否是英语，在空余时间段中找一个符合约束的时间段出来，如果没有随机找一个时间段；3、 在班级和教师的空余时间段表中去掉该时间段，并将其加入到班级和教师的课表中；4、 计算该个体的适应度。3.3.4 交叉操作常见的交叉操作有单点交叉、多点交叉、两点交叉等。在排课算法中，可以选择某节课、某班的全部课程或某年级的全部课程进行交叉。若是只是选择某班的某节课进行交叉，因为一周的所有课程安排之间也有关联，在一个个体中某课程的时间段在另一个个体中未必空余，在教师的安排上也可能产生新的冲突，而且单点交叉面积较小，也限制了其产生新基因的作用。若交叉某班的全部课程，可以避免课程的冲突，可能产生教师安
18、排上的冲突。若交叉某年级的全部课程，因为不同年级之间有重叠的教师更多，产生冲突的可能性就更大。综上所述，我们选择某班的全部课程进行交叉，在实验中的效果也相对较好。具体方法如下：1、 随机生成0-100之间的数大于交叉概率进入2，否则跳出；2、 随机生成需要交叉的班级；3、 交换两个班级的课表；4、 交换两个班级的空余时间表；5、 交换两个班级每门课程所在的时间段；6、 在教师课表中修改相应的信息；7、 计算适应度。3.3.5 变异操作常见的变异操作有等。对于排课算法来说，可以选择某班某节课重新安排、选择某班多节课重新安排或某班全部课程重新安排，也可以选择某班级的两节课互相交换。因为在排课过程中
19、，尤其是后期，产生冲突的课程仅仅是某班的某几节课，对全部课程重新安排容易造成以前进化的失效和个体适应度的过分降低。而具体选择变异的课程数量还需实验研究，所以我们选择某班级的两节课互相交换。具体方法如下：1、 随机生成0-100之间的数大于变异概率进入2，否则跳出2、 随机产生要变异的班级；3、 产生两个变异的时间段；4、 两处的课程若有3学时的，与其交换的课程的时间段必须是在下午或晚上，若是进入7，否则退出；5、 判断两个时间段内是否都已经安排课程，若是，进入7，否则进入6；6、 若只有一个时间段有课，进入7，否则说明两个时间段都没有安排课程，直接跳出；7、 交换课程，并修改染色体中相关的辅助
20、数据结构；8、 计算适应度。3.3.6 计算适应度根据所有的约束条件，适应度的计算共分成6个部分。1、 记录三个课时的课程是否安排在下午和晚上，否则fitness0减一2、 记录同一时间一位教师是否只上一门课，若是，fitness1加一3、 记录同一时间一个班级是否只上一门课，若是，fitness2加一4、 记录相邻两天是否有相同的课，有，则fitness3减一5、 记录一天内是否有相同的课程，有，则fitness3减26、 记录每天需要的教室数是否符合条件，即是否比教室总数少，少则fitness4加一7、 每天需要的各种类型的教室是否符合条件，即是否比相应类型的教室总数少，少fitness5
21、则加一其中fitness0的最优值bestfitness0是0，fitness1的最优值bestfitness1是教师总数*每周总时间段数，fitness2的最优值bestfitness2是班级总数*每周总时间段数，fitness3的最优值bestfitness3是0，fitness4的最优值bestfitness4是每周总时间段数，fitness5的最优值bestfitness5是每周总时间段数*教室类型数。适应度的计算公式为：当fitness为1时，得到一次满足所有条件的课程安排。3.3.7 优化函数在只使用传统遗传算法的实验中，我们发现，产生的个体对于硬性约束1、2的满足性较好，但对于弹
22、性约束2、4和硬性约束3的满足性较差，其中弹性约束2最不易满足，原因在于若要满足弹性约束2，需要调整多门或多次课程，并且在调整中可能产生新的冲突。所以我们编写了三个优化函数进行优化。当然，优化函数在消解一种冲突时可能产生新的冲突，所以最难满足的条件的优化函数我们放在最后执行，对于产生的新的冲突，我们把它交给下一代来消解，逐代减少冲突，提高种群的适应度，实践证明这是可行的，也取得了良好的效果。1、根据弹性约束第2条进行优化优化第2条方法是，根据“课程所在时间段表”，每周两次的课程将任意一次课程提前或延后一天。每周三次的课程直接安排在周一、周三和周五。至于安排在该天的哪一个时间段，则在尽量随机安排
23、在学生和教师都空余的时间段，如果没有，随机找一个时间段，然后把两节课进行交换。2、根据弹性约束第4条进行优化优化第4条方法是，从班级的空余时间段表中找一个下午或晚上的时间段，并且尽量随机安排在学生和教师都空余的时间段，如果没有，随机找一个下午或晚上的时间段，然后把两节课进行交换。3、 根据硬性约束第3条进行优化优化第3条方法是，从教师的空余时间段表中找一个时间段安排冲突的课程，并且尽量随机安排在学生和教师都空余的时间段，如果没有，随机找一个空余时间段，然后把两节课进行交换。3.3.8 选择函数选择操作是用于模拟生物界去劣存优的自然选择现象。它根据个体对于目标函数的适应情况，将高适应值的个体选中
24、，使其基因得以遗传复制到下一代，而低适应值的个体染色体则被淘汰。因此选择的本质是筛选，而功能则是定向进化。经过选择算子多次的定向积累，种群中的个体就会迅速向使目标函数值高的区域靠拢，形成高质量解种群。适应度越高的染色体被选择的可能性越大,其遗传基因在下一代群体中的分布就越广,其子孙在下一代出现的数量就越多。常用的选择函数有轮盘赌选择法、锦标赛选择法、随机遍历选择法等。为使种群尽快收敛，我们使用的是锦标赛选择法。具体方法如下：1、 从种群中随机选择N个体进行适应度的比较，将其中适应度最高的遗传到下一代，N一般取2；2、 重复M次上述过程，从而得到下一代种群。在选择操作中，我们采用了精英保留的策略
25、，每代中保留3%的最优个体，剩余的个体由选择函数从子种群中选出。这样经过若干代进化的种群中能够始终保持进化过程中所找到的历代最优个体，能够有效防止种群整体退化现象。3.3.9 自适应选择函数在遗传算法执行的不同阶段，个体间差异也不同，若用相同的选择策略可能会导致问题的出现：1、当个体差异较大时，高选择压力可能在淘汰掉劣势个体的同时也遗失了存在于劣势个体中的部分优良基因。2、当个体差异很小时，可能会由于选择压力不够而使搜索趋于随机化而导致收敛速度慢。因此，我们采用一种随算法的执行、种群和个体地变化而动态变化的自适应选择策略。常用的变比技术有排名变比、西格玛变比、波兹曼（Boltzmann）变比等
26、。排名变比可以很好的防止收敛过快，但也可能使得收敛太慢。西格玛变比是一种试图在多代繁衍中保持选择压力的方法，其在开始的几代收敛较快，但仍需很长的时间才能得到解。与西格玛变比相比，波兹曼变比在运行期间的选择压力会随时变化，开始时选择压力较小以保持种群的多样性，当开始接近收敛到最优解时，希望只有较好的个体产生后代。其实，波兹曼变比与模拟退火算法类似，它能以一定的概率接受劣解，以保持种群的多样性。在文献6中已经发现模拟退火算法与遗传算法结合可以很大的提高算法的效率。波兹曼变比使用一个连续变化的温度来控制选择率，公式如下：温度初始化为种群中个体数量的两倍，逐代降低的温度为0.05，最低值为1。具体方法
27、如下：1、 逐代降低少量的温度，但确保不低于最低值；2、 通过循环，计算，保存，并计算平均值；3、 通过循环，使用公式计算新的适应度。4 结果分析初始种群为200个个体，交叉概率75%，变异概率50%，数据来源于本院2008-2009学年上学期的课表1、 在未加入波兹曼变比和优化函数的条件下的结果如图4-1所示。图4-1 未加入变比和优化函数2、 加入波兹曼变比未加入优化函数的条件下的结果如图4-2所示。图4-2 加入波兹曼变比未加入优化函数3、 加入波兹曼变比并加入优化函数的条件下，进行了6次实验，结果如表4-1所示。表4-1 加入波兹曼变比和优化函数的实验结果代数适应度1适应度2适应度3适
28、应度4适应度5适应度600.966450.972780.971510.970880.971510.9740510.993670.991130.989240.99240.993670.9936720.996830.99430.995560.99430.997460.9949330.998730.99620.997460.996830.99810.9974640.999360.99810.99810.997460.999360.998735110.998730.9987310.9993660.999360.998730.9993670.999360.998730.9993680.999360.99
29、9360.999369110.99936101在实验一和实验二中，我们发现算法经常收敛于局部最优解，我们采取的方法是保留若干最优个体，然后把其他适应度相同的个体重新初始化的方法。加入变比之前，算法初期，产生更优解的时间间隔比较平均，到了算法后期（2500代以后），随着种群适应度的提高，进化压力越来越大，时间间隔越来越长，产生更优解就变得十分困难。最后也没有产生最优解（适应度为1的解），主要是由于不满足弹性约束2，其他条件可以较好满足。加入变比以后，由于能够以一定概率选择较差的解，种群的适应度更好，产生更优解的时间间隔更为平均，最后产生解的适应度更高，用的时间反而更短。在实验三中，由于优化函数实
30、际是把染色体中的不良基因有目的性的进行修正，修正时也使用随机函数随机选择合适的时间段，这样既增加了种群的适应度，还增加了种群的多样性，避免了收敛于局部最优解的问题。这种变化在初始化（第0代）和进化第1代个体的适应度中表现的尤为明显，初始化种群中最优个体的适应度在0.97左右，第一代的适应度在0.992左右，仅用一代就至少提高了0.02，达到了实验1、2需进化5000代才能达到的适应度。并且在10代以内就可以找到最优解，使适应度达到1，大大减少了排课时间，提高了排课效率。交叉和变异函数以班为单位，对原有的染色体破坏程度较小，尤其是变异函数，我们发现经过变异操作适应度一般不会降低，具体原因还有待探
31、究。当然，与实验1和实验2相比，实验3添加一些辅助的数据结构和函数，占用的内存资源更多，每代计算的时间更长，但最终用时（4min）比原来（20min）大大减低，随着计算机内存的不断增大和处理器能力的不断增强，这个问题就越来越不明显了。5 总结本文在使用传统遗传算法解决时间表问题的基础上，减小了问题的复杂度，提出了自己的编码方案和操作方法，并大胆加入优化函数，不仅有效解决了陷于局部最优解的问题，并且在排课时的能够根据排课时产生的冲突调用相应的优化函数进行优化处理，使排课效率大大提高。不仅提出了完整的解决方案，并且对遗传算法解决时间表问题进行了有益的探索，在解决其它问题时也具有借鉴意义。致谢本论文
32、的工作是在我的导师董兆安老师的悉心指导下完成的，导师渊博的知识、严谨的治学态度、科学的工作方法、勤奋的敬业精神给了我极大的帮助和影响，让我受益匪浅，在本文完成之际，衷心感谢导师对我的关心和指导。在开发系统及撰写论文期问，同组的马义凯、王丙景、邢兆林同学对我论文及研究工作给予了热情帮助，在此向他们表达我的感激之情。衷心感谢在我漫长的求学过程中，给予我无私帮助的众多老师、同学们。感谢我的家人，他们的理解和支持使我能够完成我的学业。借此机会，向在百忙中抽出时间评审本文的专家表示衷心的感谢!参考文献1 Gotlieb,.The Construction of Class-Teacher Time-Ta
33、bles C, Proceedings of the IFIP Congress., 1962, North-Holland Pub. Co., Amsterdam: 73-772 Erben,W. and Keppler, J. A Genetic Algorithm Solving a Weekly Course Timetabling ProblemM, in Practice and Theory of Automated Timetabling, Springer-Verlag Lecture Notesin Computer Science 1153, Burke & Ross,
34、eds., 19963 Arvind.S.Babu , R.Chockalingam, S.Kavitha. A Hybrid Genetic Algorithm Approach to a Departmental Class Timetabling Problem Using Efficient Data StructuresJ ,2010 International Journal of Computer Applications, 2010,Volume 1 No. 17:117-121 4 Antariksha Bhaduri.University Time Table Schedu
35、ling Using Genetic Artificial Immune NetworkC, artcom, 2009 International Conference on Advances in Recent Technologies in Communication and Computing, 2009:289-292,5 滕姿，郑辉文，杨久俊.基于遗传算法的排课系统的设计与实现J，计算机应用，2007年12月，(27)：199-2046 黄杰，陈琳，邹鹏.一种求解极小诊断的遗传模拟退火算法J, 软件学报,2004年 09期，(15)：1345-13507 （美）布克兰德，游戏编程中的
36、人工智能技术M，吴祖增，沙鹰，译.北京，2006附录实验一和实验二 的数据实验一实验二代数适应度代数适应度6010.9529411766400.9385620926230.9542483667240.942483666450.9568627458110.9503267976820.9581699358300.9516339877470.9594771248550.9529411767690.9607843149220.9542483668120.9620915039550.9555555568210.9633986939890.9568627458450.96470588210360.9581
37、699358640.96601307210650.95947712414070.96732026110980.96078431414220.96862745111380.96209150314670.96993464111440.96339869314830.9712418311800.96470588216820.97385620912870.96601307217430.97516339913140.96732026117660.97647058813230.96862745120550.97777777813460.96993464120730.97908496715700.971241
38、8320950.98169934615960.9725490222870.98300653616490.97385620923120.98431372519380.97516339930630.98562091519710.97647058830900.98692810520250.97777777834930.98823529426610.97908496735260.98954248427420.98039215755640.99215686328680.98169934655910.99346405229360.98300653630980.98562091539310.98692810539970.98823529443390.99084967343540.99215686346740.99346405248140.994771242
