（计算机软件与理论专业论文）遗传算法的改进及其在组合优化中的应用.pdf

华东师范大学硕士学位论文遗传算法的改进及其在组含优化中的席用 摘要 遗传算法“3 1 是一种概率搜索算法，其基本思想是模拟生物进化过程。由于遗传算法具 有不受搜索空间的限制性假设的约束，不要求解空间有连续性、可导等性质，且刮有并行性， 目前它在许多领域得到了，、泛的运用。 组合优化”( c o m b i n a t o r i a lo p t i m i z a t i o n ) 研究那些禽有有限个可行解的、日常生活中 ( 尤其是工程设计中) 大量存在的问题。典型的组合优化问题包括：旅行商( t s p ) 问题、车 间流水作业调度问题等。本文主要研究对遗传算法的改进算法及这些改进算法在组合优化上 的应用。 本文对遗传算法的理论、优化及应崩进行了一些研究与分析l 作。首先，介绍了遗传算 法基础原理模式定理，并分析了其在维染色体编码方案上的适用性：其次介绍了遗传 算法的理论基础，对诸如：未成熟收敛、遗传漂移及如何保持种群的多样性等有关问题作了 探讨；同时介绍了一些常见的改进方法，诸如：混合遗传锋法、基于基周库的改进遗传算法、 自适应遗传算法和小生境技术和共享函数等。针对标准遗传算法中初始种群产生的随机性， 在借鉴基因库思想”“的基础上，本文提出了一种基于基闻库的模拟退火混合遗传算法。这 种改进遗传算法具有以卜优点： l ，基于基因库和单亲遗传算法生成的初始种群。单亲遗传算子使用了基冈痒中的优质基 因，使得初始种群中个体具有的优质基因比随机产生个体的优质基冈要多，种群中每个 个体都十分接近晟优个体。冈此它 j 在种群演化较易产生最优解。 2 利用模拟退火算法较强的局部搜索能力，加快了算法的收敛速度，同时也提高了得到的 全局最优解的可靠性。 同时，将这种改进算法应用丁求解经典的货郎担( t s p ) 问题；试验结果表明：改进算 法具有更好的收敛性，而且算法收敛速度快、收敛稳定性更好；且得到了目前该问题的最优 解。 在上述改进的基础上，针对标准遗传过程中交叉概率和变异概率固定不变所带来的局限 性”“，本文进一步提出了一种基于基因库的自适应遗传算法；使遗传过程中遗传算子能 根据种群的集中程度自适应变化。这种改进遗传算法具有以下优点： 1 基于基因库和单亲遗传算法生成的初始种群中每个个体都十分接近晟优个体，它们具有 的优质基因比随机产生个体的优质基因要多，种群演化较易产生最优解。 2 遗传过程中遗传算子根据适应值集中程度，白适应地变化；确保了种群向性能好的方向 演化，因此加快了算法的收敛速度。 同时，还将这种改进算法应用丁i 求解流水作业排序问题；试验结果表明：改进算法在收 敛速度、收敛稳定性上有了较大改进：并在执行效率上比改进前的算法有了显著的提高。最 后，利用压缩映射原理和有限m a r k o v 链原理分别对两种改进算法进行了收敛性分析。 关键字：遗传算法，基冈库，模拟退火混合遗传算法，自适应遗传算法 华东师范大学硕士学位论文遗传算法的改进及其在组合优化中的应用 a b s t r a c t g e n e t i ca l g o r i t h m ”。1i sa s e a r c h i n gm e t h o du s i n gp r o b a b i l i t ya n di t sb a s i ct h e o r e mi st o s i m u l a t et h eb i o l o g ye v o l u t i o n f o ri t sf e wl i m i t a t i o no nt h ep r e s u m p t i o no f t h es o l u t i o ns p a c e ，g a d on o tr e q u i r et h es o l u t i o ns p a c et ob ec o n t i n u o u sa n dd e r i v a b l e ，a n db u i l t - i np a r a l l e l i s mm a k ei ta u s e f u lm e t h o di nm a n ya r e ae x t e n s i v e l y c o m b i n a t o r i a lo p t i m i z a t i o n f o c u s e so nt h ep r o b l e m s ，w h i c hh a v ef i n i t ef e a s i b l es o l u t i o n o re x i s tl a r g e l yi nl i f e ，e s p e c i a l l yi nt h ed e s i g n i n gp r o j e c t t h ec l a s s i cc o m b i n a t o r i a lo p t i m a l p r o b l e mi n c l u d e st h et r a v e l i n gs a l e sp r o b l e ma n df l o ws h o ps c h e d u l i n gp r o b l e m ，a n ds oo n t h i sa r t i c l ef o c u s e so nt h er e s e a r c ho fi m p r o v i n gt h eg e n e t i ca l g o r i t h m ，a n di t sa p p l i c a t i o ni nt h e c o m b i n a t o r i a lo p t i m i z a t i o n t h i sa r t i c l eh a ss o m er e s e a r c ha n da n a l y s e sa b o u tt h et h e o r y , o p t i m i z a t i o n ，a n da p p l i c a t i o no f g e n e t i ca l g o r i t h m f i r s t l y w ei n t r o d u c e dt h eb a s i cp r i n c i p l eo fg e n e t i ca l g o r i t h m - - s c h e m a t a t h e o r e m ，a n da n a l y z e di t sa p p l i c a b i l i t yt ot h ec o d e d s c h e m eo f o n ed i m e n s i o n a lc h r o m o s o m e ；t h i s a r t i c l eb r i e f l ys u m m a r i z e st h er a t i o n a l e so fg e n e t i ca l g o r i t h ma n dg i v e sa ni n t e n s i v ed i s c u s s i o n a b o u ts u c ha st h ep r e m a t u r ec o n v e r g e n c e g e n e t i cd r i f t i n gh o wt ok e e ps o c i e t yd i v e r s i t y , a n ds o o n a ts a m et i m et h ea r t i c l ei n t r o d u c e ss o m ei m p r o v e dm e t h o d s s u c ha s ：h y b r i dg e n e t i c a l g o r i t h m ，i m p r o v e dg e n e t i ca l g o r i t h mb a s i n go nt h eg e n eb a n k ，a d a p t i v eg e n e t i ca l g o r i t h m ， n i c h ea n ds h a r i n gf u n c t i o n ，a n ds oo n c o n s i d e r i n gt h er a n d o m i c i t yw h i c ht h eb a s i cg e n e t i c a l g o r i t h mp r o d u c e st h eo r i g i n a lp o p u l a t i o n ，w ed e s i g n e das i m u l a t e da n n e a l i n gh y b r i dg e n e t i c a l g o r i t h mb a s e do nt h eg e n eb a n k “4 1 j ，a n da p p l i e dt h i sa l g o r i t h mt os o l v et h ec l a s s i c a lt s p p r o b l e m t h ei m p r o v e dg e n e t i ca l g o r i t h mh a sf o l l o w i n ga d v a n t a g e s ： 1 t h ei n i t i a lp o p u l a t i o np r o d u c e db yt h eg e n eb a n ka n dp a r t h e n o - g e n e t i ca l g o r i t h m f o rt h e p a r t h e n o - g e n e t i co p e r a t o rp r o d u c et h ei n i t i a lp o p u l a t i o nb yt h ee x c e l l e n c eg e n ei ng e n eb a n k ， t h ei n d i v i d u a io ft h ei n i t i a ip o p u l a t i o nh a sm o r et h ee x c e l l e n c eg e d et h a nt h ei n d i v i d u a 【 w h i c hw a sp r o d u c e dr a n d o m l y e v e r y o n eo ft h ep o p u l a t i o ni ss oc l o s et ot h ew h o l eo p t i m a l s o l u t i o n , s ot h e yc a np r o d u c et h eo p t i m a ls o l u t i o nd u r i n gt h ep o p u l a t i o ne v o l v i n gq u i c k l y 互i ts p e e dt h ec o n v e r g e n c eo fa l g o r i t h mb yt h es t r o n gl o c a ls e a r c h i n go ft h es i m u l a t e d a n n e a l i n ga l g o r i t h m ，a n da l s oi n c r e a s et h er e l i a b i l i t yo ff i n d i n gt h ew h o l eo p t i m a ls o l u t i o n a ts a m et i m e ，w ea p p l i e dt h i sa l g o r i t h mt os o l v et h ec l a s s i cc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ， t r a v e l i n gs a l e sp r o b l e m t h er e s u l t ss h o w e dt h a tt h ei m p r o v e da g o r i t h mh a db e n e rc o n v e r g e n t p r o p e r t y ；a n dc o n v e r g e n ts p e e di sm o r eq u i c k l y ；a n dc o n v e r g e n ts t a b i l i t yi sb e a e r t h ea l g o r i t h m a l s of o u n dt h eb e s ts o l u t i o nn o w f o rt h el i m i t a t i o nb r o u g h tb yt h ei n v a r i a b i l i t yo fc r o s s o v e rp r o b a b i l i t ya n dm u t a t i o n p r o b a b i l i t yd u r i n gt h ee v o l u t i o n a lp r o c e s s 鼍w eb r o u g h tf o r w a r da ni m p r o v e da d a p t i v eg e n e t i c a l g o r i t h mb a s e do nt h eg e n eb a n k i tm a k e st h eg e n e t i co p e r a t o rt oc h a n g ew i t hc o n c e n t r a t e d d e g r e eo f p o p u l a t i o na d a p t i v e l y t h ei m p r o v e dg e n e t i ca l g o r i t h mh a sf o l l o w i n ga d v a n t a g e s ： 1 t h ei n i t i a lp o p u l a t i o np r o d u c e db yt h eg e n eb a n ka n dp a r t h e n o - g e n e t i ca l g o r i t h m e v e r y o n e o ft h ep o p u l a t i o ni ss oc l o s et ot h ew h o l eo p t i m a ls o l u t i o n t h ei n d i v i d u a lo ft h ep o p u l a t i o n h a sm o r et h ee x c e l l e n c eg e n et h a nt h ei n d i v i d u a lw h i c hw a sp r o d u c e dr a n d o m l y s ot h e yc a n p r o d u c et h eo p t i m a ls o l u t i o nd u r i n gt h ep o p u l a t i o ne v o l v i n gq u i c k l y 2 d u r i n gt h eg e n e t i cp r o c e s s ，i tc h a n g e da d a p t i v et h eg e n e t i co p e r a t o rb a s i n go nt h e 华东师范大学硕上学位论文遗传算法的改进及其在组合优化中的应用 c o n c e n t r a t e dd e g r e eo ff i t n e s s i ti n s u r e dt h ep o p u l a t i o ne v o l v e di nt h ed i r e c t i o no fe v o l v i n g i n t ot h ei n d i v i d u a lw i t hb e t t e rp r o p e r t y s oi ti n c r e a s e dt h ec o n v e r g e n ts p e e do fi m p r o v e d a l g o r i t h m a ts a i l q et i m e ，w ea p p l i e dt h i sa l g o r i t h mt os o l v et h ef l o ws h o ps c h e d u l i n gp r o b l e m t h e r e s u l t ss h o w e dt h a tc o n v e r g e n ts p e e do f t h ei m p r o v e da l g o r i t h mi st n o t eq u i c k l y ；a n dc o n v e r g e n t s t a b i l i t yi sb e t t e r t h er u n n i n ge f f i c i e n c yo ft h ei m p r o v e da l g o r i t h mi sm u c hb e t t e rt h a ni to ft h e o r i g i n a la l g o r i t h m i nt h ee n do ft h i sa r t i c l e , w ea n a l y z e dr e s p e c t i v e l yt h ea s t r i n g e n c yo ft w o i m p r o v e da l g o r i t h m sb yu s i n gt h ep r i n c i p l e so f c o n s t r i n g e n tm a p p i n ga n df i n i t em a r k o vc h a i n k e yw o r d s ：g e n e t i ca i g o r i t h m ，g e n eb a n k ，s i m u l a t e da n n e a l i n gh y b r i dg e n e t i c a l g o r i t h m ，a d a p t i v eg e n e t i ca l g o r i t h m v 华东师范大学硕士学位论文遗传算法的改进鼓其在组合优化中的应用 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在 文中作了明确说明并表示谢意。 作者签名；望龇 日期：础：! 兰：q 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名：瓣导师签名：3 ，】j 专 日期：互堂：! 兰! ；日期：圭竺垒：兰 毕东师范人学坝i j 学位瞳殳遗 算法的改j f 技j c n 纽台仉化r 一的m 州 第一章绪论 本章主要介缁了基本遗传算法及其基本片j 语雨i 特点；以及当前组台优化问题求解的研 究现状，并对本文的研究内容作了初步介绍。 1 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) ”是进化算法中发展最快和最为有效的 一种算法。1 9 5 2 年，美国m i c h i g a n 大学的h 。】l a n d 教授及其同事首先提出了g a 的基本思 想，并于6 0 年代末期形成了遗传算法的数学框架模式理论。他们研究的目的一力面是 抽象出自然系统中自适应机制并加以严格解释和分析；另一方面是设计具有这种机制的人 _ 系统和相应软件。八十年代后，g a 引起了国际学术界的普遍重视。目前，它已成为人r 智能中一个重要领域，是一种十分重要的优化算法。 遗传算法目前已在各个领域得到了广泛的应用，大量的应用结果证明了遗传算法具有 很强的优化能力。一个标准的遗传算法的处理过程如下图所示： 图1 1 标准遗传算法的基本流程 可见，它是通过模拟自然界的生物进化过程，将所求问题的解用编码串( 也称为“染 色体”) 来加以表示，井形成一组代表该优化问题的一些可能解的集合，我们称为种群：然 后利崩相应的遗传仿生葬千( 选择、交叉、变异) 作用丁_ 种群中的各个染色体，存优去劣， 反复迭代，最终得到包含问题的最优解染色体的优良种群，达到优化目的。 遗传算法处理过群中包禽了四个基本耍索，即：编码，适麻值计算，基阏操作掉f 和 g a 控制参数。这些要素相配合，支配着遗传算法的收敛速度和求出的解的优良度。 华东师旭凡掌i 学位论殳遗传算法的改逊投! l n 组合优化中的j 、计h 1 1 1 简单遗传算法 遗传算法可以形式化描述如r ： g a = ( p ( o ) ，i v , t , s , g , p , f o 这里j p r 叫= 向l f 0 土d 2 r o ，f o ，“表示初始种群： i = b = f o ，1 ，7 表示民度为l 的二进制串全体，称为位串空间； n 表示种群中宙有的个体的个数，即种群规模；l 表示二进制串的k 度； s ：i “一i 、表示选择策略； g 表示遗传算子，通常它包括选择算子0 。：i i 、交叉算子0 。：i 卜i i 和变异算 子0 i ：i x i ； p 表示遗传算子的操作概率，包括选择概率p ，、交叉概率p c 、和变异概率p ： f ：i r 是适应度函数； t ：i “一 0 ，1 ) 是终 e 原j j ! i l 。 1 1 2 基本用语 由丁遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算方法，所以遗 传算法中经常使用有关自然进化中的一些基本用语。了解这些用语对于讨论和应用遗传算 法是十分必要的。 在遗传算法中，首先要将搜索空间映射为遗传空问解的表达形式，这一操作过程称为 编码，其相反过程称为解码。对给定一个优化问题，没目标函数为f - f ( x ) ，x q ，f r 。 求k 。使得( 不失一般性，假设最大优化问题) ： 2 f i x o ，, ) 2 m a x f ( 磊) 其中x 为自变最，q 为f 的定义域，x 既可以是数字，也可以是符号；f 为实数，是 解的优劣程度或适应值的一种度量；f 为解空间x q 到f r 的一个映射。 对编码的基本要求是，两个空间的解要一一对应且编码简明有效。我们用一定比特数 的0 ，l 一进制码对自变量x 进行编码形成染色体( c h r b m o s o m e ) 或个体( i n d i v i d u a l ) ， 每一染色体代表优化问题的一个特定解，染色体上每一个编码位称为基冈。随即产生r 1 个 个体组成个初始种群p ( 0 ) ( p o p u l a r i o n ) ，该种群为给定问题的一些可能解的集合，一 般地说。初始种群p ( 0 ) 的适应值都很差，离最优解还有相当人的差距。值得一提的是，g a 不仅町以对数值符号集组成的字符串进行操作，还能够直接对结构对象进行操作，如由集 合、序列、矩阵、树结构、图表等。冈而，遗传算法在众多领域内得剑rj 泛的应h ； 。 按编码规! j ! | j 斛码，：博种群p ( t ) 巾每一个体的染色体编码为所对应的l l 变￥：xr f 一的各个 1 仁东师范人掌坝i 学位论卫 遗传算法的改进发j o n 组合优化中府h 】 参数x t ，x z ，x 一，根据适应度函数计算各自的适应倩工，i = l ，2 ，n ，工越人 表示该个体适应能力越强。适应值为种群进化时的优选提供了依据。 进化过程的优胜劣汰处理称为基因操作是模拟自然界的生物有性繁殖及进化所得到 的。一个简单的遗传算法( s g a ) 主要包含了3 个基因操作算子：选择( s e l e c t i o n ) ，交义 ( c r o s s o v e r ) 和变异( m u t a t i o n ) ，它们的土要作用是通过相互配合，从种群中选择出父 辈的优良染色体，再经过交叉、变异形成新的种群个体。显然，选择策略和交叉变异方式 都将直接影响g a 的处理结果。目前普遍采用的策略都是以和适应值成上 比例的概率来进行 选择，一般称为轮盘转策略或赌盘策略。 整个赌盘被分为大小不同的一些扇面。赌盘的指针指向各个扇面的概率与各个扇面的 圆心角大小成正比；圆心角越人；停在该扇面的可能性也越人；圆心角越小，停在该扇面 的可能性也越小。与此类似，在遗传算法中，整个种群被各个个体所分割，各个个体的适 应值在全部个体的适应值之和中所占比例也大小不一，这个比例值瓜分了整个赌盘盘面， 它1 f j 也决定了各个个体被遗传到下一代种群中的概率。 赌盘策略的具体执行过程楚： 先计算出种群中所有个体的适应值的总和。 其次计算出每个个体的相对适应值的大小，它既为各个个体被遗传到下一代种群中的 概率。 最后再使用模拟赌盘操作( 即产生0 道1 之间的随机数) 来确定各个个体被选中的次 数。 ( 1 ) 选择( s e l e c t i o n ) ，月 以形荟 概率大小从“k ) 中选出新一代种群作交配池。由于选择概率p “工因 而选择操作意味着适应于生存环境的优良染色体将有更多地存活机会，从而使优良特 性得以遗传继承，选择是遗传算法的关键和特色，它体现了自然界中生物进化过程中 的“优胜劣汰，适者生存”的思想。 ( 2 ) 交义( c r o s s o v e r ) 从选中的种群即交配池随机选择出一对染色体，并随机产生一个交配位，将双亲的染 色体在此基因值交义，部分地交换烈亲染色体，其操作过程如下： 串i ：i00 l l00l新串i ：l00010ii 单点交叉 卜 串2 ：0l0ol0 tl 新串2 ：010l l00 1 交义操作通过对破采染色体结构的分裂和露射，从而使种群产生新的基因组合它摸 拟生物演化过科中的繁衍现象，体现r 白然界中信息交换的思想。 ( 3 ) 变异( m l , t a t i o n ) # 东帅范大学坝i 学f t 论且 遗传算法的改进歧打组合优化【 1 的j 衄用 按一定的给定概率p 。对种群中每一染色体的各个基冈何进行变异操作，若采_ l j 一进制 编码，则变异操作为取反运算，即。一i ，1 0 。变异操作在g a 中起刮了局部搜索作用。 ( 4 ) g a 控制参数 控制g a 性能的主要参数是种群尺寸和遗传操作概率。g a 对种群尺寸即：种群中个体数 的殴定是十分敏感的。从维护种群中个体的多样性，以防算法陷入局部最优的角度出 发，种群尺寸越人越好，但这样除了明显增加计算量外还有可能影响个体竞争。遗传 操作概率包括：交叉概率和变异概率。其设定尚未有明确的理论指导，多数与具体问 题有关。其中，变异概率的选择最为凼难，稍有不适便会产生不成熟收敛。 1 1 3 遗传算法的特点 我 f j 可以把任何抽象的任务都看作是一个求解寻优的问题，而问题求解又可看作是对 解空间的搜索。对于小的解空间，经典的耗尽搜索方法足以解决问题；然而相对较大的空 间，就需要采用更高级的自适应寻优技术，其主要应用领域是复杂的1 e 线性优化问题。尽 管遗传算法可归类于概率算法，但它不同于随机算法，它把定向搜索与随机搜索有机地结 合起来，正因如此，遗传算法强于已有的定向搜索方法和随机搜索方法”“。 遗传算法的另一个重要特点是使用一个潜在解的种群来空间。而传统方法一般使用单 点来搜索解空间，例如“爬山”法使用的单点迭代改进技术，由于它们是一个随机的初始 单点出发来寻优的，因而它依赖于初始点的选择，其寻优结果往往是局部优化的点。与此 相对照，遗传算法保持一个潜在解的种群实现了多个方向上的搜索同时，在搜索过程中 鼓励各个不同方向上信息的结合和交流。代表问题解的种群经历了一个模拟进化过程，所 得解通常是全局晟优的。 遗传算法与传统的算法相比具有很多不同之处，但其最主要的特点体现在卜述两个方 面1 ”： ( 1 ) 自组织、白适应和自学习性( 智能性) 遗传算法的智能性包括自组织、白适应和自学习性等。应用遗传算法求解问题时，在 确定了编码方案、适应度函数及遗传算子以后，算法将乖j 用演化过程中获得的信息臼行组 织搜索。由于基于自然的选择策略为适者生存，故而适应值大的个体具有较高生存概率。 通常适应值人的个体具有与环境更适应的基因结构，再通过交叉年变异等遗传操作就可能 产生于环境更适应的基冈结构。遗传算法这种自组纵、自适应的特征也同时赋予了它能根 据环境变化自动发现环境特性和规律的能力。 自然选择消除了算法设计过程中的一个最人障磷，即：事先需要描述问题的全部特点， 并说明针对问题的不同特点算法应采取的措施。下是，利用遗传算法我们可以解决那些结 构尚无人能理解的复杂问题。 ( 2 )本质并行性 遗传算法的本质并 什表现在酣个方丽：一是遗传算法是内在并行的( i n h e r e n l ) ，即 4 半彖师他人学坝i 学位论文 遗传算法的改进技j 再：组合抛化巾的埘用 遗传算法本身非常适合大规模并行。最简单的并行方式是止几白台甚至数干台计算机各自 进行独立种群的演化计算，运行过程中甚至不进行任何通讯，等4 运算结束时才比较，选 取最佳个体，这种并行处理方式对并行系统结构也没有什么限制和要求。可以说，遗传算 法适合在目前所有的并行机或分布式系统上进行并行处理，而且对其运行效率没有太大的 影响。二是遗传算法的内含并行牲( j m p l i c i tp a r a l l e lj s m ) ，由丁遗传算法采用神群的方 式组织搜索，从而它可以同时搜索解空间内的多个区域。并相互交流信息，这种搜索方式 使得它虽然每次只执行与种群规模n 成正比例的计算，而实质上已进行了大约0 ( n ) 次有 效搜索。这使得遗传算法能以较少的计算获得较大的收益。 1 2 当前遗传算法的研究现状 遗传算法是在二十世纪六七十年代创立的，但在当时并没有受到普遍的重视。其主要 原因一是因为当时这些方法本身还不成熟；二是由于这些方法需要较大的计算量，而当时 的计算机还不够普及而且速度也跟不上要求，这样便限制了它们的使用；三是当时基于符 号处理的人工智能止处于其顶峰状态，使得人们难以认识到其他方法的有效性及适应性。 到八十年代，人们越来越清楚地意识到传统人工智能方法的局限性，并且由于计算机速度 的提高以及并行计算机的普及，已使得遗传算法对机器速度的要求已不再是制约其发展的 因素。由于遗传算法的不断发展及其在一些应用领域内取得的成功，使得它表现出了良好 的应用前景。 当前遗传算法的研究课题主要集中在以下凡个方亟】1 , 1 3 1 优化搜索方法的研究 迄今为i p ，优化问题的求解仍在遗传算法研究中占很人比重，诸如t s p 等组合优化问 题一直是遗传算法十分活跃的研究课题。尽管遗传算法比其他传统搜索方法有更强的鲁棒 性，但它更擅长全局搜索而局部搜索能力却不足。研究发现，遗传算法可以用极快的速度 达到最优解的9 0 左右，但要达到真正的最优解则要花费很长时间。一些对比实验还表明， 如果兼顾收敛速度和解的品质两个指标，单纯的遗传算法方法未必比其他搜索方法更优越。 为此，除了要进一步改进基本理论和方法外，还要采用和神经网络、模拟退火和j 专家系统 等其他方法相结合的策略。许多研究结果表明，采用这种混和模型可有效提高遗传算法的 局部搜索能力，从而进一步改善其收敛速度和解的品质。此外，探明如何能充分发挥遗传 算法优越性的问题性质和类型也是十分有意义的r 作。 2 学刊系统的遗传算法研究 蕈基传算法的学习系统现今面临的课题有：1 ) 适合遗传算法的高层次知识的表示： 2 ) 更通用的基t 语义的操作；3 ) 搜索能力的分析：4 ) 更有效的体现和变动环境相互作用 的适应度函数导入等。 3 卡物进化与遗传算法的研究 n f 纪上从生物进化的角度石，现拒的遗传算法理论框架尚处j 恢糖核酸( r n a ) 的水平， 牛东州范人学帧i 学化沦文 遗传算法的改进驶强杠魂i 合优化中柏府朋 模拟从r n a 向d n a 的进化过群和机制，从而提高遗传算法的性能是值得注意的研究课题。 4 遗传算法的并行分布处理 遗传算法由丁其种群性操作，所以本质上具有很好的并行处理特性。尤其是遗传算法 中各个个体的适应值计算( 这是遗传算法中最人的计算开销) 可独立进行而彼此间无需任 何通信，所以井行处理效率是很高的。闼此，设计有效的并行遗传算法及相应的实现系统 对于遗传算法的理论研究和应用研究都是十分重要而迫切的任务。 5 人工生命与遗传算法的研究 实现人工生命的手段很多，遗传算法在实现人r 生命中的基本地位和能力究竟如何， 这是值得研究的课题。 由丁遗传算法的整体搜索策略和优化计算时不依赖于梯度信息，所以它尤其适台于处 理传统搜索方法难以解决的高度复杂的非线性问题。它在组合优化、模式识别、机器学习、 规划策略、信息处理和人工生命等领域的麻用中展示出优越性和魅力，从而也确定了它在 2 l 世纪的智能计算技术中的关键地位。 1 3 本文的研究内容 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 埘研究那些含有有限个可行解的、日常生活中 ( 尤其是工程设计中) 人量存在的问题。组合优化的特点是可行解的数量有限。虽然从理 论上讲这种有限问题可以通过简单的枚举找到最优解，然而在实际情况中通常无法实现。 特别当实际问题的规模很大，可行解的数量i 常多时更是如此。典型的组合优化问题包括： 旅行商( t s p ) 1 6 7 题、车间流水作业调度问题等。 在过去的1 0 年中，遗传算法受到组合优化界人士越来越多的关注；有超过1 0 0 篇研究 遗传算法或者将遗传算法应用于组合优化等不同领域的博十论文发表；组合优化问题是遗 传算法研究界的重要研究对象。遗传算法在许多难以解决的问题上表现出很强的能力，并 得到了很有价值的解。 对于t s p 问题近年来一直有一些学者在采用各种改进遗传算法来解决此问题。主要 有f 面一些： 1 9 9 6 年，s a n g i tc h a t t e r j e e 等在文献 3 5 1 中提出了采用一种由无性繁殖结合一般变异手 段的改进方法。由于算法采用了“合法”交叉的固定状态，避免了一些染色体编码的中间 步骤；算法在求解t s p 问题求解上得到了较好的结果。但由于采用的无性繁殖类似f 单亲 遗传，算法的收敛稳定性难以保证。 1 9 9 7 年，解伟等舀：文献 2 7 1 中分别用g a 耵lh g a 求解t s p 问题；并对两种算法的求 解结果进行了对比。绵犍表明：h g a 在求解该问题时具有较大的优越性。 2 0 0 1 年，g a n d a lj a y a l a k s h m i 等在文献【4 4 j 中用三种不同的启发式方法结合泄羁j 遗传 算法求二类t s p 问题。f l ! 算法不同的启发式方法对虑于求解不同类的t s p 问题，贝育一定 的局限一陛。 毕东帅范人学坝 学位论殳遗传算法的改进投l n 绁台优化中的j h 开 2 0 0 2 年，谢胜利等在文献 1 2 1 刖浓度控制选择策略、贪婪交叉锋子平l l 启发式倒位变 异算f 来改进算法求解t s p 问题。但该算法只是对遗传算子进行了一些改进，初始种群还 是随机化产生，对算法性能的提高程度有限。 2 0 0 3 年，胡能发等在文献【7 忡提出了构建“基因库”改进遗传算法，并将其应用到求 解t s p 问题。该算法在求解中表现出了根好的效果，并得到了当时的最好解。但其群体演 化采用了标准遗传算法的群体演化方法，这阻碍了基因库在群体演化中的应用。 对于流水作业排序问题，近来也有很多用改进遗传算法求解该问题的相关文章频频在 各种权威杂志或国际会议上发表。主要如f 一些： 1 9 9 7 年，t s u j i m u r a 等在文献【5 2 1 中对三种编码方式：基于持续的表示、随机键表示和 基于丁序的表示对求解j s p 问题进行了比较研究。 2 0 0 0 年，王锡禄等在文f 酞 5 3 1 给出了优化模型和遗传算法求解j s p 的一般算法框架。 但它对遗传算法求解j s p 的内部具体实现方法探讨很少。 2 0 0 2 年，谢胜利等在文献 4 2 1 采用分段结构染色体编码、可行调度判断和应用修正 算子等改进算法求解j s p 问题。该算法具有较好的稳定性；但遗传算子和修正算子的选取 需要经验或反复试验。 2 0 0 3 年，c h ib i n 等在文献f 1 9 1 中提出了两种改进的自适应遗传算法及相应的编码方 案；并比较了6 种不同算法求解j s p 问题的情况。文章得出结论：自适应遗传算法优于非 自适应遗传算法。 本文在总结前人所做上作的基础上，研究了遗传算法改进及其在求解组台优化问题中 的应用。本文所做的主要t 作如下： 1 在借鉴了基因库思想的基础上，州模拟退火混合遗传算法对原有的群体演化算法进行 了改进：并将改进算法应用丁- 求解t s pc h i n a1 4 4 问题，且得到了目前该问题的最优 解。 2 在上述改进的基础上，进一步提出了基于基因库的自适应遗传算法，使遗传过程中遗 传算子能根据种群的集中程度自适应变化：并将改进算法应用子求解流水作业排序问 题，改进后算法在运行效率上比改进前算法有了显著的提高。 3 将基因库思想由原来求解t s p 问题，拓广到求解流水作业排序问题：为进一步将该改 进方法应用到其他组台优化闯题的求解做了有用的探索。 4 编程实现了两种改进算法，井进行了实验分析；同时还对两种改进算法分别进行了理 论上的收敛性分析，为迸一步改进算法作了一些理论上的准备。 其中：针对标准遗传算法中初始种群产生的随机性，在借浆基因库思想”的基础上， 本文提出了一种基于基阕库的模拟退火混合遗传算法。这种改进遗传算法具有以f 优点： 1 基丁_ | 基冈库和单亲遗传算法生成的朗始种群，使得初始种群中个体具有的优质基冈比 随机产生个体的优质基网要多，种群中每个个体都十分接近最优个体。田此，它们在 种群演化较易产生展优解。 华东帅范人学坝i j 学位论文遗传算 上的改进艟其n - 鼬合优化- p 的成h 2 利用模拟退火算法较强的局部搜索能力，加快r 算法的收敛速度，同时也提高了得剑 的全局最优解的可靠性。 在上述改进的基础上，针对标准遗传过程中交义概率和变异概率固定不变所带来的局 限性”“”，本文进一步提出了一种基于基因库的白适应遗传算法：使遗传过程中遗传算子 能根据神群的集中程度自适戍变化。这种改进遗传算法具有以f 优点： 1 基于基因库和单亲遗传算法生成的初始种群中每个个体都十分接近最优个体，它们具 有的优质基因比随机产生个体的优质基因要多，因此，种群演化较易产生最优解。 2 遗传过程中遗传算子根据适应值集中程度，自适应地变化；确保了种群向性能好的方 向演化，因此加快了算法的收敛速度。 在第四章和第五章分别对两种改进算法进行了编程实现，并应用于求解t s p 和流水作 业排序问题，结果与目前所提出的一些性能较优的算法m 进行了比较。在最后还对两种改 进算法分别进行了收敛性分析。 1 4 本文的内容安排 本文内容安排如下： 第一章绪论，主要介绍了基本遗传算法及其基本用语和特点，以及当前组合优化问题求 解的研究现状；并对本文的研究内容作了初步介绍。 第二章遗传算法基本原理的研究与分析，主要对目前已有的一些遗传算法基本原理的研 究和分析进行了总结。首先分绍遗传算法研究的理论基础搂式定理，并剧模 式定理对一维染色体编码的遗传算法进行了分析；同时介绍了交叉和变异算子对 算法的影响以及遗传算法性能的评价方法；最后介绍了两个评价遗传算法的性能 指标。 第三章遗传算法常见的改进方法，主要介绍目前遗传算法一些常见的改进方法，包括： 改进的最佳保留策略、大变异操作和过滤操作等机制；以及自适应、模拟退火混 合、基于基冈库和基于小生境技术等的改进遗传算法。 第四章改进的基丁基冈库混合遗传算法和t s p 问题，主要对模拟退火捏合遗传算法的改 进进行了研究，并在借鉴基因库思想的基础上提出了一种改进的基于基因库混合 遗传算法；同时将改进算法用f 求解经典的t s p 问题，并对实验结果进行了比较 和分析。 第五章改进的基于基因库自适应遗传算法和流水作业排序问题，主要介绍了自适戍遗传 算法的改进；在借鉴基因库思想的基础l 提出了一种改进的基丁基冈库白适应遗 传算法，并将改进算法用r 求解经典的流水作业排序问题。 第六章遗传算法收敛性分析，主要埘常见的遗传算法的收敛性定义、以及分析原理进行 了总结；并住此基础上，对本文中提出的两种改进算法分别运用乐缩映射原理和 有限m a r k o v 链原理进行了收敛性证明。 8 毕东帅范人学顺1 j 学托睑文遗传算法的改进殷j l 订纽台优t 中的应用 第二章遗传算法基本原理的研究与分析 本章主要对目前已有的一些遗传算法基本原理的研究和分析进行了总结。首先介纠遗 传算法研究的理论基础模式定理，并j f = i 模式定理对一维染色体编码的遗传算法进行了 分析；同时介绗了交叉和变异算子对算法的影响以及遗传算法性能盼评价方法；最后介绍 了两个评价遗传算法的