（计算机应用技术专业论文）高校自动排课算法的研究与实现.pdf

0 二：0it 二 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 7 o o 分s - 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：靶日期： 哪，r f i 1 摘要 l i i ii i fillii iui ii iiil y 17 8 7 7 7 4 摘要 1 排课是高校教务管理部门一项非常重要而且关键的工作，科学合理的课程 表是高校教学工作正常开展，提高高校教学质量的重要保证。计算机自动排课 不仅能够把教务人员从繁重的排课任务中解脱出来，而且采用计算机排课能够 增强课程表的科学性。由于各个高校的教学模式和管理方法的不同，使得软件 公司所开发的高效自动排课系统很难普遍适用，因此，高校根据自身实际开发 一套适用的排课系统有着十分重要的意义。 本文在研究现有排课算法的基础上，汲取经典排课算法的精华思想，以基 于优先级的排课算法为主要基础，针对北京联合大学生物化学工程学院的具体 情况，对算法进行改造和补充，设计了适用于本院完整的排课算法。采用面向 对象的分析方法，利用u l v i l 相关图对排课系统进行功能需求分析，并进行模 块划分。排课系统采用c s 模式，用户分权限级别管理，利用v i s u a lb a s i c 6 0 作为前台开发工具，s q ls e r v e r2 0 0 0 数据库管理系统设计的数据库作为后台， 实现了系统需求中相应的功能。最后经过系统运行测试验证说明本课题所设计 的算法具有可行性和有效性。 关键词排课算法；基于优先级的排课算法；排课系统：c s 模式；课程表 t，p虢哼葫，、。，_。：-，；矿“f 北京工业大学工学硕士学位论文 i i m和精kp警魄。岳+鼬o；。 k，_?一譬 a b s t r a c t a b s t r a c t a r r a n g i n g c o u r s ei s v e r yi m p o r t a n tf o re d u c a t i o n a l a d m i n i s t r a t i o ni nh i g h s c h 0 0 1 s c i e n t i f i ca n ds o u n dc u r r i c u l u ms c h e d u l ee n a b l e st e a c h i n go fh i g hs c h o o li n g o o dc o n d i t i o na n dp r o m o t i n gt e a c h i n gq u a l i t y a r r a n g i n gc o u r s eu s i n gc o m p u t e r c a nn o to n l ym a k et h ea d m i n i s t r a t o ro u to fh e a v ym a n u a lw o r kb u tb e t t e rt h e c u r r i c u l u ms c h e d u l e a sd i f f e r e n tu n i v e r s i t i e sh a v et h e i ro w nt e a c h i n gm o d e la n d a d m i n i s t r a t i o nm e t h o d , t h ec o m m e r c i a ls o f t w a r ef o ra r r a n g i n gc o u r s ec a nn o tb e s u i t a b l ef o re v e r yu n i v e r s i t y i ti ss i g n i f i c a n tf o rt h e mt od e v e l o pas u i to fs o f t w a r e f o ra r r a n g i n gc o u r s ea c c o r d i n gt ot h e i ro w nc o n d i t i o n t h ee s s a yi sa b o u td e v e l o p i n gas u i to fs o f t w a r ef o rb i o c h e m i c a le n g i n e e r i n g c o l l e g eo fb e i j i n gu n i o nu n i v e r s i t y , w h i c hi sb a s e do nc u r r e n ta r i t h m e t i co na r r a n g i n g c o u r s ea n da b s o r b sc l a s s i c a li d e a l s t h ea r i t h m e t i ci sm a i n l yb a s e do np r i o r i t ya n dd o s o m ec h a n g ea n ds u p p l e m e n tf o ri t ，w h i c hi sa p p l yf o rb e i j i n gu n i o nu n i v e r s i t y b i o c h e m i c a le n g i n e e r i n gc o l l e g e s o f t w a r ed e s i g na d o p t so r i e n to b j e c tm e t h o da n d u s e su m lr e l a t i o nc h a r tt od os y s t e mf u n c t i o n a lr e q u i r e m e n ta n a l y s i s ，i na d d i t i o nt o p a r t i t i o nm o d u l e s t h ed e v e l o p e da r r a n g i n gc o u r s es y s t e mi sb a s e do nc sf r a m e m o d e ，a d m i n i s t r a t e su s e r so nt h e i ro w nl e v e l ，u s e sv i s u a lb a s i c 6 0a si t sd e v e l o p i n g l a n g u a g e ，m a k e ss q ls e r v e r2 0 0 0a si t sd a t a b a s e ，a n df i n a l l yr e a l i z e st h ew h o l e s y s t e mr e q u i r e m e n t f e a s i b i l i t ya n dv a l i d i t yo ft h ea r i t h m e t i cm e n t i o n e di nt h e e s s a ya r ep r o v e di nt h ee n do ft h ee s s a y k e y w o r d sa r i t h m e t i cf o ra r r a n g i n gc o u r s e ；a r i t h m e t i c f o ra r r a n g i n gc o u l s eo n p r i o r i t y ；a r r a n g i n gc o u r s es y s t e m ；c sm o d e ；c u r r i c u l u ms c h e d u l e m 、 北京工业大学工学硕士学位论文 i v 目录 目录 摘j 要。i a b s l r a c t 第1 章绪论l 1 1 课题来源及研究意义1 1 2 高校自动排课概述2 1 3 本人完成的工作3 1 4 本文结构3 1 5 本章小结3 第2 章主要排课算法分析5 2 1 排课的基本问题5 2 2 遗传算法6 2 2 1 遗传算法的特点6 2 2 2 遗传算法的演算过程6 2 2 3 用遗传算法解决高校排课问题7 2 2 4 用遗传算法解决排课问题的结果分析1 2 2 3 蚁群算法1 2 2 3 1 生物原型1 2 2 3 2 数学模型1 2 2 3 3 用蚁群算法来解决高校排课问题1 4 2 3 4 用蚁群算法解决排课问题的结果分析一1 6 2 4 改进型回溯算法。16 2 4 1 回溯算法及其改进1 6 2 4 2 用改进型回溯算法来解决高校排课问题1 7 2 4 3 用改进型回溯算法解决排课问题的结果分析2 0 2 5 基于优先级的算法2 0 2 5 1 排课的预处理2 0 2 5 2 每一子类的排课处理2 2 2 5 3 基于优先级的算法解决排课问题的结果分析2 3 2 6 排课算法分析结论2 3 2 7 本章小结2 4 第3 章本课题算法设计2 5 3 1 调度的优先级设计2 5 北京工业大学工学硕士学位论文 3 2 课程表的优化2 6 3 3 主要数据项及数据结构2 8 3 4 排课的基本步骤2 9 3 5 本章小结。3 2 第4 章系统的设计与实现3 3 4 1 系统分析：3 3 4 1 1 系统用例图：3 3 4 1 2 系统时序图：3 5 4 1 3 系统类图3 5 4 1 4 系统模块划分。3 6 4 2 系统设计：3 8 4 2 1 系统采用的模式结构二3 8 4 2 2 技术方案选择4 0 4 2 3 数据库设计及实现。4 1 4 2 4 对数据库中数据的访问4 4 4 3 系统实现4 6 4 3 1 用户权限设置及验证。4 8 4 3 2 排课功能的实现5 0 4 3 3 数据操作5 0 4 4 本章小结5 3 第5 章算法效果分析5 5 5 1 系统运行环境。5 5 5 2 排课结果5 5 5 3 结果分析。5 7 5 4 本章小结5 8 结论5 9 参考文献。6 1 攻读硕士学位期间所发表的学术论文。6 5 致谢6 7 第l 章绪论 1 1 课题来源及研究意义 第1 章绪论 本课题是北京联合大学生物化学工程学院教务管理系统课题的一部分， 其核心内容是在现有排课算法的基础上，通过分析比较和研究，找到一种适合我 院教学实际情况的排课算法，采用该算法开发的自动排课系统能够代替纯粹的人 工排课，产生科学、合理的课表。该项目的相关子课题有教学计划管理、学生成 绩管理、学生学籍管理、课程注册与考试管理、奖学金评定等。 民族要振兴，国家要富强，就一定要发展教育，通过教育来培养优秀的高素 质的社会建设人才。目前，高校培养人才的主要途径是教学，资源投资和所有的 工作都以教学为中心，只有做好了教学工作，整个高校才能够正常运行。所有高 校在每个学期开学前都要对本学期教学任务进行合理的安排，这是教务管理部门 的一项重要任务，其中排课是最为关键的环节。排课问题的本质是将课程、教师 和学生在合适的时间段内分配到合适的教室，需要考虑的因素比较多，首先，在 教学规模不断扩大而教室、实验室、机房等教学资源相对不足的情况下要合理充 分的利用这些资源，保证教学工作的正常开展；第二，要兼顾教师、学生、教室 三者可利用的时间，课表不能出现冲突；第三，要优化学生的学习进程，根据课 程特点不同类型的课程要安排在一天不同的时间段，以利于学生对知识的接受， 另外同一门课在一周之内如果上两次以上，还要考虑时间间隔的合理性，间隔太 7 短，不利于学生对知识的消化吸收，间隔太长教学效果同样不会太好。也就是说， 课表既要能够保证教学活动的正常进行，又要讲求科学合理性。目前很多院校仍 然采用传统的人工排课方式，在兼顾多重约束条件的情况下，人工排课的工作量 很大，而且课表往往在科学性上有一定的欠缺。北京联合大学生物化学工程学院 目前仍然采用人工排课的方式，每个学期末就开始编排下学期的课表，课表产生 之后，会不断发现问题，教务人员需要花费很多时间进行课程表的修改工作。利 用计算机进行自动排课，不但能使教务人员从繁杂的排课任务中解脱出来，大大 提高教务管理工作的效率，改善教学管理质量，合理高效地利用有限的资源，而 且对于优化学生的学习进程、评估每位教师对教学的贡献、领导的合理决策等都 具有重要意义，可以间接提高教育教学质量，促进教学的良性循环。目前计算机 自动排课问题已经成为软件公司的一个课题，但一方面真正投入使用而且功能比 较完善的排课系统尚不多见，另一方面，每个高校的教学资源配置情况不同，办 学定位和办学层次决定了每个高校的教学模式以及管理方法不同，编排课程表时 考虑的相关因素的权重也不同等等，直接导致目前现有的计算机自动排课系统的 通用性不强。所以，对于大多数高校，非常需要根据本校的具体情况量身定做一 北京工业大学工学硕士学位论文 个计算机自动排课软件。 本课题的研究对开发高校自动排课系统有指导作用，另外因为排课问题的核 心为多维资源的冲突与抢占，对研究类似问题有参考价值，特别是对于解决其他 多约束、大规模的时间表问题具有重要的指导意义。 1 2 高校自动排课概述 1 9 6 2 年，g o t l i e b 曾提出了一个课表问题的数学模型，并利用匈牙利算法解 决了三维线性运输问题。此后，人们对课表问题的算法、解的存在性等问题做了 很多深入探讨，但是大多数文献所用的数学模型都是g o t l i e b 的数学模型的简化 或补充。4 0 多年来，人们对课表问题的计算机解法做了许多尝试。其中，课表 编排的整数规划模型将问题归结为求一组0 1 变量的解，但是其计算量非常大。 m i h o c 和b a l a s ( 1 9 6 5 ) 将课表公式化为一个优化问题，k r a w c z k 则提出一种线 性编程的方法，j u n g i n g e r 将课表问题简化为三维运输问题，而t d p a t h y 则把课表 问题视作整数线性编程问题并提出了大学课表的数学模型。此外，有些文献试图 从图论的角度来求解排课表的问题，但是图的染色问题也是n p 完全问题，只有 在极为简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数学模型 与实际相差太远，所以对于大多数学校的课表编排问题来说没有实用价值。进入 九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的 v a s t a p u r 大学管理学院的a r a b i n d a t r i p a t h y 、加拿大m o n t r e a l 大学的j e a na u b i n 和j a c q u e sf e r l a n d 等。目前，解决课表方法的问题有：模拟手工排课法，图论方 法，拉格朗日法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进 行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的 巨大障碍。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通 的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望得到成功的办 法。 在国内，对课表问题的研究开始子8 0 年代初期，具有代表性的有：南京工 学院的u t s s ( au n i v e r s i t yt i m e t a b l es c h e d u l i n gs y s t e m ) 系统，清华大学的t i s e r ( t i m e t a b l es c h e d u l e r ) 系统，大连理工大学的智能教学组织管理与课程调度等， 这些系统大多数都是模拟手工排课过程。目前常用的解决排课问题的算法有：模 拟退火算法，遗传算法，蚂蚁算法等随机寻优算法，另外还有一种是基于优先级 的排课算法。 从实际使用的情况来看，国内外研制开发的排课系统在实用性上仍然有所欠 缺。一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事， 另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍适用，特别是在 第1 章绪论 调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大 变动。所以对于学校，特别是规模相对较大的高校，应该有针对自身情况的排课 软件。 综上所述，排课问题早在上个世纪7 0 年代就证明是一个n p 完全问题，即 算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于 n p 完全问题目前在数学上是没有一个通用的算法能够很好地解决，但是很多n p 完全问题目具有很重要的实际意义。目前人们对n p 完全问题研究的主要思想是 如何降低其计算复杂度，即利用一个近似算法来代替，力争使得解决问题的时间 从指数增长化简到多项式增长，结合到课表问题就是建立一个合适的现实简约模 型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课 问题一个很常见的思路。 1 3 本人完成的工作 本人主要完成以下三个方面的工作： ( 1 ) 算法分析，详细分析比较现有的排课算法，找出每种排课算法的优缺 点或适用的范围，为本课题算法的选择作好准备。 ( 2 ) 算法设计，分析北京联合大学生物化学工程学院的教学实际要求，结 合现有算法设计出一种完整并适用的排课算法。 ( 3 ) 算法实现，基于设计的算法，开发北京联合大学生物化学工程学院的 计算机自动排课系统，采用自动排课系统来代替人工排课，产生课程表，以此来 验证算法的可行性和有效性。 1 4 本文结构 本文共分为六大部分，第1 章为绪论，主要介绍课题来源、课题研究的背景 意义及国内外研究现状，说明本人要完成的主要工作；第2 章对现有主要的排课 算法进行分析，为本课题的算法选择做好准备；第3 章进行本课题的算法设计； 第4 章描述排课系统的设计和实现：第5 章对排课系统进行运行测试，说明排课 结果并对结果进行分析，以此来验证本课题所设计的算法的可行性和有效性； 结论部分对本课题的研究状况进行总结说明。 1 5 本章小结 本章首先说明了课题来源，分析了课题研究的背景意义，对国内外的研究现 北京工业大学工学硕士学位论文 状进行了分析，说明了本人要完成的主要工作，为后面的研究指明了方向。 第2 章主要排课算法分析 第2 章主要排课算法分析 2 1 排课的基本问题 计算机自动排课系统实际上是时间表的优化问题，目的是协助教务管理人员 完成高校课程表的编排工作。排课的主要任务是对教师、教室、班级、时间、课 程5 个因素进行最优化组合配置，保证充分发挥各资源优势和提高教学质量。课 程表应该满足以下约束： ( 1 ) 同一教学班级的学生在同一时间不能安排两门以上的课程； ( 2 ) 同一教师在同一时间不能安排两门以上的课程： ( 3 ) 同一教室在同一时间不能安排两门以上的课程； ( 4 ) 同一时间安排课程总数不能大于所能提供的教室总数； ( 5 ) 某一教学班的人数不能大于所安排教室的容量。 课程表除了满足以上硬性约束之外，排课时还应该遵循以下原则： ( 1 ) 有效原则，这是排课总的原则，应该根据每类课程的特点，把这类课程 安排在上课效果最好的时间，比如数学、物理i 化学、理工类专业课、需要计算 分析的课程等应尽量安排在上午，文科类课程、体育课应该安排在下午等。 ( 2 ) 交错原则，要交错安排特点不同的学科，比如需要逻辑思维和形象思维 的学科要交错安排，脑力消耗大的和脑力消耗小的学科要交错安排，体力消耗大 的和脑力消耗大的要交错安排等。 ( 3 ) 分散原则，首先，- h 课要尽量分散在一个星期中，即某天上完某- i - j 课后，要隔一天以上再上这门课，这样教师就有足够的时间来备课和批改作业， 学生也有足够的时间来复习消化。其次，由于人的精力有限，为了保证教师课堂 授课效果，一个教师的课不能排满一整天。学生课表中的上课时间不能过分集中， 应该避免一天课程很满而另外一天课很少或者没课的情况。 ( 4 ) 优先原则，由于教师兼任行政职务或进修或有其他特殊困难对排课要特 定要求的要优先处理；公共课，合班专业课等涉及面较广、学时多的课程应该优 先处理。 ( 5 ) 相对固定原则，同一教师、同一课程应尽量选择相对固定的几个教室。 另外还应考虑学生相邻两堂课的教室距离不能太远，要保证足够的时间作上 课准备等。 2 2 2 5 对目前比较成熟的高校排课算法进行较为详细的分析。 北京工业大学工学硕士学位论文 2 2 遗传算法 遗传算法m q 力是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算 模型，是一种通过模拟自然进化过程搜索最优解的方法，它是美国m i c h i g a n 大 学j h o u a n d 教授于1 9 7 5 年首先提出来的，并出版了颇有影响的专著( ( a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) ，g a 这个名称才逐渐为人所知，j h i l l a n d 教授 所提出的g a 通常为简单遗传算法( s g a ) 。 2 2 1 遗传算法的特点 遗传算法是一类可用于复杂系统优化的具有鲁棒性、全局最优性、可并行处 理性及高效性的搜索算法，体现了自然界“物竞天泽，适者生存 的进化过程， 在函数优化、组合优化、生产调度、机器学习、图像处理、模式识别等多个领域 得到了广泛的应用，由文献 1 】可知，与传统的优化算法相比，主要有以下特点： ( 1 ) 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接 决策变量的实际值本身，而遗传算法处理决策变量的某种编码形式使得我们可以 借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理， 也使得我们能够方便的应用遗传操作算子。 ( 2 ) 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。仅 用适应度函数值来评价个体，在此基础上进行遗传操作。适应度函数不仅不受连 续可微的约束，而且其定义域可以任意设定，这一特点使得遗传算法的应用范围 得到扩大。 ( 3 ) 遗传算法使用多个点的搜索信息，对多个解进行评估，减少了陷入局 部最优解的风险，同时实现了隐含并行化。 ( 4 ) 遗传算法使用概率搜索技术，而非确定性规则。 ( 5 ) 具有自组织、自适应和自学习性。利用进化过程获取的信息自行组织 搜索，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构，适 应度小的个体也有生存的可能性，这样既保证了群体的多样性，也使得较差个体 中的优秀基因得以保存。 2 2 2 遗传算法的演算过程 运用遗传算法求解问题，首先需要将所求解的问题进行编码，然后在可行域 中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函 数值，即编码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机 第2 章主要排课算法分析 挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的个体能够保 留较多的样本，而适应度较低的个体则保留较少的样本，甚至被淘汰。在接下去 的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。 交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随 机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上 述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解 就是问题的最终结果。由此可见，遗传算法采用的是类似基因演化的循环过程， 概括地讲其演算过程闭如下： 。 随机产生一定数目的初始种群； 对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个 体及其代表的最优解，并结束计算，否则转向第步； 依据适应度选择再生个体； 按照一定的交叉概率和交叉方法生成新的个体； 按照一定的变异概率和变异方法生成新的个体； 由交叉和变异生成新一代的种群，然后返回第步。 由文献【1 】可知遗传算法的伪码描述： b e g i n ： i = 0 ； i n i t i a l i z ep 圆； f i t n e s sp ( i ) ； w h i l e ( n o tt e r m i n a t e c o n d i t i o n ) i + + ； g a - o p e r a t i o np ； f i t n e s sp ； e n d 2 2 3 用遗传算法解决高校排课问题 应用遗传算法来解决高校的排课问题有很多案例，本人通过查阅相关资料并 进行分析研究，给出一种用遗传算法来解决高校排课问题的经典案例。 ( 1 ) 基因编码及染色体表示 在遗传算法的设计过程中，首先要确定编码方案，在经典的遗传算法中常采 用整数编码、浮点编码、d n a 编码、二进制编码等方法，编码方式的优劣关系 北京工业大学工学硕士学位论文 到信息的完备表达、遗传操作算子的设计和执行效率，最终直接影响到收敛速度。 高校排课一般只考虑周课表，根据课表的实际特点，我们采用矩阵编码，一个矩 阵y 表示一个可能的排课表。矩阵y 的行标题为班级名称，列标题为教学时间 片，每个学校可以根据自己的实际情况来划分时间片，进而确定时间片的多少， 也就是确定矩阵的列数。 在这里首先对排课系统中几个重要的数据库表进行说明：本学期的课程信息 表记录了本学期每门课程的信息，包括课程编号、课程名称、课程性质、总学时、 任课教师、开课班级、教室要求等字段；班级信息表包括班级编号、班级名称、 人数等字段；教师信息表包括教师编号、教师姓名等字段；教室信息表包括教室 编号、教室类型、可容纳学生数、是否已排课等字段。 可以根据班级信息表以及它与本学期课程信息表的关系，找到每个班的所有 课元，再根据这些课元以及本学期课程表和排课表之间的关系，找到这个班的所 有排课元。每周5 天，把每天上课的时间分成时间片，大学的课程一般都是两节 连上，假定每天有三个时间片，每周5 天，共涉及1 5 个时间片，用t l ，t z ， t 1 5 来表示。将这1 5 个时间片随机的分配给上述某个班的所有课元，也就排好了 一个班的课表。一个班的“排课元 的数目一定小于或等于1 5 ，如果小于1 5 则 有时间片未用到。把班级和教室作为一个变量来对待。对于班级而言，因为某个 学期开的课程和教师是固定的，因此可以把课程和教师作为一个变量来对待( 可 以用教师+ 课程的编号来代替这个变量) 。通过以上把班级和教室等同、课程与教 师等同的处理之后，原课表的五要素就转换化为班级、课程、时间三要素了，把 班级固定要上的课看作基因，染色体在这里就是所有班级和1 5 个时间片组成的 二维表。 ( 2 ) 建立初始种群 建立初始种群只要随机产生一定数量的染色体即可，并且要使产生的这个染 色体是可行的，也就是说要满足课表编排的约束条件，数学模型分析如下： 1 ) 初始种群解空间解空间x 是该班所有课程得到编排的课表，解可以表 示为 x l ，x 2 ，x l s ，x l ，x 2 ，x 1 5 是1 ，2 ，1 5 的一个排列，表示一 周授课的教学时间单元，x j 表示在j 时间单元的课程代号，初始解可选为( 0 ， o ) ，表示未编排任何课程。 2 ) 状态匹配数组 d nd 1 2 d 2 ld 2 2 d y id y 2 d y i s ( 2 1 ) 状态匹配数组d 用来表明给定班级任课教师排课情况，d i = ( d n ，d i 2 ， 第2 章主要排课算法分析 d i l 5 ) 表示教师i 在第j 个教学单元排课情况d i i _ 1 表明已排课d i j = 0 表明未排， i = l ，j = l ，1 5 ，y 表示给定班级的所学课目数，假设每位教师在该 班只任- - i 1 课程， 因此教师数也为y ， 若教师在该班不只任- - f - j 课程，可用 不同的别名代替。 3 ) 产生初始种群 初始化状态匹配数组； d nd 1 2 d 2 ld 2 2 d y ld y 2 = 0 ( d i j = 0 ) ( 2 - 2 ) 初始化班级数i = 0 ； 选定班级，确定该班的课程名通过教师信息库中所有担任该班教师的课程 中获取，班级课程名可与教师代码建立对应关系； 初始化解空间x = ( x l ，x 2 ，x 1 5 ) = 0 表明未对该班进行课表编排； 确定该班的所学科目数y 值，给定班级的周学时m 及每个教师在该班的 周教学时数n ； 根据课表编排的约束条件和教师的任课时数，在状态匹配数组d i i 要求的 位置上置l ( 若此位置已占用，另考虑其他未占用的位置) ，要求同一列只允许 一个位置占用，表明同一时段在给定班级只能有一个教师上课。此时即得到一个 随机解( 染色体) 。 x ( x i ，x 2 ，x 1 5 ) = l ，k 2 ，印啤k l ，k 2 ，釉 d y ld 蛇d y i 5 ( 2 3 ) 矩阵相乘实际是将y 个教师所任课程的代号随机填入班课表数组x 转化 为随机填入状态匹配数组d ，第i 个班级排课结束。 ( 3 ) 目标种群的适应度函数 班级课表编排寻求的是最优解，不是唯一解，为了寻求最优解，适应度函数 的选取至关重要。通过适应度函数来决定课表编排的优、劣程度，它反映了课表 编排的满意度。对于一个给定的优化问题，如何设计构造适应度函数是一个很关 键的问题。适应度函数构成每个个体的生存环境，根据个体的适应度可以决定它 在此环境下的生存能力。一般来说，好的染色体具有比较高的适应度即可以获得 较高的评价，有较强的生存能力。在初始种群之后，产生的肯定是一个可行解， 而一个好的课表就是要找到课程编排的最优解。排课优化最为重要的目标就是使 北京工业大学工学硕士学位论文 1 1 得教学效果最好，即使课程安排在好的时间里上课，尤其对于核心课程和相对重 要的课程。我们采用对不同的时间设定优劣系数k ( 值越大的越优) ，对不同的 课程给定优先值m l ( 值越大的越重要) ，那么系统的这个优化目标为： m a x ( f i ) = ( k fxmi)(2-4) 其中t i 为课程l 所安排的时间。第二个重要的目标就是教室资源的利用率问 题，一个合理优化的安排结果可以有效利用资源，一次授课中教学班人数c 。l 与 该教室容量c 彻i 的比值越大，则浪费越少，最大为1 表示刚好容纳，优化目标为： m a x ( 龟) = ( c xc 删) ( 2 5 ) 第三个重要的目标是课时分布的均匀性，一门课尽量分散在一个星期中，给 出上课时间间隔的满意度设为s l ，则优化目标为 m a x ( f 3 ) = y ( s ，) ( 2 6 ) 其他的优化目标还有教师对上课时间的偏好，学生课表均匀分布还是过于集 中等等，根据各高校的实际情况适当增删，在此不作详细叙述。最终个体的适应 度函数则根据各个目标值进行简单加权或者相乘，具体采用哪种方法可根据案例 的情况来定，简单加权较为稳定，收敛速度较慢，乘积则相反，我们采用前者， 得适应度函数为： ： m a x ( & ) = i 峨+ b 最+ c 6 + ：( 2 7 ) 各系数通过试验来确定。 ( 4 ) 遗传操作 对产生的初始种群用适应度函数进行检验，值大的生存下来，满意度不高 的对种群的个体进行交叉、变异操作产生新的种群，这样不断循环，直至产生 最优解。 具体操作流程： 计算每个种群的适应度函数值，按照选择概率选择一定的种群遗传至下一 代。 对适应度函数值不满意的种群，按照交叉概率，选择一定的种群对其个体 进行交叉操作，产生新的种群。 对适应度函数值较小的种群，进行变异操作，生成新种群。 对新生成的种群，计算每个种群的适应度函数值，不断循环，直至产生最 优解。 下面对选择算子、交叉算子、变异算子分别介绍： 选择运算用于模拟生物界去劣存优的自然选择现象，它从种群中选择出适应 度高的某种染色体，放入配对集合中，为染色体交叉和变异运算产生新的种群做 好准备。适应度越高的染色体被选择的可能性越大。选择操作的方法有很多，常 第2 章主要排课算法分析 见的有轮盘赌选择法、局部选择法、竞标赛选择法等。我们采用轮盘赌选择法， 首先将整个群体根据个体的适应度不同分布在轮盘上，适应度大的个体占的比例 大一些，适应度小的个体占的比例小一些。然后对每个个体的概率进行累积，所 有个体的概率和为1 0 0 ，每个个体占其中的一个百分比段。选择时系统随机产 生一个百分数，落在哪个个体的百分比段就选择哪个个体，这种选择方法对适应 度高的个体选中的机会相对就多，实现了优胜劣汰，同时也存在选中适应度小的 个体的可能性，这样又保证了群体的多样性，使保留在较差个体中的优秀基因段 也得以保存，设计时为了得到适应度越大越容易被选中的结果，对目标函数的设 计采用了求最大值的方式。 交叉算子是遗传算法中一个最为重要的操作，是复杂遗传算法设计的难点。 交叉点的选择一般有单点交叉和均匀交叉。单点交叉染色体靠近的等位基因可保 持在一起，使优良的基因片段得到继承。对于有些问题各个基因段之间相关性不 是很大，则希望交叉充分，采用均匀交叉会使收敛速度加快，考虑到排课中各个 班级之间合班授课的情况较多，即各个基因片段之间存在一定的约束，采用了单 点交叉的方式。 一 变异操作是随机改变染色体中任一授课时段，将时段随机抽取一点在设定范 围内改变。变异运算模仿了生物在自然遗传环境中由于各种偶然因素引起的基因 突变，通过变异染色体适应度有可能加强也有可能降低，但它确保了种群中遗传 基因类型的多样性，使搜索在尽可能大的空间中进行，获得最优解的可能性大大 加强。根据人类进化的规律，变异应该是往更好的方向发展，予个体继承了父个 体的特性，同时应有别于父个体，增加新的更好的特性。在变异过程中，一方面 是随机的，另一方面应有向高适应度的方向发展的趋势，因此我们采用“培养型 变异”策略，其基本思想是：当个体变异后产生了新的个体，比较新个体的适应 度与父个体的适应度，若新个体比父个体的适应度高，则用新个体替换原有个体， 否则，再进行一次变异。第二次变异对适应度不做检查，直接替换原有个体，这 样一方面保持了变异的随机性，另一方面含有向适应度高的方向发展的趋势。 经过上述有限代的遗传操作之后即可得出最优解。 ( 5 ) 冲突检测与消除 对每一个课程表二维数组进行冲突检测，然后用自动定位变异算子消除冲 突。首先，消除同一时间一个教师同时上- - f - 以上课程的冲突： 1 ) 对第一个课程表二维数组( 班级数，1 5 ) 读取它的第一行、第- n 的教师 编号； 2 ) 与二维数组同一列、下一行的教师编号比较，若相同，则随机产生一个 1 - 1 5 之间的整数m ，判断这一行第m 列的教师是否为特定教学时间，如果是则 重新产生随机数n ，否则将两个数组元素的值互换后再重新比较，直到无相同元 北京工业大学工学硕士学位论文 素为止； 3 ) 读取该列、第二行的教师名，重复2 ) 直到第一列的所有元素的教师名 不相同； 4 ) 读取课程表二维数组的第二列、第一行的教师名，重复2 ) 、3 ) 直到每 一行的所有元素的教师名不相同，即没有在同一时间一个教师同时上一门以上课 程的冲突，同理，教室冲突也可以通过这种方法消除。 2 2 4 用遗传算法解决排课问题的结果分析 用遗传算法解决高校自动排课问题有很多成功的案例，这些成功案例表明应 用遗传算法能够找到合理的课程安排，不仅能够满足课程编排的硬性约束，不存 在时间、教师、教室资源的冲突，而且能够遵循排课的基本原则，算法性能好， 求解速度比较快。但遗传算法本身较为复杂，编码和系统实现有定的难度，在 教学规模大，系统开发投入的人力和资金较多的情况下选用较为合适。 2 3 蚁群算法 2 0 世纪9 0 年代初意大利学者d o r i g o m a n i e z z o 依照蚂蚁觅食原理提出了第 一个“蚂蚁算法( a n tc o l o n ya l g o r i t h m ) ，这是一个群体智能的算法，成功地解 决了t s p 问题。 2 3 1 生物原型 蚁群算法嘲叫m 3 是受真实蚁群觅食行为的启发而产生的。仿生学家长期研究 发现蚂蚁在觅食过程中如果寻找到较大的食物需要回去求援，就会沿途留下一种 叫“臭迹外激素( 外激素代表一定的信息，以下我们称外激素为信息素) 的 挥发性物质，其他蚂蚁嗅到这个信息素的“味道 ，就会根据信息素的浓度的大 小来选择路径奔向目的地，并且沿途又留下信息素，于是又吸引更多的蚂蚁。一 段时间后，所有蚂蚁将都选择最短路径奔向食物，这是一个奇妙的大自然现象。 2 3 2 数学模型 设有m 只蚂蚁，问题规模为n ，b i ( t ) 表示t 时刻位于i 节点的蚂蚁数目， 下i j ( t ) 为t 时刻路径( i ，j ) 上的信息量。设初始时刻r 珏( o ) = 常数。用禁忌表 t a b u k ( k = l ，2 ，m ) 来记录蚂蚁k 当前所走过的点，禁忌表的内容随时调整。 第2 章主要排课算法分析 在寻优过程中，蚂蚁从当前节点转移到哪个节点是根据状态转移概率确定的。若 p k i j ( t ) 捌et 时刻蚂蚁k 由i 转移到j 的概率， 则 坐塑：! 幽! ，j a l l o w e d k r i r a ( t ) 口盼】， p k i j ( t ) = ( 2 8 ) l 0 否则 其中，a l l o w e d k = o ，1 ，n 1 一t a b u k ，r t u 是启发函数，表示边( i ，j ) 的能见度，一般取1 1 i j = d i ，d i j 表示节点i 和节点j 之间的距离。q 是边上 信息量的重要程度的参数，8 是能见度重要程度的参数。各路径上的信息量要适 时根据以下公式作调整： ti j ( t + r 1 ) = ( 1 - p ) ti j ( t ) + at i j ( 2 9 ) t i j = m 钿k ( 2 1 0 ) 式中，1 p 表示信息素残留因子， a t 嵇表示本次循环中( i ，j ) 路径上的 信息素增量，tk 目表示第k 只蚂蚁在本次循环中留在路径( i ，j ) 上的信息量。 有3 种不同版本的基本蚁群算法模型： ( 1 ) a m - d e n s i t y