（计算机应用技术专业论文）遗传算法中自适应进化与复合交叉的应用研究.pdf

摘要 遗传算法作为一种通用性好、鲁棒性强的启发式随机化搜索优 化算法，广泛地应用于自动控制、组合优化、图像处理、机器人、 人工生命、机器学习、人工智能和工程设计等领域。尤其是当搜 索空间很大、非常复杂或对问题领域的先验知识很少时，使用经 典搜索工具如枚举法、启发式方法等不适宜的情况下，遗传算法 提供了一种效率高且有效的求解问题的合理方法。 本文首先较全面系统地介绍了目前国内外研究者在改进遗传 算法搜索性能方面进行的研究工作和取得的研究成果。接着提出 了一种基于个体相似度的遗传算法，新算法对标准遗传算法产生 子代个体( 交叉和变异) 的策略进行了修改，其基本思想是：当两 父个体相似度较低时执行交叉操作产生子代个体，父个体相似度 较高时则采用变异的方法产生子代个体。这样，一方面交叉产生 的优秀子个体将不经变异直接与其它子个体( 交叉产生的其它个 体以及变异产生的个体) 竞争而得以生存下来，而在标准遗传算法 中，交叉产生的优秀个体再历经变异，极有可能在变异过程中遭 到破坏而成为非优秀个体，从而影响算法的收敛性及收敛速度； 另一方面又避免了高相似度个体进行交叉而导致种群多样性的丧 失，从而一定程度上能抑制早熟收敛现象的发生。使用此改进的 遗传算法对多个b e n c h m a r k 测试函数在计算机上进行模拟求解， 将之与采用普通交叉变异策略的遗传算法的计算结果进行了对 比，证明该算法的有效性。然后将基于个体相似度的遗传算法应 用于图的度约束最小生成树构造问题，取得了令人满意的结果。 针对实数编码提出了一种通用的基于决策变量的复合交叉算子， 并将之用于多目标优化问题的求解，实验证明使用复合交叉算子 的算法对于多目标优化问题求解非常有效，一定程度上解决了高 维多目标优化问题在用遗传算法求解时收敛性差这一难题。 关键词：复合交叉相似度基于个体相似度的遗传算法 最小生成树度约束最小生成树问题 a b s t r a c t g e n e t i ca l g o r i t h mi sag e n e r a l ，r o b u s t ，r a n d o m i z e dh e u r i s t i c s e a r c h t e c h n i q u ew h i c h i s w i d e l ya p p l i e dt o a u t o c o n t r 0 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 ，i m a g ep r o c e s s i n g ，r o b o t s ，a r t i f i c i a ll i f e ， m a c h i n el e a r n i n g ，a r t i f i c i a li n t e l l i g e n c e ，e n g i n e e r i n gd e s i g na n ds oo n e s p e c i a l l yw h e np r o b l e ms e a r c hs p a c ei sv e r yl a r g e ，c o m p l i c a t e do r w ek n o wl i t t l ea b o u tp r o b l e mi na d v a n c e ，i ti s i n a p p r o p r i a t ef o r c o n v e n t i o n a ls e a r c ht o o l s ( s u c ha se n u m e r a t i o nm e t h o da n dh e u r i s t i c t e c h n i q u e ) t os o l v et h e s ep r o b l e m s ，b u tg e n e t i ca l g o r i t h mc a nd o e f f e c t i v e l ya n de m c i e n t l y a tf i r s t ，t h i sp a p e ri n t r o d u c e sr e c e n tr e s e a r c hw o r k sa n dr e s u l t s a b o u ti m p r o v i n gg a ss e a r c hp e r f o r m a n c e su pt on o w i nt h i sp a p e r , w ep r o p o s ea s i m i l a r i t y - b a s e dg e n e t i ca l g o r i t h m ( s b g a ) i tm o d i f i e s c r o s s o v e ra n dm u t a t i o ns t r a t e g yo fs i m p l eg e n e t i ca l g o r i t h m ( s g a ) w h e np a r e n t s s i m i l a r i t yd e g r e e ( s d 、i sl o w e r , c r o s s o v e ro p e r a t o ri s u s e dt og e n e r a t ec h i l d r e n ，o t h e r w i s em u t a t i o no p e r a t o ri su s e d o nt h e o n eh a n d ，s u p e r i o ri n d i v i d u a l s g e n e r a t e db yc r o s s o v e ro p e r a t o r n e e d n tg ot h r o u g hm u t a t i o na n dc a ns u r v i v ea f t e rc o m p e t i t i o n sw i t h o t h e ri n d i v i d u a l sg e n e r a t e db yc r o s s o v e ra n dm u t a t i o no p e r a t o r s b u t f o r s i m p l eg e n e t i ca l g o r i t h m s ，s u p e r i o ri n d i v i d u a l sg e n e r a t e db y c r o s s o v e r o p e r a t o rh a v et ou n d e r g om u t a t i o na n dm a yt u r nt ob e i n f e r i o ri n d i v i d u a l sa f t e rm u t a t i o np r o c e d u r e t h e ni n f l u e n c eg a s c o n v e r g e n c eq u a l i t y a n dc o n v e r g e n c es p e e d o nt h eo t h e rh a n d ， s b g ad o e s n ta l l o wh i g h e rs i m i l a r i t yi n d i v i d u a l st oc r o s s o v e r , s o p r e v e n tf r o mt h el o s s o fp o p u l a t i o n s d i v e r s i t yb yc r o s s o v e ra n d r e s t r a i np r e m a t u r ec o n v e r g e n c ei nac e r t a i ne x t e n t t h e nt h i sm o d i f i e d g e n e t i ca l g o r i t h mi sa p p l i e dt of i g u r i n go u ts e v e r a lb e n c h m a r kt e s t f u n c t i o n s ，a n dw ef i n dt h a ti to u t p e r f o r m sg e n e t i ca l g o r i t h mw h i c h d o e s n te m p l o ys i m i l a r i t yi n f o r m a t i o n a tl a s t ，w eu s et h ea l g o r i t h m t oc o n s t r u c td e g r e e - c o n s t r a i n e dm i n i m u ms p a n n i n gt r e ef d m s t ) o fa g r a p h o u re x p e r i m e n t a lr e s u l t sp r o v i d es t r o n ge v i d e n c et h a tt h e g e n e t i ca l g o r i t h me m p l o y i n gs i m i l a r i t y i n f o r m a t i o nt od e c i d e i i 瑚l d o m g r a p hd - m s tp r o b l e m st h a nr i v a l m e t h o d c h a d t e r4 曲8 钟i b e sa na l l - p u r p o s ec o m p o u n dc r o s s o v e rw h i c h o p e r a t e so nt 黼 。e a l - c o d e dd e c i s i o n v a r i a b l e s w h e na p p l i e dt o h i g h e r - d i m e n s i o n m u l t i 。o b j e c t i v eo p t i m i z a t i o np r o b l e m s ，i tp e r f o r m sv e r yw e l l 1 i i 翟 嫩g 移姐 赫即 _ 砉| 胁 = 囊 涨m 溉 ：軎，嚏则蛳鲫 掣a m 霉一 叠 g 舭 嚣一蒜一 _ 暑堍 湘潭大学 学位论文覆铷蛀声喽 本人郑重声明：所呈交的论文足本人在姑j j | j 的指导下独立进行研 变瘊敬褥瓣疆究威塞。狳了文。卜将溺热强檬浚写l 溪於瘫察努，奉论文 不包含任何其他个人或集体己经发表或撰写的成果作品。对本文的研 究做出显要贡献的个人或集体，均已在文中以骥确方式橼嚷。本人完 全意识到本声明的法律后果由率入承担。 佟卷签名：圆y 授 | 曩麓： ，降 月硼西 攀位论文版权使用授权书 本学位论文作街完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向阑家有关部门或机构送交论文的复印件和电子版， 允许论文被查阚程僚阅。本入授权滋潭大学爵潋将本学位论文翡全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复到手袋绦存饔汇绫本学经沦文。 保密口，在年解密蔚适用本授权书。 本学位论文属于 ， 不保密滔。 ( 请在以上棚应方框内- 打“4 ”) 佟畿签 导师签 舀麓：群年f # 露勋强 同期：如丫年，。月7 日 第一章引言 2 0 世纪6 0 年代以来，生物学中的进化论被广泛地应用于工 程设计、自动控制、函数优化和人工智能等领域中，形成了一类 新的搜索算法一进化算法( e 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 m s 。g a ) 、进化 策略( e v o l u t i o ns t r a t e g i e s ，e s ) 、进化规划f e v o l u t i o n a r y p r o g r a m m i n g ，e p ) 。这几类算法非常相似，它们的基本思想均源于 生物学家达尔文的“优胜劣汰、适者生存”的自然选择和生物进 化的理论，算法由一组随机生成的初始可行解出发，借助选择( 复 制) 、交叉( 重组) 和变异等遗传操作产生新代解群体，在这样的 迭代搜索过程中自动获取并积累解空间的有关知识，逐步向问题 的最优解或满意解逼近。 进化算法与其他优化搜索技术( 如梯度法、随机搜索方法、启 发式方法和穷举法等) 相比，进化算法具有简单通用、鲁棒性强、 逶予并行分毒处瑗以及应震蒎霾广等显蔫特点，奠定了它俸为2 l 世纪关键智能计算技术的地位。进化策略和进化规划针对连续变 量使用实数编码，变异算子楚产生后代的首要算予；遗传算法则 主要使惩二进制缡码，其产生后代的蓠簧舞子是杂交箕子。 丸十年代初为了促避这煞不同的模拟生物进 乞算法之闻的交 流，提出了进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 的概念，进化 计算现已成为“智能”与“优化”两个主题研究的新热点，出现 了遴纯诗算的繁荣。 随着遗传算法和进化计算研究热潮的兴起，人工智能再次成 为人们关注的焦点。有些学者甚至提出，进化计算是人工智能的 未来。葵礴点是，虽然我们不裁设计入王智能( 即用枧器代骛入豹 自然镄能) ，但我们可以利增进化通过计簿获得智能。蟊前进化计 算己和人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 、模糊逻辑 ( f u z z yl o g i c ，f l ) 棚结合，产生了一门新的综合性的计算技术学科 诗算智戆( c o m p u t a t i o n a li n t e l l i g e n c e ，c i ) 。入王镪施已献传统 的基于符号处理的符号主义，向以神经网络为代表的连接主义和 以进化计算为代表的进化主义方向发展。 遗传算法是进化算法中产生最早、影响最大、应用也比较广 泛的一个研究方向和领域。目前在进化计算领域，遗传算法可以 说是最广为人知的进化算法，以遗传算法的研究与应用最为广泛 深入，在多目标进化算法( m u l t i o b j e c t i v ee v o l u t i o n a r ya l g o r i t h m s ， m o e a s ) 中g a 作为主要进化模型也是被采用最多的。它不仅包含 了进化算法的基本形式和全部优点，同时还具备若干独特的性能 f 5 】 在求解问题时，遗传算法首先要选择编码方式，它直接处 理的对象是参数的编码集而不是问题参数本身，搜索过程 既不受优化函数连续性的约束，也没有优化函数导数必须 存在的要求。通过优良染色体基因的重组，遗传算法可以 有效地处理传统上非常复杂的优化函数求解问题。 在所求解问题为非连续、多峰以及有噪声的情况下，能够 以很大的概率收敛到最优解或满意解，具有较好的全局最 优解求解能力。 v 对函数的几何特性无要求，针对某一问题的遗传算法经简 单修改即可适应于其他问题，或者加入特定问题的领域知 识，或者与已有算法相结合，就能很好地解决较复杂问题， 因而具有较好的普适性和易扩张性。 遗传算法的基本思想简单，运行方式和实现步骤规范，便 于具体使用。 监于遗传算法具有上述特征，一经提出即在理论上引起了高 度重视，并在实际工程技术和经济管理等领域得到了高度重视和 应用，产生了大爨的成功案例。 近年来，遗传算法不断地得到改进犟耩完善，并大量应用到涵 数优化、工程计算、自动控制、组合优化、机器人、人工生命、 机器学习、人工翘能等领域中，具有广阕的发展和应用前景，值 褥我稍进一步酶磷究窝探讨。 第二章遗传算法性能改进方法磷究概况 和本文主要工律 第一节遗传算法性能改进方法研究概况 遗传算法是一类借鉴自然界生物种类的遗传和进化过程褥形 成的一种自适应全局优化搜索算法，它的主要特点是群体搜索策 略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它戈 萁逶孀于处瑾蕊统搜索方法难良鳃决鳃复杂亵j 线经运题，鬻广 泛用于组合优化、机器学习、自适应控制、规划设计和人工生命 等领域，是2 1 世纪有关智能计算中的关键技术之一。遗传算法研 究酶兴起是在鞠年代寒秘年代初期，但它酶历史起源霹遗溯 到6 0 年代。早在1 9 6 7 年b a g l e y 就提出了“遗传算法”一词并发 表了第一篇有关遗传算法应用的论文【l 。1 。从6 0 年代至7 0 年代中 期，这一阶段对遗传算法的研究主要侧蹙予对一些复杂操作的研 究，如自动博奔、生物系统模拟、模式识瘸毒妥丞数优化等，这是 一个无明确目标的发展时期，缺乏带有指导性的理论和计算工具 的开孛石。这种现象直到7 0 年代中期由于j h o l l a n d 和d ej o n g 的 创造链磅变成暴麓发表才褥叛改蕊。遗传算法戆基本瑾论窝基本 方法耀初由美国m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年首先提 出1 9 】，同年d ej o n g 4 针对他提出的5 个测试函数( f 1 ，f 5 ) 【1 对桥准 遗传算法s g a ( s i m p l eg e n e t i ca l g o r i t h m ) 的基本参数及其部分变 落形式的搜索性麓进行了缁羧的分析磷究。献越，遗传算法不断 得到改进和提高，并已在实际应用领域中取得了臣大的成功，目 前它已成为进化计算的一个研究热点。 对于标准遗传簿法s g a ，其仍然存在一些缺陷，鼬：早熟收 敛、收敛速度过慢等。针对s g a 的这些缺点，大量专家学者提豳 了许多改进的遗传算法，能有效地克服或减轻以上的缺点。 w h i t l e y f2 1 汲为，g a 中最蓬要的两个闲素就是“种群多样性” 和“选择压力”。选择压力过大是早熟收敛( p r e m a t u r ec o n v e r g e n c e ) 的一个重要原因，过大的选择压力鼹然可以加快算法的收敛速度， 翡会傻穗群中适应度傻较低麴个体迅速“臻亡”，秘蓑懿多样涟遭 到破坏，使得算法搜索空间减小，进而导致算法错误地收敛到局 部最优值。降低选择压力虽然可以增大算法搜索到全局最优值的 概率，但却会降低搜索效率，使算法的收敛速度变馒。因此，为 了使算法具蠢好的性熊，必须在撬嵩选择压力和保持静群多样性 之间达到某种平衡。 很多学者采用改进的选择算予用于调节选择压力、避免早熟 收敛瑗象酶发生，魏d ej o n g 在文献器】中绘耄醵几穗选择舞子： 最佳个体保留机制( e l i t i s tm o d e l ) 、期望值方法( e x p e c t e dv a l u e m o d e l ) 、最佳个体保留与期望值方法( e l i t i s te x p e c t e dv a l u em o d e l ) 等，b r i n d l e 对选择冀子提出了多种改进方法1 6 j ，如确定取样 ( d e t e r m i n i s t i cs a m p l i n g ) 、无放回随概余数取样( r e m a i n d e rs t o c h a s t i c s a m p l i n g w i t h o u t r e p l a c e m e n t ) 及有放回余数取样法( r e m a i n d e r s t o c h a s t i cs a m p l i n gw i t hr e p l a c e m e n t ) ，由g o l d b e r g ，k o r b 和d e b 撬赛薛锦标葵选择( t o t m a a m e n ts e l e c t i o n ) n i ，w e t z e l 提安静隧瓿镳 标赛选择( s t o c h a s t i ct o u r n a m e n ts e l e c t i o n ) 7 9 1 ，b o l t z m a n n 锦标赛选 择【5 2 1 ，w h i t l e y 等提出的基于排名的选择算予【1 1 ，b a k e r 的随机遍 历取样法( 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 ) 7 8 1 。 对适应度函数遴行尺度变换的方法也常被用于调节选择压 力、避免早熟收敛现象的发生，如线性尺度变换 12 1 、o 截断 ”】、 鞯尺度变换【1 4 1 、对数尺度变换1 2 1 、窟 2 1 技术f | 5 】、标准化 1 6 1 等。 穰多学者剜提凄务； 孛改遴鲢交叉、变异葬予来解决缳持耱黎 彩样性与提高算法搜索效率之间的矛盾，如两点交叉、均匀交叉、 多亲交叉1 2 4 1 1 8 2 1 、非均匀变异 6 1 、引入突变算予【7 1 、交叉位置非等概 率选取疆l 、淤壹近亲繁蘧f 2 8 1 等。 对于均匀交叉与两点交叉，文献f 2 6 】中指蹬一般说来均匀交叉 优于两点交叉，但文献【25 】也指出两点交叉对菜些问题的求解优于 均匀交叉。 磐亲交叉【2 4 【8 2 】是在实行交叉操作时，参与交叉的父个体数多 于灏个，如多亲对焦交叉、多亲季j 掺交叉等。如e i b e n 露 k e m e n a d e 口9 1 针对若干数德阔题证明了对角交叉中多个父俸的参 与能提高算法的收敛速度及全局最优解的精度。 窜瑶等【3 】针对二进制编码提出了一种非等概率选取交叉位置 酶改进酶遗传算法，隧麓邋过改避交叉操作中交叉位置麓逸敬方 法使产生的子代个体尽可能均匀地分布在优化变鬣搜索空间璺， 从而提高遗传算法的寻优收敛速度。实验表明改进的交叉操作方 法黠予蘧数优化等阕题收敛速度有了明显酶提高。 2 0 0 3 年苏小红等【q 提蹬了基于避化稳定策略的遗传算法，该 算法根据设置的稳定参数，通过对多余的优秀个体实施不同于一 般变异算子的突变操作，使褥每一代群体中优秀个体的数目维持 在一个稳定毽，既减轻了逸择税裁对低适应瘦毽个体所逢裁的生 存压力，保持了种群的多样性，避免过早收敛，闷时又扩大了搜 索空间，起到了通常的变异捧子达不到的、快速逃离局部最优解 误医的作耀，掇褰了收敛速度。 马钧水等i 2 l 提出了一种大变异( b i gm u t a t i o no p e r a t i o n ) 操作，用 于改进遗传算法的搜索性能。大变异操作的思路怒：当某代中所 有个体趋向于嗣一个体时，以一个远大予通掌的变异概率豹概率 执行一次变异掇作，具有大变异概率的变舁操作缝够随枫独立地 产生许多新个体，从而使整个种群脱离“早熟”。 e s h e l m a n 等i z 州通过避兔在海明距离低于菜一闽值的个体阅进 行交叉麓方法寒达妥防壹：i 遴塞繁殖、携离静嚣多群性的鑫的。 m i c h a l e w i c z l 6 在拥挤因子模型基础上提出了通过减少高适应 度值个体产生相同后代的概率来降低早熟收敛概率的m o d g a 算 法。 有的学者刘寻求遗传参数值的适应性调整方法在提高选择压 力和保持种群多样性之间达到某种平衡【 j 【馆1 ，如s h a e f e r 提出了对 交叉概率和变异概率实施二进制编码并连接到可行鳃的编码位串 上，傻褥它稍稷霹行瓣一起逡德，黻絮在群体避纯过程中逐渐获 得最佳的交叉概率和变异概率 s l l ；s r i n i v a s 等提出了一种将交叉概 率和变异概率根据群体的收敛性和个体的适应度值而动态改变， 使得它们对不同代群体和不同个体采取不同的值1 2 7 ；h e r r e r a 等采 用自适应变异率 1 7 1 的方法来保证算法在进化后期亦能维持种群较 高的多样性；r e c h e n b e r g 在进化策略算法中使用1 5 成功准则来 指导变异步长的调整【8 3 1 ；j u s t r o m 提出的根据杂交算子和变异算子 的性能调节杂交率和变异率的适应性机制【l 9 】；l e e 等人将模糊逻 辑方法用于动态调整遗传算法策略性参数【2 0 1 ；j o h nj g r e f e s t e t t e 利用m e t a g a 来优化g a 参数( 包括群体规模和选择方法) 2 2 1 ；丁承 民等【2 l 】则利用正交试验法来优化选取g a 控制参数，此法利用正 交试验的均衡分散性使得通过较少的试验次数就可搜索绝大部分 参数组合空间；m i c h a l e w i c z t 6 1 提出了一种变群体规模遗传算法， 其群体规模是随算法运 - ，i t 寸间而变化的；庄健和王孙安【8 1 】通过对 普通遗传算法选择、交叉、变异三个算子的深入分析，揭示了早熟 现象产生的原因，并从数学的角度证明了选择算子是早熟现象的 主要原因，在此基础上设计了一种变异概率可以自调节的自调节 遗传算法，提出了群体相异度指标来衡量多样性，通过相异度自 动地调节变异概率的大小，确保群体的多样性来避免早熟现象的 出现。 为了克服普通二进制编码所带来的g a 早熟问题， s c h r a u d o l p h 等提出了动态参数绫码( d y n a m i cp a r a m e t e re n c o d i n g ， d p e ) 2 3 $ j l n 。d p e 动态改变变量的定义域，当由某种方法褥知种 群已经收敛，则变量定义域缩小一个范围，从而使得在全局最优 点附近可以遴行更精确的搜索。s c h r a u d o l p h 等通过对d ej o n g 的 f 1 f 5 函数进行测试，发现采用d p e 质优化效果除多极值函数f 5 乡 ，冀余丞数优优结梁均有较大改善。 旌! s g a 的演化过程中，常用的种群更新策略为：使用新的个 体替换搏整个秘婺，帮溺爱代替换摔囊有魄父髂。这静罩孛嚣替换 策略将可能使得某些优良父体所具有的优良基因结构得不到繁 殖，藤且由于杂交和变异算予的作髑可能会破坏掉柴些优良父体 而产生较差的后代。考虑到s g a 的这一缺点，g - s y s w e r d a 在文 簸【3 l 】中提出了稳态遗谨算法( s t e a d ys t a t eg e 羲菇ea l g o r i t h m ) 豹策 略。其基本思想是：在每一个进纯迭代过程中，通过遗传操作产 生的新个体只替换掉当前群体中的一部分较差的个体，选择被替 换个体可以采用基于局部竞争的随机选取的方法，使褥适应度l 矗 趣差麓个薅被选择到酶橇警越大。这梯，当前群体中的最貔解将 肯定被保留到下一代群体，而另一些较优的个体也能以较大的概 率被保留。gs y s w e r d a 在测试了稳态遗传算法的性能后声称：至 少对墓些阂题，稳态逮绩算法麓戳更少憋时闻找到与s g a 笺找到 的样好或更好的解p “。 e s h e l m a n 和s h a f f e r 在文献【2 8 j 中掇出了一种无复本的稳态繁 殖策略( s t e a d ys t a t er e p r o d u c t i o nw i t h o u td u p l i c a t e s ) 。其聂的是在产 生蓊群体霹，镬箕中酶个体都不重复。他稍的骰法是在蒋某个个 体插入到新群体之前，先检查该个体与群体内的个体是否重复， 若重复则不插入。这种方法增加了群体的多样性，从而使得算法 龛塞搜索更多靛区域。 s a t o h 等则创造性地提出了最小代沟模型( m i n i m a lg e n e r a t i o n g a pm o d e l ，m g gm o d e l ) 1 3 4 j ，在种群替换迭代过程中，每一次迭 代均只有两个父体被替换；它较好地均衡了算法的探索 ( e x p l o r a t i o n ) 和开发( e x p l o i t a t i o n ) 能力，算法懿搜索效率较高。 d e b 等【33 j 于2 0 0 2 年提出了一种广义代沟模型( g e n e r a l i z e d g e n e r a t i o ng a pm o d e l ，g 3m o d e l ) ，在实验过程中将，。义代沟模型与 p c x ( p a r e n tc e n t r a lc r o s s o v e r ) 交叉算予缀合，结采爱示毒：与其镱 算法相比，这种新的算法对系列测试函数显示出无可比拟的优 越性能，甚至在初始种群偏离最优解( 从不包含最优解的区间开始 搜索) 麴。凌况下，最优解的搜索也取得了成功，两在传统的函数谯 纯算法中，搜索总是从包含最优解的送阀开始。 针对多模态函数优化问题，为使遗传算法能够搜索到尽凝多 的或所有的全局最优解和有意义的局部最优解，d ej o n g 等人提嫩 了撵挤模型嘲、概率捧挤模鍪瑟懿，g o l d b e r g 晕嚣r i c h a r d s o n 掇爨了 适应值共享模型、基于适应值共享机制的小生境技术瞄1 等。 还有大量研究人员则从事与其它启发式搜索技术相结合的混 合遗传算法的研究。如文献陋”中将模拟退火过程引入遗传算法， 在优选交叉和变异个体的过程中加入一定的“扰动”，以达到保持 种群内位串的多样性和位串之间的竞争机制，克服了算法易陷于 极小点的问题，使得搜索沿着全局最优方向进行；综合遗传算法的 全局性和神经网络的并行快速性等特点提出的遗传神经网络算法 哺“，可克服遗传算法收敛速度慢和神经网络易陷入局部解的缺陷， 具有较好的全局性和收敛速度。 第二节本文主要工作 本文主要研究了以下几个问题： 在第三章中首先提出了一种改进的遗传算法( 基于个体相似 度的遗传算法) ：当两父个体相似度较低时执行交叉操作产生新个 体，父个体相似度较高时则采用变异的方法产生新个体。并用此 改进的遗传算法对多个b e n c h m a r k 测试函数进行计算机模拟求 解，将之与普通遗传算法的计算结果进行了对比，验证该策略的 有效性。然后将基于个体相似度的遗传算法应用于图的度约柬最 小生成树的构造问题，取得了令人满意的结果。 在第四章中，针对实数编码提出了一种通用的基于决策变量 的复合交叉算子，选择单个或多个决策变量作为交叉点，实施基 于决策变量的实数交叉运算( 如算术交叉，模拟二进制交叉等) ， 再将各执行实数交叉运算的决策变量看作二进制编码遗传算法交 叉操作中的交叉点，执行类似二进制交叉的交换操作。然后将复 合交叉算子用于多目标优化问题的求解，算法效果良好，一定程 度上解决了高维多目标优化问题在用遗传算法求解时收敛性差这 一难题。同时，通过实验揭示了交叉点数对多目标遗传算法性能 的影响。 最后在第五章对本文进行了总结，并指出了有待进一步解决 的问题及将来的研究方向。 第三章基于个体相似度的遗传算法及应用 在遗传算法中一个关键问题是必须采取措施保持种群多样 性，防止算法出现早熟收敛。本章提出一种基于个体相似度的遗 传算法种群多样性保持策略，并给出了具体算法( 基于个体相似度 的遗传算法) 。然后以几个b e n c h m a r k 测试问题为例进行计算机模 拟求解，将之与未使用此策略的普通遗传算法进行了对比，验证 新算法的有效性。最后将基于个体相似度的遗传算法应用于图的 度约束最小生成树的构造问题，取得了预期的效果。 第一节自适应遗传算法 鉴于遗传算法是受进化思想启发而来的，人们很自然希望适 应性不仅用于寻找给定问题的解，同时还可以让遗传算法针对特 定问题进行变化。在过去的几年里，为了将遗传算法针对现实世 界的问题有效地实现，已经提出并测试了许多适应性方案。总起 来说，存在两类适应性呻1 ： 1 对问题的适应性 2 对进化过程的适应性 以上二者的区别在于：前者提出修改遗传算法的某些元素( 比 如编码、交叉、变异和选择) 从而得到算法的理想形式以满足给定 问题的本质；后者提出一种在遗传算法解决问题的同时对其参数 进行动态调整的方法。根据h e r r e r a 和l o z a n o 的报道，对进化过 程的适应性可以进一步划分为以下几种“： 1 适应性参数设置 2 适应性遗传算子 3 适应性选择 4 适应性表示 5 适应性适应度函数 在以上几种适应性进化方法中，参数适应性在过去的l o 年中 l n 得到了比较充分的研究昭7 儿“1 ，原因在于诸如变异率、交叉率和 种群规模等策略性参数对于确定全局搜索和局部搜索的折中是关 键的因素。长久以来，人们已经得到了一致的认识，即这些策略 性参数对于遗传算法的性能有着显著的影响。 自适应遗传算法( a d a p ti v eg a ) 其通常作法是使交叉概率p c 、 变异概率p m 等遗传参数在进化过程中根据种群的实际情况，动态 调整大小，当种群趋于收敛时，增大p c 、p m 等参数值，破坏当前的稳 定性，克服过早收敛：当种群个体发散时，减小p c 、p m 等参数，使个 如文献幢“提出了一种使交叉概率只和变异概率p 。随适 应度自动改变的方法，分别见式( 1 ) 、式( 2 ) ： 胪f 芝嚣篙 其中，厶。，为种群最大适应度，i 是种群平均适应度，五为 用于交换的两个个体中较大的适应度，也。、如为参数 k 。1 号弩f m f，叭 m 一 1 m a x 上厶 【k 。：f , o i 其中为变异个体的适应度，、为参数 本文作者则从适应性遗传算子的角度讨论了自适应遗传算 法，提出了一种基于个体相似度的遗传算法。 第二节基于个体相似度的遗传算法 一、基于个体相似度的遗传算法 1 个体的相似度 个体的相似度是指两个体对应染色体中具相同等位基因的基 因个数与基因总数( 即染色体长度) 的比值。两个染色体中等位基 因相同的基因个数越少，其相似度越小，反之亦然。 l l 对于群体中任意二进制编码个体a 与b ，其相似度按下式计 冀： s d ( a ，口) = t - ( f , 4 0 岛) f - 】 式中：是二进制染色体串的长度；a ；是个体a 对应染色体的 第i 个基因；器；是令钵转对应染色体的繁i 个鏊医；$ 是黪藏运 算符。 2 基于个体相似度的遗传算法( s i m i l a r i t yb a s e dg e n e t i c a l g o r i t h m ，s b g a ) 两个配对个体，当它们非常相似时，执幸亍交叉揉作，将缀难 产生新的个体，这样g a 也就很难搜索到新的解空间。反而此时若 采用变异的方法产生耨个体则可搜索到新的解空间。另外，在传 统豹遗传篓法运行过程中，撬耄亍交叉操作螽薪个体又以一定斡变 异概率执行交界运算，极可能将交叉产生的优秀个体破坏掉，影 响算法的收敛效果。因此，我们对遗传算法的算法流程作了改进： 当嚣父个体相似度较低时执行交叉掇作产生子代个体，个体襁戗 度较高时刚果粥变异的方法产生予代个体。这样交叉产生的优秀 子个体将与其它子个体( 交叉产生的其它子个体以及变异产生的 予个体) 竞争丽得以生存下来，同时又避免了高相似度个体进行 交叉覆罨致静群多样注戆丧失。 操作步骤如下： s t e p1 ：初始化群体p o p ，种群大小为p o p s i z e ； s t e p2 ：计算p o p 中个体豹适应度； s t e p3 ：跌p o p 中选择个体进入塞本港m a t e p o p ： s t e p4 ：在m a t e p o p 中按锦标赛选择机制选取父个体，并计 算每一对个体之间的相似度； s t e p5 ：瓣个毒参粳似度s d 一s ) 的个体执行变异操作； s t e p6 ：将s t e p5 交叉或变异后的子代个体与上一代保留的 最优个体( 保留比例取1 一2 0 ) 放入临时种群t e m p p o p ，从 t e m p p o p 孛择镶选取p o p siz e 个个髂缀威毅一代群体； s t e p7 ：若满足算法终止条件则结束；否则转s t e p2 。 流程图见图3 。1 。 3 锦标赛选择遗转簿法( t o u r n a m e n ts e l e c t i o ng e n e t i c a l g o r i t h m t s g a ) 与s b g a 相比，不同之处在于s t e p 4 和s t e p5 中处理方式不 霆( 蒸滚程翔图3 2 襞示) ，具体操 乍步骤如下： s t e p1 ：初始化群体p o p ，种群大小为p o p s i z e ； s t e p2 ：计算p o p 中个体的适应艘； s t e p3 ：从p o p 中选择个体进入慧本池m a t e p o p ： s t e p4 ：在m a t e p o p 中按镐标赛选择瓿裁选敬父个体； s t e p5 ：对父个体执行交叉操作，然后执行燮异操作； s t e p6 ：将s t e p5 交叉、变异后的子代个体与上一代保留的 最饯个体( 保露比例取1 - - 2 0 ) 放入临时种群t e m p p o p ，从 t e m p p o p 中择绲选取p o p s i z e 个个体缝成薪一代群体； s t e p7 ：糟满足算法终止条件则结束；否则转s t e p2 。 4 自调节遗传算法( s e l f - a d j u s t i n gg e n e t i ca l g o r i t h m ， s a g a ) 疆1 】 箕算法愚慧是：先计箨群体中任意两个俸韵糨异度，以此为 基础计算群体的相异率，当群体相异率小于一定阀值时增加种群 变异概率，以掇高种群的多样性，有利于算法性能的提高。 对于群体中任意薅个铬表，b 魄捆辩度翔下式联示： f ( a ，君) = ( 4e & ) l i = l 式中：是二进制染色体串的长度；彳彳是个体a 对应染色体 魄第j 个基因；厦是个体转对应染色体豹第i 个纂因；毋是器或 运算符。 群体相异率按下式所示： 毽= a 劂，i n d k ) ( n - 1 ) h 1 0 0 j ； 女* f 式中：为群体规模，三为染色体串的长度，如谚是种群中 第j 个个体。 算法操作步骤如下： 1 ) 初始化群体，总个体为朋设定杂交概率只，变异概率为初 始变异概率匕，目 i p - - 匕： 2 ) 统计群体中相异率，并计算每个个体的适应度值： 3 ) 将群体里比基因库中更好的个体保存到基因库中，如果没 有发现更好的个体，则释放基因库中优良个体到群体中去； 4 ) 判断群体相异率玖是否小于设定阈值口，如果是，p m = p 纫+ p m ，否则，辟忍； 5 ) 进行遗传操作( 先交叉后变异) ： 6 ) 中止条件判断：若满足算法终止条件则结束，否则跳转到 步骤2 。 二、s b g a 与t s g a 对比实验与结果分析 为初步验证s b g a 算法中提出的基于个体相似度的交叉变异 策略的有效性，将之与采用普通交叉变异策略的t s g a 算法进行 了对比实验。 1 参数设置 算法t s g a 、s b g a 使用相同的遗传操作参数： 使用二进制位串编码，每一个决策变量编码码长2 0 位，采用 位单点交叉，交叉概率为o 8 ，使用位单点翻转变异，变异概率 为( 1 染色体长度) ，选择方法为二元锦标赛选择( b i n a r y t o u r n a m e n ts e l e c t i o n ) ，算法中最优个体保留比例取2 ，种群 大小为1 0 0 ，算法随机运行2 5 次，每次运行1 0 0 代。 2 算法性能指标 b a c k 定义了一个用来评价收敛速度的参数，称为“进程度量 值”( p r o g r e s sm e a s u r e ) ，它表示的是进化的相对收敛进程”。 j p ：l n 幽 vf b 。( 7 ) 其中五。，( r ) 表示第t 代种群中最好的目标函数值( 如为最小化 问题，则取最小目标函数值) 。 图3 1基于个体相似度的遗传算法 图3 2 锦标赛选择遗传算法 1 6 3 测试函数 1 ) s c h a f f e r 函数嗡 最小化：如( _ x 2 ) _ 0 5 十而磊箭盂耳0 掰5 s l n l 、7 贯+ 巧一 一1 0 0 9 x j 1 0 0 i = 1 , 2 + 该懑数的全麓最筑鼹力：在点( 0 ，o ) 处取最小毽0 。 2 ) r o s e n b r o c k 涵数盔3 3 最小化：k 瓴，x 2 ) = 1 0 0 ( x 2 - x i ) 2 + ( x l - 1 ) 2 ，一2 0 4 8 兰x 1 ，x 2 2 0 4 8 该涵数的全弱最优解为：在点( 1 ，1 ) 处取最小值0 。 3 )糖球蘧数( e l l i p s o i d a lf u n c t i o n ) 8 8 最小化：，= 留，一l - - 1 8 2 e - 81 8 8 e 一23 5 6 e - 91 2 75 4 6 e - 1 21 8 3 e - 2 l s 激l ，8 2 e - 82 ，l l e - 14 。9 0 e - 91 0 s 5 。4 6 e - 1 25 。5 5 e 一2 单次运彳j + 结柬时种群的平均函数值) 由表3 1 、图3 3 和图3 4 可知，就算法搜索到的最优解来说， 算法s b g a i ( h 荻度阙篷取o 。参) 与t s g a 捆毙弱好藏不稷上下， 但在种群平均适应度值( 郎算法的在线性能) 方面，s b g a 明显优予 t s g a ；同时，由上述测试溺数优化例的仿真实验结果可看出： s b g a 箨法中个体相似度阈德s 取0 9 时结果要优于o 8 取值时的 结采。总之，基予个体翔似凌