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

太原理一i _ = 火学硕士研究生学位论文 遗传算法求解排课问题的研究 摘要 排课问题是一个有约束的、多目标的组合优化问题，并且已经被证 明为一个n p 完全问题。运用计算机进行自动排课既是高校教务管理的迫 切需要，同时也有重要的理论意义。但由于排课问题复杂多变，几十年 来一直没有很好解决。本文的目的就是要找到一种解决这种复杂问题的 方法。 遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度 并行、自适应的随机搜索算法，是一种非常有效的解决n p 完全的组合问 题的方法。本文将遗传算法应用于排课问题的求解，进行了以下几个方 面研究工作： 1 系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目 标和难点，用数学模型完整地描述了排课问题，并提出了排课问题 求解方法的总体框架和技术路线。 2 给出了排课问题的e r d 和类图，设计了排课系统的数据结构，并 以此对课表安排过程的各个子算法进行了研究。 3 针对排课问题研究了染色体编码方式以及遗传操作算子的设计，并 引入多目标决策协调模型，提出了一种基于多目标决策协调模型的 适应度计1 算方法，并改进了遗传算法一般结构，形成r 一套多目标 太原理工火学硕十研究生学位论文 协同优化的排课算法。 4 以v c + + 为基本开发工具，m ss q ls e r v e r 2 0 0 0 为后台数据库， 设计和实现基于g a 算法的排课测试系统。通过一个实例分析了遗传 算法的各个参数的设置对排课效率以及排课质量的影响，分析显示遗 传算法的应用使所得结果令人满意，大大提高了工作人员的排课效 搴。 关键字：遗传算法，排课问题，组合优化，测试 t h er e s e a r c ho fg e n e t i c a l g o r i t h mi nt t p a bs t r a c t t i m e t a b l i n gp r o b l e m ( t t p ) i sam u l t io b j e c t i v ec o m b i n a t i o n o p t i m i z a t i o n p r o b l e mw i t h c o n s t r a i n t s ，a n d a l s oh a sb e e n p r o v e d n p c o m p l e t e d ；i ti st h ed e m a n dr e s e a r c h i n gt h a tc o m p l e t es o l v e dc o m p l e t e l y f o ri t so fb o t h u n i v e r s i t y e d u c a t i o n m a n a g e m e n ta n dt h e o r yt h et a b l e s c h e d u l i n gw i t hc o m p u t e r s t h ep u r p o s eo ft h i sp a p e ri st ot r ya n o t h e rw a yt o s o l v et h ec o m p l e xp r o b l e m g e n e t i ca l g o r i t h m ( g a ) i sah i g h - e f f e c t i v er a n d o m l ys e a r c h i n ga l g o r i t h m ， b a s e do nt h en a t u r ee v o l u t i o n i ti sav e r ye f f e c t i v e a l g o r i t h mt or e s o l v e n p - c o m p l e t e dc o m b i n a t i o no p t i m i z a t i o np r o b l e m t h ep a p e ri sa i m e da t s o l v i n gt i m e t a b l i n gp r o b l e mu s i n gg a t h em a i nc o n t e n ta r ea sf o l l o w i n g ： 1 w es y s t e m a t i c a l l ya n dc o m p l e t e l yd i s c u s sf a c t o r s ，r e s t r i c t i o n s ，o b j e c t i v e a n dd i f f i c u l t ya t t a c h e dt o1 v r p ，d e s c r i b e st t p b ym a t h e m a t i cm o d e l a n db r i n g f o r w a r dth ew h o l ef r a m ea n d t e c h n o l o g yr o u t eo fm e t h o d s i i i 查堕堡! 查堂堡塑塑生堂堡堡塞 2 g i v i n go u te n t i t y r e l a t i o nd r a w i n g ( e r d ) a n dc l a s si l l u s t r a t i o n ，d e s i g n i n g d a t as t r u c t u r e ，w es t u d ym a n ys u b a l g o r i t h m si nc o u r s eo fs o l v i n gp r o b l e m ， p u t f o r w a r dar a n d o m a r r a n g e m e n ta l g o r i t h mh a v i n g l o c a l h e u r i s t i cb a c k d a t i n ga b i l i t yt of i n df e a s i b l es o l u t i o nq u i c k l ya n de a s i l y 3 w es t u d yc h r o m o s o m ec o d i n ga n dh e r e d i t yo p e r a t o rd e s i g n i n ga i m e da t t t p , t h e ni n t r o d u c et h em u l t io b j e c t i v ed e c i s i o n m a k i n gc o n c o r d a n c em o d e l ， p u tf o r w a r daf i t n e s sc o m p u t a t i o nm o d eb a s eo nm u l t io b j e c t i v ec o n c o r d a n c e d e c i s i o n m a k i n gm o d e la n di m p r o v et h eg e n e r a l i z e ds t r u c t u r eo fg a ，f o r ma c o o r d i n a t e dm u l t io b j e c t i v eo p t i m i z a t i o na l g o r i t h mo f t t p 4 w eu s ev c + + a sb a s i cd e v e l o p m e n tt o o l s ，m ss q l s e r v e r 2 0 0 0a s d a t a b a s e ，d e s i g na n dr e a l i z ea u t o t i m e t a b l i n gs y s t e mb a s e do ng a a f t e r a n e x a m p l e ，w ef i n dt h a tt h es o l u t i o ni s s a t i s f i e d t h ea l g o r i t h mi ss t e a d ya n d o p t i m i z e w a r da n di m p r o v e st i m e t a b l i n ge f f i c i e n c yg r e a t l y k e yw o r d s ：g e n e t i c a l g o r i t h m ，t i m e t a b l i n gp r o b l e m ，c o m b i n a t i o n o p t i m i z a t i o n ，t e s t i v 声明 y3 7 9 3 8 8 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 垂尘! 圭肇 日期：v o s s 1 3 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：至生垡日期：1 2 望6 ：羔：! 导师签名：羔兰! 旦签日期：坦：皇：! ； 太原理】人学硕+ 研究生学位论文 第一章引言 高校的教务管理中，排课表工作非常复杂，通常是手工操作要花费大量的精力， 且效率低下，教学资源也很难充分利用因此，这是一个急需解决又非常棘手的问题 由于高校教学单位和课程众多，且相互交叉，教师和教室又严重短缺，很难用手工制 定出准确、统一、高效、合理的课表。另一方面教学管理的信息化不可能建立在手工 操作的基础上，而理论研究和软件技术的成熟已为我们提供了计算机自动排课的重要 手段，编制出一套完备、高效、准确、实用的排课表程序已成为可能。 高校排课管理的主要任务是把全校各系或各授课部门的课进行汇总，然后根据教 学计划和教学资源制订全校的公共课，各院系的公共基础课和各班级的专业课课表， 以充分满足专业教学的要求，并优化配置各种教学资源，使教学工作科学、高效、顺 利的进行。 本章概述了排课问题，评述了前人的研究工作，引出了本文的研究内容。 1 1 排课问题的意义和目标 排课工作开始于教学计划的编制。即教务处必须在每学期前收集各个学院每学期 的开课信息，然后统计下学期全校可用的教学资源，与各学院协调交互，决定各校区 的时间组织形式和各门课程的开课与否，最后根据不同的专业背景，以班级为单位编 制下学期的开课任务书。开课任务书应该包括全校每个班级的开课计划表，而开课计 划表中的每个开课计划都应该包含校区、班级、教师、课程、课程类型、开课学院、 人数、需求教室资源类型、每周课时的情况、有特殊要求时的上课方式以及教师期望 时间等完备信息。 教学计划的实施的关键是课表的编排。根据课程的特性，或者出于特殊情祝的考 虑，某些开课计划有着先于全校统一安排的要求，则这些课程必须优先安排预置，上 报教务处备案。待特殊丌课计划安排完毕，教务处还必须确定哪些丌课计划为难排计 太原理1 人学硕十研究生学位论文 划，哪些丌课计划为易排计划，根据“先难后易”的原则，逐个对开课计划进行安排。 在此过程中，还必须遵守多个排课原则： 1 在同一时间同一学生不能上两门不同的课程： 2 在同一时间同一教师不能给两门不同课程上课： 3 在同一时间同一教室不能安排两门不同课程： 4 每门课程的教室都有自己特定的类型： 5 教室必须足够大，能够容纳上课的学生； 6 教师、学生在不同校区上课时要留一定的时间用于赶赴； 7 体育课需安排在特定时间，且同一时段内之后不能再安排课程； 8 实验课、实习课等课程有自身的安排方式。等等 而且一般还有以下多个目标： i 一个班级时间安排在天上尽量分布均匀： 2 对于校区设置的课表的各个时间存在一定的偏好： 3 尽量满足教师上课时间的期望； 4 教师对时间安排在课表上的密度有一定的喜好： 5 教师和班级相邻两次上课地点尽量较近；等等 时下大多数院校的排课方法是手工编排方法，它主要通过人智能的判断和协调来 完成的。手工编排工作往往开始于一个学期数月前，各部门的协调交互频繁，而且在 实际安排过程中，涉及的校区有多个，教师数量成千，学生数目上万，教师跨院上课 和班级交叉上课众多，而且在计划安排完毕之后，往往由于频繁的变动不得不及 时调整。所有诸如此类因素，使得排课工作不堪重负，工作结果也不尽人意。 计算机排课，它是把排课问题化为计算领域的有约束的时空组合优化问题进行 求解的。它对课表上的时间进行了分片和编号处理，使分成的每个时间片和每个教室 空间组合，构建了一个个大小不等的时空组合块，并根据求解规则，对每个开课计划 进行时空组合块分配，而且分配的组合( 安排方案) ，必须在目标空间中表现出良好的 人为满意度。这些人为满意度往往不仅多个，而且是模糊的。 虽然利用计算机来模拟手工排课工作，可以抽象问题中的各个要素，数学表达 各种约束条件，并根据课表的组织形式和普遍存在的规律，缩减了问题空白的搜索范 2 太原理r 人学硕十研究生学位论文 围，以及有效组织了排课知识，使其在一定程度上呈现智能化。但由于其问题本身的 求解规模过于庞大，各要素之间的关联层出不穷，以及人们对多个课表优劣评定的准 则存在差异，使计算机在求解排课问题的过程中，面对难以穷尽的组合和多个模糊目 标的优化，也表现得无能无力。 就其实质而言，排课问题是一个有约束的、非线性的、模糊多目标优化的、难解 的、时空组合的数学问题。即在满足各种已知的约束条件的情况下找到一组较优的时 空组合，同时在具体实践上它受到教学组织形式、客观物质条件和求解目标等多种因 素的相互影响，使这一问题在实际解决时呈现出受具体条件制约的特点。 1 2 排课问题研究综述 排课问题是n p 完全问题，许多学者分别在理论、启发式搜索技术应用求解、专 家系统应用求解和遗传算法应用求解上作了很多研究。 1 2 1 排课问题的理论研究 国外从2 0 世纪5 0 年代末就对排课问题开展了研究。1 9 6 3 年g o t l i e b 在他的文 章【2 1 中提出了排课问题的数学模型，它标志着排课问题的研究正式跨入了庄严的科学 殿堂，但由于在实践中遇到的困难，使人们排课问题的题解是否存在产生了疑问。1 9 7 6 年se v e n 在论文【2 2 】( 译：关于时间表和多物流问题的复杂性) c o o p e r 等人在【2 3 中，证明 了排课问题是n p 完全的，这虽然回答了排课在实践中遇到困难的原因，但同时等于 宣布计算机、解决排课问题无法实现，因为计算机难解性的理论研究指出，现代计算 机尚未找到解决n p 完全问题的多项式算法。此后这一问题的研究大多离开理论研讨 的轨道而转向经验方式，这使8 0 年代的许多排课系统缺乏普适性。 se v e n 的论证正式确立了排课问题的学术地位，把人对课表编排复杂性的认识 提高到了理论的高度。 122 排课问题的求解方法 从1 9 6 3 年g o t l i e b 提出了一个排课问题的数学模型之后，人们又对排课问题的 3 太原理工火学硕士研究生学位论文 算法作了许多探索，但由于排课问题是n p 完全问题，并且易受实际问题边界的影响， 大多数求解结果都不理想。 f e r l a n d 等人和吴金荣 3 1 】把排课问题化成整数规划来解决，但计算量很大，其 仅仅适用于规模很小的课表编排，对于大规模复杂的排课情况，至今没有一个切实可 行的算法：何永太【6 】和胡顺仁等人【7 】试图用图论中的染色问题来求解排课问题，可惜 图的染色问题本身也是n p 完全问题。由于问题的复杂，许多文章【2 】【1 5 【1 6 】【1 7 【1 8 1 利用 启发式函数来解决排课问题，大多数启发方法都是模拟手工排课的过程来实现的。由 于实际的排课问题存在各种各样的限制条件与特殊要求，对这些因素处理的好坏就显 得尤为重要。 进入2 0 世纪9 0 年代，国外对排课问题的研究仍然非常活跃。如印度v a s t a p u r 大 学管理学院a r a b i n d at 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 sa f e r l a n d 以及c h a r l e sf l e u t e n t 等【8 】。 a r a b i n d at r i p a t h y 的工作是针对以“人”为单位进行课 表编排的。他运用拉格朗日松弛法和分支定界技术求解，这种方法的缺点是为了减少 变量的个数，人为造成科目间的冲突。a t r i p a t h y 还研究了研究生课表编排问题，他 采用多重课组的方法来处理冲突( 即根据学生选课的矛盾情况，将人数多的课程在一 星期内开多次) 。j a c q u e sa f e r l a n d 等人则把排课问题分成两个子问题：时间表问题和 分组问题。在时间表问题中，根据学生注册情况、教师和教室的可利用情况形成一个 主时间表。对于选课人数较多的大课，一个星期要分成几个时间段来上，分组问题就 是将学生分给各时间段。两个问题相关联，通过惩罚因子来构造启发函数。他们研制 的s a p h i r 课程调度决策支持系统分为数据处理、自动优化、交互优化等几个模块。 该系统解决矛盾的主要方法也是采用多重课组。这是与西方的教学管理体制不可分 的。 另外一批学者还将模拟退火法应用到排课问题的研究中例【3 0 【1 1 【1 2 】。模拟退火法 ( s i m u l a t e da n n e a l i n g ) 是k i r k p a t r i c k 等人于1 9 8 3 年首先提出的，它是人们从自然界固 体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优 化问题的出发点是基于物理中固体物质的退火过程与一般优化问题间的相似性。在对 固体物质进行退火处理时，常常先将它加温使其粒子可自由运动，以后随着温度的逐 渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度下降速率足够慢，则固体 4 太原理t 人学硕+ 研究生学位论文 物质定会形成最低能量的基态，优化问题也存在类似过程。模拟退火法被用来解决许 多实际应用中优化问题，取得了不错的效果，但用其解决排课问题，现在还处在模型 试验阶段，还有许多问题要解决。 国内对排课问题的研究开始于8 0 年代初期，所用方法从模拟手工排课到运用人 工智能构建专家系统或决策支持系统都有。 基于时间位图迭加匹配的算法定义了教学过程中的时间位图、课时模式和时间匹 配等概念，将排课问题转化为基于时间位图迭加匹配的课时模式查找问题，给出了相 应的抽象具体排课过程，并对于排课过程中可能出现的冲突，探讨了三种回溯消除冲 突方式。 基于优先级自动排课算法口】利用了运筹学中分层规划的思想，把排课问题在数 学上看作为一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊要求为 约束条件的组合规划问题，采用了化整为零的思想及提出了优先级的概念，有效地抽 象了实际排课情况，缩小了求解问题的空间。 基于专家系统的求解算法【34 将专家系统知识引入排课问题的求解中，有效组织排 课过程中的知识，使各种排课逻辑从程序中解放出来，能够便于各种排课经验的累计， 使排课结果更加符合实际情况。 更多算法 1 9 】【2 0 1 1 2 1 1 1 2 2 】【2 3 】 2 4 1 1 2 5 1 已经提出，它们都是一定程度上启发搜索求解方法， 虽然对后继者有一定的借鉴意义，但它存在以下几点不足之处： 1 对于启发式搜索技术来说，搜索过程的启发信息依赖于实际情况，排课问 题的求解只能针对个别的实际问题，不能形成一种通用的有效排课方法。 2 引入专家系统技术的排课方法，虽然可以对排课规则知识有效组织，但由 于排课过程中各要素关联规则的难以提取，并且实际求解效果也不理想。 3 没有引入目标优化技术，课表的优劣判定的论述甚少，只能在问题的某个 方向进行搜索，不可能达到多个目标同时优化。 对于排课系统的研发，林漳希和林尧瑞1 9 8 4 年在”】上发表了该课题上的实验 性研究成果。成形的系统有大连理工大学1 9 9 8 年推出的的教学调度系统3 0 0 版本【3 8 】 和由清华大学计算机与信息管理中心开发的综合教务管理系统。但是，实际上： 1 国内的排课软件很少，涉及到自动排课算法的系统更少，大部分局限于辅助 n 太原理| = 人学硕十研究生学位论文 人工排课，并没有任何“智能”成分。 2 自动排课系统往往由于在随机求解过程中出现太多的未被安排课程而很难在 实际中使用。 随着人工智能的发展，特别是在计算智能领域的拓展，借鉴于生物界进化思想 和遗传机制的遗传算法，由于其超群的并行搜索能力，以及在解决优化问题中表现出 来的高度鲁棒性，它己经被广泛应用于各个领域。 作为一种随机的优化与搜索方法，遗传算法有着两个主要特性： 1 智能性。即遗传算法在确定了编码方案、适应值函数及遗传算子以后，算法 将利用演化过程中获得的信息自行组织搜索。适应值大的个体具有较高生存概率，它 是具有“潜在学习能力”的自适应搜索技术。 2 并行性。由于遗传算法采用种群的方式组织搜索，从而可以同时搜索解空间 内的多个区域，并相互交流信息，这种搜索方式使得它虽每次只执行与种群规模成 比例的计算，而实质上，据g o l d b e r gd e 推算已进行了大约o ( n3 ) 次有效搜索。这 使得遗传算法能以较少的计算获得较大的收益。正是由于遗传算法的两个特性，使 得遗传算法迅速被运用于求解组合优化的排课问题。 c h upc 和b e a s l e y 对一般的安排问题中使用了遗传算法进行求解矧，他们着重 于遗传算法的全局最优解的搜索能力，避免了问题的局部最优解。日本的s i g e r u 用具 有控制约束的遗传算法来解决大学排课问题【2 8 1 ，提高了遗传算法的搜索效率。姚新使 用遗传算法优化了教师的合理利用，解决了在教室较少的情况下，如何对教室的利用 进行合理的分配【2 9 。针对高中课程的特点，意大利的c o l o r n i 等人使用遗传算法解决 了排课问剐3 0 1 。张春梅等人对大学课程进行分类，并对不同的课程使用具有自适应能 力的遗传算法进行了安排【3 1 】。p h i l i p p i n e s 的h os u n gc l e e 使用遗传算法对 p h i l i p p i n e s 大学的数学学院排课问题进行了求解。杨宇分别使用遗传算法对局部排课 问题和全局排课问题进行了求解【3 。 他们运用遗传算法针对自身所描述的排课问题进行求解，虽然在一定程度上取得 了喜人的成果，但综合考虑求解情况，有以下几点不足： 1 求解问题的边界定义。由于各自的研究背景不同，他们考虑的往往是排课一 6 太原理一人学硕+ 研究生学位论文 般情况，有些甚至是理想状态的排课，对于排课中更多的约束条件未予以考虑，而且 问题的求解规模普遍偏小，使得实用程度较低，很难在学校中展开使用。 2 问题的编码。一种较好的遗传算法的编码方式，应该不仅能够反映解空间完 备并无歧义的遗传信息，而且操作尽量简单，从而可以快速遗传操作和适应度评定， 继而影响算法整体的收敛时间。在以往的研究中，他们编码通常使用二进制，不能很 好地反映针对课表问题的更多实际情况的遗传信息。 3 求解的目标。以往的应用中，采用惩罚函数的居多，处理的都是单目标问题， 即使有多个目标，往往也线性聚合成一个目标进行处理。这在多目标优化理论中， 往往求解所得的是一个非劣解，而忽略了一组非劣解。 1 2 3 遗传算法与其他搜索技术的比较 对于课程表的编排这类整体优化问题的搜索求解技术，主要包括基于微分的 搜索技术、随机搜索技术、启发式搜索技术和枚举技术。遗传算法属于进化算法，而 进化算法及进化算法中的每一个分支均属于启发式随机搜索方法。 目前，对于求解整体优化问题已经进行了大量理论研究，并提出了许多基于导数 的解析方法和其他非解析的数值集约化技术。但是，在实际领域中存在着各种高度复 杂的优化问题，其目标函数可能表现为非连续或非处处可微、非凸、多峰和带噪声等 各种形式，这类复杂优化问题不适合于采用解析方法，同时用传统上的搜索技术求解 也会遇到许多困难。因此，多年来人们一直在努力寻找能够处理这类问题的新的、更 稳健的优化技术。 借鉴于自然界的进化过程，h o l l a n d 首先将g a 用于计划的优化和选择，使得g a 逐渐成为一种典型的启发式随机搜索算法，为求解优化问题提供了一个有效的新工 具。采用g a 以及e s ( e v o l u t i o n a r ys t r a t e g i e s ，进化策略) 、e p ( e v o l u t i o n a r y p r o g r a m m i n g ) ，进化规划) 等一类进化算法来求解整体优化问题是目前进化计算研究 和应用的重点，统称为“进化优化”，而用来求解整体优化问题的遗传算法也被称为 “遗传优化器”。 传统的基于微分的方法，包括直接法( 如爬山法) 和间接法( 如求导数方法) ，对问 7 太原理i ：人学硕士研究生学位论文 题性质有较高的要求，或者是针对特定问题形式而设计的，一般统称为强方法。枚举 方法是一种解空间的搜索方法，包括动态规划法、隐枚举法和完全枚举法等，其特点 是可以发现问题的全局最优解，但是计算效率太低( 存在着维数灾难) ，不适用于大型 优化问题求解。随机搜索方法是在问题空间中随机选择一定数量的点，然后从中选优， 带有一定盲目性，对于问题不能保证解的质量，而且其计算效率与枚举方法基本等价。 启发式随机搜索方法是目前关于复杂优化问题求解的一类有效方法，不需要或需 要很少的关于问题的先验信息。其次，该类算法具有很强的鲁棒性，即能适应不同领 域的优化问题求解，并在大多数情况下都能等到比较满意的解。启发式随机搜索方法 一般统称为弱方法。g a 就是一种典型的弱方法，与模拟退火算法、爬山算法等相比， 具有独特的算法形式和运行机理，在复杂优化问题求解中有着比较显著的优势。 与传统的启发式优化搜索算法相比，遗传算法的主要本质特征在于群体搜索策略 和简单的遗传算子。群体搜索使遗传算法得以突破邻域搜索的限制，可以实现整个解 空间上的分布式信息探索采集和继承；遗传算子仅仅利用适应值度量作为运算指标进 行染色体的随机操作，降低了一般启发式算法在搜索过程中对人机交互的依赖。这样 就使得遗传算法获得了强大的全局最优解搜索能力、问题域的独立性、信息处理的隐 并行性、应用的鲁棒性、操作的简明性，是种具有良好普适性和可规模化的优化方 法。 作为搜索技术的不同分支一爬山法、模拟退火和遗传算法，有人用“袋鼠登高” 作了的形象比喻【3 6 l “注意，在目前讨论的所有爬山法中，袋鼠最有希望到达靠近它出发点的的山顶。 但不能保证该山顶是珠穆朗玛峰，或者是一个非常高的山峰。各种使用的方法都试图 找到实际全局最优值。 在模拟退火中，袋鼠喝醉了，而且随机地跳跃了很长时间。但是，它渐渐清醒了 并朝着峰顶跳去。 在遗传算法中，有很多袋鼠，它们降落到喜马拉雅山脉的任意地方( 如果飞行员 没有迷失方向) 。这些袋鼠并不知道它们被设想寻找珠穆朗玛峰。但每过几年，你就 在一些高度较低的地方射杀一些袋鼠，并希望存活下来的那些是多产的，并在那里生 儿育女。 只 太原理t 人学硕十研究生学位论文 从遗传算法的特点可以看出，利用遗传算法求解排课问题，与利用其它启发搜索 方法相比较，其搜索过程带有自组织的智能性和并行性，且操作简单，可以更少地依 赖于实际问题的情况，实现课表的优化。 1 3 本文研究内容 由于排课问题是一个有约束的、多目标的、难解的组合优化问题，采用具有智 能性和并行性的遗传算法，来对排课问题进行求解，是所有求解该问题方法中较明智 的选择。本文目的是在相关遗传算法的基础之上，提出一个课表方案的随机生成和优 化算法，能够较大程度地反映实际排课情况和尽量达到多个目标最优。本论文的研究 内容有： 1 详细说明排课问题中的要素和常用的约束条件，分析排课问题的求解难点和 目标，给出排课问题的完整数学描述，并提出本文求解排课问题方案的总体思路和技 术路线。 2 通过排课问题的e r d 和o o a 分析，描述排课系统的数据库结构，并对课表 安排过程的各个子算法展开描述，提出了一个的随机安排算法，生成可行解，产生初 始种群，为后续的遗传算法优化课表的过程提供了遗传操作、迭代进化的初始种群。 3 对多个排课问题的目标进行量化分析，建立遗传算法优化的目标空间。针对 排课问题进行染色体编码以及各个遗传算子设计，并对具有多个目标的适应度如何确 定展开讨论，最后集成排课整体优化算法。 4 对一个实际问题的算例，利用上述的随机生成方案算法和基于遗传算法的排 课优化算法进行求解，并对一些中间值进行跟踪分析，从试验的角度论述算法的可行 性。 9 太原理工人学硕士研究生学位论文 2 1 遗传算法简介 第二章遗传算法的基本理论 遗传算法( g e n e t i c a l g o r i t h m s ，g a ) 是一种借鉴生物界自然选择和自然遗传机制的 随机搜索算法，其主要特点是群体搜索策略和种群中个体之间的信息交换。它尤其适 用于处理传统搜索方法难以解决的复杂的和非线性的问题。如著名的巡回旅行商问题 ( t r a v e ls a l e s m a np r o b l e m ，t s p ) 、作业调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s p ) 、 背包问题( k n a p s a c kp r o b l e m ，k p ) 、排课问题等。由于它具有这些特点，自2 0 世纪8 0 年代以来关于它的理论和应用研究都成了十分热门的课题，尤其是应用研究显得格外 活跃，不仅应用领域扩大了，而且利用遗传算法进行优化和规则学习的能力也显著提 高，目前它已被广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命 等领域，被认为是2 1 世纪有关智能计算中的关键技术之一。尽管遗传算法在实际应用 中取得了巨大的成功，但相对其鲜明的生物基础，其数学基础是相对不完善的，主要 表现为：缺乏广泛而完整的遗传算法收敛性理论；h o l l a n d 的模式定理尚不能清楚解释 遗传算法在非二进制形式表示情况下的应用：用遗传算法解决实际问题的时间复杂性 这些不足严重阻碍了遗传算法的应用推广，有待于进一步研究。 2 1 1 遗传算法的简要由来 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 的研究开始于2 0 世纪6 0 年代末期到7 0 年 代初期，主要由美国m i c h i g a n 大学的j o h nh o l l a n d 教授与其同事、学生们研究形成 了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟 生物进化的机制来构造人工系统的模型。随后经过多年的发展，取得了丰硕的应用成 果和理论研究的进展，特别是近年来世界范围形成的进化计算热潮，计算智能已作为 人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗传算法受到广泛 1 0 太原理工人学硕士研究生学位论文 的关注。从1 9 8 5 年在美国卡耐基梅隆大学召开的第一届国际遗传算法会议 ( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r it h m s ：i c g a 8 5 ) ，到1 9 9 7 年5 月 i e e e 的t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 创刊，遗传算法作为具有系统 优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。 2 12 遗传算法的基本术语 既然遗传算法效法于自然选择的生物进化，是一种模仿生物进化过程的随机方 法，因此下面先给出几个生物学的基本概念与术语，这对理解遗传算法是非常重要的。 染色体( c h r o m o s o m e ) 是生物细胞中含有的一种微小的丝状化合物。它是遗传物质的 主要载体，由多个遗传因子一基因组成。遗传因子( g e n e ) d n a 或r n a 长链结构中占有 一定位置的基本遗传单位，也称为基因。生物的基因数量根据物种的不同多少不一， 小的病毒只含有几个基因，而高等动植物的基因却数以万计。一个基因或多个基因决 定了组成蛋白质的2 0 种氨基酸的组成比例及其排列顺序。 个体( i n d i v i d u a l ) ：指染色体带有特征的实体，在问题简化的情况下可代表染色 体。 种群( p o p u l a t i o n ) ：染色体带有特征的个体的集合称为种群该集合内个体数称 为群体的大小。有时个体的集合也称为个体群。 进化( e v o l u t i o n ) ：生物在其延续生存的过程中，逐渐适应其生存环境，使得其 品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。 适应度( f i t n e s s ) ：在研究自然界中生物的遗传和进化现象时，生物学家使用适 应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应度高的物种 将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖的机会就会相对 较少，甚至逐渐灭绝。 选择( s e l e c t i o n ) ：指决定以一定的概率从种群中选择若干个体的操作。一般而 言，选择的过程是一种基于适应度的优胜劣汰的过程。 复制( r e p r o d u c t i o n ) ：细胞在分裂时，遗传物质d n a 通过复制而转移到新产生的 细胞中，新的细胞就继承了旧细胞的基因。 太原理工人学硕士研究生学位论文 交叉( c r o s s o v e r ) ：有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉 而重组，即在两个染色体的某一相同位置处被切断，其前后两串分别交叉组合形成两 个新的染色体。这个过程又称为基因重组( r e c o m b i n a t i o n ) ，俗称“杂交”。 变异( m u t a t i o n ) ：在细胞进行复制时可能以很小的概率产生某些复制差错，从而 使d n a 发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。 编码( c o d i n g ) ：d n a 中遗传信息在一个长链上按一定的模式排列，即进行了遗传 编码遗传编码可以看作从表现型到遗传子型的映射。 解码( d e c o d i n g ) ：从遗传子型到表现型的映射。 2 1 3 遗传算法的基本思想 现在，我们引用上面的术语来更好地描述算法的基本思想。遗传算法是从代表问 题可能潜在解集的一个种群( p o p u l a t i o n ) 开始的，而一个种群则由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体( i n d i v i d u a l ) 组成。每个个体实际上是染色体 ( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合， 其内部表现( 基因型) 是某种基因组合，它决定了个体的性状的外部表现，如黑头发的 特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从 表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行 简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代 ( g e n e r a t i o n ) 演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度 ( f i t n e s s ) 大小挑选( s e l e c t i o n ) 个体，并借助于自然遗传学的遗传算子( g e n e t i c o p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异m u t a t i o n ) ，产生出代表新的解集的种 群。这个过程将导致种群像自然进化一样的后代种群比前代更加适应于环境，末代种 群中的最优个体经过解码( d e c o d i n g ) 可以作为问题近似最优解遗传算法采纳了自 然进化模型，如选择、交叉、变异、迁移、局域与临域等计算开始时，随机地初始 化一定数目的个体( 父个体1 、父个体2 、父个体3 、父个体4 、父个体n ) 形成初 始种群，并计算每个个体的适应度函数，第一代( 初始代) 就产生了。如果不满足优化 准则，开始产生新一代的计算。为了产生下一代，按照适应度选择个体，父代要求基 1 2 太原理 火学硕十研究生学位论文 圜重组( 交叉) 而产生子代所有的子代按一定概率变异。然后子代的适应度又被重新 计算，子代被插入到种群中将父代取而代之，构成新的一代( 子个体1 、子个体2 、子 个体3 、子个体4 、) 。这一过程循环执行，直到满足优化准则为止。 尽管单一种群的遗传算法很强大，可以很好地解决相当广泛的问题。但采用多种 群即有子种群的算法往往会获得更好的结果。每个子种群像单种群遗传算法一样独立 地演算若干代后，在子种群之间进行个体交换。这种多种群遗传算法更加贴近于自然 中种族的进化，称为并行遗传算法( p a r a l l e l i n gg e n e t i ca l g o r i t h m s p g a ) 遗传算 法的基本特点我们知道，传统的优化方法主要有三种：枚举法、启发式算法和搜索算 法： 1 枚举法枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函 数，该方法要求先对其进行离散化处理，这样就可能因离散处理而永远达不到最优解。 此外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前先进计算工 具上无法求解。 2 启发式算法寻求一种能产生可行解的启发式规则，以找到一个最优解或近似 最优解。该方法的求解效率比较高，但对每一个需求解的问题必须找出其特有的启发 式规则，这个启发式规则一般无通用性，不适合于其他问题。 3 搜索算法寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操 作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最 优解，但若适当地利用一些启发式知识，就可在近似解的质量和效率上达到一种较好 的平衡随着问题种类的不同以及问题规模的扩大，要寻求一种能以有限的代价来解 决搜索和优化的通用方法，遗传算法正是为我们提供的一个有效的途径，它不同于传 统的搜索和优化方法。主要区别在于： ( 1 ) 自组织、自适应和自学习性( 智能性) ，应用遗传算法求解问题时，在编码方 案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索 由于基于自然的选择策略为“适者生存，不适应者被淘汰”，因而适应度大的个体具 有更适应环境的基因结构，再通过基因重组和基因突变等遗传操作，就可能产生更适 应环境的后代。进化算法的这种自组织、自适应特征，使它同时具有能根据环境变化 来自动发现环境的特征和规律的能力。自然选择消除了算法设计过程中的一个最大障 13 太原理工火学硕士研究生学位论文 碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措 施。因此，利用遗传算法的方法，我们可以解决那些复杂的非结构化问题。 ( 2 ) 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而 不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的( i n h e r e n t p a r a l l e l i s m ) ，即遗传算法本身非常适合大规模并行。最简单的并行方式是让几百甚 至数以千台计算机各自进行独立种群的演化计算，运行过程中甚至不进行任何通信 ( 独立的种群之间若有少量的通信一般会带来更好的结果) ，等到运算结束时才通信比 较，选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求，可以说， 遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，而且对并行效率没 有太大影响。二是遗传算法的内含并行性( i m p l i c i tp a r a l l e l l i s m ) 。由于遗传算法 采用种群的方式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息。 使用这种搜索方式，虽然每次只执行与种群规模l q 成比例的计算，但实际上已进行了 大约0 ( n 3 ) 次有效搜索，这就使得遗传算法能以较少的计算获得较大的收益。 ( 3 ) 遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数 和相应的适应度函数。 ( 4 ) 遗传算法强调概率转换规则，而不是确定的转换规则。 ( 5 ) 遗传算法可以更加直接地应用。 ( 6 ) 遗传算法对给定问题，可以产生许多的潜在解，最终选择可以由使用者确 定( 在某些特殊情况下，如多目标优化问题不止一个解存在，有一组最优解这种遗传 算法对于确认可替换解集而言是特别合适的) 。 2 2 基本遗传算5 去( s i m p l eg a ，s g a ) 的表示 要利用遗传算法解决问题，就必须将其表示成便于处理的形式，这里介绍一下基 本遗传算法( s i m p l eg a s g a ) 的表示。s g a 可定义为一个8 元组： s g a - ( c ，e ，p 。n ，中，r ，1 i r ，t ) 式中各元素代表的意义： c 个体的编码方法，s g a 使用固定长度二进制符号申的编码方法 太原理：r 人学硕士研究生学位论文 e 个