（计算机应用技术专业论文）遗传算法的研究及其在ttp问题中的应用.pdf

摘要 摘要 时间表问题t t p ( t i m et a b l ep r o b l e m ) 是一类特殊的资源调度问题，是一个多因素优 化决策问题，也是组合优化中的典型问题。随着计算机的飞跃发展以及各高校教学管理 体制的完善，用计算机来辅助排课成为了各大高校急需解决的问题。本文以大连交通大 学研究生学院的时间表问题排课问题为研究对象，分析了其约束条件，建立了数学 模型，提出了基于遗传算法的改进算法，并用此算法解决排课问题。 遗传算法g a ( g e n e t i ca l g o r i t h m ) 作为- - l - j 新兴学科，从二十世纪八十年代开始迅速 发展。它是一种用于解决优化问题的并行寻优算法，已被广泛用于解决各类n p 问题。 标准遗传算法仍然存在一些缺陷，为了克服这些缺陷，本文设计了一个全新的改进 遗传算法m e g a ( m o d i f i e da n de v o l v e da l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m ) ，这一算法 在进化方式上与传统的改进遗传算法明显不同，最后用遗传算法常用的测试函数对 m e g a 算法进行数学分析，证实了它相对基本的遗传算法有一定的改进。 通过设计m e g a 算法的选择、交叉、变异算子等，证明了m e g a 算法能有效地消 除冲突，保证种群多样性，防止局部早熟收敛；通过一些典型函数测试验证了其有效性； 处理排课问题时把课程分为两类，简化了问题的求解难度。在变异过程中引入混沌理论， 在较优个体的变异操作中引入一个混沌小扰动，并把混沌运动的遍历范围“放大”到优 化变量的取值范围，通过一代代地不断进化，收敛到一个最适合环境的个体上，求得问 题的最优解。 根据大连交通大学研究生课程排课问题的特点，本文对遗传算法进行了多方面的改 进，重点分析了遗传算法、t t p 问题及其数学模型、面向对象技术，把理论研究和实际 应用结合起来设计开发了基于遗传算法的排课系统。 关键词：遗传算法；t t p ；排课；混沌 大连交通大学丁学硕十学位论文 a b s t r a c t t i m et a b l ep r o b l e m ( t t p ) i sas p e c i a lp r o b l e mo fr e s o u r c ea r r a n g e m e n ta n da m u l t i e l e m e n t so p t i m a ld e c i s i o np r o b l e m a n di ti sa l s oat y p i c a lc o m b i n a t i o n - o p t i m a l p r o b l e m a st h eq u i c kd e v e l o p m e n to fc o m p u t e rt e c h n i q u ea n dt h ep e r f e c t i o no fs c h o o l m a n a g e m e n t ，u s i n gc o m p u t e rt oa s s i g nc o u r s es c h e d u l i n gb e c o m e sap r o b l e mt h a tn e e d st o s o l v e 1 1 1 i sp a p e r , t a r g e t i n ga tt h es p e c i a lt t p _ _ t h es o l u t i o no fd a l i a nj i a o t o n gu n i v e r s i t y g r a d u d a t es c h e d u l i n g i sd i r e c t e dt o 也ea n a l y s i so f r e s t r i c t i o nf a c t o r sa n dt h ee s t a b l i s h m e n to f m a t h e m a t i cm o d e l ，p r o p o s e sam o d i f i e da n de v o l v e da l g o r i t h mb a s eo ng e n e t i ca l g o r i t h m w ed e v e l o pas c h e d u l i n gs y s t e mu s i n gt h i se v o l v e da l g o r i t h m g e n e t i ca l g o r i t h m ( g a ) i san e ws u b j e c t i t sa p p l i c a t i o nb e g a nt of l o u r i s hs i n c et h e e i g h t i e so ft h e2 0 sc e n t u r y 1 1 1 eg e n e t i ca l g o r i t h mi s an e wp a r a l l e lo p t i m i z ea l g o r i t h m ， w h i c hc a nb eu s e dt os o l v em a n yk i n d so fn p - h a r dp r o b l e m s s t a n d a r dg e n e t i ca l g o r i t h mh a ss o m ef a u l t s i no r d e rt oo v e r c o m et h e s ef a u l t s ，w e d e s i g n e da n e wh y b r i dg e n e t i ca l g o r i t h m m o d i f e da n de v o l v e da l g o r i t h mb a s e do ng e n e t i c a l g o r i t h m ( m e g a ) t i l i sa l g o r i t h mi sd i f f e r e n tf r o mt r a d i t i o n a lg a i ne v o l u t i o nm a n n e r , a n d t h e nw eu s es o m em a t h e m a t i cf u n c t i o n st oa n a l y s i so u rm e g a i th a sp r o v e dt h a tm e g a i s i m p r o v e dt h a ns t a n d a r dg e n e t i ca l g o r i t h m b yd e v i s i n go p e r a t o r s ( m u t a t i o n ，e l e c t i o n ，c r o s s o v e r ) o fg a ，m o d i f e da n de v o l v e d a l g o r i t h mb a s e do ng e n e t i ca l g o r i t h ma r ep r o p o s e dh e r e ，w h i c hc a ne f f e c t i v e l yd i s p o s et h e c o n f l i c t s o ，t h i sa l g o r i t h mc a ne n s u r et h ev a r i e t yo ft h ep o p u l a t i o n ，c a na v o i de a r l y c o n v e r g e n c ea n ds o m et y p i c a lb e n c h m a r kf u n c t i o n sh a v eb e e nt e s t e d c o u r s e sa r ed i v i d e dt o t w ot y p e st or e d u c et h ed i f ! f i c u l i t y i n t r o d u c i n gt h ec h a o st h e o r yw i t hm u t a t i o n , as m a l l d i s t u r i b a n c ei sa d d e dt ot h em o r ee x c e l l e n tm u t a t i o ni n d i v i d u a l sa n dt h es c o p ei sm a g n i f i e dt o t h es c o p eo fo p t i m a lv a r i a b l e a sp o p u l a t i o n sa r ee v o l v i n g ，i tw i l lf o c u so nt h em o s tp r o p e r i n d i v i d u a l e sa n dg e tt h em o s ts u i t a b l ei n d i v i d u a l e s a c c o r d i n gt ot h es c h e d u l i n gf e a t u r e so fd a l i a nj i a o t o n gu n i v e r s i t yg r a d u d a t ea c a d e m y s c u r r i c u l a , t h i sp a p e ri m p r o v e sg e n e t i ca l g o r i t h m ，w e i g h t i l ys t u d i e sg e n e t i ca l g o r i t h m ，t i m e t a b l ep r o b l e ma n di t sm a t h e m a t i c sm o d e l ，o b j e c t o r i e n t e d as c h e d u l i n gs y s t e mi sd e v e l o p e d u s i n gt h e s et e c h n o l o g i e sa n dg e n e t i ca l g o r i t h m k e yw o r d s ：g e n e t i ca l g o r i t h m ；t i m et a b l ep r o b l e m ；s c h e d u l i n g ；c h a o s i i 绪论 第一章绪论 1 1 课题研究背景、目的及意义 时间表问题t t p ( t i m et a b l ep r o b l e m ) 是一类特殊的调度问题，是最有名的复杂组合 优化问题之一，可描述为在资源有限的条件下将事件安排到时间段。根据约束条件、优 化目标、问题领域等的不同，时间表问题又可分为很多种类，其中包括工厂作业调度、 铁路时刻表安排、中小学及大学课程表问题等。随着高校扩招、学分制改革的进行，而 教师、教室等教学资源增长相对落后，排课冲突也越来越明显，冲突发生后最直接的办 法就是回溯和重排。传统的人工排课一般由经验丰富的排课专家集中数周时间进行编 排，协调其中出现的各类矛盾。这是一项相当复杂繁重的调度管理工作，非常容易出错。 近几年计算机在教学管理工作中得到普及应用，用计算机来实现劳动强度大、工作 效率低的手工排课工作，成为教学管理人员和计算机专家共同面临的一个难题。由于排 课问题本身的复杂性，一直没有很有效地解决。许多研究人员认为t t p 不可能自动解决， 其理由有：一种排课结果和另外一种排课结果孰优孰劣很难判断，往往需要人的主观感 觉去判断，而各人的评价标准不一致；搜索空间太大，计算机不可能达到最优解。 作为强有力且应用广泛的随机搜索和优化方法，遗传算法可能是当今应用最广泛的 进化计算方法之一。在过去的几年中，遗传算法将更多的注意力放在工业、教育领域的 优化问题上，并由此产生了一批新的研究和应用。 1 2 国内外研究现状综述 1 2 1 遗传算法的国内外现状 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，该算法由密执安大 学教授h o l l a n d 及其学生于1 9 7 5 年创建，其基本思想是基于d a r w i n 的进化论和m e n d e l 的遗传学说。与传统搜索算法不同，遗传算法从一组随机产生的初始解，称为种群 ( p o p u l a t i o n ) ，开始搜索过程。种群中的每个个体是问题的一个解，称为染色体 ( c h r o m o s o m e ) 。染色体是一串符号，例如一个二进制字符串。这些染色体在后续迭代中 不断进化，称为遗传。在每一代中用适应度( f i t n e s s ) 来衡量染色体的好坏，由前一代染 色体通过交叉( c r o s s o v e r ) 或变异( m u t a t i o n ) 运算形成，生成下一代染色体，称为后代 ( o f f s p r i n g ) 。根据适应度大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。 适应度高的染色体被选中的概率高。这样，经过若干代之后，算法收敛于最好的染色体， 它很可能就是问题的最优解或次优解。 大连交通大学工学硕士学位论文 作为强有力且应用广泛的随机搜索和优化方法，遗传算法川可能是当今应用最广泛 的进化计算方法之一。遗传算法作为一种有效的全面并行优化搜索工剧2 1 ，早被众多应 用领域所接受。遗传算法应用于决策树，分类器，模糊规则的获取等方面的文献不断涌 现。由于遗传算法解决问题以混沌、随机和非线性为典型特征【3 】，它为其它科学技术无 法解决或难以解决的复杂问题提供了新的计算模型【4 j 。对于数据的嘈杂无序的特征，遗 传算法是有效解决此类问题的方法之一【5 1 。遗传算法是模拟自然进化的通用全局搜索算 法，避免了搜索过程中的局部最优解 6 1 ，在组合优化方面发挥更大的优势。 1 2 2t t p 问题的国内外现状 6 0 年代末，国外就有人开始研究课表编排问题。1 9 6 2 年，g o t l i e b 曾提出了一个课 表问题的数学模型，并利用匈牙利算法解决了三维线性运输问题。此后，人们对课表问 题的算法、解的存在性等问题做了很多深入探讨。九十年代以后，国外对课表问题的研 究仍然十分活跃。比较有代表性的有印度的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 等。目前，解决课表方法的问题有： 模拟手工排课法，图论方法，拉格朗日法等多种方法。国外的研究表明，解决大规模课 表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解， 将是一个有希望得到成功的方法。 在国内，对课表问题的研究始于2 0 世纪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 e s c h e d u l e 0 系统，大连理工大学的智能教学组织管理与课程调度系统等。这些系统大都 是模拟手工排课过程，以“班为单位，运用启发式函数来进行编排的。这些课表编排 系统往往依赖于各个学校的教学体制，不宜进行大量的推广。正如华东交通大学的郑晓 芳副教授1 7 】在校学报排课管理系统的设计中所述：“通过实践我们发现不同的学校， 管理政策不同，其教务管理软件很难实现真正意义上的通用，各高校应针对自己的情况 开发出适合自己的应用软件。”可见排课系统再怎样完善也很难满足各个学校的不同教 学体制的要求。 近4 0 年来，人们对课表问题的计算机解法做了许多尝试。其中，课表编排的整数 规划模型将问题归结为求一组0 1 变量的解，但是其计算量非常大。解决o 1 线性优化 问题的分支定界技术却只适用于规模较小的课表编排，m i h o c 和b a l a s 将课表公式 化为一个优化问题，k r a w c z k 则提出一种线性编程的方法。 此外，有些文献试图从图论的角度来求解课程表的问题，但是图的染色问题也是 n p 完全( n o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e ) i n - 题，只有在极为简单的情况下才可以 2 绪论 将课表编排转化为二部图匹配问题，这样的数学模型与实际相差太远，所以对于大多数 学校的课表编排问题来说没有实用价值。 从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人 意。一方面原因是作为一个很复杂的排课系统，要想面面俱到是一件很困难的事；另一 方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程 中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应 用中这是很难实现的事情。 1 2 3 遗传算法求解1 曙问题的国内外现状 排课问题是个典型的时间表问题，由于该问题具有较大实用价值和问题模型的代表 性，吸引了许多学者对该课题进行研究，从各个角度对问题进行了分析，提出了许多模 型和算法，如：王璐等利用多a g e n t 之间的协商来实现排课【8 】；潘以锋则通过对教学任 务安排优先级，采用优化资源查找算法来解决排课问题【9 】。但这些模型和算法有的智能 性并不强，需要过多的启发信息和人的参与，有的虽然可以排出课程表，但课表的质量 并不高，如课程对时间段的特殊需求未被考虑，或者教师的偏好未被考虑等。事实上， 在1 9 7 5 年，排课问题已被s e v e n 等人论证为n p 完全问题，而对于这类问题，只能利 用智能算法求得满意解。遗传算法是一种适合求解那些带有多参数、多变量、多目标和 在多区域但连通性较差的n p c 优化问题的智能优化算法，而排课问题正具有这些特点。 然而由于g a 本身的固有不足，许多学者提出把g a 与局部搜索方法有机结合起来 解决排课问题，是改进g a 性能的一个卓有成效的方法。这种混合型遗传算法不但模拟 了生物种群的学习过程，而且事实上还模拟了种群的个体在其生命周期内具有学习行为 这一生物现象。禁忌算法t s ( t a b us e a r c h ) 是一种局部搜索算法，因此陈守家【lo 】等将g a 结合t s 来求解排课问题。并行遗传算法具有较强的全局搜索能力和并行性，但局部搜 索能力差，禁忌搜索算法比较适合于局部搜索，所以并行遗传算法和禁忌搜索算法结合 也是解决排课问题的一种方法。本文是在遗传算法的基础上提出一种改进的遗传算法来 解决排课问题。 1 3 研究目标及主要内容 本课题的研究工作是结合大连交通大学研究生学院的排课工作，对教学工作研究的 实际需求而开展的。结合上述背景，提出数学模型和基于遗传算法的新算法，结合大连 交通大学研究生学院的排课系统，将遗传算法应用于教育领域。本文的主要研究内容有： 遗传算法理论分析 3 大连交通大学工学硕士学位论文 介绍了遗传算法的基本概念和基本思想，分析了遗传算法中染色体编码方案、适应 度函数构造及遗传算子的设计和改进方法，同时对改进m e g a 算法的应用流程和算法 也做了分析。 t t p 问题的分析 分析了t t p 问题，总结其共性，确定大学课程表编排问题是一类复杂而典型的t t p 问题，分析从最原始的人工排课到计算机排课的思想过程，从而提出解决t t p 问题的数 学模型。 u m l 技术分析 全面阐述了统一建模语言u m l ( u n i f i e dm o d e l i n gl a n g u a g e ) 的相关知识，就排课问 题用面向对象思想进行了分析；重点探讨采用用例图、类图、状态图和顺序图来分析排 课问题。 基于遗传算法的t t p 问题的应用研究 通过对遗传算法、t t p 问题和u m l 技术的分析，在利用面向对象技术分析的基础 上，提出一种基于遗传算法的r r p 问题求解模型，并将其应用于大连交通大学校研究生 学院的排课管理系统。通过实验证明了算法的有效性和可行性，实验效果良好。 1 4 本文结构 全文组织如下：第一章是绪论部分，系统回顾了遗传算法和1 v r p 问题的发展历程和 概况，结合我校研究生学院的排课问题指出了论文选题的内容和意义，并对论文作了概 括；第二章详细介绍了遗传算法的基本原理和方法，详细分析了遗传算法中的操作算子 及其作用，对面向对象技术作了详细概述；第三章主要介绍了t t p 问题，首先概述了 t t p 问题的共性及其数学解决模型，然后对t t p 问题的特例排课问题，从人工排 课、计算机排课和u m l 技术三个方面进行分析，总结解决排课问题的算法及求解模型； 第四章介绍了用标准遗传算法求解t t p 问题的过程，提出标准遗传算法的不足；第五章 是本论文的核心部分，详细介绍了用改进的m e g a 算法分析求解排课问题的过程，并 对实验程序定义的数据结构和程序核心内容作一介绍；第六章主要介绍了遗传算法的应 用实例，介绍了系统所采用的技术以及模块的划分，对主要功能作了详细介绍。最后对 全文进行了总结并提出了进一步的研究方向。 4 第二章遗传算法和u m l 技术 第二章遗传算法和u m l 技术 2 1 引言 本章主要对目前已有的一些遗传算法基本原理的研究和分析进行了总结，首先详细 阐述了遗传算法的原理和思想、基本过程、交叉和变异、收敛性分析；然后介绍了u m l 技术的内容体系和建模机制。 2 2 遗传算法 2 2 1 遗传算法原理 遗传算法基于达尔文生物进化的“适者生存 理论，其模拟生物进化过程实现问题 优化的基本原理描述如下： 1 利用一个种群表示问题的一组候选解，种群中每个个体的染色体代表问题的一 个解。采用某种编码方案( 如二进制数、浮点数或符号等) 对染色体进行编码。 2 利用目标函数计算种群中各个个体的适应值，以评价个体的优劣。通过一定的 选择策略从种群中挑选若干个体繁殖后代，种群中适应能力强的个体有较大的繁殖机 会，劣质的个体将被淘汰。 3 杂交( 即交叉) 和变异操作模拟生物繁殖中的重组和变异现象。经过若干代的进化 后，得到满足约束的个体。 这样，遗传算法采用启发式搜索能在一个较大的问题解空间中有效发现最优解或次 优解。 遗传算法的基本思想可归为两点：第一，将物种进化理论用于求问题的解，物种进 化又可分为遗传和变异两个方面；第二，只有最适合环境的物种才能保留下来，因而需 经反复求解后才可以得到最佳的解。 在求解具体问题时，g a 首先要求构建一个初始群体( p o p u l a t i o n ) ，群体中的任一个 体均是原问题一个可行解的编码，从而整个初始群体构成问题解集的一个随机采样。然 后引入一个适应度函数来评价群体中的个体的优劣程度，以供“选择 优胜劣汰的依据。 其次引入门德尔摩根遗传学说中的“交叉、“变异 概念，对选出的“优胜 个 体进行“交叉 、“变异 生成新的个体。最后根据一定的选择策略，重组新一代种群。 这样反复迭代下去直至找到“满意解”或迭代足够长的时间为止。 标准遗传算法的伪代码描述如下： p r o c e d u r es g a 大连交通大学_ t 学硕十学位论文 i n i t i a l i z ep ( 0 ) ； t = 0 ； w h i l e ( t 班级课表 操作2 教学楼班级 + 周六9 、l cl 节 + 班级i d + 班级i d 0 + 教学楼i d j 架1 ，# j = u + 专业i d + 班级名称+ 教学楼名称 + 课程i d + 所属专业l d 11 操作2 操作l 操作11 一 图3 5 排课系统类图 f i g 3 5c l a s so fs c h e d u l i n gs y s t e m 资源管理、计划管理、排课管理用例用到了图3 5 中的所有类，显然这些类对完成 整个排课系统是必不可少的，而系统管理用例中会用到时间安排信息类、学年学期类， 计划管理用例中用到教学计划类，工作量管理用例中用到工作量类，所以在实现本系统 时还应加入这四个类。其中，时间安排信息类中设有的属性有每周上课天数、上课节次、 本节课时数、开始时间和结束时间，操作为“操作1 ”。学年学期类中包含属性学年、 学期、本学期开学时间和放假时间，操作为“操作1 。教学计划类包含的属性有教学 计划i d 、课程名称、教材名称、学时数、所属学期、上课班次、所属教研室、考试考 第三章时间表问题 查类型、前序课程等，操作为“操作1 。工作量类包含的属性有工作量i d 、系数1 、 系数2 、教师i d 、课程i d 、课时等，操作有查询( ) 、计算工作量( ) 、保存( ) 、导出到 e x c e l 表( ) 、打印( ) 、退出( ) 。这四个类的增加体现了面向对象分析方法o o a ( o b j e c t o r i e n t e da n a l y s i s ) 模型的进一步完善，因此，整个排课系统共涉及十六个类。 3 排课系统的状态图 一个状态图主要描述某个对象从一个状态到另一个状态的控制流，描述了一个事物 整个生命周期中的状态迁移。排课系统中生命周期最明显的就是课表，随着新学期开始 被创建，随着学期结束其生命周期也就结束。 9 未生成 吟阱一 排课结束 图3 6 排课系统状态图 f i g 3 6s t a t u so fs c h e d u l i n gs y s t e m 排课过程实质上就是在教师、教室、班级和课程之间取得一个有机的合理的对应关 系，在没有固定因素的情况下，四个因素对应起来排课的时间复杂度是很大的，具体进 行排课时可以把变动的因素转换成固定的因素，如在学期开始时，根据教学任务书上的 规定，某一位教师讲授哪门课程是确定的，所以四个变动因素就简化成了三个因素，再 根据教学计划可以确定这门课提供给哪个班级上课，所以只要能排除班级的冲突，三个 因素的问题求解就简化成了两个因素的求解，在此基础上进行排课时工作量大大减少。 大连交通大学工学硕士学位论文 可以选取三种排课方式，按教师排课、按班级排课和按教室排课，其中以按教师排 课为主，按班级和按教室排课为辅进行排课，辅助排课的进行就是把按教师排课得到的 课表进行优化的过程。综合分析后得到o o a 状态图，如图3 6 所示。 其中符号解释如下：状态表示成四角均为圆角的矩形，内部水平线上面的部分是状 态名称；水平线下面是内部转换分栏，该分栏列出了对象在这个状态中所执行的内部动 作或活动的列表，动作可以并发执行，用虚线表示。动作标号有三种：e n t r y 标识了进 入该状态时执行该动作，e x i t 标识了在退出该状态时执行该动作，d o 活动是在对象处于 一个状态中的整个阶段执行的一个动作或动作的集合。表示初始状态，表示终止 状态。箭头表明了状态之间的迁移，箭头的上面部分说明了迁移的条件，没有条件的箭 头表示状态自动迁移。当某一个状态要经过循环往复才能完成时，用( v 表示循环【2 3 1 。 图3 6 的整个流程解释如下：进入排课子模块开始排课时教务人员在没有选定排课 对象之前得到的是一张空课表，空课表的形成是调用了时间安排信息类，形成了横向注 有星期标记，纵向标有每天上课节次标记的二维课表样式。当选定教师为排课对象后， 需先设置一些较强的约束条件，如难度系数大的课程安排在上午上课、选修课程安排在 晚上上课等，在此基础上进行自动或手动排课，排课进行中要排除班级和教室的冲突， 基本课表形成后，如果不能满足教师的要求可以通过调课来达到其要求，或者用组合优 化算法对课表进行优化，如此往复，直到形成满意的课表后可以查询并打印。 4 排课系统的顺序图 顺序图除描述对象间的交互行为外，还揭示了一个特定场景的交互，为详细描述排 课过程的进行，选取一次排课过程( 生成教师课表) 为场景，采用回朔算法实现排课过程， 具体描述如图3 7 所示。 顺序图是二维的，垂直方向表示时间，水平方向表示不同的对象或参与者。虚线表 示对象生命线，位于对象符号下，生命线可以在某处分裂成两条或多条并行的生命线， 也可以在某个后继点处合并。生命线之间的箭头表示对象之间的通信。循环标记用一个 矩形框与其所包含的一组消息表示，由方括号围起来的标识表示停止( 或继续) 循环的条 件。 整个流程解释如下：当外部消息触发一门课程开始排课时，首先获取课程的i d ， 在教师课表中查找没有安排任何课程的时间，若周一至周五没有合适的时间安排此课 程，则把该课程调至周末；若查找到合适的上课时间，则从教师授课任务书中得到开设 此门课程的班级i d ，再次在教师课表中查找满足课程和班级的同时没有冲突的时间， 反复循环，直到课程和班级同时没有冲突为止。同样，当没有合适的时间时，请求系统 做调课等处理。若课程和班级的冲突已经排除，再根据上课人数和占用教室的类型查找 2 4 第三章时间表问题 匹配的空教室。如此反复，直到查找到课程、班级和教室共同没有冲突的时间为止；若 仍没有合适的时间，做调课等局部异常处理。图中的“时间片+ + 表示按查找算法查找 下一个满足条件的上课时间。图3 7 只说明一次排课过程，若任务书规定此课程一周内 安排，1 次课，则图中所示过程需循环d ( 甩) 次，若此教师安排了m 门课程，则最外层需要 d ( 肌) 次循环。依次类推，可以完成整个学校全体教师的课程安排，从而得到各个教师 的课表。 图3 7 一次排课过程顺序图 f i g 3 7s e q u e n c eo f o n c es c h e d u l i n g 没有 找到 请求 处理 3 2 4 排课算法数学模型 排课问题是一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊要求 为约束条件的组合优化问题，其实质就是解决各要素之间的冲突。为了达到最好的教学 效果应遵循一定的要求，下面通过教学排课算法的数学模型来进一步实现排课算法。 1 问题的定义 设排课系统中用到的基本资源定义如下： 班级集合：b = 6 。，b 2 ，6 r ，b r ) 课程集合：c = 乜，c 2 ，c ，c 教室集合：r = ，l ，r 29 0 lo ，r s ) 时间集合：s = s l ，s 2 ，s ， 大连交通大学工学硕士学位论文 教师集合：t = f l ，t 29 9 缸，r 2 优化模型 将约束条件分为两级约束，一级约束为必须满足的基本约束，二级约束是在一级约 束满足的基础上进行调整，以便更好地满足要求。 一级约束条件集合r e q = r e q l ，r e q 2 ，r e q 3 ，r e q 4 ，r e q 5 ，r e q 6 ，r e q 7 ) 的描述如下： r e q ：某一时间片一个教师只能上- n 课程； s7 x 岛啊。1 ( 3 1 ) n = l j = lt = l 其中：k = 1 ，k ；m = 1 ，m 。 x c： 1 篓鉴i 在时间和教室。上课程巳 ( 3 2 ) b t r s t k s m 一10 否则 v 7 r e q ：某一教室的某一时间片只能被一门课程占用： rrr x 讹“1 n = lt = lt = l ( 3 3 ) 其中：r = 1 ，t ；d = 1 ，d 。 _ 仉。： 1 教室在时间由教师t k 上课程巳(34)lihl “岛掣i 一1 0口外j 、j 7 r e q ，：某班学生在某一时间片只能被安排在一个教室上课5 x 啪。l 其中：f = 1 ，t ；d = 1 9 o0 9 d 。 f 1 班级包在时间s 册上教师t 。的课程巳 _ 慨2 10 否则 r e q 4 ：某教师，在时间s 。时不能上课； x c b l v i s j = 0 其中： i = k ，j = m ，n = l ，n ，t = 1 ，t ，s = 1 ，s 。 ( 3 5 ) ( 3 6 ) ( 3 7 ) 第三章时间表问题 r e q ，：某课程c 。必须安排在预定的时间s 。上； x c l b l 。t s j = 1 其中： i = n ，j = m ，k = 1 ，k ，t = 1 ，t ，s = 1 ，s 。 r e q 。：同一课程不能在连续的时间片内连续开课； ( 3 8 ) x 6 ，；“囊x 6 ， “= 0 ( 3 9 ) 其中：刀= 1 ，n ；t = 1 ，t ；s = l ，s ；k = 1 ，k ；m = 1 ，m 。 r e q ，：某些课程对教学设备有特殊的要求。 解决时间表问题有时需要考虑所有的约束条件并且需要满足这些条件，这种情况下 可以成为搜索问题；但也可以把时间表问题转化为优化问题，即需要的时间表问题在满 足基本约束( h a r dc o n s t r a i n t s ) 的前提下，尽量使给定的目标函数( o b j e c t i v ef u n c t i o n ) 最大 ( 或最小) ，给定的目标函数也称为软约束( s o f tc o n s t r a i n t s ) 。 软约束条件是在排课过程中可以满足、也可以不满足的约束条件，是在满足排课硬 约束的基础上能尽量满足的约束条件，以下几个是在排课过程中经常要满足的约束条 件： ( 1 ) 课程安排节次函数石。课程的上课教学效果与上课的节次是有联系的，尽量将 课程安排在教学效果较好的节次中。 ( 2 ) 课程周次组合函数 。对于周学时大的课程( 4 ) ，应该将其进行隔天安排，具 备较好的分散度的课程才有好的教学效果。 ( 3 ) 满足教师期望条件函数六。排课需要考虑教师提出上课时间和上课地点的要 求。 ( 4 ) 班级课表日课时分布函数 。 3 求解目标 由上可见，排课问题是一个在约束条件下的多目标组合优化问题。对于组合规划问 题，如果想找到最优解，必须有足够的约束条件来实现，因此将各软约束条件作为优化 的目标函数，将各硬约束条件作为其约束条件。 建立数学模型： m a x 厂( x ) = ( 石，厶，以，厶) 大连交通大学t 学硕十学位论文 r e q ： r e q l r e q 2 r e q 3 r e q 4 r e q 5 r e q 6 r e q 7 3 2 5 解决排课问题的基本算法 排课问题早在7 0 年代就证明是一个n p 完全问题，即算法的计算时间是呈指数增长 的，这一论断确立了排课问题的理论深度。对于n p 完全问题目前在数学上还是没有一 个通用的算法能够很好地解决。解决n p 完全问题只能靠近似算法，所以下面介绍几种 常用的设计思想，包括动态规划、关联规则算法、优化算法、模拟退火、遗传算法等。 1 动态规划法 动态规划是将求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直 到可以直接求出其解的子问题为止。分解成的所有子问题按层次关系构成一个子问题 树。树根是原问题。原问题的解依赖于子问题树中所有子问题的解。动态规划算法通常 用于求一个问题的某种意义下的最优解。设计一个动态规划算法，通常可按以下几个步 骤进行： ( 1 ) 分析最优解的性质，并刻划其结构特征； ( 2 ) 递归地定义最优解； ( 3 ) 以自底向上的方法计算出最优解； ( 4 ) 根据计算最优解时得到的信息，构造一个最优解。 步骤( 1 ) 弋3 ) 是动态规划算法的基本步骤。在只需要求出最优解的情形，步骤( 4 ) 可以 省去。若需要求出问题的一个最优解，则必须执行步骤( 4 ) 。此时，在步骤( 3 ) 中计算最 优解时，通常需记录更多的信息，以便在步骤( 4 ) 中，根据所记录的信息，快速地构造出 一个最优解。 2 关联规则算法 在孙建平、梅晓勇、肖政宏、史忠植的关联规则在高效智能排课系统中的应用 中【2 1 1 ，采用布尔型关联规则f p g r o w t h 算法的思想来处理排课问题。考虑了班级冲突、 教师冲突和教室冲突，避免了排课冲突，能够基本满足要求，但对于多学时课程的离散 性问题、好的教学日和教学时间点如何合理分配等问题没有很好的解决。 3 优化决策法 第三章时间表问题 ( 1 ) 分批优化法。排课问题中一般要考虑至少上百门甚至上千门课程，因此，采用 分批使用匈牙利算法来减化编排，称之为分批优化匈牙利算法 2 2 1 。该方法的优点是能求 得每批的最优解，如分批的合理，且每项赋值能正确反映每门课的具体情况( 如主干课 在上午上课时间的取值要大于一般的课，不希望上课的时间可能取值很小等) ，就可得 到全局较满意的解。缺点是分批和取值完全合理比较困难，因为合理取值需要长期使用 的验证和对教学规律的深刻认识等。另外，对特殊要求( 如对教学场地和设备以及一次 连上3 节或4 节的课等) 无法解决，在编排过程中需人工干预较多( 如一个教师有多门课 时) ，当课程门数较大时运算时间较长。 ( 2 ) 分组优化决策算法。分组优化决策算法就是模拟“人工 排课的一种方法【2 3 1 。 先难后易原则是多约束条件下排课表成功的要点之一，因而逐批排课时，在待排的课程 集合中挑选排课难度大的课程组先排；其次对课程组排课时，先搜索本课程组的课程在 当前的阶段课表条件下，所有可用的时间模板和教室，并用优化方法抉择出其中的特定 时间模板和教室，将本课程组各个课程排入课表。优化抉择的原则是，所选择的某个时 间模板及教室，应使与本课程组相关的课程，在后续排课时产生的不利影响要小。 4 模拟退火算法 课程表问题的特点说明，一个好的排课系统，通常要使用启发式算法，而且要与用 户有很强的交互性，可以由用户确定每个条件的权值，并可根据对排课结果的不同看法， 对一条件的权值作调整和重排，以此满足不同用户对课表质量的要求。而模拟退火算法 s a a ( s i m u l a t e da n n e a l i n ga l g o r i t h m ) 是一种启发式的随机搜索算法，往往能在较短的时 间和较大的解空间内找到最优解，对求解课程表这样的组合优化问题是很有效的。为此， 对求解组合优化问题很有效又能提供交互性的模拟退火算法可以用来解决课表问题，其 目标函数诸因素的权值可以由用户设定和修改，从而使退火结果所获得的解尽可能满足 不同用户对课表质量的要求1 2 4 彩j 。 5 遗传算法 用遗传算法来解决排课时间表问题在国外早就有了较多的应用 2 6 - 2 8 l ，如日本的 s i g e r u 采用遗传算法中加入控制约束的方法解决大学课表安排问题，意大利的c o l o m i 等人用遗传算法求解高中课程表的安排问题。在国内，使用遗传算法来解决排课问题也 有了较多的报道【2 邺6 1 。在现有的遗传算法求解排课问题中，能够对其使用的学校的排课 问题进行求解，在一定程度上取得了很好的成果，但处理的都是单目标问题，即使有多 个目标，也采用了线形加权法生成一个目标进行处理，所求得的解是一个非劣解，而非 一组非劣解。 大连交通大学工学硕十学位论文 3 3 排课时间表问题研究的目的和意义 在大连交通大学研究生学院的教学活动中，有一系列管理工作。其中，教学计划的 实施是一个重要的环节，每学期管理人员都要整理教学计划，根据教学计划下达教学任 务书，然后根据教学任务书编排课程表。学期末还要安排期末考试及补考事宜。在这些 教学调度工作中，既有大量繁琐的数据整理工作，也有严谨思维的脑力劳动。此外，还 要填写大量的表格，因此工作非常繁重。加之教学改革，招生人数的增加及教室设备的 不足，不但增加了工作的难度，而且要求管理工作更加快速准确。为此，研究生学院自 然希望用先进的管理手段完成这些工作。如何利用有限的师资力量和有限的教室资源， 在最短的时间内排出一个合理的课表，这对正常教学秩序的维护和教学效果的提高有重 要的作用。目前，大连交通大学研究生学院排课工作大多手工进行，由经验丰富的教务 人员集中数周时间进行编排、协调出现的各种矛盾，在这个基础上再由排课专家反复检 查合理性，修正课表，直至符合要求为止。这是一项繁重复杂的调度工作，主要依靠人 长年积累的经验知识来完成。因此，要在以上众多复杂因素下运用各种知识建立合理自 动排课模型，并且在排课系统中加以应用，这就是本课题要研究的主要问题。 排课系统是一个极其复杂的信息决策系统，目前尚未有普遍适用并反映良好的计算 机排课系统，所以研究具有一定通用性的排课算法对于教务管理工作和教育事业的发展 具有重大的现实意义。大连交通大学研究生学院原有系统模拟手工排课虽然在一定程度 上提供了很大的方便，但是还是有很大的缺陷，而且没有充分体现出排课系统的自动化 和智能化。本课题正是出于这一目的而提出来的，以达到排课系统能根据教学计划的内 容以及一些限制条件自动生成课程表，充分体现自动排课的智能化，从而减轻排课的工 作量、提高排课的效率和科学性。因此本课题具有很重要的实际意义。 本章小结 本章首先介绍了对t t p 问题及t t p 问题的特例排课问题的认识，首先全面认 识了1 v r p 问题、分析了t t p 问题的硬、软约束条件，提出了解决t t p 问题的通用数学 模型；并对排课问题作进一步的研究，从人工排课的思想、计算机排课过程和u m l 技 术的用例图、类图、状态图、顺序图来分析解决我校研究生学院的排课问题，从中提出 解决排课问题的通用数学模型，分析了当前解决排课问题常用的方法。最后对本课题的 研究目的和意义作了进一步的阐述。 3 0 第四章标准遗传