欢迎来到天天文库
浏览记录
ID:326603
大小:172.00 KB
页数:11页
时间:2017-07-23
《基于遗传算法的高校网上排课系统5》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、AnOptimizedGeneticAlgorithmBasedUniversityTimetablingSystem基于遗传算法的高校网上排课系统目录摘要1关键词1Abstract1Keywords11引言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#实现了一个网上自动排课系统,并使用本学院的真实数据进行测试,满足所用的约束条件,产生了满意的结果。关键词:大学排课问题遗传算法冲突检测在线AnOptimizedGeneticAlgorithmBasedUniversityTimetablingSystemAbstract:UniversityCourseTimetableProblemisNP-Hardcombinatorialopt
3、imizationproblem.BasedonthetraditionalGeneticAlgorithm,wedecompensatetheproblemtodecreasethecomplexity,advancetheproblem-specificchromosomeandoperationstoavoidgenerateillegaltimetables,andusecollisiondetectionandresolutiontooptimizethepopulation,increasethefitnessanddecreasethetimeneeded.Final
4、ly,weimplementtheonlinetimetablingsysteminASP.NETandC#.Thealgorithmistestedwithrealdatefromourcollege,satisfiesalltheconstraintsofproblemandyieldpromisingresult.Keywords:UniversityTimetabling;GeneticAlgorithm;CollisionDetection;Online;1引言1.1研究背景和意义长期以来,在高校的教务管理中通常使用手工或者辅助软件进行排课,手工排课相对更为常见,一般是对
5、上一年的课表稍加修改然后予以沿用。然而随着专业的发展和高校的扩招,在不同年级之间,不论从人数、授课教师还是开设的课程,与原来相比都有较大的不同。因而往年的课表对于排课的借鉴作用逐步削弱,一种能满足各种排课约束条件的自动排课软件呼之欲出。尤其在网络不断发展的今天,在线的排课系统更能给教务人员带来更多的便利。1.2国内外研究的现状排课问题,也称为课程表问题。目前,国内外已经有很多人对于这个课题进行了研究,提出的解决方法也多种多样。1963年,C.C.Gotlieb在其TheConstructionofClass-TeacherTime-Tables[1]一文中第一次提出了课表编排的数学
6、模型。1975年,Even.S证明了排课问题是一个NP完全问题,无法用计算机实现,从理论上对时间表问题有了全新的认识。因而,众多的研究者们又开始考虑用其他方法来解决这一问题,比如使用组合逻辑、禁忌搜索、决策系统、贪心算法、图论、模拟退火算法、遗传算法[2,3]、免疫网络[4]等。其中,遗传算法因为其良好的智能性、并行性、简单易用、鲁棒性强等特点,成为一种优秀的亚启发式算法,并成功的应用于例如TSP、地图着色、卫星轨道控制等方面,在解决课程表问题方面也有着不俗的表现。在国内,虽然较国外起步较晚,80年代以来,清华大学、大连理工大学、原南京工学院、西安交通大学等国内高校都进行了相关的研
7、究并研制了相应的软件。比如清华大学的TISER系统,西安交大自行开发的排课系统,中山大学基于智能规划的排课系统,华中科技大学的基于模糊专家系统的排课系统,武汉大学基于回溯算法的排课系统等。10从实际情况来看,由于排课问题的复杂性和各个学校自身教学的特殊性,国内外研制开发的这些软件系统实用性仍然有待提高。排课问题作为NP问题,它的解决也有着典型的代表性。所以,对排课问题的研究无论从理论还是实践上都有着重要意义。1课程表问题1.1课程表问题简介课程表问题是把教师、教室、班
此文档下载收益归作者所有