（计算机系统结构专业论文）蚁群优化在时间表问题中的研究与应用.pdf

， 藿：毫 1 - r ， ：| at h e s i si nc o m p u t e ra r c h i t e c t u r e r e s e a r c ha n d a p p l i c a t i o n0 t i m e t a b l i b yd e n gm i n s u p e r v i s o r ：a s s o c i a t e p r o f e s s o rz h a n gy i n h u i n o r t h e a s t e r nu n i v e r s i t y j u l y2 0 0 8 片毋h“潆，mij “，；嫦$ 独创性：声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 ：也 恧o 学位论文作者签名：叉产奄久 e t 期：0 8 7 6 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年囵一年口一年半口两年口 学位论文作者签名：p 锹 签字日期：0 3 7 导师签名：狱压劣牟 签字日期：o 8 7 易 本文首次将蚁群优化推广到解决时间表问题中，以蚁群优化和概率统计理论为基 础，提出了基于蚁群优化的时间表算法，并对蚁群优化及算法中所涉及的个体启发信息 策略、自适应选择策略、最大最小信息素策略和信息素平滑处理机制等关键问题作了系 统、深入和较为全面的研究： 首先，从理论上介绍了a c o 的生物原理及算法模型，并提出了a c o 算法的若干改 进策略，如：信息素更新机制，分组策略等；然后，以课程表问题为例，对时间表问题 进行数学描述，提出了时间表问题的二分图模型；接着，从理论上论述了如何用a c o 算法来解决时间表问题，提出了基于蚁群优化的时间表算法；最后，将基于蚁群优化的 时间表算法应用到课程表问题中，并对算法进行了分析，得到了较高质量的课程表。 研究与应用结果表明，本文提出的基于蚁群优化的时间表算法是可行的，它拓宽了 时间表算法的解决方案；以概率统计理论和蚁群优化理论为基础，对其中所涉及的信息 素策略和选择机制等问题的研究也是有效的，推广了a c o 的应用。 关键词：组合优化；蚁群优化：时间表问题；课程表问题；二分图 一i i 一 f oo-ii-r 1 东北大学硕士学位论文 r e s e a r c ha n d a p p l i c a t i o no fa n tc o l o n yo p t i m i z a t i o ni n t i m e t a b l i n gp r o b l e m a b s t r a c t t i m e t a b l i n gp r o b l e mi sat y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o na n da nu n c e r t a i ns c h e d u l i n g p r o b l e m w i t ht h ed e v e l o p m e n to fa r t i f i c i a li n t e l l i g e n c et e c h n o l o g i e s , p e o p l eh a v eh a da s t r o n gn e e di na u t o m a t i o ns o l u t i o nf o rt i m c t a b l i n gp r o b l e m a n tc o l o n yo p t i m i z a t i o nd e r i v e df r o mt h ef i e l do fs v d a r l ni n t e l l i g e n c e i th a sag o o d g l o b a ls e a r c hc a p a b i l i t y , aw i d er a n g eo fa p p l i c a t i o n si no p t i m i z a t i o np r o b l e m 。 t h i st h e s i sf i r s te x t e n d sa c o ( a n tc o l o n yo p t i m i z a t i o n ) t os o l v et h et i m e t a b l i n gp r o b l e m b a s e do na c oa n dt h et h e o r i e so fp r o b a b i l i t y , s t a t i s t i c s ，t i m e t a b l i n ga l g o r i t h mb a s e do na c o i sg i v e n a n tc o l o n yo p t i m i z a t i o na n dc o r r e l a t i v ek e yp r o b l e m s ，s u c ha si n d i v i d u a le n l i g h t e n i n f o r m a t i o ns t r a t e g y , a d a p t i v es e l e c t i o ns t r a t e g y , t h em a xa n dt h em i n i m u mi n f o r m a t i o n s t r a t e g ya n di n f o r m a t i o n - s m o o t h i n gm e c h a n i s mf o rh a n d l i n g , a r es t u d i e d a n da n a l y z e d s y s t e m a t i c a l l yi nt h i st h e s i s f i r s t ，a f t e rd e s c r i b i n gt h eb i o l o g i c a lt h e o r ya n da l g o r i t h mm o d e l so fa c ot h e o r e t i c a l l y , w ec o n c l u d es o m ei m p r o v e m e n ts t r a t e g i e s ，s u c ha s ，i n f o r m a t i o n - u p d a t em e c h a n i s m ，g r o u p s t r a t e g ya n ds oo n s e c o n d ，t a k et h ec u r r i c u l u mp r o b l e ma sa ne x a m p l e ，t h em a t h e m a t i c a ld e s c r i p t i o no f t h e t i m e t a b l i n gp r o b l e mi sp r o p o s e d ，a n dt h eb i p a r t i t eg r a p hm o d e li sg i v e n t h i r d ，t h em e t h o do fh o wt os o l v et h et i m e t a b l i n gp r o b l e mu s i n ga c o i sd i s c u s s e d t h e o r e t i c a l l y t h e nt h et i m e t a b l i n ga l g o r i t h mb a s e do na c o i sp r e s e n t e d a tl a s t ，t h et i m e t a b l i n ga l g o r i t h mb a s e do na c oi sa p p l i e dt ot h ec u r r i c u l u mp r o b l e m w ea n a l y z et h ea l g o r i t h ma n dt h e ng e tag o o dc u r r i c u l u mr e s u l t t h er e s u l t so fr e s e a r c ha n da p p l i c a t i o ns h o wu st h a tt h et i m e t a b l i n ga l g o r i t h mb a s e do n a c oi sf e a s i b l e i tb r o a d e n st h em e t h o d so fs o l v i n gt h et i m e t a b l i n gp r o b l e m a n di ti s e f f i c i e n tt or e s e a r c hs o m ek e yp r o b l e m si ni n f o r m a t i o ns t r a t e g ya n dc h o i c em e c h a n i s mu s i n g t h et h e o r i e so fp r o b a b i l i t y , s t a t i s t i c sa n da c o i tp o p u l a r i z e st h ea p p l i c a t i o no f a c o k e y w o r d s ：c o m b i n a t o r i a lo p t i m i z a t i o n ；a n tc o l o n yo p t i m i z a t i o n ；t i m e t a b l i n gp r o b l e m ； c u r r i c u l u mp r o b l e m ；b i p a r t i t eg r a p h i i i j_ 尹 i j 1 1 弓i 言1 1 2 时间表问题简述。2 1 3 蚁群优化简述3 1 4 主要内容及意义5 第2 章时间表问题7 2 1 引言7 2 2 课程表问题8 2 2 1 问题概述8 2 2 2 数学描述8 2 3 求解时间表问题的常用算法1 0 2 4 刀、结1 6 第3 章蚁群优化算法。1 7 3 1 引言1 7 3 2 蚁群优化算法原理1 7 3 2 1a c o 生物原理1 7 3 2 2a c o 算法模型1 9 3 2 3a c o 算法系统特征2 2 3 3 蚁群优化算法系统模型的实现2 3 3 3 1t s p 数学描述2 3 3 3 2a c o 算法系统模型的实现2 4 3 3 3 算法分析2 6 3 4a c o 算法的改进2 7 3 5a c o 算法的应用领域3 0 3 6d 、1 2 ；3 2 第4 章基于蚁群优化的时间表算法3 3 一一 东北大学硕士学位论文 目录 4 1 引言。3 3 4 2 数学模型的建立3 3 4 2 1 二分图模型的顶点集3 4 4 2 2 二分图模型的边集3 4 4 2 3 二分图模型边的权植。3 5 4 2 4 二分图模型的创建3 5 4 3 算法设计3 7 4 3 1 蚂蚁个体的构造3 7 4 3 2 蚂蚁的一次周游。3 9 4 3 3 路径构建机制4 0 4 3 4 信息素更新机制4 2 4 4 约束的检测和处理4 2 4 4 1 硬性约束的检测和处理4 3 4 4 2 软性约束的检测和处理4 4 4 5 算法流程图二少”4 7 4 6d 、结5 0 第5 章应用案例与分析5 l 5 1 应用案例5l 5 1 1 数据介绍5l 5 1 2 算法实现5 2 5 1 3 结果效果图5 3 5 2 案例结果分析5 6 5 2 1 参数对算法的影响5 6 5 2 2 课程表质量分析6 0 5 3 与其他算法的比较6 l 5 4d 、结6 2 第6 章结论6 3 6 1 本文的结论6 3 6 2 未来的研究方向6 4 参考文献6 5 致j 射6 7 一v 一 东北大学硕士学位论文 1 1 引言 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是在给定有限集的所有具备某些条件的子集 中，按照某种目标找出一个最优子集的一类数学规划，属于运筹学分支。它是通过数学 方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，涉及到信息技术、经济 管理、工业工程、交通运输和通信网络等许多方面【l 】。 在运筹学的众多领域中，很多问题都可以归结为组合优化问题。例如，最小决策树 ( m j n i i n a ls p a n n i n gt r e e s ) 、最短路径( s h o r t e s tp a t h s ) 、最大流量( m a x i m u mf l o w s ) 、图着色 问题( g r a p hc o l o r i n gp r o b l e m ，g c p ) 、旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、 车辆路由问题( v e h i c l er o u t i n gp r o b l e m s ，v l u , ) 、工序调度问题( j o bs c h e d u l i n gp r o b l e m s ， j s p ) 、线形整数混合整数规划( l i n e a r i n t e g e r m i x e di n t e g e rp r o g r a m m i n g ) 、时间表问题 ( t i m e t a b l i n gp r o b l e m ，1 1 卫) 等等。这些易于表述但难于求解的组合优化问题始终是科学 家研究的一个热点。 时间表问题是一类典型的组合优化和不确定性调度问题，在现实世界中有着巨大的 应用价值。根据约束条件、优化目标和问题领域的不同，时间表问题在实际应用中有多 种类型，如火车、汽车、飞机时间表；会议时间表以及各类型学校的课程时间表和考试 时间表等。大学课程与考试时间表安排的自动生成问题，随着目前大学招生规模的扩大 和大学辅助教学系统的开发，已经引起了越来越多的关注。时间表问题的求解是近来科 学家研究的热点，现实生活中也对智能化时间表产生了迫切的需要。目前求解时间表问 题的常用算法有遗传算法( g e n e t i ca l g o r i t h m s ，o a ) 圆、模拟退火算法( s i m u l a t e da n n e a l i n g ， s a ) 、人工免疫算法等，或者是把这些算法组合起来形成的混合算法。由于时间表问题 具有求解规模大、约束条件复杂以及本质不断变化等特点，上述算法仍然存在编排时间 表时间过长，排出的时间表质量难以保证等许多不足之处。 属于群智能算法的蚁群优化( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 算法是由意大利学者 m d o r i g o 等人【l 】在2 0 世纪9 0 年代初首先提出的，这是一种基于种群的启发式仿生进化 算法。a c o 算法发展至今才不过短短1 7 年的时间，然而，这种新型的优化算法很快得 到了广泛的认可。a c o 算法在求解旅行商问题、二次分配问题、调度问题等组合优化 问题中取得了一系列较好的实验结果。本文在研究a c o 算法求解组合优化难题的基础 上，将时间表问题表示成构造图的形式，建立了时间表问题的二分图模型，提出了基于 蚁群优化的时间表求解算法。 国际上对时间表问题的研究，目前主要集中在对“课表”自动生成的研究，即所谓 一1 一 东北大学硕士学位论文第1 章绪论 “c l a s s t e a c h e r 时间表问题”。本文对“时间表问题”的讨论也是以“课表”为主要对象，建 立的课程表问题的二分图模型和算法模型，可以推广到其他类的时间表问题中。 1 2 时间表问题简述 时间表问题是指在给定的时间内合理地安排某些事件的进行，使之发生冲突的可能 性最小，也就是要求安排出一个合理的时间序列，根据此序列所有的事件都可以顺利进 行。当然，这种时间序列并不是唯一的，有些时间序列是可行的却不能达到指定的目标。 时间表问题在现实的生活中有着广泛的应用，如学校课程表的安排、体育赛事中赛 程的安排、交通时刻表的制定等都属于时间表问题的范畴。时间表问题是典型的组合优 化和不确定性调度问题，并且已经被证明是n p - 完全问题，不存在确定型多项式复杂性 解法。通常，这样的时间序列是由问题领域方面的专家得出并做出选择的。专家们所依 赖的是一般的常识和以往的经验知识。他们决策思路一般没有明显形式化的过程所遵 循，考察和选择时间序列的困难之处在于如下三个方面： 第一，尽管事件的数量比较小，但是由于事件涉及到的方面比较多，它们的时间序 列( 组合) 数也是很惊人的。并且随着事件数目的增加，这种序列的个数将急剧上升。 第二，时间表问题中一些具体要求更增加了解决问题的难度，这类问题的约束一般 来说是多元约束问题，并且每个约束之间并不是孤立的，他们之间的联系使得问题的解 决更加困难。 第三，有些时间表问题并不是一成不变的，经常处于一种动态的过程之中。 因此，在决定所用的序列之前，专家一般也不能考虑所有可行的时间序列，所以通 常专家们制定出的时间序列不一定是最优的，并且有些专家认为并没有合适序列，当然 也有可能确实存在一个时间序列，只是专家没有发现而已。近二十年来，由于人工智能 等技术的研究进展，使得人们对自动化解决时间表问题产生了浓厚的兴趣，也正是由于 各种逻辑特别是约束逻辑、时序逻辑和智能规划等各种技术综合应用的研究，对自动化 时间表研究产生了迫切需要。下面具体来看看时间表问题的研究历史和研究现状。 ( 1 ) 研究历史 1 9 6 2 年g o t l i e d t 3 】第一次提出了一个课表问题的数学模型，此后人们对课表编排问题 的算法、解的存在性等问题做了许多探讨，从而拉开了人们对时间表问题探讨的序幕。 c o o p e r 等人【3 】以5 种不同的方式证明了时间表问题是n p 一完全类问题。到目前为止， 求解时间表问题可以分为两类解决方法：一类是采用传统的程序设计的方法，先对问题 建立数学模型，然后基于数学模型利用计算机求解；第二类是采用专家系统的方法，对 时间表问题设计相应的专家系统代替人类专家来编排时间序列，按照传统的程序设计方 法，先对课程安排所涉及的各种问题建立数学模型，然后寻找算法来求解。随着人工智 一2 一 i 墓 东北大学硕士学位论文第1 章绪论 能专家系统的成熟，人们针对课程表问题设计了相应的专家系统，此类专家系统基本上 属于基于规则的系统，它们以产生式规则为基础，课表问题领域的知识被划分成两部分： 凡是静态的知识以其所称的事实来表示，而把推理和动作的过程以产生式规则来表示。 这类系统的特点是：简单、表示形式单一、高度模块化、易于修改和扩充。 但是由于课表编排问题的复杂性，信息的不精确性和不完全性以及知识的冗余性等 等，这种采用专家系统的方法数学建模难度大，课程安排算法复杂，排出的课程表难以 保证质量，此外软件的适用性和通用性不好，并且大部分没有学习的能力。因此人们在 算法的实现中加入了一些智能算法，如遗传算法、模拟退火算法等。 ( 2 ) 研究现状 现在研究时间表问题的组织机构比较多，主要有英国航空署( b r i t i s h a e r o s p a c e ) 资助 的e u m e t s a t ( m i s s i o np l a n n i n ga n ds c h e d u l i n gf o rt h ee u r o p e a nm e t c o s t a t ) 项卧3 1 、欧洲 航天蜀( e u r o p e a ns p a c ea g e n c y ) 资助的o p t i m u m - a i v l 4 1 ，美国国防部高级研究计划局 d a r p a ( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 和r o m e 实验室合作的d a r p a r o m ep l a n n i n gi n i t i a t i v e ( a f r i ) 计划等等【4 1 。并且现在也出现了各种各样时间表问题解决 系统，应用领域从军事后勤物资的调度运输到学校课程表的编排等等，取得了巨大的社 会经济效益。一个非常著名的应用是在海湾战争行动中成功解决了军队人员物资等的调 度运输问题，据称仅此一次应用所带来的价值就足以抵上美国政府在人工智能和基于知 识系统( a i 、v d 3 s ) 的研究中过去3 0 年所投资的总额。 在国外，对课程表问题的研究比较有代表性的有印度的v a s t a p u r 大学管理学院的 a r a b i n d at r i p a t h y l 5 1 、加拿大m o n t r e a l 大学的j e a n a u b i n 和j a c q u e sf e d a n d 【6 】等。 在国内，对课程表问题的研究开始与2 0 世纪8 0 年代初期f 7 1 。大多数系统都是模拟 手工课程表编排过程，以“班”为单位，运用启发式函数来进行编排的。但是这些课表编 排系统往往依赖于各个学校的教学体制，不宜于进行大量推广。从实际使用情况来看， 国内外的这些软件系统在实用性上仍然差强人意。一方面问题本身是n p 一完全问题，算 法比较复杂；另一方面由于学校众多，每个类型的学校均有各自的特殊性，自动课程表 编排软件很难普遍使用，因此只能根据不同类型的学校，开发其对应的自动课程表编排 系统。 目前，利用遗传算法来解决时间表问题已经被科学家普遍研究和应用了，但遗传算 法有着一些不足，如运行速率过慢等。新兴的群智能优化算法，如a c o 算法良好的全 局搜索能力和鲁棒性引起了科学家的广泛注意。 1 3 蚁群优化简述 2 0 世纪5 0 年代中期创立了仿生学，人们从生物进化中得到启发，提出解决复杂优 一3 一 ( d ) 对问题定义的连续性无特殊要求； ( e ) 算法实现简单。 群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对计算 机c p u 和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度 信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数 全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的 以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分 析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。 ( 3 ) a c o 算法应用现状 一4 一 东北大学硕士学位论文第1 章绪论 随着群智能理论和应用算法研究的不断发展，研究者已尝试着将其应用于各种工程 优化问题，并取得了意想不到的收获。多种研究表明，群智能在离散求解空间和连续求 解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。 a c o 算法为解决组合优化问题提供了新思路，并很快被应用到一些组合优化问题 中。比较典型的应用研究包括：网络路由优化、数据挖掘、二次规划问题( q u a d r a t i c a s s i g n m e n tp r o b l e m ，q a p ) 、机器人路径规划、作业流程规划、图着色( g r a p hc o l o r i n g ) 等问题。 c o s t a 和h e d l o 】提出增强的a s 算法，并将其应用于分配类型的问题。利用该算法 在求解图的着色问题时，得到了可以完全和其它启发式算法相媲美的结果。 b u l l n h e i m e r 、h a r f l 和s t r a u s s 1 】用算法a s r a n k 来求解车辆路由问题，取得了和最优 解非常相近的结果。近几年，g a m b a r d e l l a ，t a i l l a r d 和a g a z z i i 】对心问题的研究，对 一些标准基问题的最优解有所提高。 a c o 在电信路由优化中已取得了一定的应用成果。h p 公司和英国电信公司在9 0 年代中后期都开展了这方面的研究，设计了蚁群路由算法( a n tc o l o n yr o u t i n g ，a c r ) 1 1 。 每只蚂蚁就像a c o 算法中一样，根据它在网络上的经验与性能，动态更新路由表 项。因为如果一只蚂蚁经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表 项作比较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路 由信息。这样，在当前最优路由出现拥堵现象时，a c r 算法就能迅速的搜寻另一条可 替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方面的应用研究仍 在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演 化与a c o 的算法本质和特性非常相似。 经过多年的发展，a c o 已成为能够有效解决实际二次规划问题的几种重要算法之 一。蚂蚁系统( a n ts y s t e m ，a s ) 在作业流程计划( j o b - s h o ps c h e d u l i n g ) i 口 题中的应用实例 已经出现，利用m a x - m i na s 【l l 】解决p a q 也取得了比较理想的效果，并通过实验中的 计算数据证明采用该方法处理p a q 比较早的s a 算法更好，且与禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，t s ) 算法性能相当。利用a c o 实现对生产流程和材料管理的综合优化， 并通过与遗传、模拟退火和禁忌搜索算法的比较证明了a c o 的工程应用价值。 1 4 主要内容及意义 由上面的分析可以看出：易于表述但难于求解的组合优化问题一直是近年来研究中 的热点。组合优化问题涉及的范围很广泛，时间表问题是组合优化问题的一种类型，它 属于一类特殊的调度问题，是指在资源有限的条件下将事件安排到一定的时间段。根据 约束条件、优化目标和问题领域的不同，时间表问题在实际应用中又有多种类型，如火 一5 一 东北大学硕士学位论文第1 章绪论 车、汽车、飞机时间表；会议时间表以及各类型学校的课程时间表和考试时间表等。大 学课程与考试时间表安排的自动生成问题，随着目前大学招生规模的扩大和大学辅助教 学系统的开发，已经引起了越来越多的关注。 属于群智能优化算法的a c o 算法寻优简单、鲁棒性强、易于并行化，是一种效率 很高的寻优方法。它不依赖被控对象的精确数学模型，能有效地攻克十分困难的优化问 题，使处理问题更具灵活性、适应性和鲁棒性。该算法不仅能提高控制系统设计的品质， 而且能降低设计的难度。a c o 算法在各个工程领域中有着十分广阔的应用前景。 本文根据时间表问题的特点，运用a c o 算法来解决时间表问题，主要研究内容及 成果如下： ( 1 ) 第2 章，简单描述了时间表问题，以课程表问题为例子，分析了课程表问题的数 学描述，并对时间表问题的求解方法进行了介绍； ( 2 ) 第3 章，首先简单描述了a c o 算法的生物模型以及算法模型；然后给出了a c o 算法可以应用的问题类型，以及a c o 算法的通用结构，并总结了a c o 算法的系统特征； 接着以t s p 为例，主要分析了a c o 算法系统模型的实现及改进，并对a c o 算法的性能效 率进行了简单分析；最后总结了a c o 算法的一些改进策略； ( 3 ) 第4 章，根据a c o 算法的特点并结合第2 章的内容提出了时间表问题的一种新的 数学模型二分图模型；以课程表问题为例，并由第3 章得到启发建立了a c o 算法解 决时间表问题的算法模型，提出了基于蚁群优化的时间表算法； ( 4 ) 第5 章，首先将基于蚁群优化的时间表算法应用到解决课程表问题中；然后对实 验结果进行分析，分析了各种参数对算法性能的影响，实验结果证明a c o 算法解决时间 表问题是完全可行的；最后对课程表质量进行评价，并总结了该算法的优点及不足。 总之，本文对a c o 算法以及时间表问题进行了研究，建立了有效的算法模型来解 决时间表问题，提出了基于蚁群优化的时间表算法，为时间表问题的求解开创了一种新 的思路；并且本文对a c o 算法的应用和研究，也具有一定的理论价值。 一6 一 东北大学硕士学位论文第2 章时间表问题 第2 章时间表问题 2 1 引言 时间表问题是一类多元受限的不确定性调度问题，它在工程实施、交通营运、竞赛 安排、军事指挥、课表生成等诸多领域有着广泛的应用。时间表问题中涉及的元素可以 作如下形式描述：假设有n 个项目和n j 个资源，用c i 表示将第i 个项目分配给第j 个资 源的“代价 。时间表问题是这样的问题：它决定一个从项目到资源的最优分配，使得总 的“代价”最小并且能满足k 个附加条件，即： m i n f ( x ) = c u x u( = l ，1sfs ) ( 2 1 ) 6 i ( 1 ksk ) ( 2 2 ) 这里而= 似? 颗卧篙张，毗是耕m 。 一般来说，求解时间表问题有以下困难【1 2 l ： ( 1 ) 时间表问题是m 一完全问题，不存在确定的多项式时间算法； ( 2 ) 难以设计有效的启发式算法，也就是使用各种不同的启发式算法也不能保证在 解空间中搜索到最优解； 一 ( 3 ) 一般的算法也许是不适用的，因为在一个具体的问题实例中有多个特定的约束； ( 句现实生活中带有约束的时间表问题是不能精确描述的，有时甚至是不能描述的。 m i r j a n ac a n g a l o v i d l 2 1 指出，一般而言时间表问题是n p 一完全性问题，不存在确定性 多项式复杂性解法。 目前求解时间表问题的常用算法有遗传算法、模拟退火算法、人工免疫算法等，或 者是把这些算法组合起来形成的混合算法。 课表编排问题是时间表问题的最典型问题。国际上对时间表问题的研究，目前主要 集中在对“课表”自动生成的研究，即所谓“教室一时问”的时间表问题。本文对时间表问题 的讨论也主要是以“课表”为对象，所给出的数学模型和a c o 算法模型可以推广到其他 类的时间表问题中。 本章首先对最典型的时间表问题课程表问题进行数学描述，然后对时间表问题 的一些常用算法进行了一一讲解，这为第4 章中a c o 算法解决时间表问题建立的数学 模型和算法模型奠定了基础。 一7 一 ( 4 ) 对同一教师、同一上课对象应尽量选择相对固定的教室； ( 5 ) 教师提出的对上课时间和地点的特殊要求。 课程表问题实质上是一个目标组合规划问题，很显然，要对课表在多资源上实现最 优的配置实际上是不可能的，因此，本文放弃了寻求“绝对最优”的企图。无任何硬性冲 突的课表，是最基本的要求，在此基础上课表能够满足尽量多的软性冲突，就认为这个 课表是可行并且较优的。 2 2 2 数学描述 ( 1 ) 课程表问题中的元素 课程表问题是这样的问题：设一个学校有n 个教学班、m 个任课教师和s 门课程， 每门课程划分成若干个教学单元，而每个教学单元又由若干个授课单位组成，每个授课 单位可以是一个或多个连续的课时( 每课时一般为4 5 分钟) 。就一个班而言，其各门课程 的教学单元之间存在着一种前驱种后继的偏序关系，而不同教学班的课程之间不存在 这种关系。教师按教学单元分配，每个教学单元由一个教师讲授，而一个教师可在一个 一8 一 东北大学硕士学位论文第2 章时间表问题 或多个教学班讲授一个或多个教学单元。在课程表问题中，主要的任务是将课程、教师、 班级安排在一周内相应的时间和教室内且不发生冲突。由此可见，在课程表问题中存在 五个因素。设 课程集合：l = l i ，l 2 ，h ) ， 教师集合：t = t l ，t 2 ，t 雎) ， 班级集合：c = c i ，c ；2 ，c ， 时间集合：p = p l ，p 2 ，p 砷) ， 教室集合：l b r l ，r 2 ，k ) ， p i 表示课程安排的第i 个时间段，如p i 表示周一1 2 节，p l l 表示周三5 - - 6 节。 五个元素的笛卡儿积l x c x t x p x r 就构成了课程表问题的解空间，而课程表问题的 编排也就是在这个解空间中找到一个满足各种约束的解。教学规模太大，这个解空间的 规模也就可想而知非常大了。总校在课程安排之前，各院系要先从教学计划中把院系内 各个年级专业下学期开设的课程筛选出来，安排教师签写教学任务书，整理完毕后交与 总校教务处。换句话说， 的关系在总校课程安排之前就已经明确，这 些数据及其之间的关系是来源于各院系教务科的。易见， 之间的关系 绝不是满映射关系。又因为每个教学时间段、每个教室都可以安课程安排程，所以 可以看成是p x r 的满映射。 课程表问题可以表示为映射f ：l - p x r ，即为每门课程寻找合适的时间和教室。其 中l 是课程实体，它与教师实体和班级实体有关，即每门课程有其对应的任课教师和学 习班级( 周两次以上的课看成是不同的课程) ；p x r 表示时间和教室的笛卡尔积。 ( 2 ) 课程表问题的数学描述 根据上面的元素定义，课程表问题的目标函数为满足各种约束的前提下，获得代价 最小： mi n costi i ( 2 3 ) i e 口 其中，q 表示l x c x t 笛卡尔积中相关联的课程的集合，jep x r ；c o s t i j 表示给课程i 分配j 对需要付出的代价。 ( 3 ) 课程表问题中约束的描述 课程表编排实质上是将教师、学生和相应的课程在时间和空间上根据不同的约束条 件进行合理的安排。在2 2 1 节中，简单介绍了课程表问题中应满足的硬约束条件和软 约束条件。课程表问题中涉及的五大因素采用集合形式表示，在此基础上，可以清晰地 将2 2 1 节中提及的几个硬性约束描述如下： ( a ) 在一个教学单位时间内，同一个教师不可能在同一时间在两个不同的地方上课； 设t i j 表示l i 这门课的任课教师，f 【l i i 沪( p 抛，玛m ) ，坟k ) = ( p 加，r y l l ) ，且m n ， 一9 一 东北大学硕士学位论文第2 章时间表问题 则当t h _ t i j l 时，必有p 珊p 柚。 ( b ) 在一个教学单位时间内，同一班级不可能在同一时间上两门不同的课程； 设c t i 表示l i 这门课的任课教师，坟l 瑚户口m ，r y m ) ，t l l 护( p 柚，n ，且m n ， 则当c l m - - - - c l n 时，必有p m p 柚。 ( c ) 在一个教学单位时间内，同一教室在同一时间不可能同时上两门不同的课程； 设f 【l n 沪( p m ，玛m ) ，坟【啊) = ( p 柚，蹦，且m 1 1 ，则当r l m - - r l n 时，必有p 瑚p m 。 ( d ) 教室容量必须满足上课学生人数； 设c a p a c i t y 是教室主体的一个属性，r i c a p a c i t y 表示r i 教室所能容纳的学生数，c o u n t 是班级主体的一个属性，c i i 硼越表示k 这门课对应班级的学生人数。 如果f 【l l i 沪( p m ，r 岬) ，则c h 棚l m = ，r y 札c a p a c i t y 。 ( e ) 课程要安排在它所需类型的教室中。 设c l a s s r o o m t y p e 是课程主体的一个属性，l i c l t y p e 表示l i 课程所需要的教室类 型，t y p e 是教室主体的一个属性，r i t y p 。表示教室r i 的教室类型，如果f 【l i i i ) = ( p x m ，r y m ) ， 则i 佩c l 髑删瓣铆l e = i 己y i n t y p e 。 满足上面这五个约束条件的映射就可以称为课程表问题的可行解。 直观上来看，其解不是唯一的，应该有多个解。而且上述的模型只是考虑到解决硬 约束条件的问题，还没有解决软约束条件的问题。软约束条件根据不同的学校条件要求 是不同的，这将在第4 章中具体介绍。 一个高质量的课程表应该是一个多目标优化的。多目标优化是指课表在多个资源上 追求最优的配置，即教室资源、时间资源、教师资源、班级资源等都要求是最优的。实 际上这是不可能的，在实际中一般是求得一个相对较优的一个可行解就行了。因此，本 文放弃了寻求“绝对最优”方案的企图，除了基本的“教室、教师、学生在任一时间的安 排只能出现一次”的硬性约束条件外，课表只要能够满足人工排课中的“合理、实用、有 特色”的要求，就认为是可行的了。所以，在可行解集合中，得到“相对最优”的解则是 的目标之一。 2 3 求解时间表问题的常用算法 时间表问题属于组合优化问题，解决组合优化问题的一种最直接的方法就是穷举搜 索( e x h a u s t i v es e a r c h ) ，也就是枚举所有可能的解和所有可能的对最优解的选择。然而在 大多数的情况下，由于可能出现的解数量会以实例规模1 1 为底数呈指数级增长，而使得 这种自然但近乎幼稚的算法在n 较大的时候不再可行了。而这个代表实例规模的固定值 n 的大小通常都需要预先定义，比如说，对一个具体实例进行编码时要知道需要使用的 二进制数字的个数。对于某些组合优化问题来说，更深入地了解问题的结构以及进一步 一l o 东北大学硕士学位论文第2 章时间表问题 探讨与问题相关的性质，可以使得定义出来的算法能够比穷举搜索更快