（计算机应用技术专业论文）时间表问题的研究.pdf

摘要 时间表问题是一类特殊的资源调度问题，广泛应用于学校课程安排， 会议日程安排、体育比赛和航班时刻表的制定等。所以如何求解时间表闯 题成为一个关键的问题。本文以大学课程安排为例子，介绍了一种图形学 和人工智能算法相结合的一种方法来对时间表问题进行求解。 图形理论中的着色问题其本质是一个划分问题，将相互之间有冲突 的点划分到不同的子集中去。所以，由于图形着色的这种独特的能力，在 现实中有着广泛的应用，尤其是在需要解决冲突的领域。 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的算法， 具有高度并行、随机、自适应强的特点，是一种非常有效解决n p 完全问 题的方法。 课程安排问题由于要考虑的限制条件相对来说比较多，属于限制满 足的问题，根据这个特征，本文利用图形着色理论( g r a p hc o l o rt h e o r y ) 的点着色来表示这些限制条件，将整体的排课分解成三种图形( 周图形、 日图形、教室图形) 来表示。图形中各个节点为要进行分析的对象，即教 师、课程、时段以及教室，每条边表示对象之间的互斥关系。 本文的工作重点在于对点着色模型进行求解。针对点着色模型，提 出了两个切实可行的求解方法。第一个是分组遗传算法，第二个是基于序 列模型的点着色求解方法。 关键词：分组遗传算法，序列模型算法，时间表问题，大学课程表 问题 a b s t r a c t t n n e t a b l ep r o b l e m 叮r p ) i sas p e c i a lp r o b l e mo fr e s o u r e ea r r a n g e m e n t w h i c hi sw i d e l ya p p l i e di nc o u r 鹦s c h e d u l i n gp r o b l c m ( c s p ) 、a l ls o r t so f l a r g e c o n f e r e n c e s 、s p o r t sg a m e sa n dp l a n es c h e d u l i n gp r o b l e m h o w t or e s o l v er r p i sak e yp o i n t t h i sp a p e ri n 吐o d u c e same l 【h o db a s e do nt h eg r a p h i c st h e o r y a n dt h ea r t i f i c i a li n t e l l i g e n c et h a tt or e s o l v et h em i ne s s e n c e ，t h eg r a p hc o l o r i n gt h e o r yi sap a r t i t i o np r o b l e m i td i v i d e d t h ep o i n t sw h i c hc o n f l i c tw i t he a c ho t h e ri n t od i f f e r e n ts u b s e t s b a s e do nt h i s i n s t i n c t , g r a p ht h e o r yh a sb e e nu s e dw i d e l yt os o l v et h ep r o b l e mt h a tn e e dt o s o l v et h ec o n f l i c tp r o b l e m g e n e t i ca l g o r i t h mi sa ni n t e l l i g e n ta l g o r i t h mt h a ts i m u l a t e st h ep r o c e s s o f b i o l o g i c a le v o l u t i o n a saf l e wa l g o r i t h mo fo v e r a l lo p t i m i z e ds e a r c h , i t h a sa c h i e v e db r o a da p p l i c a t i o ni ns o l v i n go p t i m i z a t i o np r o b l e m sd u et os u c h d i s t i n c t i v ef e a t u r e s 嬲s i m p l i f i e dp r o c e s s u n i v e r s a l i t y , r o b u s t n e s sa n d a v a i l a b i l i t yo fp a r a l l e lp r o c e s s i n g g e n e t i ca l g o r i t h mh 勰b 渤m e 姐e f f e c t i v e m e t h o dt or e s o l v en pc o m p l e t e n e s sp r o b l e m g e n e r a ls p e a k i n g ，c s pi sap a r to fc o n s t r a i n ts a t i s f a c t i o np r o b l e m e m p l o y i n gv e r t e xc o l o r i n go f g r a p ht h e o r y , w e c a ne a s i l yt r a n s f e rt h ec s pi n t o as o l v a b l ep r o b l e m f o rc s ph a st oa s s i g ne a c hc o u r s eas p e c i f i ct i m es l o t ，t h i s s t u d yi st h ef i r s te v e rt oc o n s t r u c tt h r e el a y so fg r a p h s ，n a m e da sw e e k d a y , d a i l y , a n dr o o mg r a p h st os i m p l i f yt h ep r o b l e m t h en o d e sa l et h e nd e f i n e da s t e a c h e r , c o u l l j e ，t i m e t a b l ea n dc l a s s r o o m t h ee d g ec o n n e c t e dt w on o d e s m e a n sc o n f l i c t i o n , w h i c h s a y s b o t ho ft h et w on o d e sn o te x i s t e n c e s i m u l t a n e o u s l y t h ee m p h a s i so ft h i sp a p e ri st os o l v et h eg r a p hm o d e l t os o l v et h e m o d e l ，t h i sp a p e rb r i n g sf o r w a r dt w om e t h o d s t h ef i r s to r e i sg r o u pg e n e t i c a l g o r i t h m , t h es e c o n do n e i sm e r g em o d e l k c yw o r d s ：g r o u pg e n e t i ca l g o r i t h m s ，m e r g em o d e l ，丁r p ，c s p 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本论文 不包含其他个人已经发表或撰写过的研究成果对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名： 学位论文授权使用声明 本人完全了解华东师范大学有关保留，使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 学位论文作者签名：导师签名： 日期： o r i g i n a l i t yn o t i c e i n p r e s e n t i n g t h i st h e s i s i f l p a r t i a l f u i f i l l m e n t o ft h e r e q u i r e m e n t s f o r t h em a s t e r s d e g r e e a te a s tc h i n an o r m a l u n i v e r s i t y , 1w a r r a n tt h a tt h i st h e s i si so r i g i n a la n da n yo ft h e t e c h n i q u e sp r e s e n t e di nt h et h e s i sh a v eb e e nf i g u r e do u tb ym e a n y o ft h er e f e r e n c e st ot h ec o p y r i g h t , t r a d e m a r kp a t e n t , s t a t u t o r yr i g h t , o rp r o p r i e t yr i g h to fo t h e r sh a v eb e e ne x p l i c i t l ya c k n o w l e d g e da n d i n c l u d e di nt h er e f e r e n c e ss e c t i o na tt h ee n do ft h i st h e s i s s i g n a t u r e ：，d a t e ： c o p y r i g h t n o t i c e ih e r e i na g le et h a t t h el i b r a r yo fe c n us h a l lm a k ei t sc o p i e s f r e e l ya v a i l a b l ef o ri n s p e c t i o n if u r t h e ra g r e et h a te x t e n s j v ec o p y i n g o f t h et h e s i si sa l l o w a b l eo n i yf o rs c h o l a r l y p u r p o s e s ，i np a r t i c u l a r , s t o r i n gt h ec o n t e n to ft h i st h e s i si n t or e l e v a n td a t a b a s e s ，a sw e l la s c o m p i l i n ga n dp u b l i s h i n gt h et i t l ea n da b s t r a c to ft h i st h e s i s ， c o n s i s t e n tw i t h “f a i ru s e ”a sp r e s c r i b e di nt h ec o p y r i g h tl a wo ft h e p e o p l e sr e p u b l i co fc h i n a a u t h o rs i g n a t u r e ：d i r e c t o r s i g n a t u r e ： d a t e ： d a t e ： 1 1引言 第1 章绪论 时间表问题是一类特殊的资源调度问题，其应用领域十分广泛。随 着现代社会相对可利用资源的日益紧张，作好各类资源的统筹安排优化利 用是一件非常有意义的事情。本文研究的重点是时间表问题在教育领域的 实际应用为研究内容。时间表问题最典型的一个例子就是学校里面的课程 表的安排。本文就以课程表为例，详细介绍了一种解决时间表问题的方法。 课程表安排问题是学校每学期必须处理的例行工作。目前人们对时 间表问题应用在学校应用研究及其成果主要在三类：中小学课程时间表 ( s c h o o lc o u r s et t m e t a b l i n g ) 、大学课程时间表( u n i v e r s i t yc o u r s e t t m e t a b l i n g ) 和考试时间表( e x a m i n a t i o nt u n e t a b l i n g ) 。 课程表问题求解的时候需要考虑所有的约束条件，并且要满足这些 条件。可以把时间表转化成组合优化问题，即我们所要求的时间表在满足 基本约束条件( 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 研究背景 1 2 1 遗传算法 遗传算法是一种基于生物进化理论发展起来的仿生优化算法。主要 的机理是参照生物进化和遗传的规律，利用复制、交叉和变异等操作，使 优胜者生存，经过每一代的重复同样的操作，最终找到问题的最优解。遗 传算法的特点是群体搜索策略和群体中个体之间的信息交换。具有很强的 鲁棒( r o b u s t ) 性，因此被广泛应用于很多学科和工程领域。 近年来，随着对遗传算法的研究深入，遗传算法越来越多的应用于 各种领域，特别是n p 问题的求解。比如t s p 问题、作业调度问题和图着 色问题。因此遗传算法主要应用于复杂优化问题的求解。 1 2 2 图着色 图的着色问题是现代图论中的一个重要部分，是图匹配和平面图理 论的一个直接应用，无论在理论上还是在工程应用方面都有良好的应用， 诸如电路布线问题、工序问题、时间表资源问题等方面都有直接的应用。 图的着色问题主要包括两种类型，一种是求图的所着色数问题，另外一种 是给定颜色数，要求对图的顶点或边着色。 简单介绍图着色的相关的概念： ( 1 ) 图的匹配：设g 2 是无向无自回路的图，m e 。 如果m 中任意两边均不邻接，则称肘为“的一个匹配。 ( 2 ) 顶点着色：图中任意相邻的点着不同的颜色。 ( 3 ) 图的k 顶点着色：用k 种颜色对图进行顶点着色。 ( 4 ) 图的色数：对图进行顶点着色所需的最少颜色数。 ( 5 ) 边着色：图中任意相邻的边着不同的颜色。 ( 6 ) 图的k 边着色：用k 种颜色对图进行正常边着色。 无论是求解一个图g 的色数五“) 的算法，还是对一个给定的图g 进行顶点着色或者边着色都是一个n p 问题。 1 2 3 本文的主要工作 本文以时间表问题、图的顶点着色和遗传算法为主要研究内容，主 要的工作包括以下几个方面： ( 1 ) 详细介绍了时间表问题的概念。以时间表问题的一个最典型的 例子大学课程表安排为例，介绍了一种基于点着色算法的解决时间表问 题的方法。 ( 2 ) 认真分析排课问题中的各中约束条件，根据这些约束条件，将 排课问题转化成图形问题，从而使求解排课问题转变成求解图顶点着色问 题。在这个阶段，将课程表安排中所需解决的一周课程安排，每天课程安 2 排，教室安排问题转化成对应的三个图形：一周课程图形，每日课程图形， 教室安排图形； ( 3 ) 运用遗传算法，对转换后的图形进行求解，提出了一种分组遗 传算法求解图的顶点着色； ( 4 ) 针对图形着色问题，提出了一个基于排列模型求解该问题的方 法。 2 1排课问题 第2 章文献回顾 排课问题其实是一个在多重限制条件之下，分配出全校的课程安排、 上课时间安排和教室安排的问题。排课问题的复杂主要在于安排过程中所 需要考虑的因素和限制较多。影响排课的因素很多，大致可以分为以下几 个方面：教师集合，课程集合，学生以及教学设施。 s e v e n 在论文( o nt h ec o m p l e x i t yo f t n n e t a b l ea n dm u l t i c o m m o d i t y f l o wp r o b l e m s ) ) 中给出了证明，证明了排课问题是一个n p 完全问题。在 他的论文中讨论的排课问题是一个朴素的数学模型，忽略了很多实际中起 作用的因素，在这个模型的基础上添加新的约束条件。 约束条件又分为硬约束和软约束，硬约束条件是排课过程中必须满 足的，常见的硬约束有： ( 1 ) 一个教室不能同时安排两位以上的教师上课 ( 2 ) 一个教师不能同时上两门课程 ( 3 ) 一个班级不能同时上两门课 ( 4 ) 参加每门课的上课人数不能超过教室的容量 软约束，即希望所采用的排课方案尽可能多的满足的约束，虽然在 不满足这些约束的条件下仍然可以进行排课。常见的软约束有： ( 1 ) 考虑到教学效果，尽量将课程安排在教学效果较好的时段中； ( 2 ) 对于每周课时数较多的课程，将其隔天安排，具有较好的分散 度的课程安排才会有较好的教学效果； ( 3 ) 尽量满足不同老师对上课时段的要求； 基于上面的理论给出排课问题的数学模型i 。为了便于描述，定义 如下的记号： 乞：第聊位教师，删= 1 ，2 ，一- m ； 已：第疗个班级，刀= 1 ，2 ，m ； ：第p 门课程，p 2 1 ，2 ，p ；不同教师上的同一名称的课程 记为两个课程，同一个教师给不同的班级所教授的同- f q 课程也记为两门 课程； ：星期k ： 蚴：第d 个时间段，d = 1 ，2 ，d ； 4 g r ：第r 种教室，= 1 ，2 ，r ，这里按照教室的容量划分教室的 种类； 口( 盔) ：星期k 的时间段数，k - - 1 ，2 ，k ； 鼬) 2 荟粥+ 1 ：星期k 的起始时间段数 ( 毋) ：第，种教室的数量，= 1 , 2 ，r ； y ( j ，) ：第j ，课程每周的上课次数； ：第p 课程所在教室o 。f ，；选修第p 课程的班级的集合。 考虑每个班级上课的时间安排有足够的分散度以及教室资源充分利 用等条件，建立数学模型如下： v 1 ：兰艺以警h 杰玩嘞 屹：兰艺烈”警h 州“1 警驴1 壹。o “一 wdrpf ，、 v 3 = i 兀x t 。c 蚴毋i ( 毋一亿) m i l l ( q v l + 呸吃+ c o s v s ) s t ： 吖pr 厶g r 1 m = l 严lr = l pr n x t m l p cu a g ，1 ，一1r 2 1 “ n x t cu d g , = r q ) j h 5 1d = lr 2 1 。* k l l p 吖凡 兀x t , l p c u d g , ( g , 一吃) o m 爿r = l “ 吖p n x t 。l v c l t d g rs 夕( 晶) m ；lp = 1 “ 5 其中栅2 i ；，等于l 表明教师f 在r 型教室”时间段给班级c 上， 课。一2 扣，等于1 表明教师f 在两个时间蚴和段都有课。式子 一中三个权值的含义是；q 表示同一天中同一门课程重复的次数；( - 0 2 表 示相邻天中同一课程重复的次数；伤表示课程实际安排教室类型与理想 教室的差值总和；式子( 2 ) 表明任一时间内每个班级只能上一门课程； 式子( 3 ) 表示任何时间段内每位教师最多只能上一门课；式子( 4 ) 表示 参加同一门课程的班级可以同时上课；式子( 5 ) 表明上课的人数不能超 过教室的容量；式子( 6 ) 表明所需的教室总数没有超过实际的教室的总数。 2 2排课问题的相关研究 课程表的安排的问题是一个组合问题，求解难度很高。不管是小学 生的课程安排还是大学课程表安排，由于组合的情况很多，需要考虑的因 素也很多，各种软硬约束的情况也不尽相同，因此，单纯的穷举法或者贪 婪搜索方法都不可能找到优秀的解。因此国内外的众多学者对之进行了深 入的研究，提出了各种不同的解法目前求解的方法主要有三类：整数规划 算法( i n t e g e rp r o g r a m m i n g ) 、基于图论的算法( 图的顶点着色，二分图) 、 启发式算法。下面就这些现阶段主要的方法进行介绍。 整数规划方法：排课问题中最重要的两个观念为：一个教师在某一 个时段中只能教授一个班级；一间教室在某一个时段中只能容许一个班级 上课。在数学规划中的体现就是属于0 1 整数规划。相关研究中， m u l v e y ( 1 9 8 2 )u c l a 管理研究所作为其分析对象，利用整数规划中的 0 1 规划，建立数学模型分析排课问题。 目标函数：一个班级只能被派到一个时段中，其教室座位使用率最 高。限制条件包括：一个班级只能被派到一个时段，修课学生需小于教室 内座椅数，一个教师教授一个班级、一个学生集合指派一个班级。 w e r r a ( 1 9 8 5 ) ，利用o 1 整数规划对排课问题作了一个概念性的描述，目标 函数为当一课程被指派到某一时段的有利条件( 如教师对授课时间的偏 6 好) ，并且利用松弛法求解问题，将某些约束松弛之后加入目标函数中， 使排课问题转化成一种容量限制的运输问题，再利用相关方法求出近似最 优解。 g l e s s e y 和m i z r a e h ( 1 9 8 6 ) 以o 1 规划，考虑更详细的因素，目标 函数为步行距离最短、剩余座位数最少以及教学设施之间的置率最低；限 制条件为每一课程都必须指派至一间教室、同时间同一间教室不能安排两 种课程，利用一种启发式算法，快速求得近似解，求出的结果需要人工调 整。 基于图论的算法：图论( g r a p ht h e o r y ) 在排课问题上的应用相当广 泛，将排课问题的相关影响因素转换成图形表示，再利用相关解法进行求 解。图论中的着色理论在排课问题的求解上的效果不错。w e r r a ( 1 9 8 5 ) 利用图着色理论处理排课问题，假设教师与课程满足每个限制，并且证明 问题有解。此外，w e r r a 对点着色与边着色研究，证明当排课问题限制很 多时，点着色比较适合。马允宜( 1 9 9 4 ) 探讨了图与图着色在计算机辅助 排课表中的应用。吴金荣( 2 0 0 2 ) 利用图着色理论提出了一种解决该类问 题的方法。何永太( 2 0 0 3 ) 利用了二部图结构构造数学模型，解决教师和 班级分组问题的算法。 启发式算法：由于排课问题属于n p - c , o m p l e t e 问题，在求解上找寻 最佳解不容易，所以有许多学者利用相关启发式算法来求解此问题。李增 智( 2 0 0 3 ) 提出了一种混合模拟退火算法，分两个阶段解决课程表问题： 第一阶段采用基于概率论的启发式算法，利用基于概率论的启发式算法排 出每个班每门课每天上几节，可得到多种排法，采用启发式方法，排出每 个班每天每一节上什么课，可得到多个不同的课表。第二阶段运用模拟退 火算法，进行进一步的优化。使其尽可能满足所有约束条件。郑月锋( 2 0 0 6 ) 对普通遗传算法进行改进，通过线性加权法将各目标优化函数进行整合转 化成为单目标优化问题，对排课问题进行求解。 2 3图着色方法 图着色方法是图论中的一个重要的课题。很多数学家都在研究图的 7 着色问题，期望能够解决这个问题。在图着色问题中，最著名的就是由 e g u t h d e 于1 8 5 2 年提出的“四色问题”，该问题直到1 9 7 6 年才由k a p p e l 和w h a k e n 两位数学家合力解决。 决定一个图形的最小着色的颜色数的问题是一个n p - c o m p l e t e 问题， 随着所求问题规模的增大，求解的时间的增长呈现指数级数增长。现在， 很多研究者尝试用启发式算法去求解该问题【2 j 。 图形着色的理论涉及很多方面，最基本的两个就是“点着色”和“边 着色”问题。边着色就是让图形的每一条边涂上一种颜色，遵守的准则是 相邻边的颜色不同。边着色问题和点着色问题在很多方面都是类似的。对 于一个图形来说，每个图形都会有一种边着色；对一个图形使用k 种颜 色进行边着色，那就可以使用k + 1 种颜色进行边着色。 图着色的应用现在很受人们重视。目前图着色在很多领域得到了广 泛的应用。下面介绍图着色的几个重要的应用： 1 贮藏问题：某工厂生产刀种化学制品q ，巳，一嵋一，其中，若有些制 品存放在一起，会有安全隐患，作为一种预防措施，工厂必须将它们分开 存放，也就是将仓库分成若干个隔间，以便把不相容的制品存放在不同的 隔间里面。对此，构造一个简单无向图u 2l p ，e j ，其中 y ( g ) 2 如，c 2 ，c 。) ，e 【c ，0 ) 等价于化学制品q 和巳互不相容，由此 可以得到仓库的最小隔问数等于图的色数。 2 电视频道问题：某地区有珂家电视发射台1 1 ，j 2 ，1 一，主管部门为 每家电视台分配一个频道，同一频道的发射台之间的距离必须大于指定的 正数d ，我们构造一个无向图g = ( y ，e ) ，y ( g ) = 五，五) ，e ( 互，乃) 等价于1 - 与之间的距离小于d ，由此我们可以得到所需的频道数目。 3 考试安排问题：某高校有，l 门选修课程，”2 ，现在需要进行 期末考试安排。限定条件：同一位学生在同一天里不能参加两门课程的考 试。这是一个简单的时间表问题。现在问考试需要安排几天。构造无向图 g 2 ( 矿，e ) ，点，) 等价于课程v i 和课程同时被一名同学选中。考 试的最小天数为图的最小颜色数。 最后一个应用就是一个时间表问题的例子。因此，排课问题可以归 结为图形着色，然后利用一些启发式智能算法对所获得的图形进行求解。 目前求解图的顶点着色的方法主要有以下几种： 1 贪婪算法( g r e e d ya l g o r i t h m ) 1 3 1 ：为顺序着色算法( s e q u e n t i a l a l g o r i t h m ) 。贪婪算法依次从预先排好序的顶点序列中取出一个顶点，用 已经使用过的颜色对他进行着色。换句话说，就是试着把它加进已有的分 8 类中去。如果不能用已有的颜色对它进行着色，就分配一个新的颜色，形 成一个新的分类。贪婪算法有很多变种，主要有：s i m p l eg r e e d y 、l a r g e s t f i r s tg r c e d y 、s m a l l e s tf i r s tg r e e d y 、r a n d o ms e q u e n t i a lg r e e d y 、r e v 盯s e o r d e rg r e e d y 、s t i rc o l o r g r e e d y 。 s i m p l eg r e e d y 算法的执行过程如下： 1 ) 扛1 ： 2 ) c = 1 3 ) 若对砂( ) ，万抄) c ，则令万( ) 2 c ，转第5 步； 4 ) c 2 c + l ，转步骤3 ； 5 ) 若l 0 ) 或减少 ( c 0 ) = 五，厶) ，有以下定理：在只有选 择算子的情况下，染色体日的极限概率为： p * i h ) 2 卿- 暇j 5 0 枷，日h 手二 ( 4 ) 这一类算子虽然得到了广泛的应用，但是仍然有不合理之处：( 1 ) 要求适应值函数大于零，对于实际的目标函数，其值域无法预知，从而无 法事先确定能使函数值为正的转换函数，并且转换函数的选择对算法性能 也有很大影响；( 2 ) 是导致过早收敛至局部解的一个重要原因，在基于适 应值比例的选择下，一个具有很高适应值的个体很容易大量繁殖，而其他 个体被淘汰，这时参加交叉运算的两个个体相同的可能性很大，从而导致 过早收敛至局部解；( 3 ) 如果群体中各个染色体的适应值相差不大，则它 们后代的个数也会基本相同，好的个体得不到更不多繁殖的机会，从而使 得算法的速度更慢。 2 这类选择算子不要求适应值函数一定要大于零，并且既可以求适 应值函数最大值，也可以求适应值函数最小值问题。基本过程如下： ( 1 ) 从上一代群体中等概率选取q 个染色体； ( 2 ) 在这q 个染色体中选择最好的( 可以是适应值最大的，也可以 是最小的) 放入下一代群体中； ( 3 ) 重复以上各步，直至新的一代群体中也包含川个染色体。 对于这种选择算子，一个染色体被选择的概率只能取决于它在群体 中的大小顺序，该染色体适应值比其他染色体大多少或者小多少不会影响 其后代数量，从而在一定程度上避免了经过选择后染色体过于集中的情 况。 设群体规模为川，不妨将这川个染色体按适应值从优到劣的顺序排 列为五，吒，h ，从这个染色体中等概率抽取g 个，不允许重复，可 能的情况共有l 膏+ r 1 种，在这g 个个体中选择最优的个体，则以是最优 个体的情况等价于在吒，吒- l ，h 中，这一 一1 ) 个染色体中等概率 抽取日一1 个，然后再加上，这样可能的情况共有。一1 t 一一卜1 种，从而 ，口i 懈在一为：帖警2 等 ( 5 ) ，如此重复次，得到个染色体作为下一代，在这些后代中，故 的个数期望值为行“所( ) = n + p ( x k ) ( 6 ) 。可以看到这种选择算子与染 序庀有关，而该染色体适应值比群体适应值大或者小并没有联系，这样就 避免了如果某一染色体适应值过高而导致下一代中该染色体过多的情况， 也避免了群体中各个染色体适应值相差不大而导致优秀个体得不到足够 的后代的情况。 这种选择算子既能够使好的个体得到较多的繁殖的机会，又能防止 其繁殖过多的个体。所以该选择算子更具有合理性，同时在使用过程中， 可以根据当前群体的具体情况，适当调整g 的取值，从而影响染色体后代 的个数，因而这种选择算子更具有一定的灵活性。 三、交叉算子： 定义( 交叉算子) ：设m = 2 ，一个随机映射c ：础哼碟称 为一个交叉算子，如果它满足 ( 1 ) 对任何最优种群有p 门( c ( x ) ) = ) o ： ( 2 ) 对任何齐次种群 x 】u 有p c ( 【x 】) = 【x b2 1 。 交叉操作是遗传算法中的核心操作。通过交叉，遗传算法的搜索能 力能够得到很大的提高。下图是简单遗传算法( s g a ) 中交叉算子的示意 图： 。，二 o 交换两个个体的后半部分，得到两个新个体，任取两 个个体之一为杂交结果。例如，取见2 1 ，交叉点为k ( k = 1 ，) 并取 交叉后的第一个个体为交叉结果，则对母体( 爿，口) 实施杂交操作过程如下 1 9 所示： a = a l a 2 a k i a k + l a l b = 6 1 6 2 钆；钆钆 c ( a ，b ) = q 吃q + l ( 2 ) 多点交叉( m u l t i - p o i n tc r o s s o v e r ) ：首先在母体对的基因串中 随机设置多个交叉点，然后依照一定的概率在交叉点所分隔的基因段中进 行段交换。例如两点杂交是将母体的基因串分成三部分，交换中间部分， 即为杂交结果。 ( 3 ) 均匀交叉( u n i f o r mc r o s s o v e r ) ：是指对母体对中的每一基因都 以相同的交叉概率进行交换，从而形成新个体的操作。 ( 4 ) 算术交叉( a r i t h m e t i cg l - o s s o v l ) 是指由两个个体的某种线性 组合生成新个体的繁殖操作，一般用于实数编码。例如，可设 c ( 置，五) 2 五+ ( 1 一) 五，【o ，l 】取为随机数时称为凸组合交 _ f 扣l ，( 玉净f ( 以) 叉，而取p i f o ，( 玉f ，( 也时称为线性交叉。 四、变异算子： 定义( 变异算子) ：一个随机映射m ：磁专钟称为是一个变异 算子( m u t a t i o no p e m l d r ) ，如果对任何种群x e 卅， p m ( x ) n b 1 2 j 0 、 变异算子的作用方式是：独立地分别作用于种群x 上的每一个个体 置，以某种概率方式生成变异后的个体m ( 置) ，从而 m ( x ) = ( m ( 五) ，m ( 五) ，m ( 以” 以下列举几种常见的变异方法： ( 1 ) 点变异( p o i n t m u t a t i o n ) ：设x 2 q 口2 q 吼是一个个体， r 为等位基因，口j l 。点变异是指以某一概率独立地改变x 的各位基 因取值的进化操作( 生物上模拟基因突变) 。例如，对于二进制编码 r 2 o ，1 i ，指定一个变异概率己 o ，贝t j m ( x ) = 6 1 6 2 钆吼定义 为p 岛2 q ) = 1 - 已，p 6 j = 1 一q ) = 已( 即改变的概率是名，不改 变的概率是1 一己) 。所以，如定义】，= 包6 2 既吼为任一个体，则 尸 m ( x ) = y = ( 1 一只) l - d ( x y ) e m 4 j ，其中d ( x ，y ) 表示个体x 与 y 有不同基因的位数，即哈明( h a m m i n g ) 距离。 ( 2 ) 均匀变异( u n i f o r mm u t a t i o n ) ：它分别用等位基因i 内的均匀 分布的随机数，以某一较小概率1 m 来替代个体编码串各个基因座上的原 有基因值。 ( 3 ) 正态变异：用于实数编码，是用服从正态分布的随机数 ( 置，盯) 代替原基因置的变换。例如，正像演化策略( e s ) 中所使用的 那样，取髟2 置+ ( 0 ，盯) ，正态变异通常被用作局部搜索( 盯较小时) ， 其作用与均匀变异有显著不同( 均匀变异的作用是在搜索空间中自由移 动，从而增加种群多样性) 。 ( 4 ) 非一敏耍异( n o n - u n i f o r mm u t a t i o n ) ：是一种强化局部搜索， 而且强调作用随演化过程调整的变异操作。f a x ( t ) 5 五屯h 是s e a 在f 代所产生的一个个体，薯【口j ，b 1 】，则非一致变异作用于x ( f ) 所产 生的变异个体y ( f ) = m x ( t ) 2m 耽蜘定义为： 乃2 ：篙2 ：器笔：矧暑，式中r a n d o m ( o ，1 是( o ，1 ) 之内的随机数，一i 而一( 屿一1 加础m ( o - l m ，式中，l j 是【u ，l j 之内的随机数， a ( t ，) ，) o ，y 】是服从均匀分布的一个随机数，要求随着进化代数f 的增 加，a ( t ，力单调减且趋于零。例如a ( t ，y ) 可按照下式定义： a ( t ，y ) = y + ( 1 _ r o - t r ) ) ，其中r 为【o ，1 】内符合均匀分布的一个随机数， r 是最大进化代数，6 是一个可调参数，它决定了随机扰动对进化代数f 的 依赖程度。 五、适应度度量： 遗传算法中的适应度代表了一个全局最优解的可接受程度，是遗传 算法评价和选择个体的度量依据。 定义( 适应度) ：吼上的一个适应度是一个映射厂：吼一对。 适应度度量的确定通常应该反映应用者对个体( 候选解) 的评价标 准和搜索原理。例如说在t 代。为了避免对质量不高解重复控索，我们可 2 1 以_ 应月j i 舌应度：以( 彳) 2 ；：嚣啦掣，这里碰表示在讯之前记录的 最高个体适应值。 常见的适应度函数有以下几种： ( 1 ) 直接以待求解的目标函数的转化为适应度函数，也就是：若目 标函数为最大化问题，f i t ( f ( x ) ) = 厂( 川，若目标函数为最小问题， f i t ( f ( x ) ) = 一( z ) 这种适应度函数简单直观，但是存在两个问题，其一 是可能不满足常用的轮盘赌选择中概率非负的要求：其二是某些代求解的 函数在函数值分布上相差很大，由此得到的平均适应度可能不利于种群的 平均性能。 ( 2 ) 若目标函数为最小问题，则f i t ( f ( 工) ) 2 9 囊n 7 z 卜c 叫， 其中g 。为，( x ) 的最大值估计。若目标函数为最大问题，则 f i t ( f ( 石) ) 2 ；：j x p c 脚，式中c m 为厂( x ) 的最小值估计。这种 方法是对第一种方法的改进，可以称为“界限构造法”，但有时存在界限 值预先估计困难、不可能精确的问题。 (3) 若目标函数为 最 小问 题 即( m ) ) = 而1两c o ，c + 朋) o 。若目标函数为最大问 题砌m ”= 而c 巩c 一似邳。这种方法与第二种 方法相似，c 为目标函数界限的保守估计值。 3 2 3 本章小结 本章首先重点介绍了图形着色的原理，在此之后，重点介绍了遗传 算法的发展历史和它的一些理论基础。根据图形着色理论的特点，可知该 理论非常适合于时间表问题的求解，由于图形着色理论本身就是一个n p 问题，所以我们需要一个比较优化的算法来对其进行求解，遗传算法在这 方面有着非常好的性能，所以采取了遗传算法来对所建立的模型进行求 解。 第4 章排课问题的求解 4 1着色理论应用于排课问题 4 1 1 排课中的点着色 若将排课问题以图形“来表示，其顶点有时段、班级、教师及课程 所组成，由点着色的观念，如果顶点间彼此有冲突，如同一个教师不能在 相同的时间内同时上两门课程；同一个班级的课程不能安排在同一个时间 段内，就将这两个顶点作为相邻的顶点。根据图形着色理论，相邻的顶点 不能有相同的颜色。图4 1 就是这样的一个例子。 节点由两种组成：一种是时间段节点，一种是课程节点。时间段节 点中含有数字，该数字代表是第几节课。课程节点包含了字母和数字，字 母表明了这是一节什么课，数字表明该课的时间段。遵照排课的准则，相 同的课程不能安排在同一时间段内，所以m 1 和m 2 这两个节点要有边相 连。如果时间段节点和课程节点有边相连，则说明该课程不能安排在这个 时间段内。所以e 1 因为时间问题不能安排在三四节，e l 节点和3 、4 节 点有边相连。根据以上的分析，我们能够创建如图4 _ 1 所示的图形。对该 图形进行求解，所得出的一个可行解如图4 - 2 所示。 图4 - l 简单捧课问题的图形g 图4 - 2 图g 的一个可行解 从图4 2 中得出一个简单的排课结果。语文安排在第二节课，数学 安排在三四节课，英语安排在一二节课。 4 1 2 排课问题图形化 进行课程安排的关键就是将课程安排图形化。将整个排课的流程转 换成一个图形g2 【，丘：) ，图中的顶点代表着色的单位( 课程、时间段和 教室) ，节点相互之间有冲突，就把这两个节点之间以边相连，利用点着 色原理进行求解。一般来说，学校安排课程都是从星期一到星期五，每天 从早上8 点钟开始。在研究的时候，将整体排课分成三个部分，教室图形， 周图形，日图形。 一周课程图形； 建立周图形是为了将教师的所有课程安排到整个星期课表中。在周 图形中包含两类节点：星期节点和教师节点。星期节点集合包含星期一到 星期五总共五个节点。在教师节点集合中包含了每个教师所有的课程节 点。对于教师的课程节点，我们作如下的处理：如有一个教师，有一个三 学分的课程，我们将该课程分割成2 小时和1 小时，分在两天上课，因此 课程要以两个节点表示，并且这两个节点要是楣邻节点，表示不能在同一 天上课。如图禾3 所示。 图4 - 3 分割后的课握 在点着色的时候，如果两个节点存在着互斥情形，这两个节点以边 相连，说明这两个节点不可同时存在，因此在周图形中，如果教师无法于 某一天上课，则将该日节点与该教师集合以边相连。根据此得到如4 - 4 所 示的图形。 倒“周图形 图中1 - 5 节点表示星期- n 星期五，矩形框内表示教师集合，说明 某一个老师的待排课程。课程节点的表示方式，m 0 9 0 1 代表课程编号， 数字3 表示上课的节数。由图可知，教师集合t l 与星期一和星期二节点 相连，说明该教师所教授的课程不能安排在星期一和星期二。教师集合 1 r 2 中由于m 0 1 8 1 分成两学分以及一个学分来上，所以该课程要排入不同 的两天。我们运用点着色的方法，可以将教师集合中所有的课程排入每一 天中。 二、每日课程图形： 在周排课阶段，利用周图形将所有课程排入整个星期后，得到了每 天的所有课程，接下来的任务就是把每天的课程安排到适当的节次中。 日图形中的节点包括节次节点和课程节点两种，节次节点是每日的 上课节点，包括从早上到晚上的所有课程安排。课程节点就是需要安排的 所有课程。如果某个课程需要三个小时以上，设计的时候以三个节