基于迭代搜索算法的研究生排课系统的研究与实现.doc

1、北京林业大学硕士学位论文论文题目：基于迭代搜索算法的研究生排课系统的研究与实现 作者姓名 指导教师 学科专业 所在学院 提交日期 2012年3月北京林业大学学位论文原创性声明本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得北京林业大学或其它教育机构的学位证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律责任。作者签名：日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的

2、规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密，在_年解密后适用本授权书。2、不保密。（请在以上相应方框内打“”）作者签名：日期： 年 月 日导师签名：日期： 年 月 日摘要高等学校智能排课系统具有其固有的复杂性，其本质是一个多资源约束分配问题，需要周密的思考和研究以及不断的实践过程。高校排课是教学运行管理中非常重要的环节之一，排课系统中涉及的资源包括教师、教室、课程、班级、时间段五个元素，而这些资源都是有限的，怎样准确、合理、快速无误地编排好课表已成为高校管理中

3、一大热点和难点。本文深入研究了国内外排课系统的现状，分析了排课核心算法，根据高等学校中课程限制较多的特点，用基于约束模型的迭代搜索算法来求解排课问题，并提出了高等学校课程排课问题的解决方案；在此基础上，本文结合研究生排课工作信息化工作，建立了针对学校排课问题的排课模型，设计出高效的排课算法，并以J2EE为技术平台，设计和实现了建立在B/S架构之上的排课系统。并根据排课问题的特点，建立约束模型，提出了约束满足、安排等模型概念。采用迭代搜索算法解决排课问题，根据课程、教室、时间、教师、学生等排课中需要考虑的因素进行约束化，再根据约束模型进行搜索安排，得出符合研究生要求的课程安排。实验结果表明，用约

4、束模型解决排课问题是可行的。关键词：排课；约束化；约束满足；迭代搜索Input your English Title of your articleMaster Candidate: Input your name(Input your Major)Directed by Input your DirectorABSTRACTCollege Intelligent Timetabling System has its inherent complexity, its essence is a resource constraints and more assignment problem, n

5、eed careful thought, study and constantly practice process。UniversityTimetabling is one of the important link of the Teaching Operating Management, including five elements，those are teachers，classrooms，resources，class，and the time，and these resources are limited，how to layout good schedule with accu

6、rately reasonably, and fast，it has become a hotspot and difficulty problem in the UniversityManagementCourse Scheduling System status quo at home and abroad, in-depth study and analysis of the Timetable core algorithm, according to the characteristics of the Higher course is more limited, with the c

7、onstraint model-based iterative search algorithm to solve the course timetabling problem and proposed Highercourse Timetable solution to the problem; on this basis, the combination of graduate the Timetable work of information technology work for schools Timetable Timetable model design efficient Ti

8、metable algorithm, and the J2EE technology platform。design and implementation of the Course Scheduling System built on top of the B / S structure。And the characteristics of the course timetabling problem, the establishment of the constraint model, constraint satisfaction, arrangements model concept。

9、Iterative search algorithm to solve the course timetabling problem, according to the factors to be considered in the curriculum, classroom time, teachers, students, etc。Timetable constraints of search arrangements according to the constraint model, and come to meet the graduate requirements of the c

10、ourse arrangements。Experimental results show that the constraint model to solve the course timetabling problem is feasibleKey words: Timetable; constraints; constraint satisfaction; iterative search目 录第一章 引言21。1 研究的背景及意义21。2 国内外研究现状31。2。1 国外研究现状31。2。2国内研究现状51。3论文研究内容和框架8第二章 主要排课研究算法分析92。1 遗传算法92。1。1

11、 GA的特点92。1。2 GA的演算过程102。1。3 GA算法解决高校排课问题112。2 蚁群算法162。2。1 数学模型172。2。2 用蚁群算法解决研究生排课问题182。2。3 排课问题的结果分析202。3回溯算法212。3。1 回溯算法改进212。3。2 用改进型回溯算法求解研究生排课问题222。3。3 算法的实现23第三章 研究生排课问题分析和求解253。1 排课问题概述253。2 研究生排课问题的数学描述263。2。1 研究生排课问题因素263。2。2 排课问题中约束的描述273。2。3 排课问题的优化求解模型273。3 研究生排课问题的求解方案28第四章 用约束模型求解研究生排课

12、问题294。1 排课问题的描述294。1。1课程分类294。1。2硬约束和软约束304。1。3 排课问题的数学模型314。2 迭代搜索算法324。3 实验与分析354。3。1 系统说明354。3。2 算法验证36第五章 总结与展望385。1 总结385。2 展望381引 言11 研究的背景及意义学校的课表安排工作是一项既基本又重要的教学管理活动。它是学校建立稳定教学秩序的基本保证，也是影响教学质量的决定因素之一。随着国家对教育事业的重视，学校的招生规模也在迅速扩大。但是，可利用的教学资源始终是有限的，这就给课表安排带来了巨大的挑战。因此，根据不同学校的实际情况，设计出高效的算法以安排出科学、合

13、理、人性化的课表具有重要的现实意义。课表安排需要考虑多方面的主客观因素。从学生的角度出发，为使其有利于提高学习效率，应让课时分布均匀、课程时间间隔合理。从教师的角度出发，具体要考虑教师的授课时间的均衡性，不要在同一天或连续两天内安排较多的课程，以防止教师过度疲劳，影响教师健康和教学效果。此外，目前大多数大学学生上课都没有固定的教室，有些大学甚至是异地跨校区教学，如果课程之间的连续组合不科学，则容易导致学生和教师在课间经常要奔波于不同教学楼之间，因此，在课表安排过程中应当尽量避免出现这种时间紧张的情况。从资源的利用角度出发，有些实验室的器材和设备长时间使用容易加速其损耗，而有些体育场地如游泳池等

14、则不适宜长时间闲置，因此，安排出的课程表应要能发挥教学资源的最大功能，达到经济效益的最大化。由此可见，不同对象对课表的约束需求侧重点各有差异，还有可能互相制约，所以，满足所有约束条件的课表是不可能存在的，追求这种完美的课表也是不切实际的。同时，不同的国家由于教育制度、风俗文化和作息时间都有比较大的差异，甚至在同一个国家，不同学校的教学方式也各有特点，相应的课表安排问题特征可能截然不同，因此，万能的课表安排算法也是不存在的。针对不同的课表安排问题，我们需要分析其根本特征，在借鉴各种成功的优秀算法和思想的基础上，根据每个学校的实际情况设计出最高效的算法。课表安排问题是一个关于组合优化的NP完全问题

15、，迄今还没有找到一个完全解决这个问题的精确多项式算法，目前研究的重点方向主要定位在设计出简单、高效而又比较通用的启发式排课算法。Cooper and Kingston的工作证明了时间表调度问题在只考虑某些约束的情况下可以转化到图着色(Graph Coloring)问题1。例如，对于课表安排问题和图着色问题，如果我们将课程对应于图中顶点，将课程之间的冲突关系对应于图中的边，将不同课时对应于不同颜色，那么将课程安排到特定的课时则可以看成是给对应的顶点染上对应的颜色。但是，课表安排除了要求有冲突的课程不能安排到相同的课时外，还需要考虑其它的约束条件，所以，要将课表安排问题完整归约到图着色问题，还必须

16、增加更多的附加约束。图着色是一个有着良好的研究基础的经典图论问题，很多学者已经将图着色的一些优秀算法和思想借鉴到了课表安排当中去。同样，课表安排问题的一些高效算法通过改进也可以运用到图着色等其它组合优化问题上。可见，研究课表安排问题也是探索NP完全问题的一种有效途径，并且可以深化我们对NP完全理论的认识。综上分析，研究课表安排问题具备广泛的实际应用价值和重要的理论意义。12 国内外研究现状121 国外研究现状国外从20世纪50年代末就对这个课题开展了研究。1963年，Gotlieb在他的文章The Construction of Class-Teacher Time-Tables(课程时间表的

17、构造结构)中提出一个课表问题的数学模型2,3。此后，人们对课表问题的算法、解的存在性等问题做了很多深入探讨，但是大多数文献所用到的数学模型都是Goflieb的数学模型的简化或补充，而至今还没有一个较为可行的算法来解决课表问题。Bondy于1976年提出了一个简单的排课表问题，将问题归结为一个图的边染色问题，并且对提出的简单排课表问题给出了一个算法4。然而，实际教学活动中的排课表问题远非如此简单，且由于它必须满足各种复杂约束条件而使这种算法实际上是无能为力昀。1976年S。Even在论文On The Complexity of Time Table And Multi Commodity Flo

18、w Problems (关于时间表和多物质流问题的复杂性)中，证明了课表问题是NP完全的，这虽然回答了计算机编排课表在实践中遇到困难的原因，但同时等于宣布计算机编排课表是无法实现的，因为计算机难解性的理论研究指出，现代计算机尚未找到解决NP完全类问题的多项式算法5。此后这一课题的研究大多离开理论研讨的轨道而转向经验方式，这使80年代的许多课表编排系统缺乏普适性SEven的论证正式确立了课表问题的学术地位，把人们对课表编排复杂性的认识提高到了理论的高度6,7。从1963年Gotlieb提出了一个排课问题的数学模型之后，人们又对排课问题的算法作了许多探索，但由于排课问题是NP完全问题，并且易受实际

19、问题边界的影响，大多数求解结果都不理想8。Ferland等人和吴金荣把排课问题化成整数规划来解决，但计算量很大，其仅仅适用于规模很小的课表编捧，对于大规模复杂的排课情况，至今没有一个切实可行的算法9；还有何永太和胡顺仁等人试图用图论中的染色问题来求解排课问题10，可惜图的染色问题本身也是NP完全问题。由于问题的复杂，还有人利用启发式函数来解决排课问题，大多数启发方法都是模拟手工排课的过程来实现的11。由于实际的排课问题存在各种各样的限制条件与特殊要求，对这些因素处理的好坏就显得尤为重要。进入20世纪90年代，国外对排课问题的研究仍然非常活跃。例如印度Vastapur大学管理学院的Arabind

20、aTripathy、加拿大Montreal大学的JeanAubin和JacquesAFerland以及Charles Fleutent等12。Arabinda Tripathy的工作是针对以人”为单位进行课表编排的13,14。他运用拉格朗日松弛法和分支定界技术求解，这种方法的缺点是为了减少变量的个数，人为造成科目问的冲突。A。Tripathy还研究了研究生课表编排问题，他采用多重课组的方法来处理冲突(根据学生选课的矛盾情况，将人数多的课程在一星期内开多次)。JacquesAFerland等人则把排课问题分成两个子问题15：时间表问题和分组问题。在时间表问题中，根据学生注册情况、教师和教室的可利

21、用情况形成一个主时间表。对于选课人数较多的大课，一个星期要分成几个时间段来上，分组问题就是将学生分给各时间段。两个问题相关联，通过惩罚因子来构造启发卤数。他们研制的SAPHIR课程调度决策支持系统分为数据处理、自动优化、交互优化等几个模块16。该系统解决矛盾的主要方法也是采用多重课组。这与西方的教学管理体制不可分的。另外一批学者还将模拟退火法应用到排课问题的研究中17。模拟退(simulated Annealing)是Kirkpatrick等人于1983年首先提出的，它是人们从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优化问题的出发点是基于物理中固体物质的

22、退火过程与一般优化问题的相似性18。在对固体物质进行退火处理时，常先将它加温使其粒子可自由运动，以后随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度下降速率足够慢，则固体物质定会形成最低能量的基态，优化问题也存在类似过程。模拟退火法被用来解决许多实际应用中优化问题，取得了不错的效果，但用其解决排课问题，现在还处在模型试验阶段，还有许多问题要解决。为了能用计算机管理教学调度工作，国外对排课算法做了很多研究，开发出相应的通用自动排课系统。但从实际使用情况来看，实用性上仍不尽如人意19。由于国外软件未考虑教室的约束因素，普遍没有考虑教室资源不足的问题，而我国近几年高校扩招，教室资源普

23、遍紧张，不符合我国的实际，不适用于我国高校教室紧张的情况。122国内研究现状我国对这一课题的研究起步比较晚，清华大学1984年在清华大学学报(自然版)上发表了林漳希和林尧瑞在该课题上的实验性研究成果20，接着当时的南京工学院、大连理工学院等高等院校都相继开展了这方面的研究工作。所用方法从模拟手工排课到运用人工智能构建专家系统或决策支持系统都有。基于时间位图迭加匹配的算法定义了教学过程中的时间位图、课时模式和时问匹配等概念，将排课问题转化为基于时间位图迭加匹配的课时模式查找问题，给出了相应的抽象具体排课过程，并对于排课过程中可能出现的冲突，探讨了三种回溯消除冲突方式21。基于优先级自动排课算法利

24、用了运筹学中分层规划的思想，把排课问题在数学上看作是一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊要求为约束条件的组合规划问题，采用了化整为零的思想及提出了优先级的概念，有效地抽象了实际排课情况，缩小了求解问题的空间。基于专家系统的求解算法将专家系统知识引入排课问题的求解中，有效组织排课过程中的知识，使各种排课逻辑从程序中解放出来，能够便于各种排课经验的累计，使排课结果更加符合实际情况22,23。更多算法已经提出，它们都是一定程度上启发搜索求解方法，虽然对后继者有一定的借鉴意义，但它存在以下几点不足之处：l，对于启发式搜索技术来说，搜索过程的启发信息依赖于实际情况，排课问题的求解只

25、能针对个别的实际问题，不能形成一种通用的有效排课方法。2、引入专家系统技术的排课方法，虽然可以对排课规则知识有效组织，但由于排课过程中各要素关联规则的难以提取，并且实际求解效果也不理想。3、没有引入目标优化技术，课表的优劣判定的论述甚少，只能在问题的某个方向进行搜索，不可能达到多个目标同时优化。国内一些高等院校也进行了很多相关软件的开发研制工作。例如，西南交通大学在分析高校课表编排所遵循的基本原则和模糊性原则的基础上，定义了课元之间，关于教师的相关关系和关于自然班的相关关系，提出以课元相关运算和课元的候选时空片计算为核心的计算机排课算法；延边大学根据高校课程表的制作特点，设计了计算机自动排课的

26、数据结构与算法24；沈阳电力高等专科学校研制了基于C/S的开放式智能排课系统；山西大学在总结排课工作经验的基础上，提出了一种解决问题的形式化描述，在这种想法上实现了基于知识推理的排课系统；大连理工大学1998年推出的的教学调度系统3。00版本，由清华大学计算机与信息管理中心开发的综合教务管理系统等等25，所有这些系统都是模拟手工排课过程，以班为单位，运用启发式函数来进行编排的。从实际使用情况来看，这些软件系统在实用性上仍不尽如人意。l、国内的排课软件系统很少，涉及到自动排课算法的系统更少，大部分都仅仅局限于辅助人工排课，并没有任何。智能”钓成分。2、仅有的几套自动排课系统往往由于在随机求解过程

27、中出现太多的未被安排课程使得后期人工调整的工作量并不比重新排课的工作量小很多，系统很难在实际中使用。3、每个学校由于其各自的特殊性，这些排课系统往往比较依赖于各个学校的教学体制，不宜于进行广泛推广。随着人工智能的发展，特别是在计算智能领域的拓展，借鉴于生物界进化思想和遗传机制的遗传算法，由于其超群的并行搜索能力，以及在解决优化问题中表现出来的高度鲁棒性，它己经被广泛应用于各个领域26。作为一种随机的优化与搜索方法，遗传算法有着两个主要特性：1智能性。即遗传算法在确定了编码方案、适应值函数及遗传算予以后，算法将利用演化过程中获得的信息自行组织搜索。适应值大的个体具有较高生存概率，它是具有“潜在学

28、习能力”的自适应搜索技术。2并行性。由于遗传算法采用种群的方式组织搜索，从而可以同时搜索解空间内的多个区域，并相互交流信息，这种搜索方式使得它虽每次只执行与种群规模成比例的计算，而实质上，据Goldberg DE推算已进行了大约O(N3)次有效搜索。这使得遗传算法能以较少的计算获得较大的收益。正是由于遗传算法的两个特性，使得遗传算法迅速被运用于求解组合优化的排课问题。ChuPC和Beasley对一般的安排问题中使用了遗传算法进行求解嘲，他们着重于遗传算法的全局最优解的搜索能力，避免了问题的局部最优解。日本的Sigeru用具有控制约束的遗传算法来解决大学排课问题，提高了遗传算法的搜索效率27。姚

29、新使用遗传算法优化了教师的合理利用，解决了在教室较少的情况下，如何对教室的利用进行合理的分配。针对高中课程的特点，意大利的Colomi等人使用遗传算法解决了排课问题。张春梅等人对大学课程进行分类，并对不同的课程使用具有自适应能力的遗传算法进行了安排。Philippines的Ho Sung C。Lee使用遗传算法对Philippines大学的数学学院排课问题进行了求解28。杨宇对分别使用遗传算法对局部排课问题和全局排课问题进行了求解他们运用遗传算法针对自身所描述的排课问题进行求解，虽然在一定程度上取得了喜人的成果，但综合考虑求解情况，有以下几点不足：1求解问题的边界定义。由于各自的研究背景不同，

30、他们考虑的往往是排课一般情况，有些甚至是理想状态的排课，对于排课中更多的约束条件未予以考虑，而且问题的求解规模普遍偏小，使得实用程度较低，很难在学校中展开使用。2问题的编码。一种较好的遗传算法的编码方式，不仅能够反映解空间完备并无歧义的遗传信息，而且操作尽量简单，从而可以快速遗传操作和适应度评定，继而影响算法整体的收敛时间。在以往的研究中，他们编码虽然通俗易懂，但不能很好地反映针对更多实际情况的遗传信息，而且操作很不方便。3求解的目标。以往的应用中，采用惩罚函数的居多，处理的都是单目标问题，即使有多个目标，往往也线性聚合成一个目标进行处理。这在多目标优化理论中，往往求解所得的是一个非劣解，而忽

31、略了一组非劣解。13论文研究内容和框架论文 基于迭代搜索算法的研究生排课系统共有五章：第一章 : 引言。分析论文的研究背景，并确定论文的研究方案和框架。第二章 : 分析了研究生排课中存在的问题，分析排课问题的影响因素，对排课问题中约束进行描述，找到排课问题的优化求解模型。第三章 : 对研究生课程排课问题进行数学描述，确定排课问题的因素，排课问题中的约束描述，找出排课问题的优化求解模型。第四章 : 用约束模型求解研究生排课问题，首先对研究生课程具体的课程进行分类，对硬约束和软约束进行参数，说明迭代搜索的数学模型，并通过JAVA语言开发一个原型系统，证明了改算法的有效性。第五章 : 总结和展望。总

32、结论文的主要创新点以及不足之处，并对后续研究做展望和计划。n 研究内容研究迭代向前搜索算法，在一定的时间内找到最满足用户条件的课程表。研究排课过程中考虑每一个学生的因素，充分体现以人为本的思想，将教师、教室、课程、学生等因素结合起来，建立算法模型。n 重点解决的问题考虑每个学生的因素。为了发挥学分制的优势，实施先选课后排课，排出的课表要充分考虑每个学生的时间、地点约束，尽量做到让最多的学生所选择的课程在时间、地点上不冲突，最后再手工调整小部分冲突的学生。n 创新点：新的排课算法迭代向前搜索算法，与现在国内的排课算法都不一样。引入约束模型把所有的课程需求都转为约束条件，与迭代向前搜索算法相结合。

33、先选课后排课的排课流程设计充分考虑学生的选课要求，现存的排课系统都是以班级为学生的组织单位，先排课后选课的模式，扼杀了学生的选课自由度，没有考虑到学生的课程合理性。使用先选课后排课的模式，考虑每个学生的时间、教室约束，使得排课结果更合理，更具人性化。引入学生分配算法满足先选课后排课的需求而设计的，学生分配算法独立于迭代向前搜索算法，但是同时迭代向前搜索算法中又使用到了学生分配算法。2主要排课研究算法分析自动排课系统实际上是时间表的优化问题，目的是协助教务管理人员完成高校课程表的编排工作。排课的主要任务是对教师、教室、班级、时间、课程5个因素进行最优化组合配置，保证充分发挥各资源优势和提高教学质

34、量。21 遗传算法遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是美国Michigan大学J。Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J。Hilland教授所提出的GA通常为简单遗传算法(SGA) 29,30。211 GA的特点遗传算法是一类可用于复杂系统优化的具有鲁棒性、全局最优性、可并行处理性及高效性的搜索算法，体现了自然界“物竞天泽，适者生存的进化过程，在函数优化、组合优化、生产调

35、度、机器学习、图像处理、模式识别等多个领域得到了广泛的应用31，由文献可知，与传统的优化算法相比，主要有以下特点：(1)遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际值本身，而遗传算法处理决策变量的某种编码形式使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。(2)遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。仅用适应度函数值来评价个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定，这一特点使得遗传算法的应用范围得到扩大。(3)遗传算法使用多个点的

36、搜索信息，对多个解进行评估，减少了陷入局部最优解的风险，同时实现了隐含并行化。(4)遗传算法使用概率搜索技术，而非确定性规则。(5)具有自组织、自适应和自学习性。利用进化过程获取的信息自行组织搜索，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构，适应度小的个体也有生存的可能性，这样既保证了群体的多样性，也使得较差个体中的优秀基因得以保存。212 GA的演算过程运用遗传算法求解问题，首先需要将所求解的问题进行编码，然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，即编码的适应度32。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁

37、殖过程前的编码样本。选择机制应保证适应度较高的个体能够保留较多的样本，而适应度较低的个体则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是问题的最终结果33。由此可见，遗传算法采用的是类似基因演化的循环过程，概括地讲其演算过程如下：随机产生一定数目的初始种群；对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及

38、其代表的最优解，并结束计算，否则转向第步；依据适应度选择再生个体；按照一定的交叉概率和交叉方法生成新的个体；按照一定的变异概率和变异方法生成新的个体；由交叉和变异生成新一代的种群，然后返回第步。可知遗传算法的伪码描述：BEGIN：I=0；Initialize P(I)；Fitness P(I)；While(not Terminate-Condition)I+；GA-Operation P(I)；Fitness P(I)；END213 GA算法解决高校排课问题应用遗传算法来解决高校的排课问题有很多案例，本人通过查阅相关资料并进行分析研究，给出一种用遗传算法来解决高校排课问题的经典案例。(1)基因

39、编码及染色体表示在遗传算法的设计过程中，首先要确定编码方案，在经典的遗传算法中常采用整数编码、浮点编码、DNA编码、二进制编码等方法，编码方式的优劣关系到信息的完备表达、遗传操作算子的设计和执行效率，最终直接影响到收敛速度34,35。高校排课一般只考虑周课表，根据课表的实际特点，我们采用矩阵编码，一个矩阵Y表示一个可能的排课表。矩阵Y的行标题为班级名称，列标题为教学时间片，每个学校可以根据自己的实际情况来划分时间片，进而确定时间片的多少，也就是确定矩阵的列数。在这里首先对排课系统中几个重要的数据库表进行说明：本学期的课程信息表记录了本学期每门课程的信息，包括课程编号、课程名称、课程性质、总学时

40、、任课教师、开课班级、教室要求等字段；班级信息表包括班级编号、班级名称、人数等字段；教师信息表包括教师编号、教师姓名等字段；教室信息表包括教室编号、教室类型、可容纳学生数、是否已排课等字段。可以根据班级信息表以及它与本学期课程信息表的关系，找到每个班的所有课元，再根据这些课元以及本学期课程表和排课表之间的关系，找到这个班的所有排课元。每周5天，把每天上课的时间分成时间片，大学的课程一般都是两节连上，假定每天有三个时间片，每周5天，共涉及15个时间片，用t1，t2，t15来表示。将这15个时间片随机的分配给上述某个班的所有课元，也就排好了一个班的课表。一个班的“排课元的数目一定小于或等于15，如

41、果小于15则有时间片未用到。把班级和教室作为一个变量来对待。对于班级而言，因为某个学期开的课程和教师是固定的，因此可以把课程和教师作为一个变量来对待(可以用教师+课程的编号来代替这个变量)。通过以上把班级和教室等同、课程与教师等同的处理之后，原课表的五要素就转换化为班级、课程、时间三要素了，把班级固定要上的课看作基因，染色体在这里就是所有班级和15个时间片组成的二维表。(2)建立初始种群建立初始种群只要随机产生一定数量的染色体即可，并且要使产生的这个染色体是可行的，也就是说要满足课表编排的约束条件，数学模型分析如下：1)初始种群解空间解空间X是该班所有课程得到编排的课表，解可以表示为xl，x2

42、，xls，Xl，x2，X15是1，2，15的一个排列，表示一周授课的教学时间单元，xj表示在j时间单元的课程代号，初始解可选为(0，0)，表示未编排任何课程。2)状态匹配数组 公式（2-1）状态匹配数组D用来表明给定班级任课教师排课情况，表示教师i在第j个教学单元排课情况表明已排课表明未排，i=l，j=l，15，Y表示给定班级的所学课目数，假设每位教师在该班只任一门课程， 因此教师数也为Y， 若教师在该班不只任一门课程， 可用不同的别名代替。3)产生初始种群初始化状态匹配数组； 公式（2-2）初始化班级数i=0；选定班级，确定该班的课程名通过教师信息库中所有担任该班教师的课程中获取，班级课程名

43、可与教师代码建立对应关系；初始化解空间X=(x1，x2，x15)=0表明未对该班进行课表编排；确定该班的所学科目数Y值，给定班级的周学时m及每个教师在该班的周教学时数n；根据课表编排的约束条件和教师的任课时数，在状态匹配数组dij要求的位置上置l(若此位置已占用，另考虑其他未占用的位置)，要求同一列只允许一个位置占用，表明同一时段在给定班级只能有一个教师上课。此时即得到一个随机解(染色体)。 公式（2-3）矩阵相乘实际是将y个教师所任课程的代号随机填入班课表数组X转化为随机填入状态匹配数组D，第i个班级排课结束。(3)目标种群的适应度函数班级课表编排寻求的是最优解，不是唯一解，为了寻求最优解，

44、适应度函数的选取至关重要。通过适应度函数来决定课表编排的优、劣程度，它反映了课表编排的满意度。对于一个给定的优化问题，如何设计构造适应度函数是一个很关键的问题。适应度函数构成每个个体的生存环境，根据个体的适应度可以决定它在此环境下的生存能力。一般来说，好的染色体具有比较高的适应度即可以获得较高的评价，有较强的生存能力。在初始种群之后，产生的肯定是一个可行解，而一个好的课表就是要找到课程编排的最优解。排课优化最为重要的目标就是使得教学效果最好，即使课程安排在好的时间里上课，尤其对于核心课程和相对重要的课程36。我们采用对不同的时间设定优劣系数Kt(值越大的越优)，对不同的课程给定优先值M1(值越

45、大的越重要)，那么系统的这个优化目标为： 公式(2-4)其中t1为课程l所安排的时间。第二个重要的目标就是教室资源的利用率问题，一个合理优化的安排结果可以有效利用资源，一次授课中教学班人数Csl与该教室容量Crml的比值越大，则浪费越少，最大为1表示刚好容纳，优化目标为： 公式(2-5)第三个重要的目标是课时分布的均匀性，一门课尽量分散在一个星期中，给出上课时间间隔的满意度设为S1，则优化目标为: 公式（2-6）其他的优化目标还有教师对上课时间的偏好，学生课表均匀分布还是过于集中等等，根据各高校的实际情况适当增删，在此不作详细叙述。最终个体的适应度函数则根据各个目标值进行简单加权或者相乘，具体

46、采用哪种方法可根据案例的情况来定，简单加权较为稳定，收敛速度较慢，乘积则相反，我们采用前者，得适应度函数为： 公式（2-7）各系数通过试验来确定。(4)遗传操作对产生的初始种群用适应度函数进行检验，值大的生存下来，满意度不高的对种群的个体进行交叉、变异操作产生新的种群，这样不断循环，直至产生最优解37。具体操作流程：计算每个种群的适应度函数值，按照选择概率选择一定的种群遗传至下一代。对适应度函数值不满意的种群，按照交叉概率，选择一定的种群对其个体进行交叉操作，产生新的种群。对适应度函数值较小的种群，进行变异操作，生成新种群。对新生成的种群，计算每个种群的适应度函数值，不断循环，直至产生最优解。

47、下面对选择算子、交叉算子、变异算子分别介绍：选择运算用于模拟生物界去劣存优的自然选择现象，它从种群中选择出适应度高的某种染色体，放入配对集合中，为染色体交叉和变异运算产生新的种群做好准备。适应度越高的染色体被选择的可能性越大。选择操作的方法有很多，常见的有轮盘赌选择法、局部选择法、竞标赛选择法等38。我们采用轮盘赌选择法，首先将整个群体根据个体的适应度不同分布在轮盘上，适应度大的个体占的比例大一些，适应度小的个体占的比例小一些。然后对每个个体的概率进行累积，所有个体的概率和为100，每个个体占其中的一个百分比段。选择时系统随机产生一个百分数，落在哪个个体的百分比段就选择哪个个体，这种选择方法对适应度高的个体选中的机会相对就多，实现了优胜劣汰，同时也存在选中适应度小的个体的可能性，这样又保证了群体的多样性，使保留在