毕业设计-学分制模式下基于遗传算法的排课系统的设计.doc

普通本科毕业论文(设计)题 目: 学分制模式下基于遗传算法的排课系统的设计院 别 信息管理学院 学生姓名 王兆奇 学 号 0031718 年 级 2003级 专 业 信息管理与信息系统 指导教师 凌传繁 职 称 教授 二OO七 年 五 月论文独创性声明本人声明，所呈交的毕业论文是在导师指导下本人独立完成的研究成果。文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。本文如违反上述声明，愿意承担以下责任和后果：1.交回学校授予的学位证书；2.学校可在相关媒体上对作者本人的行为进行通报；3.本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害，进行公开道歉；4.本人负责因论文成果不实产生的法律纠纷。论文作者签名： 日期： 年 月 日摘 要排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为NP完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决NP问题非常有效。本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问题的优化目标，设计出了适合于遗传操作的编码模型，给出了合理的适应度值的计算方法。通过对初始种群进行选择、交叉、变异等过程不断进化，取得了优化的课表。在排课系统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。【关键词】学分制模式；排课系统；遗传算法；多目标优化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-constraints 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 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 course 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 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 Optimization目 录1 引言12 遗传算法22.1 遗传算法研究的内容32.2 遗传算法的基本术语42.3 遗传算法的基本思想52.4 遗传算法的基本操作63 排课系统的需求分析83.1 排课系统的业务流程分析83.2 排课因素分析103.3 排课的约束条件114 基于遗传算法的排课算法的描述124.1 排课问题的目标分析124.2 排课系统中的基本算法154.2.1 排课算法的面向对象的应用154.2.2 教室调度算法174.2.3 基因初始化算法184.2.4 冲突检测算法194.3 排课问题中遗传算法的设计194.3.1 遗传算法的编码194.3.2 初始种群的产生204.3.3 遗传操作的设计204.3.4 适应度函数的设计225 实验及结果分析225.1 排课系统开发环境225.2 参数设置对排课效率的影响235.3 结果分析266 总结与展望27参考文献2929江西财经大学本科毕业设计1 引言排课问题是高校日常教学工作和其他各项活动的基础。课程表不仅是老师和学生上课的依据，也对学校的其他工作的安排有一定影响。利用计算机辅助排课，是教学管理实现科学化，现代化的重要课题之一。目前高校招生逐年扩张，学生人数不断增加，再加上大多数高校实行学分制，课程开设逐渐向着广度和深度扩展，但学校的教学资源及设备却得不到及时补充，这些都给教务处排课人员造成很大的压力。单纯采用劳动强度大、效率低的手工排课，已成为提高教学管理质量的瓶颈。随着计算机在教学工作中的普及应用，利用计算机进行自动排课已经成为一个重要的研究课题。排课问题不仅是教学管理工作中必需面对的问题，而且也是运筹学中研究的一个问题时间表问题 (TimeTable Problems，简记TTPS)。排课问题的研究始于20世纪50年代末，但直到1963年，Gotlieb在他的文章中对排课问题进行了形式化描述并提出了排课问题的数学模型1，才标志着排课问题的研究进入科学的殿堂。但由于在实践中遇到的困难，人们对排课问题的解是否存在产生了疑问。1976年，S Even和Cooper等人证明了排课问题是NP完全问题2,3，这虽然回答了在排课实践中遇到困难的原因，但同时宣布计算机解决排课问题无法实现，因为计算机难解性理论指出，现代计算机尚未找到解决NP完全问题的多项式算法。我国对排课问题的研究始于20世纪80年代初期，所用方法从模拟手工排课到运用人工智能构建专家系统或决策支持系统。吴金荣把排课问题化成整数规划来解决4，但计算量很大，而且仅仅适用于规模很小的排课问题。何永太、胡顺仁等人试图用图论中的染色问题来求解排课问题5,6，但染色问题本身也是排课问题。基于专家系统的求解算法将专家系统知识引入排课问题的求解7，能有效组织排课过程中的知识。但由于实际排课问题存在各种各样的限制条件与特殊要求，至今没有一个有效地普遍适用的排课算法。随着现代智能优化技术的出现和发展，模拟退火算法、禁忌搜索算法、蚁群算法、遗传算法等被应用到排课问题中。模拟退火算法(Simulated Annealing)是Kirkpatrick等人于1983年首先提出的，它是人们从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题间的相似性。在对固体物质进行退火处理时，常先将它加温使其粒子可自由运动，以后随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度下降速率足够慢，则固体物质一定会形成最低能量的基态。优化问题也存在类似过程。模拟退火法被用来解决许多实际应用中的优化问题，取得了不错的效果，用其解决排课问题8，现在还处在模型实验阶段，还有许多问题要解决。禁忌搜索的思想最早由Glover于1986年提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。禁忌搜索算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。文献9中提出了结合网络流算法与禁忌搜索算法的优势，求解排课问题的方案，虽然得出了可行解，但结果不够理想，很多优化因素没有考虑。蚁群算法是随着仿生学的发展而发展起来的，它是由意大利学者M.Dorigoz在20世纪90年代初提出的，它通过模拟蚁群觅食的过程中寻找最短路径的方法来求解优化问题。文献10提出了基于二部图的排课模型，并揉合蚁群算法AS、ACS、MMAS三个不同模型的优点，提出一种面向排课问题的改进型蚁群算法，但是问题求解复杂，操作繁琐。上述算法都是一定程度上的启发搜索算法，但是搜索过程的启发信息依赖于实际情况，排课问题求解只能针对个别的实际问题，且没有引入目标优化技术，更不用说人性化方面的考虑。正是因为如此，具有智能性、并行性和高鲁棒性的遗传算法迅速应用于排课问题，并得到了很快的发展。本文正是在上述背景下展开的，在分析和实践的过程中，针对江西财经大学排课问题的具体情况，结合排课问题中常见的约束及优化目标，采用了一种适应于排课问题的编码方法，并将遗传算法应用到课表的优化，以此获得最终的排课方案。2 遗传算法遗传算法(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。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应的搜索算法。其主要特点是群体搜索策略和种群中个体之间的信息交换。由于其具有健壮性，特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。简单的讲，它使用了群体搜索技术，从而产生新一代的种群，并逐步使种群进化到近似最优解的状态。遗传算法是多学科结合与渗透的产物，从产生至今已广泛地运用于包括工程设计、制造业、人工智能、计算机科学、生物工程、石油勘探、自动控制、社会科学、商业和金融等各个领域。2.1 遗传算法研究的内容遗传算法的研究主要集中在编码方法、适应函数、遗传算子、遗传算法参数选择、全局收敛性和搜索效率的数学基础、欺骗问题、收敛性分析、局部收敛及混合遗传算法等8。本文在将遗传算法应用到排课问题中时，对遗传算法的编码、适应函数的设计、遗传算子、遗传算法参数的选择等进行了分析11。(1) 编码方法遗传算法的编码在许多问题的求解中，对算法的性能有很重要的影响。简单二进制编码的采用得到了Holland早期理论结果（Schema定理、最小字母表原理）的支持，但仍有很多不足之处。灰色编码可用于克服二进制编码映射的不连续问题。动态参数编码的提出是为了克服搜索效率与表示精度间的矛盾，同时对克服过早收敛现象也有所帮助。此外，多值编码、实值编码、区间值编码、Delta编码、对称编码以及将以往的合成编码分解成多个相对独立编码的独立编码策略等多种编码方法也都被证明各有优缺点。这些编码方法的提出是启发式的，缺乏一个理论基础来判断各种编码方法的好坏并指导它们的设计。为解决二进制编码带来的“组合爆炸” 和遗传算法的早熟收敛问题，提出了十进制编码。根据Holland教授提出的编码应该有利于交叉变异操作的编码原则4，本文设计了适用于排课问题的编码模型。(2) 适应函数的设计在遗传算法中，适应度值是用来区分群体中个体好坏的标志。遗传算法正是根据适应值对个体进行选择的。在实际操作中，适应函数的设计对算法的收敛性及收敛速度的影响较大。本文根据排课问题的求解目标，并考虑系统与排课者的交互，设计了合理的适应度函数。(3) 遗传算子遗传算法的三个算子分别是选择、交叉和变异。选择体现“适者生存”的原理，通过适应值选择优质个体而抛弃劣质个体。杂交能使个体之间的遗传物质进行交换从而产生更好的个体。变异能恢复个体失去的或未开发的遗传物质，以防止个体在形成最优解过程中过早收敛。 选择策略是遗传算法中的很重要的一个环节。由于其对遗传搜索过程具有较大的影响，很多人早就意识到它在遗传算法中的重要性。所以近年来，不同的遗传策略相继被提出。Potts等人概括了23种选择策略。Goldberg首先引入了选择算子的收敛模型，随后，他和Deb又作了扩展，并提出取代时间概念，可以对各种选择策略之间选择压力进行定量分析。Muhlenbein和Schlierkamp-Vossen讨论了选择强度在收敛分析中的应用。Back对选择压力进行推广。后来为解决模式里有太大的变动或遗传算法欺骗问题，有人提出了具有破坏性选择的遗传算法。 交叉操作使不同个体间的基因相互交换。Potts概括了17种交叉方法。吴少岩等研究了交叉算子与其探索子空间之间的关系，并提出了设计良好算子的指导性原则，并构造出一种启发式交配算子。 变异是一种防止早熟的操作。Potts总结的变异技术有管理变异，变化的变异概率和单值运算。本文根据这些相关算子设计原则，设计了有利于排课操作的遗传算子。(4) 参数的选择遗传算法的群体规模、收敛判据、交叉概率和变异概率都对排课算法的效率有很大影响，但这些参数的设置还缺少相应的理论指导。由于参数选择关系到算法的精度、可靠性和计算时间等诸因素，并影响到结果的质量和系统性能，因此参数选择的研究受到重视。本文各参数的设置主要是建立在实验的基础上。2.2 遗传算法的基本术语既然遗传算法效法于自然选择的生物进化，是一种模仿生物进化过程的随机算法，那么我们先分析几个生物学的基本概念与术语，这对理解和运用遗传算法是非常重要的13。(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)编码的逆过程，即从遗传子型到表现型的映射。2.3 遗传算法的基本思想通过以上分析，我们可以更好的描述遗传算法。遗传算法是从代表问题可能潜在解集的一个种群(population)开始的，而一个种群则由经过基因(Gene)编码(coding)的一定数目的个体(individual)（或染色体）组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（基因型）是某种基因组合决定的。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解。在每一代中，根据问题域中个体的适应度(fitness)大小挑选(selection)个体，并借助于自然遗传学的遗传算子(geneticoperators)进行组合交叉(crossover)和变异(mutation)，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码(decoding)可以作为问题近似最优解。遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与临域等。计算开始时，随机地初始化一定数目的个体(父个体1、父个体2、父个体3、父个体4、父个体N)形成初始种群，并计算每个个体的适应度函数，第一代(初始代)就产生了。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体，父代要求基因重组(交叉)而产生子代，所有的子代按一定概率变异。然后子代的适应度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代(子个体1、子个体2、子个体3、子个体4、)。这一过程循环执行，直到满足优化准则为止13。遗传算法的过程如图2-1所示。选出适应度最高的个体结束遗传操作变异操作产生初始种群满足优化准则Y选择操作N计算个体适应度交叉操作新一代群体图2-1 遗传算法的过程2.4 遗传算法的基本操作遗传算法包括三个基本操作：选择、交叉和变异。这些基本操作又有许多不同的方法。(1) 选择(selection)遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算3。 选择是用来确定重组或交叉个体，以及被选个体将产生多少子代个体。首先计算个体适应度，具体有以下算法：(a) 按比例的适应度计算(proportional fitness assignment)(b) 基于排序的适应度计算(rank-based fitness assignment) 适应度计算之后是实际的选择，按照适应度进行父代个体的选择。选择算法有：(a) 轮盘赌选择(roulette wheel selection) (b) 随机遍历抽样(stochastic universal sampling) (c) 局部选择(local selection)(d) 截断选择(truncation selection)(e) 锦标赛选择(tournament selection)(2) 交叉或重组基因(crossover/recombination)遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法3。基因重组是结合来自父代交配种群中的信息产生新的个体。依据个体编码表示方法的不同，可以有以下的算法： 实值重组(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)(e) 缩小代理交叉(crossover with reduced surrogate)(3) 变异(mutation)遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体3。交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化。依据个体编码表示方法的不同，可以有以下的算法： 实值变异 二进制变异3 排课系统的需求分析排课系统的设计必需建立在对排课流程的详细分析的基础之上。由于各学校自身情况、采用的教学模式(学分制或学年制)的不同，导致各学校排课流程存在差异，本文以江西财经大学为分析对象，设计出适合学分制模式下的高校排课算法14,15。3.1 排课系统的业务流程分析(1) 主要流程江西财经大学排课工作的基本流程如图3-1所示：教务处下达教学任务书学院按教学任务书安排教师，提出相关要求教务处编排、调整课表图3-1 基本流程 (2) 教务处工作流程教务处根据各年级、各专业的培养方案，学生人数结合考虑课程性质向各个学院下达教学任务书，明确这学期的教学要求。教学任务书中要明确所要开设的课程、应开设班级数目(班别)、课程开设的校区等信息。其中，某课程应开设的班级数，是由要选修该课程的学生总数及该课程的参考容量决定的，各学院可以根据自身情况对其进行调整。教务处工作流程如图3-2 所示。各年级、各专业培养方案各年级、各专业学生人数课程性质制定教学任务书教学任务书教务处图3-2 教务处工作流程 (3) 学院工作流程教学任务书下达到各学院后，各学院根据自身教师情况，可以适当调整教学任务书中某课程的开课班级数及班级容量。然后，在教学任务书中为每门课程的每个班添加老师，以及该课程对教室的要求，这样形成的信息称之为课元信息。同时学院的老师可以向教务处提交特殊时间要求，如星期三下午，信息学院领导因工作会议，不能安排上课。学院工作流程如图3-3 所示。调整课程班级及容量、安排教师学院提出特殊要求时间要求课元信息表教学任务书教师信息图3-3 学院工作流程 (4) 排课流程各学院把课元信息提交给教务处，教务处根据全校教师情况，教室资源情况，老师的特殊要求利用排课系统排出预排课表，学生根据预排课表选课，教务处在学生选课后，根据各个选课班的人数，撤销人数小于15人（特殊课程除外）的选课班。课程表包括全校总课程表、学生课程表、教师课程表和教室课程表。课程表由教务处编制，不得随意变动。如因特殊情况调整，须按学校有关规定办理手续，并由教务处下达调课通知。执行流程如图3-4所示。安排、调整课表课程表课元信息表时间要求培养方案教室资源信息教务处图3-4 排课流程(5) 江西财经大学排课总流程江西财经大学每届新生入学前，各学院各专业已经为新生制定了在校四年的培养方案，作为在校期间学生选课的依据。其中不仅列出了学生完成学业所必需选修的公共基础课、专业课，还列出了有利于学习专业知识、扩大知识面的推荐选修课，以及这些课程在哪个学期开设。并注明了所列出的每门课程的学分，及每个学生毕业时所要修完的总学分。排课工作开始后，教务处根据各年级各专业培养方案、各年级各专业学生人数、课程性质，生成教学任务书，其包括要开设的课程名称、该课程要开设的班级数(班别)、校区等信息。教学任务书下达到各学院后，学院根据自身教师情况，修改某些课程的班级数目及相应的班级容量，之后为教学任务书添加老师，并提出课程对教室的要求，及学院老师对上课时间的要求(如某个时间段不能安排课程)，这样就形成了课元信息。学院再将课元信息提交教务处，教务处根据教师情况，教室资源情况，老师的特殊要求利用排课系统排出预排课表，学生根据预排课表选课，教务处在学生选课后，根据各个选课班的人数，撤销人数小于15的选课班。教务处可以根据具体情况调整课程表，并下达调课通知。执行流程如图3-5所示。安排教师课元信息表各年级、各专业培养方案各年级、各专业学生人数课程性质教师信息学院安排、调整课表教务处时间要求培养方案教室资源信息制定教学任务书教学任务书提出特殊要求教务处课程表图 3-5 排课总流程时间要求3.2 排课因素分析排课工作是教学工作顺利进行的基础工作，排课问题涉及到的因素也几乎是全校性的。从排课可能引起的冲突的角度来考虑，排课涉及到的因素如下： (1) 时间因素 在排课问题中涉及到的时间因素主要有学年、学期、周、天、时段、节次等。一般我们按照周课表来上课，从开学第一周到第N周，江西财经大学每上学上课16周。一周上课天数M7，一般学校一周上课5天(二专周六、日上课，本文不作考虑)。每天上午分两个时间段(片)，每个时间段两节课，下午和晚上各一个时间段，每个时间段三节课。这样一周有20个时间段。(2) 课程因素课程有课程编号、课程名称、课程的周学时、课程学分、课程对教室类型的要求、所属学院等。每门课程可以有指定的老师授课，也可以没有。课程因素还包括开设的班级数及课程开设的校区等。(3) 教室因素 每个教室都有教室编号，教室代号及所属的教学区域。每个教室都有教室类型，教室类型包括普通教室、多媒体教室、语音教室、实验室、机房、体育馆等。每个教室都有一定的容量，教室的容量必须不小于上课的人数。(4) 教师因素每个教师都有自己的编号及姓名，每个教师都隶属于一个学院，教师可以对上课时间提出自己的特殊要求。同一时间老师只能上一个教学班的课。(5) 班级因素本文所涉及的班级均指的是教学班（选课班或行政班）。如前面的分析，教务处下达的教学任务书里规定了开设的课程名称、班别、开设的校区等。其中课程名称，班别，校区编号唯一决定一个选课班。每个选课班都有一个的最大选课人数的限制。(6) 校区因素每个校区都有编号和名称。其中蛟桥园编号为“A”，麦庐园为“B”，枫林园为“C”。当老师、学生在不同校区上课时，应该留有一定的时间用于赶赴。根据江西财经大学课间时间的安排，上午两个时间段之间留有40分钟的时间，上午跟下午，下午跟晚上的上课时间间隔在90-120分钟之间，所以赶赴的时间本文不予考虑。3.3 排课的约束条件排课问题中，主要任务是将班级、教师、课程安排在一周内某一不发生冲突的时间和教室，保证课表在时间的分配上符合一切共性(时间上不存在冲突)和个性(不与老师的特殊时间要求冲突)的要求，在此基础上，使其安排在各个目标上尽量达到最优。一张可行的课表首先要满足排课因素的约束。这里的约束条件主要是避免冲突。只有在满足全部约束条件和避免所有冲突的基础上，才能保证整个教学计划合理正常进行。对教师、班级、课程、时间、教室等几部分资源进行最优化配置，才能保证排课的顺利完成以及充分发挥各个资源的优势以达到提高管理水平和教学质量的目的。根据是否必须满足，我们可以将约束条件分为硬约束和软约束。硬约束是指教师、班级、教室、校区在时空概念上发生了不可能发生的事情，也就是发生了冲突。它是在排课过程中需要满足的最基本的约束条件，是排课时必须遵循的原则，否则将会导致排课结果无意义。软约束则是指排课过程中若满足则更佳，不能满足也不影响教学的开展的约束条件。它能够使课表更加合理，更加具有人性化16，它影响排课结果的好坏。通常，排课方案的标准有多个，以下是按照江西财经大学的校情制定的约束条件。(1) 硬性约束条件 同一时间同一班级只能上一门课； 同一时间同一教室只能上一门课； 同一时间同一教师只能上一门课； 教室的容量必须不小于或等于实际上课的人数； 所分配的教室类型必须与课程所要求的教室类型一致； 课程必须安排在教学任务书所规定的校区。(2) 软性约束条件 每个时间段安排的课程数尽量均匀； 一周的课表中每个上课时间都有一定的优度，尽量将课程安排在优度高的时间段； 一门课程的多次上课的时间尽量间隔并分布均匀； 教室容量适中，以充分利用教室； 两个课时的课程尽量不要安排在下午或晚上，以免造成一个课时的浪费。4 基于遗传算法的排课算法的描述本文前面已经对遗传算法、排课流程、排课因素及排课的约束条件进行了分析，下面结合上述分析将遗传算法具体应用到排课算法的设计过程中。4.1 排课问题的目标分析根据江西财经大学的校情，本文确定了五个目标，分别为：教室利用度、节次优度、课程日组合优度、时间片利用度、课程的时段分布均匀度。下面分别介绍这五个目标17。(1) 教室利用度教室利用度，是衡量所开设的课次的教室利用程度的好坏标志。其计算方法如下： (4.1)式中 所有课次的教室利用率的平均值 第i个课次的教室利用率 课次总数值越大，我们认为排课方案的教室利用率越高。(2) 节次优度节次优度是对某一时间片上课效果好坏的量化。我们为每一个时间片赋予不同的优度值以表示对这个时间片的偏好程度。节次优度含有一定的主观因素，每个人对同一时间片的偏好不同，不同的季节同一个时间片的上课效果也会有差别。我们可以让排课人员来设置每个时间片的节次优度，以体现不同人，不同学期的要求。如学年的第一个学期进入到冬季时，上午1、2节比3、4节的节次优度可能低些，因为天冷部分同学不愿早起上课。第二学期进入到夏季时，下午的时间片的节次优度要低些，因为此时上课，效果会差些。本系统采用的节次优度值如表3-1所示。表4-1 节次优度表时间片星期一星期二星期三星期四星期五上午1、2节0.950.990.970.940.92上午3、4节0.850.890.870.840.82下午5、6、7节0.450.490.570.510.52晚上8、9、A节0.550.590.570.510.52我们用全校课程的节次优度的平均值来衡量排课方案中节次安排的好坏，即对开课方案中每个课次的节次优度进行累加，再除以总的课次数。 (4-2)式中 全校课程的节次优度的平均值 第i个课程的第j个时间段的节次优度 第i个课程的时间段的个数 所开设的课程的总数的值越大，我们认为排课方案的节次优度越好。(3) 课程日组合优度课程的日组合优度，是衡量每周上课次数大于1的课程的多次上课的日组合优度好坏的标志。我们对所有的课程的日组合优度进行优度判定。例如：一个周学时为6的课程，每周上课3次，每次两个课时，如果这三个时间片分别为周一的1、2节、周三的3、4节、周五的1、2节或者周一的3、4节、周三的1、2节、周五的3、4节，则我们认为该课程的日组合优度为1。如果一门周学时为4的课程，分别安排在周二的3、4节、周三的1、2节，则我们认为该课程的日组合优度为0.2。当然，有些课程属于例外，例如两节理论假两节实验则可以间隔较短的时间；有些课程设计则需要连续进行。我们可以利用全校的所有周上课次数大于1的课程的日组合优度的平均值来衡量课程表中日组合优度的优劣。 (4.3)式中 全校所有周上课次数大于1的课程的日组合优度的平均值 课程i的日组合优度 周上课次数大于1的课程总数值越大，说明课表中非2课时的课程日组合优度越大。(4) 课程时间片利用度课程的时间片利用度，是衡量该课程的每次上课对所分配的时间片的利用情况的标志。例如：一个周学时为2的课程，如果为其分配的时间片是在上午(1、2节或3、4节)，则其时间片利用度为1，如果在下午或晚上，则会造成一节课时间的浪费，其时间片利用度就为0.3。 (4.4)式中 所有课程的时间片利用度的平均值 课程i的第j个时间片的利用度 课程i的所分配的时间片的个数 所开设的课程的总数的值越大，说明课表的所有课程的时间片利用度越高。(5) 课程时间段分布均匀度课程的时间段分布均匀度的作用是使每个时间段所安排的课程的数目相对均匀，避免出现某个时间段的课程过于集中，某个时间段没有课的现象。如果安排在每个时间段的课程的数目越均匀，同样数目的课程对资源的需求就越少。课程的时间段分布均匀度为： 其中 (4.5)式中 课程的时间段分布均匀度