本科生毕业论文(设计)
题 目
基于遗传算法的高校网上排课系统
An Optimized Genetic Algorithm Based University Timetabling System
姓 名
王坤 0611701106
院 系
计算机科学
专 业
计算机科学与技术
指导教师
董兆安 职称 讲师
2010 年 5 月 20 日
曲阜师范大学教务处制
目 录
摘要 1
关键词 1
Abstract 1
Key words 1
1 引言 1
1.1 研究背景和意义 1
1.2 国内外研究的现状 1
2 课程表问题 2
2.1 课程表问题简介 2
2.2 课程表问题中的基本约束 2
3 排课系统的具体设计实现 2
3.1 模块划分 2
3.2 课程表问题基本数据结构介绍 2
3.3 遗传算法 3
4 结果分析 6
5 总结 8
致谢 8
参考文献 8
附录 9
基于遗传算法的高校网上排课系统
计算机科学与技术专业学生 王坤
指导教师 董兆安
摘要:大学排课问题是一种NP难的组合优化问题。在传统遗传算法的基础上,首先把问题分解以减少算法的复杂度,然后提出了适合本问题的染色体编码方案和操作方法,以尽量减少非法个体,并采用冲突检测和消解策略,对种群进行优化,提高种群的适应度,并有效缩短了产生最优解的时间。最后使用ASP.NET和C#实现了一个网上自动排课系统,并使用本的真实数据进行测试,满足所用的约束条件,产生了满意的结果。
关键词:大学排课问题 遗传算法 冲突检测 在线
An Optimized Genetic Algorithm Based University Timetabling System
Student Majoring in Computer Science & Technology
Tutor Zhao' an Dong
Abstract: University Course Timetable Problem 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 population, 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 Algorithm; Collision Detection; Online;
1 引言
1.1 研究背景和意义
长期以来,在高校的教务管理中通常使用手工或者辅助软件进行排课,手工排课相对更为常见,一般是对上一年的课表稍加修改然后予以沿用。然而随着专业的发展和高校的扩招,在不同年级之间,不论从人数、授课教师还是开设的课程,与原来相比都有较大的不同。因而往年的课表对于排课的借鉴作用逐步削弱,一种能满足各种排课约束条件的自动排课软件呼之欲出。尤其在网络不断发展的今天,在线的排课系统更能给教务人员带来更多的便利。
1.2 国内外研究的现状
排课问题,也称为课程表问题。目前,国内外已经有很多人对于这个课题进行了研究,提出的解决方法也多种多样。1963年,C. C. Gotlieb在其The Construction of Class-Teacher Time-Tables[1]一文中第一次提出了课表编排的数学模型。1975年,Even. S证明了排课问题是一个NP完全问题,无法用计算机实现,从理论上对时间表问题有了全新的认识。因而,众多的研究者们又开始考虑用其他方法来解决这一问题,比如使用组合逻辑、禁忌搜索、决策系统、贪心算法、图论、模拟退火算法、遗传算法[2,3]、免疫网络[4]等。其中,遗传算法因为其良好的智能性、并行性、简单易用、鲁棒性强等特点,成为一种优秀的亚启发式算法,并成功的应用于例如TSP、地图着色、卫星轨道控制等方面,在解决课程表问题方面也有着不俗的表现。
在国内,虽然较国外起步较晚,80年代以来,清华大学、大连理工大学、原南京工、西安交通大学等国内高校都进行了相关的研究并研制了相应的软件。比如清华大学的TISER系统,西安交大自行开发的排课系统,中山大学基于智能规划的排课系统,华中科技大学的基于模糊专家系统的排课系统,武汉大学基于回溯算法的排课系统等。
从实际情况来看,由于排课问题的复杂性和各个自身教学的特殊性,国内外研制开发的这些软
相关热词:cnet 基于 遗传 算法 高校 网上 系统 毕业 论文