（计算机应用技术专业论文）基于差分演化和分布估计的混合演化算法研究.pdf

摘要 全局优化问题几乎应用于每一个学科，工程领域和业务中。例如，工程师要 为设计的汽车提供最佳的性能。为了实现这一目标，需要优化汽车的配置参数。 最佳参数配置的查找就属于全局优化类别。现在大量的工作一直致力于解决联系 的全局优化问题。而连续的全局优化问题的主要挑战是这类问题往往有很多的局 部最优解。差分演化算法( d e ) 的是在解决连续全局优化问题上有着相当好的 表现。它主要是使用从目前的个体所获得的距离和方向信息，引导其进一步搜索。 分布估计算法( e d a ) 的概率模型，从一个有前途的解决方案集中提取的并按照 其生成新的样本。本文所提出的三种d e 和e d a 混合算法模型，综合了2 种算 法的优点，对连续的全局优化问题进行求解。把三种算法通过典型的测试问题进 行测试研究，比较d e 算法最好的版本和e d a 算法。实验结果表明，这三种算 法模型优于d e 算法和e d a 算法，并分析比较了三种算法模型，以及考察其性 能参数的实验效果。 本文以d e 和e d a 算法为基础，提出三种混合算法模型：1 ) 基因混合模型： 如果把每个个体比喻成一个基因链，那么基因链中的基因一部分来自d e 算法一 部分来自e d a 算法，该模型使个体更加具有多样性；2 ) 个体混合模型：如果把 种群比喻成一个社会，那么社会中的个体一部分来自d e 算法种族，一部分来自 e d a 算法种族，该模型使种群更加具有多元性；3 ) e d a 指导d e 变异方向：如 果把种群比喻成一个团队，e d a 根据统计概率生成的临时个体就像一个领导者 去指导种群中的个体按照优秀方向去变异( 搜索) ，该模型使搜索在全局和局部 都有很好的表现。 本文最后通过典型的测试函数对三种算法模型进行了测试，以及考察各个模 型的性能系数的实验效果，并且与d e 和e d a 算法进行了比较。通过对5 4 8 0 组 试验数据分析表明，三种模型算法在有多峰特性问题和骗特性问题上的效果更加 优于d e 和e d a 算法。最后分析了各个模型的性能系数，以及比较了三种模型 的个子特点。 关键字：差分演化算法，分布估计算法，全局优化问题，混合算法，变异 a b s t r a c t g l o b a lo p t i m i z a t i o np r o b l e m sa r eu s e da l m o s ti ne a c hs u b je c t ，e n g i n e e r i n gf i e l d a n db u s i n e s s f o re x a m p l e ，a ne n d n e e rn e e d st od e s i g nc a r sw i t hb e s tp e r f o r m a n c e ，s o h em u s to p t i m i z ec o n f i g u r a t i o np a r a m e t e ro ft h ec a r si no r d e rt or e a l i z et h i st a r g e t t h es e a r c ho fb e s tc o n f i g u r a t i o np a r a m e t e rb e l o n g st og l o b a lo p t i m i z a t i o nc a t e g o r y , a n dal o to f j o b sa l w a y sd e v o t et os o l v er e l a t i v eg l o b a lo p t i m i z a t i o np r o b l e m s ，b u tt h e m a i nc h a l l e n g eo fc o n t i n u o u sg l o b a lo p t i m i z a t i o np r o b l e mi st h a tt h e r ea r ea l w a y s m a n yl o c a lo p t i m a ls o l u t i o n si nt h i sp r o b l e 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 mh a s p r e t t yw e l lp e r f o r m a n c ei ns o l v i n gt h i sc o n t i n u o u sg l o b a lo p t i m i z a t i o np r o b l e m i t l e a d sf u r t h e rs e a r c ht h r o u g hu s i n go b t a i n e dd i s t a n c ea n dd i r e c t i o ni n f o r m a t i o nb y p e o p l en o w a d a y s ，n l ep r o b a b i l i t ym o d e lo 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 s e x t r a c t e df r o map r o m i s i n gs o l u t i o ns e ta n dg e n e r a t e dn e ws a m p l ea c c o r d i n gt oi t t h r e eh y b r i da l g o r i t h mm o d e l sb a s e do nd ea n de d a i n t e g r a t et h ea d v a n t a g e so f t h e s et w oa l g o r i t h m si nt h i sp a p e r , t os o l v ec o n t i n u o u sg l o b a lo p t i m i z a t i o np r o b l e m t h r e ea l g o r i t h m sa r et e s t e dt h r o u g hc l a s s i cb e n c h m a r kf u n c t i o n s ，a n dt h eb e s td e a l g o r i t h mi sc o m p a r e d 、 ，i t l le d aa l g o r i t h m 1 1 l es i m u l a t i o n sp r o v et h a tt h et h r e e m o d e l sa r eb e r e rt h a nd ea n de d a a l g o r i t h m ，a n dm e ya r ea n a l y z e df r o me a c ho t h e r t h r o u g hi n v e s t i g a t i n gt h ep e r f o r m a n c ep a r a m e t e rr e s u l t s t h r e eh y b r i da l g o r i t h mm o d e l sa r ep r o p o s e db a s e do nd ea n de d a a l g o r i t h mi n t h i sp a p e ra sf o l l o w i n g ：1 ) g e n eh y b r i dm o d e l ：t h eg e n e si ng e n e t i cc h a i np a r t i a l l y c o m ef r o md e a l g o r i t h ma n dp a r t i a l l yc o m ef r o me d aa l g o r i t h mi fe a c hi n d i v i d u a li s c o m p a r e dt oag e n e t i cc h a i n ，t h i sm o d e lm a k e si n d i v i d u a l sh a v em o r ed i v e r s i t y ；2 ) i n d i v i d u a lh y b r i dm o d e l ：t h ei n d i v i d u a l si ns o c i e t yp a r t i a l l yc o m ef r o md ea l g o r i t h m p o p u l a t i o na n dp a r t i a l l yc o m ef r o me d aa l g o r i t h mp o p u l a t i o ni ft h ep o p u l a t i o ni s c o m p a r e dt oas o c i e t y , t h i sm o d e lm a k e sp o p u l a t i o nh a sm o r ep l u r a l i t y ；3 ) e d a g u i d e st h em u t a t i o nd i r e c t i o no fd e ：t h et e m p o r a r yi n d i v i d u a lg e n e r a t e da c c o r d i n gt o s t a t i s t i c a lp r o b a b i l i t yb ye d a g u i d e si n d i v i d u a l st om u t a t et o w a r de x c e l l e n td i r e c t i o n a sal e a d e ri ft h ep o p u l a t i o ni sc o m p a r e dt oat e a m ，t h i sm o d e lm a k e sl o c a la n dg l o b a l r e s e a r c hh a v eb e r e rp e r f o r m a n c e t h r e ea l g o r i t h mm o d e l sa r et e s t e dt h r o u g hc l a s s i cb e n c h m a r kf u n c t i o n sf i n a l l yi n t h i sp a p e r , a n dt h ep e r f o r m a n c ep a r a m e t e rr e s u l t sa r ei n v e s t i g a t e dt h r o u g hc o m p a r i n g d ea l g o r i t h mw i t he d aa l g o r i t h m t h e5 4 8 0g r o u p so ft e s tr e s u l t sp r o v et h a tt h e t h r e em o d e l sh a v eb e a e rp e r f o r m a n c et h a nd ea n de d a a l g o r i t h mi nm u l t i m o d a l f u n c t i o na n dc h e a tf u n c t i o n t h ep e r f o r m a n c ep a r a m e t e r so fe a c hm o d e la r ea n a l y z e d t h r o u g hc o m p a r i n gt h ec h a r a c t e r i s t i c so ft h r e em o d e l s 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 na l g o r i t h m ，e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m ， g l o b a lo p t i m i z a t i o np r o b l e m ，h y b r i da l g o r i t h m ，m u t a t i o n l 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：塑圭递日期：兰坐：! ! 兰z 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定户 研究生( 签名) ：狱立瓦 导师( 签名) 兰兰迦：2 p 肌。，2 7 武汉理t 大学硕士学位论文 1 1 问题的提出 第1 章绪论 差分演化( d i f f e r e n t i a le v o l u t i o n ，d e ) 1 - 2 】是最成功的对连续的全局优化问 题的演化策略( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 之一。差分演化从目前的个体提 取出不同的信息( 如距离和方向等信息的解决方案) 【3 】，以指导其进一步的搜索。 然而，差分进化没有任何机制来提取和使用全局信息的搜索空间。分布估计算 法( e s t i m a t i o no fd i s t r i b u t i o n a l g o r i t h m ，e d a ) , h i 2 , 1 5 是一种进化算法 ( e v o l u t i o n a r ya l g o r i t h m s ，e a ) 1 3 , 1 4 】的新类。分布估计算法( e d a ) 的直接提 取来自搜索到目前为止全局搜索空间的统计资料，并根据优秀的个体构建一个 有前途的概率模型解决方案。新的解决方案是从有前途的概率模型中采样。分 布估计算法( e d a ) 已经被应用在许多的全局连续的优化问题上。取得良好的结 果，但还有许多工作要做，以进一步改善她的表现。 一个优秀的进化算法( e a s ) ，应兼顾本地的局部信息和迄今为止的全局信息， 兼顾效率和搜索空间范围。分布估计算法( e d a ) 的估计搜索主要是基于全局 的信息，而差分演化算法( d e ) 的距离和方向信息是居于局部的信息【3 1 。因此， 这是值得研究两者的混合是否可以改善算法的表现。本文是基于这种思想提出 几种方法兼顾本地信息和全局信息的d e 和e d a 混合算法。 1 2 分布估计算法及其研究现状 1 2 1 基本思想 分布估计算法是一种基于概率模型的进化算法，最早由m t i e h l e n b e i n 和 p a a l 3 ( 1 9 9 6 年) 提出【1 5 】。其思想就是提取当前优秀个体集合的概率模型来指导 算法下一步的搜索。由较优解的概率分布函数中抽样产生新的个体。在e d a 中， 第一批的候选解决方案一般通过是随机产生。评估种群中每个个体的适应值， 倾向于选择较优秀的解决方案。将搜索推向了更好的空间和区域。下一代的候 武汉理工大学硕士学位论文 选方案是由从选定的解决方案提取的概率模型生成的新的样本。这种特殊的取 样方式使分布估计算法与其他进化算法相区别。分布估计算法的基本框架可如 下表示【3 7 】： s t e pl ：初始化种群； s t e p2 ：评估每一个个体的适应值，根据某种选择机制从种群中选取部分优 秀的个体； s t e p3 ：用选择的优秀个体估计一个概率分布，建立分布模型； s t e p4 ：根据分布模型生成新的中间解决方案； s t e p5 ：替代旧种群中的一些或全部个体生成下一代种群； s t e p6 ：若终止条件不满足，则算法停止；否则便返回步骤2 7 圈 l 评估和选择 1 布建立模型r 1一生嚣霎羹一1 一瞀殃 聚止广 最优解yes 1 2 2 研究现状 图1 1 分布估计算法的流程图 分布估计算法是一个相对较新的算法，是已经建立的进化计算的分支【4 1 。分 布估计算法，最初引入进化计算领域，是为了克服早期的离散进化算法特别是 简单遗传算法( g e n e t i ca l g o r i t h m ，g a ) 的一些缺点。分布估计算法的主要操作 是对选定的解决方案为基础的概率分布的估计，新的解决方案服从这一分布。 自1 9 9 6 年分布估计算法的概念的提出，在2 0 0 0 年前后得到迅速发展，成为当 前进化计算领域前沿的研究内容。 下表我们列出e d a 的发展史： 2 武汉理工大学硕士学位论文 表1 1e d a 主要算法 时间作者算法 1 9 9 4 年 b a l u j ap b i l ( p o p u l a t i o n b a s e di n c r e m e n t a ll e a m i n g ) 算法【1 6 - 1 8 1 9 9 6 年 m i i e h l e n b e i n u m d a ( u n i v a r i a t em a r g i n a ld i s t r i b u t i o na l g o r i t h m ) 算 参# 【1 9 - 2 0 】 t 1 9 9 7 年d e b o n e t 等m i m i c ( m u t u a li n f o r m a t i o nm a x i m i z a t i o nf o ri n p u t c l u s t e r i n g ) 算法【2 1 】 1 9 9 7 年 b a l u j ac o m i t ( c o m b i n i n go p t i m i z e r s 、) l ，i t l lm u t u a li n f o r m a t i o n t r e e s ) 算法f 2 2 】 1 9 9 8 年 s e b a g 等p b i l 推广到连续空间 1 9 9 8 年h a r i k 等 c g a ( c o m p a c tg e n e t i ca l g o r i t h m ) 算法 1 9 9 9 年p e l i k a n 等 b m d a ( b i v a r i a t em a r g i n a ld i s t r i b u t i o na l g o r i t h m ) 2 3 , 2 4 1 9 9 9 年 m i i e h l e n b e i n f d a ( f a c t o f i z e dd i s t r i b u t i o na l g o r i t h m ) 算法【2 5 - 2 9 1 9 9 9 年h a r i k 等e c g a 算法【3 0 】 1 9 9 9 年p e l i k a n 等 b o a ( b a y e s i a no p t i m i z a t i o na l g o r i t h m ) 算法【8 3 1 3 2 】 2 0 0 0 年 l a r r a n a g a 等e b n a ( e s t i m a t i o no fb a y e s i a nn e t w o r k sa l g o r i t h m ) 算法 【3 3 2 0 0 0 年b o s m a n 等 i d e a ( i n t e g r a t e dd e n s i t y e s t i m a t i o n e v o l u t i o n a r y a l g o r i t h m ，) 算法【3 4 】 2 0 0 1 年s t s u t s u i 等g m d c m l l 2 1 2 0 0 2j o 芒e n k e kp a r a l l e le s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m s 3 5 】 2 0 0 5p e l i k a n h b o a ( h i e r a r c h i c a lb a y e s i a no p t i m i z a t i o na l g o r i t h m ) t 3 6 】 2 0 0 5 qz h a n g 等 d e e d a 3 】 3 武汉理i 大学碗学位论文 图1 - 2 e d a 发展情况 1 3 差分演化算法及其研究现状 差分演化算法i f f e r e n t i a l e v o l u t i o n , d e ) t ”堤由r s t o m ；和k p r i c e ：1 9 9 5 年提 出的一类基于实数编码的、求解连续全局优化问题的演化算法。并且在1 9 9 6 年 首届i e e e 进化算法大赛中被证明为最快的进化算法。而且在收敛速度和稳定性 方面都超过了其它几种知名的随机算法。日前，d e 已经在应用到了许多领域。 1 3 1 基本思想 与遗传算法相同d e 的基本操作也包括变异( m u t a t i o n ) 、交叉( c r o s s o v e r ) 和选择( s e l e c t i o n ) 三种操作。不同的是，差分演化算法是先变异后杂交。 1 变异操作 变异策略公式如下： k “1 = 砖+ f x ( 霹霹) 式1 - 1 其中r l 表示种群的规模；个体掣，i = 1 ，2 ，n ，表示父代个体：时“表示 中间个体；a , b 和c 是从【l , h i 中随机产生的不同于i 且互不相同的整数。 变异因子f 是用于控制差分向量( 霹一霹) 的缩放程度。 2 交叉操作 为了保持增强新种群的多样性，d e 算法同样引入了交叉操作。交叉策 略如下： 武汉理工大学硕士学位论文 叫笔k 扪 其c 他r “卢刁 其中m d o 是服从 o ，1 均匀分布；“? “1 m k 。+ l ，甜：k 。+ lk + 1 ) 表示中加个体； z - - r n d ( i ) 是一个在 1 ，2 ，d ) 中的随机选择序列，用它来保证“? + 1 至少从 k “1 获得一个代码( 基因) ；c r o ，1 卜一交叉算子，用来控制交叉代 码的程度。 3 选择操作 向量“，是否成为下一代的个体还要进行一步选择操作。选择操作公式 如下： = 落抓似虢八确 其中厂( 霹) 表示为第k 代第i 个个体的适应值。 堕 应 图1 - 2 d e 算法流程图 与其它的进化算法相比，差分演化算法具有以下主要几个特征： 1 ) 算法通用，不依赖问题信息； 2 ) 算法原理简单，容易实现； 3 ) 算法群体搜索能力强，具有记忆最优解个体的能力； 4 ) 算法具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力。 武汉理工大学硕上学位论文 1 3 2 研究现状 近年来，d e 在各个方面得到广泛的应用。国内外学者对d e 算法的研究取得 良好的效果。 时间 作者算法 提出了一种对于整数变量直接在 1 9 9 9 年 y u n g - c h i e nl i n 整数空间进行优化计算的改进差 分进化算法【3 9 】 用于求解多目标优化问题的 2 0 0 0 年h a a b b a s s 等 p a r e t o 前沿【4 0 4 1 】 国2 0 0 2 年k n a t e r i基于p a r e t o 理念的多目标d e t 4 2 1 外简单的约束处理方法与d e 算法相 2 0 0 2 年j o u n il a m p i n e n 缝厶 4 3 】 ；口口 罚函数法和权值系数差分进化算 2 0 0 3 年b v b a b u 法【删 2 0 0 4 年 k e p a r s o p o u l o s 等 矢量评估差分进化算法【4 5 】 2 0 0 6 年b v b a b u加速收敛速度改进【蛔 国内 2 0 0 6 年 刘建、黄文奇参数动态调整的d e 算法【4 7 】 1 4本文研究内容及主要创新点 1 4 1本文研究内容 我们比较d e 与e d a 的算法发现，d e 算法的这个过程( 1 3 1 ) 并没有涉及 到种群的全局信息，只是在一定的功能上保存了种群的最优解。这使其不能更 好的利用上种群的全局信息；而e d a 算法( 1 2 1 ) 通过统计种群中优秀个体的信 息，使种群的发展按照这个统计的结果去发展。但这样往往忽视了对种群局部 的搜索，使搜索能力下降；而且往往陷入某一局部最优解。 我们比较d e 和e d a 算法 表1 - 2d e 与e d a 的优缺点 武汉理工大学硕士学位论文 差分演化算法分布估计算法 维持父代的多样性统计全局信息 优点利用差异性的计算加强局部算法收敛速度快 的搜索能力 收敛性不稳定易陷入局部最优解 缺点 易陷入局部最优解 通过表1 2 我们发现这2 种算法一种是局部搜索占有优势，一种是全局搜索 占有优势。故这2 种算法的混合可以对算法进行改进，因此本文的研究主要内 容是提出这2 种算法混合模型，并对模型分析验证。 1 4 2 本文主要创新点 本文以d e 和e d a 算法为基础，提出三种混合模型，1 ) 基因混合模型： 如果把每个个体比喻成一个基因链，那么基因链中的基因一部分来自d e 算法、 一部分来自e d a 算法，该模型使个体更加具有多样性；2 ) 个体混合模型：如 果把种群比喻成一个社会，那么社会中的个体一部分来自d e 算法种族，一部分 来自e d a 算法种族，该模型使种群更加具有多元性：3 ) e d a 指导d e 变异方 向：如果把种群比喻成一个团队，那么e d a 根据统计概率生成的临时个体就像 一个领导者去指导种群中的个体按照优秀方向去变异( 搜索) ，该模型使搜索在 全局和局部都有很好的表现。其中前两种模型可以广泛运用到其他许多的混合 算法中去。 1 5 本文的组织结构 论文安排如下：第2 章对本文涉及到的背景知识进行简要介绍。第3 章提出 基于d e 和e d a 的三种混合模型，并对每个模型进行详实的叙述，并分析每个模 型的特点，所涉及参数，给出每个模型的算法框架和伪码表示。第4 章通过典型 的测试函数对第3 章所提出的三种模型去验证分析，同时对比了d e 与e d a 算法， 比较了三种算法优缺点。第5 章对本文工作进行总结，并对进一步工作进行展望。 7 武汉理工大学硕士学位论文 第2 章相关背景知识 2 1 分布估计算法 本文所设计的混合算法的一部分思想就是利用了分布估计算法强化了算法 对全局信息的利用。而在全局信息的利用方面e d a 算法有着天生的优势。分布 估计算法的指导思想就是从全局信息获得的概率模型去指导搜索更好的解决方 案。与传统的g a 不同，e d a s 在生成后代种群时不需要交叉、变异操作，是以 服从根据包含从前代种群中挑选出来的个体的数据集中估计出来的一个概率模 型进行采样新的个体生成下一代种群。以这个概率模型采样可以生成更有价值 的群体和个体。因此，分布估计算法利用每一代种群的群体信息，从中学习概 率模型，然后用学习到的概率模型再生成下一代新的个体，如此循环。 分布估计算可以归纳为下面的基本步骤： 设p o p ( t ) 为第t 代的种群。e d a 提供在以下迭代方式： 步骤1 ：选择。从当前的解决方案p o p ( t ) 中选择m 个有前途的解决方案，形 成遴选方法的父母q ( t ) ； 步骤2 ：模型。建立概率模型p ( t ) 从q ( t ) 的解决方案为基础提取统计资料； 步骤3 ：采样。根据构造概率模型p ( t ) 生成新的解决办法； 步骤4 ：替换。全部或部分取代解决方案在p o p ( t ) ，形成新的种群p o p ( t + 1 ) ； 匡巫匝匦 茎j 丑 遗传算法e d a 算法 图2 1 e d a 算法与遗产算法比较图 武汉理工大学硕士学位论文 2 2 分布估计算法分类 分布估计算法是一种基于概率模型的进化算法，利用概率模型描述变量之间 的相互关系。根据优化问题的复杂性，研究者们设计了很多种不同的概率模型 表示变量之间的关系，形成了多种分布估计算法。 表2 1d e a 算法分类 分类描述代表算法典型模型 离变量无关变量之间相互独立p b i l 算法如图2 2 散双变量相关两个变量之间的依赖关系m i m i c 算法 如图2 3 多变量相关变量之间复杂的依赖关系b o a 算法如图2 4 连变量无关变量之间相互独立g m d c m 公式2 1 续变量相关变量之间相互依赖g m采用高斯分布 翩 一心! ( ? - ) ! ! 吲 吲吲 ( )伊1 吲 一 图2 - 2 向量无关种群 图2 3m m i c 算法向量关系图 图2 4b o a 结构向量关系图 9 武汉理工大学硕上学位论文 2 3变量无关的连续e d a 通过上述的介绍我们以了解了一般的e d a 算法操作和分类。本文研究的是 以变量无关的连续e d a 算法为基础，把d e 与d e a 算法相混合，下面简要介绍 下变量无关的连续e d a 算法。 2 3 1算法概率模型 本文所用的概率模型【8 1 如下： 驰) = 鼻( 怫q ) 其中( 怫q ) = 丽1 z , i u a 刊公船 f 暑l 、，f 其中均值吩标准差q 它们估计玩与喀如下： 霉= 霉= 击姜薯最= i 翮 2 3 2 算法基本操作 s t e p1 ：t - - 0 ，初始化种群，本文采用随机出示化种群；x d 】_ l o w + r a n d 0 ( h i g h l o w ) ； s t e p2 ：根据适应值，选择m 个优秀个体组成临时种群d ； s t e p3 ：根据d 计算均值和方差的估计值； s t q a4 ：由产生的均值和方差的估计值建立概率模型并根据此模型产生中间 种群d ； s t e p5 ：中间种群d 。中个体和父种群d ，中个体比较产生下一代种群d ； s t o p6 ：若终止条件不满足，t - - t + l ，转s t e p2 ) ，否则，停止。 2 3 3算法伪码 初始化种群： f o r ( i = o ；i n ；i ) 根据边界随机生成每个个体 计算每个个体的适应值 l o 武汉理工大学硕士学位论文 ) 生成下一代种群： f o r ( g = 1 ；乎。m a x o e n s ；州 1 、选取m 个最优个体 f o r ( i = 0 ；i m ；i + + ) 选择m 个最优个体 ) 2 、计算均值和方差 f o r ( i = 0 ；i d ；i + + ) u i - o 0 ； e i - 0 0 ： 根据m 个最优个体计算均值u 和方差e ) 3 、根据均值和方差生成中间种群 f o r ( i = 0 ；i n ；i + + ) 根据均值和方差生成新的个体 f o r ( j = 0 j d j + + ) x x i j 】n o r m a l _ r a n d ( u j ，e 团，l o o ) ；生成一个以u 为均值，e 为均方差的正态 随机数，大数取10 0 e n df o r i 与父代个体比较 f o r ( i = 0 ；i n ；i 什) s c o r e - e v a l u a t e ( x x i 0 ，d ) ； i f ( s c o r e = e o s t i ) e o s t i 】 - s c o r e , f o r 0 = 0 ；j d ；j + + ) x 1 【i 】【j 】 - x x i 】d 】； ) e n df o r i e n df o r g 武汉理工大学硕十学位论文 2 4 折中差分演算法算法 本文所设计的混合算法的另外一部分思想就是利用了差分演化算法超强的 局部搜索能力。差分演算法( 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 年由r a i n e r s t o r e 和k e n n e t hp r i c e 所提出，并在1 9 9 6 年首届i e e e 进化算法大赛中被证明为 最快的进化算法中。其基本思想是应用当前种群中个体的差来重组得到中间种 群，然后通过父子之间的选择机制获得新一代种群。其基本方式如1 3 1 所述。 其主要参数有：n 种群规模，d 个体维数，f 变异因子，r c 交叉概率。d e 算法 有多个版本，本文所用的是最好的之一【4 】。其变异策略为： y-y = 当蔓+ f x ( x a 一置+ 五一鼍) 式2 - 2 二 其中局是优于或等于实验向量五的随机向量，五和鼍是不同于和鼍 且互不相同的随机向量。 2 4 1基本框架 s t e p l ：k = - 0 ，设置变异因子f 、交叉概率c r 和停止条件；并随机生成n 个 个体( x , o ，霹，磙) ，记录到数组x 1 ( n x d ) 中； s t 印2 ：对于每个个体群( 1 f a 0 ，执行d e 的算法操作，以产生后代舛“； s t 印3 ：如果给定的停止条件不符合，k = - k + 1 ，转到第2 步；否则停止输出x 1 。 对个体彤用d e 算法生成后代祥+ 1 的方法如下： s t e p l ) ：在数组x 1 中随机的选取一个适应值不小于五的适应值的个体局； s t e p 2 ) ：在【0 , n 一1 】的整数中随机的选取两个不等于d 和i 的数b ，c ； s t e p 3 ) ：生成一个临时解决方案u - - - - ( u l ，“2 ，u d ) ，z _ r o d 0 木d s t e p 3 1 ) 设x + = ( 0 5 - f ) 五+ ( 0 5 + f ) 局+ ，( 五一置) s t e p 3 2 ) 如果r n d 0 c r 或者j 气 “，= z 否则 u ，= ( 群) ， s t e p 4 ) ：如果厂( “) 厂( 舛) ，f + 1 = “；否则，舛”= 霹。 1 2 武汉理工大学硕士学位论文 2 4 2算法伪码 图3 - 1 折中d e 算法流程图 初始化种群： f o r ( i 2 0 ；i n ；i 什) 根据边界随机生成每个个体 计算每个个体的适应值 ) 生成下一代种群： f o r ( g = 1 ；乎。m a x g e n s ；州 武汉理工大学硕士学位论文 f o r ( i = 0 ；i n ；i + + ) ，选个体d 优于实验个体i d od - m do * n ；w h i l e ( e o s t d c o s t i ) ； 不同于个体i 和d 的随机个体b ，c d ob - m do 宰n ；w 1 1 i l e ( b i | l b = 由； d 0c - m do 事n ；w h n e ( c i i i c = = 训c b ) ； z 确保有基因变异 z = r n d0 宰d ； j = o ； w h i l e ( j d ) if ( r n d 0 = c r i ij 一- z ) dii f 一f 幸g k l d 】 j 】- x 1 i 】【j 】+ x 1 【b 】【j 】- x 1 【c 】d 】) ； x 2 i j 】 - ( ( x 1 【i d 】+ x 1 d 】 j 】) 2 + d i 母；省略的对越界的处理 ) r i s e x 2 【i 】d 】 - x 1 【i 】 j ； j + + ； ) f o r ( i = o ；i n ；i + + ) s c o r e - e v a l u a t e ( x 1 i 】，d ) ； i f ( s c o r e = e o s t i ) e o s t i 】 一s c o r e ； f o r 0 = 0 ；j d ；j + + ) x 1 i 】【j 】 - x 1 【i 1 【j 】； ) 2 5 其它的差分演化算法 差分演化算法研究的主要工作之一是对变异策略公式的改进，研究者通过研 究提出了许多模式，为了表示方便，统一采用d e x y z 的形式来描述。 x 表示变异操作中实验向量( 被选中的变异的个体) 的选择方式，其中 r a n d 表示从种群中随机选择的一个个体； b e s t 表示当前种群中适应值最优的个体。 1 4 武汉理工大学硕士学位论文 y 表示用于差分矢量的个数。 z 表示交叉方式，( e x p 表示e x p o n e n t i a l ；b i n 表示b i n o m i a l ) 。 在此列出一些主要模式： 表2 - 2 各种d e 算法变异向量策略 算法模式 变异向量策略公式 概述 r a n d 表示随机选取三佃个体向量x 。g 、 x b g 、x c g ，并通过变异因子( m u t a t i o n w e i g h t i n gf a c t o r ；f ) ，将向量x a g 和 d e 依a n d 1 厂b i n v i ，a + i = x a , g + f 幸( x b ，g x c ，g ) p ( x b g - x ，g ) 进行相加操作，获得合成 向量( d o n o rv e c t o r ) 。此方法是最常兄的 差分演化算法策略。 以d e r a n d 1 为基础，b e s t 表示选取的 式样向量不是随机选取的个体向量 d e b e s t 1 b i i l v i ，g + l = x b c s g + p ( x b ，g - x c g ) x 。g ，而是由当前代的适应值最优个体 x b c s l g 做为实验向量。 以d e r a n d 1 为基础，该策略是在差分 g + l = x 4 g +矢量时多选取一组个体向量x c g - x 。g d e 瓜a n d 2 厂b i n f ( x b ，g - x ，g + x 正g - x , , g )和x b ，g 戈，g 做成合成向量，即由更多向 量取得差异来增加求解的多样性。 以d e r a n d 2 为基础，b e s t 表示选取的 g + l = x b 喊g + 式样向量不是随机选取的个体向量 d e 厂b e s t 2 b i n f ( x b , g - x e ，g + ) ( d ，g - x , ，g ) x 。g ，而是由当前代的适应值最优个体 x b e 盹g 做为实验向量。 d e 瓜a n dt o v l g + i = x l g + 差分矢量是由目前代中的最优个体与 实验个体向量问的差异和一组随机个 b e s t 1 b m f ( ) ( b e s t g 蕊g ) + f ( x b ，g - x c ，g ) 体的差异x b ，g k ，g 相加组合而成。 与d e 瓜a n d 1 厂b i n 相同只是在交 d e r a n d 1 e x p v i g + l = x a ，g + f ( x b ，g + x c ，g ) 叉方式上不同。 与d e b e s t 1 厂b i n 相同只是在交叉 d e b e s t 1 e x pv i ，g + 1 = 咄g + f 事( x b ，g + ) ( c g ) 方式上不同。 v i , g + l = x a , g + 与d e i ia n d 加i l l 相同只是在交 d e r a n d 2 e x p f ( x b ，o - x ，g + x d ，g 戈，g )叉方式上不同。 g + l = 喊g + 与d e b e s t 2 b i n 相同只是在交叉 d e b e s t 2 e x p f ( x b 。g x c ，g + x d g - x , ，g )方式上不同。 d e ，i i a n dt o v l g + l = x l g + 与d e r a n dt ob e s t l b i n 相同 b e s t 1 e x pf ( x b 吼g x i o ) + f ( x b ，g x c ，g ) 只是在交叉方式上不同。 武汉理工大学硕士学位论文 以上各种变异向量策略公式有着各自的特点，但r a