学分制模式下基于遗传算法的排课系统的设计(ASP.NET2.0+SQL)

摘    要
排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为NP完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决NP问题非常有效。本文将遗传算法应用于排课问题中，通过对排课因素和约束条件的深入分析，设计出了适合于遗传操作的编码模型，制定了排课问题的优化目标，给出了合理的适应度值的计算方法，通过对初始种群进行选择、交叉、变异等过程不断进化，取得了可行的优化的课表。在排课系统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。(爱毕业设计网 www.2bysj.cn)
【关键词】排课问题；遗传算法；多目标优化
 
Design of the Course Arrangement System Based on Genetic Algorithms Under the Credit System
Wang Zhaoqi
Abstract：
Course Arrangement Problem which is proved NP-Completed is a multi-constraints combination optimization problem with multi-Objective, its essence is Timetable Problem.Genetic Algorithm as a randomly searching algorithm and using colony searching technology, is particularly applicable for NP-Completed. This thesis aimed at solving Timetable Problem using GA. Through deeply analyzing factors and restrictions attached to Timetable Promble, we designed the chromosome coding suitable for Timetable Promblem, the Objective Optimization, and the fitness computation mode. We get the best result through the operation of selection, recombination, mutation to initialization colony. When designed the Course Arrangement System, we use OOA and study attemper classroom algorithm, fill genetic algorithm and check conflict algorithm, we easily realize the Course Arrangement System with the help of them. Experiment is carried out with the actual data. We analyse the infection of parameters setting.

Keywords：
TimeTable Promblem;Genetic Alogrithm;multi-objective optimization

排课问题是一个高校日常教学工作和其他各项活动的基础。课程表不仅是老师和学生上课的依据，也对学校的其他工作的安排有一定影响。利用计算机辅助排课，是教学管理实现科学化，现代化的重要课题之一。
目前高校招生逐年扩张，学生人数不断增加，再加上大多数高校实行学分制，课程开设逐渐向着广度和深度扩展，但学校的教学资源及设备却得不到及时补充，这些都给教务处排课人员造成很大的压力。单纯采用劳动强度大，效率低的手工排课，已成为提高教学管理质量的瓶颈[1]。随着计算机在教学工作中的普及应用，利用计算机进行自动排课已经成为一个重要的研究课题。
排课问题不仅是教学管理工作中必需面对的问题，而且也是运筹学中研究的一个问题——时间表问题 (TimeTable Problems，简记TTPS)。排课问题的研究始于20世纪50年代末，但直到1963年，Gotlieb在他的文章中对排课问题进行了形式化描述并提出了排课问题的数学模型[2]，才标志着排课问题的研究进入科学的殿堂。但由于在实践中遇到的困难，人们对排课问题的解是否存在产生了疑问。1976年，S Even和Cooper等人证明了排课问题是NP完全问题[3]，这虽然回答了在排课实践中遇到困难的原因，但同时宣布计算机解决排课问题无法实现，因为计算机难解性理论指出，现代计算机尚未找到解决NP完全问题的多项式算法。
我国对排课问题的研究始于20世纪80年代初期，所用方法从模拟手工排课到运用人工智能构建专家系统或决策支持系统。吴金荣把排课问题化成整数规划来解决[4]，但计算量很大，而且仅仅适用于规模很小的排课问题。何永太，胡顺仁等人试图用图论中的染色问题来求解排课问题[5,6]，但染色问题本身也是排课问题。基于专家系统的求解算法将专家系统知识引入排课问题的求解[7]，能有效组织排课过程中的知识。但由于实际排课问题存在各种各样的限制条件与特殊要求，至今没有一个有效地普遍适用的排课算法。
本文正是在上述背景下展开工作的，在研究和实践的过程中，针对江西财经大学排课问题的具体情况，结合排课问题中常见的约束及优化目标，采用了一种适应于排课问题的编码方法，并将遗传算法应用到课表的优化，以此获得最终的排课方案。

遗传算法简介
遗传算法(Genetic Algorithm, GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它出现在20世纪60年代，最早是由美国密执安大学的John Holland教授与其同事，学生研究形成的一个比较完整的理论和方法，在一系列研究工作的基础上，80年代由Goldberge进行归纳总结，形成了遗传算法的基本框架。经过20余年的发展，计算机智能已经成为人工智能研究的一个重要方向，以及后来人工生命研究的兴起，使遗传算法受到广泛关注。从1985年在美国卡内基梅隆大学召开的第一届国际遗传会议(International Conference on Genetic Algorithms：ICGAs，85)，到1997年5月，IEEE的Transaction on Evolutionaly Computation创刊，遗传算法作为系统优化、自适应和学习的高性能计算和建模方法的研究日趋成熟[3]。
遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应的随机搜索算法。其主要特点是群体搜索策略和种群中个体之间的信息交换。由于其具有健壮性，特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。简单的讲，它使用了群体搜索技术，从而产生新一代的种群，并逐步使种群进化到近似最优解的状态。

遗传算法的基本术语
既然遗传算法效法于自然选择的生物进化，是一种模仿生物进化过程的随机算法，因此下面先给出几个生物学的基本概念与术语，这对理解遗传算法是非常重要的[8]。
(1) 染色体(chromosome)
生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子——基因组成。遗传因子(Gene) DNA或RNA长链结构中占有一定位置的基本遗传单位，也称为基因。生物的基因数量根据物种的不同多少不一，小的病毒只含有几个基因，而高等动植物的基因却数以万计。
(2) 个体(individual)
指染色体带有特征的实体，在问题简化的情况下可用染色体代替。
(3) 种群(population)
染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小或种群的规模。有时个体的集合也称为个体群。
(4) 进化(evolution)
生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。
(5) 适应度(fitness)
在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应度高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖的机会就会相对较少，甚至逐渐灭绝。
(6) 选择(selection)
指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。正如达尔文描述的，适者生存。
(7) 复制(reproduction)
细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。
(8) 交叉(crossover)
有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，即在两个染色体的某一相同位置处被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称为基因重组(recombination)，俗称“杂交”。
(9) 变异(mutation)
在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。
(10) 编码(coding)
DNA中遗传信息在一个长链上按一定的模式排列，即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。
(11) 解码(decodi ng)
编码的逆过程，即从遗传子型到表现型的映射。

 排课问题的业务流程分析
(1) 主要流程
 
(2) 教务处工作流程
教务处根据各年级、各专业的培养方案，学生人数结合考虑课程性质向各个学院下达教学任务书，明确这学期的教学要求。教学任务书中要明确所要开设的课程、应开设班级数目(班别)、课程开设的校区等信息。其中，某课程应开设的班级数，是由要选修该课程的学生总数及该课程的参考容量决定的，各学院可以根据自身情况对其进行调整。
 
(3) 学院工作流程
教学任务书下达到各学院后，各学院根据自身教师情况，可以适当调整教学任务书中某课程的开课班级数及班级容量。然后，在教学任务书中为每门课程的每个班添加老师，以及该课程对教室的要求，这样形成的信息称之为课元信息。同时学院的老师可以向教务处提交特殊时间要求，如星期三下午，信息学院领导因工作会议，不能安排上课。
 
(4) 排课流程
各学院把课元信息提交给教务处，教务处根据全校教师情况，教室资源情况，老师的特殊要求利用排课系统排出预排课表，学生根据预排课表选课，教务处在学生选课后，根据各个选课班的人数，撤销人数小于20的选课班。课程表包括全校总课程表、学生课程表、教师课程表和教室课程表。课程表由教务处编制，不得随意变动。如因特殊情况调整，须按学校有关规定办理手续，并由教务处下达调课通知。执行流程如图3-4所示。
 
(5) 排课总流程
每届新生入学前，各学院各专业已经为新生制定了在校四年的培养方案，作为在校期间学生选课的依据。其中不仅列出了学生完成学业所必需选修的公共基础课、专业课，还列出了有利于学习专业知识、扩大知识面的推荐选修课，以及这些课程在哪个学期开设。并注明了所列出的每门课程的学分，及每个学生毕业时所要修完的总学分。排课工作开始后，教务处根据各年级各专业培养方案、各年级各专业学生人数、课程性质，生成教学任务书,其包括要开设的课程名称、该课程要开设的班级数(班别)、校区等信息。教学任务书下达到各学院后，学院根据自身教师情况，修改某些课程的班级数目及相应的班级容量，之后为教学任务书添加老师，并提出课程对教室的要求，及学院老师对上课时间的要求(如某个时间段不能安排课程)，这样就形成了课元信息。学院再将课元信息提交教务处，教务处根据教师情况，教室资源情况，老师的特殊要求利用排课系统排出预排课表，学生根据预排课表选课，教务处在学生选课后，根据各个选课班的人数，撤销人数小于20的选课班。教务处可以根据具体情况调整课程表，并下达调课通知。(爱毕业设计网 www.2bysj.cn)














 
目    录
1  引言 1
2  遗传算法简介 1
2.1  遗传算法的基本术语 2
2.2  遗传算法的基本思想 3
2.3  遗传算法的基本操作 4
3  排课问题的需求分析 5
3.1  排课问题的业务流程分析 5
3.2  排课因素分析 8
3.3  排课的约束条件 9
4  基于遗传算法的排课算法的描述 10
4.1  排课问题的目标分析 10
4.2  排课系统中面向对象的应用及用到的算法 13
4.2.1  排课算法的面向对象的应用 13
4.2.2  教室调度算法 15
4.2.3  基因初始化算法 16
4.2.4  冲突检测算法 17
4.3  排课问题中遗传算法的设计 17
4.3.1  遗传算法的编码 17
4.3.2  初始种群的产生 18
4.3.3  遗传操作的设计 18
4.3.4  适应度函数的设计 20
(爱毕业设计网 www.2bysj.cn)
5  实验及结果分析 20
5.1  排课系统开发环境 20
5.2  实例说明及参数设置对排课效率的影响 20
5.3  结果分析 23
5.3.1  排课结果分析 23
5.3.2  与人工排课的比较 24
6  结束语 25
参考文献 26