（应用数学专业论文）差分进化算法及其应用.pdf

摘要 在最优化领域，一些常规的计算方法如牛顿法、共扼梯度法、单纯形法等很 难解决多峰、高维等复杂的优化问题。针对这类问题，人们通过模拟自然界的进 化过程，进而提出各种模拟算法用于解决这类问题。基于这种思想而发展起来的 一种通用的问题求解方法，我们统称为进化算法。它可以在不用描述问题的全部 特征的情况下，采用简单的编码技术来表示各种复杂的结构，通过对编码进行简 单的操作和优胜劣汰的自然选择来指导学习和确定搜索方向。这种崭新的特点使 得进化算法不仅能获得较高的效率而且具有简单、易于操作和通用的特性，因此 进化算法越来越受到人们的青睐。 近年来，一种新的进化算法一差分进化算法( d 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 m ，d e ) ，被各国学者所广泛关注。它的主要特点是算法简单、收敛速度 快，所需领域知识少。通过大量研究发现，d e 算法具有很强的收敛能力，比较 适合于解决复杂的优化问题。 d e 算法从2 0 0 0 年以后才开始被大多数学者研究，已取得了不少研究成果， 与其它进化算法相比，d e 算法用于求解最优问题时优势比较明显，但也发现算 法存在许多待改进的地方，无论是从理论角度还是从实践方面考虑，d e 算法目 前都尚未成熟。因此很有必要继续研究d e 算法，从而扩大算法的应用领域，解 决更多的问题。 本文首先分析了研究d e 算法的重要意义，接着对d e 算法相关的研究问题， 如算法的基本结构、算法特点、参数设置、改进方法、实现模式及应用等做了较 为系统的研究，并将d e 算法用于解决最优特征子集提取，最优神经网络结构设 计等应用问题。 本文的主要研究成果可归纳如下： ( 1 ) 全面的介绍了d e 算法的原理，基本结构，实现模式和国内外学者对算 法的改进措施及相关应用领域；针对d e 算法的控制参数，通过标准函数的测试， 对算法的参数选取问题进行了较为细致的研究。 ( 2 ) 由于d e 算法是一神实数编码的优化算法，不能很好的解决离敖优化问 题，针对这类应用问题，本文提出一种二进制离散编码方法，并将该方法应用于 特征子集选择问题中。通过实验分析，这种方法能够有效的提取特征，从而提高 了分类算法的预测准确率。 ( 3 ) 人工神经网络在工程领域有着广泛应用，尤其是b p 网络和r b f 网络， 但它们的学习算法存在训练速度慢、易陷入局部极小和全局搜索能力弱等缺点。 而d e 算法不要求目标函数具有连续性，且它的搜索具有全局性和并行性，因此 构建了一个用d e 算法训练网络结构和权值的进化神经网络模型，分别用于训练 b p 网络和r b f 网络，通过测试，取得了良好的效果。 关键词：进化算法，差分进化算法，特征子集选择，b p 神经网络，r b f 神经网 络 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 ma n di t sa p p l i c a t i o n a bs t r a c t i no p t i m i z a t i o na r e a , s o m ec o m m o nc o m p u t a t i o nt e c h n i q u e ss u c ha sn e w t o n m e t h o d , c o n j u g a t eg r a d i e n tm e t h o d , s i m p l e xa r e d i f f i c u l tt os o l v ec o m p l e x m u l t i m o d a lp r o b l e m sw i t hh i g h - d i m e n s i o n f o rs o l v i n gt h e s ep r o b l e m s ，r e s e a r c h e r s g i v e ns o m ea d v a n c e ds i m u l a t i o na l g o r i t h m st o s i m u l a t et h e mb a s e do nn a t u r e e v o l u t i o np r o g r e s s t h i sc o m m o nm e t h o d sw h i c hc o m ef r o mt h ei d e ao fn a t u r e e v o l u t i o na n dw ec a l l e dt h e m “e v o l m i o na l g o r i t h m ”t h e s em e t h o d sw h i c hd o n tn e e d m o r es p e c i f i ci n f o r m a t i o no fp r o b l e m sa d o p ts i m p l ee n c o d i n gt e c h n i q u et oi n d i c a t e c o m p l e xs t r u c t u r e ，u s es i m p l ep r o c e s s i n go nt h ee n c o d i n ga n ds e l e c t i o nm e t h o db a s e d o nn a t u r a ls e l e c t i o nm e c h a n i s mo ft h es u r v i v a lo ft h ef i t t e s tt og u i d et h es e a r c h d i r e c t i o n b a s e do nt h e s es p e c i a lf e a t u r e s ，e v o l u t i o na l g o r i t h ma r ev e r ys i m p l ea n d p o p u l a rt ou s ea n dg e tm o r ee f f i c i e n c ye a s i l y i nr e c e n t l yy e a r s ，an e we v o l u t i o na l g o r i t h mw h i c hc a l l e d “d 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 m ”i sv e r yf a m o u sa n dp o p u l a r i th a ss o m ef e a t u r e ss u c ha ss i m p l et ou s e ， f a s t c o n v e r g e n c es p e e da n dn e e d l i t t l ei n f o r m a t i o na b o u tp r o b l e m s t h r o u g h r e s e a r c h i n g ，w ef o u n di t i sv e r ys u i t a b l et os o l v es o m ec o m p l e xo p t i m i z a t i o n p r o b l e m s r e s e a r c h e r sb e g a nt or e s e a r c ht h ea l g o r i t h mf r o m2 0 0 0y e a r sa n dg o tal o to f p r o d u c t i o n c o m p a r e dw i t ho t h e re v o l u t i o na l g o r i t h m s ， 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 mi sm o r ee f f e c t i v et os o l v eo p t i m i z a t i o np r o b l e m s ，b u t w ef o u n ds o m ef a u l t sa n dt h ea l g o r i t h mi sn o tm a t u r e s ow em u s tk e 印o n r e s e a r c h i n g i ta n de x t e n di t sa p p l i c a t i o na s p e c t i nt h i s p a p e r , f i r s t l y , w ei n t r o d u c e dt h ei m p o r t a n c eo fd 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 m ；s e c o n d l y ，w ea n a l y z e ds o m es p e c i a lp r o b l e m sa b o u td 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 ms u c ha sd a t as t r u c t u r e ，p a r a m e t e rs e t t i n g ，i m p r o v e dm e t h o d sa n da p p l i c a t i o n c t o ；t h i r d l y , w eu s e dt h ea l g o r i t h mt os o l v ef e a t u r es e l e c t i o np r o b l e m ；l a s t l y , w eu s ei t t oo p t i m i z et h en e u r a ln e t w o r ks t r u c t u r e t h em a i nc o n t r i b u t i o no f t h i sp a p e rc a nb es u m m a r i z e da sf o l l o w s ： ( 1 ) o n et h e o n eh a n d ，w e f u l l yi n t r o d u c e d t h et h e o r y , b a s i c s t r u c t u r e ， i m p l e m e n t i n g , i m p r o v e dm e t h o d sa n da p p l i c a t i o n so fd 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 o nt h eo t h e rh a n d ，w eh a v ed o n ee m b e d d e dr e s e a r c ha b o u tp a r a m e t e r ss e l e c t i o na n d s e t t i n gp r o b l e m s ( 2 ) b e c a u s ed 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 ma d o p tr e a ln u m b e re n c o d i n gf o r m a t ， i ti su n s u i t a b l et os o l v es o m ed i s c r e t eo p t i m i z a t i o np r o b l e m s t h e nw ea d d r e s s e da b i n a r ye n c o d i n gd i s c r e t ed i f f e r e n t i a le v o l u t i o na n du s ei tt os o l v ef e a t u r es e l e c t i o n p r o b l e m s t h r o u g he x p e r i m e n ta n a l y s i s ，t h em e t h o di se f f i c i e n tt og e tt h eb e s tf e a t u r e s u b s e ta n di m p r o v et h ep r e d i c t i o nv e r a c i t yo f c l a s s i f i c a t i o na l g o r i t h m s ( 3 ) t h en e u r a ln e t w o r k sh a v em a n ya p p l i c a t i o n so fe n g i n e e r i n g ，e s p e c i a l l yf o r b pa n dr b fn e t w o r k s b u tt h e s en e t w o r k sa r ee x i s t e ds o m ef a u l t ss u c ha sl o w e r c o n v e r g e n c es p e e da n de a s i l yg e tt h el o c a lm i n i m u me t e b u td 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 mh a ss o m es p e c i a lf e a t u r e ss u c ha sp a r a l l e lc o m p u t a t i o n ，e a s i l yg e tg l o b a l m i n i m u ma n dd o n tn e e dc o n t i n u i t yc o n s t r a i n t s o ，w eu s ed 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 mt ot r a i nb pa n dr b f n e t w o r k ss t r u c t u r ea n dc o n n e c t i o nv a l u e ，a n dt h e ng e t e v o l u t i o n a ln e t w o r km o d e l s t h r o u g ht e s t i n g0 1 1c l a t a s e t s ，t h e s em e t h o d sc a l lg e tm o r e e f f i c i e n c y y ub i n g ( a p p l i c a t i o no fm a t h e m a t i c s ) d i r e c t e db yp r o f e s s o rx i n g s h ih e k e yw o r d s ：e v o l u t i o na 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 , f e a t u r es u b s e t s e l e c t i o n , b pn e u r a ln e t w o r k , r b fn e u r a ln e t w o r k 西安工程大学学位论文知识产权声明 本人完全了解西安工程大学有关知识产权的规定，即：研究生在校攻读学位 期间学位论文工作的知识产权归属西安工程大学。本人保证毕业离校后，使用学 位论文工作成果或用学位论文工作成果发表论文时署名单位仍然为西安工程大 学。学院有权保留送交的学位论文的复印件，允许学位论文被查阅或借阅；学校 可以公布学位论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存 学位论文。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：石六 指导老师签名：埙鞋时 日 期加田p ；。 西安工程大学学位论文独创性声明 禀承学校严谨的学风与优良的科学道德，本人声明所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加 以标注和致谢的地方外，学位论文中不包含其它人已经发表或撰写过的研究成 果，不包括本人已申请学位或他人已申请学位或其它用途使用过的成果。与我一 同工作的同志对本研究所作的任何贡献均已在论文中作了明确的说明并表示了 感谢。 学位论文与资料若有不实之处，本人承担相关责任。 学位论文作者签名：畲：妥 日 期：a 嘟。；t 6 1绪论 1 t 研究背景及意义 1 绪论 优化是人们在科学研究、工程技术和经济管理等诸多领域中经常碰到的问 题，它所研究的问题是在众多方案中寻找最优方案，从数学的角度就是找到使目 标函数达到最小或最大的条件。法国数学家c a u c h y 首次采用最速梯度下降法解 决无约束优化问题，后来针对约束优化问题又提出了l a g r a n g e 乘数法等。 随着人类生存空间的扩大以及认识世界和改造世界范围的拓宽，人类需要对 客观世界的规律有更全面深入的理解。常规优化方法如牛顿法、共扼梯度法、模 式搜索法、单纯形法等在处理人们所面对的复杂问题时，如高维、多极点、函数 性质复杂等，在解的精度或求解所需时间等方面，结果往往很不能令人满意。因 此设计高效的优化算法成为科学工作者的研究目标之一。 自然界的进化是经过漫长的自适应、进化过程而获得结果的，人们通过模拟 自然界的进化过程，进而提出各种模拟算法用于解决这类复杂的高维、多峰问题。 基于这种思想而发展起来的一种通用的问题求解方法，我们统称为进化算法。它 可以在不用描述问题的全部特征的情况下，采用简单的编码技术来表示各种复杂 的结构，通过对编码进行简单的操作和优胜劣汰的自然选择来指导学习和确定搜 索方向。由于它采用种群的方式组织搜索，这使得它可以同时搜索空间内的多个 区域，而且用种群组织搜索的方式特别适合大规模的并行计算，具有不受搜索空 间限制性条件( 如可微、连续、单峰等) 的约束及不需要其它辅助信息( 如导数) 的特点。这种崭新的特点使得进化算法不仅能获得较高的效率而且具有简单、易 于操作和通用的特性，因此进化算法越来越受到人们的青睐。 近年来，一种新的进化算法一差分进化算法( d 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 m ，简称d e ) ，被各国学者所广泛关注。作为进化算法的一个分支，d e 算法最初由r a i n e fs t o r e 和k e n n e t hp r i c e 于1 9 9 5 年提出“1 。它是一种实数编码 的进化算法，具有较强的全局搜索能力和收敛速率，在解决复杂的全局优化问题 方面，差分进化算法被实践证明是一种有效的全局最优解的搜索算法。1 。它的主 要特点是算法简单，收敛速度快，所需领域知识少，比较适合于解决复杂的优化 问题。 d e 算法己于1 9 9 5 年被提出，但从2 0 0 0 年以后才开始被大多数学者研究， 目前已取得了不少研究成果，与其它进化算法相比，d e 算法用于求解最优问题 第1 页共“页 绪论 时优势比较明显，但也发现算法存在许多待改进的地方，无论是从理论角度还是 从实践方面考虑，d e 算法目前都尚未成熟。因此很有必要继续研究d e 算法，从 而扩大算法的应用领域，解决更多的问题。 1 2 国内外研究的现状 近几年来，差分进化算法开始在国际进化算法领域流行，取得了一些重要的 理论及应用研究成果。p r i c ek v 通过研究算法的变异操作机制，提出了几种改进 的变异操作，并进行了详细的分析。1 ；差分进化算法的主要参数是变异因子f 和 交叉概率c r ，r o g e rg a m p e r l e 等人通过实验分析，对算法的参数设置问题进行 了探讨。1 ；为了提高算法的收敛速度，很多学者对d e 算法做了研究，如f e n g x u e 等人用模糊逻辑控制理论来动态调整算法的参数“1 ，h u iy u a n 和j o u n il a m p i n e n 通过改进变异操作方式而提出一种三角变异差分进化算法“1 ；在进化算法框架里 有很多类型的算法，j a k o bv e s t e r s t r o m 和r e n et h o m s e n 将差分进化算法、遗传算 法、粒子群优化算法进行实验分析，指出在解决复杂优化问题方面，差分进化算 法的收敛速度更快，稳定性更强”1 ；差分进化算法目前已取得了不少的应用，如 多目标优化问题”一，复杂的约束优化问题。1 ，人工神经网络训练“”，高性能聚类 分析o “，文本聚类问题研究“”，电容器最优设置问题“”，生物反应模型中的参数 优化问题。“，热交换机的优化设计“”，农业灌溉规划。”，地震源定位“”等工程应 用。 国内近几年有少数学者对差分进化算法做了一些研究，如刘明广通过引入迁 徙操作而提出一种修正差分进化算法“，并将差分进化算法用于解决机械设计中 常遇到一类非凸、多峰及非线性函数优化问题“，吴亮红提出的基于群体适应度 方差自适应二次变异的差分进化算法1 ，高飞提出的基于空间收缩的种群灭亡差 分进化算法”“等。 虽然人们对差分进化算法的研究已取得了一系列的理论及应用成果，这些表 明差分进化算法具有十分广泛的发展前景，具有重要理论及应用研究价值。但目 前尚处于研究的初期阶段，还有许多问题需要研究： ( 1 ) 关于差分进化算法的基础理论研究贫乏，差分进化算法在实际应用中 被证明是有效的，但并没有对差分进化算法收敛性问题给出数学证明； ( 2 ) 由于算法的局限性，并不能很好的解决所有问题。在文献”中就指出 差分进化算法处理带噪声的数据效果比较差，对于实际中的多维问题，算法的收 敛速度会很慢，容易陷入局部最优解等。因此需要对算法不断的改进，使得应用 范围更广。 第2 页共“页 i绪论 ( 3 ) 通过合理的编码，利用其具有全局优化的优势，与其它的应用领域如 数据挖掘等结合，从而扩大算法的应用领域，解决更多的问题。 1 3 本文研究的内容 本文的主要研究成果可归纳如下： ( 1 ) 详细的分析了差分进化算法。首先介绍标准差分进化算法，并列举了其 它重要的扩展模式，接着讨论了算法的参数设置问题，指出了算法最优参数设置 的规则，针对标准差分算法的缺陷，如容易陷于局部最优解等问题，介绍了一些 常用的改进思路，并介绍了算法的典型应用领域及其应用效果，最后将d e 算法 同其它流行的进化算法如粒子群算法，遗传算法进行了比较，分析了算法的优缺 点。 ( 2 ) 由于d e 算法是一种实数编码的优化算法，不能很好的解决一些离散优 化问题，针对这类问题，本文提出一种二进制差分进化算法，并将该方法应用于 特征子集选择问题中。 ( 3 ) 利用算法的全局优化能力，将差分进化算法应用于神经网络训练中，针 对b p 网络和r b f 网络存在的问题，如训练速度慢、易陷入局部极小和对样本数 据和参数敏感等缺点，通过合理的编码，利用差分进化算法来动态优化网络的结 构及参数，从而获得最优的神经网络模型。 1 4 本文组织结构 本文主要由五章内容组成。第一章是绪论，主要介绍了研究背景，国内外研 究进展及本文所研究的内容；第二章详细的介绍了标准差分进化算法，相关改进 算法及其应用领域；第三章提出一种二进制编码的差分进化算法，并用于解决特 征子集选择问题：第四章将差分进化算法应用于人工神经网络的训练，针对b p 和r b f 网络分别提出了不同的训练算法；第五章总结了本论文研究的内容及取得 的成果以及未来的研究发展方向。 第3 页共“页 2差分进化算法 2 差分进化算法 2 1 标准差分进化算法 自然界的生物体在遗传、选择和变异的作用下，优胜劣汰，不断地由低级向 高级进化和发展，人们注意到这种适者生存的进化规律的实质可加以形式化而构 成一种优化算法。根据这种进化思想，r a i n e rs t o m 和k e n n e t hp r i c e 于1 9 9 5 年提出 了差分进化算法。它是一种随机的启发式搜索算法，简单易用，以其稳健性和 强大的全局寻优能力己在多个领域取得成功。 从数学角度看差分进化算法是一种随机搜索算法，从工程角度看它是一种自 适应的迭代寻优过程。算法基本思想是从某一随机产生的初始群体开始，通过把 种群中任意两个个体的向量差加权后按一定的规则与第三个个体求和来产生新 个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的适 应度值优于与之相比较的个体的适应度值，则在下一代中就用新个体取代旧个 体，否则旧个体仍保存下来，通过不断地迭代计算，保留优良个体，淘汰劣质个 体，引导搜索过程向最优解逼近。与传统的优化方法相比，差分进化算法具有以 下特点： 差分进化算法不是从一单个点，而是从一个群体开始搜索； 差分进化算法直接对结构对象进行操作，不存在对目标函数的限定 ( 如要求函数可导或连续) ； 差分进化算法具有内在的并行性，因此可以充分利用计算机的并行 计算能力； 差分进化算法采用概率转移规则，不需要确定性的规则； 简单差分进化算法( s i m p l ed 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 ) 采用的选择、交 叉和变异这三种基本差分操作是算法的基础。构成差分进化算法的要素主要有： 个体适应度评价，差分操作和参数设置。 ( 1 )适应度函数 在差分进化算法中，差分操作主要通过适应度函数( f i t n e s s f u n c t i o n ) 的导向 来实现的，它是用来评估个体相对于整个群体的优劣的相对值的大小。通常根据 具体问题定义适应度函数。 ( 2 )差分进化算法的三种差分操作 在迭代过程中，每一代g 的种群中都包含个个体，这个种群可以用个d 第4 页共“页 2差分进化算法 维的参向量来表示：z 。：i = l ，2 ，n ，对于每个个体进行如下操作： 变异操作 变异操作指算法按照这种策略从父代种群中生成新个体进入中间代。 变异策略：对于个体置g ：i = 1 ，2 ，n ，一个新的个体k g + 可通过下式产生： 驯= g + f + ( g x 正) ( 1 ) 这里，吒和吒是从区间【l m 上随机选取的互不相同的整数，且不同于下标指 数f ，变异因子f 是 o ，2 上的一个实常数，其主要作用是控制差分向量k 盯噶盯 的放大程度。 图2 1 以二维h y p e r s p h e r e 函数为例展示变异矢量v g 的生成 f i 9 2 1g e n e r a t i o no f m u t a t i o nv e c | o rv j gu s i n gh y p e r - s p h e r ef u n c t i o n 交叉操作 为了增加新种群的多样性，引入了交叉操作。根据新生成的个体巧。，按 照交叉策略使新旧个体互相交换部分代码，从而形成新的个体。记交叉后的新个 体为： v ，g + l = ( 嘶t , g + l ”2 j g + 1 ，i i d t , g + i ) ( 2 ) 舯m = 饿徽鬻；嬲篇蹴，枞 r a n d b ( y ) 是 0 ，1 之间均匀分布概率，c r 是用户预定义的交叉概率，c r ( 0 ，1 ) ， 第5 页共“页 2 差分进化算法 m b r ( i ) 表示 1 ，d 之间生成的随机整数。 卜滑 l - 1 2 3 4 5 7 i 嚣嚣) 毛口 变异矢量a试用矢量元。 图2 2d e 的交叉操作 f i 9 22c r o s s o v e ro p e r a t i o no f d e 选择操作 为了决定向量v g + 是否能成为第g + i 代种群中的个体，将u g + 。与置6 进行 比较，若前者的适应度值优于后者，则在第g + l 代中就用u g + 。取代置g ，否则 z 。保留。 ( 3 )差分进化算法的运行参数 在使用差分进化算法时有四个运行参数需要提前设定： 群体大小n ，即群体中所含个体数量，一般取2 0 一5 0 ，n 越大，种群 多样性越强，获得最优解概率越大，但是计算时间更长； 最大迭代代数g ，迭代次数越大，最优解更精确，同时计算时间更 长，要根据具体问题设定； 变异因子f ，0 - 2 之间，一般取0 7 ； 交叉概率c r ，o - 1 之间，一般取0 4 ； 这四个参数对差分进化算法的求解结果和求解效率都有很大的影响，因此， 要合理设定这些参数才能获得较好的效果。 下面给出简单差分进化算法的框架，见图2 3 第6 页共“页 2差分进化算法 图2 3 简单差分进化算法运算流程 f i g2 3d i a g r a mo f s i m p l ed i f f e r e n t i a le v o l u t i o n 2 2 差分进化算法研究 从上面的介绍可以看出，简单差分进化算法结构比较简单，作为进化算法的 一个新分支，具有很好的研究价值。要对一个新算法进行进一步改善，提高其性 能，首先要对该算法本身有一个深刻的认识，然后对算法进行实验分析，针对其 存在的问题，结合其它相关的算法知识，提出一定的改进措施。基于这种研究思 路，通过查阅相关文献和最新的国际会议论文，本节主要分析以下内容：首先探 讨了差分进化算法的其它模式，然后对算法的参数设置问题进行了探讨，详细介 绍了当前研究学者对该算法的一些改进措施，并与其他进化算法进行比较，分析 各自的优缺点，最后介绍了算法当前的一些应用领域。 2 2 1d e 算法扩展模式 对于标准d e 算法，通过改进d e 算法的变异操作方式，人们提出了许多模式。 在此列出一些主要模式： 模式1 ：d e r a n d 1 ( 标准d e 算法) 第7 页共4 4 页 2差分进化算法 q g = l 6 + f ( 2 g 一3 g ) 模式2 ：d e b e s t i h ，g = g + ，( 2 6 一3 g ) 模式3 d e r a n d t o b e s t i v g = ，g + f + ( g 一玉，g ) + ，( x 一g 一2 g ) 模式4 ：d e b e s t 2 v 正= 】删 g + ，( 1 g + 2 g 一3 6 一4 ，g ) 模式5 ：d e r a n d 2 v ，g = ，g + f ( l 芦+ x ，2 6 一工r 3 ，g 一4 g ) 注：以上5 种模式中，i = 表示第g 代种群中最好的个体；r l ，r 2 ，r 3 ，r 4 ，r 5 为 随机整数，表示个体在种群中的序号。 在文献。1 中，作者通过大量的函数测试，发现各种模式的d e 算法效果有一定 的差别，其中以模式1 ，模式4 的d e 算法效果最好，但是采用模式1 的d e 算法最为 简单，因此在应用该算法时推荐使用标准d e 算法。 2 2 2d e 算法参数设置问题 在进化算法领域，参数多少及其设置的复杂性常常用于衡量一个算法优劣的 标准。要取得理想的结果，参数的选择至关重要。为了合理的使用d e 算法，发挥 其性能，本节对d e 算法的参数设置问题进行一定的讨论分析，供参考。 在d e 算法中有以下参数需要设置：最大迭代次数g ，种群个体数目，变 异因子，交叉概率c r 。 迭代次数g 依据具体问题而定，g 越大，最终结果越精确，更接近实际目 标，同时计算时间更长。 群体所含个体数量一般介于5 * d 与i o * d 之间( d 为问题空间的维度) ，但 不能少于4 ，否则无法进行变异操作，越大，种群多样性越强，获得最优解概 率越大，但是计算时间更长，一般取2 0 5 0 。 在d e 算法中比较重要的两个参数是变异因子，和交叉概率c r 。f 控制种群 多样性和收敛性，一般在 0 ，2 之间取值，c r 可控制个体参数的各维对交义的 参与程度，以及全局与局部搜索能力的平衡，一般在 0 ，1 之间。文献。1 q h r o g e r g a m p e r l e 详细的介绍t d e 算法的参数设置技巧，指出f 小于一定的值v 将导致算 第8 页共“页 ” d m d a 0 ( ( ( 2差分进化算法 法不收敛，矿依赖适应度函数和其他参数，越大，算法更容易逃出局部极小点， 更容易收敛到全局最优点，但是当f 1 时，收敛速度将变慢，因此最好的选择是 ，耿0 6 。c r 越大，算法更容易收敛，但易发生早熟现象，因此比较合理的设 置是c r = o 3 。 以上讨论了d e 算法的参数设置技巧，但是根据具体问题还是要进行调整的。 2 2 3d e 算法相关改进 在文献“”中作者分析了d e 算法的优越性，和其它进化算法相比，d e 算法具有 以下优点： d e 算法在求解非凸、多峰、非线性函数优化问题表现极强的稳健性； 在同样的精度要求下，d e 算法收敛的速度更快； d e 算法尤其擅长求解高维的函数优化问题； d e 算法操作十分简单，易编程实现； 尽管d e 算法具有上述的各种优点，但其自身的缺陷也是不可回避的。由于 d e 算法的关键步骤“变异操作”是基于群体的差异向量信息来修正各个体的值， 随着进化代数的增加，各个体之间的差异化信息在逐渐缩小，以至于后期收敛速 度变慢，甚至有时会陷入局部最优点。为了克服上述缺点，本节将介绍目前对该 算法的一些改进方案。 简化版本d e 算法( s d e ) 通常d e 算法采用固定的变异因子f ，尽管经验表明f = o 6 比较适合，但是 涉及到具体问题仍需要进行调整。在使用d e 算法时为了减少用户的参与程度，避 免f 值对结果的影响，最好的解决方案是自适应调整f ，因此在这里用肚删， 即取0 ，1 之间的随机数来代替固定值。这种方案称之为简化d e ( s d e ) 。在文献1 中作者对这种方案进行实验分析，表明s d e 还是比较有效的。 修正的d e 算法( m o d i f i e dd e ) 在文献“”中采用自适应线性变异操作，以加快算法收敛速度，并引入迁徙操 作( m i g r a t i o no p e r a t i o n ) 来防止过早收敛，这种改进的差分进化算法称为修正的 d e 算法( m o d i f i e dd e ) 。 自适应线性变异操作定义： x 0 ( t + 1 ) = ( 1 一r ) x ( f ) + 刁( 3 ( f ) 一x p 3 ，( f ) ) ( 8 ) 第9 页共4 4 页 2差分进化算法 f 缶- ) l 其它 ( 9 ) 岛2 击善胞l ( f 州吐，( f ) ) ( 1 0 ) 为预先指定的最小缩放因子，厂眦和k 分别是第t 代中最大和平均函数 值，显见叩【。，2 】。自适应线性变异可以加快差分进化算法的收敛速度，但仍 删出卅，羞蓦二篡r其an它du。帑xbj-x#xbj(t)+ra ， 。 【甩办( 菇一嘞) ， 其它 “ 其中i 是个体编号，j 是对应的第j 个元素，u ，分别是第，个元素的上界 和下界，( f ) 是第f 代种群中最好的个体，r a n d f ，r a n d ，是 0 ，1 之间的随机小数。 表2 1d e 和m d e 效率和误差比较 t a b l e 2 1t h ec o m p a r i n go f e f f i c i e n c ya n de r r o rr a t i ob e t w e e nd ea n dm d e 算法 试函t 董事( 蜥)量怃位谩差 d em d ed em d e r u t r i i i n9 51 0 o l 1 5 r o _ m b r o c k9 8o 0 3 8 2 5 s c h 珏h9 51 0 0仉0 2 4 6 7 g r h n k1 0 0l o oo 0 第1 0 页共4 4 页 h n u纠陪 l叫i o 矗 h h 嗽 一 ， 一 、 = 7 2差分进化算法 l d el 弧 1 啦l ”蛰 、 、 、l 进化代披 图2 4m d e 、d e 对r o s e n b r o c k 函数的仿真结果 f i 口4t h es i m u l a t i o nr e s u l to f r o s e n b r o c kf u n c t i o nb e t w e e nm d e a n dd e 相关测试函数如下： 测试函数1 ( r a s t r i g i n ) ： 石( 工) = 1 0 n + 孵- 1 0 c o s ( 2 n x j ) ， e 【1 0 0 ，1 0 0 ， = 5 测试函数2 ( r o s e n b r o c k ) ： 正( 工) = 1 0 0 ( x j 。一巧) 2 + ( 一- i ) 2 】， 工，【一5 0 0 ，5 0 0 ，疗= 1 0 测试函数3 ( s c h a f f e r ) ： 删= o s + 黯藤嚣， 而，而卜1 0 0 ，1 0 0 】 测试函数4 ( g r i e w a n k ) ： 驰h + 善n 意2 一珥n s z ，“- 2 0 0 ，2 0 0 ，n = 1 5 以上各函数最优点都在原点，最小值都为0 。 第1 i 页共“页 2差分进化算法 动态改变权重因子和交叉率的混沌差异演化算法( c d d e ) 在该算法中作者引入了进化速度因子和聚集度因子。变异因子被表示为聚集 度因子的函数，交叉概率被表示为进化速度因子的函数。在每次迭代时利用聚集 度因子动态改变变异因子，利用进化速度因子动态改变交叉率，从而使算法具有 动态自适应性。通过引入“混度变异”算子，利用混沌的随机性和遍历性使算法 具有较强的跳出局部最优值的能力。 1 ) 聚集度因子 用聚集度因子来表示种群中个体的差异程度。每代种群中个体的聚集度用下 式表示： f 三姜堕一 ， m a x ( ( f ( g ) ，( g ) 。) ，( ( g ) 。厂( g ) ) ) 用c 来表示种群聚集度因子，c 【o ，1 】，它反映种群当前的聚集程度，同时 在一定程度上也反映了种群中个体的多样性。c 值越大，聚集程度越高，个体差 异性越小。，( g ) 。表示第g 代种群中最佳个体的适应度，( g ) 表示第g 代种群 的平均适应度，( g ) ，为第i 个个体的适应度。 2 ) 进化速度因子 进化速度因子a 用下式表示： 口：堕二三k 二堕二监! ! 型 ( 1 3 ) f ( g 一2 ) 一( g ) h + c o n s t 厂( g 一1 ) 和厂( g 一2 ) 蛔为第g 一1 和第g - 2 代个体的最优适应度。c o n s t 为小 的常数，使分子、分母恒不为0 a 1 ，该参数反映了种群的进化速度，a 值越 小，进化速度越快，当经过一定代数之后，口值保持为1 ，则断定算法停滞或者 找到了最优解。 3 ) 混沌变异因子 所谓混沌遍历，即系统由某个初始状态开始按照其自身的运动规律，在经过 足够长的时间后不重复地经历相空间中的所有状态。混沌遍历较之随机遍历性能 更优越，其原因就是混沌遍历的规律性及不重复性，而随机遍历则是无规则运动。 根据混沌理论，可以把基因突变看作是一个混沌动力学过程，因此可利用混沌机 制为d e 算法引入混沌变异操作。采用u l a m v o n n e u a m a n n 混沌映射1 来实现混沌 变异： 第1 2 页共4 4 页 2 差分进化算法 岛+ l = 1 2 露 ( 1 4 ) 在空间 一l ，1 间遍历。x v ( g ) 为个体f 第，个分量，设( g ) 的取值范围为 口，b a ， p , j ( g ) = 一l + 等 ( 1 5 ) p o ( g + 1 ) = 厂【岛( g ) 】 ( 1 6 ) 毛( g + 1 ) = q + 岛( g + 1 ) 宰生 ! l ( 1 7 ) 式中代表式( 1 4 ) 的混沌映射公式。 因此定义变异因子f = c + e ，交叉概率c r = 口c r , ，其中f j c f l c r , 为常数。 算法过程： 1 ) 初始化种群规模m ，变异因子f 。交叉率c 冠； 2 ) 利用标准d e 算法生成新种群： 3 ) 对新种群进行混沌变异操作，产生新种群工( g + 1 ) ； 4 ) 对种群x ( g + 1 ) 和x ( g + 1 ) ，根据标准d e 算法的选择算子进行选择操作； 5 ) 判断是否到达最大进化代数或进入收敛误差，如果达到最大进化代数 或进入收敛误差，执行6 ) ，否则迭代次数j j 1 1 ，执行2 ) ； 6 ) 输出最优值； ， 在文献”中，作者采用了基准测试函数r o s e n b r o c k ，r a s t r i g r i n 和g r i e w a n k 对c d d e 和d e 进行实验分析，相关实验结果如下： 表2 2 第2 0 0 0 步时的平均最优值 t a b l e 22a v e r a g eo p t i m u ma ts t e p2 0 0 0 表2 3 两种算法的失效次数比较 t a b l e 23f a i l u r et i m e so f d ea n dc d d e 第1 3 页共4 4 页 2 差分进化算法 以上分析t d e 算法的三种主要的改进方式，由于d e 算法效果明显，很多学者 都对该算法进行了改进，