（计算机软件与理论专业论文）基于混沌遗传算法的排课问题研究.pdf

哈尔滨工程大学硕士学位论文 摘要 为了保证教学质量，学校需要制定一套规范的教学计划，而课表编排是 教学计划得以顺利执行的重要一环。随着高校学生数量猛增，数据规模增大、 约束条件增多，在教学资源一定的情况下排课越来越复杂，人工排课已经难 以完成课表编排的工作要求。因此，利用计算机解决排课问题成为当务之急。 排课问题是典型的多重约束和组合优化问题，并且早在7 0 年代已经被证明是 一个n p 完全问题。 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的自适应随机 搜索算法。它具有良好的并行性、通用性、稳定性，是一种非常有效的解决 n p 完全问题的方法。 目前，使用遗传算法解决排课问题已经成为众多学者和高校的研究热点。 本文所做的工作就是针对单一智能算法存在的问题和不足，设计混沌遗传算 法这种混合智能算法，并利用混沌遗传算法对高校排课问题进行较为深入的 研究。尝试性的将混沌遗传算法应用到排课问题中，从而证明混沌遗传算法 在解决排课问题方面能够取得一定的效果。 论文首先对排课问题进行了概述，介绍国内外对这一问题的研究现状和 发展趋势，从高校排课实际情况出发，提出排课问题的数学模型。然后概括 说明了遗传算法的结构、功能、特征，并分析了混沌理论的主要特点及现状。 针对遗传算法的不足，把混沌引入到遗传算法中，利用混沌序列的内在规律 性，有效地引导交叉和变异操作；而在遗传算法中加入混沌优化策略后，大 大地拓展了算法的搜索空间，同时避免了标准遗传算法容易陷入局部极小的 缺陷。 最后论文分别采用标准遗传算法和混沌遗传算法对相同条件下的排课问 题进行仿真，通过比较其计算结果，证明了混沌遗传算法完全适用于排课问 题，而且具有更高的效率，为排课问题的发展提供了新的思路。 关键词：排课问题；遗传算法：混沌理论；三维编码 哈尔滨工程大学硕士学位论文 a b s tr a c t i no r d e rt oe ：b s u t et h eq u a l i t yo ft u i t i o n , au n i v e r s i t ym u s te s t a b l i s has e to f n o r m a lt e a c h i n gp l a n s ，w h i l ea r r a n g i n gc o u r s e si sa ni m p o r t a n ts t e po fc a r r y i n g o u tt h et e a c h i n gp l a ns u c c e s s f u l l y w i t ht h ei n c r e a s i n gq u a n t i t yo fc o l l e g es t u d e n t s ， t h es c a l eo fd a t aa r eh u g e ，a n da l lk i n d so fc o n s t r a i n t sa r ec o m p l e x ，c o u r s e s a r r a n g e m e n tb e c o m e sm o r ea n dm o r ed i f f i c u l ti nt h el i m i t e dt e a c h i n gr e s o u r c e s a r r a n g i n gc o u r s e sb yh a n di si m p o s s i b l et of i n i s ht h ew o r k t h e r e f o r e , i t su r g e n t t os o l v et h ec o u r s e sa r r a n g e m e n tw i t hc o m p u t e r t i m e t a b l i n gp r o b l e m ( t p ) i sa t y p i c a lp r o b l e ma b o u tm u l t i - r e s t r a i n t sa n dc o m b i n a t i o no p t i m i z a t i o n ，a n dh a sb e e n p r o v e dt ob ean o n d e t e n n i n i s t i cp o l y n o m i a lc o m p l e t e d ( n p c ) p r o b l e mi nt h e 1 9 7 0 s t h eg e n e t i ca l g o r i t h m ( g a ) ，b a s e do nt h eb i o l o g i c a lm e c h a n i s mo fn a t u r a l s d e e t i o n & h e r e d i t y , i sa na d a p t i v ea n ds t o c h a s t i cs e a r c ha l g o r i t h m i tc a nb e h i g h l yi m p l e m e n t e di np a r a l l e l f o rt h es t a b i l i t y a n dg e n e r a l i t yo fg e n e t i c a l g o r i t h m ，t h eg e n e t i ca l g o r i t h mi so f t e nu s e dt os o l v ec o m p l i c a t e dn p cp r o b l e m a tp r e s e n t ，t h et i m e t a b l i n gp r o b l e mh a sb e c o m eah o tr e s e a r c hs p o t i nv i e w o ft h es o l ei n t e l l i g e n ta l g o r i t h me x i s t i n gp r o b l e m sa n di n s u f f i c i e n c y , t h ea u t h o r d e s i g n st h ec h a o sg e n e t i ca l g o r i t h i n a n dt h ep a p e rh a sc o n 姗e d m o r et h o r o u g h r e s e a r c hb yu s i n gt h ec h a o sg e n e t i ca l g o r i t h mt ot h eu n i v e r s i t yt i m e t a b l i n g p r o b l e m t h ep u r p o s eo f t h i sp a p e ri st r yt ou s ec h a o sg e n e t i ca l g o r i t h mi nt h e t i m e t a b l i n gp r o b l e m ，a n dp r o v e st h ec h a o sg e n e t i ca l g o r i t h mi sa na d v a n c e d a l g o r i t h ma d a p t i n gt h ep r o b l e m f i r s to fa l l ，t h i sp a p e rs u m m a r i z e st i m e t a b l i n gp r o b l e ma n di n t r o d u c e st h e a c t u a l i t ya n dd e v e l o p m e n to ft h et i m e t a b l i n gp r o b l e mi na n do u to fc h i n a n e x t ， t h ep a p e rs u m m a r i z e st h es t r u c t u r e ，t h ef u n c t i o na n dt h ec h a r a c t e r i s t i c so ft h e g e n c t i ca l g o r i t h m s ， a n da l s oa n a l y z e st h em a i nc h a r a c t e r i s t i c sa n dp r e s e n t s i t u a t i o no ft h ec h a o st h e o r y i ti n t r o d u c e st h ec h a o st ot h eg 饥c t i ca l g o r i t h m s ， 哈尔滨工程大学硕士学位论文 l i i u s i n gt h ec h a o ss w i t c hg e n e t i ca l g o r i t h m sc o u l df u l l yu s et h ec h a o ss e q u e n c e i n t r i n s i cr e g u l a r i t y , e f f e c t i v e l yg u i d i n gt h eo v e r l a p p i n ga n dt h ev a r i a t i o no p e r a t i o n a f t e rj o i n i n gt h ec h a o ss e a r c hs t r a t e g yi nt h eg e n e t i ca l g o r i t h m s ，i th a si m p r o v e d t h ea l g o r i t h ms e a r c hs p a c eg r e a t l y , a tt h es a m et i m ea v o i d i n gt h es t a n d a r dg e n e t i c a l g o r i t h m sb e i n g e a s yt of a l li n t ot h ep a r t i a lm i n i m u m f l a w f i n a l l y , r e a lc o u r s ed a t ai su s e dt ot e s tt h eg a a n dt h ec g ai nt h ea p p l i c a t i o n o fr e a lt i m e t a b l i n gp r o b l e m t h er e s u l t sp r o v et h a tc g ai sn o to n l ya p p l i c a b l et o t h et i m e t a b l i n gp r o b l e m ，b u ta l s ow i t hh i g h e re f f i c i e n c y k e yw o r d s ：t i m e t a b l i n gp r o b l e m ；g e n e t i ca l g o r i t h m ；c h a o s ；t h r e e d i m e n s i o n c o d i n g 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：嘶擞 日期：妒7 年弓月i ；日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、 作者签字。备三茂俭 日期：加罗年弓月，31 9 导师( 签字) 川年弓月，乡日 哈尔滨工程大学硕士学位论文 1 1 研究背景和意义 第1 章绪论 科学技术革命正将人类带入一个全新的时代。以电子计算机为代表的 微电子技术以及光导纤维、生物工程、新材料、新能源、空间技术、海洋 技术等新的技术群的产生与发展，即将把历史牵引到一个新的经济时代一 知识经济时代。在知识经济时代里，科学技术对经济和社会发展的影响越 来越大，高校作为社会生产的有机组成部分，其作用也越来越大。作为传 播科学知识的高等院校，只有了解和掌握科学技术、文化知识的前沿，才 能培养出合格人才，才能在激烈的竞争中立于不败之地。 在高校中，教学是培养学生的主要途径。课程表是学校开展教学活动 的指令性文件，是学生和教师上课的依据，也是对学校资源合理分配的体 现。在传统方式下，课表编排主要靠手工完成，排课人员通常需要花费一 两个月的时间和精力才能将一学期课程合理安排好。这种方式不仅效率低 下，而且容易出错，同时也不能满足资源需求的经常变化。 利用计算机进行自动排课，不但能使教务人员从繁杂的排课任务中解 脱出来，提高教务管理工作效率，而且能改善教学管理质量，合理、高效 地利用有限的教学资源，使学校的各种教学活动、教学管理及其它相关的 工作能够有序、规范地进行。维持正常的教学秩序，对推动教务管理的信 息化也起到非常重要的作用。 然而，就其实质而言，排课问题是一个有约束的、非线性的、模糊多 目标优化的、难解的、时空组合的数学问题。即在满足各种己知的约束条 件的情况下找到一组较优的时空组合，同时在具体实践上受到教学组织形 式、客观物质条件和求解目标等多种因素的相互影响，这些使排课问题在 实际解决时呈现出受具体条件制约的特点。这也是造成排课问题很难获得 普遍性解决的主要原因。 总的说来，由于国内各高校资源的不同、规则的差异，纵然现有的排 哈尔滨工程大学硕士学位论文 课问题解决方法多种多样，却难于提高它的普遍适用性，使教务排课工作 至今仍是以手工排课为主，计算机排课为辅。所以，研究高效、灵活、自 动化程度高的排课方法不但仍有意义而且是迫切的需求。 1 2 研究现状与发展趋势 1 2 1 国外研究现状 自1 9 6 3 年以来，国外对学校课程表的自动生成技术给予了极大的关注， 发表了大量研究此类问题的学术论文，一些相关的应用也取得了成功。 国外早期研究大多数运用启发式方法，在模拟人工解决此类问题的基 础上进行研究。后来，国外研究者们开始运用综合性的技术探讨课程表类 问题，例如整数规划、网络模型等。另外，也有学者试图将这类问题抽象 成图着色问题来加以研究。 近年来，学者们试图用人工智能技术研究课程表问题，例如专家系统、 模拟退火思想、禁忌搜索以及遗传算法等，并产生了很好的效果。近几年 的国外主要研究现状如表1 1 所示。 表1 1 国外研究现状 年份研究者使用方法发表文献 2 0 0 7s a l w a n ia b d u l l a he t c h y b r i de v o l u t i o n a r y 文献1 2 0 0 6p a t r i c kd ec a u s m a e c k e re t cm e t a h e u r i s t i ca p p r o a c h文献2 2 0 0 5s h a wc h i n gc h a n g ae t cg e n e t i ca l g o r i t h m文献3 2 0 0 2a s a s r a t i a ne t cg e n e r a l i z e dc l a s s t e a c h e rm o d e l 文献4 2 0 0 2r a m o l la l v a r e zv a l d e se t c乃6 us e a r c h 文献5 2 0 0 2 s h a n g y a oy a ne t co p t i m i z a t i o nb a s e da p p r o a c h 文献6 2 0 0 1u a lt u r k ie t ct a b us e a r c h文献7 2 0 0 lm i c h a e lwe t ct l b us e a r c h文献8 2 0 0 1m i k ew h g h ts u b c o s t g u i d e ds e a r c h 文献9 2 0 0 1 k i m l i n c h e w e t c o p t i m i z a t i o nb a s e da p p r o a c h 文献1 0 2 哈尔滨工程大学硕士学位论文 表1 1 国外研究现状( 续) 年份研究者使用方法发表文献 2 0 0 0l r f o u l d sd e c i s i o ns u p p o r ts y s t e m文献1 1 2 0 0 0r r l n o na l v a r e zv a l d e se c c t a b us e a r c h文献1 2 2 0 0 0 p e r r yf i z z a n oe t co p t i m i z a t i o nb a s e da p p r o a c h 文献1 3 2 0 0 0b r u n od eb a c k e re t c c o n s t r a i n tb a s e da p p r o a c ha n d文献1 4 m e t a h e u r i s t i c s 1 9 9 9 s a f a a id e r i se t c c o n s t r a i n tb a s e da p p r o a c ha n d文献1 5 g e n e t i ca l g o r i t h m 1 9 9 8a l b e r t oc o l o m ie t cm e t a h e u r i s t i c文献1 6 1 9 9 8m i c h a e le t c g e n e t i ca l g o r i t h ma n dt a b us e a r c h文献1 7 1 2 2 国内研究现状 国内对课程表问题的研究开始于2 0 世纪8 0 年代初期。研究的早期主 要以临界资源分配算法为主，随后出现了以人工智能理论为基础的算法， 如知识推理、专家系统等。 自1 9 7 5 年美国m i c h i g a n 大学h o l l a n d 教授提出了遗传算法并将其成功 地应用到机器学习当中，遗传算法在解决组合优化问题上给予了人们新的 启示。于是，应用遗传算法解决课程表问题成为新的研究方向。在非数值 计算方法中，除了遗传算法外，还出现了其他模拟自然界的方法，如进化 算法、模拟退火算法等等。近年来的国内研究现状如表1 2 所示。 表1 2 国内研究现状 2 0 0 8韦玉、冯速免疫遗传算法文献1 8 2 0 0 7陈守家、付霞、周欣遗传禁忌算法文献1 9 2 0 0 6聂小东贪婪算法文献2 0 2 0 0 5陈炼、刘昌平 模拟多处理机调度的方法文献2 l 哈尔滨丁程大学硕士学位论文 表1 2 国内研究现状( 续) 年份研究者使用方法发表文献 2 0 0 4朱冠宇、王乘、席大春遗传算法文献2 2 2 0 0 4孙建平、曾经梁专家系统文献2 3 2 0 0 3业宁、梁作鹏、董逸生遗传算法文献2 4 2 0 0 3 李增智、王云岚、陈靖混合型模拟退火算法 文献2 5 2 0 0 2 唐勇、唐雪飞、王玲遗传算法 文献2 6 2 0 0 2 孙建平、梅晓勇、肖政宏、史忠关联规则 文献2 7 植 2 0 0 2胡顺仁、邓毅、王铮图论法文献2 8 2 0 0 2陈谊、杨怡、张国龙、王尚忠基于优先级的方法文献2 9 2 0 0 1熊伟清、魏平、赵杰煜遗传算法文献3 0 2 0 0 l胡小兵、鲁宏伟模糊专家系统文献3 l 2 0 0 l孙吴基于时间位图迭加匹配文献3 2 的方法 2 0 0 1赵辉、秦维佳基于资源分配的方法文献3 3 2 0 0 0汗灯层、康立山等 演化算法文献3 4 2 0 0 0周建新、王科俊、王文武、张建专家系统文献3 5 波 2 0 0 0 黄干平、姚自珍、张轶静模拟退火算法文献3 6 2 0 0 0龙一飞、郭文宏知识推理文献3 7 2 0 0 0金炳尧、蔚承建、何振亚进化算法文献3 8 2 0 0 0陈幼明、陈光喜基于资源分配的方法文献3 9 1 9 9 9陈淑珍、孙晓安回溯算法文献4 0 1 9 9 8 董艳云、钱晓群、张宇舒基于课元相关运算的方文献4 l 法 1 9 9 8 王祜民、赵致格定额匹配算法 文献4 2 4 哈尔滨工程大学硕士学位论文 1 1 i lmn ni暑 i i i 皇萱皇宣i i i 宣i i i i 1 2 3 当前发展趋势 由于排课问题充满挑战性，加上优化技术的不断发展，近年来关于排 课算法的研究活动可谓层出不穷。2 0 0 8 年8 月第七届p a t a t ( i n t e m a t i o n a l c o n f e r e n c eo nt h ep r a c t i c ea n dt h e o r yo fa u t o m a t e dt i m e t a b l i n g ) l 蚕际会议在 加拿大的蒙特利尔大学举行，会上向人们展示的求解技术手段主要如下所 示： 1 限制策略( c o n s 仃a m t b a s e dm e t h o d s ) 2 超启发式( h y p e r - h e u r i s t i c s ) 3 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 4 模拟退火( s i m u l a t e da n n e a l i n g ) 5 软计算( s o f tc o m p u t i n g ) 6 人工智能( a r t i f i c i a li n t e l l i g e n c e ) 7 局部搜索( l o c a ls e a r c h ) 8 图染色( g r a p hc o l o r i n g ) 9 数学规划( m a t h e m a t i c a lp r o g r a m m i n g ) 1 0 蚁群算法( a n tc o l o n ym e t h o d s ) 11 混合优化策略( h y b r i dm e t h o d s ) 1 2 专家系统( e x p e r ts y s t e m s ) 1 3 超大规模邻域搜索( v e r yl a r g en e i g h b o r h o o ds e a r c h ) 1 4 多目标决策( m u l t i c r i t e r i ad e c i s i o nm a k i n g ) 1 5 启发式搜索( h e u r i s t i cs e a r c h ) 1 6 禁忌搜索( t a b us e a r c h ) 17 模糊推理( f u z z yr e a s o n i n g ) 18 知识系统( k n o w l e d g eb a s e ds y s t e m s ) 19 元启发式( m e t a - h e u r i s t i c s ) 2 0 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 可以看出，当前求解排课问题方法的研究趋势，是使用经典搜索算法 与现代智能优化算法相结合的方式。使用这些方法求出的一般不是最优解， 但是常常能满足实际的需求。 哈尔滨工程大学硕士学位论文 另外，对于求解排课问题的研究还应该遵循以下几点： 1 排课问题标准化、统一化 每所学校都有自己的排课规则与要求，不同学校间存在很多不同的制 约排课的因素，这一现象在高等院校中尤为严重。这就使得为一所学校编 制的排课程序很难适用于其他学校。尽管如此，用高度抽象的数学语言建 立一个满足所有学校排课要求的超集，从而使排课问题标准化、统一化， 对解决排课问题是非常有益的。 2 深入研究现有理论、技术与方法 深入研究各种应用在解决排课问题上的搜索优化技术，继续探讨目前 各种解决组合优化问题的理论、技术与方法，拓宽这些理论、技术与方法 在排课问题上的应用范围。 3 比较并综合各种不同理论、技术与方法 比较各种解决排课问题的方法，可以对特定方法的性能及适用范围有 更深入的理解。比较同样也能说明在各种不同的情况下哪种方法能取得较 好的效果。将各种适应情况不同的方法综合起来，取长补短，就可能可以 在原有的基础上生成更优的解决方案。例如为了克服t a b u 搜索的局部寻优 及遗传算法的早熟现象，m i c h a e l 等人采用了两者相结合的方法探索时间表 问题的解。 4 研究排课问题的最优解 目前度量解决排课问题的算法的质量方法比较单一，只能通过和其他 算法的比较来说明，而不能通过和近似最优解的比较来证明。相反，其他 问题( 如图着色和工厂作业调度) 的理论研究都提供了大量的近似最优解。 因此，研究排课问题的近似最优解是非常有意义的。 5 研究、运用新的理论、技术与方法 由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增 大。国外的研究表明，解决大规模课程表编排问题单纯依靠现有方法是行 不通的，需要研究、运用其他的理论、技术与方法。如利用运筹学中分层 规划的思想将排课问题分解，是一个有希望得到成功的方法。 1 3 排课问题的求解方法 6 哈尔滨工程大学硕士学位论文 早期的计算机自动排课技术是基于模拟人工的做法，被称为“直接启 发式 ( d i r e c th e u r i s t i c s ) 的连续增长方法，把课程逐步添入现有课表，直到 所有课程都被排入课程表或者没有不违反约束条件的课程可排。然而这种 方法没有任何智能的成分，不考虑课程表的优化性，一旦发现违反约束条 件，只能重新计算。可见基于模拟人工排课的方法缺乏理论的指导和普遍 的适用性。 后来有研究者把排课简化为人们熟知的经典问题求解，出现了整数规 划( i n t e g e rp r o g r a m m i n g ) 的方法，另外还有基于网络流( n e t w o r kf l o w ) 和基于 图染色( g r a p hc o l o r i n g ) 等的算法。这些方法建立在排课模型极大简化的基础 之上，一般只考虑寻找可行解而忽略了其他优化条件。 再后来，随着现代智能优化技术的出现和发展，出现了遗传算法、模 拟退火算法、蚁群算法、启发式数值算法、分组优化决策算法、关联规则 算法、分支定界算法等新方法，它们在排课问题的求解上取得了较大成功。 下面对这些研究成果进行简单介绍。 1 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 遗传算法是一种智能性的算法，具有本质并行、自组织、自适应和自 学习等特性。用遗传算法来解决排课时间表问题有较多的应用【1 9 】。在现有 的遗传算法求解排课问题中，能够对其所使用的学校的排课问题进行求解， 在一定程度上取得了很好的成果。 2 模拟退火算法( s i m u l a t e da n n e a l i n g ，简称s a ) 模拟退火算法是一种启发式的随机搜索算法，往往能在较短的时间和 较大的解空间内找到最优解，对解课表这样的组合优化问题是很有效的。 文献【3 6 】介绍了用模拟退火算法实现交互性的课表问题求解方法。其目标函 数中各因数的权值可以由用户设定和修改，从而使退火结果获得的解尽可 能满足不同用户对课表质量的要求p 州。 3 蚁群算法 蚁群算法是通过模拟蚁群在觅食过程中寻找最短路径的方法来求解优 化问题。蚁群算法目前有a s ，a c s ，m m a s 等三种常用的模型，但是在排 课问题上这三种蚁群算法都有易于陷入局部最优解的缺陷，从而使得排课 问题的求解过程过早地停止。 7 哈尔滨 二程大学硕_ 七学位论文 文献【4 3 】提出了基于二部图的排课问题模型，并揉合蚁群算法a s 、 a c s 、m m a s 三个不同模型的优点，提出一种面向排课问题的改进型蚁群 算法。算法中先把大部分课程都安排好，再解决所遇到的冲突，逐步接近 最优解。 4 启发式数值算法 文献 2 7 】提出了求解排课问题的启发式数值算法，即根据排课问题特 性，通过构造典型运输网络，把课表问题转化为典型运输网络中求最小费 用最大流问题。具有易于编程实现、收敛性好等优点。 但是这种方法建立在约束条件极大简化的基础上，只解决教师、班级 时间上的冲突，不考虑课程对教室的要求以及课程对上课时间的要求。处 理的情况较为简单，主要适用于中小学的排课表问题。 5 分组优化决策算法 文献 3 5 】介绍了分组优化决策算法。计算机模仿了人工编排课程表的过 程，按先难后易的原则，分组逐次排课。由于利用这种算法在编排课表时 是对全部的课程的一个部分进行编排，这样最终形成的课程表就可能是局 部的最优解，而不是全局的。 6 关联规则算法 文献 2 7 】介绍了采用布尔型关联规则f p g r o w t h 算法的思想来处理排课 问题。考虑了班级冲突、教师冲突和教室的冲突，避免了排课冲突，能够 基本满足需求，但对于多学时课程的离散性问题、好的教学日和教学时间 点如何合理分配等问题没有很好的解决。 7 分支定界算法 文献 2 6 描述了采用枚举法进行搜索。在对一棵庞大的树进行搜索时， 大胆地将无可行路线的大量分支去掉，即采用“分支限界法来剪枝。这 棵树的根就是排课的起点。限界采用一种判别原则，即在编排课程表时， 定义一种抽象的界，使得在排到某门课时，判断它是否超过了这个界，如 果超过了这个界，就把它剪掉。这是一种非完全的穷举法，有可能过早地 产生可行解而进入局部最优的陷阱。而且计算量很大，仅适用于规模较小 的课表编排情况。 哈尔滨工程大学硕士学位论文 1 4 现有遗传算法解决方案 目前，国内外已经有很多使用遗传算法求解课程表编排问题的应用： ( 1 ) 9 0 年代初期，c o l o m i 等人首先尝试应用遗传算法( g e n e t i ca l g o r i t h m ， g a ) 来解决u 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 ，大学课程表问题) 问题，引进 了矩阵表示方案及相应的交叉、变异算子。后来c o l o m i 又将其成功地应用 到了意大利米兰市的一所规模较大的学校中。 ( 2 ) c h upc 和b e a s l e yje 对课程表的一般安排问题使用了遗传算法进 行求解，着重于遗传算法的全局最优解搜索，避免了问题的局部最优解。 ( 3 ) 日本的s i g e r u 用具有控制约束的遗传算法提高了搜索效率。该算法 优化了教室的合理利用，解决了在教室较少的情况下，如何对教室进行合 理分配。 ( 4 ) p h i l i p p i n e s 大学的h os u n gc l e e 使用遗传算法对数学学院的课程 表问题进行了求解。 ( 5 ) 北京理工大学的杨宇使用遗传算法分别对局部排课问题和全局排 课问题进行了求解。 ( 6 ) 华北电力大学的兰慧使用基本遗传算法( s g a ) 设计了一个基于组件 结构的排课系统c a s 。系统设计成组件结构，每个组件完成一个较独立的 逻辑功能，增加了系统的灵活性和可维护性。 ( 7 ) 浙江工业大学的胡献华针对排课问题引入多目标决策协调模型，提 出了一种基于多目标决策协调模型的适应度计算方法，并改进了遗传算法 一般结构，形成了一个多目标协同优化的排课算法。 这些使用遗传算法对课程表进行编排的应用说明了课程表编排问题的 解决完全可以采用遗传算法，并且使用遗传算法来解决课程表的编排问题 能够获得很好的效果。但是单一的遗传算法在解决问题时仍有很多缺陷， 如易早熟、收敛速度慢等，因此本文试图将混沌优化算法与遗传算法结合， 构造一个混合遗传算法，用来改进单一遗传算法的不足。 1 5 论文组织结构 本论文正文内容的组织结构如下： 9 哈尔滨工程大学硕士学位论文 第l 章，绪论。首先阐述了本课题的研究背景、意义，其次介绍了国 内外研究动态及发展趋势，再次简要概括了当前存在的排课问题主要求解 方法及现有基于遗传算法的解决方案，最后介绍了论文的组织结构。 第2 章，排课问题原理及数学模型。首先概述了课程表问题的发展历 程，然后介绍课程表问题设计的要素并做了符号约定、简析各种规则，分 析了排课问题的求解复杂度，其中包括排课问题的解空间问题和求解目标， 最后建立了排课问题的组合优化模型，指明一般意义下的目标函数定义。 第3 章，标准遗传算法在排课问题中的应用。首先介绍了遗传算法的 基础知识，其中包括基本术语、基本思想、一般结构与遗传操作和遗传算 法的特点，然后将标准遗传算法应用在排课问题上，分别介绍编码方法、 种群初始化、适应度函数、复制算子选择、交叉算子选择以及变异算子选 择。 第4 章，混沌遗传算法在排课问题中的研究。在第3 章的基础上，分 析标准遗传算法的局限性及其原因，提出两种改进方法，包括基于混沌控 制的遗传算法和基于混沌优化的遗传算法，并且介绍了两种算法在排课问 题中的应用。 第5 章，实验结果分析。针对第3 章和第4 章的算法在排课问题中的 应用进行试验，并分析试验结果得出结论。 1 0 哈尔滨工程大学硕士学位论文 第2 章排课问题的原理和数学模型 课程表是一个学校日常教学工作和其它各项活动的指挥调度表。它不 仅是学生和教师上课的依据，而且对学校其它工作的统一安排也有直接影 响。利用计算机辅助手段编排课表，是教学管理实现科学化、现代化的重 要研究课题之一。本章将对排课问题的相关知识进行简要的介绍。 2 1 排课问题概述 从概念模型上讲，排课是一个四维空间上的组合优化求解问题。四维 分别指分别为教师、学生、时间和教室，约束条件为教学计划和各种现实 情况的特殊要求。排课问题的实质就是解决各因素之间的冲突，最终形成 符合需求的课表，并以不同对象的视角加以呈现，如图2 1 所示。 图2 1 课程表问题的概念模型 从理论上讲排课问题又可以称为课程时间表问题( c o u r s e t i m e t a b l i n g p r o b l e m ) ，是一个涉及多种因素的基于时间规划和组合优化的问题。由于 问题具有的难度和挑战性，许多研究者在这上面投入了大量精力，并取得 了丰硕成果。从二十世纪五十年代以来，国际上就有人开始研究计算机自 动排课问题。1 9 6 2 年，g o t l i e b c c 教授就对课程表问题进行了形式化描述， 哈尔滨工程大学硕士学位论文 即一系列规划组合问题。到了7 0 年代，s e v e n 等人将排课表问题理论化， 证明该问题是一个n p 完全类问题，根据计算理论和难解性理论，排课表问 题没有多项式算法。当问题的规模增大时，解的数目呈指数函数增长，在 一般的实际情况中是不可能准确地求出最优解的【2 0 】。 随着算法复杂性理论的完善，人们不再强调一定要求得最优解，更多 的研究转向实际应用的角度，能够得到较好的解得近似算法，或以一定的 概率保证解的质量的随机算法的研究越来越受到重视。于是兴起了现代智 能优化技术，出现了崭新的智能优化算法，诸如人工神经网络、遗传算法、 蚁群算法、进化计算、模拟退火、禁忌搜索及其混合优化策略等。自从2 0 世纪8 0 年代以来，这些优化技术在诸多领域得到了成功应用，使得排课问 题的研究也出现了崭新面貌，直到今天仍有巨大的发展。 2 2 排课问题的要素 排课问题需要考虑的因素几乎是全校性的，像可以单独完成某种任务 的机器。学校是一个有机组合而成的整体，其内部各组成部分既各司其职， 又密切协调合作，以保证日常正常教务工作的运转和教学任务的完成。 排课的过程是对学校中各种资源的重新规划，将学生、教师、课程安 排在一段时间的某个教室内，因此排课问题需要考虑的必要要素有以下5 个： ( 1 ) 时间：排课中关于时间的概念有年、学期、周、天、节。一次排课 过程针对某一年份中某一学期进行，学期以周为元素，从开学的第一周至 学期结束的第n 周，每周内含有教学日，一般为5 或6 天( 由教学单位自 行制定) 。每个教学日由节构成，是上课的最小单元。时间集合为： 尸= 切。，p ：，p 3 ，p 口j ，鼻表示可排课的第i 个时间段，如舅代表学期第一 周的第一个教学日内的第一个节次。 ( 2 ) 教室：与教室相关的概念有教学楼、楼层、编号、类型、支配使用 单位。每个教室在同一时间内只能进行一门课程的授课，并且教室的容量 应该大于或等于上课的人数。教室集合为：r = 瓴，r 2 ，r 3 ，k 。 ( 3 ) 课程：课程拥有自己独立的编号、名称和开课学院。课程可以拥有 1 2 哈尔滨工程大学硕士学位论文 葺i i i i i i i i i i i i i i i i i 宣i i i i i i i i i i i i i i i i i i 宣|r _v i 7 。 i i | | 多个教师以及多名学生。每门课程都有指定的教室类型，如多媒体教室、 实验教室或普通教室等。课程根据自己的授课计划，设定了授课起始周和 截至周以及对应的周学时数。课程集合为：l = l i ，：，1 3 ，) 。 ( 4 ) 教师：教师拥有独立的编号，每个教师同一时间内只能上- i 1 课程。 教师集合为：t = t it 2 ，t 3 ，t ) 。 ( 5 ) 班级：每个班级隶属于不同的院系、专业。同一班级在同一时间内 只能接受- i 1 课程。班级集合为：c = 矗，c ：，岛，) 。 2 3 排课的规则及优化模型 排课是将教师与学生在时间和空间上根据不同的规则、条件进行排课 组合，以使教学工作正常进行。这里的规则主要是避免冲突。避免冲突也 是排课问题中要解决的核心问题。只有在满足全部规则和避免所有冲突的 基础上，才能保证整个教学计划合理正常进行。对教师、班级、课程、时 间、教室等几部分资源进行最优化配置，才能保证排课的顺利完成以及充 分发挥各个资源的优势以达到提高教学质量的目的。 将排课的规则按照程度分类，可以有效的优化课表编排过程。一般将 其分为两类：硬规则和软规则，前者是衡量排课方案是否切实可行的标准， 软规则是衡量排课方案优劣的标准，通常判断一个排课方案的优劣标准有 多个。 1 硬规则：基本硬规则指资源在时间或空间上发生了冲突，是不可违 背的规则。一般硬规则包含以下几点： a )在同一时间同一教室内不能上两门不同的课程，见式2 - 1 。 r l ： ( 2 - 1 ) 其中：j | = l ，k ；q = 1 ，q 。 r一1 教室r k 在时间pq 由教师t 历上课程l p ； 一“p 一10 否则。 b )在同一时间同一教师不能给两门不同的课程上课，见式2 - 2 。 1 3 i 工 一 k晡 屯 m 删 删 p 川 哈尔滨丁程大学硕士学位论文 r 2 ： ( 2 - 2 ) 其中：朋= 1 ，m ；q = 1 ，q 。 ，一j 1教师t 。在时间p q 、教室r k 上课程l p ； 1 一| p 一10 否则。 c )在同一时间同一学生不能上两门不同的课程，见式2 - 3 。 r 3 ：e 工协 1 ( 2 3 ) 其中：1 1 = 1 ，n ；q = 1 ，q 。 yj1 班级c n 在时间p q 上教师t 埘的课程l p ； 1 p - 一10否则。 2 软规则：排课过程中希望被满足，但不满足也无大碍的规则，它们 的违反与否往往是与排课实际情况相关。 a )课程安排节次函数z 。课程的上课教学效果与上课的节次是有 联系的，尽量将课程安排在教学效果较好的节次中。用万。表示第h 节次的 教学效果系数，见式2 - 4 。 = e c n wl ( 2 4 ) b )课程周次组合函数厶。对于周学时比较大的课程( 如4 ) ，应 该将其进行隔天安排，具备较好的分散度的课程才有好的教学效果。用万：d 表示- - n 课程安排隔天天数d 的教学效果系数，见式2 - 5 。 = c 。刃2 d ( 2 5 ) c )满足教师期望条件函数六。排课需要考虑教师提出上课时间和 上课地点的要求。课程的主讲教师和课程有着对应的关系，将教师提出的 上课要求固化在其对应的课程上，用吼表示满足课程上课要求的系数，见 式2 - 6 。 1 4 一 k 研 删k 尸川 哈尔滨工程大学硕士学位论文 a = ec n t o 3 ， ( 2 6 ) 可见，排课问题是一个在约束条件下的多目标决策优化问题，因此将 各软规则作为优化的目标函数，将各硬规则作为其约束条件。建立数学模 型，见式2 - 7 、2 - 8 ： m a x 厂g ) = ( 六， ，六) ( 2 7 ) 鲥r 偿 8 ， 2 4 排课问题的复杂度分析 排课问题是一个组合优化问题。经典的组合规划问题的求解，主要依 靠约束条件，即规则来实现。只要规则充分，那么最优的组合方案就能被 唯一确定。因此，从理论角度来说，组合规划作为描述课表问题的数学模 型并无不妥，但在实际工作中，随着论域范围的膨胀，即组合方案数的增 加，规划问题也就