《网络工程毕业设计（论文）基于遗传算法的高校排课系统设计实现》由会员分享，可在线阅读，更多相关《网络工程毕业设计（论文）基于遗传算法的高校排课系统设计实现（44页珍藏版）》请在金锄头文库上搜索。
1、本科毕业论文（设计）题 目 基于遗传算法的高校排课系统学 院 计算机与信息科学学院、软件学院 专 业 网络工程 年 级 200X 级 学 号 姓 名 指 导 老 师 成 绩 200X 年 4 月 30 日 1.引言12.问题分析12.1业务需求分析12.2 数据需求分析22.2.1时间问题32.2.2 教师和课程问题42.2.3教室的问题42.3功能需求分析42.3.1院管理模块52.3.2校管理模块52.3.3自动排课模块52.4排课过程的约束条件63.数据模型73.1 问题陈述73.2 数据流程图84.问题解决104.1 数据库设计104.1.1 概念模型设计104.1.2 逻辑模型设计1
2、24.1.3 数据库的物理设计164.2自动排课系统的设计164.2.1遗传算法的思想164.2.2构建基因编码和染色体174.2.3 初始化种群204.2.4 冲突检测及排除214.2.5 构造适应度函数224.2.6遗传算子244.2.7设置控制参数264.3教室位置填充设计274.4功能模块的设计284.4.1 登录模块284.4.2主界面模块294.4.3学院管理模块304.4.4校管理模块304.4.5查询模块314.4.6 排课模块315.系统运行结果及分析315.1结果315.2分析326.总结及后续工作35参考文献：35基于遗传算法的高校排课系统XXXXXX大学计算机信息与科学
3、学院，重庆 400715摘要：排课问题是当今各大高校在教学资源管理、最优化配置上面临的主要问题之一。本文将遗传算法应用于排课问题的求解中,采用基于轮盘赌算法的选择操作方法和优化的个体适应度计算方法，满足了排课过程中多部分软硬约束条件，实现了各种类型课程的排课。针对之前研究者未解决的运行时间太长问题，本文提出了一套基于二维编码的改进的编码方法和教室位置填充方法，精简了染色体信息量而大大缩短了系统的运行时间。此外，在系统设计中，运用了基于容器的容器编程技术，实现了不定数据量的便捷处理。关键词：遗传算法；排课；教室安排；University Timetabling System based on g
4、enetic algorithm Zhang XiaodongThe college of Computer Information and Science ,Southwest University, Chongqing 400715, ChinaAbstract:Timetabling problem is one of the major problem,which todays universities face in teaching resource management and the optimized configuration.This article,where gene
5、tic algo-rithm will was applied to solve problems,uses the course choice operation method based on rou-lette algorithm and the optimization calculation method of individual fitness, satisfying most ofthe soft and hard constraint conditions int the timetabling process and achieving the timetablation
6、of various types of courses. According to the problem that running time is too long,which the res-earchers didnt resolved well before,this paper puts forward a improved method based on two-dimensional coding and the classroom filled method, simplifying the chromosome informationand greatly shortenin
7、g the syetem operation time. In addition, in the system design, we use the programming method of container based on container , realizing the convenient and fast processing of uncertain quantity data. Key word: Genetic Algorithm; Timetabling; Classroom Arrangement;1.引言随着高校招生逐年扩张，大学课程向着广度和深度发展，高校的教师、
8、教室等一些资源越发显得紧张，不管是在时间还是效率方面，用人工排课已不能够解决现有的问题。排课是高校日常教学工作和其他活动的基础，是教师和学生正常科学工作学习的依据。所以计算法自动排课已成为一个重要的研究课题1。国内学者在自动排课系统方面曾做过一些研究，如用到到退火算法、回溯算法、遗传算法，但运行结果尚有待改进的地方，排课效果不尽人意5。我们认为，问题不尽在数学建模上，还与问题的处理方式有关。将遗传算法应用于排课问题中，首先，初始化课表种群，其次，检测初试种群中的冲突，然后，对种群做选择，杂交，突变操作，一直迭代到具体指定的代数，最后就会得到较优解。文1中提到编码时染色体上基因片存储信息大小为1
9、1字节，而本文的编码方式一个基因片只用了6字节，轻装运行，经试验得出，速度更快。还有,文1介绍把教室与时间等信息共同处理的思路，这可能会产生空间上的冲突，而本文提出将教室分离出以单独处理，就完全解决了空间上的冲突问题。本文根据高校开课的具体情况，采用优化的编码方案，满足排课过程中的一些硬性和软性约束因素，利用遗传算法对课表进行了优化，从而得到了最终的无冲突、更人性的排课方案。2.问题分析2.1业务需求分析排课工作是一项十分繁重而复杂的工作，就以一般高校而言，它涉及到几千多门课程进行合理的组织安排，而所使用的教室资源却在学生规模每年都在增加的趋势下越发显得紧张了。排课的整个过程中充满了矛盾运动，
10、其中包括上课班级、所开课程、任课教师、上课时间、上课地点这5个方面在排列组合中发生的冲突和矛盾现象。课程门类多、班级多、教师少、教室少、教师连续上课的要求、班级连续上课的时间合理安排是排课时发生冲突和矛盾的主要因素，而班级多、教室少则是矛盾的重要方面。课程表则是解决这些矛盾的舞台，是提高教学管理水平、组织师生进行有序教学的规范之一，对有效地提高教育教学质量有重要作用。如果课程表编排得不合理、不科学，将影响课堂教学的效率和教学的整体效果。要想编排好学校的课程表，需要综合考虑学校的教师、教室、学生、班级、时间等多方面因素，反复调整，避免冲突。分析一般高校的排课流程，其过程将如下，下面将排课整个流程
11、作个介绍:(1)各学院从教学计划中导入开课任务书，让各学院安排好教师及教师的各种相关要求，比如班级、教室类型、时间类型等。同时做好教学楼、教室和时间基础数据的输入（已存在数据库中）。这一时间段主要做好班级、课程、教师的协调。(2)把各个学院开课任务书集合为学校开课任务书，同时规划好学院上课所在的教学楼形成位置表，以减少学生的跑动范围。(3)系统会根据校开课任务书自动排课。这一过程主要完成班级、课程、教师及上课时间的安排。(4)把上一步排出的结果与位置表结合，就完成了课表的安排，中间整个过程都要解决冲突问题。(5)课表确定后，进行课表的查询。图2-1排课流程图Chart 2-1 timetabl
12、ing flow chart2.2 数据需求分析排课涉及的相关数据主要包括:时间、班级、课程、教室（空间）、教师等5个要素。开始算法设计的基础是对这些数据之间的问题的透彻分析和适当的处理。2.2.1时间问题在本文中考虑的是周课表，通过对全国部分高校做的调查，综合分析了其中大部分高校的教学特点，我们在此做出了一个较大众化的且较合理的时间划分模式。设定周一至周五，共五天上课，一天有十节课，上课方式都为一大节包括2个相邻的小节，不能在上、下午之间跨时段。把每天用于上课的时间划分为5个时间片，根据学院开课的实际情况，一般每学时是45分钟，为1小节课，每2小节课合为一大节课，故把每2小节课时间定为一个时
13、间片，一天划分为5个时间片: (1)上午1, 2节课8:10-9:50; (2)上午3, 4节课10:10-11:50; (3)下午5, 6节课2: 30-4:10; (4)下午7, 8节课4:20-5:50; (5)晚上9, 10节课7:30-9:10; 这样，每周5天涉及25个时间片。用Tl, T2,.,T25表示，其中TI, T2, T3, T4, T5为星期一的5个时间片，依次类推。则排课问题类似于填充55的周时间片安排表。 表2-1周时间片分布表Table2-1 the management table of the week time slip 周一周二周三周四周五T1T6T11T
14、16T21T2T7T12T17T22T3T8T13T18T23T4T9T14T19T24T5T10T15T20T25根据时间片编号，可进一步转化为125的表格。全校有N个教学班级，则周课表为:以25个时间片为列，形成一维的时间序列，每个班级为行组成的一个二维数据表。我们在此系统的排课都是按一个大节开设的，符合按25个时间片划分的设计，但确有少量的课程的周学时数为单数，如“3学时”或“5学时”，在此仍按“4学时”或“6学时”进行编排，虽然这会浪费一小节课程。2.2.2 教师和课程问题每个课程都有自己的编号、名称以及开课学院。每个课程都要有授课教师。每门课程都有指定的教室类型。如普通教室、语音室、操场、实验室或机房等等。每门课程都有授课计划，包括起始周和截止周以及周学时安排。在处理课程与教师时要注意以下几个问题:(1)“授一班多门课”问题:同一教师可以只上一门课，也可上多门课，如果同一教师在同一个班级教授多门课程，那么把课程和教师作同一变量考虑就会引起课程的混乱，此问题须分情况解决，我们将在系统设计中，学院安排开课任务时解决此问题。 (2)“一师多班”冲突问题:一位教师可能只给一个班讲课，也可能同
