（控制科学与工程专业论文）改进的差异进化算法求解高维全局优化问题研究.pdf

r e s e a r c ho ni m p r o v e dd i f f e r e n t i a le v o l u t i o n a l g o r i t h mf o r s o l v i n gh i g h - d i m e n s i o n a lg l o b a lo p t i m i z a t i o np r o b l e m s s p e c i a l t y ： c o n t r o ls c i e n c ea n de n g i n e e r i n g m a s t e r d e g r e ec a n d i d a t e ： s u p e r v i s o r ： s c h o o lo fi n f o r m a t i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a n p r c 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特， l j ) j n 以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：蔓毒股这 日期：旦l 年月；日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容， 可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技 术信息研究所将本学位论文收录到中国学位论文全文数据库，并 通过网络向社会公众提供信息服务。 作者签名：越导师签名塞立。量日期：翌f 旦年上月卫日 摘要 全局优化问题在科学与工程领域普遍存在，具有重要的研究意义和 应用价值。随着研究的深入，因搜索空间巨大而求解难度大的高维全局 优化问题逐渐成为优化问题研究的新热点。而对求解一般全局优化问题 具有较好性能的差异进化算法，在求解高维全局优化问题时则需要做很 大改进才能取得较好的效果。本文围绕改进差异进化算法求解高维全局 优化问题展开，并对进化算法框架等相关领域进行了较为深入的研究。 本文首先阐述差异进化算法的标准实现、常用差异策略、最新发展 和当前研究热点，在描述了高维全局优化问题之后，介绍了对求解高维 全局优化问题的较为有效的协同进化算法。 本文通过将差异进化算法与p o t t e r 协同进化模型结合，提出了一种 自适应构造块识别协同差异进化算法。该算法使用了两个种群，一个为 基因序种群，用于调整候选解个体的基因序以识别构造块，一个为候选 解种群，用于搜索最优解和评价基因序个体的优劣。两个种群使用不同 的搜索算法进行进化，并具有协同进化机制，通过种群合作搜索最优解。 实验表明，自适应构造块识别协同差异进化算法具有较强的全局和局部 搜索能力，是求解高维全局优化问题的一种有效算法。 由于目前进化算法的分支众多，研究者亟需便利的研究工具。本文 提出了一种进化算法框架e a 卜十，该进化算法框架抽象了进化算法的种 群结构、进化过程、进化算子、适应值评估、数据统计等主要组成部分， 提供了进化算法的基础实现，采用了低耦合的模块设计、可扩展的分层 设计和高效率的底层实现，具有较为安全的异常处理机制。与进化算法 领域的其他框架比较，e a h 框架具有高效、灵活、可扩展、可配置、 可移植的特点，对进化算法的研究者们具有较高的应用价值。 关键词进化算法，差异进化算法，高维全局优化问题，协同进化，进 化算法框架 a b s t r a c t g l o b a lo p t i m i z a t i o np r o b l e m s ( g o p s ) a r ep r e v a l e n ti ns c i e n c ea n d e n g i n e e r i n g ，a n dh a v ei m p o r t a n tr e s e a r c hs i g n i f i c a n c ea n da p p l i c a t i o nv a l u e w t ht h ed e v e l o p m e n to fr e s e a r c h ，h i g h - d i m e n s i o n a lg l o b a lo p t i m i z a t i o n p r o b l e m s ( h g o p s ) ，w h i c hh a v eh u g es e a r c hs p a c ea n da r ed i f f i c u l tt os o l v e ， a r eb e c o m i n gan e wh o t s p o t i n s t e a do fo w n i n gg o o dp e r f o r m a n c ef o r s o l v i n gg o p s ，d i f f e r e n t i a le v o l u t i o n a r y ( d e ) a l g o r i t h mn e e dt ob eg r e a t l y i m p r o v e dt oa c h i e v eb e t t e rr e s u l t sf o rs o l v i n gh g o p s t h i sp a p e rf o c u s e so n i m p r o v i n gd et os o l v eh g o p s ，a n dd i s c u s s e ss o m er e l a t e da r e a ss u c ha s e v o l u t i o n a r ya l g o r i t h mf r a m e w o r k ( e a f ) f i r s t l y , t h i sp a p e rd e s c r i b e dt h es t a n d a r di m p l e m e n t a t i o n ，e x i s t i n g d i f f e r e n t i a ls t r a t e g i e s ，t h el a t e s td e v e l o p m e n t sa n dc u r r e n tr e s e a r c hf o c u s e s o fd e a f t e re x p l a i n i n gt h eh g o p s ，i n t r o d u c e dc o - e v o l u t i o n a r ya l g o r i t h m ( c e a ) w h i c hh a s e f f e c t i v ep e r f o r m a n c ef o rs o l v i n gh g o p s c o m b i n e dd ew i t hp o t t e rc o e v o l u t i o nm o d e l ，t h i sp a p e rp r o p o s e dt h e c o o p e r a t i v ec o e v o l v i n g d i f f e r e n t i a l e v o l u t i o nw i t h a d a p t i v e b u i l d i n g b l o c k si d e n t i f i c a t i o n ( c c d e - a b i ) a l g o r i t h m c c d e a b iu s e st w o p o p u l a t i o n s ，o n e i su s e dt o p e r m u t et h eg e n es e q u e n c eo fs o l u t i o n i n d i v i d u a l st oi d e n t i f yt h eb u i l d i n g b l o c k s ，t h eo t h e ri su s e dt os e a r c hf o r o p t i m a ls o l u t i o n sa n de v a l u a t et h ef i t n e s so ft h eg e n es e q u e n c ei n d i v i d u a l t w op o p u l a t i o n su s i n gd i f f e r e n te v o l u t i o n a r ya l g o r i t h mh a v ec o o p e r a t i v e c o e v o l u t i o n ( c c ) m e c h a n i s m i n s e a r c h i n g t h e o p t i m a l s o l u t i o n e x p e r i m e n t ss h o wt h a tc c d e a b ih a se x c e l l e n tg l o b a la n dl o c a ls e a r c h c a p a b i l i t i e s ，a n di sa ne f f e c t i v ea l g o r i t h mf o rs o l v i n gh g o p s s i n c ee x i s t m a n yb r a n c h e s o ft h e e v o l u t i o n a r ya l g o r i t h m ，t h e r e s e a r c h e r sn e e df a c i l i t a t er e s e a r c ht 0 0 1 t h i sp a p e rd e s i g n e dae v o l u t i o n a r y a l g o r i t h m sf r a m e w o r kn a m e d e a + + w h i c ha b s t r a c t se v o l u t i o n a r ya l g o r i t h m ( e a ) m a j o rc o m p o n e n t ss u c ha sp o p u l a t i o ns t r u c t u r e ，e v o l u t i o np r o c e s s ， e v o l u t i o n a r yo p e r a t o r s ，f i t n e s se v a l u a t i o n ，s t a t i s t i c se t c e a + + p r o v i d e st h e e v o l u t i o n a r ya l g o r i t h mf u n d a m e n t a li n f r a s t r u c t u r e ，a n dh a sl o w c o u p l i n g m o d u l e s ，s c a l a b l eh i e r a r c h i c a ls t r u c t u r e ，e f f i c i e n tu n d e r l y i n gi m p l e m e n t a t i o n i i a n dm o r es e c u r e e x c e p t i o nh a n d l i n gm e c h a n i s m c o m p a r e dt o o t h e r e v o l u t i o n a r ya l g o r i t h m sf r a m e w o r k s ，e a + + e x p r e s s e se f f i c i e n t ，f l e x i b l e ， s c a l a b l e ，c o n f i g u r a b l e ，p o r t a b l ec h a r a c t e r i s t i c s ，a n dh a sh i g h e ra p p l i c a t i o n v a l u ef o rr e s e a r c h e r s k e yw o r d se v o l u t i o n a r ya l g o r i t h m ，d i f f e r e n t i a le v o l u t i o na l g o r i t h m ， h i g h - d i m e n s i o n a lg l o b a lo p t i m i z a t i o np r o b l e m s ，c o - e v o l u t i o n ，e v o l u t i o n a r y a l g o r i t h mf r a m e w o r k i l i 摘要i a b s t r a c t i i 第一章绪论l 1 1 课题研究背景1 1 2 现存技术及存在的问题2 1 3 本论文的主要工作3 第二章差异进化算法4 2 1差异进化算法的起源4 2 2 标准差异进化算法4 2 3差异进化算法的差异策略6 2 4 差异进化算法的发展7 2 5差异进化算法的研究热点。9 2 6 本章小结1 1 第三章高维优化问题及求解算法1 2 3 1高维优化问题描述1 2 3 2 高维优化问题求解1 2 3 3协同进化算法1 3 3 3 1竞争型协同进化算法1 3 3 3 2协作型协同进化算法1 4 3 3 3协同进化算法的发展1 5 3 4 本章小结1 7 第四章自适应构造块识别协同差异进化算法1 8 4 1算法描述l8 4 1 1高维优化问题与差异进化算法1 8 4 1 2构造块识别与子问题划分1 8 4 1 3多种群设计19 4 1 4 基因序种群的进化2 l 4 1 5 候选解种群的进化2 3 4 1 6算法框架2 6 4 1 7 空间与时间复杂度分析2 8 4 2 实验结果及讨论2 9 i v 4 2 1测试函数与参数设置2 9 4 2 2算法的整体性能比较2 9 4 2 3正交算子的作用3 1 4 2 4不同候选解种群进化算法的比较3 4 4 3 本章小结3 5 第五章e a + + 进化算法框架3 6 5 1e 卅进化算法框架设计与实现3 6 5 1 1已有框架介绍3 6 5 1 2进化算法的抽象分析3 7 5 1 - 3e a + + 进化算法框架的设计3 8 5 1 4 e a 卜+ 进化算法框架的实现。4 0 5 1 5e a + + 进化算法框架的扩展4 4 5 1 6e a + + 进化算法框架的使用。4 5 5 2进化算法框架的比较4 7 5 2 1框架的评价4 7 5 2 2进化算法框架评价标准4 8 5 2 3进化算法框架比较4 9 5 3 本章小结5 l 第六章总结与展望5 2 6 1 总结5 2 6 2 展望5 3 参考文献5 4 附勇乏5 8 致谢5 9 攻读硕士学位期间主要的研究成果6 2 v 1 1 课题研究背景 全局优化问题是各领域中都存在的问题。虽然全局优化问题来源于历史悠久的 极值问题，但直到十九世纪四十年代，研究者提出了解决全局优化问题的一般方法， 全局优化问题研究才成为了一门独立的学科。经过几十年，全局优化问题的研究已 经应用于经济、管理、生产、国防、交通等各研究领域，是极为重要的基础研究。 随着计算技术的快速发展和计算机的普及，为全局优化问题的基础研究提供了更好 的基础。目前，全局优化问题得到了各领域研究者的关注，获得了令人惊叹的研究 进展。 高维全局优化问题是一类较难求解的全局优化问题，近年来成为研究的新热点。 一些求解全局优化问题有效的算法，如牛顿法、动态规划法、模拟退火、禁忌搜索、 随机爬山、进化算法等，求解该类问题时效果欠佳。虽然如此，研究表明进化算法 相对于其他算法具有较大的优势。牛顿法、动态规划法等在求解的时候需要问题的 先验信息，对问题有可微的要求，对于不满足要求的问题无法求解，求解高维全局 优化问题时更加困难。进化算法没有牛顿法、动态规划法的这些缺点，并且相对模 拟退火、禁忌搜索、随机爬山等算法，具有更高的准确性，更少的参数、更简单的 实现、和更高的效率。 自从达尔文提出生物进化的理论之后，自然界生物进化的研究得到了很大的推 进。虽然还存在拉马克进化、综合进化论、间断平衡论、中性学说等多种进化学说， 对于进化的过程还没有研究定论，但研究者已经认识到生物进化的基本特性。生物 进化研究与全局优化问题研究的交叉产生了进化算法。 进化算法本质上是一种启发性算法，种群中的个体表示问题的一个候选解，从 随机初始种群开始，通过迭代使用选择算子、变异算子和交叉算子，获得近似最优 解。选择算子使适应值高的父代个体具有更大可能进入子代，交叉算子将父代基因 块进行交叉并将他们保留到子代，变异算子在种群中引入了新的基因。 与牛顿法、动态规划法等算法相比，进化算法不需要高维全局优化问题的先验 信息，也不需要高维全局优化问题可微，使用基于群体的启发式搜索机制，依靠群 体的迭代进化，逐步搜索最优解。因为具有上述优势，进化算法在近年来发展迅速， 广泛应用于求解各类全局优化问题。研究者也将其应用到求解高维全局优化问题， 取得了很大的进展。 算法，而进化算法中的差异进化算法正是具有强搜索能力的优秀算法，但求解高维 全局优化问题时仍有以下几个问题需要改进： 1 增强搜索能力。高维全局优化问题的维数达到几百维甚至上千维，搜索区域 非常大，一般的差异进化算法面对如此大解空间时，需要进化很多代才能接近最优 值，计算代价太大。如何在固定的群体规模下，以最少的进化代数和最小的计算代 价，搜索到最优解区域，是改进差异进化算法的方向。差异进化算法对低维全局优 化问题的搜索能力虽然很强，但面对高维全局优化问题时，还需要进一步增强其全 局搜索能力，使其能够在同样的计算代价下，搜索更大的解空间。 2 分解高维问题。高维全局优化问题由于维数太高，整体搜索收敛缓慢，容易 陷入局部最优。一些研究者已经认识到，求解高维全局优化问题时，将其分解为规 模较小的若干个子问题，可以加快搜索进程，提高收敛速度，但是仍然面临陷入局 部最优的风险，并且有些高维全局优化问题，各维之间存在较强的耦合关系，分解 成子问题，求解效果反而变差。在求解高维全局优化问题时，需要更好的分解方法， 既能缩小问题规模，加快收敛速度，又能避免陷入局部最优，同时在求解一些各维 之间具有强耦合性的不可分解的全局优化问题时，处理好各维之间的耦合关系。 3 识别各维之间的耦合性。大部分进化算法在求解一些可分解的全局优化问题 时，性能都不错，但在求解一些具有强耦合性的不可分解的全局优化问题，差别很 大。在识别各维之间的耦合性上，已经出现了多种方法，如分布估计法、随机分组 法等，如何结合已有的方法，识别出耦合性的同时，兼顾高维问题的分解，使识别 与分解能够紧密结合，提高对求解高维不可分解的全局优化问题的性能，是差异进 化算法的改进重点。 4 改进步长调整机制。在求解高维全局优化问题时，由于解空间大，为快速搜 2 硕士学位论文第一章绪论 索，要求搜索步长较大，但搜索到最优值附近区域时，由于已经接近最优值，步长 太大反而跳出了最优区域，这时又要求搜索步长小，因此要求算法在进化过程中能 够调整搜索步长。在差异进化算法中，已有三种方法调整搜索步长：1 ) 固定型。参 数f 在进化前设定好，进化中不发生变化，通过群体中个体差异大小，调整搜索步 长；2 ) 适应型。参数f 在进化过程中，为适应进化根据一定规则调整；3 ) 自适应 型。参数f 也成为个体的一部分，随同起进化而调整。求解高维全局优化问题时， 需要能够适应超大搜索空间的步长调整机制，同时需要避免因步长调整不当而陷入 局部最优。 1 3 本论文的主要工作 本章对使用差异进化算法求解高维全局优化问题进行了简要的叙述，并指出了 需要改进的一些问题。本论文的研究内容主要围绕如何有效改进差异进化算法求解 高维全局优化问题而展开，各章节具体安排如下： 第二章对差异进化计算的起源、发展和研究热点做了简要介绍。差异进化算法 诞生至今发展迅速，基于其的新算法层出不穷。由于差异进化算法简单有效，搜索 能力强，改进空间大，差异进化算法成为进化计算领域的研究热点。 第三章对高维全局优化问题进行了描述，介绍了求解高维全局优化问题的难点 和基本方法，并详细介绍了求解高维全局优化问题特别有效的协同进化算法的起源、 分类、和近年来的发展。 第四章提出了一种自适应构造块识别协同差异进化算法c c d e - a b i ，结合了 j a d e o c 算法和协同进化模型，形成可以自适应识别构造块，并依据识别出的构造 块信息划分子问题的求解高维全局优化问题的高效算法。本章详细介绍了 c c d e a b i 的种群设计、构造块识别方法、子问题划分方法、基因序种群进化和候 选解种群进化，解释了c c d e a b i 的算法设计。通过实验表明，c c d e a b i 算法在求 解高维全局优化问题时，具有较强的全局搜索能力和局部搜索能力。本章的实验还 研究了正交算子和不同候选解种群进化算法对算法性能的影响，证明了正交算子的 作用，实验结果表明c c d e a b i 可以作为一个求解高维全局优化问题的算法框架。 第五章提出了一个进化算法框架e a + + ，该框架的抽象了进化算法的主要过程， 并实现了一些常用的进化算法，研究者可以非常方便地使用该框架。在该框架基础 上，研究者也可以很方便地实现新的进化算法。经过与其他常用的进化算法框架比 较，e a h 框架具有通用性较好、容易使用、效率高、鲁棒性较好、可移植的特点。 但在通用性方面，仍需要实现可配置的组合新算法的功能。在鲁棒性方面，需要提 供异常安全性保证。总体上，本文提出的e a + + 进化算法框架，表现良好，特色突出。 最后第六章对本文进行了总结，提出了值得进一步研究的方向。 3 争选择，而交叉操作方式与遗传算法也大体相同，但在变异操作方面使用差异策略， 即利用种群中个体间的差异对个体进行扰动，实现个体变异。d e 的变异方式有效 利用群体分布特性，提高了算法的搜索能力，避免遗传算法中变异方式的不足。 1 ) 变异算子 标准差异进化算法的变异算子，通过种群个体间的差异进行变异，是区别于其 他进化算法的特性，如图2 1 。变异算子，随机选取种群中的两个不同个体，将其 4 硕士学位论文 第二章差异进化算法 向量差通过缩放后，与待变异个体向量合成，即 屹暑+ l2 1 ，窖+ ，( t 2 ，g t 3 ，g )f 眨弓 ( 2 - i ) 其中f 为搜索步长，i ，吃，为三个不相等的取值范围为【1 ，n p 的随机数，胛为种群 中个体数目，- ，g ，_ ：3 ，g 为第g 代种群中的三个随机选取的个体，m ，g + 。为变异后 产生的第g + 1 代的第i 个中间个体。 x l 图2 - 1 哭异算予示意图 2 ) 交叉算子 标准差异进化算法中的交叉算子对第g 代种群中的父代个体，与变异后产生的 第g + 1 代中间个体肿。进行交叉操作： 州= 芝1 = d 鲫町钆 c2 乏， 其中c r 为交叉概率，为当前维，l 。d 为 1 ，d 】之间的一个随机数以保证最少有一 维执行了交叉操作，d 为个体的维数。“，_ 州即为交叉过后产生的第g + l 代的第f 个 中间个体。 3 ) 选择算子 标准差异进化算法采用一对竞争的贪婪算法来选择进入下一代的种群中的个 体： b = 留 f 0 + ：) 胞，g ) ( 2 - 3 ) o t l 3 c 1 w l s e 5 解空间搜索范围更大，更能保证算法收敛于最优解，但是算法的收敛速度会比较慢。 从另个角度来看，如果选择参与生成中间个体的父代个体是当前最优个体或指定 某个与最优个体有关联的特定个体，则会使算法的收敛速度大大加快，趋向最优解 的能力将会提高，但是一旦最有个体是局部极值点，则会因为种群多样性的降低， 而增加了算法收敛于局部极值点的可能性。 d e r a n d i b i n 和d e b e s t 2 b i n 是目前使用最广泛、效果最好差异策略。前一种 策略具有较强的全局搜索能力，搜索范围更大，搜索方向更广，更有利于保持种群 的多样性，算法更容易搜索到最优解，但是在进化初期，算法的收敛速度相对缓慢。 6 硕士学位论文 第二章差异进化算法 d e r a n d l b i n 譬+ l2 i ，譬+ ，( x r 2 ，暑一j c r 3 詹) d e r a n d 2 b i n ，岩+ l = l 。譬+ f ( 2 培一3 , g ) + ，。( 4 ，异一一5 , g ) d e b e s t i b i n 一，膏+ l = j 吃酬，g + 户( l ，暑一2 属) d e b e s t 2 b i n v f ，譬+ l = f 囊+ ，( l ，膏一2 ，岩) + ，。( t 3 ，名一t 4 譬) d e r a n d - t o - b e s t b i n m ，暑+ l = l 暑+ 五( 五蛔，耳一_ l , g ) + f ( 2 ，窖一3 ，暑) d e c u r r e n t - t o - r a n d b i n v ，霉+ l = 薯，耳+ 五( l ，譬一五，暑) + f ( 2 泻一3 ，譬) d e c u r r e n t - t o - b e s t b i n v ，膏+ l = 檀+ 五。( 五吲，异一t 。膏) + f ( 1 ，只一2 ，膏) d e r a n d 1 e x p u ，膏“2 l 。鼻+ ，。( t 2 ，譬一3 ，霉) d e r a n d 2 e x p k ，暑+ l = 誓l ，譬+ f 。( 一2 ，异一t 3 , g ) + ，( 4 ，膏一一5 ，霉) d e b e s t 1 e x p ，g + l2 ，膏+ f ( 一l ，异一2 檀) d e b e s t 2 e x p v ，霉+ l = f 属+ ，+ ( t l ，j 一2 , g ) + f ( t 3 痦一4 , g ) d e r a n d - t o - b e s t e x p m ，霄+ l = l ，膏+ 名( 毛吲。只一l , g ) + f ( 2 腐一如。g ) d e e u r r e n t - t o - r a n d e x p 一，譬+ l = 而，量+ 名( l 属一薯，暑) + ，。( x r 2 ，只一3 ，暑) 里型竺翌竺! ：1 2 ：堕! ! ! 兰里兰逞i i + t2 1 2 l + 旯( j c o i l l 一鼍，i 卫1 1 ) + ，( - ，1 2 l l 一z i l i i _ _ _ _ _ _ _ _ _ _ _ _ _ _ 一- 而后一种策略则加速了算法的趋优收敛进程，具有更快的收敛速度，但种群的 多样性保持能力相对较差，算法比较容易收敛到局部最优解。除此之外，还有很多 研究者提出了多种其他差异策叫1 2 1 。 2 4 差异进化算法的发展 差异进化算法提出十多年来，由于其简单高效，受到广大研究者的关注，改进 的差异进化算法层出不穷。自参数适应性调整机制提出以来，由于其参数变少，效 率更高，已经成为改进差异进化算法的主流，目前效果最好的改进差异进化算法都 属于此类。根据参数适应性调整机制的不同，可以将其分为两类：1 ) 适应性参数控 制，利用进化信息动态调整参数，如s a n s d e 、 d e 、j a d e 等；2 ) 自适应参数控 制，将参数与个体一起进化，如d e s a p 。 1 d e s a p j a s o nt e o 在2 0 0 6 年提出了d e s a p ( d i f f e r e n t i a le v o l u t i o nw i t hs e l f - a d a p t i n g p o p u l a t i o n s ) 算澍b 】。该算法不但动态适应性调整变异参数r 和交叉参数万，而且 也动态调整种群规模万。d e s a p 的差异策略与典型的d e r a n d l b i n 明显不同，其 参数刀、万与标准d e 中的c r 、肝意义相同，而参数万的意义是交叉操作后进行 额外的正态分布变异的概率。而搜索步长f 在d e s a p 中是固定的。 7 硕士学位论文第二章差异进化算法 在d e s a p 中，每个个体都有与之相对应的仉、嗔、乃，这三个参数跟一 样，要经过变异和交叉的进化过程，并且与中间个体州一起接受选择操作。尽管 d e s a p 的实现很简单，但是其效率却并没有改进多少，与标准d e 相差无几。实际 上，j a s o nt e o 提出d e s a p 只是为了展示通过自适应调整能够将控制参数减到更少 的可能性。 2 j d e b r e s t 在2 0 0 6 年提出了j d e ( s e l f - a d a p t i n gc o n t r o lp a r a m e t e r si n d i f f e r e n t i a l e v o l u t i o n ) 算澍1 4 】。该算法基于标准d e 的d e r a n d l b i n 差异策略，种群规模胛在 j d e 中是固定的，每个个体t 都有与之相对应的只、c r 。在初始化的时候，设定 每个个体所对应的f = 0 5 、c r = 0 9 。在每一次进化过程中，f 和c r 以= = o 1 概率分别在【0 1 ，l 】和【o ，l 】的均匀分布范围内产生新的参数值。该算法的基本原理是， 好的参数将产生好的个体，好的个体将有更大概率存活至下一代，从而对应的好的 参数也将保留至下一代。 实验表明，i d e 的效果非常好，显著优于标准d e 、快速进化规划、和一些其他 适应性算法。 3 s a n s d e y a n g 在2 0 0 8 年提出了s a n s d e ( s e l f - a d a p t i v ed i f f e r e n t i a l e v o l u t i o nw i t h n e i g h b o r h o o ds e a r c h ) 算法【1 5 】。该算法的变异策略由概率参数p 控制每次使用 d e r a n d l b i n 或者d e c u r r e n t t o b e s t b i n ，参数p 也是随着进化过程而变化的，哪个 策略取得的成功越多，就越偏向于使用哪个策略。搜索步长，则由概率参数廖控制 使用高斯分布或柯西分布的随机数，并且参数廖也随着进化过程而变化。交叉概率 c r 也是随着进化过程而变化的，根据记录的成功的c r 值和适应值的改进程度而自 动调整。 s a n s d e 是由n s d e ( d i f f e r e n t i a le v o l u t i o nw i t hn e i g h b o r h o o ds e a r c h ) 和s a d e ( s e l f - a d a p t i v ed i f f e r e n t i a le v o l u t i o n ) 结合而来，实验表明s a n s d e 比这两种d e 算 法的效果都好。 4 j a d e z h a n g 在2 0 0 9 年提出了j a d e ( a d a p t i v ed i f f e r e n t i a le v o l u t i o nw i t ho p t i o n a l e x t e r n a la r c h i v e ) 算法【1 6 1 。该算法引入了一种新的差异策略d e e u r r e n t - t o - p b e s t b i n ， 其变异算子为= 气g + 巧( 圪 譬一而，g ) + 巧( i ，g 一薪2 培) 。该算法的e 、c 墨都是随 着进化过程而变化，f 是记录成功的，值经过计算之后产生的柯西分布随机值，c r 是记录成功的c r 值经过计算之后产生的正态分布随机数。j a d e 中还采用了外部存 档机制，将一些进化过程中被抛弃的个体存档，变异算子中的x ，2 ，g 就是从当前群体 和外部存档的合集中随机选取的个体，圪培是从当前群体中的p 最优秀的个体中 8 硕士学位论文第二章差异进化算法 随机选取的个体。 实验表明，j a d e 比d e a s p 、j d e 、s a n s d e 的求解结果都要好，具有搜索能 力强，不易陷入局部极值点的特点，与其他改进的d e 算法相比，表现出很大的优 势，是目前效果最好的d e 算法。 2 5 差异进化算法的研究热点 在进化算法中由于选择作用的影响，随着进化代数的增加，个体间的差异会逐 渐降低。个体差异性的减少又影响变异所带来的多样性，从而导致算法过早收敛到 局部极值附近时，形成早熟收敛现象。除了早熟收敛现象，还有种群分布过于分散， 收敛速度太慢的晚熟不收敛现象。作为一种进化算法的d e ，为了提高其寻优能力、 加快收敛速度、克服启发式算法常见的早熟收敛以及晚熟不收敛现象，是许多学者 对d e 算法进行改进的研究方向。 1 选择参数 d e 的参数有种群规模胛、搜索步长，、交叉概率c r 这3 个控制参数。通常 的做法是根据经验选取一组固定参数【1 7 】。，为缩放步长，用以控制差异向量的搜索 步长，一般情况下取值在【o ，2 】之间，c r 是种群中个体交叉的概率，脚代表种群规 模。研究者从不同角度对3 个参数对于差异进化算法的影响进行了讨论，并且证明 了3 个参数的设置对于算法计算效率、有效性、鲁棒性紧密相关。因此在改进d e 算法时，需要选择正确的参数配置。 2 改进收敛性 差异进化中，好的基因总会保留并传播，而且有两个机制，可以保证其收敛：1 ) 总是优势个体替换劣势个体，可以保证其一直向前进化；2 ) 搜索步长开始时大，后 来逐步减小，能够保证搜索范围和精度。差异进化算法的进化方式称之为贪婪选择， 在进化过程的选择中，适应值高的个体被保留，适应值低的个体则不断被抛弃。经 过多轮迭代过程之后，种群中个体逐渐向最佳个体，靠拢，多样性逐渐降低，个 体差异变得越来越小，最终导致差异向量趋于零。对于单峰函数，这种机制一般情 况下会求解出最佳解，但是对于多峰函数，如果，仅仅只是个局部最优点，那 么变异操作和交叉操作将失去进化作用，导致算法陷入局部最优而出现早熟收敛现 象。要克服上述基本算法中贪婪选择的缺陷，必须减缓种群多样性的下降速度，适 当保持个体间的差异，同时保证一定的收敛速度。为此，n o m a i l 【1 8 】、a b b a s s 1 9 】、张 航【2 0 】等学者在这方面进行了深入的研究工作，并提出了很多行之有效的办法。 3 改进操作算子 标准d e 中的变异、交叉和选择算子实现简单，具有很大的改进空间，因此许 多研究者在这方面做了很多研究。 9 候停止使用，才能既充分发挥局部搜索的优势，又避免局部搜索带来的缺 陷。 4 ) 局部搜索策略。针对一个问题，有多种可选的局部搜索策略，这些策略效 率不同。通常效率越高的策略，其运算越复杂，需要权衡利弊。 h a r t 2 6 分析7 - - 种局部搜索算法：随机搜索法、共轭梯度法、随机逼近法。随 机搜索法是对一个个体的各维加上一个零均值正态随机偏差，产生一个新个体，如 果新个体比原个体差，在反方向产生一个个体。随机偏差的方差将随着产生个体的 好坏白适应的增大缩小。共轭梯度法，是顺着个体的进化梯度方向试探寻找。随机 逼近法是随机选择一个逼近对象，以一定步长逐步逼近，在个体附近搜索。l e e 掣2 刀 提出一种基于适应性步长的局部搜索来确定合适的缩放比例因子，从而加速算法搜 1 0 硕士学位论文第二章差异进化算法 索的进程。 5 混合其他算法 针对d e 中缺点，混合其他算法也成为改进d e 的研究热点。a h u j a 和o r l i n 认 为【2 8 1 ，进化应当结合随机搜索与方向性搜索，能够组合父代的优秀基因而产生优于 父代的子代个体。因此，为了能够在差异进化中实现方向性搜索，最直接的方法就 是结合传统的最优化技术。l i n 等利用梯度信尉2 9 1 、k a e l o 等引入单纯形方法【3 0 1 ，与 差异进化算法相结合，可明显改善差异进化算法的收敛速度，同时也能提高寻优精 度。 此外，也有研究与其他群体智能算法的结合。杨静宇等人【3 l 】采用模拟退火的选 择方式来确定选择概率、c h a k r a b o r 3 2 】采用p s o 算法形式实现实现变异操作、 c h i o u l 3 3 】将蚁群算法的思想引入到d e 中用于对差分策略进行最优选择。 2 6 本章小结 本章概述了d e 的起源、发展、特点、和当前的研究热点。d e 算法的搜索性能 取决于算法全局探索和局部开发能力的平衡，而这在很大程度上依赖于算法的控制 参数的选取，包括种群规模、缩放步长和交叉概率等。相对其他进化算法而言，d e 所需调节的参数较少。归纳起来，d e 算法具有如下优点： l _ ) 算法通用，不依赖于问题信息； 2 ) 算法原理简单，容易实现； 3 ) 群体搜索，具有记忆个体最优解的能力； 4 ) 协同搜索，具有利用个体局部信息和群体全局信息指导进一步搜索的能力； 5 ) 易于与其他算法混合，构造出具有更优性能的算法。 相对于低维的全局优化问题而言，求解高维全局优化问题的难度显著增大。克 服这个难度呈指数增大的高维全局优化问题一种途径是，将搜索空间划分为更小的 子空间进行分别搜索，保证搜索算法能够搜索空间中的每一个可能区域。研究者们 为求解高维全局优化问题，发展出了进化算法的一个分支：协同进化算法。经过十 多年的发展，该类算法在求解高维全局优化问题上，相对于其他算法，表现出了更 好的性能。 1 2 硕士学位论文第三章高维全局优化问题及求解算法 3 3 协同进化算法 在达尔文的进化论中，自然界物种间和同物种个体间，因为生存竞争而优胜劣 汰。但随着人们对自然界的不断观察和研究，发现