（工程力学专业论文）基于离散变量的差异进化算法研究及其在结构优化设计中的应用.pdf

山束建筑犬掣啊曩士掌位能曙乞 摘要 结构优化设计迄今已有近百年的历史。在最近的四十年内，无论在其理论、算法还是 在应用方面，结构优化设计都取得了很大的进展。而近年来智能算法在结构优化设计领域 的广泛应用，更使得结构优化设计水平达到一个新的高度。 差异进化算法( d i f f e r e n t i a le v o l u t i o n ) 是美国学者s t r o nr 和p r i c ek v 于1 9 9 5 提出的一 种智能算法，具有原理简单、鲁棒性强、收敛速度快、搜索到全局最优解概率高、对初始 值无要求、运行参数设置简单、具有并行运算特性等优点，极具发展潜力。其优秀的性能 已在许多问题的应用中得到了验证。差异进化算法的出现为求解结构优化问题提供了一条 新途径。 本文首先详细介绍了差异进化基本原理，并通过对经典d ej o n g 函数的求解，分析了 控制参数对进化过程的影响，对控制参数如何取值给出了具体建议，同时比较了差异进化 算法五种常用模式的性能。在此基础上对差异进化算法提出如下两点改进：1 对变异因子 提出一种简单的自适应操作，使差异进化算法的主要控制参数由三个减少为两个；2 把基 于双群体的进化改为基于单群体的进化，提高了进化速度。经过改进后的差异进化算法称 为自适应变异差异进化算法( a d a p t i v e m u t a t i o n - d i f f e r e n t i a le v o l u t i o n ，简称a m d e ) ，数值测 试表明，a m d e 在提高进化速度的同时，降低了差异进化算法的使用难度。 其次对约束条件问题和离散变量问题提出了相应的处理方法：将直接比例比较法 ( d c p m ) 与差异进化算法结合成为处理约束优化问蹶的a m d e - - - d c p m 方法；采用计算适 应度的个体与进化个体相分离的方法来处理离散变量和整型变量，即进化个体用连续变 量，计算适应度的个体采用整型变量和离散变量。同时对最优解接近约束边界或约束严格、 可行域小的离散变量优化问题，结合结构优化设计的特点，提出了施加人工个体的处理方 法。 最后，综合上述改进，对包括形状优化层次在内的几个结构优化问题进行了求解。结 果表明，改进的差异进化算法具有极强的全局寻优能力，将其应用于离散变量结构优化设 计是可行且有效的。 关键词：差异进化；离散变量；约束处理；结构优化设计：形状优化 山东奠乜盹大掌习e 士学位饨文 - ，_ _ _ _ _ _ _ h - _ _ - - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ a b s t r a c t t h es t r u c t u r a lo p t i m a ld e s i g nh a sah i s t o r yo fn e a r l yah u n d r e dy e a r e s p e c i a l l yi nt h ep a s t f o r t yy e a r s ，t h ee x t e n s i v e l ya p p l i c a t i o no fa l l k i n d so fi n t e l l i g e n ta l g o r i t h m s ，w h i c hu t i l i z e p r i n c i p l eo fn a t u r a lp h e n o m e n o no ro r g a n i s ma n dh a v et h ea b i l i t yo fs e l f - a d a p t i v ec o n d i t i o n ， m a k et h es t r u c t u r a lo p t i m a ld e s i g nr e a c han e wh i g l ll e v e l d i f f e r e n t i a le v o l u t i o n ( d e ) w a sp r o p o s e db yr a i n e rs t o r ea n dk e n n e t hp r i c ei n1 9 9 5 t h i s m e t h o ds h o w c a s e sm a n ya d v a n t a g e s ：f a s t e r , m o r er o b u s t ，r e q u i r i n gf e wc o n t r o lv a r i a b l e s ，e a s yt o u s e ，w e l lt op a r a l l e lc o m p u t a t i o ne t e i t se x c e l l e n c ep e r f o r m a n c eh a sb e e np r o v e db yal o to f a p p l i c a t i o ni nm a n yd o m a i n sa n dd ep r o v i d e sa n e wa p p r o a c hf o rs o l v i n gp r o b l e m so fs t r u c t u r e o p t i m i z a t i o nd e s i g n t h i sa r t i c l e , f i r s , g i v e su sd e t a i l e di n f o r m a t i o na b o u tt h eb a s i ct h e o r yo f d e a n di tw i l lb e p r e s e n t e dh o w t od e c i d et h ed e k e yp a r a m e t e r sf o rf a s t e re v o l u t i o n a ls p e e dt h r o u g hc l a s s i c a ld e j o n gf u c t i o n s ，a n das i m p l ec o m p a r eo fv a r i a n t so fd e i sg i v e n t h e nt w om e n d si sm a d e 1 ， m u t a t i o nf a c t o rs h o u l db ec o n s t a n t l yc h a n g i n gw i t hs e l f - a d a p t i v eo p e r a t i o ns ot h a tt h ep a r a m e t e r n u m b e ri sr e d u c e df r o mt h r e et ot w o 2 ，i no r d e rt oc o n v e r g i n gf a s t e r , t h ee v o l u t i o nb a s e dt w o p o p u l a t i o n si sc h a n g e di n t o i tb a s e do n ep o p u l a t i o n t h em e n d e dd ei sc a l l e da d a p t i v e m u t a t i o n d i f f e r e n t i a le v o l u t i o n ( a m d e ) s o m et e s t sd e m o n s t r a t et h a tn o to n l ya v i d ei sf a s t e r t h a nd eb u ta l s oe a s i e rt ou s e s e c o n d l y , t h ec o n s t r a i n ta n dd i s c r e t ev a r i a b l eh a n d l i n ga p p r o a c h e si sp r o p o s e df o rd e t h i s a r t i c l eu s ed i r e c tc o m p a r i s o n - - p r o p o r t i o n a lm e t h o dt oh a n d l ec o n s t r a i n t ( a m d e d c p m ) a n d u s em e t h o dt h a tt h ee v o l u t i o n a li n d i v i d u a li sc o n t i n u o u sv a r i a b l ea n dt h ei n d i v i d u a lt oc a l e u l a t e f i t n e s si sd i s c r e t ev a r i a b l et oh a n d l ed i s c r e t ev a r i a b l e m e a n t i m e ，at e c h n i q u eo fi n j e c t i n g a r t i f i c i a li n d i v i d u a li sr e c o m m e n d e df o rs t r i c tc o n s t r a i n t f i n a l l y , s y n t h e s i z i n ga b o v ea m e n d m e n t ，s e v e r a ls t r u c t u r a lo p t i m a id e s i g nq u e s t i o n s i n c l u d i n gs h a p eo p t i m i z a t i o ni sw o r k e do u t t h er e s u l tm a n i f e s tt h a tt h em e n d e dd eh a s p o w e r f u la b i l i t yt oc o n v e r g e n c et og l o b a lm i n i m u ma n di ti sf e a s i b l ea n de f f e c t i v ei ns t r u c t u r a l o p t i m a ld e s i g n k e y w o r d ：d i f f e r e n t i a le v o l u t i o n ，d i s c r e t ev a r i a b l e ，c o n s t r a i n th a n d l i n g ，s l a u c t u m lo p t i m a l d e s i g n ，s h a p eo p t i m i z a t i o n j j 山东建筑工程学院学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得山东建筑工程学院或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名日期： 山东建筑工程学院学位论文使用授权声明 山东建筑工程学院送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复 制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论 文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公 布( 包括刊登) 授权山东建筑工程学院研究生处办理。 研究生签名 导师签名： 日期：z q 盘：q ：6 山赢| 大学瘢士学啦论二 第1 章绪论 1 1 引言 现代结构优化设计理论是结构设计与运筹学交叉的学科，发展迄今有4 0 多年的历史。 传统结构优化设计方法主要包括准则法和数学规划法。总体来说，准则法在求解大规模结 构优化问题的能力强，但求解精度低；虽然数学规划法比准则法求解精度高，但在处理具 有变量数量多、可行域非凸或不连通、i f l 标函数和约束函数非线性高等特点的优化问题时， 具有较大困难，甚至无法求解。随着计算机技术、仿生学、数学、人工智能等学科的飞速 发展，一些借鉴和利用自然界中自然现象或生物体的各种原理和机理的优化算法被相继提 出，克服了传统优化方法在结构优化设计中的一些局限性，取得了良好的效果。这类仿生 算法具有自适应环境的能力，且能够处理实际对象时表现出一定的学习能力，因此又被称 为智能算法。 差异进化算法作为智能算法的一种，是近年来较有竞争力的优化算法之一。因其具有 原理简单、鲁棒性强、搜索到全局最优解概率高、对初始值无要求、运行参数设置简单、 具有并行运算特性等优点，极具发展潜力。差异进化算法的出现为求解结构优化问题提供 了一条新的途径。 1 2 结构优化设计的特点及困难 结构优化设计大体上可分为三个阶科1 1 。第一阶段是建立数学模型，把一个工程结构 的设计问题变成一个数学问题；第二个阶段是选定一个合理的、有效的计算方法；第三个 阶段是编制通用的计算机程序或者开发相应的软件，使同一类型的结构，都可以由计算机 给出最优设计方案。结构优化设计具有如下的特点： ( 1 ) 优化结果的有效性。优化提供的最优解或最优设计只是个相对的最优结构，它 仅仅是在所选用的约束与评价函数下才是最优的。实际结构优化问题往往十分复杂，涉及 各种因素( 环境、荷载、几何特性、材料、施工、费用等) 的制约，因此必须抓住问题的主 要方面和主要矛盾建立数学模型，才能实施优化。因此优化设计的价值与有效性取决于所 用的数学模型与相应的寻优算法，特别与所选用的设计变量，所考虑的约束条件和规定的 目标函数有密切关系。 ( 2 ) 隐性约束问题。结构优化设计的数学模型一般都是带约束优化问题，且约束条件 常为隐式约束，求解时需要做大量的结构重分析工作，计算量很大。 山东建筑犬掌硕士掌位静戈 ( 3 ) 离散变量问题。结构优化设计的设计变量既有连续变量又有离散变量，这给优化 设计带来了很大的困难。离散变量优化问题的基本特点是变量取值的离散性，可行解集在 设计空间中呈散点状分布，即可行域变为可行离散解集。从而数学模型中的目标函数和约 束函数不再具有连续性与可微性，原有连续变量优化中的许多有效的解析算法就无法应 用，如各种梯度型算法：而且离散变量优化的数学模型必然属于非凸规划，使各种对偶算 法在很大程度上失去有效性。解析数学对离散变量优化问题无法胜任，而且在组合数学方 法中离散变量结构优化设计属于n p 困难问题，求解极其困难【2 1 。 ( 4 ) 局部最优解问题。复杂的优化问题可能有多个解，包括有若干个局部最优解，和 一个全局最优解。传统的解析寻优算法只能寻找局部极值而非全局的极值。 ( 5 ) 形状优化及拓扑优化求解困难。结构优化设计主要包括三个层次：杆件截面尺寸 优化、形状优化和拓扑( 布局) 优化。在优化杆件截面尺寸的基础上，形状优化增加了描述 结构几何外形的设计变量( 对杆系结构来说是节点坐标，对连续体结构来说是描述结构边 界形状的控制参数) ，拓扑优化增加了描述组成方式和结构连接方式的设计变量来寻找结 构最优的拓扑形式。杆件截面尺寸变量、描述几何外形的设计变量、描述连接方式的设计 变量三者之间相互耦合，使得模型的建立和优化都极其困难。 通过上述五个结构优化设计的特点、难点可以看出，求解具有约束条件及离散变量的， 具有能精确地反映实际工程的数学模型的结构优化问题，其关键因素在于优化算法。而求 解形状及拓扑层次的优化问题更依赖于优良的算法。 智能算法的发展为求解各类结构优化问题提供了更多的可能性。 1 3 现代智能优化算法 智能算法是一种借鉴和利用自然界中自然现象或生物体的各种原理和机理而开发的 并具有自适应环境能力的计算方法【3 】。智能算法的发展已有较悠久的历史，早期发展起来 的符号主义、联结主义、进化计算、模拟退火法等方法作为经典智能方法的主要研究学派， 至今仍在计算智能领域占据着重要位置，并已取得了丰硕的理论及应用成果。目前智能算 法主要有以遗传算法为代表的进化算法1 4 、以蚁群算法f s 】和粒子群算法f 叼为代表的集群类算 法、以模拟退火法【7 】为代表的基于局部邻域的搜索法、神经元网络、由带有免疫思想的遗 传算法演变而来的免疫算法f 3 】等。尤其是进化计算的发展，使得经典计算智能的研究再度 掀起，使智能算法成为当今的研究热点之一，并己发展为一种多学科、多智能相互交叉， 融合，渗透的信息与计算机研究领域。 山东翼嫩犬掌硕士学位沧文 经典进化算法主要包括2 0 世纪7 0 年代中期的h o l l a n d 提出的遗传算法( g e n e t i c a l g o r i t h m s ，简称g a ) 、6 0 年代德国的r e c h e n b e r g 及s e h w e f e l 提出的进化策略( e v o l u t i o n s t r a t e g i e s ，简称e s ) 及6 0 年代美国的f o g e l 等人提出的进化规划( e v o l u t i o n a r yp r o g r a m m i n g ， 简称e p ) ，而g a 又是这三种算法的代表【4 】，并大量应用于结构优化设计领域里郾，1 0 l 。由 于这三种算法的基本步骤、基本结构相似，因此将此类算法统称为进化算法( e v o l u t i o n a r y a l g o r i t h m s ，简称e a ) i 引。进化算法是模拟生物自然进化机制的一种启发式随机搜索算法， 这种算法以个体构成的群体为状态并具有开发和探测能力的群体学习过程，其由基于群体 的选择、交叉、变异三种操作组成。选择操作反映了物种进化的“适者生存，优胜劣汰” 思想。交叉操作是自然进化的主要机制，反映了个体之间信息交换和信息传递的关系，变 异操作使得群体搜索具有遍历性。选择、交叉、变异分别反映了物种进化过程的特定运行 机制，这三种操作在g a 、e s 及e p 中的重要程度不同。g a 以选择和交叉为主产生多样的 和高适应度个体，变异起到微调群体多样性的作用；e s 及e p 主要通过变异产生多样的个 体，通过选择获得最优秀个体【3 】og a 是以多个个体构成当前状态，搜索过程是个体群进化， 最终获得的状态是由多个优良个体组成。但g a 维持群体多样性及局部搜索能力较弱，搜 索性能与初始群体的分布密切相关，已有结论表明基本遗传算法不是以概率1 收敛的，易 于出现早熟f 3 】0e s 是基于实数编码的保优算法，其主要的操作是确定性的选择操作及高斯 变异策略，突出的优点在于适应度函数可直接选择为优化问题的目标函数，对目标函数较 为光滑的优化问题有较好的效果。e p 是基于实数编码的并行搜索算法，其与g a 的区别在 于e p 的选择为k 联赛选择，突变为高斯变异策略。模拟退火法s a 的思想是m e r t o p o l i s 等在1 9 5 3 年提出的，之后k i r k p a t r i c k 等人于1 9 8 3 年在科学杂志上将其用于组合优化。此 算法属于局部搜索算法，其基本思想是设计初始状态、初始温度及物体冷却的退温函数， 以单个个体作为当前状态，在此状态的邻域中产生新状态，并按m e t r o p o l i s 准则接受稍次 的新状态作为下一状态，最终达到寻优的目的。 目前智能算法的研究呈现出三大趋势：一是对经典智能算法的改进和广泛应用，阻及 对其理论的广泛、深入研究；二是现代智能算法的发展，即开发新的智能工具，拓宽其应 用领域，并对其寻求理论基础；三是经典智能算法与现代智能算法的结合建立混合智能算 法。现今新的智能算法不断涌现，涉及的应用领域不断增多，如优化计算、模式识别、智 能控制、计算机安全、计算机网络、投资组合等等。在这些领域中，优化计算是智能算法 的一个重要的应用领域，求解优化问题的效果是衡量一个智能算法性能的关键指标之一。 山东建筑大掌硕士掌位论文 1 4 差异进化算法研究现状 差异进化算法( d i f f e r e n t i a le v o l u t i o n ，简称d e ) 最初是美国加洲大学伯克利分校的两位 学者k e n n e t hp r i c e 和r a t h e rs t o m 为求解切比雪夫多项式而提出的。1 9 9 5 年3 月，k e n n e t h p r i c e 和r a l n e rs t o r e 发表了第一篇介绍d e 的文章：g d i f f e r e n t i a le v o l u t i o n as i m p l ea n d e f f i c i e n ta d a p t i v es c h e m ef o rg l o b a lo p t i m i z a t i o no v e rc o n t i n u o u ss p a c e s ) 1 1 1 , 1 9 9 6 年6 月 在日本名古屋举行的第一届国际进化算法大赛( f i r s ti n t e r n a t i o n a lc o n t e s to ne v o l u t i o n a r y c o m p u t a t i o n ) 上差异进化算法表现突出获得了第三名，受到各国学者关注。随后r a i n e r s t o r e 在论文 o nt h eu s a g eo f d i f f e r e n t i a le v o l u t i o nf o rf u n c t i o no p t i m i z a t i o n $ 1 3 1 进一步完 善了差异进化算法，d e 开始在各领域中得到应用。 通常认为一个良好的优化算法应该具备下列四个条件【1 4 】： 1 有处理不可微且非线性目标函数的能力。 2 在解决大型优化问题时，为充分利用计算机资源，算法应具有并行运算的能力。 3 易于使用，如只需要通过较少的控制参数就能调节控制优化过程。 4 良好的收敛特性，如在一系列独立的测试中都能收敛到全局最优解。 d e 同其他优秀的优化方法样，基本具备了上述四个条件。d e 采用的是随机方向搜 索的办法，在优化过程中不需要利用目标函数的梯度信息，对函数的非线性程度也不做要 求。同其他进化算法一样，d e 是基于群体的优化算法，当对群体进行扰动产生予群体的 过程中，可以将运算分布到多个计算机或者处理器中去进行，这就具备了并行运算的能力。 d e 的主要控制参数只有三个群体规模、交叉因子和变异因子，d e 的效能对于控制参 数的敏感程度要比遗传算法、模拟退火法等其他智能算法对控制参数的敏感程度低许多， 参数的取值相对简单容易。对于算法的收敛性条件，是优化能否成功的关键，能否收敛到 全局最优解是衡量一个优化算法优劣的重要条件之一。现有文献表明，d e 在参数选取适 当的情况下，收敛到全局最优解的概率是极高的 1 4 , 15 , 1 6 , 1 7 , 1 8 1 。 差异进化算法在诞生的初期就具有各种优良的特性和效能，在许多领域得到了应用。 国外，比较有代表性研究工作的有1 9 9 6 年，r a i n e rs t o r e 运用d e 进行数字滤波电路的参 数设计 1 9 , 2 0 ：在人工智能领域，2 0 0 3 年。j o u n il a m p i n e n 等人提出了基于d e 的多重前向 神经网络方法i 2 1 1 ；2 0 0 4 年m a g o u l a sg d 基于d e 的神经网络在线学习方法；在化工方 面，b vb a b u 等人在1 9 9 9 年使用d e 进行了滴流床反应器中热交换参数的优化田1 ，在2 0 0 1 年对热烈化反应的操作进行优化设计【2 叭，在2 0 0 5 年用改进的d e 对非线性化学反应过程进 行了优化| 2 5 】；2 0 0 3 年，b vb a b u 还运用d e 进行了天然气传输网络的优化设计和污水处 山东建筑大掌萄【士掌位论0 理系统的优化设计 2 6 , 2 7 ；1 9 9 9 年r o g a l s k yt d e r k s e nrw 和k o c a b i y i ks 用d e 对风机叶 片进行了基于空气动力学的形状优化研究阢2 9 l ；2 0 0 6 年，m f a t i h t a s g e t i r e n ，y u n - c h i a l i a n g 等运用d e 处理单机总误工问题 3 0 。作为一种新出现的进化算法，差异进化算法的性能研 究还处于初级阶段，相关文献还较少。2 0 0 5 年，e m e z u r a - m o n t e s ，c a c c o d l o 等 将无参数罚函数罚引入d e 中来处理约束条件，取得了良好的效果j 。2 0 0 3 年，z h a n gw j ， x i ex f 将粒子群箅法与d e 结合提出了d e p s o 方法i 3 2 ，降低了算法对控制参数的敏感层 度，尤其是对整型变量问题有良好的效果。同年，b vb a b u 在d e 算法现有的几种常用模 式基础上，提出了两种新的进化模式n s - 1 和n s - 2 ，文中算例表明这两种新模式具有更强 的鲁棒性和更好的收敛性 3 3 1 。1 9 9 9 年r o g a l s k y , t 将下山法引入d e 中进行局部寻优操作， 提高了优化速度p g 。n a s i m u ln o m a n 和h i t o s h ii b a 提出最佳个体精炼法对d e 进行了改进 在一定程度上提高了d e 处理大规模优化问题的收敛速度【3 4 1 。2 0 0 0 年，j o u n il a m p i n e n 对 d e 在运算过程中发生停滞现象进行了研究，对算法的停滞进行了描述，揭示了停滞现象 的机制，研究了出现停滞现象的原因。给出了减少此现象发生的一些建议1 35 1 。将d e 运用 在多目标优化问题上，也取得了良好的效果f 3 6 ，3 7 3 引。 国内对d e 研究还处于起步阶段，并逐渐成为研究热点。2 0 0 4 年，谢晓锋等对d e 的 性能进行了研究【3 9 j ；方强针对d e 的早熟问题，加入了重布操作和单纯形操作，并应用于 化工模型参数的估计1 4 0 1 ；高飞提出了基于空间收缩的种群灭亡差异进化算法，提高了算法 搜索效率【4 “。2 0 0 5 年，宋立明将d e 运用与三维叶栅气动优化设计f 4 2 1 ；刘明广在d e 中加 入了自适应线性变异和迁徙操作【4 3 】；邹士新将包括d e 在内的几种优化算法在求解浅海匹 配场反演问题的性能进行了比较，文章结果表明d e 的性能最佳：高飞运用改进的d e 计 算离散动力系统不稳定周期轨道问题。2 0 0 6 年，梁才浩以p c 集群为平台做并行计算运行 d e ，求解电力系统无功优化问题1 4 4 1 ，取得了良好效果。 d e 在结构优化设计领域的研究与应用还未见有文献报道，故本文尝试将差异进化算 法这一优良的进化算法应用于结构优化设计，探讨差异进化算法在结构优化设计领域中的 表现。 i 5 研究工作及意义 虽然差异进化算法在诞生之初就具备一些优良的性能，但是作为进化算法的一种，差 异进化算法同样也具有各类进化算法所共有的弱点，如目标函数调用次数多，进化后期收 山东建筑大孽峨士掣啦忱- ： 敛速度慢且对某些问题如当参数选取不当易发生早熟或者进化停滞注，对带有约束条件的 问题的运算效率有待进一步提高等。 本文针对结构优化问题的特点，对d e 进行有目的的改进并应用于结构优化设计。主 要工作有以下几个方面： ( 1 ) 首先通过经典b e n c h m a r k 问题，对d e 的参数取值问题做进一步的研究，并对各种 模式在解决b e n c h m a r k 问题时所表现出的效能进行比较，总结出算法控制参数取值规则及 模式取用建议。 ( 2 ) 在对差异进化算法控制参数对进化过程影响进行了研究基础上，对d e 进行改进， 在不增加控制参数数量的前提下，保证并提高进化速度，进一步弱化算法对参数的敏感程 度。 ( 3 ) 针对离散变量结构优化设计中约束条件的特点，提出适合差异进化算法的约束条 件处理方式。 ( 4 ) 结构优化设计大多都为离散变量与连续变量并存的混合变量优化问题，故研究基 于混合变量差异进化算法的性能。 ( 5 ) 针对一些常见结构形式进行截面和形状两个层次的优化设计，编制相应结构分析 和优化程序。 通过上述工作，拓宽d e 这一优秀进化算法的应用领域，力争为求解结构优化问题提 供又一强有力的工具。 “本文中早熟指进化陷入局部最优解无法眺出 进化停滞拯虽宋陷入局部最优解。但仍长时间停止进化。 6 山裹建筑大掣“葭士群啦论文 第2 章差异进化算法的基本原理及其改进 差异进化算法同其他进化算法的基本原理类似，都是借鉴生物界自然选择和自然遗传 机理的随机化搜索过程，其综合了适者生存和遗传信息之间的结构性和随机性的生物进化 特点。差异进化算法尽管具有一些随机性，但它并不是一种简单的随机搜索方法。它充分 利用历经的信息来确定新的更好的搜索点。本章首先介绍差异进化算法的基本原理弗探讨 控制参数如何取值才能获得较快的进化速度，然后针对差异进化算法提出两点改进，并通 过一些b e n c h m a r k 经典测试函数验证改进的效果。 2 1 标准差异进化算法 差异进化算法是采用实数编码的进化算法。其基本思想是将优化问题的解向量作为进 化的基本个体，用随机方法产生若干个解个体组成解群体，在群体中通过对个体旋加个体 间的加权差异而产生新的个体和群体，从而来达到进化的目的。 2 1 1 差异进化算法基本原理 差异进化算法与其他一些进化算法的基本步骤基本一致，主要包括编码、变异、交叉 和选择等操作。下面通过求解非线性函数： f ) = ，b ，x ，吒) ( x ，x ：，= 1 , 2 ，胛) ( 2 1 ) 的最小值问题来叙述差异进化算法的基本原理。 2 1 1 1 形成初始群 差异进化算法的编码非常简单，直接将优化问题的解x ，x ：，组成解r 甸t t ： z f g = 扛l ，x 2 ，x 。) i = 1 , 2 ，p ( 2 - 2 ) 每个解向量就是进化的基本个体。群体进化的每一代表示为g ，表示个体在群体中 的位置，p 表示群体的规模。群规模p 为差异进化算法的主要控制参数之一，一定规模 的群体是保证个体具有足够的多样性，以便使进化得以进行的必要条件。但是过大规模的 群体会使目标函数调用次数过多。内存用量增大。用随机的方法产生第一代群： x 。x ；+ 一( z ；x ；)f = l ，2 ，p ( 2 _ 3 1 其中r 删。为【o ，1 】之间的平均随机数，x ；和z 分别为第，个变量取值范围的下界和上 界。通常情况下，随机产生的第一代群体应能均匀分布在解空间中，保证第一代个体的多 样性。 山东建筑大掌；啊士掌位论文 2 1 1 2 变异操作( m u t a t i o n ) 变异操作是差异进化算法产生子个体的基本方式。通过将在父个体中施加群体中两个 或者多个个体之间的特征差异的办法来产生子个体。这样就把父代群体所具有的进化信息 进行了改变并传给了子代群体。变异操作的基本单位是个体，即解向量。 对于每一代进化目标向量彳。，i = 1 , 2 ， 驴，其变异操作如下： 一g + 1 = x n d + f ，2 g x ，3 盯) ( 2 4 ) 图2 1 显示了一个二维函数的变异过程。其中r l ，r 2 ，r 3 为【1 ，2 ，p 】中互不相等的 任意整数，且不等于i 。x 。称为父个体或者基个体。f 为变异因子，是差异进化的主要 控制参数之一，在( 0 ，2 ) 中取值【l l 】，但在随后的研究中发现在( 0 ，1 ) 之间效果较好【h 1 。这 是基本的变异模式，被称做d e ，m n 彬1 模式。除了上述基本进化模式外，差异进化算法还 有其他变化形式。r a i n e rs t o r n 使用下面的表达式来定义各种差异进化模式【1 4 j ： d e i x y z x 表示在变异操作时，是随机( r a n d 选取当前代中某一个体作为父个体还是选择当前代 中最优( b e s t ) 个体作为父个体；y 表示在变异操作时，所使用差异向量的个数：z 表示交叉 模式，有= 项式模式( b i n ) ，指数模式( e x p ) ，后面会介绍交叉模式的相关问题。差异进化算 法变异操作有如下五种常用模式： d e 6 e s f 1 ： 。= k 。+ f c ：。一爿? ，。) ( 2 5 ) d e m 册1o k m 。= x r + f ：。一墨3 g ) ( 2 6 ) d e i b e s t 2 ： k m ，= x 。+ f 一x ，：口+ z ，。一墨。) ( 2 7 ) d e 序册d 陀： 。+ ，= x r ，“+ f u ，r ：口一墨，d + t g z ，。)( 2 - 8 ) d e ，r a n d - t o b e s t 2 ： g i , g + = x 。十f 。一x ，+ x ，2 。一x 。) ( 2 9 ) 其中。为当前代最优个体x ，l x ，：，x 。x ，以，( r z r 2 r 3 r 4 r 5 i ) 为随机选择的个体。 山东嗣臼盹大掌硕士掌位能i 丈 图2 - 1 二：维函数变异过程 2 1 1 3 交叉操作( c r o s s o v e r ) 交叉操作是为了增加群体的多样性。恰当的交叉操作可以有效的提高全局寻优能力， 使进化跳出局部最优点，避免发生早熟。交叉操作有两种模式，分别为指数交叉模式( e x p ) 和二项式交叉模式( b i n ) 。交叉操作的基本单位是个体的基因，即解向量中的元素。 指数交叉模式具体操作如下： 。麓 ，= ( 棚) 。，( r a n d n + 1 ) 。 j ( r a n d n ) d ( r a n d n + 1 ) d ，( r a n d n + d n ，( 瑚砌+ 三( 2 - 1 0 ) 符号( ) 。代表对d 取余。r a n d n 为在区间【1 ，d ) 中随机选取的整数，决定交叉操作时起 始变量的位置。整数代表将要参加交叉操作的变量个数，取值范围为 1 ，d 】。l 的取值概 率为：n 0 v ) = ( c 只) ”，v 0 。交叉因子c r 【0 ，1 】为交叉概率，是主要控制参数之一，其 值在优化过程中保持不变。在每产生一个新的试验个体“。+ 时都需要对r a n d n 和上重新取 值。 二项式交叉模式具体操作如下： i f ( r a n d b ( ，j ) ) j ) 。 r a n d b ( j ) 为 o ，l 】之间的随机小数， r n b r ( i ) 为【1 ，n 】之间的随机整数，c 足为交叉因 9 + 灯 盯b ，j【 = + g 甜 山东爿嫩大学硕士掌位忱- 文 子。二项式交叉过程如图2 - 2 所示。 x j 。g v l 。g + 1 j _ 1 2 3 4 5 6 7 j 篁1 2 3 4 5 6 7 u i g + l 震 l j 鲁1 霆 2 n t n d b ( 3 ) = c r 、 8 v ， 黧r l n d b ( 4 ) , , c rj 。 l 一 霪 5 r b n 曲) - cr盎k 鬟l v r 霪 7 图2 - 2 多项式交叉模式示例 这两种交叉策略可确保“盯+ 至少有一分量由”肺+ 1 的相应分量贡献。现有文献表明， 两种交叉模式的效能基本相同，且相对来说二项式交叉模式使用起来更为简捷方便，易于 在编程中实现，故现今对差异进化算法的研究与应用绝大部分都采用二项式交叉模式，本 文的研究也采用二项式交叉模式。 2 1 1 4 适应度计算 差异进化算法采用实数编码，所以直接将目标函数作为适应度值即可。如果是求极大 值问题。可将目标函数整体取负，即为极小值问题。 2 1 1 5 选择操作( s e l e c t i o n ) 由交叉操作所产生试验向量u 。和目标向量置。代入目标函数进行比较，如果试验向 量u ，。+ 的目标函数值小于目标向量一。的目标函数值，那么目标向量墨。被u j 。+ 替代；反 之，z 。将被保留。由此形成下一代解群。 反复进行变异，交叉，适应度计算，选择等操作，直至进化满足终止条件。终止条件 为达到人工给定的最大进化代数，或者目标函数小于某个给定值。 2 1 2 差异进化算法主要控制参数取值分析 差异进化算法的主要控制参数有三个：种群规模p ) ，变异因子( d ，交叉因子( c r ) 。 但是参数的选择对进化速度有一定影响，且参数选取不当会出现进化停滞和早熟现象。本 文通过对四个b e n c h m a r k 函数最小值问题1 4 5 】进行数值分析，着重研究变异因子和交叉因子 1 0 山东e j 宅大掌壕士学位论文 对进化过程的共同影响，总结控制参数与进化过程之问的关系。 2 】2 1 d e 1 0 n g 提出的五个b e n c h m a r k 函数最小值问题 d ej o n g 根据函数优化相关的各种特性，精心挑选了五种b e n c h m a r k 函数最优化的测 试例子。这五个函数在计算机上经过大量的计算实践，已成为进化算法研究和发展的典范 f 4 5 j 。现取其中的四种进行研究“。 ( 1 ) s p h e r e 函数 3 0 鼻= 工? 一5 t 2 s _ 5 1 2 仁l 为简单的平方求和函数，具有光滑，单峰，对称的性质。函数图像见图2 3 。其最优 状态和最优值为： r a i n ( f 伍+ ) ) = 只( o ，o ，o ) = 0 近似目标函数最优值定为1 0 x1 0 。4 。 刚2 - 3 函数f ：的三维图像 ( 2 ) r o s e n b r o c k sv a ll e y 函数 e = 1 0 0 g ? x 2 r + ( 1 一x 1 ) 22 0 4 8 x ，蔓2 0 4 8 是经典的优化函数。其全局最优解在一个狭长的，类似抛物线曲面状的“峡谷”里。 函数图像见图2 4 。找到这个“峡谷”很容易，但收敛到全局最优解非困难，因此这个问 题经常被用来测试优化算法。其最优状态和最优值为： m i n ( f 2 扛) ) = 忍( 1 ，1 ) = 0 “1 被舍去的函数为含有随机值的噪声函数。闻本文所研究的结构优化设计问题不含肯随机值，故小对此函数作研究 1 l 山东建筑夫掌司| - 目q 止倒嚏 近似目标函数最优值定为1 o xl o 。 ( 3 ) s t e p 函数 图2 4 函数e 的三维图像 3 0 巧= i n t e g e r ( x ，) - 5 1 2 蔓t 5 1 2 是不连续函数，由变量取整后求和得到，在三十维窄问中有一个极小值。函数图像见图2 - 5 。 最优状态和最优值为： m 加以 + ) ) = f ，( - 5 一卢，一5 一，一5 一p ) - - 一1 5 0 ，f o ，0 ，1 2 】 ( 4 ) s h e k e l sf o x h o l e s 函数 图2 - 5 函数只的三维图像 山东奠躐犬掌司l 士掣啦谴文 e =o o 舵+ 艺 ”1 ，+ 善b q ) 一6 5 5 3 6 x s6 5 5 3 6 ( 口，) = 。- 一。3 2 2 ，, 一- ，1 ：6 ，, 一兰，三6 ，一耋一瑟，j 3 荔：； 是多峰函数，具有2 5 个局部最小值。函数图像见图2 - 6 。其最优状态和最优值为 m 抽亿伍) ) = f ( - 3 2 ，一3 2 ) 0 9 9 8 0 0 3 8 3 9 目标函数近似最优值定为0 9 9 8 0 0 4 。 图2 - 6 函数只的三维图像 2 1 2 2 参数分析方式 下面分别对五种变异模式进行测试，交叉模式均采用二项式模式。种群规模n p 统一 定为变量个数的1 0 倍。对每个测试函数，交叉因子c r 由0 1 变化至0 9 ，每次变化0 1 ： 同时针对每一个c r 值，变异因子，同样由o 1 变化至0 9 ，变化步长也为0 1 。观察比较 测试函数在在不同c r 值下，最先到达最优解的f 值和进化代数。函数的最优值假定为上 述近似最优函数值。最大进化代数根据各个测试函数情况而定。 本文程序采用f o r t r a n 9 0 语言编制，在c o m p a qv i s u a lf o r t r a n6 5 平台运行。算法中所 有的随机数均由f o r t r a n 语言中的伪随机数生成函数“r a n d o m )”产生。以下测_number( 试及本论文研究所需的随机数均由此函数产生。 2 1 2 3 测试结果 表2 i 一表2 5 列出了四个测试函数在不同c r 值下，前两位最先到达最优目标函数值 3 山