（计算机应用技术专业论文）基于混合算法的考试时间表问题研究.pdf

湖北工业大学硕士学位论文 摘要 时间表问题是一类特殊的资源调度问题，广泛应用于学校课程和考试的时间 安排、各类大型会议、体育比赛、航班( 火车、飞机、轮船等) 时刻表的制定等。 由于考试时间表问题属于n p 完全问题，随着求解规模的扩大，传统的求解算法将 很难得出其优化解。 根据大学时间表问题的特点，我们分析讨论了考试时间表问题的各种约束条 件，对考试时间表问题建立了数学模型。提出了大学考试时间表问题拆分化简方 案，使问题的数学模型适合分步求解。遗传算法是一种借鉴生物界自然选择和进 化机制发展起来的算法，具有高度并行、随机、自适应强的特点，是一种非常有 效解决n p 完全问题的方法。模拟退火算法是人们从自然界固体退火过程中得到启 发并从中抽象出来的一种随机优化算法。本文综合了统计物理学和局部搜索方法 的思想，通过研究遗传算法和模拟退火算法最终提出一种求解大规模组合优化问 题，特别是n p 完全问题的有效近似算法遗传模拟退火法。最后对考试科目考 试时间确定问题进行了求解试验，并分析比较不同算法不同参数取得的试验结果。 关键词：时间表，遗传算法，模拟退火算法，遗传模拟退火算法 湖北工业大学硕士学位论文 a b s t r a c t t i m e t a b l ef o rt h ei s s u ei sas p e c i a lk i n do fr e s o u r c es c h e d u l i n g ，w i d e l yu s e di nt h e s c h o o lc u r r i c u l u ma n de x a m i n a t i o ns c h e d u l e ，v a r i o u sl a r g e s c a l ec o n f e r e n c e s ，s p o n s c o m p e t j t i o n s ， s c h e d u l e d( t r a i n s ， p l a n e s ，s h i p s ，e t c ) ， s u c ha st h ef b r m u l a t i o no f t i m e t a b l e 。t h ee x a m i n a t i o nt i m e t a b l ei sn p c o m p l e t ep r o b l e m ，a sf 0 tt h ee x p a n s i o no f t h es c a l e ，t h et r a d i t j o n a la l g o r i t h mw i l lb ed i f 丘c u l tt oc o m et ot h eo p t j m a ls o l u t i o n a c c o r d i n gt ot h et i m e t a b l ef o rt h eu n i v e r s i t yo fc h a r a c t e r i s t i c s ，w ed i s c u s s e dt h e t i m e t a b l ef o rt h ee x a m i n a t i o n0 fv a r i o u sc o n s t r a i n t s ，0 nt h ee x a m i n a t i o nt i m e t a b l ef o r t h ee s t a b l i s h m e n to fam a t h e m a t i c a lm o d e l u n i v e r s i t ye x a m i n a t i o n sp r o p o s e dt i m e t a b l e f o rr e s o l u t i o o ft h em i n i m a l i s ta p p r o a c ht ot h em a t h e m a t i c a lm o d e lf o rs t e p - b y s t e p s 0 1 u t i o n g e n e t i ca l g o r i t h mi sar e f 色r e n c eb i o l o g i c a le v 0 1 u t i o na n dn a t u r a ls e l e c t i o n m e c h a l l i s mf o rd e v e l o p m e n to ft h ea 1 9 0 r i t l l i i l ，h i 曲l yp a r a l l e l ，r 卸d o m i z e d ，s t r o n g a d a p t i v ec h a r a c t e r i s t i c s ，i sav e r ye f i e c t i v es 0 1 u t i o nn p c o m p l e t ep r o b l e m s i m u l a t e d a n n e a l i n ga l g o r i t h mi sp e o p l ef 】0 mt h es o l i dn a t u r ea n n e a l j n gp r o c e s sa n db ei n s p i r e d b vt h ea b s t r a c tf i 0 mar a n d o mo p t i m i z a t i o na l g o r i t 血i nt h i sp a p e r ，s t a t i s t i c a lp h y s i c s a l l dl o c a ls e a r c hm e t h o d so ft l l i n l 【i n g ，b ys t u d y i n gg e n e t i ca l g o r i t h m sa n ds i m u l a t e d 锄e a l i n ga 1 9 0 r i t l l i i lf i n a lp r o p o s a l sf o r al a r g e s c a l ec o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m s ，i np a r t i c u l a rt h en p - c o m p l e t ep r o b l e m se 骶c t i v e l ya p p r o x i m a t i o na l g o r j t h m 。 g e n e t i cs i m u l a t e da n n e a l i i l gm e t h o d f 鼍n a l l y ，t h et e s ts u b j e c t se x a m i n a t i o nt i i i l e t 0 i d e n t i f yp r o b l e m sw e r es o l v e dt e s t ，题d 卸a l y s i sa n dc o m p a r i s o no fd i f i e r e n tp a r 锄e t e r s o ft h ea l 霉r o r i t h i nf b rd i f f e r e n tt e s tr e s u l t s k e y w o r d s ：t i m et a b l e ，g e n e t i c 龇9 0 r i t h m s ，s i m l l l a t e da n n e a l 通g 舢9 0 r i t h 】【i lg e n e t i c a n ds i m u l a t e da n n e a l i n ga 1 舒丽t h m 湖业j 堂大学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作者签名：子l 竹 日期：加陴石月上日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名：孙学 日期：久o 伴歹月工日 指导教师签名：詹撑文 日期：9 绛6 月) 日 湖北工业大学硕士学位论文 1 1 研究背景 第1 章引言 目前许多高等院校的期末排考工作任务艰巨复杂，每次安排考试课程大约在 上千门左右。然而面对这一繁重的资源安排和处理工作，长期以来高校教务部门 一直主要靠手工完成，使排考结果既不科学也耗费了大量人力。随着办学规模逐 渐扩大，专业不断更新和增加，国内各所高校都面临着由于扩招学生带来的教学 资源严重不足的情况，因此针对于教学资源日益紧张的高校，合理高效的解决排 考问题愈益突显，急需找到有效的排考算法，达到考试资源的最优组合。 由于国内的高校教学方式与国外的一些学校有所不同，国内的学者把更多的 目光投给了授课时间表，而对考试时间表问题关注的较少，且在编排考试时间表 时，人们似乎找到了一种快速手工编排方法。以某高校为例，大学本科有四个年 级，每天上下午各有一个考试时间段，因此在手工编排考试时间表时，把一年级 的考试放在第一天的上午，把二年级的考试放在第一天的下午，把三年级的考试 放在第二天的上午，四年级的考试放在第二天下午，这样编排工作的压力就减轻 了很多，且自然而然地满足了学生不希望连续参加考试约束。然而这样快速的编 排方法是用以牺牲时间资源、空间资源为代价换来的。在国内高等院校，一二年 级的考试科目数量远大于三四年级的考试科目( 因为三四年级，实习、实践工作较 多) ，且一二年级跨系别的公共考试科目较多，而三四年级本专业考试科目较多， 因此用这样方法编排的考试时间表必定需要更多考试时间与空间，且不能保证对 每个考试时间的考场资源进行更充分地利用。另外对于规模较大的学校，在进行 手工编排考试时间表时，哪怕仅仅是对所有考试事件与时间考场做个简单的组合， 也会因其数据数量的巨大而变得复杂，且需要花费一定量编排时间，在编排过程 中也往往由于疲劳而造成差错。因此，通过计算机辅助手段自动生成大学考试时 间表，是件十分有意义的工作，且用计算机自动生成时间表会更加便利学校用计 算机管理学校的教学计划，提高工作效率。 1 2 国内外研究现状 包括考试时间表在内的时间表是一个多目标、有限资源、带有模糊约束条件 的组合规划问题，也是计算机应用领域的具有代表性的难题。国外从2 0 世纪5 0 湖北工业大学硕士学位论文 年代末就对这个课题丌展了研究。1 9 6 3 年c c g o t l i b e 在他的文章t h e c o n s t r u c t i o no fc 1 a s s t e a c h e rt i m e t a b l e 【1 】中提出了时间表问题的数学模型， 它标志着时间表这一课题的研究正式跨入了庄严的科学殿堂，但由于在实践中遇 到的困难，使人们对时间表问题的题解是否存在产生了疑问。1 9 7 6 年s e v e n 在论 文o nt h ec o m p l e x i t yo ft i m et a b l em u l t ic o m m o d i t yf l o wp r o b l e m s 【2 1 中，第 一次证明了时间表问题是n p 完全的，这虽然回答了计算机制定时间表在实践中遇 到困难的原因，但同时等于宣布计算机编排时间表问题无法实现，因为计算机难 解性的理论研究指出，现代计算机尚未找到解决n p 完全问题的多项式算法。此后 这一课题的研究大多离开理论研讨的轨道而转向经验方式，这使8 0 年代的许多时 间表制定系统缺乏普适性。s e v e n 的论证正式确立了时间表问题的学术地位，把 对时间表制定的复杂性认识提高到了理论的高度。 9 0 年代初期，c o l o r n i 【3 】等人首先尝试应用遗传算法( g e n e t i ca l g o r i th f i l ，g a ) 来解决u t t p ( u n i v e r s i t yt i m e t a b l ep r o b l e m s ) 问题，引进了矩阵表示方案及相 应的交叉、变异算子。后来c o l o r n i 【3 】又将其成功地应用到了意大利米兰市的一所 规模较大的学校中。p a e c h t e r 【4 】等人对u t t p 问题进行了研究，提出了时域置换法 和放置查找法，并针对较大规模的实际u t t p 问题比较了这二种算法的性能。 b u r k e 【5 】对将进化算法分阶段的用于u t t p 问题做了初步的研究，得到一些颇有价值 的成果。为了能用计算机进行管理教学调度工作，国外许多软件商也作了很大努 力，并开发出相应的通用自动排课排考系统。b o n d y 于1 9 7 6 出了一个简单的排课 问题，将问题归结为一个图的边染色问题，并且对提出的简单排课表问题给出了 一个算法i 州。但实际教学活动中提出的大学时间表表问题远非如此简单，且由于它 必须满足各种复杂约束条件而使这种算法实际上是无能为力的。 我国对这一课题的研究起步比较晚，清华大学1 9 8 4 年在清华大学学报【| 7 】 上发表了林漳希和林尧瑞在该课题上的实验性研究成果，接着当时的南京工学院、 大连理工学院等高等院校都相继开展了这方面的研究工作。国内其他一些高等院 校也进行了很多相关软件的开发研制工作。成形的系统有大连理工大学1 9 9 8 年推 出的教学调度系统3 0 0 版本【8 】和清华大学计算机与信息管理中心开发的综合教务 管理系统【7 】但是总的来说，国内在这方面的研究开发应用方面也存在如下一些不足： 国内的时间表软件很少，涉及到自动时间表制定的算法的系统很少，大部分局限 于辅助人工时间表的制定，并没有任何“智能”成分。自动时间表制定系统往往 由于在随机求解过程中出现太多的未被安排课程而很难在实际中使用。 c h upc 和b e a s l e y 对一般的安排问题使用了遗传算法进行求解1 9 j ，他们着。 重于遗传算法的全局最优解的搜索能力，避免了问题的局部最优解。日本的s i g e r u 用具有控 2 湖北工业大学硕士学位论文 制约束的遗传算法优化了教室的合理利用，解决了在教室较少的情况下，如何对 教室的利用进行合理的分配【1 0 1 。张春梅等人对大学课程进行分类，并对不同的课 程使用具有自适应能力的遗传算法进行了安排【1 1 】。p m l i p p i n e s 的h o s u n g c k e 使用 遗传算法对p h i l i p p i n e s 大学的数学学院时间表问题进行了求解f 1 2 j 。杨宇对分别使 用遗传算法对局部时间表问题和全局时间表问题进行了求解【1 3 】。 1 3 论文特色及论文安排 大学考试时间表问题是一个有约束的、多目标的、难解的组合优化问题，己 经证明了属于n p 完全问题【1 】f 1 4 】【1 5 l ，随着求解规模的扩大，传统的优化算法将很 难得出其优化解。本文中应用了混合智能算法遗传模拟退火算法来求解大学 考试时间表问题。 本文的主要工作如下： 第2 章详细介绍了时间表问题，特别是大学时间表问题( u t t p ) ，并给出了 时间表的一般数学模型。然后针对u t t p 详细介绍和分析了现有求解方法的优缺点。 第3 章对遗传算法和模拟退火算法进行了深入系统的研究，在分析两种算法 优缺点的基础上介绍由这两种算法综合形成的混合算法遗传模拟退火算法。 并指出该算法在求解优化问题时有明显的优越性。 第4 章分析讨论了考试时间表问题的各种约束条件后，对考试时间表问题建 立了数学模型：提出了大学考试时间表问题拆分化简方案，使问题的数学模型适合 分步求解。 第5 章利用三种智能优化算法：模拟退火、遗传算法、遗传模拟退火混合算法， 对考试科目考试时间确定问题进行了求解试验，并分析比较不同算法不同参数取 得的试验结果。 本文最后对混合智能算法研究在高校管理问题研究进行了总结与展望。 研究的主要内容和特色有： ( 1 ) 详细介绍了遗传算法、模拟退火算法并对其优化进行了深入系统地研究， 在分析两种算法及其理论的基础上，指出其各自的优缺点，表明在求解优化问题 中，混合智能算法具有明显的优越性。 ( 2 ) 分析讨论了考试时间表问题的各种约束条件后，对考试时间表问题建立 了数学模型；提出了大学考试时间表问题拆分化简方案，使问题的数学模型适合 分步求解，设计遗传模拟退火混合算法，利用三种智能优化算法：模拟退火、遗传 算法、遗传模拟退火混合算法，对考试科目考试时间确定问题进行了求解试验， 并分析比较不同算法不同参数取得的试验结果。 3 湖北工业大学硕士学位论文 2 1 时间表问题 2 1 1 时间表问题概述 第2 章时间表问题 时间表问题( t t p ：t i m et a b l ep r o b l e m ) ，是一类特殊的资源调度问题，是指 在给定的时间内合理安排某些事件的进行，使之发生冲突的可能性最小，。也就是 要求安排出一个合理( 最优) 的时间序列，根据此序列所有的事件都可以顺利进行， 而有些时间序列却不能达到指定的目标【1 6 】。根据约束条件、优化目标和问题领域 的不同，时间表问题在实际应用中又有多种类型，如火车、汽车、飞机时间表：雇 员班次安排表；各种活动如运动会的时间表；电影院的场次安排表；会议时间表 以及各类型学校的课程时间表和考试时间表等，也可以应用于与时间相关的装配 序列规划a p s ( a s s e m b l ys e q u e n c ep l a n n e r ) 中。随着现代社会相对可利用资源的 日益紧张，作好各类资源的统筹安排、优化利用是一件非常有意义的事情。本文 将把时间表问题在教育领域的实际应用为研究内容。 2 1 2 时间表问题的一般数字模型 在时间表问题中，设给定n 个项目( i t e m s ) 和m 个资源( r e s o u r c e ) ，用c 表 示将第i 个项目分配给第j 个资源的代价( c o s t ) ，所求问题为决定一个从项目到 资源的最优分配，使得总的代价最小且满足k 个附加条件【1 7 】【1 8 1 。即： m ；n - 厂g ) 2 砉薹c 玎z 巧( 薹h 昌l 1 d s ，z ) 且 荟荟勤s 钆 这里 f 1 矿i i ( 1s 尼5 蠡p 如果项目f 分配给资源j 否则 4 湖北工业大学硕士学位论文 而是第k 个附加代价 2 1 3u t t p ( u niv e r sit ytim e t a biep r o bie m ) 狭义的时间表问题通常是指大学时间表问题，因为大学时间表问题在时间表 领域最具代表性，在实际应用中较为常见，对它的研究也比较广泛和深入，尤其 是大学时间表问题u t t p 因其约束条件最多、求解难度最大而为广大学者一直以来 所积极研究，它也是本文的主要研究对象。 包括大学时间表问题在内的所有时间表问题已被证明为是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 ep r o b l e m ) ，不存在确定型多项式复 杂性解法【1 9 1 【2 1 。通常，这样的时间序列是由问题领域方面的专家得出并做出选择， 专家们所依赖的是般的常识知识和以往的经验知识，他们决策思路( 方法) 一般 没有明显形式化的过程所遵循。考察和选择时间序列的困难之处在于如下3 个方 面： ( 1 ) 即使事件的数量比较小，但是由于涉及到的方面比较多，它们的时间序列 ( 组合数) 也是很惊人的，并且随着资源、事件数目的增加，这种序列的个数将急 剧上升。比如，解空间中的课表数目与时间、班级、教室等资源的数目直接相关， 任何一项资源数目的增加都会导致课表数目成倍地增长： ( 2 ) 此问题的相关领域的一些具体要求更增加了解决问题的难度。这类问题的 约束一般来说是多元约束问题，并且每个约束之间并不是孤立的，他们之间的联 系使得问题的解决更加困难； ( 3 ) 另外一个方面，有时问题并不是一成不变的，经常处于一种动态的过程之 中，像教学政策的改变将直接影响到考试科目的编排。 因此，在决定所用的序列之前，专家一般也不能考虑所有可行的时间序列， 所以通常专家们制定出的时间序列不一定是最优的，并且即使是一位专家认为没 有合适序列的情况，也有可能确实存在一个时间序列，只是专家没有发现而已。 一直以来，许多学者都投入到了对时间表问题的研究之中，特别是近二十年来， 随着计算机技术、智能算法和人工智能等技术的研究进展，使得人们对自动化时 间表问题产生了浓厚的兴趣，对时间表问题的研究自上个世纪9 0 年代以来成为了 一个新的热点，人们也研究设计了多种解决t t p 尤其是u t t p 的方案。我国在课程 和考程编排领域和其他时间表领域的应用方面大多还处在人工凭经验安排的阶 段，因此对自动化时间表问题的研究是一项意义重大的任务。 5 湖北工业大学硕士学位论文 2 2u t t p 问题的求解 总体上来说，研究u t t p 的主要策略大致可以分为基于传统数学规划和运筹学 的方法、人机互动方法、基于人工智能的方法和基于启发式算法的方法； 2 2 1 基于传统数学和运筹学的方法 这类方法的主要思想是改进传统的数学规划和运筹学方法，或将这些方法以 适当的方式相结合来建立相应的模型并求解。作为运筹学领域的一个问题，其解 决方法的发展自然从采用运筹学中的各种数学规划方法开始，其中主要包括整数 规划( i n t e g e rp r o g r a m m i n g ，i p ) 、线性规划( l i n e a rp r o g r 锄i n g ，l p ) 和图着色 ( g r a p hc 0 1 0 r i n g ，g c ) 方法。 整数规划解决时间表问题的一般模型为【驯 f i i l dy 腺 ( f = 1 ，刀；拓1 ，妒)( 2 1 ) s u b j e c t t 0 ：苫y d t = = 尼z c z = = 1 ，留， c 2 2 ， 善y 谵鲋七 怍1 ，v ) 茎舻1 y 腑如，1 ( 2 3 ) p = 1 ，- 乒= 1 ，妒) ( 2 4 ) a = 1 ，灯乒= 1 ，护)( 2 5 ) ( 2 1 ) 式中，y 膻表示将课程i 安排到时间段k ，反之则为0 ，朋七为第k 时 段所能进行的最多考试科目数( 如教室的间数) 。约束( 2 2 ) 表示学科包含的课程门 数，约束( 2 3 ) 表示同一时段考试的课程数数目少于教室的数目，约束( 2 4 ) 则避 免了同一门课程被安排在同一时段的情况。上个世纪7 0 年代，z o i n t s 证明了用线 性解决t t p 问题的效率比整数规划要高，不过整数规划仍然是一种行之有效的方 法。此外，应用整数规划来解决时间表问题的学者还有s d a s k a l a k i a ，t b i r b a s 6 湖北工业大学硕士学位论文 等人f 2 1 】。 图着色理论的基本思想是定义一个图g = ( v ，e ) ，其中v v i ，v 2 ，v n ) 表示 图的顶点，e 则表示连接这些顶点的边的集合，找到一个着色输c ：y 呻，使得 由连线连接的顶点没有一对具有相同的颜色，从而得出着色顶点的总加权。而时 间表问题很容易用图着色模型来描述，以事件( 如课程) 等代表顶点，每一种颜色 则代表一个时间片，让互斥的课程( 如同一个班级考试的课程) 如k ，构成图中相 邻的顶点，则边形，巧) ) 则表示事件k ，不能安排在同一个时间片内，如图2 1 所示。 图2 1 用图着色法来构建时间表模型 将考试时间表问题转化成图着色模型之后，便可以用数学规划的方法来求解 g c p ( g r a p hc o l o r i n gp r o b l e m ) 了。b e r n da k n a u e r 利用线性规划的方法来求解 g c p ，并且在求解g c p 的过程中加入启发式的方法，从最可能发生冲突的课程开始 搜索。k n a u e r 在求解g c p 的过程中加入启发式方法的目的是借助过去经验的帮助， 以提高搜索的效率，而r a b i n d at r i p a t h y 则是利用“分群( g r o u p i n g ) 的概念， 将考同一门课程的学生归为一群，借此减少排课过程中的变量以简化g c p ，再利用 数规划的方式来求解g c p 【矧，国内的研究者有张健【2 3 l 利用图论染色和最优匹配原 理来简化算法来解决排课问题。 此外，应用于时间表表问题的运筹学方法还包括匈牙利方法、分组优化和定 额匹配算法、与或树搜索算法、分支定界算法和分层次的贪心算法等等。应用数 学规划和运筹学方法可以较好地解决小规模的时间表表问题，但随着问题规模的 扩大和约束的增多，这类方法往往无法求解，因此它们在现实问题的中的应用相 当有限。 7 湖北工业大学硕士学位论文 2 2 2 基于人机交互的方法 m u l v e y 于1 9 8 2 年最早提出了人机交互( h u m a n m a c h i n ei n t e r a c t io n ) 的方法来解决大学课表问题【2 4 】，引入计算机来帮助大学课表问题的解决。计算机 的好处是拥有强大的计算能力，并且其内存可以提供簿记( b o o k k e e p i n g ) 功能。 在当时的环境下，很少有单位拥有大型主机( m a i n f r a m ec 0 m p u t e r ) 而只有微机 ( m i c r o c o m p u t e r ) ，而微机计算能力有限，加上对课表相关要求的变化比较快， 所以事实上无法用计算机自动产生可行的课表。折中的方式就是利用计算机的运 算能力和簿记功能，再结合专家的经验，从而产生了人机交互的方法。这种 方法是首先由计算机产生一个初始解，然后由专家进行相应的修改或指导机器产 生新的解，直到得到满意解为止。它分为逼近( a p p r o x i m a t i o n ) 、评价( e v a l u a t i o n ) 和修正( m o d i f i c a t i o n ) 三个阶段。具体的步骤是： ( 1 ) 根据用户输入的资源( 如可提供的教室) 、约束( 如教学政策) 等产生构建模 型所需的数据： ( 2 ) ( a p p r o x i m a t i o n ) 计算机根据数据产生一个网络模型并求解； ( 3 ) ( e v a l u a t i o n ) 评价侯选解是否可行，如不可行，转至步骤( 1 ) ： ( 4 ) ( e v a l u a t i o n ) 评价侯选解是否满意，满意则转至( 8 ) ，不满意则转至步骤 ( 6 ) ； ( 5 ) 确定修改解或修改模型，如修改解则转至( 6 ) ，修改模型则转至( 7 ) ； ( 6 ) ( m o d i f i c a t i o n ) 专家手工修改解，转至( 3 ) ； ( 7 ) ( m o d i f i c a t i o n ) 修改模型，转至( 2 ) ； ( 8 ) 输出满意解。 这种方法的好处是具备交互性，用户可以在求解的过程中不断提出新的约束 要求，在一定程度上结合了计算机和专家的优点。但它毕竟只是一个半自动化的 方法，专家的经验对于问题的最终解决起着至关重要的作用，而且对于规模较大 的问题，这种方法所耗费的时间和工作量过于庞大而且不具备通用性。 2 2 3 基于人工智能的方法 计算机技术的出现和发展促使了人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 的 迅猛发展，自1 9 5 6 年a i 被正式提出以来，它己经在人类社会的各领域得到了广 泛的应用，在各类优化问题上的应用尤为普遍，包括生产线管理( s e q u e n c i n g ) 、 车辆路径问题( v e h i c l er o u t i n g ) 等等。目前用于解决大学课表问题的a i 方法主 要有两种：约束满足规划( c o n s t r a i n ts a t i s f a c t i o np r o g r 锄i n g ，c s p ) 阎和专 8 湖北工业大学硕士学位论文 家系统( e x p e r ts y s t e m ，e s ) 。 c s p 问题是由一组变量和约束所组成，每一个变量都有其可行域，而约束则描 述各变量之间的关系，会对变量的取值产生影响。在满足所有约束的情况下，为 每一个变量找到一个在其可行域中的值，这一组变量的值所构成的集合便构成c s p 问题的一组解。由于c s p 问题中的约束包含硬约束和软约束，且通常也是n p 完全 的，这与时间表问题的性质吻合，因此将时间表问题当作c s p 问题来看待，用c s p 来解决是可行的。 用来解决c s p 的搜索算法有三种，包括回溯法( b a c k t r a c k i n g ) 、向前搜索法 ( f o r w a r dc h e c k i n g ) 和节线一致性法( m a i n t a i n i n ga r cc o n s i s t e n c y ，m a c ) 。 这三种算法的搜索过程都可以用树状的结构来表示，如图2 2 a 对于某个节点，选 定一个分支，即指定一个可能的值，然后删除下一层的节点中与当前所得的解不 ，一致的解，即无法满足两个节点( 变量) 之间的约束的值，直到搜索至整个树的最 下一层为止。如无法往下搜索则重新选择上层的分支。 图2 2c p s 的搜索过程 c s p 可以用用计算机程序语言来实现，而针对c s p 的特点，目前已有一些改 进的程序可以很好的处理c s p 问题，比如：c h i p ( c o n s t r a i n th a n d l i n gi np r o l o g ) ， 它是对p r o l o g 的改进，使p r o l o g 可以处理c s p 中的变量和约束；还有基于 c + + 的i l o gs c h e d u l e r 和s o l v e r 等。 专家系统则将传统的数据库和专家系统结合起来，充分发挥各自的长，达到 优势互补的目的。系统将拥有的几方面的知识如教室、班级、课程、时间等详细 资料存入数据库中，将一些限制条件放入规则库中，专家系统使用排考专家的大 量排考知识策略( 这里的策略指把求解过程看成对一种与或图的搜索) ，通过查询 数据库和进行规则推理，灵活的编排出符合要求的时间表。 由于专家系统的推理机制是处理关系方面的问题，而数学规划处理的是数量 方面的问题，从这个意义上说，专家系统更利于解决类似于t t p 之类的资源分配 9 连 量 司题。专家系统的优势在于。 ( 1 ) 用户可以很容易地描述问题的约束和专家的经验： ( 2 ) 根据推理过程所引用的规则，可以解释最终解的产生过程： ( 3 ) 易于达成多目标。 2 2 4 基于启发式算法的方法 启发式算法主要是指最优化领域三大非经典算法：遗传算法，模拟退火算法和 禁忌搜索算法。这些算法自从被提出以来，由于良好的特性使得其被应用于越来 越多的最优化领域之中，t t p 问题自然也不例外。 一遗传算法 遗传算法( g e n e t i ca 1 9 0 r i t h m s ，g a ) 是美国密歇根大学的h 0 1 1 a n d 教授于1 9 7 5 年受生物进化论思想的启发而提出来的。g a 是模拟自然界中“适者生存”机制的一 种高度并行、随机和白适应的优化算法。它将问题的求解表示成“染色体 的进 化过程，通过一代代的进化，包括复制、交叉和变异等过程，最终收敛到“最适 应环境”的个体，从而求得问题的最优解或满意解。 遗传算法是一类随机优化算法，但它不是简单地随机比较搜索，而是通过对 染色体的评价和染色体中基因的作用，有效地利用己有的信息来知道搜索可能改 善优化质量的状态。 正是由于遗传算法良好的特性，虽然它目前还没有完整的数学理论基础，不 过这丝毫不影响遗传算法在现代工程技术上的应用，其中也包括u t t p 和其他类型 的时间表问题，本文所要应用的也正是改进的遗传算法。与一般的运筹学方法不 同，用遗传算法来求解大学课表问题是与问题密切相关的，它没有固定的公式， 对于问题编码的设计即解的模板的设计显得尤为重要。因此，尽管应用遗传 算法来求解大学课表问题的学者很多，但他们的编码方式和求解过程却存在着显 著的差别。 二模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 来源于固体退火原理，将固体加 温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能 增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达 到基态，内能减为最小。根据m e t r o p 0 1 i s 准则( 随机接受准则) ，粒子在温度t 时 趋于平衡的概率为e 一e7 盯，其中e 为温度t 时的内能，篮为其改变量，k 为 b 0 1 t z m a n n 常数。用固体退火模拟组合优化问题，将内能e 模拟为目标函数值f ， 温度t 演化成控制参数t ，即得到解组合优化问题的模拟退火算法：由初始解i 和 l o 湖北工业大学硕士学位论文 控制参数初值t 开始，对当前解重复“产生新解计算目标函数差接受或 舍弃”的迭代，并逐步衰减t 值，算法终止时的当前解即为所得近似最优解，这 是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。 a b r a m s o n 最早使用模拟退火技术来求解大学课表问题【2 7 1 ，模拟退火算法的优 势在于其良好的灵活性和在全局上的强大搜索能力，一般来说，模拟退火算法比 遗传算法的搜索能力要好，但遗传算法更容易被用户所接受，而且，前者所花费 的计算时间通常更长。国内有黄干平，姚自珍等应用模拟退火算法来解决课表问 题，李增智等还采用了混合的模拟退火技术【2 9 】 三禁忌搜索算法 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，t s ) 算法是一种全局性邻域搜索 算法，模拟人类具有记忆功能的寻优特征。禁忌搜索算法通过局部邻域搜索机制 和相应的禁忌准则来避免迂回搜索，并通过破禁水平来释放一些被禁忌的优良状 态。进而保证多样化的有效探索，以最终实现全局优化。 禁忌搜索思想最早由g 0 1 v e r 提出，它属于确定性的迭代优化算法。主要针对 一般下降算法的缺点而出现的。一般的下降算法在搜索到一个局部最优解时，就 会自动停止：而禁忌搜索采用禁忌策略尽量避免己搜索过的对象，从而保证了对不 同的搜索路径的探索。因此禁忌搜索算法克服了传统的搜索算法易于陷入局部最 优的缺陷，是求解组合优化问题的少有的有效算法之一。 禁忌搜索算法流程禁忌搜索算法的主要步骤如下： ( 1 ) 产生初始解x 缸； ( 2 ) 设当前解邑。x 妇； ( 3 ) 重复第( 4 ) 步到第( 9 ) 步，直到满足停止条件； ( 4 ) 在x n t 的邻域内产生，个测试解x f ，1 s fs ，； ( 5 ) 求出目标函数厂傅；) ； ( 6 ) 判断测试解是否在禁忌表中，若不在禁忌表或在禁忌表中但其目标函数值 比x 妇还好，则把它作为新的当前解石。嗍，并转到第( 7 ) 步；否则，继 续测试下一个测试解。若所有测试解都在禁忌表中，则转到第( 4 ) 步； n x 妇= xc u 。哪； ( 8 ) 若禁忌表已满，则按先进先出的原则更新禁忌表； ( 9 ) 把当前解x 一，插入禁忌表； 湖北工业大学硕士学位论文 ( 1 0 ) 记下最优解x 胁结束算法。 h e n z 【3 0 】将禁忌搜索算法应用于课表问题的方法是将其改造成图着色的问题， 初始解是满足一系列约束的课表，而领域内的测试解则是改变初始解中某一门课 程分配的时间片。b u r k e 【3 1 】等人通过对课程表和护士排班表两个典型的时间表问 题的分析证明了禁忌搜索算法在时间表问题上的有效性，国内的李红、成新文【3 2 】 还对禁忌搜索算法和遗传算法在求解大学课表问题上进行了比较，说明了禁忌搜 索算法比遗传算法更容易跳出局部最优，但由于其迭代方式是单一移动，缺乏遗 传算法的并行性，因此其计算时间普遍比遗传算法长。而且对于大规模的问题， 遗传算法和模拟退火算法的表现要更加优秀。我们将在下一章对遗传算法和模拟 退火算法进行更加详细的介绍。 湖北工业大学硕士学位论文 第3 章混合算法的理论基础 遗传算法是一种进化搜索算法，它的基本思想是基于d a r w i n 的进化论和 m e n d e l 的遗传学说。其中交叉算子和变异算子是遗传算法的两个重要组成部分， 它们被重复地应用到对问题的解进行编码而构成的染色体上。在许多优化问题和 工业实际应用上，g a 已经得到了成功的应用。模拟退火算法源于对固体退火过程 的模拟，它能够以随机搜索从概率的意义上找出目标函数的全局最优点。模拟退 火算法特别适合于解决大型组合优化问题，算法的核心在于模拟热力学中液体的 冻结与结晶或金属溶液的冷却与退火过程。混合算法研究的目的是保持原来算法 的优点，克服降低其自身弱点，提高算法的效率。 遗传算法和模拟退火算法有互补性，遗传算法把握总体的能力比较强，但局 部搜索能力比较差；模拟退火算法具有比较强的局部搜索能力，但全局搜索能力 不如遗传算法。因此将遗传算法与模拟退火算法结合起来，可以克服遗传算法和 模拟退火算法各自的缺点，发挥它们的优势。 3 1 遗传算法 3 1 1 遗传算法的概念 遗传算法( g e n e t i ca 1 9 0 r i th l i l ，g a ) 是一类借鉴生物界自然选择和自然遗传机 制的随机化搜索算法。该算法是一种群体型操作，这种操作以全体中的所有个体 为对象，其操作包括：选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 、变异( m u t a ti o n ) 三个 主要遗传算子，他们使得遗传算法具有了其他传统方法所没有的特性。遗传算法 的核心内容是它的五个基本要素，它们是：参数编码、初始群体的设定、适应度函 数的设计、遗传操作的设计、控制参数的设定【3 3 】【川。下面，对一些概念进行描述 和解释： ( 1 ) 编码 生物的性状是由生物的遗传基因的编码所决定。遗传算法的操作对象是字符 串，变量与个体间的映射要通过编码来实现。编码方法要求：一是字符串要反映所 研究问题的性质：二是应遵循字符串长度最短、模式阶次最高、模式数目最大等原 则。设有两种编码方法，一种是二进制编码，另一种是k 进制编码。从理论上可 以证明。当k 2 时用二进制编码来描述个体比用k 进制编码能反映更多数目的基 1 3 湖北工业大学硕士学位论文 因模式，因此遗传算法中常用二进制编码。在遗传算法中一个基因的编码就代表 了问题的一个解，一个基因编码也称为一个个体或称为一个染色体。 ( 2 ) 适应度函数 生物个体对环境适应程度的各不相同，从而表现出不同的生命力。在遗传算 法中，适应度是描述个体性能的主要指标，是评价个体优劣的重要标准。根据适 应度的大小对个体进行择优选取，符合生物学中“优胜劣汰，适者生存”的原则， 这在遗传过程中具有着重要意义。将优化问题的目标函数与个体的适应度建立映 射关系，即可在群体进化过程中实现对优化问题目标函数的寻优。将目标函数转 换成适应度函数一般应遵循两个原则：一是适应度必须非负，二是优化过程中目标 函数的变化方向应与群体进化过程中适应度函数变化方向一致。 ( 3 ) 群体 一个群体是若干个体的集合。在遗传算法中，单个个体表示了问题的一个解， 因此由这些问题解组成的群体就构成了该问题的解集合。群体的初始化是指产生 第一代一定数量的个体一般可先将优化问题的初始解转化为个体，第一代群体中 的其余个体随机产生。 ( 4 ) 选择 选择的目的就是为了从当前群体中选出优良的个体，使他们有机会作为父代 产生后代个体。每代群体中的单个个体，其适应度函数的大小决定它能否进入到 下一代的概率。通过选择算子的调用，使得群体中的优秀个体数目不断增加，整 个进化过程朝着更优解的方向进行，反映了“优胜劣汰 的原则【3 5 】【蚓【3 7 1 。 ( 5 ) 交叉 选择算子虽然可以使可行解群体朝着最优解方向移动，但只能在现有群体内 寻优，它不能产生与亲代不同的个体。许多生物体的繁衍是通过染色体的交叉来 完成的。在遗传算法中引入了这一概念，形成了交叉算子。每一代的各个个体之 间按一定的概率交换其部分基因，产生新的基因组合，使各个解有机会交流其优 秀基因，可望获得比亲代更好的解的结构。执行交换的个体是随机选择的，通常 按给定的一定的概率发生，这一概率称为交叉概率。通常按给定的交叉概率足， 用轮盘算法按适应度大小选择被交换的个体。交叉点的选择也是随机的。 ( 6 ) 变异 选择算子和交叉算子只能在现有的基因型的排列组合内寻找最优，而不能产 生新的基因型。在生物体的繁衍过程中基因的变异也是一个重要的步骤。通过在 染色体上的某些基因位置产生突变，产生一个与其他个体不同的子代个体。遗传 算法也同样引入了这一概念。在遗传算法中，变异算子对群体中的某个个体，即 1 4 湖北工业大学硕士学位论文 染色体，随机选取一位作为基因变异位，将基因翻转。产生一个新的染色体，扩 大了寻优范围。变异染色体的选择以及基因变异位的确定，都是采用随机的方法 产生。变异算子也是按一定的概率发生的，这一概率称为变异概率。 3 1 2 遗