1、学分制模式下基于遗传算法的排课系统的设计 普通本科毕业论文(设计)题 目: 学分制模式下基于遗传算法的排课系统的设计院 别 信息管理学院 学生姓名 王兆奇 学 号 0031718 年 级 2003级 专 业 信息管理与信息系统 指导教师 凌传繁 职 称 教授 二OO七 年 五 月论文独创性声明本人声明，所呈交的毕业论文是在导师指导下本人独立完成的研究成果。文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。本文如违反上述声明，愿意承担以下责任和后果：1.交回学校授予的学位证书；2.学校可在相关媒
2、体上对作者本人的行为进行通报；3.本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害，进行公开道歉；4.本人负责因论文成果不实产生的法律纠纷。论文作者签名： 日期： 年 月 日摘 要排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为NP完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决NP问题非常有效。本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问题的优化目标，设计出了适合于遗传操作的编码模型，给出了合理的适应度值的计算方法。通过对初始种群进行选择、交叉、变异等过程不断进化，取得了优化的课表。在排课系
3、统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。【关键词】学分制模式；排课系统；遗传算法；多目标优化Design of the Course Arrangement System Based on Genetic Algorithms in Credit ModeWang ZhaoqiAbstract：The problem of course arrangement is an optimization problem with multi-constraint
4、s and multi-objective, which is actually a timetable problem and has been proved to be a NP-completed problem. As a ramdom searching algorithm, the genetic algorithm(GA) using colony searching technology is very suitable for NP-completed problem.This thesis uses GA for the course arrangement system
5、with credit mode. Therough analyzing deeply the factors and constraints of course arrangement, the optimization objectives of course arrangement are determined first. Then the coding mode for genetic operations is designed and the computation method for reasonable fitness is given. An optimized cour
6、se table is gotten through the operations of selection, recombination and mutation on the initial colony.Based on the object-oriented method, this design makes use of classroom schedule algorithm, genetic fill algorithm and conflict detecting algorithm to arrange course. The experiments are carried
7、out using real data to analyse the influence of all parameters on the genetic operations and results.Keywords：Credit Mode; Course Arrangement System; Genetic Alogrithm; Multi-objective Optimization1 引言排课问题是高校日常教学工作和其他各项活动的基础。课程表不仅是老师和学生上课的依据，也对学校的其他工作的安排有一定影响。利用计算机辅助排课，是教学管理实现科学化，现代化的重要课题之一。目前高校招生逐年
8、扩张，学生人数不断增加，再加上大多数高校实行学分制，课程开设逐渐向着广度和深度扩展，但学校的教学资源及设备却得不到及时补充，这些都给教务处排课人员造成很大的压力。单纯采用劳动强度大、效率低的手工排课，已成为提高教学管理质量的瓶颈。随着计算机在教学工作中的普及应用，利用计算机进行自动排课已经成为一个重要的研究课题。排课问题不仅是教学管理工作中必需面对的问题，而且也是运筹学中研究的一个问题时间表问题 (TimeTable Problems，简记TTPS)。排课问题的研究始于20世纪50年代末，但直到1963年，Gotlieb在他的文章中对排课问题进行了形式化描述并提出了排课问题的数学模型1，才标志
9、着排课问题的研究进入科学的殿堂。但由于在实践中遇到的困难，人们对排课问题的解是否存在产生了疑问。1976年，S Even和Cooper等人证明了排课问题是NP完全问题2,3，这虽然回答了在排课实践中遇到困难的原因，但同时宣布计算机解决排课问题无法实现，因为计算机难解性理论指出，现代计算机尚未找到解决NP完全问题的多项式算法。我国对排课问题的研究始于20世纪80年代初期，所用方法从模拟手工排课到运用人工智能构建专家系统或决策支持系统。吴金荣把排课问题化成整数规划来解决4，但计算量很大，而且仅仅适用于规模很小的排课问题。何永太、胡顺仁等人试图用图论中的染色问题来求解排课问题5,6，但染色问题本身也
10、是排课问题。基于专家系统的求解算法将专家系统知识引入排课问题的求解7，能有效组织排课过程中的知识。但由于实际排课问题存在各种各样的限制条件与特殊要求，至今没有一个有效地普遍适用的排课算法。随着现代智能优化技术的出现和发展，模拟退火算法、禁忌搜索算法、蚁群算法、遗传算法等被应用到排课问题中。模拟退火算法(Simulated Annealing)是Kirkpatrick等人于1983年首先提出的，它是人们从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题间的相似性。在对固体物质进行退火处理时，常先将它加温使
11、其粒子可自由运动，以后随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度下降速率足够慢，则固体物质一定会形成最低能量的基态。优化问题也存在类似过程。模拟退火法被用来解决许多实际应用中的优化问题，取得了不错的效果，用其解决排课问题8，现在还处在模型实验阶段，还有许多问题要解决。禁忌搜索的思想最早由Glover于1986年提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。禁忌搜索算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。文献9中提出了结合网络
12、流算法与禁忌搜索算法的优势，求解排课问题的方案，虽然得出了可行解，但结果不够理想，很多优化因素没有考虑。蚁群算法是随着仿生学的发展而发展起来的，它是由意大利学者M.Dorigoz在20世纪90年代初提出的，它通过模拟蚁群觅食的过程中寻找最短路径的方法来求解优化问题。文献10提出了基于二部图的排课模型，并揉合蚁群算法AS、ACS、MMAS三个不同模型的优点，提出一种面向排课问题的改进型蚁群算法，但是问题求解复杂，操作繁琐。上述算法都是一定程度上的启发搜索算法，但是搜索过程的启发信息依赖于实际情况，排课问题求解只能针对个别的实际问题，且没有引入目标优化技术，更不用说人性化方面的考虑。正是因为如此，
13、具有智能性、并行性和高鲁棒性的遗传算法迅速应用于排课问题，并得到了很快的发展。本文正是在上述背景下展开的，在分析和实践的过程中，针对江西财经大学排课问题的具体情况，结合排课问题中常见的约束及优化目标，采用了一种适应于排课问题的编码方法，并将遗传算法应用到课表的优化，以此获得最终的排课方案。2 遗传算法遗传算法(Genetic Algorithm, GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它出现在20世纪60年代，最早是由美国密执安大学的John Holland教授与其同事、学生研究形成的一个比较完整的理论和方法，在一系列研究工作的基础上，80年代由G
14、oldberge进行归纳总结，形成了遗传算法的基本框架。经过20余年的发展，计算机智能已经成为人工智能研究的一个重要方向，以及后来人工生命研究的兴起，使遗传算法受到广泛关注。从1985年在美国卡内基梅隆大学召开的第一届国际遗传会议(International Conference on Genetic Algorithms：ICGAs，85)，到1997年5月，IEEE的Transaction on Evolutionaly Computation创刊，遗传算法作为系统优化、自适应和学习的高性能计算和建模方法的研究日趋成熟3。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、
15、自适应的搜索算法。其主要特点是群体搜索策略和种群中个体之间的信息交换。由于其具有健壮性，特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。简单的讲，它使用了群体搜索技术，从而产生新一代的种群，并逐步使种群进化到近似最优解的状态。遗传算法是多学科结合与渗透的产物，从产生至今已广泛地运用于包括工程设计、制造业、人工智能、计算机科学、生物工程、石油勘探、自动控制、社会科学、商业和金融等各个领域。2.1 遗传算法研究的内容遗传算法的研究主要集中在编码方法、适应函数、遗传算子、遗传算法参数选择、全局收敛性和搜索效率的数学基础、欺骗问题、收敛性分析、局部收敛及混合遗传算法等8。本文在将遗传算法应用到
16、排课问题中时，对遗传算法的编码、适应函数的设计、遗传算子、遗传算法参数的选择等进行了分析11。(1) 编码方法遗传算法的编码在许多问题的求解中，对算法的性能有很重要的影响。简单二进制编码的采用得到了Holland早期理论结果（Schema定理、最小字母表原理）的支持，但仍有很多不足之处。灰色编码可用于克服二进制编码映射的不连续问题。动态参数编码的提出是为了克服搜索效率与表示精度间的矛盾，同时对克服过早收敛现象也有所帮助。此外，多值编码、实值编码、区间值编码、Delta编码、对称编码以及将以往的合成编码分解成多个相对独立编码的独立编码策略等多种编码方法也都被证明各有优缺点。这些编码方法的提出是启
17、发式的，缺乏一个理论基础来判断各种编码方法的好坏并指导它们的设计。为解决二进制编码带来的“组合爆炸” 和遗传算法的早熟收敛问题，提出了十进制编码。根据Holland教授提出的编码应该有利于交叉变异操作的编码原则4，本文设计了适用于排课问题的编码模型。(2) 适应函数的设计在遗传算法中，适应度值是用来区分群体中个体好坏的标志。遗传算法正是根据适应值对个体进行选择的。在实际操作中，适应函数的设计对算法的收敛性及收敛速度的影响较大。本文根据排课问题的求解目标，并考虑系统与排课者的交互，设计了合理的适应度函数。(3) 遗传算子遗传算法的三个算子分别是选择、交叉和变异。选择体现“适者生存”的原理，通过适
18、应值选择优质个体而抛弃劣质个体。杂交能使个体之间的遗传物质进行交换从而产生更好的个体。变异能恢复个体失去的或未开发的遗传物质，以防止个体在形成最优解过程中过早收敛。 选择策略是遗传算法中的很重要的一个环节。由于其对遗传搜索过程具有较大的影响，很多人早就意识到它在遗传算法中的重要性。所以近年来，不同的遗传策略相继被提出。Potts等人概括了23种选择策略。Goldberg首先引入了选择算子的收敛模型，随后，他和Deb又作了扩展，并提出取代时间概念，可以对各种选择策略之间选择压力进行定量分析。Muhlenbein和Schlierkamp-Vossen讨论了选择强度在收敛分析中的应用。Back对选择
19、压力进行推广。后来为解决模式里有太大的变动或遗传算法欺骗问题，有人提出了具有破坏性选择的遗传算法。 交叉操作使不同个体间的基因相互交换。Potts概括了17种交叉方法。吴少岩等研究了交叉算子与其探索子空间之间的关系，并提出了设计良好算子的指导性原则，并构造出一种启发式交配算子。 变异是一种防止早熟的操作。Potts总结的变异技术有管理变异，变化的变异概率和单值运算。本文根据这些相关算子设计原则，设计了有利于排课操作的遗传算子。(4) 参数的选择遗传算法的群体规模、收敛判据、交叉概率和变异概率都对排课算法的效率有很大影响，但这些参数的设置还缺少相应的理论指导。由于参数选择关系到算法的精度、可靠性
20、和计算时间等诸因素，并影响到结果的质量和系统性能，因此参数选择的研究受到重视。本文各参数的设置主要是建立在实验的基础上。2.2 遗传算法的基本术语既然遗传算法效法于自然选择的生物进化，是一种模仿生物进化过程的随机算法，那么我们先分析几个生物学的基本概念与术语，这对理解和运用遗传算法是非常重要的13。(1) 染色体(chromosome)生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子基因组成。遗传因子(Gene) DNA或RNA长链结构中占有一定位置的基本遗传单位，也称为基因。生物的基因数量根据物种的不同多少不一，小的病毒只含有几个基因，而高等动植物的基因却数以万计
21、。(2) 个体(individual)指染色体带有特征的实体，在问题简化的情况下可用染色体代替。(3) 种群(population)染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小或种群的规模。有时个体的集合也称为个体群。(4) 进化(evolution)生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。(5) 适应度(fitness)在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应度高的物种将获得更多的繁殖机会，而对生存环境适应程度较低
22、的物种，其繁殖的机会就会相对较少，甚至逐渐灭绝。(6) 选择(selection)指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。正如达尔文描述的，适者生存。(7) 复制(reproduction)细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。(8) 交叉(crossover)有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，即在两个染色体的某一相同位置处被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称为基因重组(recombination)，俗称“杂交”。(9) 变异(mu
23、tation)在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。(10) 编码(coding)DNA中遗传信息在一个长链上按一定的模式排列，即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。(11) 解码(decodi ng)编码的逆过程，即从遗传子型到表现型的映射。2.3 遗传算法的基本思想通过以上分析，我们可以更好的描述遗传算法。遗传算法是从代表问题可能潜在解集的一个种群(population)开始的，而一个种群则由经过基因(Gene)编码(coding)的一定数目的个体(individual)（或染色体）
24、组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（基因型）是某种基因组合决定的。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解。在每一代中，根据问题域中个体的适应度(fitness)大小挑选(selection)个体，并借助于自然遗传学的遗传算子(geneticoperators)进行组合交叉(crossover)和变异(mutation)，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码(de
25、coding)可以作为问题近似最优解。遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与临域等。计算开始时，随机地初始化一定数目的个体(父个体1、父个体2、父个体3、父个体4、父个体N)形成初始种群，并计算每个个体的适应度函数，第一代(初始代)就产生了。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体，父代要求基因重组(交叉)而产生子代，所有的子代按一定概率变异。然后子代的适应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代(子个体1、子个体2、子个体3、子个体4、)。这一过程循环执行，直到满足优化准则为止13。遗传算法的过程如图2-1所示。
26、2.4 遗传算法的基本操作遗传算法包括三个基本操作：选择、交叉和变异。这些基本操作又有许多不同的方法。(1) 选择(selection)遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算3。 选择是用来确定重组或交叉个体，以及被选个体将产生多少子代个体。首先计算个体适应度，具体有以下算法：(a) 按比例的适应度计算(proportional fitness assignment)(b) 基于排序的适应度计算(rank-based fitness assignment) 适应度计算之后是实际的选择，按照适应度进行父代个体的选择。选择算法有：(a
27、) 轮盘赌选择(roulette wheel selection) (b) 随机遍历抽样(stochastic universal sampling) (c) 局部选择(local selection)(d) 截断选择(truncation selection)(e) 锦标赛选择(tournament selection)(2) 交叉或重组基因(crossover/recombination)遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法3
28、。基因重组是结合来自父代交配种群中的信息产生新的个体。依据个体编码表示方法的不同，可以有以下的算法： 实值重组(real valued recombination)(a) 离散重组(discrete recombination)(b) 中间重组(intermediate recombination) 二进制交叉(binary valued crossover)(a) 单点交叉(single-point crossover)(b) 多点交叉(multiple-point crossover)(c) 均匀交叉(uniform crossover)(d) 洗牌交叉(shuffle crossover
29、)(e) 缩小代理交叉(crossover with reduced surrogate)(3) 变异(mutation)遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体3。交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化。依据个体编码表示方法的不同，可以有以下的算法： 实值变异 二进制变异3 排课系统的需求分析排课系统的设计必需建立在对排课流程的详细分析的基础之上。由于各学校自身情况、采用的教学模式(学分制或学年制)的不同，导致各学校排课流程存在差异，本文以江西财经大学为分析对象，设计出适合学分制模式下
30、的高校排课算法14,15。3.1 排课系统的业务流程分析(1) 主要流程江西财经大学排课工作的基本流程如图3-1所示： (2) 教务处工作流程教务处根据各年级、各专业的培养方案，学生人数结合考虑课程性质向各个学院下达教学任务书，明确这学期的教学要求。教学任务书中要明确所要开设的课程、应开设班级数目(班别)、课程开设的校区等信息。其中，某课程应开设的班级数，是由要选修该课程的学生总数及该课程的参考容量决定的，各学院可以根据自身情况对其进行调整。教务处工作流程如图3-2 所示。 (3) 学院工作流程教学任务书下达到各学院后，各学院根据自身教师情况，可以适当调整教学任务书中某课程的开课班级数及班级容
31、量。然后，在教学任务书中为每门课程的每个班添加老师，以及该课程对教室的要求，这样形成的信息称之为课元信息。同时学院的老师可以向教务处提交特殊时间要求，如星期三下午，信息学院领导因工作会议，不能安排上课。学院工作流程如图3-3 所示。 (4) 排课流程各学院把课元信息提交给教务处，教务处根据全校教师情况，教室资源情况，老师的特殊要求利用排课系统排出预排课表，学生根据预排课表选课，教务处在学生选课后，根据各个选课班的人数，撤销人数小于15人（特殊课程除外）的选课班。课程表包括全校总课程表、学生课程表、教师课程表和教室课程表。课程表由教务处编制，不得随意变动。如因特殊情况调整，须按学校有关规定办理手
32、续，并由教务处下达调课通知。执行流程如图3-4所示。(5) 江西财经大学排课总流程江西财经大学每届新生入学前，各学院各专业已经为新生制定了在校四年的培养方案，作为在校期间学生选课的依据。其中不仅列出了学生完成学业所必需选修的公共基础课、专业课，还列出了有利于学习专业知识、扩大知识面的推荐选修课，以及这些课程在哪个学期开设。并注明了所列出的每门课程的学分，及每个学生毕业时所要修完的总学分。排课工作开始后，教务处根据各年级各专业培养方案、各年级各专业学生人数、课程性质，生成教学任务书，其包括要开设的课程名称、该课程要开设的班级数(班别)、校区等信息。教学任务书下达到各学院后，学院根据自身教师情况，修改某些课程的班级数目及相应的班级容量，之后为教学任务书添加老师，并提出课程对教室的要求，及学院老师对
