基于遗传算法的高校网上排课系统

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

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基于遗传算法的高校网上排课系统摘要：大学

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

3、etablingSystemAbstract:UniversityCourseTimetableProblemisNP-Hardcombinatorialoptimizationproblem.BasedonthetraditionalGeneticAlgorithm,wedecompensatetheproblemtodecreasethecomplexity,advancetheproblem-specificchromosomeandoperationstoavoidgenerateillegal

4、timetables,andusecollisiondetectionandresolutiontooptimizethepopulation,increasethefitnessanddecreasethetimeneeded.Finally,weimplementtheonlinetimetablingsysteminASP.NETandC#.Thealgorithmistestedwithrealdatefromourcollege,satisfiesalltheconstraintsofprob

5、lemandyieldpromisingresult.Keywords:UniversityTimetabling;GeneticAlgorithm;CollisionDetection;Online;1引言1.1研究背景和意义长期以来，在高校的教务管理中通常使用手工或者辅助软件进行排课，手工排课相对更为常见，一般是对上一年的课表稍加修改然后予以沿用。然而随着专业的发展和高校的扩招，在不同年级之间，不论从人数、授课教师还是开设的课程，与原来相比都有较大的不同。因而往年的课表对于排课的借鉴作用逐步削弱，一

6、种能满足各种排课约束条件的自动排课软件呼之欲出。尤其在网络不断发展的今天，在线的排课系统更能给教务人员带来更多的便利。1.2国内外研究的现状排课问题，也称为课程表问题。目前，国内外已经有很多人对于这个课题进行了研究，提出的解决方法也多种多样。1963年，C.C.Gotlieb在其TheConstructionofClass-TeacherTime-Tables[1]一文中第一次提出了课表编排的数学模型。1975年，Even.S证明了排课问题是一个NP完全问题,无法用计算机实现，从理论上对时间表问题有了全

7、新的认识。因而，众多的研究者们又开始考虑用其他方法来解决这一问题，比如使用组合逻辑、禁忌搜索、决策系统、贪心算法、图论、模拟退火算法、遗传算法[2,3]、免疫网络[4]等。其中，遗传算法因为其良好的智能性、并行性、简单易用、鲁棒性强等特点，成为一种优秀的亚启发式算法，并成功的应用于例如TSP、地图着色、卫星轨道控制等方面，在解决课程表问题方面也有着不俗的表现。在国内，虽然较国外起步较晚，80年代以来，清华大学、大连理工大学、原南京工学院、西安交通大学等国内高校都进行了相关的研究并研制了相应的软件。比如清

8、华大学的TISER系统，西安交大自行开发的排课系统，中山大学基于智能规划的排课系统，华中科技大学的基于模糊专家系统的排课系统，武汉大学基于回溯算法的排课系统等。10从实际情况来看，由于排课问题的复杂性和各个学校自身教学的特殊性，国内外研制开发的这些软件系统实用性仍然有待提高。排课问题作为NP问题，它的解决也有着典型的代表性。所以，对排课问题的研究无论从理论还是实践上都有着重要意义。1课程表问题1.1课程表问题简介课程表问题是把教师、教室、班