（应用数学专业论文）基于遗传算法的课程表问题研究.pdf

东北大学硕士学位论文 摘要 基于遗传算法的课程表问题研究 摘要 课程表编排问题是时间表问题之一，也是一个解决时间和空间资源矛盾的 多因素优化决策问题，即对各类课程、教师、学生进行时空安排问题，这种安 排问题需要满足一定的约束条件集，如关于教室的位置与容量、时间间隔、特 定课程承接关系等方面的约束条件。目前各类学校都存在着学生数量、课程设 置增多，而相应的配套资源没有太大变化的情况。这就要求能充分利用已有的 资源，选择最合理的编排方案。近4 0 年来，人们尝试着用各种方法求解此类 问题，如：整数规划、图着色、各种推理搜索方法、进化算法等等。 遗传算法是一种拟自然的、具有随机性的全局优化方法。近些年来，遗传 算法在求解复杂问题中发挥了重要的作用。同样，遗传算法也能有效的求解课 程表问题。 本文分析了课程表问题的发展状况；综述了遗传算法在数学基础、遗传操 作以及各领域的应用发展现状：根据大学授课形式的特点建立了大学课程表问题 的数学模型；给出了基于不同目标的遗传算法求解方法；提出教师和教室的两种 编码形式，为了提高解的质量和加快收敛速度又设计最佳时段一查找法，并将其嵌 入遗传算法中；对于利用教室编码的遗传算法提出了一种新的交叉算子；通过实 验验证了本文所提出的算法适合于所建模型的求解，是可行性和有效性。最后 给出了课程表问题进一步研究的方向。 关键词：时间表问题、课程表问题、遗传算法、编码、遗传操作、早熟收敛、 进化计算、数学模型 ，i i 查! ! 垄兰翌主兰堡堕圭一垒坐! ! 坚 r e s e a r c ho nl e c t u r et i m e t a b l i n gp r o b l e m b a s e do n g e n e t i ca l g o r i t h m a b s t r a c t l e c t u r et i m e t a b l i n gp r o b l e mi so n eo ft h et i m e t a b l i n gp r o b l e m s i tp e r h a p si so n e o ft h e g r e a t e s tp r o b l e m st o b es o l v e da tt h e b e g i n n i n go fe a c ht e r m l e c t u r e t i m e t a b l i n gp r o b l e mi st h ep r o b l e m o f a s s i g n i n gt i m e sa n dp l a c et om a n ys e p a r a t e l e c t u r e st u t o r i a l se r e t o s a r i s f y s e v e r a lc o n s t r a i n t s c o n c e r n i n gc a p a c i t i e s a n d l o c a t i o n so fa v a i l a b l er o o m s ，f r e e t i m en e e d sa n do t h e rs u c hc o n s i d e r a t i o nf o r l e c t u r e r s ，a n dr e l a t i o n s h i p sb e t w e e np a r t i c u l a rc o u r s e s a se d u c a t i o n a li n s t i t u t i o n s a r ec h a l l e n g e dt o g r o wi nn u m b e ra n dc o m p l e x i t yw i t ho f t e nn oc o r r e s p o n d i n g i n c r e a s ei nr e s o u r c e sd u et ou s u a lb u d g e tc o n s t r a i n t s ，t h e i ro p e r a t i o n sn e e dt ob e s t r e a m l i n e dm o r ea n dm o r ee f f i c i e n c yw h i l em i n i m i z i n gr e s o u r c e su s a g e o v e rt h e l a s t4 0y e a r s m a n ya p p r o a c h e sa n dm o d e l sh a v eb e e np r o p o s e df o rd e a l i n gw i t ha v a r i e t yo ft h et i m e t a b l i n gp r o b l e m s ，s u c ha si n t e g e rp r o g r a m m i n g ，g r a p hc o l o r i n g ， h e u r i s t i c ss e a r c hm e t h o d sa n de v o l u t i o n a r ya l g o r i t h m s g e n e t i ca l g o r i t h mi sar a n d o mo p t i m i z a t i o na n ds e a r c ht e c h n i q u e i th a sb e e n a p p l i e dt oav a r i e t yo fc o m p l e xp r o b l e m s l e c t u r et i m e t a b l i n gp r o b l e mi sc o u l d b e s o l v e db yg e n e t i ca l g o r i t h m q u i t es u c c e s s f u l l y i nt h i s p a p e r , ab r i e fi n t r o d u c t i o nt os o m ea p p r o a c h e st ol e c t u r et i m e t a b l i n g p r o b l e m i sg i v e n t h e n ，s u r v e ya b o u t g e n e t i ca l g o r i t h m o dt h eb a s eo f m a t h e m a t i c s ， g e n e t i co p e r a t o r sa n d r e l e v a n ta n a l y s i si st h o r o u g h l yp r e s e n t e d t h i r d ，w ep r o p o s ea m o d e l a c c o r d i n g t ot h ec h a r a c t e r i s t i c so f u n i v e r s i t yt i m e t a b l i n gp r o b l e ma n ds o l v e d b yg e n e t i ca l g o r i t h m f o ri m p r o v i n gt h es o l u t i o n q u a l i t y a n d i n c r e a s i n g t h e c o m p u t a t i o n a le f f i c i e n c y ，t h e b e s t t i m e s l o t - f i n d i n ga l g o r i t h m i s p r o p o s e d a n d c o m b i n e dw i t hg e n e t i ca l g o r i t h m t w ok i n d so fc o d e sa n dan e w k i n do fc r o s s o v e r a r eg i v e ni nt h i sp a p e r f i n a l l y ，t h ee x p e r i m e n t sv e r i f yt h a tt h i sm e t h o di su s e f u lt o s o l v et 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 k e yw o r d s ：t i m e t a b l i n gp r o b l e m ，l e c t u r et 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 s ， e n c o d e ，g e n e t i co p e r a t o r s ，p r e m a t u r e c o n v e r g e n c e ，e v o l u t i o n a r yc o m p u t a t i o n ， m a t h e m a t i c a lm o d e l i i i 声明 本人声明所交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表 或撰写过的研究成果，也不包含本人为获取其它学位而使用过的材 料。与我+ 同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 本人签名： 敲，浆 日 期：0 弓7 王口 东北大学硕士学位论丈 第一章引言 第一章引言 时间表问题( t i m e t a b l ep r o b l e m ，简称t t p ) 是运筹学领域中组合优化问 题之一。它有广泛的应用背景。如护士工作时间表、各种体育赛事安排时间表、 火车时刻表、各类院校每学期的考试时间表、课程表等等。w r e n 1 将时间表定 义为满足约束条件的安排方案，即将关于所研究对象的特定资源安排到一定时 空中，并使其尽可能多的满足一系列目标约束。b u r k e 2 称t t p 简单地说就是 将一系列的事件安排到特定的时域点上，使得同一空间( 容量充足) 、同一时 间只允许一个事件占用。在简化情况下如果有m 个事件安排到盯个时域点上， 则共有n ”种安排方案；因在约束条件下每一种方案都有其适用的约束范围，故 只有极少数方案可以满足全部约束条件。求解t t p 就是寻找满足全部约束条件 的最优安排方案。 最初人们是通过手工方式编排t t p ，但这种方式费时、费力，而且随着时 代的进步关于各类t t p 的信息量大幅度增加，手工制表已经很难找到满意的结 果，e v e n 3 等人已证明t t p 是一个具有n p 难度的问题。因此求解t t p 引起 了各领域专家的极大兴趣，并对其进行了深入的研究，不断的将一些现代优化 算法用于求解该类问题，如神经网络技术( n e u r a ln e t w o r k s ，简称n n ) 、专家 系统( e x p e r ts y s t e m ，简称e s ) 、模拟退火算法( s i m u l a t e da n n e a l i n g ，简称 s a ) 、进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，简称e c ) 等等。 本文着重讨论课程表的编排问题。课程表问题( l e c t u r et i m e t a b l i n g p r o b l e m ，简称l t p ) 看似简单，实质上是难解的t t p 之一。近四十年来人们 试着用各种优化方法求解此类问题，尝试着构造自动制表系统来代替手工制 表，例如运用直接启发算法( d i r e c th e u r i s t i c sa l g o r i t h m s ，简称d h a ) 、约束 目标规划( c o n s t r a i n tp r o g r a m m i n g ，简称c p ) 、禁忌搜索( t a b us e a r c h ，简称 t s ) 、s a 、e c 等等。但到目前为止还没有找到通用的适用于各种变化条件下的 课表编排系统，仅能制订出适用于特定条件的l t p 编排方案。 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a s ) 是一种新兴的模拟生物进化过 程的随机搜索算法，g a s 具有不受搜索空间的限制性假设的约束的特点、不必 要求诸如连续、导数存在、单峰等假设，且具有固有的并行性，目前广泛的用于 求解经济、工程、计算机等多个领域的复杂难解问题，并取得了许多成功的应用 东北大学硕士学位论文第一章引言 f 5 8 6 3 6 8 1 。因l t p 具有搜索空间大，约束条件复杂等特点而适合于用g a s 求 解。近年来人们开始尝试用g a s 求解l 1 p ，并取得了一些成果 9 7 】 1 0 5 。 本文主要分析了g a s 的实现原理、发展状况及其在求解l t p 的应用状况， 并根据大学授课形式的特点建立了大学课程表问题( u 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 ，简称u t p ) 的数学模型，并提出了两种编码方式，利用g a s 求解模 型，通过实验对比，验证了所提出的算法的可行性和有效性。 内容安排如下：第一章引言：第二章概述l t p 研究的必要性、l t p 的描 述及分类办法；第三章全面分析了g a s ；第四章分析了g a s 在l t p 的应用状 况，建立了基于不同目标的u t p 数学模型，并提出了基于g a s 求解u t p 的方 法，进行了实例分析；第五章对全文进行了总结，并指出了今后进一步研究 l t p 的方向。 东北大学硕士学位论文 第二章l t p 概述 第二章l t p 概述 2 1l t p 研究的必要性 长期以来人们通过手工制表或借助于简单的软件系统来编排课程表，手工 制表是最常用的办法之一，即直接对前一年的课程表进行修改继续延用。实践 表明这种办法在每年课程设置、教师、学生及教室规模变化不大的情况下是有 效的。但随着我国教育体制改革的不断深入，特别在高校系统中连年的扩召、 扩建、不断的改进专业设置、实行学分制的新形式下，在校学生、教师、教室 及课程数量上都有大幅度增长，学生在选择课程上有了更大的灵活性，这使得 以前的课程表无法延用，而需要每学期都重新编排课程表。很多学校一直采用 传统的手工制表的方式编排课表，这样不但浪费人力( 需要熟悉编排工作的人 花费几个星期的时间) ，而且经常出现问题( 如教室座位不够、教师同一时间 重复安排上课等) ，尤其个别课程需要调整时整个课程表都要重新编排。求解 l t p 面i 临着两大难点：一是涉及的人员增多；二是需要处理的约束增多。理论 和实践表明只要课程表所涉及的信息量稍有所增加就会导致“组合爆炸”，使 得课程表编排的方案剧增。由此看来手工制表已经无法处理如此巨大的信息 量，需要对l t p 进行深入的研究，寻求行之有效的解决办法。 开发出有效的课程表编排系统不但能使学校教学系统运行得更加顺畅、合 理，还能节约人力，有效的利用学校的各项资源，节省学校的各项支出。 2 2l t p 2 2 1 l t p 定义 l t p 是一个解决时间和空间资源矛盾的多因素优化决策问题，即对各类课 程、教师、学生进行时空安排问题，这种安排问题需要满足一定的约束条件集， 如关于教室的位置与容量、时间间隔、特定课程承接关系等方面的约束条件。 l t p 也可以定义为如下形式： 给定资源的描述e = 乜，p ：，e v ) 表示事件 ( 各类课程) ，t = r ，t ：，f ， 表示时间( 允许安排课程的时间段) ， 查! ! 垄堂堡圭兰堡丝圭 苎三主望旦垫兰 ，： p ，p ：，p 。，) 表示空间( 有足够位置可安排上课的教室) ， a ： n ，n ：，一，d 。) 表示人员( 上课的教师、班级) ： f 1 ) 每个安排为一个由四个元素构成的有序组( p ，t ，p ，a ) ( ，时间段在p 教 室，a 教师和相应班级上p 课) ，其中e e ，r t ，p p ，a a ； f 2 1课程表为全体安排的一个组合( 包括可行的课程表和不可行的课程 表) ； ( 3 )求解l t p 就是寻求满足约束集合的安排( 真实解) 或寻求满足最多 约束的安排( 近似解) 。 2 2 2l t p 的约束条件 在l t p 中主要涉及到班级、教师、时间、课程、教室等五个相互制约的基 本因素。合理的课程表安排需要满足由这五个因素形成的如下约束( 可将其分 为“硬”约束和“软”约束) 。 “硬”约束：可行课程表必须满足的约束条件，如果某个约束不能满足则 不能作为可行的课程表。常见的“硬”约束条件如： ( h 1 ) 一个教室不能同时安排两位以上的教师上课； ( h 2 ) 一位教师不能同时上两门课； ( h 3 、一个班级不能同时上两门课； ( h 。) 参加每门课的人数不能超过所安排教室的容量。 “软”约束：希望所采用的课程表编排方案尽可能多的满足约束，虽然这 些约束不满足时仍是可实行的课程表。但满足“软”约束条件越多则课程表编 排方案越合理。满足所有“软”约束的课程表编排方案是最优方案。常见的“软” 约束条件如： ( sj ) 每门课程要有足够的课程分散度； ( s 2 ) 安排到每个教室上课的人数应尽量和教室容纳人数相吻合，这样不但 能合理利用教室资源，而且教学效果也好； ( s 3 ) 保留一些特殊的时间，如户外活动、星期三下午作为政治学习或开班 会的时间等； ( s 4 ) 一周多学时课程应尽量安排在一个教室( 方便教师及学生) ； ( s 5 ) 担任多门课教学任务的教师希望将不同课程尽可能安排在同一天上 这样可以保留某天无课； ( s 6 ) 一个班级前后两门课的上课教室之间的距离不能太远； 查! ! 垄堂堕主兰堡垒墨 堑三兰坚里垫垄 ( s 7 ) 尽量安排在好的教学时间段上课( 如上午比下午好) ； ( s 8 ) 有些课程需要其他课程之后上更合理。 2 3l t p 的分类 可以根据不同的标准对l t p 进行分类： n ) 根据学校类别及约束类型的不同，可将学校课程表分为三种形式：中 学课程表、大学课程表和考试时间表。但这种划分并不严格，有些特 殊情况没有考虑，例如：各类技工学校的课程表 4 】等。 ( 2 ) 根据课程表的使用者的不同，可将课程表分解为五个子表：课程安排 表、每位教师的课程表、每个班级的课程表、教师任务安排表、教室 安排表5 1 。 2 4l t p 的求解办法 自动课程表的编排工作包括三个步骤： ( a ) 整理数据，即将课程安排编写为可行的数据格式： ( b ) 应用相应的算法对数据进行处理，找到合理的l t p 编排方案； ( c ) 维护、修改，将输出数据还原成各类可用课程表。 ( a ) 、( c ) 步一般是通过手工的形式完成( 到目前为止课程表的编排还没完 全离开手工方法) 。 现将( b ) 步骤的工作归纳如下： ( 1 ) 直接运用各种优化方法 很长时间以来人们都是通过手工制表的方式编排课程表，当需要编排的课 程表十分复杂时就只考虑主要约束，即使这样整个编排过程还要花费熟悉制表 工作人员很多天的时间，有时仍不能达到满意的效果( 如教师不能相邻天上同 一门课等) 。于是4 0 年前人们就尝试研制自动制表系统。g o t l i e b 6 首先开始 运用推理的方法建立自动制表系统。之后人们又将多种优化方法用于自动制表 的研究。 最初的一类方法是模拟手工制表的推理方法，可称为“直接启发算法”。 这类方法是通过不断应用推理规则将课程逐一填入课程表的方式实现的，当所 有的课程都填完，即得到了可行的课程表编排方案，事件的编排顺序由事件受 约束的程度决定。这种方法一般要好于随机排序的方法。如推理序列( h e u r i s t i c 东北大学硕士学位论文 第z - 章l t p 概述 s 。q u e n c i n g ) 的方法 7 】，即通过推理来估计各课程编排的难易程度，难度大的 课程先排，难度小的课程后排。后来为了提高编排质量，人们对其进行了改进， 加入了回放过程( b a c k t r a c k i n g ) ，即当遇到矛盾事件时将其中的事件放回待排 序列等待以后再排。但加入回放过程后增加了机器运行时间。 之后人们开始将一些常用的优化方法引入到求解l t p 中来。如整数线性规 划算法( i n t e g e rl i n e a rp r o g r a m m i n g ) 8 、网络流算法( n e t w o r kf l o w ) 9 1 及将 问题缩减为图着色问题( g r a p hc o l o r i n g ) 1 0 、约束处理规则( c o n s t r a i n t h a n d i n g r u l e s ) n 3 1 等方法，其中图着色方法研究的比较深入。但这类方法需要手工完 成任务部分较多。如文献 3 5 1 提出的一种基于网络流算法的多层次分配算法， 需要操作者根据求解问题的规模设置参数，进行编码。这类方法的优点在于能 求得可行的课程表编排方案，缺点是不能根据“软”约束条件选择最优安排方 案。 近些年来人们又将一些新兴的优化技术( 如s a 【1 1 】、t s 1 2 、g a s 2 等) 用于求解l t p 的编排，并取得了较好的结果。 ( 2 ) 多种优化方法相结合的方法 ( 1 ) 中的各类解法都只用了一种优化方法，无法克服其自身的局限性。较好 的方法是将这些算法结合起来，进行优势互补综合应用。 s c h a e r f 1 4 提出了一种随机爬山( h i l l c l i m b i n g ) 与t s 相结合的局部搜索 算法，该算法交替使用两种移动方式，即利用随机爬山算法形成初始群体，然 后进行t s 寻优，利用t s 可将约束条件适当放松扩大搜索范围。这种利用局部 搜索方法缺点在于使用者不能随意修改某些课程的编排，即不允许使用者根据 推理插入一些加快编排速度的方案。为了克服这一缺点文献 1 5 尝试着将推理 方法和局部搜索技术结合，取得了较好的结果。k o w a l c z y k 1 6 1 提出了基础约束 规则与分支定界技术相结合的方法，但这种方法求解能力取决于搜索策略所确 定决策树的深度和广度等因素。基础事件规则的方法也能有效的求解l t p ，该 方法延用了在手工制表时经常在已有表的基础上进行修改，形成新课程表的想 法，将一些解决过的l t p 保留为基础事件，用于求解新的l t p 。这类方法经常 用价值图来代表事件，然后形成由决策树表示的基础事件，制定出补救过程来 表示新增事件和约束，最后通过如图推理等方法形成新表。b u r k e 1 7 总结了应 用这种方法时需要解决的四个问题，并指出不但新问题的价值图与原问题的价 值图同构时能被再利用，而且部分结构相似时也能被再利用，并给出了新问题 的价值图与已有价值图的相似程度的加权衡量公式。这种方法的缺点是由于需 东北大学硕士学位论文 第二章l t p 概述 要保留所有的变更信息，因此仅适用于变化较小的l t p ，如果课程表的规模远 远大于基础事件则无法求解。基于此b u r k e 1 9 又提出了多阶段恢复过程，每个 恢复过程在基础事件中找到部分事件与新问题匹配。 f 3 1 将整个问题分为若干个子问题的方法 c a r t e r 1 8 1 提出将整个问题分解为几个易求解的小规模子问题，之后用如整 数线性规划等常规方法求解。t r i p a h y 8 提出了两阶段的方法，第一个阶段处理 课程和教室的安排；第二个阶段处理时间安排并用了拉格朗日松弛( l a g r a n g e r e l a x a t i o n ) 方法处理分组后的小规模问题。这种方法虽然降低了问题的复杂程 度，但只能针对作者所提出的确切问题，如果改动约束条件或者修改问题的规 模，则需要重新考虑整个分析过程。但若根据求解的难易程度动态的增大子问 题的规模，运行结果表明随着规模增加，求解时间也在增加，解的质量在降低。 b u r k e 1 9 指出子问题的规模与处理问题所包含的事件的数量有关，对具体问题 应采用相应的固定规模的子问题求解效果较好。 东北大学硕士学位论文 第三章g a s 简介 第三章g a s 简介 3 1g a s 的产生与发展 早在5 0 年代，随着生物科学和计算机科学的发展，一些学者开始尝试着 从生物进化的机理中寻求解决现实世界复杂工程优化问题的新工具，即所谓的 “人工进化系统”的研究。密西根大学的h o l l a n d 教授所从事的研究即为该类 研究的一个重要方向。1 9 6 7 年b a g l e y 2 0 发表了关于g a s 的论文，在其论文中 首先使用了“g e n e t i ca l g o r i t h m s ”来命名h o l l a n d 教授所提出的进化方法。虽 然在六、七十年代由于计算机运行速度慢、成本高，人们没有认识到进化算法 研究的重要性而热衷于一些人工智能的应用与研究，但是h o l l a n d 及其学生仍 坚持这一方向的研究，并于1 9 7 5 年发表了g a s 领域具有里程碑意义的著作 “a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m s ”【2 1 】。这本书为所有的适应系统 建立了一种通用的理论框架，并为g a s 奠定了数学基础，同时展示了如何将自 然的进化过程应用到人工系统中去。同年，d ej o n g 2 2 建立了著名的d ej o n g 五函数测试平台，用于研究g a s 的基准参数。为g a s 的性能评定制定了评价 标准。进入八十年代，传统的人工智能研究暂时陷入困境，计算机技术日新月 异地飞速发展，利用生物系统进化思想的模拟智能的研究重新活跃、繁荣起来。 1 9 8 3 年g o l d b e r g 第一次把g a s 用于实际工程系统一煤气管道的优化。此后， g a s 得到了更多领域人们的关注，对g a s 的应用和理论研究更为深入和丰富。 1 9 8 5 年以后，每两年举行一次g a s 国际学术会议。各种与g a s 相关的国际会 议也逐年举行。1 9 8 9 年g o l d b e r g 2 3 所著的“g e n e t i ca l g o r i t h m s i ns e a r c h ， o p t i m i z a t i o na n dm a c h i n el e a r n i n g ”作为第一本g a s 教科书，对当时g a s 的理 论及应用作了较为全面的分析和论证，使得g a s 这一技术得到普及和推广。九 十年代后，很多专家将g a s 应用到各自所从事的领域，在人工智能、自动控制、 社会科学、商业和金融、生物工程等等领域都取得了成功的应用。1 9 9 2 年 m i c h a l e w i c z 2 4 1 出版的著作“g e n e t i ca l g o r i t h m s + d a t as t r u c t u r e s = e v o l u t i o n p r o g r a m s ”对g a s 应用于优化问题起到了推波助澜的作用，使g a s 不断的向 深度和广度发展。g a s 模拟生物界的自适应过程，g a s 为各类复杂问题提供了 种通用的、易于实现的解决方法，并以其简单、鲁棒性强、不受搜索空间的 东北大学硕士学位论文 第三章g a s 简介 约束条件限制等特点受到各领域专家重视，在各个领域中得到广泛的应用。九 十年代末到本世纪初，由于g a s 的理论研究与应用研究的发展不相平衡，人们 仅能从特定条件下分析g a s 的收敛性、收敛速率等一些性能指标，因此人们更 加注重遗传机理的研究；同时随着生物科学与计算机科学的发展，一些科学家 想借助更复杂的遗传手段来丰富g a s 。 3 2g a s 的基本原理 g a s 的实施过程包括编码、产生初始群体、计算适应度、复制、交换、变 异等操作。具体算法如下 2 5 ： ( 1 1 随机产生一个由确定长度的特征串组成的初始群体； ( 2 ) 对串群体迭代地执行下面的步( a ) 和步( b ) ，直到满足停止准则： 计算群体中每个个体的适应值； 伯) 应用复制、交换和变异算子产生下一代群体； ( 3 ) 把在任何一代中出现的最好的个体串指定为g a 的执行结果。 标准g a 框图由图3 1 给出，其中变量g e n 是当前代数。 3 3g a s 的数学基础 3 3 1 模式定理与建筑块假说 h o l l a n d 2 1 所提出的模式定理是g a s 的理论基础，它描述了二进制编码 情况下应用适应度比例选择策略g a s 的有效性。 定理3 1 ( 模式定理) ：具有短的定义长度、低阶、适应值在群体平均适 应值以上的模式在g a 迭代过程中将按指数增长率被采样。 模式定理说明，g a 根据模式的适应值、长度和阶次来为模式分配搜索次 数。模式定理指出中、高阶模式的适应值计算困难，b e t h k e 2 6 运用w a l s h 函 数和模式转换通过低阶模式的适应度来估计高阶模式的适应值。有些学者指出 模式定理不能解释各种不采用按适应度比例选择策略的遗传算法的有效性，认 为模式定理仅适应于线性的、单极值搜索空间，而g a s 所求解问题的搜索空间 几乎全是非线性、多极值空间，因此模式定理不再适用。g o l d b e r g 将具有短的、 低阶的、较高适应值的模式称为“建筑块”。h o l l a n d 和g o l d b e r g 在模式定理 的基础上提出了“建筑块假说”，指出g a 的搜索模式存在着内在的并行性。 图3 1 标准g a 流程图 f i g3 1t h ec i r c u i tf l o wd i a g r a mo fs t a n d a r dg e n e t i ca l g o r i t h m 1 0 - 查i ! 垄堂塑主芏堡堕查 一一 苎兰主鱼垒! ! 尘 种群大小为h 时，每一代处理有效模式的下限值为d ( ”3 ) 。文献 2 7 】推广了这一 结论，证明了每次至少产生0 ( 2 ”1 ) 数量级的新模式的结果。 3 3 2 全局收敛性与搜索效率的数学基础 3 3 2 1 基于m a r k o v 链分析g a s 的收敛性 1 9 8 7 年o o l d b e r g 和s e g r e s t 2 8 首先使用m a r k o v 链分析g a s ，并分析了 一种只有变异和复制的g a s 的收敛性。1 9 9 1 年d a v i s 2 9 将s a 理论外推到g a s 的m a r k o v 链中分析了标准g a 所生成的m a r k o v 链是各态历经的。同年e i b e n 3 0 提出了一种抽象g a ，并证明了其找到全局最优解的概率为1 。1 9 9 3 年 m a h f o u d 3 1 1 讨论了当有限m a r k o v 链用于描述b o l t z r a a n n 锦标选择是其转移概 率的确定过程。1 9 9 4 年r u d o l p h 3 2 给出了一种针对个体收敛性的定义，并通 过m a r k o v 链方法证明了简单g a s 收敛不到全局最优解，若每次迭代过程保留 了最优个体时，能达到全局晟优，但这样的改动并不能提高收敛速度，甚至要 花费更长时间。同年，f o g e l 3 3 i t 正明了当不使用变异算子时，g a 所生成的 m a r k o v 链存在吸收态。1 9 9 5 年s u z u k i 3 4 从m a r k o v 链的角度分析了g a s 的统 计规律，通过估计转移矩阵的特征值，分析了带有精英选择g a s 的收敛性与收 敛速度。1 9 9 6 年r e y n o l d s 和g o m a t a m 3 5 为了克服m a r k o v 链描述g a s 时对采 用的编码方式的依赖性，引入了以向量为指标的矩阵乘方概念，将g a s 的搜索 过程分为替代抽样和非替代抽样两大类后，建立了相应的m a r k o v 链模型，考 察了其收敛性。 3 3 2 2 基于动力学模型分析g a s 的收敛性 1 9 9 1 年v o s e 3 6 提出了在二进制编码条件下，标准g a 所应用的比例选择、 交叉和变异算子的不动点的存在性与稳定性来研究g a s 的渐近性。说明了g a s 收敛性态是随种群规模变化的。1 9 9 2 年n i x 和v o s e 3 7 描述了有限种群规模下 g a s 的实际m a r k o v 链演化过程，但由于计算复杂而不能直接用于分析g a s 的 收敛性态。1 9 9 4 年b h a t t a e h a r y y a 和k o e h l e r 3 8 将v o s e 3 6 的结果进一步推广 到了非二进制g a s 中的相同算子。同年，d a w i d 3 9 推广了文献 3 6 】的结论，研 究了当每个个体的适应值由一个依赖于整个种群状态的函数来确定时，g a s 的 m a r k o v 链描述问题。1 9 9 6 年v o s e 4 0 建立了基于有限m a r k o v 链的无限群体的 动力学模型。证明了对于大种群的g a s 的短期收敛形态是由所选取的初始种群 的吸引域决定。1 9 9 7 年b e s o m 【4 l 】指出了文献 4 0 1 模型应用上很不方便，并 建立了另一模型，考察了其收敛性给出了相应的证明。文献 4 2 】使用动力系统 的方法研究g a s 的运行机理，讨论了g a s 在局域吸引点的动力学形态，指出 查! ! 垄堂堡主兰堡堕查 星三主g 垒! 塑坌 g a s 在群体规模足够大和忽略变异算子的情况下如果算法收敛到一个局部一 致的状态，那么这个状态就是算法的局部极值点。 3 3 2 3 其他方法 文献【4 3 】采用纯概率的方法和迭代公式分析了g a s 一般模型的收敛性，并 给出了杰出者g a 、整体退火g a 、最佳值选择g a 、广义模拟退火g a 的概率 收敛定理。m i c h a l e w i c z 2 4 给出了针对整个种群的一种渐近收敛的定义，提出 可以用b a n a c h 不动点原理来解释g a 的收敛性。同时设计了一种压缩映射g a ， 并利用b a n a c h 压缩映射定理证明了其在渐近收敛定义下能够收敛到全局最优 解。 3 4 遗传操作分析 3 4 1 分析g a s 的编码策略 g o l d b e r g 2 3 给出了g a s 编码应满足的三个规则。h o l l a n d 建议使用二进 制编码，使得相等的问题编码空间对应于最大的模式空间，后为了克服 h a m m i n g 距离，利用一个变换将二进制编码转换为g r a y 编码 4 5 1 。为了提高二 进制编码的搜索精度w h i t l e y 4 6 提出了“d e l t 编码”，s c h r a u d o l p h 和b e l e w 4 7 1 提出了“动态参数编码”等改进形式的二进制编码。但二进制编码不能直接反 映问题的结构，精度不高，个体长度过大，占用内存过多。对此，a l a n d e r 指 出应当使用其他表示方案。m i c h a l e w i e z 2 4 指出应用解决问题时应当选取最“自 然”的编码方案。人们在以后的应用g a s 中对不同的问题提出了多种编码形式。 如：g o l d b e r g 4 8 指出应用实数编码求解数值优化问题时可以直接在表现型上 进行遗传操作，通过引入相关领域的知识增加算法的搜索能力，精度更高、更 稳定。还有将二进制编码与实数编码结合起来采用了一种混合变长编码策略。 但m i c h a l e w i c z 2 4 比较了二进制编码与实数编码的优缺点，指出二进制编码的 进化层次是基因，实数编码的进化层次是个体，用前者的理论来指导后者是不 合适的。大量的实验结果表明，对同一优化问题两种形式编码的g a s 不存在显 著的性能差异。二进制编码比实数编码搜索能力强，但稳定性差。实数编码比 二进制编码能更好的保持种群的多样性。v o s e 4 4 扩展了h o l l a n d 的模式概念， 指出不同编码之间是同构性的。其它编码方式还有：使用复数编码的来解决二 维优化问题；使用多维实数编码使得无效交叉发生可能性大大降低；使用对称 编码，通过优良型保护，以加快收敛速度。c o l o m i 4 9 使用矩阵编码的g a 解 1 ， 东北大学硕士学位论文第三章g a s 简介 决l t p ，并指出这是一种解决该类问题的最自然的表示方式。k o z a 5 0 应用计 算机程序来编码，扩大了g a s 的应用领域。c o o p e r 5 1 采用压缩编码，提高了 g a s 设计模糊控制器的适应性与灵活性。有些学者指出在解决优化组合问题 ( t s p 问题，f l o w s h o p 问题，列车占线问题等) 用序列编码表示使问题更自 然、合理。v o i g h t 5 2 基于模糊优化问题给出了一种模糊编码的g a ，即扩展了 传统的二进制编码，每一位可以取 0 ，1 之间的任何值。还有可分解，可拼接编码 的编码方式。 3 4 2 基因操作策略及其性能研究 3 4 2 1 复制( 选择) 复制可以避免基因缺失，提高全局收敛性和效率。复制的类型：轮盘选择 ( 误差较大) 、无放回随机选择( 降低选择误差，操作不便) 、确定式选择( 选 择误差小，操作简便) 、柔性分段式选择( 防止了基因的缺失，要选择有关参 数) 、自适应柔性分段式动态群体采样( 提高搜索效率) 、线性排名选择、非 线性排名选择( 当群体规模较大时，计算量大) 、无回放式余数随机选择( 误 差最小) 、均匀排序( 与适应度大小，差异程度正负无关) 、最优串选择( 全 局收敛，不适用于非线性强的问题) 、最优串保留( 全局收敛) 、排挤选择、 基于免疫多样性的选择( 依赖于串的稠密度进行选择) 等等。 3 4 2 2 交叉 通过交叉组合成新的个体在串空间进行有效搜索，是g a 区别于其他进化 算法的重要特征。交叉算子对染色体有破坏和重构的双重作用。文献 5 3 1 给出 了在只有交叉算子作用下染色体的数量和分布范围的变化规律，提出交叉算子 在演化代数增加的时候能够使模式内部各基因趋于独立，并且只要组成模式的 各个基因都存在，则该模式一定能被搜索到，此时模式的极限概率等于组成该 模式各基因的初始概率的乘积，并且与模式的定义长度无关，从而说明了交叉 算子能使群体分布扩充的特性。交叉之前一般要随机配对，而且不同的编码下 交叉操作是不一样的。文献 5 4 】分析了二进制编码条件下，利用m a r k o v 链证明 了对于两个互补的二进制串，交叉操作能够进行遍历搜索。文献 5 5 1 对近亲交 叉回避策略进行了改进，提出若两个体的h a m m i n g 距离较大则将其选为待交 叉母体，否则在该群体中选择另一个个体，h a m m i n g 距离下限随进化代数而变 化的防止近亲交叉策略。其它交叉类型还有： ( 1 ) 用于符号编码的交换类型：单点交换、双点交叉、均匀交叉、多点交 查! ! 垄兰堡主堂堡垒圭羔兰皇_ 塑i 坠 叉、自交叉算子； f 2 1 用于序号编码的交叉类型：部分匹配交叉( 记为p m x ) 、序号交叉( 记 为o x ) 、圈交叉( 记为c x ) 、启发式交叉、基于位置交叉； ( 3 1 其它类型的交叉：算术交叉( 实数) 、代数交叉算子( 二进制编码) 。 3 4 2 3 变异 为了扩大群体的多样性，避免早熟收敛，引入了变异操作来随机的改变个 体的基因值，引导搜索转向，增加搜索到全局最优的机会。变异类型有： f 1 ) 用于符号编码的变异类型：常规位变异( g a 标准操作) 、有效基因 变异、自适应有效基因变异、概率调整变异、群体列变异，动态变异( 变 异半径动态调整) 、单变量变异( 仅对父本最优个体的基因位进行变异， 其它个体不变异) ； ( 2 ) 用于实数编码的变异类型：均匀变异、非均匀变异、三次高斯近似变 异、零变异、一致变异、非一致变异； ( 3 ) 用于自然数编码的变异类型：倒位变异算子、部分倒位变异算子。 3 4 3g a s 参数的选择 g a s 的参数主要包括群体规模、交叉概率、变异概率、代距等。初始群体 的选择对于遗传算法的收敛速度和结果有一定的影响，文献【5 6 】提出了基于实 数编码的区间分割方法，改进初始群体的产生办法，增加了最优解组合的概率， 避免了接近个体的入选，提高收敛速度，防止早熟收敛。文献 5 7 】提出在选择 操作中根据搜索结果动态的调整各染色体被选中的概率交叉和变异的概率越 大，算法的探测能力越强，越能够探测到新的超平面，个体平均拟合度的波动 较大；反之交叉和变异的概率越小，算法的开发能力越强，使得较优个体不易 被破坏，个体的平均拟合度平稳，但收敛速度较慢。目前常用的选取变异概率 的方法是根据经验值确定。但根据经验参考值确定变异概率