（信号与信息处理专业论文）基于拥挤差分进化算法的多模态优化及其应用研究.pdf

荩r 拥挤芽分进化箅法的多模态优化及其麻j j 研究 摘要 多模态优化是近些年兴起的- - f - j 新学科，目前在科研和工程实践的应用需求同显突 出。对航空航天、网络通信、生命科学等诸多实际问题进行数学建模后，都可以将其抽 象为一个数值函数的优化问题，而在大量的实际优化问题的求解计算中，由于生产实践 中种种客观条件的限制，有些全局最优解在实际中往往并不适用，因此不仅要在可行域 内寻找全局最优解，而且需要搜索有意义的局部最优解，这种技术就是多模态优化算法。 针对目前多模态优化存在无法找到全部局部极值解的问题，本文提出了一种基于拥 挤模型的差分进化算法用于多模态优化，利用差分进化算法的全局搜索策略和内在的并 行方式，通过拥挤模型的高群集因子搜索，避免了取代错误，保持了物种的多样性，可 准确定位多模态函数的最优解和全部极值解。同时，该算法具有参数少、操作算子简单、 收敛速度快等特点。实验结果表明，本文提出的拥挤差分进化算法处理多模态优化问题 时在收敛速度、收敛精度上皆明显优于目前处理多模态优化问题效果最好的拥挤遗传算 法。 在m i m o o f d m 系统中，根据信道状况自适应地分配天线与子载波是使信道容量 达到最大的关键技术。本文将拥挤差分进化算法用于解决天线和子载波联合分配问题， 利用该算法参数少、寻优能力强、收敛速度快的特点，可快速确定最佳的天线和子载波 联合分配方案，实现信道容量最大。 认知无线电系统中，对检测出来的频谱进行分配是使频谱效益实现最大的关键过 程。本文将拥挤差分进化算法应用到动态频谱分配，可快速确定能够实现频谱效益最大 的分配方案。 关键词：多模态优化；拥挤差分进化算法；天线和子载波联合分配；动态频谱分配 哈尔滨f 稃人学硕十学位论文 a bs t r a c t m u l t i m o d a l o p t i m i z a t i o n i san e ws u b j e c ta n de x i s t si ns c i e n t i f i cr e s e a r c ha n d p r o d u c t i o na p p l i c a t i o n s a f t e rb u i l d i n gm o d e l s o fs u c ha v i a t i o na n d a e r o s p a c e ，n e t c o m m u n i c a t i o n ，l i f es c i e n t i f i cp r o b l e m s ，i tc a nb ea b s t r a c t e di n t oaf u n c t i o no p t i m i z a t i o n p r o b l e m h o w e v e r ，t h eb e s ts o l u t i o ni sn o ta l w a y su s e f u li nr e a lw o r l d ，a n dt h eo p t i m a l s o l u t i o ni sa l s on e e d e d ac r o w d i n gd 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 mi sp r e s e n t e da n da p p l i e dt om u l t i m o d a l f u n c t i o no p t i m i z a t i o nf o rf i n d i n ga l lt h ee x t r e m es o l u t i o n s ，w h i c hu s e sd e sg l o b a ls e a r c h s t r a t e g ya n di n t e r n a lp a r a l l e lp a t t e r n ，t h r o u g ht h eh i g hc fv a l u es e a r c h ，a v o i d i n gt h e r e p l a c e m e n t e r r o r , m a i n t a i n i n gs p e c i e sd i v e r s i t y ，c a na c c u r a t e l y l o c a t ea l lt h eo p t i m a l s o l u t i o n sa n de x t r e m es o l u t i o n s m e a n w h i l e ，t h i sa l g o r i t h mh a sal o to fa d v a n t a g e ss u c ha s p a r a m e t e rl e s s ，o p e r a t o rs i m p l ea n ds w i f tc o n v e r g e n c er a t e t h ea l g o r i t h mi sc o m p a r e dw i t h c r o w d i n gg e n e t i ca l g o r i t h ma n de x p e r i m e n tr e s u l t ss h o wt h a tc d ei sb e t t e rt oc g ai nb o t h c o n v e r g e n c er a t ea n dc o n v e r g e n c ea c c u r a c y i nt h em i m o - o f d ms y s t e m ，t h ea l l o c a t i o no fc o m b i n e da n t e n n aa n ds u b c a r r i e r a c c o r d i n gt ot h ec h a n n e lc o n d i t i o n si st h ek e yt e c h n o l o g yt om a x i m i z ec h a n n e lc a p a c i t y c d e i sa l s oi n t r o d u c e dt os o l v et h ep r o b l e mo ft h ea l l o c a t i o no fc o m b i n e da n t e n n aa n ds u b c a r d e r i nt h em 1 m o - o f d m s y s t e m t h i sa l g o r i t h mh a ss u c hc h a r a c t e r i s t i c sa sf e wp a r a m e t e r sa n d f a s tc o n v e r g e n c e ，s ot h eb e s ta l l o c a t i o no fc o m b i n e da n t e n n aa n ds u b - c a r r i e rc a nb ef o u n d a c c u r a t e l ya n dq u i c k l ya n dt h em a x i m u mc h a n n e lc a p a c i t yc a nb ea c h i e v e db yu s i n gt h i s a l g o r i t h m t h ea l l o c a t i o no fs p e c t r u mi sa l s os t u d i e di nt h i sp a p e r t h ep a p e ru s e st h ec o n c e p to f c d et os o l v et h ep r o b l e mo fd y n a m i cs p e c t r u ma l l o c a t i o na n dg e ta g o o dr e s u l t k e yw o r d s ：m u l t i m o d a lo p t i m i z a t i o n ；c r o w d i n gd e ；c o m b i n e da n t e n n aa n ds u b c a r r i e r a l l o c a t i o n ；d y n a m i cs p e c t r u ma l l o c a t i o n 第1 章绪论 第1 章绪论 1 1 课题的研究意义和目的 多模态优化是近年来兴起的- - f - 新学科，目前在科研和工程实践的应用需求同显突 出。对机械设计、航空航天、网络通信、作业调度、图像处理、生命科学等诸多实际问 题进行数学建模后，都可以将其抽象为一个数值函数的优化问题【，而在大量的实际优 化问题的求解计算中，由于生产实践中种种客观条件的限制，有些全局最优解在实际中 往往并不适用，因此不仅要在可行域内寻找全局最优解，而且往往需要搜索有意义的局 部最优解，这种技术就是多模态优化算法i 到。 在科学研究和工程实践中优化问题是最常见的问题之一，作为优化问题一个非常重 要分支的多模态优化问题也在生产实践中大量存在，如神经网络的结构及其权值的优化 问题，最优控制律的设计，复杂系统参数及结构辨识问题等都可化为多模念优化问题【3 1 。 某些现代投资组合问题也可以看成是多模态优化问题，该模型需要得到一组不同风险水 平的最优解，以供不同风险偏好的投资者选择。目前，多模念优化算法的研究与应用已 经深入到生产和科研的多个领域，并以取得了显著的经济效益和社会效益。总之，如何 构造一种优化算法，使之能够搜索到全部全局最优解和尽量多的局部最优解，即如何有 效地解决多模态优化问题，已成为一个亟待研究的问题。本课题的研究将对多模态优化 算法的理论发展和实际应用产生积极的推动作用，具有重要的学术意义和工程应用价 值。 多模态优化是优化算法领域国内外公认的难题之一，很多学者一直致力于多模态优 化问题的研究，他们提出了许多多模态优化算法用于解决多模态优化问题，能够在发现 全局最优解的基础上找到一些有意义的局部极值解，但是由于多模态优化问题存在解个 数的不确定性、解空间维数的不确定性、解分布的不确定性决定了解决这一问题的复杂 性，目前的多模态优化算法还不能保证找到全局最优解和全部的极值解。 国外学者为解决多模态优化问题，大多采取用小生境模型改进进化算法的策略，为 此他们提出一系列的小生境模型，这些小生境模型虽然在一定程度上缓解了模式收敛程 度，但仍然存在问题。拥挤模型当c f 值较小时存在较大的选择误差；当c f 值较大时， 不存在选择误差，但计算量增大。适应值共享模型，需要设定与目标函数先验知识相关 的共享半径，且只有当目标函数的峰半径大致相等时才能取得较好的搜索效果。动念小 生境聚类模型聚类数目的计算复杂，且对搜索到的极值数目影响很大。多种群d e 算法 哈尔滨i ：程人学硕 2 忙论文 初期的搜索效率低，且多个子种群的引入，加大了算法的计算量。 在国内，直到2 0 0 2 年爿有多模态优化的相关研究成果发表，起步较晚且大多跟从 国外研究的主要方向，不仅研究人数少而且研究成果与国外也存在一定差距。2 0 1 0 年， 相关核心期刊上发表关于多模态优化的文章有所增加，但文章大部分侧重于对原有小生 境模型的引用，而且缺乏引入新型群体进化算法解决多模态优化问题的文章。 由此可见，目前国内外现存的多模态优化算法仍存在一定的缺陷，为实际应用的需 求研究新型有效的多模态优化算法是完全必要的。通过深入的分析可知，影响多模态优 化效果有两个关键因素：进化算法的选用和小生境模型的选用。本课题经过反复的研究 论证发现，现有的多模态优化算法之所以难以发现全部的局部极值解，是因为它们把保 持种群多样性最终实现发散收敛的“重任”过度依赖小生境模型，而事实证明小生境旧 模型的改进和新模型的提出仍无法保证算法能够找到全部局部极值解，只有让进化算法 分担一部分保持种群多样性的任务，才能保证多模态优化算法整体运行的有效性，成功 地发现全部的局部极值解。因此，研究先进的进化算法来提高多模态优化算法性能是一 个可行的研究思路。 本课题的目的就是通过广泛的调研和深入的研究，提出一种基于拥挤模型的差分进 化算法( c r o w d i n gd i f f e r e n t i a le v o l u t i o n ，c d e ) 用于提高多模念优化的性能，利用高群 集因子拥挤模型能够保持种群多样性的优点，对差分进化算法的操作算子加以改进，从 而能够准确定位多模态函数的全局最优解和全部极值解。差分进化算法非常适合解决多 模态优化问题，该算法采用基于种群的全局搜索策略和基于差分的简单变异操作，能够 快速有效地找到全局最优解，是目前性能最好的进化算法，在多模态优化中的应用国内 尚没有文献报道，基于差分进化算法实现多模态优化是一次创新的尝试。虽然标准差分 进化算法的寻优结果也收敛于全局最优解，但其采用一对一竞争生存策略通过代表整个 解集的种群按内在的并行方式同时搜索多个非劣解，因而容易被改造成用于发现全局最 优解和全部极值解的多模态优化算法。 1 2 课题的国内外研究现状 1 2 1多模态优化国内外研究现状 多模态优化作为一门独立学科出现是在近一二十年问，但对多模态优化的研究可以 追溯剑2 0 世纪6 0 年代【4 1 。传统的多模态优化算法包括基于导数或其他启发式信息搜索 算法，如梯度爬山法等，但这些算法均存在着每次只能找到一个最优解和容易陷入局部 极值的问题。 2 第1 章绪论 现代多模态优化算法大多是基于进化算法的多模态寻优过程。进化算法是信息领域 近年兴起的一种新型搜索寻优技术。它作为一类启发式搜索算法，不仅对优化问题的种 类有很强的鲁棒性，更为重要的是它针对由众多个体组成的种群执行进化操作，其优化 结果是一个集合，因此特别适合用于求解多模态优化问题。 通常情况下，进化算法只能寻找到一个全局最优解，不能直接用于多模态优化问题。 现有的多模态优化算法主要是将拥挤模型、适应度共享机制等小生境模型与进化算法有 机结合，使其能够找到全部的局部极值解。本文通过查阅国内外学术期刊、会议等，对 多模态优化算法研究进行了归纳总结和分析，目前具有代表性的研究成果主要有： 国外方面对多模态优化的研究处于领先地位，他们率先提出了几种基本的小生境模 型，并成功地应用到多模态优化，取得了不错的效果。 d ej o n g 提出的标准拥挤模型【5 1 ( s t a n d a r dc r o w d i n g ) 通过替换相似父代的方法更新种 群。对于每一子代，从父代中选择c f ( c r o w d i n gf a c t o r ，群集因子) 个个体，根据某种距 离定义选择最近的一个，若子代适应值大于该个体，则替换，否则维持种群不变。基于 拥挤模型的遗传算法是一种经典的多模态优化算法，与其它算法相比该算法能找到更多 的局部极值解，但遗传算法自身易于陷入局部最优的缺点使其仍不能保证每次都准确找 到全部的局部极值解。而且拥挤遗传算法在参数c f 值的选择上存在问题：当c f 值较。i 小时，拥挤模型存在较大的选择误差，即每个子代并不能和它最相似的父代竞争，造成 种群多样性难以保证甚至单一模式收敛；当c f 值较大时，虽然不存在选择误差，但计 算量增大。 p 。 h o l l a n d 提出的适应值共享机制【6 l ( f i t n e s ss h a r i n g ) 通过改变个体的适应值影响其被 选择的概率，以促进稳定小生境的形成。对种群中的每个个体，找到在其共享半径内的 其他所有个体，共同分享适应值，分享方式由共享函数确定。基于适应值共享模型的克 隆选择算法是解决多模态优化问题的一种有效算法，其在发现全局最优解和局部极值解 的求解精度和求解速度上都有一定的优势，但是适应值共享需要设定与目标函数先验知 识相关的共享半径，且只有当目标函数的峰半径大致相等时才能取得较好的搜索效果， 使算法存在较大的局限性。 p e t r o w s k i 提出的清除模型i7 j ( c l e a r i n g ) 是一种特殊的适应值共享方法，共享半径内的 所有个体比较适应值，最佳的若干个个体存活，其余个体全部死亡。清除模型的缺点与 适应值其享方法相似。 g a n 将聚类与适应值共享相结合，提出了动态小生境聚类1 8 1 ( d y n a m i cn i c h e c l u s t e r i n g ) 的思想。对于每一代种群均进行聚类，聚类半径u ，变，类内部适应值共享。 哈尔滨l ：群人学硕_ 卜学位论文 但聚类数目的计算复杂，且对搜索到的极值数目影响很大。此外，诸如序列小生境 ( s e q u e n t i a ln i c h i n g ) 、受限联赛选择模型( r e s t r i c t e dt o u r n a m e n ts e l e c t i o n ) 、动态小生境共 享( d y n a m i cn i c h i n g ) 等其它小生境技术也都有各自的缺点，不适合解决复杂的多模态优 化问题。 在国内关于多模态优化算法的研究始于2 0 0 2 年，到目前为止所发表的文献较少且 研究成果较国外存在一定差距，特别是所发表文章大都是应用国外成型的小生境方法， 且尚未尝试引入高级的群体进化算法如差分进化算法解决多模态优化问题。 郑士芹提出一种改进克隆选择算法f 9 】用于解决多模态优化问题。其主要思想为：将 适应值大于记忆阀值的个体放入记忆库。在记忆库中，对每个个体进行梯度操作，使其 达到所在的峰，然后进行抑制操作。其本质是一种基于共享机制的小生境技术，该算法 操作算子简单有效，但如果出现比较低的峰，记忆阀值的选取就会失去意义，在峰比较 集中的情况下也容易丢失极值解。 吕佳提出一种多模态优化的混沌免疫网络算法【1 0 j 。该算法利用混沌变量来模拟免疫 细胞的增殖方式，在一定程度上增加了发现更多局部极值解的机会，但仍无法保证每次 都能找到全部的局部极值解。 谭竹梅提出一种排挤小生态遗传算法的改进方法【1 l 】。该算法通过分析适应值曲面的 拓扑结构和扩大相似性个体的搜索范围，减少了排挤的替换错误并抑制了种群的遗传漂 移，通过结合确定性替换和概率替换策略，提高了并行子种群的维持能力。但是算法复 杂度较高，而且对问题的先验知识依赖较大。 王湘中提出一种多模态优化的多种群进化策略【1 2 】。该算法在使用单基因变异、精英 繁殖、递减型策略参数的进化策略基础上，提出了一种求解多模态函数多个极值点的多 种群协同进化策略，并给出了子种群进化概率、停止条件的确定和收敛到极值点的判断 条件。其采用的山谷探索法仍属拓扑结构分析法，具有复杂度高，依赖先验知识的缺陷。 此外，唐超礼提出一种多模态优化的小生境蚁群算法l l 引，李敏强提出一种多模态优 化的协同多群体遗传算法i ，都是对解决多模态优化问题的积极探索，但其仍不能快速 有效地发现全部的局部极值解。 综上所述，现有的多模态优化算法还存在一定缺陷，尤其是国内对这方面问题的研 究属于刚刚起步阶段，因此开展多模态优化算法的研究具有十分迫切的理论意义。 1 2 2 差分进化算法的研究现状 差分进化算法1 1 4 l ( d i f f e r e n t i a le v o l u t i o n ，d e ) 是1 9 9 5 年s t o r n 等人提出的一种进化算 4 第1 章绪论 法，2 0 0 4 年被引入国内。最初的设想是用于解决切比雪夫多项式问题，后来发现d e 算 法也是解决复杂优化问题的有效技术。d e 算法和微粒群算法一样，都是基于群体智能 理论的进化算法，通过群体内个体间的合作与竞争产生的群体智能指导优化搜索。但相 比于其它进化算法，d e 算法保留了基于种群的全局搜索策略，采用实数编码、基于差 分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，d e 算 法特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的 全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学 规划方法所无法求解的复杂环境中的优化问题。因此，d e 算法作为一种高效的并行搜 索算法，对其进行理论和应用研究具有重要的学术意义和工程价值。目前，d e 算法已 经在许多领域得到了应用，如人工神经元网络、机器人、信号处理等。 在国外，已经有学者将d e 算法引入多模态优化问题的研究，并取得了不错的优化 效果。z a h a r i e 提出了多种群d e 算法i l 引，并用于求解多极值的优化问题。q i n g 发展了 多种群d e 算法，引入跨种群间的竞争算子来实现种群间信息共享，并利用该算法解决 了多个超导柱体电磁反转散射问题1 1 6 l 。p l a g i a n a k o s 等提出并行d e 算法1 1 7 l ，各个子种群一 独立进化，并利用环形网络拓扑来实现子种群之间的通信。多种群d e 算法仍不能保证 每次都找到全部的局部极值解，且存在初期的搜索效率低、计算量大等缺点。目前国晦、一j ： 尚无人将d e 算法引入多模态优化问题研究。本课题将借鉴国外研究成果，探讨实现基 于差分进化算法的多模态优化，并进一步研究其在实际应用中的效果。 1 3 课题研究内容及论文安排 ” 本课题属于基础理论研究，旨在对多模态优化的相关算法进行总结，并针对目前多 模态优化不能准确找到全局最优解和全部局部极值解的缺陷，在深入进行理论分析的基 础上提出一种基于拥挤模型的差分进化算法，用于提高多模态优化性能。 本课题还将该算法应用到m i m o o f d m 系统天线和子载波联合分配、认知无线电 系统动态频谱分配两个实际问题中，利用该算法能够准确发现全局最优解的性能，来快 速地确定最佳的m i m o o f d m 系统天线和子载波联合分配方案和认知无线电系统动念 频谱分配方案。为此，本论文的具体内容安排如下： 第1 章为绪论。首先介绍多模念优化的研究意义和目的，然后总结多模态优化算法 的国内外研究现状，给出主要多模念优化算法的实现思想，并分析其优势和缺陷。最后， 列出本文的主要：1 j 作和内容安排。 第2 章主要介绍多模念优化的基本理论知识。首先指出多模态优化算法足小q i 境 ， 5 哈尔滨l ：样人学硕十7 ：伊论文 技术和进化算法这两种关键技术实现，然后在分别介绍多模态优化的进化算法和小生境 模型的基础上，重点阐述了本课题采用的拥挤模型和差分进化算法。 第3 章将提出用于多模态优化的拥挤差分进化算法，并通过算法对四个具有代表性 的多模态函数的优化处理证明其解决多模态优化问题的高效性。 第4 章将本文提出的拥挤差分进化算法用于解决m i m o o f d m 系统天线和子载波 联合分配问题。首先给出天线和子载波联合分配的原理和数学模型，然后具体列出将本 文提出的拥挤差分进化算法用于天线和子载波联合分配的实现步骤，最后以实验仿真的 形式证明此种分配算法能够实现最佳的天线和子载波联合分配。 第5 章将本文提出的拥挤差分进化算法用于解决认知无线电系统动态频谱分配问 题。首先给出动态频谱分配的原理，然后列出将拥挤差分进化算法用于动态频谱分配的 实现步骤，最后以实验仿真的形式证明此种分配算法能够实现最佳的动态频谱分配。 6 第2 章多模态优化算法 第2 章多模态优化算法 多模态优化是近年来兴起的一门新兴学科，但对多模态优化问题的研究可以追溯到 2 0 世纪6 0 年代。科技工作者们很早就意识到，有时候全局最优解在实际中由于客观条 件的限制往往并不适用，在提出实际解决方案的同时，他们往往准备几种备选方案，这 就是多模态优化思想的萌芽。随着优化技术的发展，多模态优化算法得到了重视和研究， 一些基于导数或其他启发式信息搜索的算法被提出用于解决多模态优化问题，但这些算 法均存在着每次只能找到一个最优解和容易陷入局部极值的问题。 现代多模态优化算法大多是基于进化算法的多模态寻优过程。进化算法是信息领域 近年兴起的一种新型搜索寻优技术。自1 9 7 5 年j o h nh o l l a n d 提出遗传算法( g e n e t i c a l g o r i t h m ，g a ) 以来，基于生物模拟的进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 得至w l - r 深 入研究，由于其具有并行、不需要求导或其它辅助知识、一次产生多个解和简单易于实 现等优点，被视为求解多模态优化问题的有效方法1 1 8 i 。 多模态优化要求取全局最优值和全部局部极值解，标准的进化算法只能求取一个全 局最优解，不能直接用于解决多模态优化问题，这就要求对标准的进化算法进行改进， 使之在进化的过程中能够保持种群的多样性，进而完成发散收敛找到全局最优解和全部 的局部极值解。现有的多模态优化算法多为应用各种小生境模型对标准进化算法的改进 算法。为此，本章将分别介绍多模念优化的进化算法和小生境技术，并对本文选用的差 分进化算法和拥挤模型的基本原理进行重点阐述。 2 1 多模态优化的进化算法 进化算法被视为求解多模态优化问题的有效方法，目前应用于解决多模态优化问题 的进化算法可以分为以下三类： 1 以克隆选择算法为代表的人工免疫算法 克隆选择算法的原理是“克隆+ 高频变异+ 选择”，最后实现抗体和抗原的高亲和度 匹配【1 9 】。抗体也具有抗原性，在克隆增殖过程中会被其它抗体视作抗原，最后多个抗体 达到动态平衡。这多个抗体也可以看成多模态优化要寻找的多个最优解。克隆选择算法 在原理上与多模态优化有着天然适应性。 2 以d e 算法为代表的群体智能优化算法 多模态优化算法可以浓缩为“小生境模型+ 进化算法 ，算法的复杂度和进化算法 的效率息息相关。此时，新兴的群体智能优化算法如差分进化算法，就疆示出求解多模 7 哈尔溟l 午# 人。字：颂十学何论文 态优化问题巨大的优越性，目前己成为国外求解多模态优化问题的研究热点1 1 5 - 1 7 , 2 0 1 。就 d e 算法而言，相比于其它进化算法，其保留了基于种群的全局搜索策略，采用实数编 码、基于差分的简单变异操作和一对一的竞争生存策略，提升保持种群多样性能力的同 时降低了遗传操作的复杂性。d e 算法还特有记忆能力能够动态跟踪当前的搜索情况。 作为本文主要研究的进化算法，差分进化算法原理在下一节予以重点介绍。 3 传统的遗传算法 传统的遗传算法技术成熟，很早就用于解决多模态优化问题，有很多针对遗传算法 本身的有效改进以及和小生境模型的巧妙结合，使其在解决多模态优化问题时发挥着重 要的作用。比如一些基于遗传算法的多模态优化算法就特别考虑了多模态函数的拓扑结 构，能够发现全局最优解和更多的局部极值解，但是使用这些多模态优化算法时存在一 定的局限性，算法自身的复杂度也较高。 2 1 1 差分进化算法 差分进化算法是1 9 9 5 年s t o r n 等人提出的一种优化算法，2 0 0 4 年被引入国内。d e 算法通过众多无智能的简单个体相互合作表现出的智能行为指导优化搜索，其本质是一 种基于运动补偿发生变异的遗传算法。它保留了基于种群的全局搜索策略，采用实数编 码、基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同 时，d e 算法特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略， 具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用 常规的数学规划方法所无法求解的复杂环境中的优化问题。相对传统多模态优化方法， 差分进化算法按内在并行的方式寻找最优解，有利于快速有效的找到多模态意义下的最 优解。因此差分进化算法成为目前解决多模态优化问题最为有效的方法。 d e 算法最大的特点是以变异的方式产生新的个体，对于种群中的每一个体，随机 选取与之不同的三个个体，求取其中两个个体的矢量差并乘上一个缩放比例因子，接着 和另外一个个体矢量求和。然后，让这个新产生的变异种群以一定的交叉概率代替原种 群的个体，形成新种群。最后，进行基于贪婪策略的一对一竞争比较，即每个子代都和 自己的父代比较，适应值高的个体生存，形成的新种群接着进行上述操作，直至种群完 全收敛。 d e 算法工作原理框图如图2 1 所示。 8 第2 章多模态优化算法 图2 1 筹分进化算法一f ：作原理框图 簿i 。o o 。 一 算法首先在问题的可行解空间内随机产生初始种群，x 1 = 暖，z ，咖】，其中 p o p n u m 为种群规模，上标1 表示第1 代。个体霉= k 。，薯2 ，一x f d 1 】用于表征问题解，d 是优 化问题的维数。 对种群进行变异操作，产生临时的变异种群。具体而言，对于种群中每个个体按照 如下公式产生新的变异个体： 霉 ，o 、- 了= e ，+ f “，一，) ( 2 - 1 ) 式中：口，b ，c e 1 ，2 ，坳“朋 互不相同且与f 不同。z t + l 为子代i 的l 基因位；z ：，为 父代口吻基因位；x ：。，一石。t ，为父代6 与c 萄基因位上的差分向量；f 为缩放比例因子。 可以看出，这个公式的含义就是对个体j 的，基因位进行修改。 然后以一定的交叉概率决定变异个体是否代替父代个体进入新种群。按照如下方式 进行： 如果( r a n ds c r ) o r j = 聊硪功成立，则变异个体进入新种群。即如果当随机数小于 交叉概率或者随机数正好等于变异基凶位，则变异个体代替父代个体进入新种群。其中 r a n d 为【o r l z f b j 的均匀分布随机数：c r 为范围在【0 ，l 】之间的变异概率：r a n d ( d ) 为 1 ，2 d ) 之间的随机量，_ 为可能发生变异的琏凶位。 最后，新种群中的子代个体和原种群的柏应父代个体进行一对一竞争乍存。即比较 子代z “与父代x ；的适应值大小，如果f 代彳更好的适应值则取代之。重复以上步骤， 9 哈尔演l ：袢人硕+ 学位论文 直至种群完全收敛。 2 1 2 遗传算法 基于遗传算法的多模态优化是目前较为经典的算法，通常情况下所提出的新算法都 与之进行比较，来验证算法的优越性。本课题也将通过与之的对比仿真实验来验证所提 出算法的优越性，为此这里简要介绍一下遗传算法的原理及流程。 遗传算法是基于适者生存、优胜劣汰的生物理论而提出的一种进化算法。遗传算法 的核心思想是：求解问题过程中，将问题的所有可能解视为遗传空间，并将问题的每个 可能解作为一个染色体( c h r o m o s o m e ) ，染色体是由一些影响问题的解的因素组成， 这种因素称为基因( g e n e ) ，而所有染色体的集合叫做群体( p o p u l a t i o n ) 。算法首先将 按照一定的规则或通过随机的方式产生初始群体，并选择适当的适应度函数作为 评定初始群体每个染色体优劣的标准，适应度越大，染色体越优秀；反之亦然。 然后根据优胜劣汰的机制淘汰适应度较小的染色体，为使群体向着更好的方向发 展，再通过遗传算子对群体进行交叉( 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 ) ，并作为待求解问题的近似最优解输出。 遗传算法流程图如图2 2 所示。 图2 2 遗传算法流程图 l o 第2 章多模态优化算法 遗传算法的主要操作过程： 1 编码 编码即将待解决问题变换到遗传算法的求解空间，将实际问题应用遗传算法进行数 学建模。 2 初始种群的产生 在所有可能的解空间中，按照一定的规则或通过随机的方式产生个初始解， 每个初始解称为一个染色体，个染色体组成一个初始群体。遗传算法以这个初始 群体为起始点进行寻优迭代。 3 适应度函数的确定：适应度函数是评价染色体优劣的唯一标准。适应度函数随待 求解问题的不同而不同。在求解极小值或负数问题时，需对适应度函数进行等效变换， 先求出极大值，在变换成极小值。 4 遗传算子的运算：遗传算子包括选择、交叉和变异，它是遗传算法的核心，为此， 将详细介绍选择、交叉、变异的具体操作。 4 j 基于优胜劣汰的机制，遗传算法的选择操作根据染色体适应度的大小将优秀的染色 体作为下一代群体，而淘汰适应度较小的染色体。选择的本质是染色体的复制，用群体 中的某个染色体以某种方式替换另一个染色体，它是生物能够保持性状而达到物种稳定 的最主要原因。通过选择操作可促使整个群体向着高质量的群体繁衍。 最常用的选择策略是适应度比例法，又叫轮盘赌法。它将群体中所有染色体的适应 度值看作一个轮盘，每个染色体根据其适应度值的不同占用该轮盘的面积不同，适应度 越大，所占的面积越大。轮盘旋转后随机停在某个区域，其对应的染色体即被选中。显 而易见，适应度大的染色体被选中的概率大，该被选中的概率叫做生存概率，可用式( 2 2 ) 表示： 肛一厂 ) 厂“) ( 2 - 2 ) r 式中n 为群体染色体总数，罗厂( t ) 表示种群中所有染色体的适应度值总和，公式 篇 ( 2 2 ) 表明，染色体的适应度越大，被选择作为下一代群体的概率就越大。 交叉操作又称交换操作，它通过对群体的某两个染色体的部分基因进行交换，产生 新的染色体，以确保群体多样性。交叉操作得到的新一代个体，综合了父代个体的特性， 体现了信息交叉的思想。 交叉操作首先从选择得到的群体中随机选取要进行交叉操作的染色体；然后从长度 哈尔滨i ：样人予：硕_ f j 予：何论文 为的染色体中，随机选取一个或多个基因位作为交叉点；最后根据交叉概率 见( 0 p 。 1 ) 对染色体进行交叉操作，配对染色体在交叉位置处相互交叉各自的内容， 从而形成一对新染色体。 经选择操作和交叉操作后，初始群体在一定程度上得到了进化，但只依靠这两种遗 传操作得到新群体是远远不够的，通过这种方式得到的解很有可能仍然是问题的局部最 优解，因为算法并不能保证没有丢失一些重要信息或已经充分挖掘了潜在的最优解。所 以，为进一步扩大近似最优解的搜索范围，通过模拟生物基因突变这一现象，在算法中 引入变异算子以产生新的染色体。虽然基因突变的概率很小，但其在生物进化过程中的 作用是至关重要的。变异算子在一定程度上克服了群体陷入局部最优的缺陷，提升了遗 传算法的全局搜索能力，使群体的多样性得到了保障。 2 2 1 多模态优化的小生境技术 人工智能的发展使人们开始有意识的将自然界的规律应用到科学研究和实践应用 中，小生境技术就是在这样的背景下产生的。在自然界中，“物以类聚，人以群分”是 一种非常普遍的现象，自然界的所有生物一般都倾向于与自己形状相似、特性类似的生 物生活在一起，在繁殖后代方面更是选择与同类交配，这种交配方式在生物进化过程中 起到了积极的作用【2 2 1 。 在生物学中，把具有共同特性的组织称为物种( s p e c i e s ) ，把物种赖以生存的环境称 为小生境( n i c h e s ) 。在自然界中，小生境技术表现为：生态环境中分享不同资源的物种的 形成。随着小生境技术的发展，其与进化算法的结合研究已经形成- f - i 独立的学科，并 受到广大学者的关注。应用于进化算法的小生境技术表现为：在一个固定规模的群体中 子群体的形成，每个子群体对应问题的一个任务( 在多模态函数优化问题中，每个任务 对应找到一个峰值) 。小生境技术具有相对简单、有效和通用的特性，它可以促使群体 内个体间的协同合作，使进化算法能够找出优化问题的全局最优解和所有局部最优解。 没有使用小生境技术的进化算法，个体中仅仅存在竞争的关系，最好的个体在进化过程 中会迅速占据整个群体，即一个物种占据环境的全部资源，或者说算法仅能找出其中一 个最优解。 ， 2 2 1 主流小生境技术 1 9 7 0 年，c a v i c c h i o 提出预选择机制【2 3 l ( p r e s e l e c t i o n ) 开辟了小尘境技术的先河， 自此小生境技术步入一个快速发展的时代1 2 4 , 2 5 l 。 第2 章多模态优化算法 目前用于解决多模态优化问题的小生境模型主要有以下两类： 1 拥挤模型 拥挤的策略是：摒弃粗放的保留高适应度子代方案，采用更为精细的子代与相似父 代比较策略，这样的并行计算没有湮没低适应值的极值解，保证了种群的多样性。 2 适应值共享机制 适应值共享机制的核心原理是高适应值区域的候选解均除以一个较大的加权系数 ( 这个系数和适应值有关) ，使之与低适应值区域相仿，这样被保留下来的候选解就是 全部的极值解。 另外，p e t r o w s k i 提出一种c l e a r i n g 机制的小生境模型【7 l 。该算法的思想：修改小生 境内最优个体的适应度，使其参与进化的概率远远大于其它个体，该方法适合于求解复 杂搜索空间的优化问题。 ts u t s u i 等介绍了稳态进化算法的两种改进方法，称为f o r k i n g ( 分叉) 改进【矧。这 两种方法都是利用分叉技术以细分搜索空问。一种方法是用s a l i e n ts c h e m a 细分基因型 空间，而另一种方法则以当前最佳个体为中心利用n e i g h b o r h o o dh y p e r c u b e s 细分表现型。 空问。两种方法中搜索空间细分都取决于当前群体和解的收敛情况。 j e l a s i t y 提出了一种可变半径的小生境实现方法i 矧。该方法中，物种以表现型搜索 空间的点为中心，以r a d i u sf u n c t i o n 为半径确定一个物种。每个物种表述搜索空间中互 不相交的区域。该方法使用一种类似于模拟退火的c o o l i n g 技术，使得搜索朝着最优解 ， q 所在的区域逐步收敛。 。 g a n 和w a w i c k 提出一种小生境动态聚集方法1 8 i 。该方法在初始化种群时，以每个 个体为中心建立小生境，之后通过某种规则对小生境进行合并或重新生成，最后根据当 代群体的小生境数修改各个个体的适应度，并以该适应度值进行进化操作。 林焰提出基于隔离机制的小生境实现方法i 捌。其基本思想是将初始群体分成几个子 群体，子群体的规模正比于其平均适应值，但子群体拥有的规模必须满足最大允许规模 和最小允许规模的限制，之后在子群体间及其内部执行“优胜劣汰，适者生存来实现 种群的进化。该方法算法简单，且高度模仿生物学中物种的地域隔离进化，隔离机制对 于保持解群的多样性和引导解群进化方面具有重要作用，有较高的理论探讨价值和良好 的应用前景。但该方法子群体数的选取需要知道最优解的个数。 小生境进化算法是在进化算法的原有结构上引入小生境技术，不但不影响进化算法 的原有特点，而且既能维持种群多样性，又能提高进化算法处理多模态优化问题的能力。 因此，可以肯定，小生境技术将大大拓宽进化算法的上- - t l 应用范围，特别适用于对所有 1 3 哈尔溟t 科人7 ：硕十予：何论文 或大部分局部最优解感兴趣的应用领域。 2 2 2 拥挤模型 1 9 7 5 年，d ej o n g 将预选择机制理念具体实现，提出一种基于拥挤机制的小生境实 现方法【2 9 1 。d ej o n g 提出的标准拥挤模型( s t a n d a r dc r o w d i n g ) 通过替换相似父代的方法更 新种群。对于每一子代，从父代中选择c f ( c r o w d i n gf a c t o r ) 个个体组成子集合，根据某 种距离定义选择最近的一个，若子代适应值大于该个体，则替换，否则维持种群不变。 拥挤模型的目标是保护种群多样性，在搜索空间以更好的机会来定位全局最优值和全部 的极值解。 m a h f o u d 对拥挤模型进行了更为细致的研究，指出在算法应用中，拥挤模型的随机 替代技术将产生大量基因漂移，使算法收敛子局部最优解【矧。m a h f o u d 进一步具体化了 拥挤模型，提出了一种“确定性排挤机制 ( d e t e r m i n i s t i cc r o w d i n g ，d c ) 的小生境技 术，这种方法从本质上说是一种群集因子值为2 的特殊拥挤模型。d c 的基本思想是将 父代群体两两随机配对，若群体规模为p o p n u m ，则配对后的父代个体为p o p n u m 2 对。 每对父代个体按照进化算法的操作算子进行操作，生成两个子代个体。两个子代个体分 别与相似父代进行竞争，适应度高的个体存活进入下一代循环。 本课题将选用拥挤模型作为多模态优化算法的小生境模型，相比适应值共享模型， 拥挤模型具有以下优势： 1 拥挤模型不需要预先知道多模态最优解的个数，而适应值共享机制必须事先获 得这点先验知识。我们可以这样理解，拥挤模型是一种“全自动的多模态优化算法， 无论解有多少个或出现在什么位置，算法都能对种群内的个体进行分类并完成发散收 敛，找到全部的极值解，而适应值共享机制能算一种“半自动”的多模态优化算法。 2 相对适应值共享机制，拥挤模型需要更小的计算量。从本质上看，拥挤模型是 在自变量空间完成的聚类，而适应值共享机制是在函数空间修改适应度值实现的聚类， 显然拥挤模型需要的计算量小，这种优势会在适应度函数复杂时更加明显。 3 d e 算法和拥挤模型有着天然的相似性。它们都是应用一对一的竞争生存策略， 即基于贪婪的选择方式。只是d e 算法中，子代直接与父代比较，根据适应度值决定是 否取代；而捌挤模型是子代率先从c f 子集中选出距离最近的父代个体，然后根据适应 度值决定是否取代。可以认为，d e 算法是“亲父子”间的比较，而拥挤模型是距离最 近的“f 父子”问的比较。捐j 挤模型这种更为精细化的比较方式，有利于保持物种多样 性，保证算法找到全局最优解和全部的局部极值解。 1 4 第2 章多模态优化算法 因此，本课题选用拥挤模型作为多模态优化算法的小生境技术，其具体实现算法如 下所示： 对于每一子代+ 1 ，从父代c f 子集中，根据公式( 2 3 ) 选择最近的一个个体y ， 若子代适应值大于