（计算数学专业论文）自适应遗传算子解决排课问题的研究.pdf

内蒙古大学硕士学位论文 摘要 现代科学理论研究与实践中存在大量与组合优化、自适应等相关的 问题。使用常规方法解决这些问题，除了一些简单的情况之外，人们对 于大型复杂系统的优化和自适应问题显得无能为力。遗传算法借鉴生物 界自然选择和自然遗传机制，使用群体搜索技术，尤其适用于处理传统 搜索方法难以解决的复杂的和非线形的问题。经过近4 0 年的发展，遗传 算法在理论研究与实际应用中取得了巨大的成功，但相对其鲜明的生物 基础，其数学基础还是相对不完善的。 摘要排课问题是典型的多重约束和组合优化问题，并且早在7 0 年代 已经被证明是一个n p 完全问题。遗传算法是一种借鉴生物界自然选择和 进化机制发展起来的自适应随机搜索算法。它具有良好的并行性、通用 性、稳定性，是一种比较有效的解决n p 完全问题的方法。本文将遗传算 法应用于求解排课问题，主要进行了以下几个方面研究工作：首先，系 统分析了排课问题的各要素及多重约束条件，提出了排课问题的求解难 点和优化目标。其次，着重分析比较常用的遗传算法编码方案并研究其 在排课系统中的应用，在综合各种编码方案优缺点基础上，设计了一种 更适合解决排课问题的编码方案。较之传统编码方案，该编码方案更简 单、更高效、更易于理解。并且，根据设计的编码方案，重新设计了与 之对应的交叉算子和变异算子。 关键词：排课问题，遗传算法，编码方案，多重约束 s elf a d a p t a t io ng e n e t icg e n e t ico p e r a t o r st os o l v e c u r ric u l u ms c h e d u l in gp r o b l e m p d b s t r a c t t l l e r ea r es t i l l m a n yi s s u e st ob et a c k l e dw i t hi nm o d e r ns c i e n t i f i c t h e o 巧r e s e a r c ha n dp r a c t i c e ，w i t hr e g a r dt oc o m b m a t i o n o p t i n 此a t i o na l l d s e l f - a d a p t a t i o ne t c r o u t i n em e t h o d s o p t i m i z a t i o n a n d s e l f - a d a p t a t i o n a r e q u i t e h e l p f u lr e s o l v i n g s i m p l e p r o b l e m s b u t h e l p l e s s f o r c o m p l i c a t e d l a 唱e - s e a l es y s t e m s g e n e t i ca l g 。r i t h m s ；b a s e do nt h e b 。i o l o g i c a l m e c h a n i s m 。fn a i u r a ls e l e c t i o n & h e r e d i t y a n dl e v e r a g i n gc 。1 。n ys e a r 龇g t e c h n o l o g y , i s p a r t i c u l a r l y a p p l i c a b l e f o r t h e r e s o l u t i o n0 f c 。m p l i c a t e d & n o n - l i n e a r p r o b l e m si n t r a c t a b l ew i t h t r a d i t i 。n a l e a r c h i n g m e t h o d s f o rn e a r l y4 0 y e a r s ，d e v e l o p m e n t ，g e n e t i c 触g o r i t h m sh a sm a d e g r e a ta c h i e v e m e n t s i n b o t h t h e o r y r e s e a r c h a p p l i c a t i o n s h o w e v e r , i t sm a t h e m a t i c a l f o u n d a t i o ni s s t i l l m p a r c dw i t ht h e d i s t i n c t i v ea n ds o u n d b i o l o g i cf o u n d a t i o n c u r r i c u l u m s c h e d u l i n g p r o b l e m i sa a n d p r a c t i c a l i n c o m p l e t e t y p i c a l p r o b l e m a b o u t m u l t l 一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 np r o v e dt o b e a n o n d e t e r m i n i s t i c p o l y n o m i a l c o m p l e t e d( n p c ) p r o b l e mi nc h e 1 9 7 0 s t h e g e n e t i c a 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 f n a u r a ls e l e c t i o n & h e r e d i t y , i sa na d a p t i v ea n d s t o c h a s t i cs e a r c ha l g o r i t h m i t c a nb e h i g h l yi m p l e m e n t e di n p a r a l l e l f o r t h es t a b i l i t ya n d g e n e r a l i t y0 f g a g ai 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 i n t l l i sp a p c f 3 内蒙古大学硕士学位论文 g e n e t i ca l g o f i t h m ( g a ) i sa p p l i e dt os o l v ec u r r i c u l u ms c h e d u l i n gf o ra u n i v e r s i t y t h e m a i nw o r k sa s f o l l o w s ：f i r s t l y ，a l l k i n d so f p o t e n t i a l f a c t o r s ，m u l t i r e s t r i c t i o n s o fc u r r i c u l u m s c h e d u l i n gp r o b l e m a r e d i s c u s s e d w h a t 。sm o r e ，t h ed i f f i c u l t i e st or e s o l v et h ec u r r i c u l u ms c h e d u l i n g p r o b l e ma n dt h eo p t i m a lo b j e c ta r er e p r e s e n t e d ，a n dt h em a t h e m a t i cm o d e l a b o u tc u r r i c u l u ms c h e d u l i n gp r o b l e mi sd e s i g n e d s e c o n d l y ，s o m ec l a s s i cg a c o d i n gs c h e m e s ，a s w e l la st h e i r a p p l i c a t i o n s i nc u r r i c u l u m s c h e d u l i n g s y s t e ma r ea n a l y z e da n dc o m p a r e di nd e t a i l s b a s e do nt h es t u d i e sa b o u ta l l c o d i n gs c h e m e s s t r e n g t h sa n dw e a k n e s s e s ，a ni m p r o v e dg e n e t i ca l g o r i t h mf o r s o l v i n gc u r r i c u l u ms c h e d u l i n gp r o b l e m si sp r o p o s e d c o m p a r e dt ot r a d i t i o n a l c o d i n gs c h e m e s ，t h i s s c h e m ei s s i m p l e r , m o r e e f f e c t i v ea n de a s i e rt o u n d e r s t a n d m e a n w h i l e ，t h ec r o s sa n dm u t a t i o ng e n e t i co p e r a t i o n sa r ea l l c o m p r e h e n s i b l yr e d e s i g n e dt oc o r r e s p o n dt ot h i sc o d es c h e m e k e y w o r d s ： c u r r i c u l u ms c h e d u 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 o d i n gs c h e m e s ， m u l t i - c o n s t r a i n t s ； 4 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已 经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得内墓直盔堂及 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 学位论文作者签名：鱼望盏指导教师签名：壁主垄 日期：2 塑丑! ! 竺 日期：趔幺笸。丛 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的全 部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行检索， 也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作者在学期 间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古 大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名：逝 日 期： 群堑! 尘 指导袅师签名：垒主盔 e t 期：迎z 笸，尘 内蒙古大学硕士学位论文 第一章引言 1 1 排课问题背景及研究意义 课程表是一个学校日常教学工作和其他各项活动的指挥调度表。它不仅是学生 和教师上课的依据，而且对学校其他工作的统一安排也有直接影响。利用计算机辅 助手段编排课表，是教学管理实现科学化、现代化的重要研究课题之一。随着招生 规模逐年的扩大，以及计算机在教学工作中的普及应用，用计算机代替劳动强度大、 工作效率低的手工排课工作，越来越成为教学管理中迫切需要解决的研究课题之一。 然而排课问题作为高校教学工作过程中必须面对的问题，也是运筹学中研究的一个 问题时间表问题( t i m e t a b l e p r o b l e m s ，简记t t p s ) ，它已经被深入细致地研究并被 公认是n p 难解问题。由于排课问题本身的复杂性和难解性，使其一直没有得到有效 的解决。本文便是在上述的背景下展开工作的，在研究和实践的过程中，结合实际 排课问题中的一些常见约束条件和优化目标，摒弃了传统的编码方式，提出了针对 排课问题的一种特殊的编码方式，把遗传算法应用于排课问题中，用来优化排课方 案。 1 2 排课问题数学描述 1 2 1 定义集合： 定义教师集合尸= 扫。，p ：，p 朋) ；p n 为教师总数。 定义课程集合s = s 。，j ：，s 。 ；s n 为课程总数。( 不同班级的同名称课程认 作不同课程) 。 定义授课班集合c = c 。，c ：，c 。 ；印为班级总数。 定义教室集合尺= 饥，r 2 ，_ ) ；埘为教室总数。 6 内蒙古大学硕士学位论文 定义时间片集合丁= 饥，f ：，t 加) ，t n 表示一周可用的时间片总数，若一周上 五天课，每天上4 节课则t n = 5 4 = 2 0 时间片。 定义集合m ；s p c 是课程、教师、班级的笛卡尔乘积。称它的元素为课元。 定义一个课元是一个三元组o ，p ，c ) 一i e m ，该课元的课程是s e s ，教师是 p e p ，班级是c e c 。 定义课元集合是l = p 。，z ：，l n ) m ，是需要安排时间和教室的全部课元，其 总数是i n 。( 我们排课时是以时间片为单位，对一周四学时的课，就有两个相同的 课元) 定义教师a 要求的排课时间集合是码= f l 。，t t ：，】t ，若没有特定的时间要 求贝0z 弓= t ，f = 1 2 ，p n 。 定义班级c 。要求的排课时间集合是t c i = 戗。，：，t ，若没有特定的时间要 求则玛= t ，i = 1 , 2 ，册。 定义课程墨要求的教室集合是p s i = 饥。，吒：， 尺，若没有特定的教室要求则 胚。一尺，f = 1 ，2 ，s n 。这是课程对教室的要求，比如多媒体教室、实验室等。 定义班级c 。要求的教室集合是r c i = ，：， r ，若没有特定的教室要求则 r c ，= r ，i = 1 , 2 ，c ，l 。这是班级人数对教室的要求。 1 2 2 定义函数： 函数疋( ，) 定义为取课元i e l 的上课班级；e u ) = c e c 。 函数c ( ，) 定义为取课元i e l 的上课课程；e u ) = s e s 。 函数( f ) 定义为取课元f l 的上课教师；c ( z ) = p p 。 函数g t ( p ) 定义为取教师p p 的特定时间要求的集合；l ( p ) z 。 函数瓦( c ) 定义为取班级c e c 的特定时间要求的集合；瓦( c ) g r 。 函数巳o ) 定义为取课程s e s 的特定教室要求的集合；瓦o ) r 。 函数匕( c ) 定义为取班级c e c 的特定教室要求的集合；c ( c ) r 。 7 内蒙古大学硕士学位论文 1 2 3 数学描述： 定义集合n t x r = o 。，) ，( f 。，r 2 ) ，( f m ，) 是时间与教室的笛卡尔乘积，其 元素( f ，) 是由时间与教室组成的时间一教室对。记n = i i 表示时间一教室对的总数。 集合可以看作一个二维表，排课问题就是将课元合理的安排到二维表中，也 即求课元集合到的幂集2 的一个映射q ：l 一2 ，并且满足若干约束。 。群 滢r 1r 2f 3 i r m 时间 t 1 t 2 t 3 t 如 图1 1 集合 设：对任意的课元j l ，z e l ，课元f 分配时间一教室对是( ，) = ( f ，r ) ，课元f 分配时间一教室对是c o ( 1 ) = o ，) ，其中f ，t 丁，r e r 。 显然当z ，时，应该有( f ，) 一( f ，厂，) 。 满足如下约束： i 、教师和班级的一类时间约束： 若：( 1 ) 一u ，) ，则f f 。当任意两个课元教师相同时，不能安排同一时 间片。 若：e ( z ) = f o ( 1 ) ，则t t 。当任意两个课元班级相同时，不能安排同一时 间片。 设：对任意的课元i e l ，课元f 分配时间一教室对是( z ) = ( f ，) ，其中te t ， r 尺。 i i 、课程和班级的一类教室约束： r e ( 只( z ”。教室应该满足课元中课程对教室的要求。 8 内蒙古大学硕士学位论文 r e 兄( c u ) ) 。教室应该满足课元中班级对教室( 人数) 的要求。 i i i 、教师和班级的二类时间约束： f 限( ，) ) 。时间片应该满足课元中教师对时间片的要求。 f 瓦( f o u ) ) 。时间片应该满足课元中班级对时间片的要求。 i v 、软约束： 若e u ) = c ( f ) ，且t ( z ) = 只( z ) 则i t t l 4 ( 本文中一天上四节大课) 同一班级的同- i i 课尽量安排的分散些 若c u ) 一cu ) ，且c u ) = c u )则r 一，同一班级的同一门课尽量安排 在同一个教室 我们定义： 称违反一类教师时间约束的，为一类教师时间冲突。 称违反一类班级时间约束的，为一类班级时间冲突。 称违反一类班级教室约束的，为一类班级教室冲突。 称违反一类课程教室约束的，为一类课程教室冲突。 称违反二类教师时间约束的，为二类教师时间冲突。 称违反二类班级时间约束的，为二类班级时间冲突。 称违反软约束的，为三类课程的软冲突 第一类冲突：对于冲突类型、，要绝对避免，若它们冲突，课表是不 可行的。 第二类冲突：对于冲突类型、我们应尽量避免，考虑排课的人性化，就是说有 特定要求的尽量给于满足，、我们称之为第二类冲突。 第三类冲突：对于冲突类型、，我们也应尽量避免，尽量考虑课表的合理性， ，、我们称之为第三类冲突。引进第三类冲突实际是让课表满 足一些经验常识，还有许多经验常识如：重要的课程尽量安排在好 的教学时间点( 如上午比下午好) ，安排到教室中的人数应尽量和教 室的大小稳合，有利于资源合理利用，另外如果学校有多个校区， 尽量把一个班级或老师的课安排到一个校区等等。 内蒙古大学硕士学位论文 1 2 4 数学模型 定义： x 独= 1 表示i 时间，j 教室安排k 课元，其余情况x 独= 0 1 ) 善荟x 班暑1 ，k - - 1 , 2 i n 一个课季当且仅当安排一次。 2 荟x 驰s 1 ，f = 1 ，2 一细 _ = 1 ，2 朋，一个时间- 教室对最多安排一个课元。 3 荟澎独s 1 “- 1 ，2 砌朋- 1 ，2 ，”朋，卟刻稚叶时间片最皴排一个 课程。这是一类教师时间约束。 4 荟e 磊j 耻s 1 f ；1 , 2 i , m = 1 2 ，册，一个班级在一个时间片最多安排一个 课程。这是类班级时间约束。 5 ) x 独= 0 诺e ( 只( ) ) v ，喏l ( c ( 厶) ) ，这是课程和班级的一类教室约束。 定义： v l ；yyyx 潞 这是违反教师和班级的二类时间约束的个数。 自匀罐( ( ，i 触渔( 厶) ) 小苫b 吲删磊急m 妇坩0 其中“堤课元气的时间片这是违反 软约束的个数。 小荟k m ( f i 卜戤孙佻州- ，j 其札，是课础h 的教室这是违反软 约束( 百) 的个数。 目标函数是： r a i nw l 宰v l + w 2 宰v 24 - w 3 幸v 3 相应约束条件1 ) 5 ) 以，w 2 ，w 3 为相应的权重 1 3 排课问题研究现状 1 0 内蒙古大学硕士学位论文 2 0 世纪5 0 年代末，国外就有人开始研究课表编排问题。1 9 7 6 年s e v e n 在论文 “o nn ec o m p l e x i t yo ft i m e t a b l ea n dm u l t i c o m m o d i t yf l o wp r o b l e m s ”【1 】中，第一 次证明了时间表问题是n p 完全问题，正式确立了时间表问题的学术地位，把对时 间表制定的复杂性认识提高到了理论高度。这虽然回答了计算机制定时间表在实践 中遇到困难的原因，但同时等于宣布计算机编排时间表问题无法实现，因为现代计 算机尚未找到解决n p 完全问题的多项式算法。进入2 0 世纪9 0 年代，进入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 2 j j h 拿大m o n t r e a l 大学的 j e a n a u b i n 和j a c q u e s a f e r l a n d 以及c h a r l e sf l e u t e n t 等都对时间表问题进行了研究。 j a c q u e sa f e d a n d 等人把排课表问题分成两个子问题：时间表问题和分组问题。在 时间表问题中，根据学生注册情况、教师和教室的可利用情况形成一个主时间表。 对于选课人数较多的课程，一个星期要分成几个时间段来上，分组问题就是将学生 分给各个时间段。两个问题相关联，通过惩罚因子来构造启发函数。他们研制的 s a p h i r 课程调度决策系统分为数据处理、自动优化、交互优化等几个模块，该系 统解决矛盾的主要方法也是采用多重课组，这与西方的教学管理体制是不可分的。 另外一批学者还将模拟退火算法( s i m u l a t e da n n e a l i n g ) 应用到时间表问题的研究中 【3 ，4 1 。模拟退火算3 法是r k p a t r i c k 等人于1 9 8 3 年首次提出的，它是人们从自然 界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退火算法用 于求解优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题之间的 相似性。在对固体物质进行退火处理时，常常先将它加温使其粒子可自由运动，以 后随着温度的逐渐下降，粒子逐渐形成低能态晶格，若在凝结点附近的温度下降速 率足够慢，则固体物质定会形成最低能量的基态，优化问题也存在类似过程。模拟 退火算法被用来解决许多实际应用中优化问题，取得了不错的效果，但用其解决排 课问题，现在仍处在模型实验阶段，还有许多问题需要解决。 9 0 年代初期，c o l o m i 【s l 等人首先尝试应用遗传算法来解决排课问题，引进了矩 阵表方案及相应的交叉、变异算子。b u r k e l 6 l 对将进化算法分阶段用于排课问题做了 初步的研究，得到一些颇有价值的成果。c h upc 和b e a s l e y 对一般的排课问题使用 了遗传算法进行求解【7 1 ，他们着重于遗传算法的全局最优解的搜索能力。日本的 s i g e r u 用具有控制约束的遗传算法优化了教室的合理利用，解决了在教室较少的情 内蒙古大学硕士学位论文 况下，如何对教师进行合理的分配【引。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 大学的数学学院时间表问题进行了求解1 9 1 。蒲保兴【1 0 】在论文中提出基于遗 传算法的搿动态罚值权定标方法”和“分块遗传策略 解决排课问题。朱冠宇等【1 1 】 在论文中分析了中学课程情况，采用一种三维编码方式及相应的遗传算子构成的遗 传算法求解中学课表安排问题。聂小东【1 z l 在论文中提出了基于贪婪算法的排课系 统。该系统对于贪婪准则的确定还是建立在人工排课考虑的因素上，没有充分考虑 提高课表质量的其它人文因素，并且目前实现的排课系统只是满足用户现在的排课 要求，还没有实现真正的智能排课，有待进一步的研究。任学惠掣1 3 l 在论文中提出 了利用模拟退火遗传算法解决课程表安排优化问题的算法。这种方法结合了遗传算 法和模拟退火算法的优点，使得两种算法的搜索能力得到相互补充，克服了遗传算 法中参数选择不当易陷入“早熟 和模拟退火算法对“退温”过程的限制条件苛刻 的缺点，可以避免搜索过程陷入局部最优。张林【1 4 l 在论文中采用了蚁群算法来解决 课程表问题。蚁群算法是通过模拟蚁群在觅食过程中寻找最短路径的方法来求解优 化问题，目前在旅行商问题等组合优化问题中有成功的应用。蚁群算法目前有a s 、 a c s 、m m a s 三种常用的模型，但是在排课问题上这三种蚁群算法都有易于陷入局 部最优解的缺陷，从而使得排课问题的求解过程过早地停止。郭方铭【1 5 】在论文中给 出了基于增强学习算法的课表编排模型的实现思路。增强学习算法是一种机器学习 的框架，其智能体通过一系列的活动影响其外部环境，并收到活动的回报。智能体 通过状态映射到动作来选择能获得最大回报的动作。增强学习算法的优点：( a ) 在应 用增强学习算法编排课表时，不需要对排课问题做过多的分析，也就是说，增强学 习算法避开了课表编排问题本身的复杂性；( b ) 排课智能体能在一定程度上自主学习 并决策，大大降低了人工排课的劳动强度，而且在安排课表的同时也在进一步学习 人工决策的结果，系统的性能得以逐步提高。但是由于排课问题的复杂性，该算法 的运用中还存在一些问题有待进一步的改进：( a ) 排课任务的顺序是该算法中的一个 关键问题，不同的顺序对应不同的学习效果。因而，如何针对不同的教学情况提供 尽可能合适的排序原则是一个有待改进的问题：( b ) 系统的排课是在学年学分制体系 下，按专业教学计划进行安排的，没有考虑学分制选课模式下的排课。如何在学分 制选课模式下根据选课情况对教室资源的需求量进行估算以提高教室利用率也是有 1 2 内蒙古大学硕士学位论文 待深入研究的问题。胡小兵等【1 6 l 在论文中所用的专家系统算法的特色是实现了知识 与程序的分离。该算法把知识集中在知识库中，事实数据集中在综合数据库中，程 序则构成推理机。排课的数据、原则与程序分别对应专家系统的综合数据库、知识 库和推理机。排课数据、排课原则从推理程序中分离出来，便于进行修订和补充。 排课算法重点解决逻辑推理，使得程序结构简练清晰，便于维护，但逻辑推理过程 比较繁琐。胡顺仁等【1 7 】在论文中针对排课问题的现状，将教师、班级、教室之间的 关系转化为集合关系，提出了图论的观点，并据此将排课问题进行数学建模，把教 师、班级、教室、每节课等元素转换成图形元素之间的匹配关系，提出了较为可行 的排课算法。然而，图的染色问题本身是n p - h a r d 完全问题，因此算法比较繁琐。 乔岸红1 1 8 】乔树清1 1 9 1 陈兴刚，孟祥婧，李静，宋剑凹1 等人也对遗传算法排课做了进 一步的研究，但他们大多没有给出较全面的排课模型，只是针对部分约束进行研究， 有些甚至在理想状况下排课。张春梅【2 1 j 对课程进行分类，并对不同课程使用具有自 适应能力的遗传算法进行安排。 1 4 本文主要研究的问题 本文主要进行以下几方面的研究工作： ( 1 ) 系统分析排课问题的各要素及多重约束条件，准备提出排课问题的求解难点 和优化目标，完整设计排课问题的数学模型，并着重分析比较常用的遗传算法编码 方案并研究其在捧课系统中的应用，在综合各种编码方案优缺点基础上，从编码方 案角度寻求突破口。 c 2 ) 改进遗传算法传统编码方案，设计一种新的解决排课问题的编码方案。根据 改进的编码方案，重新设计与之对应的交叉算子和变异算子，设计了冲突消除算法。 ( 3 ) 结合排课问题数学模型，将该编码方案以及与之对应的改进遗传算子应用到 排课程序中。 ( 4 ) 以实际排课数据测试本论文设计的编码方案及对应的遗传算子在实际排课 问题中的应用效果。 内蒙古大学硕士学位论文 第二章遗传算法简介 2 1 遗传算法基本术语 遗传算法效法于自然选择的生物进化，是一种模仿生物进化过程的随机方法， 因此遗传算法的基本术语与生物学的一些基本术语一致。 染色体( 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 ) ：有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉 1 4 内蒙古大学硕士学位论文 而重组，即在两个染色体的某一相同位置处被切断，其前后两串分别交叉组合形成 两个新的染色体。这个过程又称为基因重组( r e c o m b i n a t i o n ) ，俗称“杂交”。 变异( m u t a ti o n ) ：在细胞进行复制时可能以很小的概率产生某些复制差错，从 而使d n a 发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。 编码( c o d i n g ) 由于遗传算法不能直接处理解空间的数据，因此我们必须通过编 码将它们表示成遗传空间的基因型串结构数据。 2 2 遗传算法中的基本思想 遗传算法是从代表问题可能潜在解集的一个种群( p o p u l a ti 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 co 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 、 父个体n ) 形成初始种群，并计算每个个体的适应度函数，第一代( 初始代) 就产 生了。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应 度选择个体，父代要求基因重组( 交叉) 而产生子代。所有的子代按一定的概率变 异，然后子代的适应度又被重新计算，予代被插入到种群中将父代取而代之，构成 内蒙古大学硕士学位论文 新的一代( 子个体1 、子个体2 、子个体3 、) 。这一过程循环执行，知道满足优 化准则为止。尽管单一种群的遗传算法很强大，可以很好的解决相当广泛的问题。 但采用多种群即有子种群的算法往往会获得更好的结果。每个子种群像单种群遗传 算法一样独立的演算若干代后，在自种群之间进行个体交换。这种多种群遗传算法更加贴近 于自然中种族的进化，称为并行遗传算法( p a r a l l e l i n gg e n e t i c a l g o r i t h m s ，p g a ) 。 2 3 遗传算法的运算流程 遗传算法是通过模仿生物学中遗传和进化的机理完成对问题域中最优解的搜 索。首先对目标问题进行编码，编码是表现型到基因型的映射，而遗传算法的实现 基础是基因，因此需要将问题域转换成基因空间；其次确定种群大小和适应度函数， 种群中的合法个体在解码后其表现型满足目标问题的约束条件，算法在迭代的种群 中逐步搜索目标问题的最优解或满意解，因此最优解或满意解经过有限次迭代后一 定可以找到，适应度函数是用来评价优良个体的依据，适应度高的个体得以保留， 适应度低的个体被淘汰掉；再次随机产生初始种群，产生初始种群时要确保个体的 合法性约束，算法从初始种群开始对种群中的每个个体执行遗传操作；基本遗传算 子包括选择算子、交叉算子和变异算子，选择算子以个体的适应度为标准来决定哪 些个体是否能够保留，交叉和变异算子是产生新一代种群的关键遗传算子，随机确 定交叉点和变异点在编码串中的位置，可以产生新个体从而使种群进化逐步逼近最 优解或满意解；最后确定中止代数，即达到什么条件终止算法的执行。因为算法是 在计算机上执行的，而计算机要求一定的精度，因此目标函数的最优解无法达到理 论上的数值，而是一个接近最优解的近似值，所以确定终止代数是必要的，最后逐 个解码个体并输出适应度最大的个体的表现型，即为满意解，算法结束。 遗传算法流程图： 1 6 内蒙古大学硕士学位论文 图2 1 遗传算法流程图 2 4 基本遗传算子 基本遗传算法的操作算子一般都包括选择( s e l e c t i o n ，或复制r e p r o d u c t i o n ) 、 交叉( 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 ) 三种基本形式，它们构 成了遗传算法强大搜索能力的核心，是模拟自然选择以及遗传工程中发生的繁殖、 杂交和突变现象的主要载体。遗传算法利用遗传算子产生新一代群体来实现群体进 化，算子的设计是遗传策略的重要组成部分，也是调整和控制进化过程的基本工具。 一般情况，遗传算子的设计与遗传算法编码方案密不可分，不同的编码方案应该匹 配与之适应的遗传算子。 1 选择( s e l e c t i o n ) 选择也称为复制( r e p r o d u c t i o n ) ，它是用来确定重组或交叉个体，以及被选个体 将产生多少子代个体。选择过程的第一步是计算适应度。在被选集中的每个个体具 1 7 内蒙古大学硕士学位论文 有个选择概率，这个选择概率取决于种群中个体的适应度及其分布。选择算子最 终根据选择概率进行父个体选择。 通常使用的选择方法有： ( 1 ) 轮盘赌选择( r o u l e t t ew h e e ls e l e c ti o n ) ； ( 2 ) 随机遍历抽样( s t o c h a s t i cu n i v e r s a ls a m p l i n g ) ； ( 3 ) 局部选择( 1 0 c a ls e l e c t i o n ) ； ( 4 ) 截断选择( t r u n c a t i o ns e l e c t i o n ) ； ( 5 ) 锦标赛选择( t o u r n a m e n ts e l e c t i o n ) 。 2 交叉( c r o s s o v e r ，或重组r e c o m b i n a t i o n ) 交叉操作是进化算法中遗传算法具备的原始性的独有特征。g a 交叉算子是模仿 自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个体， 并生成包含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤： ( 1 ) 从父代种群中随机取出要交配的一对个体； ( 2 ) 根据位串长度l ，对要交配的一对个体，随机选取 1 ，l 一1 中一个或多个整数k 作为交叉位置； ( 3 ) 根据交叉概率p c ( 0 p c 1 ) 实施交叉操作，配对个体在交叉位置处，相互交换各 自的部分内容，从而形成新的一对个体。 常用的交叉操作包括： ( 1 ) 单点交叉( s i n g l e - p o i n tc r o s s o v e r ) j ( 2 ) 多点交叉( m u l t i p l e - 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 ) 洗牌交叉( s h u f f l ec r o s s o v e r ) ； ( 5 ) 缩小代理交叉( c r o s s o v e rw i t hr e d u c e ds u r r o g a t e ) 。 以单点交叉为例，交叉点k 的范围为 1 ，m 一1 ，m 表示个体变量数目，在该点为分 界相互交换变量。考虑如下两个1 1 位变量的父个体： 父个体11 1 0 1l o l o l 0 1 父个体20 1 0 1 0 1 0 1 1 1 0 假设交叉点位置为6 ，交叉后生成两个子个体： 1 8 内蒙古大学硕士学位论文 子个体l1 1 0 1 1 0 0 1 1 l o 子个体20 1 0 1 0 11 0 1 0 1 3 变异( m u t a ti o n ) 变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变 染色体的结构和物理性状。在遗传算法中，变异算子通过按变异概率p m 随机反转某 位等位基因的二进制字符值来实现。 常用的变异操作包括： ( 1 ) 实值变异； ( 2 ) 二进制变异。 以二进制变异为例，对于二进制编码的个体而言，变异意味着变量的翻转。对 于每个个体，变量值的改变是随机的，如下所示，有一个1 1 位变量的父个体： 父个体1 1 0 1 1 0 1 0 1 0 1 假设在第5 位发生变异，则变异后生成子个体： 子个体l1 0 1 0 0 1 0 1 0 1 1 9 内蒙古大学硕士学位论文 第三章用遗传算法求解课表问题 3 1 用遗传算法求解课表问题算法的概述 一个排课问题就是求p x s c x t r 的一个子集，使得该子集满足一定的约束 条件。而这样一个问题是一个n p 难问题，我们不能在多项式时间内给出一个满足 约束的排课方案。但对于一个给定的排课方案，我们可以在多项式时间内判断它有 哪些冲突，以及冲突的数量，并设计算法对排课方案做出减少冲突的调整。 3 2 编码方案 本文采用的排课方法是在时间教室对的二维表中安排课元，因此染色体就是 在二维表中存放的课元编号，只不过为了方便是把二维表拉成一行，先第一行、 再第二行，直到第加行。染色体的长度就是，l = i n i = i 丁x r i ( 即时间一教室对的总数， 看表3 1 ) 。 时间f 1时间t 2时间气 厂2kr 2，m，1r 2 l l正2 表3 1 表格的最下面一行就是染色体，里面存放的是安排在该位置的课元编号。如果 j 该位置没有安排课元，则置为0 。 对这样编排的染色体很容易推出位置下标k 和对应的时间教室对( f ，) 的关系： 给定时间- 教室对o ，r ) ，它的下标是七一( r n ) x ( t 一1 ) + r ；给定下标k ，它对应的 时间教室对o ，) ，t = kd i vm + 1 ，厂= km o d 埘。其中m 是教室总数，d i v ，m o d 分别是整除和取余运算。 例如：下表( 表3 2 ) 中下标为3 的位置存放6 表示，课元以安排在位置3 。由 上面位置下标的关系，可以计算出对应的时间- 教室对o ，) 。 i 12345以 i 6 如表3 2 染色体数组 2 0 内蒙古大学硕士学位论文 那么我们的排课过程就是把课元编号往表3 2 表示的染色体数组中填，这样就 建立了从课元到时间教室对的一个对应关系 为了下面表述方便，我们对染色体里的课元编号也称作课元，课元编号于课元 是一一对应的。 3 3 排课遗传算法流程图 图3 1 排课遗传算法流程图 2 1 内蒙古大学硕士学位论文 下面逐一叙述排课遗传算法流程图中的各个部分的实现方