基于遗传算法的排课系统.doc

《基于遗传算法的排课系统.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基于遗传算法的排课系统设计陈常涛一、数据库设计Ø概述排课问题是一个多因素的组合优化问题，属于NP完全类问题。传统的方法难以得到高质量的课表，而采用遗传算法能更有效地得到更优化的课表。Ø需求分析排课问题有是关于教师，班级，时间，教室以及课程的多因素优化决策问题。所以本系统要求实现以下功能1．在得出的课表中教师不能再同一个时间片段同时上两门或两门以上课程。2．在得出的课表中一个班级在同一个时间片段内不能同时上两门或两门以上课程。3．由于教室容量有限，所以在同一个时间片段内在该教室上课的班级的人数之和不能大于教室的容量。4．在同一个教室上的课必须是同一门课，并且是同一

2、个老师教的。5．所有的课程按照上学期某各个学院的开课计划来安排Ø概念结构设计1．根据以上所述现划分出实体以及实体的属性如下l教师实体教师有其姓名，教师编号，并且一个教师可以教授多门课程和多个班级。所以教师实体的属性如下属性一：教师姓名属性二：教师编号属性三：教师所教授的班级编号属性四：教师所授的课程编号l班级实体一个班级有其所属的年纪以及班级号，也有其班级编号，当然还有班级人数这个重要的属性，所以班级实体的属性如下属性一：班级所属年级以及班级号属性二：班级编号属性三：班级人数l教室实体属性一：教室编号属性二：教室容量l课程实体属性一：课程编号属性二：课程名l开课

3、计划实体属性一：班级属性二：课程属性三：该课程每周需要开设的节次Ø逻辑结构设计实体对应以下关系模式l教师(教师编号，教师姓名，教师所教授的班级编号，教师所授的课程编号)l班级（班级号，班级编号，班级人数）l教室（教室编号，教室容量）l课程（课程编号，课程名）l开课计划（班级编号，课程编号，开设节次）Ø物理结构设计实体间参照关系如下教师实体的教师所授的班级编号和课程编号分别参照班级实体的班级编号和课程实体的课程编号开课计划的班级编号和课程编号分别参照班级实体的班级编号和课程实体的课程编号一、算法设计Ø染色体的编码基因编码为：教师编号+课程编号+教室编号并且为了更好

4、地拆分和组合基因，现规定教师编号为四位，课程编号为四位，教室编号为四位基因所代表的意思是某一时间片段的课程安排，而染色体所代表的是所有班级在一周内的20个时间片段的课程安排所以染色体为n个班和20个时间点所组成的二维维数组染色体结构如下：T1T2…T19T20班级一基因基因基因基因基因班级二基因基因基因基因基因…基因基因基因基因基因班级n-1基因基因基因基因基因班级n基因基因基因基因基因Ø群体的初始化对于每一个班级，按照开课计划实体和教师实体里以及教室实体的数据组合成一个基因随机填入不同的时间片段内。Ø适应度函数1．冲突问题对于二维数组的每一列，如果遇到教师编号

5、相同则课程编号必须相同，否则用某一方法消除。对于二维数组的每一列，如遇到教室编号相同则课程编号也必须相同，并且教师编号也必须相同，且各个班级的人数之和不能超过教室容量。否则用某一方法消除对于二维数组的每一行，要检查开设的课程是否与开课计划相符合。如遇到少开设的则增添课程，如果多开设了则删除该课程。Ø遗传操作略