毕业设计（论文）-基于遗传算法的高校网上排课系统

《毕业设计（论文）-基于遗传算法的高校网上排课系统》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科生毕业论文（设计）题　　目基于遗传算法的高校网上排课系统AnOptimizedGeneticAlgorithmBasedUniversityTimetablingSystem姓　　名学号院　　系计算机科学学院专　　业计算机科学与技术指导教师职称讲师2010年5月20日曲阜师范大学教务处制目录摘要1关键词1Abstract1Keywords11引言11.1研究背景和意义11.2国内外研究的现状12课程表问题22.1课程表问题简介22.2课程表问题中的基本约束23排课系统的具体设计实现23.1模块划分23.2课程表问题基本数据结构介绍23.3遗传算法的设计与实现34结果分析65总结

2、8致谢8参考文献8附录9基于遗传算法的高校网上排课系统计算机科学与技术专业学生指导教师摘要：大学排课问题是一种NP难的组合优化问题。在传统遗传算法的基础上，首先把问题分解以减少算法的复杂度，然后提出了适合本问题的染色体编码方案和操作方法，以尽量减少非法个体，并采用冲突检测和消解策略，对种群进行优化，提高种群的适应度，并有效缩短了产生最优解的时间。最后使用ASP.NET和C#实现了一个网上自动排课系统，并使用本学院的真实数据进行测试，满足所用的约束条件，产生了满意的结果。关键词：大学排课问题遗传算法冲突检测在线AnOptimizedGeneticAlgorithmBasedUnive

3、rsityTimetablingSystemStudentMajoringinComputerScience&TechnologyTutorAbstract:UniversityCourseTimetableProblemisNP-Hardcombinatorialoptimizationproblem.BasedonthetraditionalGeneticAlgorithm,wedecompensatetheproblemtodecreasethecomplexity,advancetheproblem-specificchromosomeandoperationstoavoi

4、dgenerateillegaltimetables,andusecollisiondetectionandresolutiontooptimizethepopulation,increasethefitnessanddecreasethetimeneeded.Finally,weimplementtheonlinetimetablingsysteminASP.NETandC#.Thealgorithmistestedwithrealdatefromourcollege,satisfiesalltheconstraintsofproblemandyieldpromisingresu

5、lt.Keywords:UniversityTimetabling;GeneticAlgorithm;CollisionDetection;Online;1引言1.1研究背景和意义长期以来，在高校的教务管理中通常使用手工或者辅助软件进行排课，手工排课相对更为常见，一般是对上一年的课表稍加修改然后予以沿用。然而随着专业的发展和高校的扩招，在不同年级之间，不论从人数、授课教师还是开设的课程，与原来相比都有较大的不同。因而往年的课表对于排课的借鉴作用逐步削弱，一种能满足各种排课约束条件的自动排课软件呼之欲出。尤其在网络不断发展的今天，在线的排课系统更能给教务人员带来更多的便利。1.2国内

6、外研究的现状排课问题，也称为课程表问题。目前，国内外已经有很多人对于这个课题进行了研究，提出的解决方法也多种多样。1963年，C.C.Gotlieb在其TheConstructionofClass-TeacherTime-Tables[1]一文中第一次提出了课表编排的数学模型。1975年，Even.S证明了排课问题是一个NP完全问题,无法用计算机实现，从理论上对时间表问题有了全新的认识。因而，众多的研究者们又开始考虑用其他方法来解决这一问题，比如使用组合逻辑、禁忌搜索、决策系统、贪心算法、图论、模拟退火算法、遗传算法[2,3]、免疫网络[4]等。其中，遗传算法因为其良好的智能性、并

7、行性、简单易用、鲁棒性强等特点，成为一种优秀的亚启发式算法，并成功的应用于例如TSP、地图着色、卫星轨道控制等方面，在解决课程表问题方面也有着不俗的表现。10在国内，虽然较国外起步较晚，80年代以来，清华大学、大连理工大学、原南京工学院、西安交通大学等国内高校都进行了相关的研究并研制了相应的软件。比如清华大学的TISER系统，西安交大自行开发的排课系统，中山大学基于智能规划的排课系统，华中科技大学的基于模糊专家系统的排课系统，武汉大学基于回溯算法的排课系统等。从实际情