排课系统的设计与实现.doc

毕业设计(论文)课 题 名 称 课表编排系统设计与实现 学 生 姓 名 吕季干 学 号 0840819035 系、年级专业 理学与信息科学系 08级信息与计算科学 指 导 教 师 戴亚滨 职 称 讲师 2012年05月300摘要近年来随着大学的扩招和规模的扩大，排课问题已成为一个非常棘手的问题，在教室资源有限的前提下课程编排显得更加繁重，同时课程的编排也更成为教学管理工作的关键，在一定程度和深度上影响着学生的培养与教学质量的提高。利用计算机进行自动排课，不但能使教务人员从繁杂的排课任务中解脱出来，提高教务管理工作效率，而且能改善教学管理质量，合理、高效地利用有限的教学资源，使学校的各种教学活动、教学管理及其它相关的工作能够有序、规范地进行，维持正常的教学秩序，同时对推动教务管理的信息化起到非常重要的作用。 排课问题是一个有约束的、多目标的、难解的组合优化问题，是属于NP-完全问题。研究者提出了多种排课算法，例如模拟退火、列表寻优搜索、约束满意等算法，而遗传算法是很有效的求解最优解的算法之一。 遗传算法通过交叉、变异、选择三种遗传算子来实现遗传和变异的功能,并采用适应度函数保证排课结果趋于最优，对现有教学资源进行科学合理的安排，在实践中具有一定的应用价值。针对之前研究者未解决的运行时间太长问题，本文提出了一套基于二维编码的改进的编码方法和教室位置填充方法，精简了染色体信息量而大大缩短了系统的运行时间。此外，在系统设计中，运用了基于容器的容器编程技术，实现了不定数据量的便捷处理。关键词 遗传算法； 排课问题； 适应度函数32ABSTRACTAbstract In recent years, with the University Expansion and expansion of the scale.timetabling has become a very difficult problem. Limited resources in the classroom context, Curriculum has become more onerous. The courses become the key to teaching management at the same time. It affects students in developing and improving the quality of teaching to some extent. Arranging automatically by computer, not only to academic staff from the cumbersome task of freeing Arranging, improve efficiency of educational administration, but also to improve the quality of teaching management. Rational and efficient use of limited teaching resources, making variety of teaching activities, teaching management and other related work orderly and standardized manner, keeping the normal teaching order, At the same time promoting the academic management of information technology play a very important role.Timetabling problem is a constrained, multi-objective, intractable combinatorial optimization problems, it belongs to NP-Complete problems. Researchers have proposed many other Timetabling Problem, such as Simulated Annealing, List of search optimization, Constraint satisfaction and so on. But genetic algorithm is very effective algorithm for solving the optimal solution .GA carry out genetic and functional variation through Crossover, mutation and selection of three genetic operators. And adopt fitness function ensure Arranging Results tend to the best. According to the problem that running time is too long,which the res-earchers didnt resolved well before,this paper puts forward a improved method based on two-dimensional coding and the classroom filled method, simplifying the chromosome information and greatly shortening the syetem operation time. In addition, in the system design, we use the programming method of container based on container , realizing the convenient and fast processing of uncertain quantity data. Key words curriculum arrangement; genetic algorithm; Priority strategy目录中文摘要 . I英文摘要 . II1前言 . 12排课问题描述 . 2 2.1 问题需求分析 . 2 2.2 数据需求分析 2.2.1时间问题 2.2.2 教师和课程问题 2.2.3教室的问题 2.3功能需求分析 2.3.1院管理模块 2.3.2自动排课模块 2.4排课过程的约束条件3自动排课系统的设计. 2 3.1遗传算法的思想 3.2构建基因编码和染色体 3.2.1混合式编码 3.2.2染色体的表示 3.2.3 初始化种群4数据库问题 .3 4.1 数据库设计 4.1.1 概念模型设计 4.1.2 逻辑模型设计 4.1.3 数据库的物理设计 4.2 期望结果 4.2.1构造适应度函数 4.3功能模块的设计 4.3.1 登录模块 4.3.2主界面模块 4.3.3学院管理模块 4.3.4查询模块 4.3.5 排课模块5冲突问题解决. 46 结果评估 . 57结束语 . 6致敬词 . 7参考文献 . 8附录 . 81 前言 随着高校招生逐年扩张，大学课程向着广度和深度发展，高校的教师、教室等一些资源越发显得紧张，不管是在时间还是效率方面，用人工排课已不能够解决现有的问题。排课是高校日常教学工作和其他活动的基础，是教师和学生正常科学工作学习的依据。所以计算法自动排课已成为一个重要的研究课题1。国内学者在自动排课系统方面曾做过一些研究，如用到到退火算法、回溯算法、遗传算法，但运行结果尚有待改进的地方，排课效果不尽人意5。我们认为，问题不尽在数学建模上，还与问题的处理方式有关。将遗传算法应用于排课问题中，首先，初始化课表种群，其次，检测初试种群中的冲突，然后，对种群做选择，杂交，突变操作，一直迭代到具体指定的代数，最后就会得到较优解。文1中提到编码时染色体上基因片存储信息大小为11字节，而本文的编码方式一个基因片只用了6字节，轻装运行，经试验得出，速度更快。还有,文1介绍把教室与时间等信息共同处理的思路，这可能会产生空间上的冲突，而本文提出将教室分离出以单独处理，就完全解决了空间上的冲突问题。本文根据高校开课的具体情况，采用优化的编码方案，满足排课过程中的一些硬性和软性约束因素，利用遗传算法对课表进行了优化，从而得到了最终的无冲突、更人性的排课方案。2 排课问题描述2.1 问题需求分析 排课工作是一项十分繁重而复杂的工作，就以一般高校而言，它涉及到几千多门课程进行合理的组织安排，而所使用的教室资源却在学生规模每年都在增加的趋势下越发显得紧张了。排课的整个过程中充满了矛盾运动，其中包括上课班级、所开课程、任课教师、上课时间、上课地点这5个方面在排列组合中发生的冲突和矛盾现象。课程门类多、班级多、教师少、教室少、教师连续上课的要求、班级连续上课的时间合理安排是排课时发生冲突和矛盾的主要因素，而班级多、教室少则是矛盾的重要方面。课程表则是解决这些矛盾的舞台，是提高教学管理水平、组织师生进行有序教学的规范之一，对有效地提高教育教学质量有重要作用。如果课程表编排得不合理、不科学，将影响课堂教学的效率和教学的整体效果。要想编排好学校的课程表，需要综合考虑学校的教师、教室、学生、班级、时间等多方面因素，反复调整，避免冲突。 一张正确的课表应至少满足以下硬约束条件：3 (1) 一个教师或者一个班级或者一个教室在同一时间段内只能安排一门课程； (2) 分配的教室可容纳人数应该大于学生数。 除了上述的硬性约束，还有些软约束，这些软约束有助于使得课表更加合理，更加人性化。这些软约束条件可能是4： (1) 尽量在早上安排必修课，而下午安排选修课，晚上尽量不排课； (2) 尽可能满足个别教师的特殊上课时间要求； (3) 一门课尽量分散在一个星期中，即某天上完某一门课后，要隔一天以上再上这门课，以使教师有充足的时间备课和批改作业，而学生也有足够的时间复习消化； (4) 一个教师的课不能排满一整天； (5) 学生课表中的上课时间不能过分集中，应避免一天课程很满而另一天却一整天没课的情况。这些软约束条件各院校有所不同，在我们的研究中，旨在我们定义的约束范围内给出一个遗传算法的解决方法，并对其进行优化操作。图1排课流程图2.2 数据需求分析排课涉及的相关数据主要包括:时间、班级、课程、教室（空间）、教师等5个要素。开始算法设计的基础是对这些数据之间的问题的透彻分析和适当的处理。2.2.1时间问题在本文中考虑的是周课表，通过对全国部分高校做的调查，综合分析了其中大部分高校的教学特点，我们在此做出了一个较大众化的且较合理的时间划分模式。设定周一至周五，共五天上课，一天有十节课，上课方式都为一大节包括2个相邻的小节，不能在上、下午之间跨时段。把每天用于上课的时间划分为5个时间片，根据学院开课的实际情况，一般每学时是45分钟，为1小节课，每2小节课合为一大节课，故把每2小节课时间定为一个时间片，一天划分为5个时间片: (1)上午1, 2节课8:10-9:50; (2)上午3, 4节课10:10-11:50; (3)下午5, 6节课2: 30-4:10; (4)下午7, 8节课4:20-5:50; (5)晚上9, 10节课7:30-9:10; 这样，每周5天涉及25个时间片。用Tl, T2,.,T25表示，其中TI, T2, T3, T4, T5为星期一的5个时间片，依次类推。则排课问题类似于填充55的周时间片安排表。 表2-1周时间片分布表Table2-1 the management table of the week time slip 周一周二周三周四周五T1T6T11T16T21T2T7T12T17T22T3T8T13T18T23T4T9T14T19T24T5T10T15T20T25根据时间片编号，可进一步转化为125的表格。全校有N个教学班级，则周课表为:以25个时间片为列，形成一维的时间序列，每个班级为行组成的一个二维数据表。我们在此系统的排课都是按一个大节开设的，符合按25个时间片划分的设计，但确有少量的课程的周学时数为单数，如“3学时”或“5学时”，在此仍按“4学时”或“6学时”进行编排，虽然这会浪费一小节课程。2.2.2 教师和课程问题每个课程都有自己的编号、名称以及开课学院。每个课程都要有授课教师。每门课程都有指定的教室类型。如普通教室、语音室、操场、实验室或机房等等。每门课程都有授课计划，包括起始周和截止周以及周学时安排。在处理课程与教师时要注意以下几个问题:(1)“授一班多门课”问题:同一教师可以只上一门课，也可上多门课，如果同一教师在同一个班级教授多门课程，那么把课程和教师作同一变量考虑就会引起课程的混乱，此问题须分情况解决，我们将在系统设计中，学院安排开课任务时解决此问题。 (2)“一师多班”冲突问题:一位教师可能只给一个班讲课，也可能同时给多个班级讲课，也就是说同一教师可以在多个班出现，这样可能会出现同一时间，同一教师在多个班级上课的冲突，在编排课程表时此类冲突必须解决。(3)“多学时”问题:对于有些课程既可能只上一次，既2学时课程，而有些课程可能上多次，如4学时、6学时等，多学时的课程如何处理也是在编排课程表时必须解决的问题。(4)“固定课”问题:有的教师因为某些原因需要安排特定的教学时一段，如教室受到其他课程的影响，或者某学院部门领导，因工作性质关系，须指定安排上课时间为“星期五的第5、6节”，这样的要求在编排课程表时必须满足，即“固定时段”问题。(5)“特殊课”问题：像体育课，要跟硬件设施有关，故要妥善处理。2.2.3教室的问题如今的大学都有很多的教学楼，校园面积也很大，宿舍与教学楼，教学楼与教学楼之间的距离可能会比较大，如果安排不佳的话，会导致学生上课时要跑动很远距离，浪费不必要的时间。本文在地理位置上是学校统一规划，进而综合解决位置问题，学校要规划好各个学院的学生在哪些教学楼里就近上课，而这样做的目的就是为了减少学生和教师的走动范围。至于如何去确定一个教室，例如5-0122，就表示5教学楼，1楼22号教室。每个教室在同一时间内只能接纳一门课程的授课，并且教室容量应该大于等于上课的人数。当上课的人数远远小于教室容量时，这种情况也往往不合适的。2.3功能需求分析根据业务分析和数据分析，可得出排课系统主要完成以下几个功能:2.3.1院管理模块这一模块首先是每个学院从教学计划中安排自己学院的开课任务书，具体就是对本学院课程和教师的安排。这一模块由学院排课工作人员来设置，如设置学年学期就是设置即将排课的学年学期，合并本学院的两个班级组成一个新班一块上一门公共课，设置一门课程则为上课周数、每周上课节次、有哪位老师讲授等等信息; 这个模块很好的解决了每个学院不同的特殊情况，以教师为重点，学院可以随意调整。另一个功能，学院在这块可以查询本学院的课表，还有学院内班级的课表。还有对已排好的课程做一些调整操作。2.3.2自动排课模块 这一模块主要完成课程上课时间、上课地点的安排。它的实现运用了遗传算法中的选择、交叉、变异等操作，对算法得出的结果中最好的一个个体保留，就是要求的结果，虽然不是最完美符合的，但是它的适应度值已经完全可以符合学校教学所要求的了。然后，对这个（班级，教师，课程，时间）记录做变换，让位置表去填充它，当然是按条件填充，就可以完成整个排课的大部分工作了，从而得到课表。此图描述了功能模块图，如图2示：图2 功能模块图Chart 2 the function model chart 2.4排课过程的约束条件 排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合，在此同时也要安排课程，以使教学正常进行。在本文约束条件主要为避免冲突，所谓冲突，它所包含的内容很广泛，几乎发生在所有两个或多个排课涉及因素之间。避免冲突也是排课问题中要解决的核心问题。只有在满足全部约束条件和避免所有冲突的基础上，才能保证整个教学计划合理正常进行。而对教师、教室、学生及时间等几部分资源进行最优化组合配置，才能保证充分发挥各资源的优势和提高教学质量。在本文中，我们把排课过程中的约束条件分为三类:基本硬约束、硬约束和软约束。其中基本硬约束是指教师、学生和教室在时空概念上发生了不可能发生的事情，既是时间，空间，人之间的矛盾，它是排课过程中最基本的约束条件，也是众多排课模型中都要涉及的约束条件；硬约束是根据学校的实际情况，排课时必须遵循的原则，否则将会导致排课结果无意义，所以要因地制宜；软约束是指排课过程中满足更佳但不满足又无妨的约束条件，这些条件的目的就是使课表更加人性化，每个排课都是要突出解决软约束这个问题的，违背这些约束就与实际情况相悖。所以，可知在三类约束条件之中，前两者是衡量排课方案是否切实可行的基本标准，软约束是衡量排课方案是否人性化的标准，通常判别一个排课方案的优劣标准有多个。可以把排课过程常见的约束条件分类罗列如下表2-2所示，这些约束条件也比较符合排课过程的实际情况。表2-2 约束表Table 2-2 constraint table基本硬约束B1同一时间，同一班级不能上两门不同的课程B2同一时间，同一个教师不能上两门不同的课程B3同一个时间，同一个教室不能上两门不同的课程硬约束H1课程的学时在每周要均匀化H2满足每门课的特定教学资源H3教室足够大，能够容纳学生H4某些课程要特定安排，如某些教师的课程要固定H5教师学生上课不能用于在路途上的奔波H6体育课尽量安排在下午软约束S1课程的分布要做到离散化S2一周有些时段处于最佳利于学习时间S3尽量不让老师连着上课S4班级相邻上课地点尽量近些3 自动排课系统的设计3.1遗传算法的思想在本课题中，遗传算法解决的问题只是求出班级+课程+教师+时间的记录集，得到比较优的一个解，然后再去按条件用教室去填充这个记录集，就形成了可行可用的课表。这块的设计在整个系统是最重要的，效率的高低，课表的优劣都由本模块确定。整个系统的流程分为以下几个主要的过程:(1)初始种群的产生:首先基因的编码，根据制定的编码方案，对每条染色体进行初始化，其次一条条染色体组成一个个体，既是形成一个二维表（可称为课表，但是适应度值不高）。(1)冲突检测和消除:初始化种群后，先对其进行各类冲突的检测，如存在冲突则消除它，而且在每次产生下一代后都要进行冲突检测。(2)计算出每个个体的适应度函数值，以进行优胜劣汰。(3)遗传操作:包括选择算子、交叉算子和变异算子，产生子代，逐渐优化。(4)迭代第四步，直到进化停止，就是generation=终止代数N。(5)班级+课程+教师+时间的记录集的产生。图3 遗传算法流程图3.2构建基因编码和染色体实施遗传算法的第1步，就是把与求解目标相关的实际参数进行基因编码，这是算法的关键与难点。3.2.1混合式编码构造合适的基因结构是遗传算法能否顺利实现的关键，设定混合式的教师编码作为本系统遗传算法的“基因”。二进制基因构成规则为:是否固定*教师编号号*课程编号*课程性质分别对应的宽为1+15+16+16共6B。下面我们给了很清晰的解释：图4 编码结构图下面我们对每个字段给予解释：a.是否固定有些教师的课程是固定在某个时间段的，所以在排课过程中，判断第一位就可以得知可否移动此基因片。这也反应了排课要人性化，毕竟有些教师有特殊的要求，例如，年龄、事物等等。b.教师编号我们给了15bit去表示教师，15bit能表示215个数，足矣满足任何一所高校的教师编号，所以，在数据库里，教师表里教师编号的数据项要为短整型。c.课程编号唯一确定一门课程，216个数，也足以表示一个学校的课程。d.课程性质 为了解决“特定资源”冲突问题，可在教师编码中加上2B表示该教师所教授的课程的性质。每一门课程都有其各自不同的特点，比如上机课需要在机房上课，英语口语需要在语音室上课，体育课需要在操场上课，为此我们规定：把16bits分开，前后8bits各有不同的意思； 图5比特信息图在此我们把课程分为专业必修课，专选科，公共课，上机实验课，专业实验课，体育课，英语语音课，前三个属于理论课，不在此分配教室。区分：计算机专业的实验课是和非计算机专业的上节实验课不同的，他们有自己的实验室，属于专业实验课。前8位编码不同时表示不同的意思：表3-1 编码课程关联表Table 3-1 the relational table of coding and course编码值表示课程类10000000专业必修课11000000专业选修课11100000公共课11110000上机实验课11111000专业实验课11111100体育课11111110语音课后8位编码表示当此教师固定在这个时间片上课时，所在的时间片值。3.2.2染色体的表示对于每一门课程既可能只上一次(规定2学时课占用一个时间片)，也可能上多次，如4学时、6学时等。上2学时课时，该教师编码只能出现1次，上4学时课时该教师编码出现2次，依次类推。在大多数，每周上6学时的课程不会太多，大多数时4学时和2学时； 通过以上把课程与教师等同的处理后，原课表的五要素(班级、教室、课程、时间、教师)转化为四要素(班级、课程、时间）和班级。功能室(实验室机房、语音室等)已经在编码时分配好，而理论课的那些，要等到后面再去分配。为了更好地阐述排课遗传算法，定义排课遗传算法名词：a.“基因”混合型的教师编码，即TI-T25时间片中的值；b.“染色体”班级名称与Tl-T25中的“基因”组成的串；c.“个体”由bjs（班级数）个染色体组合而成的二维数据表，即对应于一张课表。其中BJS为参与课表编排的班级总数；d.“种群”由ZQS个个体构成。其中ZQS为种群大小。3.2.3 初始化种群每一个“染色体”都是班级的一个课表，是开课任务书中的一个班级所有记录组成的，形成的是班级+教室+课程+时间一条记录。 对每一个课程表可以形成一个二维数组kcb (25,bjs)，每一列就表示一个班级的课表。首先把固定教学时间的教师编码填入该行中，然后使用随机函数产生一个125的数，将该班的其它教师编码填入其中。如产生的随机数对应的时间片中己有数据，则重新产生，直到将所有教师编码无重复地填入该行中。这样就有了一条染色体(一个初始的班课程表)。如此循环bjs次，产生了与班级数目对等的染色体数目。于是，一个初始个体便产生了。按种群规模的大小ZQS，产生一定数量的个体，每个个体都存放到一个按序编号的表中，由这些个体组成初始种群。很明显，由上述方式产生的个体通常含有大量的冲突。另外，在初始化种群时，基于容器的容器使其更加简捷。对于数据库中教学楼，教室，班级等一些数量都未知的数据进行存储，运用数组显然不能解决，会出现很多的冗余，浪费内存，并且处理繁琐。关联容器的使用方法如图6所示：图6容器结构图完成种群初始化后，个体的数据结构如下图示：图7 个体结构图4 数据库问题4.1 数据库设计 数据库设计是建立系统数据库及其应用系统的重要环节，系统的各个部分能否紧密地结合在一起以及如何结合，关键在数据库，只有对数据库进行合理的逻辑设计和有效的物理设计才能开发出完善而高效的排课系统。本文的数据库设计及其实现如下：4.1.1 概念模型设计 因为概念结构是面向现实世界的，用户容易理解，能够参加设计讨论，提出意见，在将分析结果抽象为逻辑数据库时可以降低设计的难度。这会将数据库的概念结构转换为逻辑结构方法简单，易于实现。对于排课问题要进行的分析主要有:教学计划、各学院教学任务、教室基础数据、时间模式、开课任务、及各种课表等数据。这些关系用E-R图表示如图8，9，10:图8 院管理E-R图图9 校管理E-R图图10 总E-R图4.1.2 逻辑模型设计 在逻辑模型设计中，并不是划分数据的粒度越小越精确就会越好，而是要符合设计现状要求和系统实现便捷，也就是说，范式越高也不一定越好。具体来说创建了以下各表:表 4-1 用户表:UserTable 4-1 user table:User编号数据项数据项别名数据类型数据项含义1用户名username Char(12)唯一2密码passwdChar(20)3学院academyChar(20)学院名，如果空的话就是代表教务处表4-2 教学计划表:TeachPlanTable 4-2 teaching plan table:TeachPlan编号数据项数据项别名数据类型数据项含义1班级classChar(15)主属性2班级编号CnoChar(10)主属性3课程courseChar(15)4课程编号courseNoSmallint(2)主属性5学院academyChar(15)6人数Pnoint7课程属性courseAtrrChar(15)8周节数pitchNumSmallint(2)9周数weekSumSmallint(2)10开课学期semesterChar(15)表4-3 教室表：ClassroomTable 4-3 classroom table：Classroom编号数据项数据项别名数据类型数据项含义1教学楼TbuildingChar(10)主属性2门号houseNoChar(10)主属性3容纳人数containSumint4教室属性houseAtrrChar(10)表4-4语音课体育课上机课位置表：Y_T_STable 4-4 the place table：Y_T_S编号数据项数据项别名数据类型数据项含义1类别categoryChar(1)区别三类教室2教室名roomnameChar(15)3教室编号roomIDsmallint4班级classChar(15)加上班级就可以确定班级上课的位置范围5学院academyChar(15)表 4-5 理论课教室表：LLKAddressTable 4-5 the classroom table of theory course：LLKAddress编号数据项数据项别名数据类型数据项含义1学院AcademyChar(20)2班级classChar(15)3教学楼TbuildingChar(10)表4-6 学院表：AcademyTable 4-6 academy table：Academy编号数据项数据项别名数据类型数据项含义1学院academyChar(20)2学院编号academyIDChar(10)主键表4-7 专业实验课位置表：ZYSYRoomTable 4-7 the lab classroom place：ZYSYRoom编号数据项数据项别名数据类型数据项含义1学院academyChar(20)2教室名roomnameChar(15)3教室编号roomIDsmallint4班级classChar(15)5容纳人数containSumsmallint表4-8 位置表：AddressTable 4-8 place table：Address编号数据项数据项别名数据类型数据项含义1学院academyChar(15)唯一2教学楼TbuidingChar(10)3班级ClassChar(15)表4-9 教师_课程表T_CTable 4-7 teacher and course table编号数据项数据项别名数据类型数据项含义1教师名Tnamechar(10)2教师编号TnoSmallint主属性3课程courseChar(15)4课程编号courseNoSmallint主属性表4-10 教师表：TeacherTable 4-10 teacher table：Teacher编号数据项数据项别名数据类型数据项含义1教师名Tnamechar(10)2教师编号TnoSmallint唯一3学院academychar(15)4年龄TageSmallint正整数5职称Titlechar(10)表 4-11开课任务表：ClassTaskTable 4-11 the plan table：ClassTask编号数据项数据项别名数据类型数据项含义1开课学期semesterChar(15)主属性2学院academyChar(15)3班级classChar(15)主属性4教师名Tnamechar(10)5教师编号TnoSmallint主属性6课程编号courseNoSmallint7人数Pnosmallint8课程coursesmallint9课程属性courseAtrrchar(15)10周数weekSumSmallint11上课次数timesSmallint12是否固定IsSettledChar(1)为0则不固定13固定时间位置TimePitchsmallint表4-12 课表：CourseTableTable 4-11 course table：CourseTable编号数据项数据项别名数据类型数据项含义1开课学期semesterChar(15)主属性2学院academyChar(15)3班级classChar(15)主属性4教师名Tnamechar(10)5教师编号TnoSmallint(2)主属性6课程courseChar(15)7地点addressChar(20)主属性8周数weekSumSmallint(2)9时间timeChar(15)主属性4.1.3 数据库的物理设计数据库的物理设计这一环节也是很重要的，它要综合考虑存取时间、存储空间利用率和维护代价三方面的因素。消除冗余数据虽然能提高空间的利用率，但同时也会提高检索的代价，因此，这三方面必须权衡，选择一个折中方案。4.2 期望结果4.2.1构造适应度函数为了能够获得切实可行的课程表，应以尽量符合排课的经验常识为目标。而这个要求是一个模糊的不确定问题。因此，为了评判一个课程表的优劣度，必须量化计算课程表的适应度值。适应度值实际上反映了排课人员对课表理想化编排的一种期望。因此，如何把这些“期望”转化为具体的“值”，是使排课系统得以智能化的关键所在。以下共列出了相关期望值定义的5个表:表4-14、表4-15、表4-16、表4-16，其中的数字分别取值于0-10，是对影响期望值的各因素进行的赋值，这些取值经过了系统模块的反复测试和调整。(1) 期望值a.专业必修课的期望值表 如表4-13所示表4-13 专业必修课的期望值Table 4-13 fitness of Professional compulsory course时间片1、6、11、16、212、7、12、17、223、8、13、18、234、9、14、19、245、10、15、20、25期望值108420b.公共课和专选课的期望值 如表4-14所示表4-14 公共课和选修课的期望值Table 4-14 fitness of proficient and selective course时间片1、6、11、16、21、4、9、14、19、242、7、12、17、223、8、13、18、235、10、15、20、25期望值28100c.体育课的期望值 如表4-15所示表4-15 体育课的期望值Table 4-15 fitness of sports course时间片1、6、11、16、21、5、10、15、20、23、24、252、7、12、17、223、8、13、184、9、14、19期望值04810d.实验课和语音课的期望值 如表4-16所示表4-16 实验课和语音课的期望值Table 4-16 fitness of experiment and Speech course时间片1、6、11、16、21、23、24、252、7、12、17、223、8、13、184、9、14、195、10、15、20期望值046108前面四种期望值的计算方式是遍历一个个体，检查它的课程性质，判断它是哪种类型的课程，当为10000000时表示专必课，算出它的适应度值加在F1中，为11000000和11100000时表示专选课和公共课，算出它的适应度值加在F2中，为11110000和11111000、11111110时表示上机实验课和专业实验课、语音课，算出它的适应度值加在F3中，为11111100时表示体育课算出它的适应度值加在F4中。e.课程离散程度期望值一门课在一周内分散安排，提供可引导性学习环境。系统使用编号相同的两课的时间差来描述这种离散度，根据测试给出相应的期望值。如表4-17所示表4-17 离散度期望值Table 4-17 fitness of Discrete degree两课时间差14、15、17、18、19、20、21、22、23、240、11、12、131、2、9、108、6、73、4、5期望值024610检查每个班级的一门课程及下一门课程的时间，算出时间差加入Fi（i=0,1,2，.n）依次计算，得出这个班级课程离散程度离散期望值Fi然后，计算F5=Fi(2) 适应度值 定义课表的适应度函数Fit为: Fit=K1F1+K2F2+K3F3+K4F4+K5F5其中Kl, K2, K3，K4，K5为控制上述各种期望值对总期望值的影响参数(权重)。这样，系统就有了冲突检测、消除函数和适应度函数。在进化过程中，冲突必须完全消除。而适应度函数值越大，则课程表的安排越合理、有效。对于每一类期望值及其在总的期望值中的比例，都可以根据每一所学校的具体情况进行必要的调整，使排课系统更加实用、有效。4.3功能模块的设计4.3.1 登录模块输入用户名密码就能进入本系统，但是得选定操作者图11 登陆框Chart 11 login dialog4.3.2主界面模块在课已排好的情况下，可以显示课表。图12 主界面Chart 12 main interface4.3.3学院管理模块学院管理本院的一些教师分配。图13 院管理界面Chart 13 interface of college management4.3.4查询模块不同用户所拥有的权限不同！图14查询界面Chart 14 interface of query4.3.5 排课模块以上模块都操作好之后，点击排课模块菜单里的排课，就可以排出课表.5 冲突问题解决 排课问题是一个NP-Complete问题，无论采用哪种方法都无法避免各种冲突问题的出现，同一位教师在同一时段内排了两门课是冲突问题中最明显的一个。为了避免这种冲突产生，在本系统开发中引进了一个冲突检测函数fConflict()，当排完一位教师的所有课程之后，系统就会用该函数对此教师课程安排的冲突情况进行检测并作修正。每个课程都有自己的编号、名称以及开课学院。每个课程都要有授课教师。每门课程都有指定的教室类型。如普通教室、语音室、操场、实验室或机房等等。每门课程都有授课计划，包括起始周和截止周以及周学时安排。在处理课程与教师时要注意以下几个问题:(1)“授一班多门课”问题:同一教师可以只上一门课，也可上多门课，如果同一教师在同一个班级教授多门课程，那么把课程和教师作同一变量考虑就会引起课程的混乱，此问题须分情况解决，我们将在系统设计中，学院安排开课任务时解决此问题。 (2)“一师多班”冲突问题:一位教师可能只给一个班讲课，也可能同时给多个班级讲课，也就是说同一教师可以在多个班出现，这样可能会出现同一时间，同一教师在多个班级上课的冲突，在编排课程表时此类冲突必须解决。(3)“多学时”问题:对于有些课程既可能只上一次，既2学时课程，而有些课程可能上多次，如4学时、6学时等，多学时的课程如何处理也是在编排课程表时必须解决的问题。(4)“固定课”问题:有的教师因为某些原因需要安排特定的教学时一段，如教室受到其他课程的影响，或者某学院部门领导，因工作性质关系，须指定安排上课时间为“星期五的第5、6节”，这样的要求在编排课程表时必须满足，即“固定时段”问题。(5)“特殊课”问题：像体育课，要跟硬件设施有关，故要妥善处理。6 结果评估 本节我们要做的就是为了实现最优化的结果，将上节的各种操作运用到GA中。实验平台是Visual C+