（计算数学专业论文）混合差分进化算法及应用研究.pdf

摘要 差分进化算法是由s t o r n 和p r i c e 于1 9 9 5 年提出的一种新的智能优化算法。它是一种简单有 效的全局优化算法，并且具有较好的稳定性和较快的收敛速度。由于其原理简单，易于理解和实 现，以及受控参数少等优点，一经提出就得到了广泛的研究和应用。 本文首先介绍了最优化问题的模型，对其按不同的标准进行了分类，接着又阐述了最优化方 法的分类，并对各类方法进行了简要介绍。文章的重点是智能优化算法，因此，对几种智能优化 算法进行了概括性的描述。 差分进化算法虽然有很多优良的性能，但是作为一种新的正在发展的算法，其在很多方面还 不成熟。针对参数设置困难的问题，文章通过大量的实验详细分析了影响算法性能的三个参数， 并给出了选取规则。尽管差分进化算法获得了广泛的研究，相对于其它算法，其研究成果还较为 分散，因此，本文给出了各种变异策略，并分析了各策略的优劣，以及不同策略的适用范围，对 差分进化算法的应用有一定的指导作用。 为了进一步改善和提高差分进化算法的性能，提出了三种混合差分进化算法。一是利用复合 形算法较强的处理约束条件的能力，提出了用于求解非线性约束优化问题的差分进化算法，扩展 了差分进化算法的应用领域。二是将具有较强局部搜索能力的h o o k e 4 e e v e s 算法以退火策略加速 差分进化算法，构造了基丁退火加速的差分进化算法，提高了算法的收敛速度和精度。三是在算 法中引入适应度方筹米判断种群多样性，并利用混沌的特性，提出了基于混沌搜索的差分进化算 法，增强了算法的全局搜索能力。 最后，展开了对差分进化算法的应用研究。先给出了一种差分进化算法的改进变异策略，并 将其应用于神经网络的训练当中，仿真实验结果表明改进的差分进化算法在神经网络的训练及应 用中有很人的潜力。其次，提出了一种基于差分进化的聚类算法，并将其应用于数据挖掘当中， 从而进一步拓宽了差分进化算法的应用领域。 关键词：全局优化；差分进化算法；h o o k j e e v e s 算法；混沌；神经网络；聚类分析 l l a b s t r a c t d i f f e r e n t i a le v o l u t i o n ( d e ) a l g o r i t h mi sp r o p o s e db ys t o r ea n dp r i c ei n19 9 5a san o v e li n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m i na d d i t i o nt oi t sf a s tc o n v e r g e n c es p e e da n dg o o dr o b u s tp r o p e r t y , d ei s a s i m p l ea n de f f i c i e n tm e t h o df o rs o l v i n gt h eg l o b a lo p t i m i z a t i o np r o b l e m s i nv i e wo fi t sa d v a n t a g e s s u c ha ss i m p l ep r i n c i p l e , e 擞t ou n d e r s t a n da n di m p l e m e n t h a v i n go n l yaf e wc o n t r o lp a r a m e t e r sa n d 8 0o n ，o n c ei tw a gp r o p o s e d , i th a db e e na p p l i e da n dr e s e a r c h e di naw i d er a n g eo ff i e l d s i nt h i sp a p e r ，t h em o d e l so fo p t i m i z a t i o np r o b l e m sa r ef i r s ti n t r o d u c e da n dc l a s s i f e da c c o r d i n gt o t h ed i f f e r e n ts t a n d a r d s a n dt h e n ，t h eo p t i m i z a t i o nm e t h o d sa r el i s t e ds e p a r a t e l yi nd i f f e r e n c et os o l v e t h ep r o b l e m sa n dd e s c r i b e db r i e f l y t h ef o c u so fo u rp a p e ri so nt h ei n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ， 8 0s e v e r a lp o p u l a ri n t e l l i g e n to p t i m i z a t i o na l g o r i t h m sa r eg e n e r a l l yd e m o n s t r a t e d a l t h o u g hd eh a sl o t so fg o o dp r o p e r t i e s ，a san e wa n dd e v e l o p i n ga l g o r i t h m ，i ti ss t i l lf a rf r o m m a t u r ei nm a n ya s p e c t s t h ep e r f o r m a n c eo fd ei ss e n s i t i v et ot h ec o n t r o lp a r a m e t e r sw h i c ha r e d i f f i c u l tt oc h o o s e ，s u f f i c i e n te x p e r i m e n t sa r ed o n eo nt h r e ei m p o r t a n tp a r a m e t e r st h a ti n f l u e n c et h e a b i l i t i e so fd eg r e a t l y , a n ds o m er u l e sa b o u tt h e ma r ed e r i v e d a l t h o u g hd eh a sb e e nw i d e l ys t u d i e d , c o m p a r e dt oo t h e ra l g o r i t h m ，i t sa c h i e v e m e n t sa r es t i l ls c a t t e r e da n dl a c k e do fs y s t e m s ot h ep a p e r p r e s e n t s s e v e r a lm u t a t i o ns t r a t e g i e s ，a n a l y s e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ed i f f e r e n t s t r a t e g i e s ，a n dg i v e st h es u i t a b l ea p p l i e da r e a a l lo ft h e s ew i l lo f f e rag u i d a n c er o l ef o rt h eu s e ro fd e i no r d e rt or e f o r ma n di m p r o v et h ep e r f o r m a n c e so ft h ea l g o r i t h m ，t h r e ek i n d so fh y b r i d 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 mh a v eb e e np r o p o s e d f i r s t m a k i n gg o o du s eo ft h es u p e r i o r i t yo f s t r o n g l yd e a l i n g 、历t ht h ec o n s t r a i n tc o n d i t i o no ft h ec o m p l e xm e t h o d ah y b r i dd ew i t ht h ec o m p l e x m e t h o dh a sb e e np r o p o s e dt os o l v et h en o n l i n e a r l yc o n s t r a i n t e do p t i m i z a t i o np r o b l e m s ，w h i c ho p e n su p an e wr a n g eo fa p p l i c a t i o n sf o rd e s e c o n d ，ah y b r i dd eb a s e d0 na n n e a l i n gs p e e d u pi si n t r o d u c e dt o i m p r o v et h ec o n v e r g e n c es p e e da n dc o n v e r g e n c ea c c u r a c y n ea n n e a l i n gs p e e d u pd em a k e sg o o du s e o ft h ea d v a n t a g eo ft h eh o o k e - j e e v e sa l g o r i t h ms u c ha ss t r o n ga b i l i t yo fl o c a ls e a r c h i n g i nt h ee n d ，a c h a o sd ei sp r o p o s e d ，w h i c hc a nj u d g et h ed i v e r s i t yo ft h ep o p u l a t i o na c c o r d i n gt ot h ef i t n e s sv a r i a n c e ， a n dc a nu s et h ep r o p e r t i e so fc h a o s t h er e s u l t ss h o wt h a ti tc a l le n h a n c et h ea b i l i t yo fg l o b a ls e a r c h i n g t h ef i n a lp a r to ft h ep a p e rd i s c u s s e st h ea p p l i c a t i o no fd e an e wm u t a t i o no p e r a t o ri si n t r o d u c e d t ot h ed e ，a n dt h e ni th a sb e e na p p l i e di nb pn e u r a ln e t w o r kt r a i n i n g ，t h en u m e r i c a ls i m u l a t e dr e s u l t s d e m o n s t r a t et h a tt h em o d i f i e da l g o r i t h mh a st h eg r e a tp o t e n t i a li nt h et r a i n i n ga n da p p l i c a t i o no fb p n e u r a ln e t w o r k i na d d i t i o n ，ac l u s t e r i n ga l g o r i t h i nb a s e d0 nd eh a sb e e ng i v e na n da p p l i e dt ot h ed a t a m i n i n gp r o b l e m s ，t h u st h er a n g eo fa p p l i c a t i o no fd eh a sb e e nm o r ew i d e n k e yw o r d s ：g l o b a lo p t i m i z a t i o n ；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 o o k e - j e e v e sa l g o r i t h m ；c h a o s ； n e u r a ln e t w o r k ；c l u s t e ra n a l y s i s u i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 研究生签名： 幺u 雪影 帆7 年多月 关于论文使用授权的说明 芗日 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交 论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位 论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 诩暑 翩躲锄4 疙 i f 笑, 导师签名：恐衫新 v v j 蝴：而年；其弓日 帅：尹乡眵日 宁疆人学砸f 论爻 第章绪论 1 1 最优化问题模型及分类 第一章绪论弗一早珀v 匕 最优化问题的数学模型的一般形式为 m i n 厂( x ) s ；t g f ( x ) 0 ，f ，= 1 ，2 ，m ( 1 1 ) 乃( 工) = o e = l ，2 ， 其中，x = ( 1 ，而，砀) t r n 称为决策变量； 厂：r d _ r 称为目标函数： g f ：r d _ r ( f j r ) 和h j ：r d r ( _ ，e ) 称为约束函数； g f ( x ) 0 ( f i ) 称为不等式约束； h i ( x ) = 0 ( j e ) 称为等式约束； 令 s = x r ”l g r x ) o , i ，h i ( x ) = o ，j e ( 1 2 ) 称s 为问题的可行域，x s 称为可行点或可行解。 最优化问题根据其中的变量、约束、目标、问题性质、时间因素和函数的解析性质等不同情 况，可分成多种类型。 1 根据有无约束条件可分为： i 无约束优化 if 等式约束优化 l 约束优化 不等式约束优化 il 混合约束优化 在约束优化问题中，根据约束条件函数的性质，又可分为1 f 线性约束优化问题和线性约束优化问 题。 2 根据函数的性质可分为： 线性规划( l p ：l i n e a rp r o g r a m m i n g ) ：目标函数和约束函数都是线性函数。 非线性规划( n p ：n o n l i n e a rp r o g r a m m i n g ) ：目标函数和约束函数至少有一个非线性。 3 凸规划：目标函数是凸函数，可行域是凸集。 4 二次规划( q p ：) ：目标函数是二次函数，约束条件是线性函数。 5 整数规划( i p ：i n t e g e rp r o g r a m m i n g ) ：决策变量必须取整数值。 6 混合整数规划：决策变量有部分取整数。 7 动态规划( d y n a m i cp r o g r a m m i n g ) ：解决多阶段决策过释的优化问题。 8 几何规划：目标函数具有多项式形式。 宁硬人，硕l 。论之 筇一节绢论 1 2 最优化方法分类及简介 不同类型的最优化问题可以有不同的最优化方法，既使同一类裂的问题也可有多种最优化方 法，某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直 接法、数值计算法和其他方法。 1 解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法 是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导 数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。 2 直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。 此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得 到所需结果。对于一维搜索( 单变量极值问题) ，主要用消去法或多项式插值法；对于多维搜索问 题( 多变量极值问题) 主要应用爬山法。 3 数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计 算相结合的方法。 4 其他方法：如网络最优化方法等。 优化方法也可以从别的角度进行分类，如：按照得到最优解的性质，可分为局部优化算法和 全局优化算法；按照是否有随机性可分为确定性优化算法和不确定性优化算法( 或随机性优化算 法) ；按照历史发展历程及优化机制可分为传统优化算法和现代优化算法( 或智能优化算法) 等 等。 针对不同的问题可以有各种不同的方法。例如：求解线性规划问题的单纯形法；求解无约束 优化问题的方法有：0 6 1 8 法，逐次插值逼近法，最速下降法，共轭梯度法，牛顿法，拟牛顿法 ( 变尺度法) 等；求解线性约束优化问题的有：可行方向法，有效集法，内点法等等；求解非线 性约束优化问题的罚函数法等。问题不同则求解的难易也会有所不同，一般来说非凸，带有非线 性约束以及函数不可微的全局优化问题较难求解。目前，传统的优化方法人多是基于梯度的局部 优化算法，不能得到全局最优解，并且对函数的要求过于严格，因此，通用性较著，应用范围有 限。 相比之下，2 0 世纪8 0 年代以来兴起的智能优化算法却有很多优良的性质，其原理和特点将 在下一节给出简要说明。 1 3 智能优化算法综述 随着科学和计算机技术的飞速发展，智能计算方法的应刚领域也越来越j “泛，本节简要介绍 了当前存在的一些智能计算方法，阐述了其基本r 作原理和特点，同时对智能计算方法的发展进 行了展望。 1 什么是智能算法 智能计算也叫软计算，是受自然规律( 生物进化和自然选择) 的启迪，根据其原理进行模仿， 求解问题的算法。从自然界得到启迪，模仿其结构进行发明创造，这就是仿生学。这是我们向白 2 j 。理、学耐ii 仑上第一誓绪沦 1i|imam - - 然界学习的一个方面。另一方面，我们还可以利刚仿生原理进行设计( 包括算法设计) ，这就是智 能计算的思想。智能计算从兴起至今已有很多算法，具有影响力的智能算法有，人上神经网络、遗 传算法、模拟退火算法、禁忌搜索算法、蚁群算法、粒子群算法以及差分进化算法等。 2 人工神经网络 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，简称a n n ) 是在对人脑组织结构和运行机制的认识 理解基础之上模拟其结构和智能行为的一种非线性动力学系统。早在2 0 世纪4 0 年代初期，心理 学家m c c u l l o c h 和数学家p i t t s 合作提出了人工神经网络的第一个数学模型，他们利用逻辑的数学 工具研究客观世界的事件在形式神经网络中的表达，从此开创了神经科学理论的研究时代。其后， r o s e n b l a t t 、w i d r o w 和h o p f i e l d 等学者义先后提出了各种不同的模型，使得人t 神经网络技术得 以蓬勃发展。 神经系统的基本构造是神经元，它是处理人体内各部分之间相互信息传递的基本单元。每个 神经元都由一个细胞体，一个连接其他神经元的轴突和一些向外伸出的较短分支树突组成。 轴突的功能是将本神经元的输出信号( 兴奋) 传递给别的神经元。其末端的许多神经末梢使得兴奋 可以同时传送给多个神经元。树突的功能是接受来自其它神经元的兴奋。神经元细胞体将接受到 的所有信号进行简单处理后，由轴突输出。 上述神经系统的基本原理是构成人工神经网络模型的基本依据。人工神经网络由于其大规模 并行处理，容错性，自组织和自适应等特点，已成为解决很多t 程复杂问题的有力工具。 3 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ) 是由h o l l a n d 教授于19 6 9 年提出的，后经d ej o n g 和g o l d b e r g 等归纳总结所形成的一种智能计算方法。它基于生物进化理论的原理发展起来的一种广为应用 的、高效的随机搜索优化方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索 不依赖于梯度信息。遗传算法是模拟自然生物的进化过程与机制而发展起来的一种自组织、自适 应算法。 迄今为止，遗传算法是进化算法中最广为人知的算法。遗传算法在复杂优化问题求解和工业 t 程领域应用方面，例如：作业调度与排序、可靠性设计、车辆路径选择与调度、设备布置与分 配、交通问题等等，取得了显著的成果，所以引起了越米越多的关注。 4 模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n g ，简称s a ) 是一种基于迭代的随机寻优算法，其基本思想 来源于同体退火过程与一般优化问题之间的相似性。物理咧体退火中，将州体加温至充分高，再 让其徐徐冷却，加温时，同体内部粒子随温升变为无序状，内能增人，而徐徐冷却时粒子渐趋有 序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。如果把退火过程中，粒 子的状态和优化中的解相对应，目标函数和能量对应，那么最优解就是能量最低的状态。 模拟退火算法由于采j f j 了具有概率突跳特性的m e t r o p o l i s 抽样策略，在解空间进行随机搜索 中，伴随温度的不断f 降重复抽样，最终得剑问题的全局最优解。 5 禁忌搜索算法 禁忌搜索算法( t a b us e a r c h ) 是由g l o v e r 于1 9 8 6 年提出的，它是对局部领域搜索的一种扩展， 是一种全局逐步寻优算法，是对人类智力过程的一种模拟。其基本思想是：给定一个初始解和一 3 j 岖j ：浮_ r i ! j ! 卜沦支旃一章绪论 皇! 曼曼曼曼曼曼皂曼曼曼舅曼曼曼璺舅舅皇! ! ! ! 曼曼曼曼曼曼曼! 曼曼曼曼皇舅曼曼! ! 曼曼曼寰曼! ! ! ! 曼m 。| = m l -m l i i ! 种领域，然后在当前解的领域中确定若干侯选解；若最优候选解优于当前最优解，则忽视其禁忌 特性，用其代替当前最优解，并将其相应的对象加入禁总表，同时修改禁忌表中各对象的任期； 若不存在上述侯选解，则选择在侯选解中选择谁禁忌的最佳状态为新的当前解，而无视它与当前 解的优劣，同时更新禁忌表；如此反复直到满足停l ：准则。 禁忌搜索是人工智能的一种表现，它最重要的思想是标记对应已搜索到的局部最优解的一些 对象，并在进一步迭代过程中尽量避免这些对象的重复，从而保证对不同的有效搜索途径的探索。 禁忌搜索算法在组合优化、机器学习、电路设计等领域取得了很人成功。 6 蚁群优化算法 蚁群优化算法( a n t c o l o n y o p t i m i z a t i o n ，简称a c o ) 是一种受自然界生物行为启发而产生的 “自然”算法，受蚂蚁觅食时通信机制的启发而产生。它用r 解决各种不同组合优化问题。 7 粒子群优化算法 粒子群优化算法( p a r t i l c es w a r mo p t i m i z a t i o n ，简称p s o ) 是一种进化计算技术，由e b e r h a r t 博士和k e n n e d y 博+ 发明，它源于对鸟群捕食的行为研究。在p s o 模璎中，优化问题的每个解对 应搜索空间中的一个鸟，称为粒子。每个粒子还有一个速度决定它飞翔的方向和距离。p s o 初始 化为一群随机粒子，然后，粒子开始追随当前的最优粒子运动，直到在整个解空间中搜索找到最 优解为止。在每次迭代中，粒子通过追踪两个极值来更新自己。一个是粒子自己找到的最优解， 称为个体极值；另一个是整个粒子群目前找到的最优解，称为全局极值。 此外，还有本文涉及剑的差分进化算法，其详细介绍将在后序章节给出。 目前的智能计算研究水平暂时还很难使“智能机器”真止具备人类的常识，但智能计算将在 2 l 世纪蓬勃发展，不仅仅只是功能模仿要持有信息机理一致的观点，印人t 脑与生物脑将不只是 功能模仿，而是具有相同的特性。这两者的结合将开辟一个全新的领域，开辟很多新的研究方向。 智能计算将探索智能的新概念，新理论，新方法和新技术，而这一切将在以后的发展中取得重大 成就。 1 4 课题的国内外研究现状 s t o r e 和p r i c e 于1 9 9 5 年提出了差分进化算法( d i f f e r e n t i a le v o l u t i o n ，简称d e ) i t ) ，并进行 了广泛的研究1 2 - 4 1 。它在1 9 9 6 年首届i e e e 进化算法人赛中表现突出，被证明为最快的进化算法 f 5 】。而且d e 算法在收敛速度和稳定性方面都超过了其它几种知名的随机算法【6 1 ，如退火单纯形 算法，白适应模拟退火算法，进化策略和随机微分方程法等，而且对于大多数数值b e n c h m a r k 问 题，d e 算法优于粒子群优化算法( p s 0 算法) 1 7 1 。 虽然著分进化算法有很多优点，但是它也存在一些无法克服的缺陷，例如：参数选取凼难， 后期收敛慢，有时陷入局部最优解等，针对这些不足国内外学者作了大量的研究：i ：作，现概括如 下： 针对参数选取困难问题，s t o r e 和p r i c e t 3 6 j 给出了一些经验规则，然而这些规则只是根据经验 而来的朱经过理论分析。l i u 等1 8 i 利j i 模糊逻辑控制器来调整缩放冈子和交义冈子，提出了模糊 臼适应差分进化算法。l e e 等1 9 1 提出了一种基于适应性步长局部搜索来确定缩放因子的策略，缩 4 j 。夏，、+ ；j “负i 。沦殳贫l 币! f i 瓮 小了参数选取的难度，加速了算法搜索的进程。谢晓锋等l 1 0 1 将缩放因子由固定数值转化为随机函 数，放宽了交叉因子的取值范围，数值实验表明该策略具有较大的优势。c h i o u 等 tj l 提出了一种 可变缩放因子，有效克服了固定或者随机因子的缺陷，提高了算法的性能。a l i 等1 1 2 1 在d e 中引 入自适应缩放比例因子，它能在算法早期增强全局搜索能力，后期具有较强的局部开发能力。文 献【1 3 】研究了多种具有自适应算子的差分进化算法，并进行了比较，结果表明改进算法能有效避 免早熟，显著提高算法的全局搜索能力。 许多学者从改变差分进化算法的操作算子入手来提高其性能。s t o m 和p r i c e t 卜叫根据变异和交 叉操作的不同提出了十种差分进化算法策略。f a n 等【1 4 1 在d e 中引入三角形变异策略，沿着三角 形的三条边分别以不同的步长搜索，来产生变异个体，增强了算法跳出局部极小点的概率。 f e o k t i s t o v 等0 5 1 提出了一种广义的变异策略框架，为开发新的变异策略提供了便利。l i u t l 6 1 等提出 了一类协进化差分进化算法。w a n g 等f 1 7 1 为加快d e 算法的收敛速度引入了加速算子，同时为了 提高种群多样性，当种群的分散度小于一定阈值时进行迁徙操作，从而保持了种群的多样性。 c h e n g 等【1 8 1 在d e 中加入了搜索空间扩展机制，有效增强了算法的全局收敛能力。文献 1 9 2 0 通 过对种群的控制来达到调节多样性，进而提高算法的效率。文献【2 l 】提出一种动态随机选择策略， 并将其应刚到约束优化问题的求解当中。p l a g i a n a k o s 等1 2 2 1 和t a s o u l i s 渊分别提出了并行d e 算 法，在提高计算能力的同时也加大了算法的计算量。 为了构造出更加有效的算法，人们展开了差分进化算法的混合算法研究。单纯形法搜索能力 较强，无需梯度信息，易于实现，冈此，方强等 z 4 1 在d e 中加入单纯形寻优操作和重布操作，提 高了单纯形方法的收敛速度，同时提高了d e 算法的收敛精度。h r s t k a 等将遗传算法的部分染 色体通过d e 的变异操作产生，同时利用二进制竞争选择策略选择子代。张吴等【2 6 1 提出将粒子滤 波和d e 算法结合，大大改善了差分进化算法的性能。b e c e r r a 等 2 7 1 将文化算法引入到d e 算法 中，并用于求解约束优化问题，但是容易出现早熟收敛。除此之外，差分进化算法还有和其它算 法的混合策略【弘川。 算法的有效性必须在应用中才能体现，因此，差分进化算法的应用一直是人们研究的热点。 差分进化算法主要是用丁连续无约求的确定性优化问题，为了拓展其应用范围，许多学者做了努 力。l a m p i n e n 等1 3 2 - 3 3 1 先利用静态罚函数方法转化为无约束问题，其后通过增人使不可行解朝约束 违背少的方向的选择压力来提高算法向可行域收敛的速度。s a r i m v e i s 等1 3 4 提出了一种利用增广 拉格朗日方法处理约束的排列d e 算法，并根据算法的进科调节罚冈子和拉格朗日乘子。c h i o u 等 【3 5 1 将问题转化为最大最小( m i n m a x ) 问题。o n w u b o l u 等m 1 利刚前向转化机制将整数变量转化为 便t - d e 处理的连续变量，利用后向转化机制将连续变量转化为可以进行目标评价的整数量，从 而将d e 算法用丁处理离散问题。宋立明等【1 9 1 将d e 算法用于优化叶轮机械三维气动优化设计： a y d i n 等1 3 7 1 将d e 与模糊推理相结合，用丁解决机器人最优路径规划问题；k a p a d i 等m 1 利用d e 解决间歇发酵最优控制和参数选取问题；q i a n 等【3 9 1 利用多目标问题的特点，提出了一种自适应 调肯变异因子的筹分进化算法，并将其应用于多目标优化当中，取得了较好的结果。 此外，差分进化算法还被应刚剑噪声1 4 0 1 ，电力系统j ，自动聚类【4 2 1 ，信号处理h 3 1 ，带有限 缓冲的流水车间调度问题1 , , 4 1 ，网络训练5 1 等复杂环境中。 5 宁夏人。? 顺l ：论文 第一节绪论 1 5 本文的主要研究内容 本文在详细介绍差分进化算法的基本原理的基础上，首先展开了对算法本身问题的研究。差 分进化算法存在参数选取难以确定以及研究成果相对分散等问题。一方面，针对参数选取问题， 文章通过几个典型的b e n c h m a r k 优化问题，对影响算法性能的三个重要参数，展开了数值实验， 分析了实验结果，并给出了参数选取规则。另一方面，详细介绍了差分进化算法的十种繁殖策略， 并对这十种策略的性能进行了仿真实验，给出了在高维，低维以及单峰，多峰等不同条件下各个 繁殖策略的优劣以及适用范围等结论。 其次，根据差分进化算法的不足，将其它优化策略嵌入到差分进化算法中，构造了三种混合 差分进化算法。一是提出了融合复合形算法的复合形差分进化算法，该算法利片j 可行点的形心来 修复变异后的不可行个体，并对各个个体进行了复合形加速，提高了算法的收敛速度，并将其用 于求解非线性约束优化问题，进一步扩展了差分进化算法的应用领域。二是将h o o k e j e e v e s 算法 融入到差分进化算法当中，取长补短，混合算法在利用h o o k e - j e e v e s 算法较强的局部搜索能力的 同时，又保持了基本差分进化算法全局收敛的性能。同时，为了加快收敛速度，给出了退火加速 策略，进一步提高了算法的性能。三是提出了一种基于混沌搜索的差分进化算法。该算法根据适 应度方差来判断早熟，并利用混沌的特性米提高群体多样性和全局收敛能力，实验表明该算法较 基本差分进化算法能以较大的概率跳出局部最优点而达到全局最优。 鉴于差分进化算法的优良性能，第四章展开了对差分进化算法的应用研究，主要是对神经网 络的权值的训练和数据挖掘中的聚类分析进行研究。 最后，总结了本文的研究内容，并对差分进化算法的以后工作进行了展望。 6 。夏人。坝卜学f 童沦上第：章艺分进化，曾；上 第二章差分进化算法 本章首先详细介绍了差分进化算法的基本原理。其次，通过实验分析了差分进化算法参数的 选取问题。最后，给出并比较了差分进化算法的十种繁殖策略。 2 1 差分进化算法原理 差分进化算法是种简单有效的全局优化算法。它是演化算法产生以来在算法方面取得的巨 大进展，由于其容易理解、易于实现，受控参数少，且对目标函数要求较少等优点，所以一经提 出就倍受关注并得到了广泛的应用。 差分进化算法与遗传算法一样都存在变异、交叉和选择操作，但是它又不同于遗传算法【4 6 1 。 主要区别为： l 、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2 、在遗传算法中通过两个父代个体的交叉产生两个子个体，而在差分进化算法中通过第两 个或几个个体的差分欠量做扰动来产生新个体。 3 、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的 个体只有当它比种群中的个体优良时才替换种群中的个体。 差分进化算法是在求解有关切比雪大多项式的问题时提出来的，是基于群体差异的进化计算 方法l i 】。其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代 个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应 度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 设当前进化代数为t ，群体规模为n p ，空间维数为d ，当前种群为x ( r ) = ，毛t ，x 0 ， 写= ( ，艺) 为种群中的第i 个个体。在进化过程中，对于每个个体依次进行下面三种操 作。 2 1 1 变异操作 对于每个个体按下式产生变异个体一= ( 嵋，吃，v ：! d ) ，则 吒= j + f ( 一，) j = l ，2 ，d ( 2 1 ) 其中= ( 。，。) ，= ( 。，：，。) 7 和= ( ，：，。) 7 是群体中随机选择的三 个个体，并且吃弓f ；，和分别为个体，；，吒和的第维分j 望r - 1 ；f 为变异因子， 一般取值- t - o ，2 卜这样就得剑了变异个体 ，；。其原理示意图( - - 维时) 如f ： 7 j ：夏人。学坝卜二位沦殳第一：亭芏分j ! 化铮法 ! i i i i i i ii i _ i i ；i 曼曼曼曼曼曼曼! 曼曼曼皇曼曼! 曼! 鼍曼舅 图2 id e 的变异操作示意图 2 1 2 交叉操作 根据以下原理由变异个体，；和父代个体得到试验个体可= ( 吒，畦，心) 7 ，则 ， j 呓矿r a n d o ，1 】c r o r j = ，一r a n d 2 1 毛矿r a n d o ，】 c rd r a n d o 1 c r a n d j 一r a n d ( 2 2 ) 9 l 毛矿 ，】 一 ( 2 2 ) j = l ，2 ，d 其中，r a n d o ，l 】是【o ，l 】间的随机数；c r 是范围在【o ，1 】间的常数，称为交叉因子，c 尺值越大，发 生交叉的可能性就越人；一r a n d 是在【l ，d 】随机选择的一整数，它保证了对于试验个体珥至少要 从变异个体，；中获得一个元素。以下是d = 7 时的交叉操作示意图： 8 j ：夏人学倾 ，f ? i 沦文 第：幸差分进化算法 x 、v、u、 图2 2d e 算法的交叉操作示意图( 其中d = 7 ) 以上变异操作和交叉操作统称为繁殖操作。 2 1 3 选择操作 差分进化算法采用的是“贪婪”选择策略，即从父代个体和试验个体嘭中选择一个适应度 值最好的作为下一代的个体“，选择操作为： g ”：p i ff i t n e s s ( x ；) f i t n e s s ( u ；) 。 ( 2 3 ) l 彬o t h e r w i s e 其中，f i t n e s s ( ) 为适应度函数，一般以所要优化的目标函数为适应度函数。本文的适应度函数如 无特殊说明均为目标函数且为求函数极小值。 2 1 4 差分进化算法的流程 综上，我们得到著分进化算法的流程如下： ( 1 ) 初始化参数：种群规模n p ；缩放因子，；变异冈子c r ；空间维数d ；进化代数t = 0 。 ( 2 ) 随机初始化初始种群x ( f ) = 畸，t ) ，其中= ( 。，：，d ) 7 。 ( 3 ) 个体评价：计算每个个体的适应度值。 ( 4 ) 变异操作：按( 2 1 ) 式对每个个体进行变异操作，并得剑变异个体 ，：。 ( 5 ) 交义操作：按( 2 2 ) 式对每个个体进行交义操作，得剑试验个体珥。 ( 6 ) 选择操作：按( 2 3 ) 式从父代个体和试验个体；中选择一个作为下代个体。 ( 7 ) 终止检验：如果达到最火进化代数或满足误差要求，则停j ：进化并输出结果；否则转( 3 ) 。 按( 2 1 ) 和( 2 2 ) 式进行的繁殖操作可以州d e r a n d 1 b i n 表示，其含义和其它策略将在后 面有所介绍。为了形象的了解著分进化算法的性能，我们采用m a t l a b 语言编制仿真程序，在5 1 2 9 1 户 2 3 5 6 7 1 尸 2 3 i 5 6 7 ：堇奋茎垒i ：茎堡耋耋薹二霍誊0 鲨兰茎薹 内存的p c l l t i u m d8 2 0 计算机上( 如无特殊说明，本文设计的编程均为此环境) t 对坤函数( 参 看附件) 进行优化。其优化的过程图如图2 3 和圈2 4 。 p e a k s 函数的等鬲缱田厦个体丹布情况p e a k s 静三摊腰霉 国2 , 4 对p 龃k s 目数的优化最终结皋目 从上述两幅图中，我们可阻看到群体中的并个个体在两数等高线上的分布情况，由数的性质， 摄优个体韵进化轨迹以及个体在二维空间的分布情况。从蚓中可以看出，p e a l c 8 函数是一个多 峰函数，但却只存在唯一全局极小点。开始时，个体随机分布在等高线值较高的地方，随着进化 宁疆二。# 顺l 学f _ 论上第：市芦分j 且化钎i 上 过程的进行，所有个体重合为一个个体，算法最终收敛于全局最优点。 2 2 差分进化算法参数研究 本：铃对影响d e 算法性能的三个主要参数种群规模n p ，缩放冈子，和交义因子c r 进行了系 统的实验，分析了各个参数对算法性能的影响及其最优选取问题，并给出了一些有益的结论，对 运用差分进化算法时的参数选取有很好的参考价值。 2 2 1 引言 d e 算法虽然是一种有效的全局寻优算法，但是其算法本身仍有很多值得研究的地方，例如： 参数的设置问题。d e 算法的主要控制参数是种群规模( 腰 ) ，缩放因子( 刃和交叉因子( c r ) 。算法 的性能很人程度上和参数的选取有关。然而对d e 算法参数分析的专门性文章却很少，例如：文 献【3 ，6 】只是对参数的选取作了简单的推荐，文献 1 0 , 4 7 针对，和c r 的综合作用进行了简单的说 明而未深入分析其机理且忽略了种群规模的作用。鉴于此，本节对影响算法性能的三个主要参数 展开了一系列的实验研究，并给出了一些合理的选取规则。 实验发现( 如表2 2 ) ，d e 算法的优化能力和收敛速度与这些参数的选择紧密相关，因此有必要 对影响算法性能的参数进行系统的分析。本节使用6 个典型的b e n c h m a r k 函数作为实例，首先对 群体规模n p 进行分析，接着对缩放因子f 和交义因子c r 的选取对优化效果的影响进行详细的实 验和分析。 实验中要测试的函数如表2 1 。 表2 1 各个函数特征及参数设置 注：其详细说明参见附录。 为了说明三个参数对算法性能的影响，对函数和正在其中两个参数相同改变另一个参数的 情况下比较得到的最优值，结果如表2 2 所示。 ：夏人学坝f 学f 乏论史第二亭艺分边化铮法 j 表2 2 不同参数设置下函数的优化结果 测试算法采用d e r a n d 1 b i n 版本，终止条件有两个原则：l 、给定最人进化代数。 ( g e n _ m a x 为1 0 0 0 代) ，比较算法得到的最优值( v a l u e ) ；2 、给定精度下( 如表1 ) 比较函数的评价次数( n f e ) 和 成功率( r a t e ( ) ) 。在测试当中，固定3 个参数中的两个，变化另外一个。各个函数连续随机运行 3 0 次，然后取其均值。 2 2 2 种群规模n p 的选择 从计算复杂度分析，种群规模越大，搜索到全局最优解的可能性就越大，然而所需的计算量 和计算时间也要增加。从表2 2 可以看到，最优解的质量并谁随种群规模的增大一味的变好。有 时种群规模的增大，反而会使最优解的精度降低，因此，合理选取种群规模对算法的搜