（计算机软件与理论专业论文）差分演化算法及其在函数优化中的应用研究.pdf

中文摘要 差分演化算法，自1 9 9 5 年被提出以来，受到了相关领域中专家学 者们的重视和青睐，并且已经在多峰函数优化、数据过滤、神经网络 学习、多目标优化等十九个大方向上得到了较好的仿真结果。 本文主要对差分演化算法在函数优化中的应用展开研究。在第二 章中用不大的篇幅阐述了差分演化算法较有影响力的三个版本，然后 在接下来的第三章和第四章中提出了四个算法，证明了两个结论，概 要如下： 1 、提出了一个改进的差分演化算法，该算法记录下了差分演化算 法在对每个个体进行变异操作时的差向量，然后以被变异的个体作为 邻域的中心，以该差向量作为邻域的半径，在该邻域内再进行一次挖 掘式的搜索。这一改进增强了原差分演化算法的局部搜索能力； 2 、设计了一个模拟退火算法与差分演化算法的混合算法，实验结 果表明混合后的算法比单一的差分演化算法更稳健，收敛速度也略有 提高； 3 、提出了一个基于小生境技术的混合差分演化模拟退火算法，实 验结果表明小生境技术极大地增强了算法保持解群多样性的能力； 4 、提出了种基于巴斯卡分布的算法框架，并从理论上证明了该 算法框架能够提高原低效算法的寻优效率； 5 、设计了一个求解约束最优化问题的方案，该方案以一种折衷的 差分演化算法为基础。实验结果表明，与同类方法相比而言，该方案 在收敛速度和稳定性两方面表现出较强的竞争力； 6 、s k o z i e l 和z m i c h a l e w i c z ( 1 9 9 9 年) 提出了一个处理约束的映 射，本文从理论上证明了当这个映射与遗传算法相结合时，该映射 是同构映射，而在差分演化算法的变异操作下，该映射不是同态映 射，更不是同构映射。进而表明，该映射更适宜于与遗传算法相结 合，而并不太适宜于与差分演化算法( 及其类似的算法) 相结合。 关键词：差分演化算法，函数优化，小生境，巴斯卡分布，同构 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 na l g o r i t h mw a si n t r o d u c e db yr s t o r na n d k p r i c ei n1 9 9 5 a n di th a sa l r e a d yb e e na p p l i e ds u c c e s s i v e l yt om a n y a r e a ss u c ha sm u l t i m o d a lf u n c t i o no p t i m i z a t i o n ，n e u r a ln e t w o r kl e a r n i n g ， d i g i t a lf i l t e rd e s i g 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 na n d s oo n i nt h i s p a p e r ，i tb r i n g s i n t of o c u so nd i f f e r e n t i a le v o l u t i o n s r e p r e s e n t a t i o ni n f u n c t i o no p t i m i z a t i o n f o u rn o v e ls c h e m e sb a s e do n d i f f e r e n t i a le v o l u t i o na r ep r o p o s e d a n dt w or e s u l t sa b o u to nd i f f e r e n t i a l e v o l u t i o na r et h e o r e t i c a l l yp r o v e d t h es u m m a r yi sf o l l o w i n g ： 1 a nm o d i f i e dd 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 d i nt h e p r o p o s e da l g o r i t h m ，t h ed i f f e r e n c ev e c t o rw h i c hi se m p l o y e di nm u t a t i n g e a c hi n d i v i d u a lb ys 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 mi sr e c o r d e d e a c hm u t a t e di n d i v i d u a li st a k e na st h ec e n t e ro fan e i g h b o r h 0 0 d ，t h e c o r r e s p o n d i n g d i f f e r e n c e v e c t o ra sr a d i u s t h e ns e a r c hi nt h e n e i g h b o r h o o da g a i n t h e m o d i f i c a t i o ni n c r e a s e st h el o c a l s e a r c h i n g a b i l i t yo 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 2 h 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 mb a s e do ns i m u l a t e d a n n e a l i n gi sd e s i g n e d a n d t e s t e d b y s e v e r a ln o n l i n e a rf u n c t i o n o p t i m i z a t i o np r o b l e m s t h er e s u l t si n d i c a t e dt h ep r o p o s e da l g o r i t h mc a n i m p r o v et h ee f f i c i e n c yo 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 ma n dm u c hm o r e r o b u s tt h a ns i m p l yd i f f e r e n t i a le v o l u t i o n 3 c o u p l i n gd i f f e r e n t i a le v o l u t i o na n ds i m u l a t e da n n e a l i n g a l g o r i t h m b a s e do nn i c h ei sp r o p o s e d t h er e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h m c a nf i n da l lg l o b a lo p t i m u mp o i n t sq u i c k l yw i t h o u ts t r i c tr e q u e s tf o r p a r a m e t e r s n i c h ec a ni m p r o v ea n dp r e s e r v et h ep o p u l a t i o nd i v e r s i t y 4 an c ws c h e m eb a s e do np a s c a ld i s t r i b u t i o ni sp r o p o s e d a n di ti s p r o v e dt h e o r e t i c a l l yt h a tt h ep r o p o s e ds c h e m ei s m u c hm o r ee f f e c t i v e t h a nt h ep r i m a r ya l g o r i t h m 5 an e wh e u r i s t i cs c h e m eb a s e do na ne c l e c t i cd 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 rc o n s t r a i n e do p t i m i z a t i o ni sp r o p o s e d a n di ti sa p p l i e dt oa s e to fw e l l k n o w nb e n c h m a r kf u n c t i o n s a n dt h er e s u l t sd e m o n s t r a t e dt h a t t h en e ws c h e m ec o n v e r g e sf a s t e ra n di sm o r er o b u s tt h a ns e v e r a lk i n d r e d m e t h o d st h a ta r er e p r e s e n t a t i v eo ft h es t a t e - o f - t h e - a r ti nt h ea r e a 6 ac o n s t r a i n e d h a n d l i n gm a p p i n gw a sp r e s e n t e db ys k o z i e la n d z m i c h a l e w i c zi n1 9 9 9 i ti s p r o v e dt h e o r e t i c a l l y t h a tt h e m a p p i n g c o m b i n e dw i t hg e n e t i ca l g o r i t h mi sa ni s o m o r p h i cm a p p i n g ，h o w e v e r ，i t i sn o tah o m o m o r p h i cm a p p i n gc o m b i n e dw i t hd i f f e r e n t i a le v o l u t i o n a n d t h e ni ti sa p p a r e n tt h a tt h em a p p i n gi ss u i t a b l ef o rb e i n gc o m b i n e dw i t h g e n e t i ca l g o r i t h m sb u tn o tf o rb e i n gc o m b i n e dw i t hd i f f e r e n t i a le v o l u t i o n ( o rt h ea l g o r i t h m sl i k ei t ) k e yw o r d s ：d i f f e r e n t i a le v o l u t i o n ，f u n c t i o no p t i m i z a t i o np r o b l e m s ，n i c h e ， p a s c a ld i s t r i b u t i o n ，i s o m o r p h i cm a p p i n g m 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意 研究生签名：孝雌日期兰业 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：鞠茸壅导师签 武汉理工大学硕士学位论文 1 1 前言 第1 章绪论 在科学和工程领域中，经常会遇到连续空间中的数值优化问题， 它们的目标函数通常是非线性甚至是不可微的，这时传统的优化方法 便很难获得成功。 近4 0 年的研究充分表明，模拟自然进化的搜索过程可产生非常 鲁棒的计算方法，即使这些模型只是自然界生物体演化过程的粗糙简 化。于是，演化算法( e v o l u t i o n a r y a l g o r i t h m ) 应运而生，并且引起了越 来越多的学者的重视。 在演化算法家族中，相对发展较早的有进化规划( e v o l u t i o n a r y p r o g r a m m i n g ) 、进化策略( e v o l u t i o n a r ys t r a t e g y ) 、遗传算法( g e n e t i c a l g o r i t h m s ) 等，它们都是基于这种思想而发展起来的问题求解方法。 这些算法在赋予演化算法自组织、自适应、自学习等特征的同时，不 受搜索空间限制性条件( 如是否可微、是否连续等) 的约束，也不需要 其他辅助信息( 如导数) ，不仅能获得较高的效率，而且具有易于操作 和通用的特点。 近些年来，演化算法发展迅速，又有一些新兴的演化算法涌现出 来，比如：微粒群算法( p a r t i c l es w a r mo 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 ) 、人口迁移算法( p o p u l a t i o nm i g r a t i o n a l g o r i t h m ) 等。其中，差分演化算法一一这种基于群体差异的演化算 法一一在首届i e e e 演化计算竞赛中表现突出。 1 2 国内外研究现状及对现状的思考 差分演化算法“。1 是在1 9 9 5 年r s t o r n 和k p r i c e 提出来的一种演 化算法。最初，主要目的是用差分演化算法来求解连续全局优化问题。 武汉理工大学硕士学位论文 其基本思想在于应用当前种群个体的差来重组得到中间种群，然后应 用直接的父子混合个体适应值竞争来获得新一代种群。 差分演化算法最新颖的特征是它的变异操作，当选定个个体后， 算法通过在该个体上加上两个个体的带权的差来完成变异。在算法迭 代的初期，因为种群中个体的差较大，从而这样的变异操作会使算法 本身具有较强的全局搜索能力，而到迭代的后期，当趋于收敛的时候， 种群中个体的差较小了，这也使得算法具有较强的局部搜索能力。这 种新颖的变异操作也使得该算法在求解函数优化等问题上有着其它同 类方法不可比拟的优点。主要优点可以总结为以下三点：( 1 ) 待定参 数少；( 2 ) 不易陷入局部最优；( 3 ) 收敛速度快。 经过十年的研究，差分演化算法得到了较大的发展。从算法设计 上看，一些改进的差分演化算法1 2 1 已经被成功的设计出来，这些改进 的算法一般是从算法的鲁棒性、算法的收敛速度、算法的局部搜索能 力、算法的全局搜索能力等几个方面或者某一个方面对基本的差分演 化算法进行改进；从应用上看，该算法已经在多峰函数优化( m 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 n ) 、数据滤波( d i g i t a lf i l t e rd e s i g n ) 、神经网络学 习( n e u r a ln e t w o r kl e a r n i n g ) 、 多目标优化( m u l t i 0 b j e c t i v e o p t i m i z a t i o n ) 等十九个大方向上得到了较好的仿真结果“3 。”。差分演化 算法也正在引起越来越多的学者的重视。 十年的时问，差分演化算法已经在十九个大的方向上得到了较好 的仿真结果，这足以见得差分演化算法在演化界所受到的重视程度。 但是在研究差分演化算法的学者中，大多数学者都专注于差分演化算 法在某方面的应用研究，而从事算法收敛性理论研究和基础应用性研 究的学者却很少。 在应用差分演化算法进行函数优化的实验中，发现在迭代收敛的 种群序列中，随着迭代次数的增加，种群的线性性也随之增强，即迭 代后期的种群围绕函数的最优解呈线性分布。可想而知：若迭代后期 的种群围绕函数的最优解呈多维正态分布( 以最优解作为正态分布的 期望) 将更有利于种群的搜索。 另外，数值试验又表明：对具有多个全局最优点的函数( 如s h u b e r t 函数，在 一1 0 ，1 0 上有7 6 0 个局部最小值点，其中有1 8 个全局最小值 2 武汉理工大学硕士学位论文 点) ，差分演化算法无法成功地一次性求出函数的所有最优值点。这表 明差分演化算法的搜索能力有待加强，或者是保持解群的多样性的能 力有待加强。再比如，差分演化算法在有约束优化领域的应用，最近 有相关文献给出了较好的结果，但同时也表现出稳健性不强、收敛速 度不够快等方面的不足。 上述对差分演化算法搜索性能的思考和通过数值试验看到的差分 演化算法的不足，说明差分演化算法的基础应用性研究还有待加强。 1 3 本文的研究内容 本文就是在上述背景下及我们所注意到的一些不足之处的基础上 开展的对差分演化算法的基础应用性研究。主要的研究内容包括三个 方面： 一是设计改进的差分演化算法。使得改进后的算法从根本上改变 收敛种群序列的后期种群的线性分布特征，从而达到提高算法搜索能 力的目的。根据这一想法，提出了两个改进方案：( 1 ) 记录下差分演 化算法在对每个个体进行变异操作时的差向量，然后以被变异的个体 作为邻域的中心，以该差向量作为邻域的半径，在该邻域内再进行一 次挖掘式的搜索；( 2 ) 设计一个模拟返火算法与差分演化算法的混合 算法。实验结果表明通过这两种改进后的新算法比单一的差分演化算 法更稳健，收敛速度也有所提高。 但是，改进后的算法是否有比原算法更强的搜索能力( 包括全局 搜索能力和局部搜索能力) 昵? 不得不指出，对一些常用多峰函数测 试集的实验不能回答这个问题。于是进行了下面第二个内容的研究。 二是应用小生境口”技术来保持种群的多样性，把小生境技术融入 到上面提出的算法中，设计了一个小生境混合差分演化模拟退火算法。 然后用上面提到的s h u b e r t 函数进行试验。多次试验的结果表明：模拟 退火算法与差分演化算法的结合增强了原差分演化算法的搜索能力。 进而，为了提高算法一次性找到类似于s h u b e r t 函数的多峰函数的所有 全局最优值点的效率，又在此基础上设计了一个算法框架：基于巴斯 卡分布的算法框架，并从理论上证明了该算法框架能够提高原低效算 3 武汉理工大学硕士学位论文 法的寻优效率； 三是应用差分演化算法来优化有约束函数。 在有约束函数优化中，首先要面对的问题是如何处理约束条件。 处理约束的方法也有很多，1 9 9 6 年z m c h a l e w i c z 等把这些方法分为四 类：基于保持可行解的方法、基于罚函数的方法、基于搜索可行解的 方法和杂交方法；而在此基础上，s k o z i e l 和z m c h a l e w i c z ( 1 9 9 9 年) 又提出了一个全新的映射来处理约束，本文简称该映射为删映射。于 是，在这些处理约束的方法中，哪一些或者哪一类方法比较适合于与 差分演化算法相结合又成了一个问题。并且，发现当g a 与k m 映射成 功结合的同时，d e 与1 0 4 映射的结合却不如d e 与其他简单的处理约束 的方法相结合口“川。循着这一思路，本文从理论上证明了当k m 映射 与遗传算法相结合时，该映射是同构映射，而在差分演化算法的变异 操作下，该映射不是同态映射，更不是同构映射。进而表明，该映射 更适宜于与遗传算法相结合，而并不太适宜于与差分演化算法( 及其类 似的算法) 相结合。进而，设计了一种折衷差分演化算法与简单的处理 约束的规则及周期模式“们相结合构造新的策略求解有约束优化问题。 1 4 本文的组织 本文后续章节组织如下：第二章介绍差分演化算法的家族中几个 较优秀的版本的基本框架。第三章介绍应用差分演化算法优化无约束 问题的研究成果，主要包括四部分，其一是改进的差分演化算法加快 收敛速度的研究成果，其二是构造混合差分演化模拟退火算法的相关 研究成果，其三是构造小生境混合差分演化算法优化具有多个全局最 优点的函数的研究成果，其四是提出基于巴斯卡分布的算法框架。第 四章介绍应用差分演化算法优化有约束问题的研究成果。第五章总结 全文，并提出了有关差分演化算法继续研究的一些想法。 4 武汉理工大学硕士学位论文 第2 章差分演化算法 差分演化算法( d i f f e r e n t i a le v o l u t i o n ，简称d e ) 是r a i n e rs t o r n 和k e n n e t hp r i c e “。1 在1 9 9 5 年为求解有关切比雪夫多项式的问题提出 来的，是一类基于群体差异的演化算法。其基本思想是应用当前种群 中个体的差来重组得到中间种群，然后通过父子之间的锦标赛制的竞 争获得新一代种群。d e 发展至今，已经有了很多不同的版本，最有影 响力的有三个口“”，本章将以其中个版本为例介绍d e 的基本操作， 鉴于该版本的特征，我们称之为折衷的差分演化算法( e c l e c t i c d i f f e r e n t i a le v o l u t i o n ，简称e d e ) ，再给出e d e 算法的基本流程和伪码， 最后再介绍另外两个版本的d e 与e d e 的不同之处。 2 1 折衷差分演化算法的基本操作 差分演化是一种基于实数编码的演化算法，算法的基本思想及整 体构架与遗传算法相类似，从一代种群到下一代种群都要经过变异、 交叉、选择等操作，也一样有几个至关重要的参数必须事先确定。下 面逐一介绍差分演化算法的几个关键性的操作。 2 1 1 参数的确定 差分演化算法主要涉及以下四个参数：种群规模大小，个 体( 也称变量) 的维数d ( 也称为染色体的长度) ，变异因子f ， 交叉概率c r 。有研究结果表明：群体规模一般介于5 d 到1 0 d 之间 ( 根据实际问题可以确定变量的维数d ) ，我们的实验结果也表明取 = 6 d 较好；变异因子f 一般在( o 2 ) 之问取值，一般我们取f 一0 5 ； 交叉概率c r 一般在【0 ，1 l 之间选择，一般来说，c r 越大，收敛速度越快， 但易于早熟，易于陷入局部最优，算法的稳健性越差，比较好的选择 是c r 0 3 。当然，这些都只是经验值，没有严密的理论证明，对于某 5 武汉理工大学硕士学位论文 些具体的问题也可能取其它的值会得到更好的结果，需要具体问题具 体分析。 2 1 2 初始化种群 先声明两个行d 列的矩阵，分别记为x i 、x 2 ，其中x 1 用来存 放当前种群，并且产生n x d 个满足约束条件且服从均匀分布的随机数 作为x 1 的初始值，具体操作如下： x 啦】【j 】一r a n d l ( h i g h j - l o w j ) + l o w j 】 其中i 1 1 2 ，一1 ，2 ，d ，r a n d l 是【0 ，1 1 上的服从均匀分布的随 机数，h i g h j 】和t o , 4 j 】分别是变量的第，维的上界和下界。 2 1 3 变异操作 与传统的遗传算法不同，差分演化的变异操作通过加上一个均值 为0 的随机向量到被变异的目标向量上来完成。如何产生一个均值为0 的随机向量呢? 该算法通过从种群x 1 中随机的选择两个向量( 这两个 向量都不等于目标向量) ，然后求这两个向量的差来得到均值为o 的随 机向量。当然，把这个差随机变量乘以某个变异因子f 后，其均值还 是0 。这里保持用来变异的随机向量的均值为0 ，可以从很大程度上减 小不可行解出现的概率。 如下所示，就是通过两个随机向量x 曲和x k 来变异目标向量z 1 4 成x k 的表达式： x l a 一x l a + ，( x l b x k ) ( 2 1 ) 2 1 4 杂交操作 要进行杂交运算，首先必须给目标向量选择交叉的对象，在这里， 本算法随机地从种群中选取一个不比目标向量的适应度低的向量作为 交叉对象。这样既能保持种群的多样性，又能兼顾收敛速度，是一种 折衷的选取方法。 一旦目标向量x l i 的交叉对象x l d 被选定，则作如下式所示的带权 6 武汉理工大学硕士学位论文 的加法： x l m 一( o 5 - f ) x i + ( o 5 + f ) j 埘 ( 2 2 ) 事实上，上式可以理解为按一定的权值取x u 和x 1 的信息，再把 所取的信息融合在一起得到新的个体x l m 。这就类似传统的遗传算法 中的交叉，所以这里也称之为交叉。 2 1 5 构造试验向量 试验向量是某个目标向量经过上述的变异和交叉而得到的一个新 的向量，把上述( 2 1 ) 式和( 2 2 ) 式有机的结合在一起得如下的( 2 3 ) 式： x 2 一( 0 5 - f ) x i + ( o 5 + f ) x h + f 僻协- x l c ) ( 2 3 ) 上式的前两项意义是应用x l d 作为交叉对象来与目标向量x i 交 换信息，第三项的意义是应用x l b 和x l c 来变异原向量，从而得到试验 向量x 2 ，存放在事先声明的矩阵x 2 中。另外，( 2 3 ) 式等价于下式： x 2 ( x l d + x i ) + f f x l d x 1 + x l b x k ) ( 2 4 ) 2 编程计算时一般用( 2 4 ) 式。 2 1 6 选择操作 差分演化的选择操作有两次，第一次是选择进行变异和交叉的时 机，一般采用蒙特卡罗方法进行选择：事先确定一个杂交概率c r ，再 随机的产生一个服从【0 , 1 】上的均匀分布的随机数，若该随机数不大于 c r ，则对目标向量的第，维进行交叉和变异，即进行上述( 2 4 ) 的操 作。否则，该目标向量的第j 维不变，再对该目标向量的第，+ l 维进行 同样的操作。 第二次选择很好理解，是从工嘶】和x 2 i 】中选择适应值较高的进入 下一代种群。 7 武汉理工大学硕士学位论文 2 2 折衷差分演化算法的基本框架和伪码 2 2 1 基本框架 s t e p l ：给变异因子f 、交又概率c r 和最大迭代次数m a x g e n s 赋初值； s t e p 2 ：初始化种群x 1 ( n x d ) ，设置迭代次数g - 1 ； s t e p 3 ：当g 一- m a x g e n s ，输出x 1 ，终止循环否则，继续； s t e p 4 ：对x 1 中的每个向量置执行如下操作： s 4 1 ：在x 1 中随机的选取一个适应值不小于置的适应值的个体霉； s 4 2 ：在【0 ，一1 】的整数中随机的选取两个不等于f 和，的数r l ，r 2 ； s 4 3 ：随机的产生一个不小于0 ，且不大于d 一1 的整数z ； s 4 4 ：对i 的每一维j 执行如下操作： s 4 4 1 ：产生一个【0 , 1 1 上服从均匀分布的随机数，； s 4 4 2 ：如果，a c r 或者j z ，则： v o 。k j + 碳+ f k j - 嘞+ x r l , j - - x r 2 , 1 】 否则，嘞； s 4 5 ：让置与e 竞争，把胜出的个体赋予置； s t e p 5 ：g + + ，返回s t e p 3 2 2 2 算法伪码 8 ， ) woi h g l h( )( 1dn a ) r + + ) + w + j 0 n + ； l o 1 n y ； 1，、 】 t 一 tj -1， a ， 【 z 1 0 】 1 ； i 1 1 n v j 【 a l ( 1 l r x t ( 0 1 r f n o i f ( 武汉理工大学硕士学位论文 c o s t 【i 】= e v a l u a t e ( x 1 【i 】【0 1 ，d ) ； m a i n ： f o r ( g f f i l ；g f f i m a x g c n s ；g + + ) # o r ( i f 0 ；i n ：i + + ) d od = r a n d l0 n ：w h i1 e ( c o s t 【d 】 c o s t 【i 】； d ob = r a n d l 0 n ：w h i l e ( b f f i = i ii b - = d ) ； d oc f r a n d l ( ) d ：w h i l e ( c = f f i itic = - d iic 一曲) ； z f r a n d l0 d ： f o r ( j = 0 ；j d ；j + + ) i f ( r a n d l0 f f i c ri | j + + z ) d i f f f f * ( x l 【d 】【j 】- x l 【i 】【j 】+ x l 【b 】【j 卜x 1 【c 】【j 】； x 2 【i 】【j 】= ( x 1 【i 】【j 】+ x l 【d 】【j 】) 2 + d i f f ； ) e is ex 2 【i 】【j 】= x l 【i 】【j 】； ) ) f o r ( i ；o ；i n ；i + + ) i s c o r e f e v a l u a t e ( x 2 【i 】【0 】，d ) ； i f ( s c o t c = c o s t 【i 】) ( c os t 【i 】- s c o r e ； f o r ( j ；0 ；j ) ，t h e n ( 返回s t e p 2 ) 武汉理工大学硕士学位论文 e ls e ( 把p e a k i 赋予p e a k ，然后返回s t e p 2 ) p d a s 算法流程图如上图3 2 。 3 4 2 新算法( p d a s ) 框架的合理性分析 分析上述p d a s 算法的框架可知：只要算法a l g 在找到一次全部全 局最优值点之前不会找到两次相同的部分全局最优值点，则最后p d a s 算法必然会输出被优化函数的所有全局最优值点。因为当算法a l g 找到 了一次全部全局最优值点后，在数组p e a k 中储存的必然是函数的全部 全局最优值点，只有当算法a i g 再次找到所有全局最优值点时，p e a k l 才 会与p e a k 相同，才会终止程序。 3 4 2 1 算法的成功率 若设某函数具有n 个全局最优值点，则可能的结果组合就有2 个， 并且在这些可能的结果中有一个是函数的全部全局最优值点。比如 s i x h u m pc a m e lb a c kf u n c t i o n 函数在区间【- 3 ，3 1 - 2 , 2 】上具有两个全 局最小值点，分别记两个全局最小值点为五，x 2 ，则可能的结果组合有4 个：g 、“ 、忆 ，“，屯) ，最后一个是函数的全部全局最小值点集 合。 为了估算出算法p d a s 一次性找到函数的全部全局最优值点的概 率，做模型假设：假设低效算法a l g 重复执行时，每个失败的结果( 指 部分全局最优值点的结果) 都等可能的出现。若设某一算法a l g 能以概 率p 找到多峰值函数的全部全局最优值点，则对于一个具有栉个全局最 优值点的函数来说，每个失败的结果出现的概率就是歹1 - j p 。据此，我 们抽象出如下的数学模型： 在一个黑袋中装有外形相同的f 南( 2 _ 一) 1 + 丁一1 个球，其中 南( 2 i 一，) 1 个球上标有s ， 另外( 2 “一1 ) 个球上分别标有 武汉理工大学硕士学位论文 五，2 ，五，乓。若做有放回的摸球试验，则摸得s 球的概率约为p ， 而摸得正( f 一1 ，2 ，z 一1 ) 的概率约为歹1 - = i p 。考虑在摸得具有同样角标的 f 球前摸到s 球的概率，记该概率为，则p 就是原低效算法a l g 一次 性找到全部全局最优值点的概率，就是我们要求的算法p d a s 一次性 找到函数的全部全局最优值点的概率。 若记b = 摸得具有同样角标的，前摸到s 球) ，b 2 在摸到s 前摸 到，个不同的角标的，球 ，其中，。o ，1 ，z 一1 。则口2 u - i 岛，又因为b 是相互独立的，所以： ，- 即) i p ( 味b j ) 。荟尸( 岛) ( 3 1 ) 为了计算的方便，在计算时省略模型中的取整算符，即令： f 南( n ) 卜山南c z 哪n 。南c ? 非r ， 悔( 刮茜c 。 则鸺卜丁2 s - - 1 。了m s - 2 孕。仔南( 灿) 一击南fm l ：l c 扎。 代入r 的值并化简可得：即户p 。( 瓦1 - p ) 豇( 牡o ( 3 2 ) 再根舯坝s z 珂知：，叩蓦( 鼍) 珥jc 舶， s ， 下面我们举例说明p d a s 算法的功效： 例1 ：设有算法a l g l 、a 1 9 2 分别以概率0 5 、0 8 找到s i x h u m pc a m e l b a c kf u n c t i o n 函数在区间- 3 ，3 1 卜2 ，2 1 上的两个全局最小值点，试估算 武汉理工大学硕士学位论文 船嘎s 和p d a 2 s 算法一次性找出该函数的两个全局最小值点的概率。 解：分别记删一和p d a z s 算法一次性找出该函数的两个全局最小值点 的概率为只+ 和巧，则根据上述公式( 3 3 ) 有： 和l 嘉刚驴驴嘣， 同理在公式( 3 3 ) 中代入p 一0 s , n 2 就可计算知：舅一0 9 8 。 例2 ：设有算法a t g 以概率0 5 找到双变量b r a n i n 函数在【一5 , 1 0 x 0 , 1 5 j 2 的三个全局最小值点，试估算黜算法一次性找出该函数的三个全局 最小值点的概率。 解：与上例类似，在公式( 3 3 ) 中代入p 一0 5 ，甩一3 就可算得p d a s 算法 一次性找出该函数的三个全局最小值点的概率约等于0 9 1 。 从上面推导的公式( 3 3 ) 和例子可以清楚地看到p d a s 算法确实 在很大程度上提高原算法a l g 一次性找到函数的全部全局最优值点的 概率，并且该概率是最优值点的个数的增函数，也就是说随着函数的 最优值点的个数的增加，p d a s 算法成功地找到全部全局最优值点的概 率会随之增大。 3 4 2 2 算法的时间复杂度 当然，“没有免费的午餐”，p d a s 算法框架提高算法a i g 的成功率 是以增大算法的时间复杂度为代价的，从而p d a s 算法框架的实用价值 还将取决于算法的时间复杂度。下面我们估算该算法的时间复杂度。 p d a s 算法把算法a l g 当成贝努里试验重复执行，把算法a l g 找到被 优化函数的全部全局最优值点看成是贝努里试验的成功事件，又从上 面给出的p d a s 算法框架可知，只有当成功事件第二次发生的时候算法 才终止。第二次成功发生在什么时候直接决定融算法的时间复杂 度。抽象出删s 算法的数学本质：麟算法运行过程实际上是在进行 重复的贝努里试验，并且我们感兴趣的事件是第二次成功发生在什么 时候。而又因为一般求解复杂多峰值函数的算法大都采用不确定性算 法( 如演化算法) ，因此我们感兴趣的事件就变为第二次成功平均发生 在第几次贝努里试验。即感兴趣于巴斯卡分布( p a s c a l ) 的数学期望。 武汉理工大学硕士学位论文 巴斯卡分布是十七世纪法国数学家巴斯卡提出来的。该分布考虑 重复的贝努里试验，并假设第，次成功发生在第亭次试验，则随机变量 宇服从巴斯卡分布。若成功的概率记为p ，失败的概率记为q ，p + 口- 1 ， 则巴斯卡分布的分布律为：聪- k ) 一( ：) ，矿4 ，其中七- r , r + 1 显然等待r 次成功所需要的平均试验次数就是；的数学期望： 嘶) 一群：牡“ 特殊情况：当，- 2 时，e 亭( 2 ) 一耋七( 七：1 p v 一耋七 一) p 2 q k - 2m 詈，馒1 ， 怒 p 即等待两次成功所需要重复进行的贝努里试验的平均次数为三。 ， 由此可见，p d a s 算法的时间复杂度只与原算法a l g 一次性找到全 部全局最优值点的概率和原算法a l g 的时间复杂度有关，具体地说，当 原算法a l g 的运行一次需要t 秒，且算法a l g 以概率p 找到某函数的全部 全局最优值点时，则p d a s 算法运行所需要的平均时间是三t 。 p 例如，对于上面的例1 ，用m s 运行所需要的平均时间是原算法a l & 的4 倍，但一次性找到全部全局最小值点的概率却从0 5 提高到0 8 5 ； 同样，p d a 2 s 运行所需要的平均时间是原算法a l g 。的2 5 倍，但一次性 找到全部全局最小值点的概率却从0 8 提高到0 9 8 。 本节针对一些求解复杂多峰函数的优化算法的成功率不高的问 题，提出了一种基于巴斯卡分布的算法框架：p d a s ，并从理论上证明 了该算法框架能够较大的提高原算法a l g 找出多峰值函数的所有最优 值点的成功率，还计算了p d a s 相对于原算法a l g 的时间复杂度的增量。 可见只要原算法a l g 的时间复杂度不是太大，算法4 l g 本身找出多峰值 函数的所有最优值点的成功率不是太低，p 删s 算法框架就是可取的。 据此，我们建议，当原算法a l g 本身找出多峰值函数的全部全局最优值 3 1 武汉理工大学硕士学位论文 点的成功率在0 3 到0 9 之间时，可以考虑应用p d a s 算法框架来提高 成功率，而原算法a l g 本身的成功率太小会导致p d a s 算法的时间复杂 度太高，当原算法a l g 本身的成功率较高的时候，无需再牺牲时间复杂 度来增加为数不多的成功率。另外，因为p d a s 算法在本质上的并行性， 可以尝试改重复执行a l g 算法为并行执行a l g 算法，这样可以减小p d a s 算法的时间复杂度。 由此可知，p d a s 算法框架固然可以提高很多算法的成功率，但是， 要根据p d a s 算法框架构造优秀的高效算法，对a l g 算法的选择也比较 重要，一般不宜选择时间复杂度较大的算法。近些年来，差分演化算 法他3 是函数优化领域中最活跃的算法之一，文献 3 9 ，4 ，4 0 分别说 明了差分演化算法在无约束和有约束优化中差分演化算法的优越性 能，而文献 1 0 对杂交差分演化算法进行了研究，并表明了这些新设 计的杂交算法在求解复杂多蜂函数上的优越性。而差分演化算法有个 突出的特征是：算法的时间复杂度小，因此我们建议可把p d a s 算法框 架与差分演化算法( 或者杂交差分演化算法等) 相结合，不难构造出 优化成功率较高而时间复杂度不大的算法。 3 5 本章小结 本章研究了差分演化算法在无约束优化领域中的应用。在原差分 演化算法的基础上，提出了三个具体的算法和一个算法框架( 或者说 是一类算法) ，分别是改进的差分演化算法，混合差分演化模拟退火算 法，基于小生境的混合差分演化模拟退火算法和一个基于巴斯卡分布 的算法框架。实验结果表明：改进的差分演化算法能够提高原算法在 求解无约束最优化问题时的收敛速度；混合差分演化模拟退火算法能 增强原算法的稳健性；基于小生境的混合差分演化模拟退火算法又能 很好的保持解群的多样性，是一种优化多峰值函数的行之有效的方法； 后又从理论上证明了基于巴斯卡分布的算法框架可以很大程度的提高 原算法的效率。 武汉理工大学硕士学位论文 第4 章差分演化算法在有约束最优化中的应用 有约束最优化问题的数学模型在第3 章中已经给出，本章将研究 用差分演化算法求解有约束最优化问题的相关技术。研究分两个方面 来进行：其一，处理约柬的技术；其二，在不同的差分演化算法的版 本中和不同的处理约束的技术中，哪个版本的差分演化算法与哪种处 理约束的技术相结合较好。 4 1 遗传算法、差分演化和一个处理约束的映射 用演化算法求解约束优化问题的关键有两个，其一是具体算法的 选择，其二是约束处理方法的选择。对于具体算法的选择，较经典的 当然是遗传算法( g e n e t i ca l g o r i t h m ，简记为g a ) ， s k o z i e l 和 z m c h a l e w i c z 已经做了很多具体的工作“；而在一些新兴的演化算法 中，差分演化算法( d i f f e r e n t i a le v o l u t i o n ，简记为d e ) 在求解最优化问 题上表现的尤为突出“2 。”。处理约束的方法也有很多，1 9 9 6 年 z m c h a l e w i c z 等把这些方法分为四类“”：基于保持可行解的方法、基 于罚函数的方法、基于搜索可行解的方法和杂交方法；而在此基础上， s k o z