（计算机软件与理论专业论文）多目标差分演化算法的构造及其应用.pdf

武汉理工大学硕士学位论文 中文摘要 差分演化算法，自1 9 9 5 年被提出以来。受到了相关领域中专家 学者们的重视和青睐，并且已经在多峰函数优化、数据过滤、多目 标优化等十九个大方向上得到了较好的应用成果。 本文主要对差分演化算法在多目标优化和约束处理方面进行一 系列研究，并将其应用在三个现实领域中。首先，对差分演化算法 的相关背景、基本思想和具体实现进行了概述。然后，对多目标差 分演化算法的构造进行了研究，比较并分析了最近几年来发表的四 类多目标差分演化算法p d e 、p d e a 、m o d e 和d e m o ，并对d e m o 的基础思想及具体算法实现进行了深入的研究。其次，提出了一种 处理约束问题的新颖的方法，即摄各种约束条件转换成新的匿标函 数。最后，将差分演化算法d e 及本文提出的约束处理方法应用在三 个比较热门的领域，即氩原子簇空间结构优化、考虑安全性的实时 调度优化和带约束的布局优化 本文的主要贡献如下：1 ) 、对差分演化算法d e 的基本思想和具 体代码实现进行了详细的分析和总结。2 ) 、比较并分析了最近几年 来发表的四类多目标差分演化算法，并对d e m o 的基础思想及其构 造进行了深入的研究。3 ) 、本文提出了一种用多目标优化思想来处 理约束问题的新方法。实验结果表明本文提出的方法能够成功的优 化带约束的单目标和多目标问题。4 ) 、本文尝试用差分演化算法来 优化氩原子簇的空间结构。实验结果表明当原子簇数量在1 6 以内时， 均能在合理的时间内找到全局最优解5 ) ，本文提出了一种基于差 分演化算法的实时调度算法s a r e c d e ，并与s a r e c e d f 进行了比 较。实验数据表明；改进算法s a r e c d e 能够在保证用户任务实时 性的前提下，比s a r e c e d f 算法的安全级别提高了2 5 左右。6 ) 、 对带约束的布局问题进行优化，实验结果表明多晷标差分演化算法 在布局优化领域具有一定的应用前景。 关键词：差分演化算法，多目标优化，约束处理，氩原子簇空间 结构优化，安全性及实时性调度，布局问题优化 。垂堡墨王查兰堡主茎垡堡奎 a b s tr a o 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 m ( d e ) w a si n t r o d u c e db yr s t o r n a n dk 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 o m a n ya r e a ss u c ha sm u l t i m o d a lf u n o 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 k l 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 ds o 0 n i nt h i sp a p e r ，w eh a v ed o n eas e r i e so fr e s e a r c ho nd i f f e r e n t i a l e v o l u t i o na l g o r i t h mi nm 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 dc o n s t r a i n t h a n d i n ga r e a s m o r e o v e r ，w eh a v ea p p l i e di t t ot h r e er e a la p p l i c a t i o n f i e l d s f i r s t l y ，w ed e s c r i b e dt h er e l e v a n tb a c k g r o u n d ，b a s i cp r i n c i p l e a n di m d l e m e n t a t i o nd e t a i l 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 s e c o n d l y ，w ed i ds o m er e s e a r c ho nt h ec o n s t r u c t i o no fm u l t i - o b j e c t i v e 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 ，a n da n a l y z e df o u rm u l t i o b j e c t i v e 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 sw h i c hw e r ep u b l i s h e di nr e c e n ty e a r s ， s u c ha sp a r e t od i f f e r e n t i a l e v o l u t i o n ( p d e ) ，p a r e t o d i f f e r e n t i a l e v o l u t i o na p p r o a c h ( p d e a ) ，m u l t i - o b j e c t i v ed i f f e r e n t i a le v o l u t i o n ( m o d e ) a n de s p e c i a l l y d i f f e r e n t i a le v o l u t i o nf o rm u l t i - o b j e c t i v e o p t i m i z a t i o n ( d e m o ) t h i r d l y ，w ep r o p o s e dan o v e lm u l t i - o b j e c t i v e o p t i m i z a t i o nc o n c e p tt oh a n d l ec o n s t r a i n t s e x p e r i m e n t a lr e s u l t sf r o m e i g h tc o h s t r a i n e dt e s t f u n c t i o n ss h o wt h a tt h e p r o p o s e dm e t h o d i s c a p a b l e o f s u c c e s s f u l l yo p t i m i z i n g c o n s t r a i n e d s i n g l e - a n d m u l t i o b j e c t i v ep r o b l e m s f i n a l l y ，w ea p p l i e d t h ed i f f e r e n t i a l e v o l u t i o na l g o r i t h ma n dc o n s t r a i n t sh a n d l i n gm e t h o dp r o p o s e di nt h i s p a p e r t ot h r e eh o t a p p l i c a t i o nf i e l d s ，s u c h a st h e g e o m e t r y o p t i m i z a t i o no fa r g o na t o mc l u s t e r s ，t h es e c u r i t y - a w a r er e a l t i m e s c h e d u l i n ga n dt h ec o n s t r a i n e dl a y o u to p t i m i z a t i o n t h em a i nc o n t r i b u t i o n si nt h i sp a p e ra r el i s t e da sf o l l o w s ： 1 ) w ea n a l y z e da n ds u m m a r i z e dt h eb a s i cp r i n c i p l ea n da l g o r i t h m i m p l e m e n t a t i o no 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 mi nd e t a i l 2 1w ea n a l y z e da n dc o m p a r e df o u rm u l t i o b j e c t i v ed i f f e r e n t i a l e v o l u t i o na l g o r i t h m sw h i c hw e r ep u b l i s h e di nr e c e n ty e a r s ，s u c h 武汉理工大学硕士学位论文 a sp d e ( 2 0 0 2 ) ，p d e a ( 2 0 0 2 ) ，m o d e ( 2 0 0 3 ) a n de s p e c i a l l y d e m o ( 2 0 0 5 ) 3 ) i nt h i sp a p e r ，w ep r o p o s e dan o v e lm u l t i o b j e c t i v eo p t i m i z a t i o n c o n c e p tt oh a n d l ec o n s t r a i n t s e x p e r i m e n t a l r e s u l t sf r o me i g h t c o n s t r a i n e dt e s tf u n c t i o n ss h o wt h a tt h ep r o p o s e dm e t h o di s c a p a b l eo fs u c c e s s f u l l yo p t i m i z i n g c o n s t r a i n e ds i n g l e - a n d m u l t i - o b j e c t i v ep r o b l e m s 4 】i nt h i sp a p e rw ed e s c r i b e an e ws e a r c hm e t h o dt h a tu s e 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 m ( d e ) t oo p t i m i z et h eg e o m e t r y o fs m a l la r g o na t o mc l u s t e r s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e e x a c tg l o b a lo p t i m a lc o n f i g u r a t i o no fa r g o nc l u s t e r sw i t ha t o m n u m b e rn s16c a nb ef o u n di nar e a s o n a b l ec o m p u t i n gt i m e ，a n d a p p r o x i m a t eo p t i m i z a t i o nc a na l s ob eo b t a i n e df o rc l u s t e r sw i t h n = 3 0 f r o mt h e i r3 - dg e o m e t r ys t r u c t u r e s ，w ec a ns e et h a tt h e i r o p t i m a le n e r g ys t r u c t u r e sa r eh i g h l ys y m m e t r i c a l 5 ) i nt h i sp a p e r ，o nt h eo n eh a n d ，w ea b s t r a c tt w om a t h e m a t i c m o d e l sf o rt h er e a l - t i m e s c h e d u l i n gp r o b l e m sc o n s i d e r i n g s e c u r i t yr e q u i r e m e n t s o nt h eo t h e rh a n d ，w ep r o p o s ean e w s e c u r i t y a w a r e r e a l t i m e s c h e d u l i n ga l g o r i t h m b a s e do n 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 ( s a r e c d e ) ，w h i c h c a n i m p r o v e o v e r a l l s e c u r i t y l e v e lo ft h e s y s t e mb yu p t o a p p r o x i m a t e l y2 5 o nt h eb a s eo fs a r e c - e d fw h e nr e a l - t i m e r e q u i r e m e n t i s g u a r a n t e e d e x p e r i m e n t d a t aa n ds i m u l a t e d r e s u l t ss h o wt h ef e a s i b i l i t ya n da v a i l a b i l i t yo ft h ep r o p o s e d m o d e l sa n dm e t h o d 6 ) w ea p p l i e dm u l t i - o b j e c t i v e d i f f e r e n t i a l e v o l u t i o n ( d e m o ) a l g o r i t h mt ot h ec o n s t r a i n e dl a y o u tp r o b l e m ，a n de x p e r i m e n t a l r e s u l t ss h o wt h a tm u l t i o b j e c t i v ed i f f e r e n t i a le v o l u t i o n ( d e m o ) c a ns u c c e s s i v e l yo p t i m i z el a y o u tp r o b l e m k e y w o r d s ：d i f f e r e n t i a le v o l u t i o 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 n ， c o n s t r a i n t sh a n d l i n g ，g e o m e t r yo p t i m i z a t i o no fa r g o na t o mc l u s t e r s ， s e c u r i t y a w a r er e a l t i m es c h e d u l i n g ，c o n s t r a i n e dl a y o u to p t i m i z a t i o n 1 1 i 此页若属实，请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名： 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：导师 注：请将此声明装订在学位论文的目录前。 武汉理工大学硕士学位论文 1 1 背景 第一章绪论 在科学和工程领域中，经常会遇到连续空间中的数值优化问题， 它们的目标函数通常是非线性甚至是不可微的，这时传统的优化方 法便很难获得成功。 近4 0 多年来的研究充分表明，模拟自然进化的搜索过程可产生 非常鲁棒的计算方法，即使这些模型只是自然界生物体演化过程的 粗糙简化。于是，演化算法( e v o l u t i o n a r ya 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 n m i g r a t i o n a l g o r i t h m ) 等。其中，差分演化算法一一这种基于群体差 异的演化算法一一在首届i e e e 演化计算竞赛中表现突出。 1 2 国内外研究现状及对现状的思考 差分演化算法n 。1 是于1 9 9 5 年由r s t o r n 和k ，p r i c e 提出来的一种 演化算法。最初，主要目的是用差分演化算法来求解连续全局优化 问题。其基本思想在于应用当前种群个体的差来重组得到中间种群， 武汉理工大学硕士学位论文 然后应用直接的父子混合个体适应值竞争来获得新一代种群。 差分演化算法最新颖的特征是它的变异操作，当选定一个个体 后，算法通过在该个体上加上两个个体的带权的差来完成变异。在 算法迭代的初期，因为种群中个体的差较大，从而这样的变异操作 会使算法本身具有较强的金局搜索能力，而到迭代的后期，当趋于 收敛的时候，种群中个体的差较小了，这也使得算法具有较强的局 部搜索能力。这种新颖的变异操作也使得该算法在求解函数优化等 问题上有着其它同类方法不可比拟的优点。主要优点可以总结为以 下三点：( 1 ) 待定参数少；( 2 ) 不易陷入局部最优；( 3 ) 收敛速度快。 经过十年的研究，差分演化算法得到了较大的发展。从算法设 计上看，一些改进的差分演化算法“1 钉已经被成功的设计出来，这些 改进的算法一般是从算法的鲁棒性、算法的收敛速度、算法的局部 搜索能力、算法的全局搜索能力等几个方面或者某一个方面对基本 的差分演化算法进行改进 从应用上看，该算法已经在多峰函数优 化( m u l t i m o d a lf u n o 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 r d 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 o b je c t i v eo p t i m i z a t i o n ) 等十九个大方向上得到了较好的仿真 结果“3 2 “差分演化算法也正在引起越来越多的学者的重视。 十年的时间，差分演化算法已经在十九个大的方向上得到了较 好的仿真结果，这足以见得差分演化算法在演化界所受到的重视程 度。但是在研究差分演化算法的学者中，从事多目标差分演化算法、 约束处理算法以及基于现实应用的学者却为数不多。 现实世界的大多数优化问题都是多目标优化问题，既然差分演 化算法在单目标优化问题上具有明显的优越性，那么，对差分演化 算法进行扩展，使其能够处理多习标优化问题，应该也有很大的前 景。基于这一思想，近年来也相继出现了各种各样的多目标差分演 化算法，如p d e ( 2 0 0 2 ) 、p d e a ( 2 0 0 2 ) 、m o d e ( 2 0 0 3 ) 和d e m o ( 2 0 0 5 ) 等等。 现实世界中的许多优化问题实际上都是带约束的优化问题，然 而处理约束的最常用的方法还是使用罚函数法，而罚函数最大的缺 点就是需要大量的时间来调整罚系数。因而，设计一种高效而实用 的约束处理算法显得尤为重要。 2 武汉理工大学硕士学位论文 目前，在原予簇空间结构优化，安全性及实时性调度以及带约 束布局优化方面，大多数算法均采用遗传算法、模拟退火、粒子群 算法等。而这三类应用闯题均为可抽象为连续函数的优化问题，因 而更适合用差分演化算法或多目标差分演化算法来求解。 1 3 本文的研究内容 本文就是在上述背景下及我们所注意到的一些不足之处的基础 上开展的对差分演化算法的基础性和应用性研究。主要的研究内容 包括以下六个方面： 一、对差分演化算法d e 的基本思想和具体代码实现进行了详细 的分析和总结 二、比较并分析了最近几年来发表的四类多目标差分演化算法 p d e ( 2 0 0 2 ) 、p d e a ( 2 0 0 2 ) 、m o d e ( 2 0 0 3 ) 和d e m o ( 2 0 0 5 ) ，并 对d e m o 的基础思想及其构造进行了深入的研究。 三、现实世界中的许多优化问题都是带约束的优化问题，然而 处理约束的最常用的方法还是使用罚函数法，而罚函数最大的缺点 就是需要大量的时间来调整罚系数。本文提出了一种用多目标优化 思想来处理约束闯题的新方法。即先将各种约束函数转换成新的目 标函数，然后再用多目标差分演化算法对其进行优化。为了证明该 方法的有效性，我们选择了四个常用的带约束的单臣标测试问题 ( 9 0 6 ，9 0 8 ，g l la n dg e a r b o x ) 秘带约束的多目标测试闯题( c o n s t r 。 s r n ，t n ka n dk i t a ) 。实验结果表明本文提出的方法能够成功的优 化带约束的单目标和多目标问题 四、近年来，由于原子簇结构的优化在物理、化学和材料科学 方面具有极其重大的影响，因而关于原子簇空间结构优化方面的研 究越来越多。但是，搜索最低的能量结构或最稳定的空间构象是一 个n p 难问题。差分演化算法是一类启发性方法，具有三大优点：对 初使化参数不需过多调整，基本上都能找到真正的全局最优解；收敛 速度较快；算法所需的参数较少因此，本文尝试用差分演化算法 来优化氩原子簇的空间结构。实验结果表明当原予簇数量在1 6 以内 时，均能在合理的时间内找到全局最优解；当原子簇数量为3 0 时， 3 武汉理工大学硕士学位论文 差分演化算法仍然能找到近似最优解。从这些解的三维空间结构可 以发现：它们最稳定的空间构象是高度对称的。 五、在实时应用系统中，大部分应用程序除了要严格满足实时 性要求外。对系统的安全性也高度重视然而，传统的实时调度算 法并没有考虑系统的安全性这一因素。t a ox i e 。x i a oq i n 等人最近提 出了一种能够处理安全性的实时调度策略s a r e c 和相应的实时调 度算法s a r e c e d f 。但是，该调度算法s a r e c e d f 存在着一些不 足；在满足实时性的前提下尽量提高安全性这一调度问题实际上可 以抽象为一个带约束条件的求函数最大值优化问题；s a r e c 。e d f 算 法是一种贪婪搜索算法，没有对全局性进行比较，所以搜索的最终 结果可能不是全局最优解。本文一方面对安全性及实时性调度问题 抽象出了两类数学模型，另一方面提出了一种基于差分演化算法的 实时调度算法s a r e c d e ，并与s a r e c e d f 进行了比较。实验数据 和比较结果表明；改选算法s a k e c d e 镌够在保证用户任务实时性 的前提下，比s a r e c e d f 算法的安全级别整体提高了2 5 左右，因 而具有一定的可行性和有效性。 六、布局问题属于n p 难闻题。就是按一定的要求把一些物体最 优地放置在一个空间内。布局可分为二维布局和三维布局，它们一般 要求待布物之间、待布物与容器之间不干涉，并尽量提高空间利用 率，此类问题为无性能约束的布局问题。有一类问题除以上基本要 求外，还需考虑其它的性能约束，如惯性、平衡性、稳定性等，我们称 之为带性能约束布局问题，简称约束布局问题，由于这类问题的解空 间常为非凸集，因此难于求解。目前较多的做法是应用启发式方法求 其近似最优解，但结果均不太理想本文尝试用多目标优化思想处理 约束的方法来对带约束的布局问题进行优化。实验结果表明多目标 差分演化算法以及多目标优化思想来处理约束的方法在布局优化领 域具有一定的应用前景 1 4 本文内容安排 本文后续章节组织如下：第二章对差分演化算法d e 的基本思想 和具体代码实现进行了详细的分析和总结；第三章比较并分析了四 4 武汉理工大学硕士学位论文 类多目标差分演化算法p d e 、p d e a 、m o d e 和d e m o 及其构造；第 四章提出了一种用多目标优化思想来处理约束问题的新方法；第五 章用差分演化算法或多目标差分演化算法来对原子簇空间结构优 化、安全性及实时性调度以及带约束布局优化等三类问题进行求解； 第六章总结全文，并提出了有关差分演化算法和多目标差分演化算 法继续研究的一些想法。 5 武汉理工大学硕士学位论文 第二章差分演化算法及代码实现 差分演化算法( 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 o e “4 1 在1 9 9 5 年为求解有关切比雪夫多项式的问题提 出来的，是一类基于群体差异的演化算法。其基本思想是应用当前 种群中个体的差来重组得到中间种群，然后通过父子之间的锦标赛 制的竞争获得薪一代种群。d e 发展至今，已经有了很多不同的版本， 本章将以其中一个版本为例介绍d e 的基本操作，再给出d e 算法的基 本流程和伪码，最后给出d e 算法的完整代码实现( d e l p h i 版) 。 2 1 差分演化算法的基本操作 差分演化是一种基于实数编码的演化算法，算法的基本思想及 整体构架与遗传算法楣类似，从一代种群到下一代种群都要经过变 异、交叉、选择等操作，也一样有几个至关重要的参数必须事先确 定。下面逐一介绍差分演化算法的几个关键性的操作。 2 1 1 参数的确定 差分演化算法主要涉及以下四个参数：种群规模大小， 个体( 也称变量) 的维数d ( 也称为染色体的长度) ，变异因子f ， 交叉概率c r 。有研究结果表明：群体规模一般介于5 d 到1 0 d 之 间( 根据实际问题可以确定变量的维数d ) ，我们的实验结果也表明 取= 6 d 较好；变异因子，一般在( 0 ，2 ) 之间取值，一般我们取f = o 5 ； 交叉概率c r 一般在【o 1 】之间选择，一般来说，c r 越大。收敛速度越 快，但易于早熟，易于陷入局部最优，算法的稳健性越差，比较好 的选择是c r = 0 3 。当然，这些都只是经验值，没有严密的理论证明， 对于某些具体的问题也可能取其它的值会得到更好的结果，需要具 体问题具体分析。 2 1 2 初始化种群 先声明两个行d 列的矩阵，分别记为x 1 、x 2 ，其中x 1 用来存 放当前种群，并且产生n x d 个满足约束条件且服从均匀分布的随机 6 武汉理工大学硕士学位论文 数作为x 1 的初始值，具体操作如下： x l e i j 】= r a n d l ( 堙 【j 卜正口“刀) + 如，【刀 其中f = l ，2 ，n ，j - - 1 ，2 ，d jr a n d l 是【0 , 1 】上的服从均匀分布的随 机数，h i g h j 】和如埘刀分别是变量的第j 维的上晃和下界。 2 1 3 变异操作 与传统的遗传算法不同，差分演化的变异操作通过加上一个均 值为0 的随机向量到被变异的目标向量上来完成。如何产生一个均 值为0 的随机向量呢? 该算法通过从种群x 1 中随机的选择两个向量 ( 这两个向量都不等于目标向量) ，然后求这两个向量的差来得到均 值为0 的随机向量。当然，把这个差随机变量乘以某个变异因子f 后， 其均值还是o 。这里保持用来变异的随机向量的均值为0 ，可以从很 大程度上减小不可行解出现的概率。 如下所示，就是通过两个随机向量x l b 和x l c 来变异目标向量 x l a 成x l a 的表达式： x l a = x l a + f ( x l b x l c ) ( 2 - 1 ) 2 1 4 杂交操作 要进行杂交运算，首先必须给目标向量选择交叉的对象，在这 里，本算法随机地从种群中选取一个不比目标向量的适应度低的向 量作为交叉对象。这样既能保持种群的多样性，又能兼顾收敛速度， 是一种折衷的选取方法 一旦耳标向量x l i 的交叉对象x l d 被选定，则作如下式所示的带 权的加法： x l m = ( o 5 一，) x l i + ( 0 5 + f ) x l d( 2 - 2 ) 事实上，上式可以理解为按一定的权值取x l d 和x l i 的信息，再 把所取的信息融合在一起得到新的个体x l m 。这就类似传统的遗传算 法中的交叉，所以这里也称之为交叉 2 1 5 构造试验向量 试验向量是某个目标向量经过上述的变异和交叉而得到的一个 新的向量，把上述( 2 - 1 ) 式和( 2 - 2 ) 式有机的结合在一起得如下 的( 2 - 3 j 式： 7 武汉理工大学硕士学位论文 x 2 i = ( o 5 一，) x l i + ( o 5 + ，) x l d + f ( x l b - x l c ) ( 2 - 3 ) 上式的前两项意义是应用x i d 作为交叉对象来与目标向量x l i 交 换信息。第三项的意义是应用x l b 和x l c 来变异原向量，从而得到试 验向量x 万，存放在事先声明的矩阵x 2 中另外，( 2 - 3 ) 式等价于下 式： x 2 i = ( x l d = + x 一l i ) + f ( x l d x l f + x 1 6 一x l c ) ( 2 - 4 ) 编程计算时一般用( 2 - 4 ) 式。 2 1 6 选择操作 差分演化的选择操作有两次，第一次是选择进行变异和交叉的 时机，一般采用蒙特卡罗方法进行选择：事先确定一个杂交概率c r ， 再随机的产生一个服从【o ，1 】上的均匀分布的随机数，若该随机数不大 于c r ，则对目标向量的第j 维进行交叉和变异，即进行上述( 2 - 4 ) 的操作。笞则，该目标向量的第j 维不变，再对该目标向量的第j + l 维 进行同样的操作。 第二次选择很好理解，是从x l i 和x 2 【司中选择适应值较高的进 入下一代种群。 2 2 差分演化算法的基本框架和伪码 2 2 1 基本框架 s t e p l ：给变异因子，、交叉概率c r 和最大迭代次数m a x g e n s 赋初值5 s t e p 2 ：初始化种群x 1 ( n d ) ，设置迭代次数暑= l ： s t e p 3 ：当g m a x g e n s ，输出x 1 ，终止循环。否则，继续； s t e p 4 ：对x l 中的每个向量i 执行如下操作： s 4 1 ：在x l 中随机的选取一个适应值不小于焉的适应值的个体不； s 4 2 ：在【0 , n - 1 】的整数中随机的选取两个不等于i 和，的数r l 、，2 ； s 4 3 ：随机的产生一个不小于0 ，且不大于d l 的整数z ； s 4 4 ：对焉的每一维，执行如下操作： s 4 4 1 ：产生一个【0 ，1 】上服从均匀分布的随机数r ； s 4 4 2 ：如果r - c r 或者j z ，则： 8 武汉理工大学硕士学位论文 = 睇，+ 似【x , j - x o + x , ，j - x , 2 , 1 】 否则，峋= 而5 s 4 5 ：让盂与竞争，把胜出的个体赋予置。 s t e p 5 ：暑+ + ，返回s t e p 3 。 2 2 2 算法伪码 i n i t f a “z a t i o n ： f o r ( i = 0 ；i n ；i + + ) t f o r 0 = o ；j d 0 + + ) f x l 【i 】 j 】_ l o w + r a n d l ( ) + ( h i g h - l o w ) ； ) c o s t i 2 e v a l u a t e ( x 1 【i 儿0 】，d ) ； ) m a l n ： f o r ( 9 2 1 ；g 2 m a x g e n s ；g + + ) f o r ( i = o ；i n ；i + + ) d od 2 r a n d l ( ) + n ；w h i l e ( c o s t d 】 c o s t i 】； d ob 2 r a n d l ( ) n ；w h i l e ( b = = i | i b = = d ) ； d oc = r a n d l o d ；w h i l e ( c = = i t c = = d l l c = = b ) ： z 2 r a n d l 0 + d ： j f o r o = o ；j d ；j + + ) i f ( r a n d1 ( ) = c r h j + + z ) d i f f 。f ( x 1 【d 】【j 】一x l 【i 】d 】+ x 1 【b 】【i 】- x l 【c 】d 】； x 2 i j 】2 ( x 1 【i 】【j 】+ x 1 【d u ) 2 + d i i f ； 9 ：茎堡翌三奎兰堡主茎垡笙苎 ) e l s ex 2 i l u = x 1 【i 】 j 】； ) f o r ( i = 0 ；i n ；i + + ) ( s c o r e = e v a l u a t e ( x 2 【i 】【0 】，d ) ； i f ( s c o r e = c o s t i ) ( c o s t i 2 s c o r e ； f o r ( j = o ；j d ；j + + ) x 1 【i l u l = x 2 i 】 j 】； ) ) 2 3 差分演化算法d e 的完整代码实现 d e 发展至今，已经有了很多不同的开发语言版本，如j a v ac o d e 、 cc o d e 、，m a t l a bc o d e 、c + + c o d e 等。所有这些源代码均可从以下网 址中找到：h t t p ：w w w i c s i ，b e r k e l e y e d u 一s t o r n o o d e h t m l # c s o u 。 本文采用d e l p h i6 开发语言对差分演化算法d e 重新独立实现，完 熬代码及相应描述如下所示。 2 ，3 1 高维测试函数 1 0 0 0 r a i n ，( x ) = n + i x , 2 - c o s ( 2 7 r x , ) t = 1 5 t 一5 1 2 王s5 1 2 ，i = , 2 , - - - , 1 0 0 0 维数n = 1 0 0 0 ，最优值；，( o ，o ) = 0 。 1 0 茎堡里三奎堂塑主兰垡丝奎 2 3 2 运行界面及算法参数设置 图2 - 1 差分演化算法运行界面 算法参数设置： 种群大小n p = 3 0 ；变异因子f = 0 3 5 ； 交叉概率c r = o 2 ；最大迭代次数m a x g e n s = 3 0 0 0 0 ； 变异策略：d e r a n d 2 e x p 。 2 3 3 差分演化算法d e 完整代码 u n i tu n i t l ； i n t e r f a c e n s c ， w i n d o w , m e s s a g e s ，s y s u t i i o 。v a r i a n t s ，c l a s s e s ，gr a p h i e s ，c o n t r o l s ，f o r m s 。 d i a l o g s ，s t d c t r l s , t y p e t f o r mi c i a s s ( t f o r m ) m r c s u l t ：t m e t o o , m r c s u l t 2 ：t m e t o o ； g r o u p b o x l ：t g r o u p b o x ； s r u n ：t b u t t o n ： t s t r u t e g y ：t c o m b o b o x g l a b s l l ：t l a b e l ： t n p ：t e d i t ； l a b e l 2 ：t l a b e l ； l a b e l 3 ：t l a b e l ： t f ：t e d i t ： l a b c l 4 ：t l a b e l ： t c r ：t e d i t ： l a b e l 5 ：t l a b e l ： t g c n m a x ：t e d i t ； l l 武汉理工大学硕士学位论文 l a b e l 8 ：t l a b c l ： s u e c t i m e ：t e d i t ： p r o c e d u r es r u n c i i n k ( s e n d e r ：t o b j e e t ) p r t r a t e p r i v a t ed e c l a r a t i o n s p u b l i c p u b l i cd e c l a r a t i o n s e n d ； f o r m l ：t f o g m i ； i m p l e m e n t a t i o n $ r + d f r o ，定义全局常量 c o n s t m a x p o p 一5 0 0 ；最大种群数量 m a x d i m = 3 0 0 0 ；最大变量维数 个体结构 t y p e t i n d a r r a y 。a r r a y 【0 ( m a x d i m i ) 】o fd o u b l e | 斡群结构 t y p e t p o p a r r a y 。a r r a y 0 ( m a x p o p 1 ) 】o ft i n d a r r a y ； ，定义全局变量 v a r o c p o p ，d p o p ：t p o p a r r a y ；1 1 种群变量 p o l d ，p n e w ，p s w a p ：“t p o p a r r a y ；种群指针 c o s t ：a r r a y 【0 ( m a x p o p 1 ) 】o fd o u b l e ；种群的目标函数值 t m p ，b e e t ，b e s t i t ：t l n d a r r e y ；个体，全局最优个体，当代最优个体 i m i n ：i n t e g e r ； 指向全局最优值( 最小值) c m i n ：d o u b l e ；全局最优值( 最小值) n f e v a l ：i n t e g e r ；函数计算的次数 c v 4 r ：d o u b l e ； 种群的方差 c m e u n ：d o u b l e ；种群的平均函数值 g u n ：i n t e g e r ； 当前代致 t r i a l c o s t ：d o u b l e ； 变异后的函数值 d ：i n t e g e r ；变量维教 n p ：i n