（计算机软件与理论专业论文）改进的差分进化算法在异步电机优化设计中的应用.pdf

改进的差分进化算法在异步电机优化设计中的应用 摘要 论文题目： 专 业： 硕士生： 指导教师： 改进的差分进化算法在异步电机优化设计中的应用 计算机软件与理论 樊孟周 成良玉教授 摘要 异步电机因其结构简单、质量较小、运行可靠和维护方便等特点，在家用电 器和工业领域得到了广泛的应用。对电机各项性能指标的优化成为多年来研究的 一项重要课题。电机的优化设计是指从预定目标出发，在满足约束的前提下，根 据电机的数学模型，并借助最优化方法来得出最优的电机设计方案。 本文通过对电机设计理论和进化算法的研究，提出了用一种全局随机优化方 法，差分进化算法，来解决电机的多目标优化设计问题。首先，依据电机的等效 环路模型，结合电机优化的目标、约束函数以及优化设计变量建立了相应的数学 模型。然后针对电机优化的数学模型对经典的差分进化算法进行若干改进以适用 于求解多目标优化问题：1 ) 引入了外部存档，对拥挤策略进行改进。通过引入 外部存档机制，一方面保留了在整个进化搜索过程中得到的非劣解，另一方面还 可以使得这些最优解在选择、变异操作中指导进化搜索的方向。同时，对已有的 拥挤策略进行改进，以更好的保持群体解的多样性；2 ) 改进的变异算子。在进 化的初期选取了有利于加大全局的搜索的策略，当种群迭代到一定的程度，则变 换为局部搜索的策略，从外部存档中选取当前最优解来指导变异的方向，加快收 敛速度；3 ) 改进的选择算子。在选择过程中，引入了“二次比较”的选择策略， 当试验向量劣于相应的目标向量时，并不让其直接淘汰，而是随机选取一个候选 集，再次与试验向量进行比较，加大试验向量存活的机会，并加速了当前种群的 进化。最后，在基于微软n e t 的平台上编制出了更具交互性的电机校核设计软 件，并根据改进的差分进化算法实现了电机的优化设计程序。实验表明，改进的 差分进化算法与原有的优化设计方案相比，能够表现出更优的性能。 关键词：多目标优化、差分进化算法、异步电机设计 改进的差分进化算法在异步电机优化设计中的应用 a b s t r a c t t i t l e ： a p p l i c a t i o no fi m p r o v e dd i f f e r e n t i a le v o l u t i o na 1 9 0 r i t h mf o r m a j o r ： n a m e ： o p t i m u md e s i g no fi n d u c t i o nm o t o r c o m p u t e rs o f t w a r ea n dt h e o r y m e n g z h o uf a n s u p e r v is o r ：p r o f l i a n g y uc h e n a b s t r a c t i n d u c t i o nm o t o rh a saw i d er a n g eo fa p p l i c a t i o n si nh o m ea p p l i a n c e sa n d i n d u s t r i a lf i e l d s o v e rt h ey e a r s ，t h es t u d yo fv a r i o u sp e r f o r m a n c ei n d i c a t o r so fm o t o r o p t i m i z a t i o nb e c o m e sa ni m p o r t a n tt o p i ci nt h em o t o ro p t i m u md e s i g n o p t i m a l d e s i g no f m o t o r i ss t a r t e df r o mt h ei n t e n d e dt a r g e t ，t h e nf i n dt h eo p t i m a ld e s i g no f t h e m o t o r 、i t ht h ec o n s t r a i n t so fr e l e v a n tf u n c t i o n sa c c o r d i n gt ot h em o t o rm a t h e m a t i c a l m o d e l b a s e do nt h er e s e a r c ho ft h ee l e c t r i c a ld e s i g nt h e o r ya n de v o l u t i o n a r ya l g o r i t h m , w ep r o p o s e dag l o b a ls t o c h a s t i co p t i m i z a t i o nm e t h o 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 m , t os o l v et h ee l e c t r i c a ld e s i g no ft h em u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m f i r s to fa l l ， b a s e do nt h ee q u i v a l e n tc u r r e n tm o d e lo fm o t o r , w ee s t a b l i s hm a t h e m a t i c a lm o d e lo f t h ei n d u c t i o nm o t o rw i t ht h ec o m b i n a t i o no fo b j e c t i v e s ，b i n d i n gf u n c t i o n , a sw e l la s t h ed e s i g nv a r i a b l e so ft h ee l e c t r i c a lm a c h i n e a n dt h e n , f o rt h eo p t i m i z e dm o t o r m a t h e m a t i c a lm o d e l ，w ei m p r o v et h ec l a s s i cd 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 d a p p l yi tt os o l v em u l t i - o b j e c t i v eo p t i m i z a t i o np r o b l e m ：1 ，e x t e r n a la r c h i v ea n dt h e s t r a t e g yo fi m p r o v e dc o n g e s t i o n t h r o u g ht h ei n t r o d u c t i o no fa ne x t e m a la r c h i v i n g m e c h a n i s m , o nt h eo n eh a n d ，w ec a nr e t a i nn o n - i n f e r i o rs o l u t i o nd u r i n gt h es e a r c hi n t h ew h o l ep r o c e s so fe v o l u t i o n ；o nt h eo t h e rh a n d ，w ec a na l s om a k et h e s et og u i d e m u t a t i o no p e r a t i o ni nt h ec h o i c eo ft h eo p t i m a ls o l u t i o n ；2 ，t h ei m p r o v e dm u t a t i o n o p e r m o r i nt h ee a r l ys t a g e so fe v o l u t i o n ，w es e l e c tt h es t r a t e g yt h a tc a nf a v o rt h e g l o b a ls e a r c h ，w h e nt h ep o p u l a t i o ng e n e r a t i o nr e a c hac e r t a i nd e g r e eo fi t e r a t i o n , i ti s t r a n s f o r m e di n t ot h el o c a ls e a r c hs t r a t e g y , a n ds e l e c tt h eo p t i m a ls ol u t i o nf r o mt h e i i 改进的差分进化算法在异步电机优化设计中的应用 a b s t r a c t e x t e r n a la r c h i v et og u i d et h ed i r e c t i o na n ds p e e du pc o n v e r g e n c es p e e d ；3 ，t h e i m p r o v e ds e l e c t i o no p e r a t o r i nt h es e l e c t i o np r o c e s s ，w ei n t r o d u c ea ”s e c o n dc h o i c e ” s t r a t e g y , w h e nt h et r i a lv e c t o ri n f e r i o rt h ec o r r e s p o n d i n gt h et a r g e tv e c t o r , i td o e sn o t d i r e c t l yb ea b a n d o n e d ，b u tr a n d o m l ys e l e c tac a n d i d a t es e t ，t h e nt h et r i a lv e c t o rw i l l b ec o m p a r e da g a i nw i t ht h es o l u t i o nf r o mt h ec a n d i d a t es e t t h i sm e t h o di m p r o v e st h e r a t eo ft h es u r v i v a lo ft h et r i a lv e c t o r , a tt h es a m et i m et oa c c e l e r a t et h ee v o l u t i o no f t h ec u r r e n tp o p u l a t i o n f i n a l l y , b a s e do nt h em i c r o s o t t n e tp l a t f o r mw ed e v e l o p e d d e s i g ns o f t w a r eo fi n d u c t i o nm o t o r , a n di na c c o r d a n c ew i t ht h ei m p r o v e dd 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 mt oo p t i m i z et h em o t o rd e s i g np r o c e s s i ti sp r o v e dt h a tt h e i m p r o v 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 mc a no u t p e r f o r mt h ei n i t i a ld e s i g ns o l u t i o n k e yw o r d s ：m u l t i o b j e c t i v eo p t i m u m ，d i f f e r e n t i a le v o l u t i o n a r y , i n d u c t i o nm o t o r d e s i g n i i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 超盂， 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：炎互扒 导师签名： 日期砷年够月2 胡 慨如卞 1 4 。瓦汨众咿 改进的差分进化算法在异步电机优化设计中的应用第1 章绪论 第1 章绪论 1 1 课题的研究背景和意义 随着国民经济的发展，异步电机被广泛的应用在家用电器，农业生产，驱动 机床，医疗设备以及风力发电等各个领域。异步电机与其它类型的电机相比具有 结构简单，生产成本较低，质量较小，运行和维护方便等优点，因此异步电机在 国内外都有着更为广泛的应用。对异步电机的设计尤其是优化设计逐渐成为工程 数学，电机设计理论，计算机科学等众多领域的一个理论研究热点。近年来电机 优化设计的方法，呈现出以下一些发展趋势2 】： 1 ) 以寻求全局最优解为目标。对于电机优化设而言，寻求全局最优点是工 程技术人员普遍关心和研究的领域。由于智能算法在优化问题中表现出较强的全 局搜索能力，因此人们越来越多依赖于遗传算法等高级算法来进行全局解域的并 行搜索，同时和传统的数学规划方法相结合形成混合算法以加强局域搜索能力。 2 ) 以多目标优化为目标。电机优化设计中的各个性能指标往往是相互冲突 的。如电机效率和有效成本，电机效率的提高通常以牺牲有效成本为代价。这就 要求对现有的优化方法进行改进以解决多目标优化的问题。但是对于多目标优化 问题本身，特别是有关收敛性和多样性保持的理论还不是十分成熟，因此还有待 于进一步的探索和研究。 3 ) 结合新的电机设计方法，提高优化设计方案的有效性和精度。在电机优 化设计中，除了满足各项性能指标得到优化以外，还必须保证设计变量本身的精 度和有效性。目前，可以借助有限元分析软件( a n s y s ) 对得到的优化设计方 案进行有效性分析和改进。 中山大学电气与工程软件研究中心多年来一直致力于异步电机优化设计的 课题研究和软件开发工作。虽然早期开发的基于d o s 平台的电机优化软件已经 在部分电机制造厂商中得到了推广和应用，但是随着市场经济的发展和新的软件 设计需求的不断提出，早期的软件版本和开发技术已经很难适应市场和用户的需 求。总结早期电机设计软件版本的特点主要存在以下两点不足之处： 改进的差分进化算法在异步电机优化设计中的应用 第1 章绪论 1 ) 该设计软件借助于传统数学规划理论，通过在满足约束的条件下优化目 标函数有关的设计变量来达到提高电机性能的目的。但是电机优化设计具有很高 的复杂性，对于传统的数学规划方法，极易收敛到局部的最优解。而且电机优化 的各个性能指标往往是相互冲突的，早期的设计软件在优化过程中仅针对某个性 能指标的优化问题而忽略了使得多个目标同时达到最优的过程。 2 ) 软件扩展性差和缺乏交互性。由于电机优化问题的复杂性，且在软件开 发过程中没有对软件本身进行很好的模块划分，导致当新的设计需求提出的时候 对原有界面和程序的改动都出现一定的困难。加以当时计算机技术的限制，软件 界面的交互是在d o s 环境下进行的，这对设计人员的使用也造成了很多不方便 之处。 鉴于以上存在的问题，本课题在基于新的软件开发技术和优化方法的基础 上，对原有的电机优化设计软件进行改进和版本的升级。改进的异步电机优化设 计软件将具备以下一些新的特点： 1 ) 在软件开发方面，改进的电机优化软件将在n e t 平台的基础上，采用面 向对象的思想和现代软件工程的方法。对电机的优化逻辑进行良好的模块划分和 数据的封装。软件界面的设计也体现出友好的人机交互的特点，并通过水晶报表 和e x c e l 表格等形式来显示和保存优化设计的最终方案，以便工程设计人员分析、 查询。 2 ) 在算法优化方面，针对传统数学规划方法存在的不足之处，通过引入改 进的差分进化算法来解决电机设计的多目标优化问题。相对于其它智能进化算法 而言，差分进化算法结构简单，无需编码和解码的操作，而且具有全局并行搜索 的能力，健壮性和鲁棒性强。因此，可以对差分进化算法进行适当的改进来解决 电机优化问题，以期达到全局的p a r e t o 最优解。 1 2 论文的主要工作和内容 本文主要工作是对差分进化算法进行若干改进来解决电机优化设计中的多 目标优化问题，最后给出改进程序的软件实现和比较结果分析。 论文的主要内容安排如下： 第1 章为绪沦部分。介绍本课题的研究背景、意义以及论文的主要工作、相 2 改进的差分进化算法在异步电机优化设计中的应用第1 章绪论 关的内容安排。 第2 章介绍多目标优化问题和进化算法的一些概念和关键理论。为电机数学 模型的建立和优化方法的改进打下理论基础。 第3 章首先根据电机的等效环路公式给出了电机优化的数学模型，然后介绍 了差分进化算法的基本原理，最后结合电机多目标优化的特点分别对差分进化算 法的变异、选择机制进行改进，并引入了外部存档和改进的拥挤策略来指导变异、 选择的方向，保持进化过程中种群解的多样性。 第4 章分别给出了异步电机校核设计和电机优化设计程序的实现。在电机优 化设计程序中，以朔风电机的优化程序为例，并结合了改进的差分进化算法进行 优化实验。从优化的结果来看，改进的算法在搜索最优解的性能上要优于原有的 优化设计方案。 第5 章对全文的工作进行总结并就当前研究中的不足之处提出进一步的研 究方向。 改进的差分进化算法在异步电机优化设计中的应用第2 章多目标进化算法的相关理论 第2 章多目标进化算法的相关理论 2 1 多目标进化算法简介 在实际工程应用中，经常遇到需要使得多个目标在给定可行区域尽可能同时 取得最优的优化问题，而这些目标有可能是相互冲突的。例如在电机优化中，既 要考虑到电机的运转效率和启动转矩尽可能的达到最大，又要降低电机的有效成 本，同时还要兼顾到产品的可制造性，可靠性和实用性等。这里最优的概念并不 是指搜索的目标仅仅找到单个最优解，而是获得一个最优解的集合，在这个集中 各个解方案是不可比较的( 非劣解) ，最终选取哪个合适的解方案可能由决策者 根据问题的背景进行综合考虑。 长期以来，运筹学家一直致力于多目标优化问题的研究与探索工作，并产生 很多重要的技术来解决多目标问题。其理论和方法在金融工程、城市规划、对策 论、军事科学等领域有着广发的应用。传统的多目标优化方法多是将各个子目标 聚合成一个带正系数的单目标函数，然后转化为求单目标函数极值的问题，其中 系数可以根据问题的背景加以确定。解决多目标问题的这类方法有：线性加权法、 约束法、目标规划法和极大极小法等。这些解决方法虽然继承了以往求解单目标 问题的一些成熟算法的机理，但对于高维复杂问题，这些多目标优化方法很少能 被真正使用。究其原因，这些方法主要存在一些局限性：1 ) 传统优化方法如加 权法在求解多目标问题时，由于依赖对背景知识的理解其权重系数有时难以确 定，而且对最终的求解方案容易造成重要的影响，从解的效果来看，此类方法只 能得到局部极优值，且易受随机干扰的影响；2 ) 这些方法存在的一个共同缺陷 就是为获得最优解的集合必须进行多次优化迭代，由于各次优化过程相互独立， 往往得到的结果很不一致，从而令决策者很难进行有效的决策。 近年来，进化算法( e v o l u t i o n a r ya l g o r i t h m s ，e a s ) 以其并行搜索问题空间的能 力以及在单轮优化期间可以产生多个均衡解，对目标函数的连续性、非凸性不敏 感等特点，非常适合求解多目标优化问题。进化算法代表了一类模拟自然进化过 程的随机化优化方法，它是一种新兴的全局搜索寻优技术。e a s 的起源最早追溯 4 改进的差分进化算法在异步电机优化设计中的应用第2 章多目标进化算法的相关理论 到2 0 世纪5 0 年代末。在1 9 6 7 年，r o s e n b e r g 在其博士论文【3 】中提到可以采用遗 传搜索的方式来求解多目标的优化问题，暗示出进化算法在解决多目标问题的潜 力。随后的几十年，虽然多目标进化算法没有被进一步的探索，但是各个相关学 科都对多目标问题产生浓厚的兴趣，这一时期也发表了很多与多目标问题有关的 文章。在1 9 8 5 年，s h a f f e r 提出了多目标进化算法( m u l t i - o b j e c t i v ee v o l u t i o n a l g o r i t h m s ，m o e a s ) ，开创了用进化算法求解多目标问题的先河，但是m o e a s 算法在本质上仍然采用了加权和的方式。之后相继出现了很多种类型多目标进化 算法。这些进化方法根据生物学中遗传与进化的原理，遵循达尔文提出的“物竞 天择，适者生存 的选择机制，针对一组候选的解方案进行操作。简单的讲，这 组解根据选择和变种两种基本方式进行不断改良，选择过程是从已有的个体集合 里挑选出优胜者进行复制，变种过程则是通过重新组合( 交叉) 和变异形式来模 拟自然进化过程产生出新的个体。 虽然进化算法的机制简单，但它们的通用性和鲁棒性好，搜索能力强。不仅 能很好的解决古典运筹学所能处理的多目标优化问题，而且还可以处理不可微、 非连续、多维、带有约束性质的复杂优化问题。进化算法是生物科学与工程技术 相结合的一门边缘学科，目前已成为继专家系统、人工神经网络之后有关人工智 能的第三个研究热点1 4 。多目标进化算法的应用领域主要包括工程设计、工业控 制、环保学、金融学、经济学、几何学、物理学、信息以及资源管理等【5 j 。 2 2 多目标进化算法的基本概念 首先，可以对多目标优化问题( 也可以描述为多准则优化、多性能优化或者 向量优化问题) 做出如下概括【6 j ： 寻找一组由决策变量组成的向量取值使其既能满足问题给定的约束条件又 能使总目标函数达到最优化，其中组成总目标函数的元素是子目标函数。这些子 目标函数构成性能评价标准的数学描述，这类性能指标一般是相互冲突的。因此， 这里“优化”的概念实际上是指寻找一个解，使得对于决策者而言所有的子目标 函数的性能指标都是可以接受的较好解方案。 下面给出多目标优化问题的数学描述【_ 7 】： 5 改进的差分进化算法在异步电机优化设计中的应用 第2 章多目标进化算法的相关理论 一般m o p 由n 个决策变量参数、m 个目标函数和，个约束条件组成，目标 函数、约束条件与决策变量之间是函数关系。最优化目标如下： m a x i m i z ey = f 【x ) = ( z ( x ) ，五( x ) ，厶( x ) ) ( 2 - 1 ) s u b j e c t t og ( x ) = ( g l ( x ) ，9 2 ( x ) ，劭( x ) ) o 其中，x i ( 五，x 2 ，吒) x ；y 2 ( m ，奶，虼) y 。 不失一般性，把目标函数描述为极大化的形式，约束函数g ( x ) 描述为小于等 于零的形式，其它形式的目标函数( 极小化) 和约束函数( 大于等于零) 都可以 转化为这两种情况。x 表示决策向量，y 表示目标向量，x 表示决策向量x 形成 的决策空间，y 表示目标向量y 形成的目标空间，约束条件g ( x ) 确定决策向量的 可行取值范围。 一般，多目标优化问题的目标函数具有线性或者非线性性质，而优化的过程 就是将决策向量x 映射到目标向量y 。在m o p 问题中，很少存在单个解个体能 够同时优化所有的目标函数，因为在大多数情况下各子目标可能是相互冲突的， 某个子目标的改善可能引起其它子目标性能的降低，即同时使多个子目标均达到 最优往往是不可能的，我们并不将这种情况归为多目标优化问题研究的范畴。因 此，在解决多目标优化问题时，一般是找到使各个子目标达到均衡或者折衷处理 的解，使各子目标函数尽可能地达到最优。因此，多目标问题的最优解和单目标 问题的最优解有着本质的区别。 在多目标优化问题的数学模型中，把满足约束条件的解的集合称作可行解 集。该可行解集的物理意义表示把所有的决策向量x 经过函数的优化搜索映射到 目标空间的一个子空间当中。在该子空间中所有的决策向量均属于可行的。例如， 电机优化设计中，把需要满足的国家标准和企业标准可以转换为相应的约束函数 g ( x ) 来表示，相应的优化目标- 有效成本和运转效率可以表示为函数石和六。则 该目标函数所对应的可行解集为满足其约束函数g ( x ) 小于等于( 或大于等于) 给 定约束值的决策向量的集合。因此，优化的目的就是在满足相应的约束条件下， 即在可行解集内，使得最小化活性成本和最大化运转效率。 多目标优化问题在其可行集合中往往不能直接判断出各个解方案的优劣性， 因为在可行域中f 1 标函数不是全序关系：一个解要么比另一个解好，要么比它差。 6 改进的差分进化算法在异步电机优化设计中的应用第2 章多目标进化算法的相关理论 当我们要同时优化所有的子目标时，在搜索空间内仅是部分有序，即任何两个解 方案可能是不可比较的。例如在电机优化的解集中，一个解方案与另一个解方案 相比有较低的有效成本，然而其运转效率也相应较低，这种情况反之亦然。这两 个方案不可以通过比较关系来区分出优劣。因此不再同在单目标问题中的那样， 可以根据唯一的目标函数f 来确定解方案之间的优劣关系，即对可行域中的任意 两个解x t ，x 2 ，通过f ( x 1 ) ，f ( x 2 ) o 勺优劣关系比较来找到使得坟x ) 取极值的解。这 就使得多目标问题的优化与单目标优化相比更加复杂。实际上，单目标优化问题 可以看作多目标优化问题的一个特例。 下面给出了m o p 中的p a r e t o 优胜和p a r e t o 最优解的相关概念1 7 】，这些概念 在指导多目标优化朝着p a r e t o 最优集的方向进行搜索是十分重要的。 在p a r e t o 优胜关系中，对于决策向量毛、x 2 ，有：1 ) 毛 - x 2 ( 五优于屯) ： 当且仅当坟五) f 【而) ；2 ) x l 三恐( x t 弱优于x 2 ) ：当且仅当坟j c l ) f i 镌) ；3 ) x l x 2 ( 鼍 无差别于屯) ：当且仅当坟五) z 坟屯) 人坟而) z f ( x l 0 我们从p a r e t o 优胜的概念可以引出m o p 问题最优解的判断依据。这里优劣 关系的比较是针对所有的子目标函数而言的。如果一个解方案优于另外一个解方 案当且仅当该决策向量的所有子目标函数值均大于另一个决策向量对应的函数 值。 在可行解集x r 中，对于集合x x r ，如果决策向量x ex r 为非劣的当 且仅当：爿一x ： - x ，则把决策向量x 称作p a r e t o 最优解。如图2 1 ，点 a 、点b 和点c 都是p a r e t o 最优解，它们之间是无差别关系。从这里看出m o p 问题的最优解不是单独的一个解方案而是一组非劣的均衡解，称为p a r c t o 最优 集。其所在的曲面被称为p a r e t o 前端( f r o n t ) 。 若x x ，s ( x ) 为x 中非劣决策向量的集合：s ( x ) = a ex 7ia 是x 中 的非劣向量 。则集合s ( x ) 称为x 的非劣集，对应的目标向量函数f ( s ( x ) ) 称 为p a r e t o 最优集，r , = t i 鼍) 称为p a r e t o 最优前端。 对p a r e t o 最优集中的任意决策向量来说，不存在提高其中一个子目标函数的 数值而不会导致其余至少一个子目标函数数值下降的情况，它们是全局最优解。 7 改进的差分进化算法在异步电机优化设计中的应用第2 章多目标进化算法的相关理论 同时与单目标优化中存在全局最优与局部最优的问题类似，多目标优化问题中的 p a r e t o 最优集也存在全局最优和局部最优的概念之分。d e b 在其文献 7 】中给出了 p a r e t o 最优集的形式化定义，需要补充的是全局p a r e t o 最优集不一定要包含所有 的p a r e t o 最优解，因为p a r e t o 最优集的大小往往是无穷的，有限规模的种群不 可能获得整个最优集，m o e a 算法的最终目的是找到一个能代表整个p a r e t o 最 优集的可行子集。因此，当我们说整个p a r e t o 最优集时，我们一般记作p a r e t o 最优集，相应的目标向量被称为p a r e t o 最优前端。 x 图2 1 多目标优化问题的p a r e t o 最优解 我们可以对多目标优化问题总结如下：与单目标问题中只有一个最优解不 同，多目标优化问题的p a r e t o 最优解是一个解集合，即一个可以接受的均衡解或 非劣解，并且多目标优化问题存在多个p a r e t o 最优解。因此在实际的工程应用中， 最后得到的解方案是一个集合，决策人员还必须根据实际应用背景和相关的偏好 信息来挑出一个或部分解作为最终的多目标优化问题的最优解。 进化计算是根据达尔文提出的“物竞天择，适者生存”的进化学说发展而来 的。自从2 0 世纪6 0 年代以来，生物学的进化论被推广到工程技术领域，形成一 种新的计算方法，即进化算法。据统计，仅2 0 0 0 年以后关于进化算法方面的论 文和著作就有将近4 0 0 0 篇左右，可见进化算法已成为人工智能领域中继专家系 统、神经网络之后又一个理论和应用研究热点。进化算法实质上是一种优化处理 过程，但与传统优化方法的不同之处在于，传统优化方法多是依赖代价函数( 罚 函数) 来进行问题搜索的。通过计算代价函数的梯度或高阶统计值来进行优化， 通常此类方法只能得到局部极优值，且易受随机干扰的影响。而进化计算则采用 自然进化机制来表达复杂的现象，能快速可靠的解决传统方法难以解决的问题。 8 改进的差分进化算法在异步电机优化设计中的应用第2 章多目标进化算法的相关理论 进化算法本身还能够并行的对问题进行求解估计，即使目标函数是不连续，不规 则或者有噪声的情况，在搜索过程中也易陷入局部最优。最后进化算法本身也具 备很好的可扩展性，可以和其它优化方法、技术相结合组成混合算法使得它们在 最优化问题、神经网络、机器学习和并行处理等领域得到越来越广泛的应用。 与自然进化类似，进化算法的操作过程需要有三个关键步骤【8 】【9 1 ：1 ) 维持一 组候选解；2 ) 对候选解实施配对选择过程操作；3 ) 重新形成新的解集。候选集 中的每个个体基于适当结构的编码形式，作为待处理问题的一个决策向量。所有 的可行向量构成个体空间，在选择过程不断把适应度较低的值的个体从群体中移 出，那些非劣个体有更多的机会得到复制，进化结果使平均适应度得到提高。个 体的优劣与目标函数和约束条件相关，在计算个体适应度前必须先对个体解码。 变异虽然作为以很小概率发生的偶然现象，但是可以提高种群的多样性，使得种 群的改变包含一定的随机因素。 受到生物学理论的启发，人们用进化算子来近似模仿达尔文的“适者生存 学说。在进化算法中，最常用的进化操作算子包括交叉( c r o s so v e r ) 、变异 ( m u t a t i o n ) 和选择( s e l e c t ) ，其中交叉算子是最具有一般意义的算子，通过交叉操 作使得后代种群中至少有一个个体在形式上依赖于一个以上的父代个体。变异算 子的特点在于后代种群中的个体至多依赖于一个父代个体。选择算子的特点与变 异、交叉不同，它要求后代种群中所有个体都是父代种群中的个体，且其种群变 换依赖于父代种群中个体的适应度函数值和优劣关系。通过选择算子可以产生进 行更新、采样的对象或者从现有种群中选择子代个体。 2 3 多目标进化算法的关键理论 进化算法在解决多目标优化问题时，要解决两个主要的问题【io j ：1 ) 怎样处 理适应度赋值和选择机制以指导搜索尽快向p a r e t o 最优集靠近；2 ) 怎样维持多 样性以阻止早熟和保持最优解在p a r e t o 前端有广泛的分布性。这两个问题看似也 是相互冲突的，因为提高多样性可能导致收敛速度减慢或者收敛到局部最优解， 反之加快收敛速度往往不能得到很广泛的最优解。近二十年来，研究人员针对以 上两个问题展开了很多相关的研究。在1 9 8 4 年d a v es c h a f f e r 提出了基于向量评 估的遗传算法( v e g a ) ，g o l d b e r g 于1 9 8 9 年在其m o e a 的论述【1 2 1 巾引进了 9 改进的差分进化算法在异步电机优化设计中的应用第2 章多目标进化算法的相关理论 小生境机制和基于非劣解的排序方法来处理以上两个问题。后来在很多人提出的 多目标优化算法中如m o g a , n s g a , n p g a 都直接引用了g o l d b e r g 的思想：1 ) 通 过种群中支配关系的扩展来评估个体的适应度；2 ) 引入了小生境技术来解决种 群多样性问题。然后在这些算法中由于缺少精英策略，使得算法不能很好的收敛 到真正的p a r e t o 最优解。因此后来的m o e a 算法研究主要集中在如何让精英策 略引入到m o e a 中以保证p a r e t o 最优问题的收敛性。这些算法包括： s p e a , p a e s ，n s g a i i 等。随着这些理论问题的不断解决与改进，进化算法不断 被用在解决越来越多的实际问题。本节将在总结这些算法优缺点的基础上，就适 应度分配、多样性保持、收敛性和精英策略的理论展开阐述，最后就常见的约束 问题的处理机制也给出了总结。 2 3 1 适应度赋值 适应度赋值问题与进化算法中如何使进化朝p a r e t o 最优集定向搜索有关。多 目标进化算法的适应度赋值问题与单目标优化相比，无论在操作原理上还是操作 方式上都有着重要的区别。在单目标的优化中，目标函数常与适应函数是相同的。 而在多目标问题中的适应度赋值和选择必须同时考虑到几个子目标。根据目前对 多目标进化算法的研究情况，可分为三种适应度赋值策略：基于聚合的策略、基 于准则的策略和基于p a r e t o 优胜关系的策略。其中基于p a r e t o 优胜关系的策略 是在多目标问题中经常用到的适应度赋值方法。图2 。3 说明了这三种策略的特点。 基于聚合的策略沿用了传统的优化技术，组合多个子目标函数成为一个带参 数的单目标函数，然后通过求得这个单目标函数的极值来求得p a r e t o 最优前端。 在优化的过程中系统地调整该函数中的参数，以便找出一组非劣解而非单个的最 优解。但是这种方法有个最大的缺点就是不能在非凸性的均衡曲面上得到所有的 p a r e t o 最优解，不能很好的处理前端的凹部。另外，权值的参数也与问题的背景 有关，有时会因为缺乏与应用背景有关的启发知识而导致无法正常的实施优化。 如图2 3 ( a ) ，找到的最优解位于顶端的一些区域内。早期的一些多目标进化算法 就是采用了这种线性加权的方式，在优化过程中调节代表参数的权重值【1 3 ”】。 1 0 改进的差分进化算法在异步电机优化设计中的应用第2 章多目标进化算法的相关理论 y 1h ( c ) 图2 - 3 i s i m o e a s 的三种适应度赋值策略 基于准则的策略通常在选择阶段变换所选的子目标。每当种群中的个人被 选中后进行复制时，根据不同的子目标来决定是否被复制至配对池。例 如，s c h a f f e r 提出的基于向量的遗传算法根据不同目标均等地填满配对池，就是一 种典型的基于准则的适应度赋值策略。另外，k u r s a w e 在其论文中提出依赖于一 定的概率值来选择使用各个准则，其概率取值可以由用户定义也可以随机定义。 但是基于准则的策略存在的问题是进化结果容易走向某些极端边界解，且与基于 聚合的策略缺点类似，对p a r e t o 最优前端的凹部敏感。图2 - 3 ( b ) 所示为基于准则 的策略，在不同的子目标对应不同的圆，圆内包含了在该准则下相应的最优解。 基于p a r e t o 优胜关系计算个体适应度的思想最早由g o l d b e r g 提出【1 2 】，它的 个体等级排序过程是：把当前群体中所有非劣解的等级赋值为1 ，将其从种群中 暂时除去；然后在群体的其余个体中将所有非劣个体的等级赋值为2 ，同样将其 从种群中暂时除去；如此迭代直到种群中所有个体都被赋值为止。这种方法与一 般的聚合方法相比，其适应度值的计算与群体的规模有关。后人大多在此基础上 进行改进的，如将群体划分成几个有序的子群体。有些方法采用计算优胜级别的 方式，即统计群体中优于该个体的其它个体数目之和，以此确定个体的适应度值。 改进的差分进化算法在异步电机优化设计中的应用第2 章多目标进化算法的相关理论 而某些算法，如非劣排序的遗传算法( n s g a ) ，还采用了支配深度的概念，将群 体划分为几个最优前端以及次优前端等，根据当前个体所在前端深度值的不同来 赋予该个体适应度。般来说，直接统计优胜个体数目的操作方式简单，且易于 实现，像基于强度的p a r e t o 进化算法( s p e a ) 以及其改进的算法( s p e a 2 ) 都是 采用这种策略。如图2 - 3 ( c ) 为求的p a r e t o 最优解，它们明显优于左下侧矩形区域 内的解点。 多目标进化算法必须根据个体间的p a r e t o 优胜关系和其它信息为个体确定 适应度值。这种适应度值和每个目标函数的具体数值没有直接关系，而在单目标 优化中这两个函数是直接相关的。而且即使在个体保持不变的情况下，同一代个 体在这一代获得的适应度值和它在下一代的适应度值可能不相等，这样的情况在 单目标优化时是不可能出现的。p a r e t o 优胜关系是决定个体适应度函数值的重要 依据，很多m o e a s 根据个体的这种关系，将个体的适应度函数分为两个层次： 非劣解和劣解，并且总是给予前者较多的适应度值。当个体间没有p a r e t o 优胜关 系时，其它个体信息被用于确定适应度函数值。如基于多样性的原则，或者和外 部种群进行比较等。 很多研究者都采用了基于p a r e t o 优胜关系的选择方法，并产生了多种基于 p a r e t o 的适应度赋值方案。虽然在理论上这类的多目标进化算法能找到任意 p a r e t o 最优解，但有时搜索空间的维数会对它的性能造成影响。如f o n s e c a 和 f l e m i n g 在其论文中指出：仅仅基于p a r e t o 的进化算法不能正确地包含很多个子 目标的问题进行优化，由于均衡曲面的大小和纬度过高，会导致不能产生满意解 ( 全局最优解) 。但是，基于p a r e t o 的选择方法仍是多目标进化领域最流行的， 它可以解决一般的多目标优化问题【l5 1 。 2 3 2 多样性保持 多样性保持是多目标进化算法要实现的另外一个主要问题。进化算法由于其 进化算子固有的随机误差，因此基于有限群体进化时会出现收敛至某一个解的情 况。而在实际问题中，我们进行多目标优化时更希望得到一个p a r e t o 最优解集， 即搜索出的问题的整个p a r e t o 曲面上尽可能的均匀分布的最优解集，而不仅是某 一个非劣解。只有这样才可以在更多有效的非劣可行空间内，结合问题的特殊背 1 2 改进的差分进化算法在异步电机优化设计中的应用 第2 章多目标进化算法的相关理论 景和工程人员的偏好从求得p a r e t o 最优解中挑选出最终满意的方案来。因此多目 标进化算法的一个关键问题是必须在进化过程中采取适当的措施避免进化结果 收敛至单个解的情况。 群体的多样性与种群规模有一定关系，可以根据进化计算中的模式( s c h e m a ) 定理【1 6 】，若群体规模为m ，则进化操作可以从这m 个个体中生成和检测m 3 个 模式，并在此基础上不断形成和优化积木块，直至找到最优解。显然m 取值越 大，进化操作所处理的模式越多，越会生成有意义的积木块，并且逐渐进化到最 优解的机会越高。因此如果仅从群体多样性角度考虑，种群规模越大越有利于多 样性的保持。但是实际群体规模不能太大，一方面，若种群越大，导致其适应度 估值的次数增加，引起计算量的增加，从而影响算法的效率。另一方面，在进化 算法中，群体中个体的选择多采用与适应度成比例的方法，当群体中个体非常多 时，只要少量适应度很高的解个体会被选择而生存下来，而大多数解则会被淘汰， 影响配对池的正常形成，从而影响交叉操作。因此群体规模只能限定在一定数量 上，它不能成为维持种群多样性的途径。 早期的研究人员发现，在有限种群规模下进化算法易收敛于单个解的现象与 自然界的物种进化现象类似：在自然界中，当某一种群中的个体大量繁殖生存时， 为争夺有限的自然资源必然会加剧个体间的竞争，从而导致个体的存活率降低。 我们将这种现象称为遗传漂移。基于这种机制的产生，h o l l a n d 教授提出使用“拥 挤”算子，即新生成的子代替代或排挤相似的父代个体。这样在选择过程中，个 体在其领域内的密度信息值越高，被选择复制的机会就约小。多目标优化问题就 是采用了这种与单目标优化问题在选择过程中结合密度信息的类似思想来保持 群体的多样性的。这种思想与统计学中概率密度函数的估计有关，其保持多样性 的策略可以根据统计密度估计的技术进行分类【1 7 】，如图2 4 。