（电工理论与新技术专业论文）电磁场逆问题分析计算的快速全局优化算法研究.pdf

浙江大学硕士学位论文 a b s t r a c t t h a n k st ot h ea d v a n c e si nb o t ht h ec o m p u t e rs c i e n c ea n de l e c t r o m a g n e t i c s ，t h e i n v e r s ee l e c t r o m a g n e t i cp r o b l e mh a sb e c o m eat o p i c a ls u b j e c ti nc o m p u m f i o n a l e l e c t r o m a g n e t i c s i no r d e rt om e e tt h ee v e r - i n e r e a s i n gr e q u i r e m 锄临i nd e s i g n a u t o m a t i o n so f e l e c t r o m a g n e t i cd e v i c e s b a s e do nac o m p r e h e n s i v ea n a l y s i se n di n t e g r a t i o no fa v m l a b l eg l o b a lo p t i m a l a l g o r i t h m s ，t h i sd i s s e r t a t i o nm a i n l yf o c u s e so nt h es t u d yo ff a s tg l o b a lo p t i m a l m e t h o d sa p p l i e dt oi n v e r s ee l e c t r o m a g n e t i cp r o b l e m s f i r s t l y , t h eg e n e t i ca l g o r i t h m ( g a ) a n d t h ep a r a d es w a r mo p t i m i z a t i o n ( p s o ) m e t h o d sa r es t u d i e d d i f f e r e n ti m p r o v e m e n t sa g ep r o p o s e dt od e v e l o pr o b u s t o p t i m i z e r si ns e n s e so fb o t hc o n v e r g e n c es p e e d se n dg l o b a ls e a r c ha b i l i t i e s t y p i c a l m a t h e m a t i cf u n c t i o n sa r es o l v e dt od e m o n s t r a t et h ee f f e c t i v e n e s se n de m c i e i l c yo f t h e i m p r o v e dg aa n dp s o s e c o n d l y , t od e v e l o pc o m p u t a t i o n a u ye f f i c i e n tg l o b a lo p t i m a lo p t i n 1 i z e r sw i t h t h em a i ng o a lo fr e l e a s i n gt h er e q u i r e m e n tf o rt r e m e n d o u s l yh e a v yc o m p u t a t i o n r c s o b l e 船e s p e c i a l l y t or e d u c et h en u m b e ro ff u n c t i o nc a l l st h a ti n v o l v e c o m p u t a t i o n a l l yh e a v yp r o c e d u r e si nt h es t u d yo fe l e c t r o m a g n e t i ci n v e r s ep r o b l e m s ， t h er e s p o n s es u r f a c em o d e l s ( r s m ) o rm e t h o d o l o g i e sa r ei n c o r p o r a t e di n t ot h e s t o c h a s t i cg l o b a lo p t i m a lm e t h o d s f o rt h i sp u r p o s e ，t h ec o m p a c t l ys u p p o r t e dr a d i a l b a s i sf u n c t i o na n dt h em o v i n gl e a s ts q u a r e sa p p r o x i m a t i o nb a s e do n e sa r ei n t e g r a t e d i n t ot h ea f o r e m e n t i o n e dt w og l o b a l o p t i m i z e - r s a sar e s u l t , t w on o v e lh y b r i d a l g o r i t h m sa r ei n t r o d u c e d f i n a l l y , t h ep r o p o s e dh y b r i da l g o r i t h m s a r ea p p l i e d s u c c e s s f u l l yt os t u d y b e n c h m a r ki n v e r s ee l e c t r o m a g n e t i cp r o b l e m s t h en u m e r i c a lr e s u l t so ft e a m w o r k s h o pp r o b l e m2 2e n dp r o b l e m2 5 嬲r e p o r t e dv a l i d a t et h ef e a s i b i l i t ya n dt h e r o b u s t n e s so f t h ec o r r e s p o n d i n ga l g o r i t h m s k e yw o r d s ：f a s tg l o b a lo p t i m a la l g o r i t h m , i n v e r s ee l e c t r o m a g n e t i cp r o b l e m , g e n e t i c a l g o r i t h m , p a r t i c l e s w a r mo p t i m i z a t i o n , r e s p o n s es u r f a c em o d e l , o p t i m a ld e s i g n i i 浙江大学硕士学位论文 第1 章绪论 1 1 课题的背景和意义 1 8 5 6 年麦克斯韦从数学的推演出发，以微分方程和积分方程的形式描述了 电场和磁场间的相互关系，得到了举世闻名的麦克斯韦方程组。从麦克斯韦方程 组诞生至今，经典电磁学已发展了一百多年，人们以此为基础进行电磁场理论分 析与工程设计【旧。 由于电气工程中实际的电磁场问题相当复杂，如边界形状不规则、复杂的物 质结构、材料性能的非线性以及电磁场量的分布性，以致在计算机出现以前，人 们在实际的设计与计算分析中，还只能通过采用一些简化措施，得出近似的解析 解，或者用模拟实验的方法得出满足工程要求的近似结果。 电子计算机的出现，为解算复杂电气工程技术问题提供了强有力的工具。由 于计算机具有运算速度快、存储容量大、计算功能强和准确度高等优点，使得计 算技术领域发生惊人的变化，促进了数值分析在科学技术中的广泛应用。科学技 术客观上的发展需要，计算机技术所提供的物质基础，使得电磁场数值计算这门 新科学分支得到迅速发展。并且使电磁场理论得以与现代数学、计算机科学更紧 密地结合，在定量分析需求的高度上，迎合了当今工程科学发展的总趋势。1 9 7 6 年，在英国牛津召开的第一届国际电磁场计算会议( c o m p u m a g ) 标志着电磁 场数值分析已成为电气工程中一个新兴的学科。 随着科学技术的进步，当前，在电磁场工程技术的研究中，电磁场正问题的 求解( 即己知一个系统或装置的源参数、结构参数和媒质参数的情况下，由源求 场，求解其中场的信息及相关特性) 已经发展成为相当完善的理论体系，发展了 许多各具特色的解析方法和数值方法。然而，电磁场正问题的求解往往已经不能 满足工程技术发展的需要，实际工程中越来越多需要解决的是与电磁场正问题相 对应的电磁场逆问题。电磁场逆问题是电磁装置的综合问题，它是在给定电磁装 置理想的性能指标或参数条件下，采用一定的优化方法通过装置的优化设计来实 现一定的综合设计目标。即电磁场逆问题是由场反求源、几何参数或介质参数， 以至整个装置的结构和参数。 电磁场逆问题虽然是整个电磁场理论和数值计算方法的有机部分，但是由于 浙江大学硕士学位论文 其研究历史短，以及问题本身非适定性的特点，至今仍缺少相对成熟的理论体系 和快速可靠的算法。一方面，迅速发展的计算机技术，以及电磁场数值计算理论 和方法的不断丰富和完善，使电磁场逆问题的求解成为现实；另一方面，电磁场 逆问题本身的现实应用价值，使电磁场逆问题从2 0 世纪8 0 年代中期以来成为国 内外计算电磁学学术与工程界关注的研究热点，并成为在1 9 9 1 年在意大利索伦 托召开的第八届国际电磁场计算会议( c o m p u m a g ) 提出的三个鼓励性的研究 方向之一。 国内电磁场逆问题的研究始于2 0 世纪9 0 年代，在此之前也进行过一些电磁 场优化设计方面的工作，例如电磁铁动态和静态特性的优化。但真正把它们提高 到电磁场逆问题的角度进行研究始于1 9 9 2 。如今，电磁场逆问题研究已经取得 瞩目的研究成果。但总体而言，目前国内外有关电磁场逆问题的计算主要集中于 二维稳态问题，且处于实验室开发阶段。一些世界知名的电磁场计算软件包所提 供的优化模块，也仅仅提供了( 半) 人为改变装置参数的接口条件。因此，充其 量只能称之为多输入、多输出分析软件。但由于逆问题更接近于工程实际，而采 用数值计算方法计算电磁场，能更加准确地计算出装置中电磁场的分布、电磁参 数和性能指标，进而获得较准确的优化结果。因此，尽管与逆问题相关的各方面 的研究成果还很不成熟、理论基础还不十分坚实，但已引起了各国学者的普遍重 视，在电磁领域主要的国际会议上，电磁场逆问题已经成为学术交流的主要内容 之一。电磁场逆问题的研究前景令人瞩目。 1 2 国内外研究现状 解决一个电磁场逆问题，首先应建立它的数学模型，然后再对数学模型进行 分析，求解【3 】。从数学角度来看，电磁场逆问题可归结为非线性数学规划问题， 具体表述为： j m i n，( 功，x = k x 2 r s u b j e c t t og j ( x ) 0 ( j = 1 ，2 ，功 ( 1 1 ) l噍= 0 = 】，2 ，m ；m 组成 和特性，以及激励源的特性，计算场域中场量随时间、空间分布的规律( 场分布) 。 因而，对应于电磁场正问题的电磁场数值分析的任务是根据电磁场的基本特性， 即麦克斯韦方程组，首先，建立逼近实际工程电磁场正问题的连续的数学模型； 然后，采用相应的数值计算方法，经离散化处理，把连续型数学模型转化为等价 的离散数学模型由离散数值构成联立代数方程组( 离散方程组) ，应用有效 的代数方程组解法，计算出待求离散数学模型的离散解( 即场量的数值解) ；最 后，在所得该电磁场正问题的场量( 含位函数) 离散解的基础上再经过各种后处 理过程，就可以求出所需的场域中任意点处的场强、任意区域的能量、损耗分布， 以及力、力矩和各类电磁参数与性能指标，以达到对给定的工程电磁场正问题进 行理论分析、工程判断以及优化设计等目的。 2 1 麦克斯韦方程组 麦克斯韦关于涡旋电场和位移电流的假设，揭示了电场和磁场之间既对立又 统一的内在联系存在变化电场的空间必存在变化的磁场，存在变化磁场的空 间也必存在变化的电场。麦克斯韦以精辟的数学语言将这一宏观电磁现象的规律 性归结为四个方程，合称为麦克斯韦方程组【l , 4 , 5 1 。 2 1 1 麦克斯韦方程组积分形式 麦克斯韦方程组可以用积分形式表示为： 铲蕊= f 霜+ 嚣衣眇寂iss 。s 铲扛嚣岙 ( 1 吾蠢= o 吨舀岙= i p 积 式中五、膏、西、画、歹和p 分别表示电场强度、磁场强度、 强度、电流密度和电荷密度。 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) 电位移、磁感应 6 浙江大学硕士学位论文 2 1 2 麦克斯韦方程组微分形式 麦克斯韦第一方程即式( 2 1 ) 和麦克斯韦第二方程即式( 2 2 ) ，分别反应了 电磁场理论中的全电流定律和电磁感应定律，由全电流定律和电磁感应定律的微 分形式，并依据散度定义，即可得出与式( 2 1 ) ( 2 4 ) 相应的麦克斯韦方程组的微 分形式为： v 膏：了+ 丝( 2 5 ) 西 v 五一o b a v b = 0 v d = p ( 2 6 ) ( 2 7 ) ( 2 8 ) 对式( 2 5 ) 取散度，并应用式( 2 8 ) ，得到电流连续性方程 v 了：一望( 2 9 ) 三个独立的方程式( 2 5 ) ，( 2 6 ) 和( 2 9 ) 连同洛仑兹力公式户= g ( 云+ 哥雪) ， 共同构成了宏观电磁现象的理论基础。 2 2 位函数 为有效地减少待求自由度数，提高电磁场数值计算的效率，同时，也为了简 化概念，更简便地构造数学模型，在电磁场理论的发展进程中，人们引入和应用 了各种位函数。由于本文中所研究的典型电磁装置优化设计都为恒定电流所产生 的恒定磁场，即为静态磁场，其场量和源量均为不随时间而变化的空间坐标的函 数，现仅以静态磁场为例的对其位函数方程进行分析。 在静态磁场情况下，场量满足如下的基本方程： j 乳，“ ( 2 1 0 ) i v b = 0 定义向量磁位函数j ( 尹) ，满足 雪：v j ( 2 1 1 ) 从而等价的向量磁位函数的双旋度方程为 浙江大学硕士学位论文 v 上v j ：了 ( 2 1 2 ) 若场域中媒质为各向同性的线性媒质，则弓i 入库仑规范v j ；i = 0 ，式( 2 1 2 ) 可简化为向量形式的泊松方程 v 2 j = 面 ( 2 1 3 ) 在无电流区域，静态磁场的基本方程( 2 1 0 ) 变成 j 乳，= 0 ( 2 1 4 ) ， l v b = 0 此时，可引入标量磁位函数( f ) ，而令 日= 坷 ( 2 1 5 ) 显然，标量磁位恒满足拉普拉斯方程 v 2 = o ( 2 1 6 ) 2 3 定解条件 为解决实际工程问题，除了建立场域中位函数满足的微分方程，即泛定方程 外，还必须给出电磁场问题的“个性”描述，即定解条件。由前面分析可知，场 向量豆、画、雪、歹和位函数的微分方程，均为一元二次线性偏微分方程，其定 解条件包含给定待求函数“( 尹，f ) 的初始条件和边界条件： 2 3 1 初始条件 初始条件给出初始瞬阿待求场函数”在场域各处的值 u l ，l o = g i ( f ) ( 2 1 7 ) 以及初始瞬间场域各处“对时间的变化率，即 詈k 撕) ( 2 1 8 ) 2 3 2 边界条件 边界条件与空间坐标变量尹相联系，给出场域边界s 上待求场函数“的边值， 可划分为第一类边界条件( 狄利克雷边值问题) 、第二类边界条件( 诺伊曼边值 问题) 和第三类边界条件( 洛平边值问题) ，分别定义如下： 浙江大学硕士学位论文 ( 1 ) 第一类边值条件 第一类边界条件给定整个场域边界s 上的场函数值 u l s = 石( 亏，t ) ( 2 1 9 ) 式中，露为相应边界点的位矢。 ( 2 ) 第二类边值条件 第二类边值条件给定的是场函数在边界s 上的法向导数值： 缸= f 2 c 亏, t ) ( 2 2 0 ) ( 3 ) 第三类边值条件 第三类边值条件给定的是边界s 上的场函数与其法向导数的线性组合，即 【”彤饥，r ) 警l s = 正( 亏，f ) ( 2 2 1 ) 需要指出的是，本文所研究的典型电磁装置优化设计中为静态磁场，其定解 条件没有初始条件而只有边界条件，即为边值闯题。 2 4 本构关系 物质的本构关系又称物质的电磁性质方程，指的是与媒质电磁特性相联系的 场量之间或源与场量之间的关系。本构关系是通过对电磁场作用下媒质分子极 化、磁化以及电流传导的机理分析和实验研究而总结出来的，对各向同性线性媒 质，本构关系可以简洁地表示为： d 一：e e 一 ( 2 2 2 ) 云= 詹 ( 2 2 3 ) 其中暑，分别称为媒质的介质常数( 电容率) 和磁导率，真空中介电常数 和磁导率分别为岛= 8 8 5 x 1 0 - ”f m 和p o = 4 ，r x l o - t h m 。对于一般性媒质，本 构关系为： 声= 西一毛云 ( 2 2 4 ) 府：旦一膏( 2 2 5 ) 胁 户和露分别表示极化强度矢量和磁化强度矢量。特别地，对各向同性媒质，有 浙江大学硕士学位论文 p = x , s o e ( 2 2 6 ) m = 日 ( 2 2 7 ) 其中苁、分别称为媒质的极化、磁化率，令 b = ( 1 + 乞) 岛= e , g o ( 2 2 9 ) = ( 1 + ) 硒= 以胁 ( 2 2 9 ) 则得到式( 2 2 2 ) 和式( 2 2 3 ) 。其中，脾分别称为相对介电常数和相对 磁导率。关于媒质导电性能的本构关系为： z = 盯云 ( 2 3 0 ) 其中z 是指电场作用下导电媒质中的传导电流，它不同于外加电流源。盯称为 媒质的电导率，特别地，对理想介质有o r = 0 ，对理想导体有t y - - - - o o ，对一般导 电媒质有0 口 。= j 1 妒) ；【k 】。 办。 ( 2 4 6 ) 群巧磁 式中 k l 【墨l + 玛l = i 巧蟛懿 k ：i i x ；x 纛 ( 2 4 7 ) 这一三阶方阵 k l单元电磁场能的离散矩阵，称为单元电磁场能系数矩阵， 它是一个对称阵，其元素的一般表达式为 群= 群2 云何以+ q 乞) 以j = l 工叻 ( 2 4 s ) 2 5 2 2 总体合成 按式( 2 4 0 ) ，为了得到整个d 域内二次泛函以纠关于节点电位的离散表达 式，首先必须把式( 2 4 6 ) 作适当的改写，即把 刃，扩充为 办( 力为由全部节 点电位值按节点编号顺序排成的一个b 阶列阵) ；把【k l 扩充为【j - l ( 暖l 系在 1 4 麓m听晒 坼 浙江大学硕士学位论文 式( 2 4 7 ) 所示的【k 】。基础上，按节点编号序展开行与列，构成阶方阵，其中 除行、列数分别为i ，j ，m 时存在有9 个原晖】。的元素外，其余各行、列的元 素都应为零元素) 。经这样处理后，式( 2 4 6 ) 可改写为 以胗】_ 昙 办7 【冠】 奶 ( 2 4 9 ) 于是，总体的能量积分，e p - 次泛函川纠也就离散化为 唧1鱼1 以纠* j 刃；艺以 纠= 办7 ( 霞】。) 办= 寺 妒) 7 【吲 伊 ( 2 5 0 ) 仁1 归l 式中，【k 】可称为总电磁场能系数矩阵。由于，【捌= 【足l 根据矩阵的运算， 可以看出总电场能系数矩阵的元素 局= 巧o ，j = l ，2 ，n o ) ( 2 5 1 ) 这就是说，凡下标相同的单元电磁场能系数矩阵的元素( 如j 薯和磁等等) 都 应予以相同，形成总电磁场能系数矩阵中同一下标的元素( j 匕) 。由此也就可 以判定，【刚是一个对称阵( 1 i p 巧= ) 。这样，由式( 2 5 0 ) 可见，变分问题 ( 2 3 4 ) 被离散化为如下的多元函数的极值问题： - ，【纠* ，( 仍，仍，吼) = 寺 伊，【刚 办= 寺艺毛仍纺= m i n (252)1 l 生 - - 1 ，o - 根据函数极值理论，应有罢：0 ( 扛l ，2 ，嘞) ，故由式( 2 5 2 ) 即得 或表示为矩阵形式 羔毛纺：o ( ，= 1 ，2 ，) ( 2 5 3 ) i - i 明 研= o 最终获得了所要求解的多元线性代数方程组，即所谓有限元方程 浙江大学硕士学位论文 2 5 - 3 有限元方程的求解与强制边界条件的处理 在得出有限元方程之后，可以选择各种代数解法求解，如高斯消元法，列主 元消去法，改进的平方根法及共轭梯度迭代法等。但对于条件变分问题，由于式 ( 2 3 4 ) 中的强制边界条件，意味着位于边界厶上的各节点电位值是被给定的， 它们无需通过有限元方程求解，相反地，却正是在给定这些边界节点电位值的基 础上去推求其余各节点电位值。因此，在解有限元方程前，还必须进行强制边界 条件的处理。 强制边界条件处理的方法将因代数方程组的解法而异。若运用迭代法求解， 则凡遇到边界节点所对应的方程均不进行迭代，使该节点电位始终保持初始给定 值，此时就不必单独进行边界条件的处理。但若选用直接法( 高斯消去法) 时， 则处理方法是：如果已知1 号的节点为边界节点，其电位值为纯= ，这时应将 主对角线元素k 。置1 ，行行和n 列的其他元素全部置零，而右端改为给定电位值 ；其余方程的右端要同时减去该节点电位与未处理前对应的，列中的系数的乘 积。如式( 2 5 4 ) 经上述方法处理后，应修改为 o o oo l o0 o o 仍 仍 ： ： 一k 。绲 一局。 一五。，炳 ( 2 5 5 ) 此时，待求的代数方程组形式为 【k 。】 办= ， ( 2 5 6 ) 至此，应用已有的各种代数方法，并调用相应的计算程序，即可求得方程组 ( 2 5 6 ) 的解答，也就是待求边值问题拉普拉斯场的离散解( 数值解) 仍，仍，9 k 。 2 5 4 有限元的自动剖分技术 如何将实际工程中复杂场域离散为“有限元”，即剖分问题，始终是有限元 1 6 浙江大学硕士学位论文 法实际应用中一个主要的研究方面。现在有限元类文献中的“剖分”，一般均指 自动剖分。而如何把连续场域自动剖分成为有限数量的单元，并无绝对的规律或 标准，但由于剖分单元的形状、数量、分布密度等与数值解的精度及机器运算时 间有着密切的联系，因此在本文所分析的电磁装置优化计算中，其剖分遵循如下 几点： ( 1 ) 为保证计算精度，各单元边的长度彼此不要悬殊太大，即要尽量避免出现 呈尖锐形的单元；在每一单元内部，其物理特性参数的变化应保持连续。 ( 2 ) 在场域对称部分，其单元的形态也应力求对称；需着重分析的区域，其单 元分布密度应高于其他部分。 ( 3 ) 边界单元边上节点的配置应使单元的对应边尽量逼近边界；单元( 包括节 点) 编排方法力求规范化。 1 7 浙江大学硕士学位论文 第3 章电磁场逆问题分析计算的改进遗传算法 3 1 遗传算法的产生与发展 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型， 该算法以一个适应度函数( 或目标函数) 为依据，通过对群体施加遗传操作实现 群体内个体结构重组的迭代处理过程。遗传算法的研究的历史起源可追溯到上世 纪六十年代初期，其创始人是美国m i c h i g a n 大学的j h o l l a n d 教授。1 9 6 7 年， b 列e y 发表了关于遗传算法应用的论文，首次使用了“遗传算法”( g e n e t i c a l g o r i t h m ) 来命名h o l l a n d 所提出的“进化”方法。1 9 7 5 年，h o l l a n d 总结了自 己的研究成果，发表了在遗传算法领域具有里程碑意义的著作自然系统和 人工系统的适应性( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) t 8 】。 人们通常把h o l l a n d 所提出的遗传算法称为基本遗传算法或标准遗传算法 ( 简称s g a ) 。在s g a 的基础上，人们不断对之进行了各种改进和完善，并将 s g a 与其他算法相结合以解决不同领域的问题。在过去的3 0 多年里，遗传算法 在解决复杂自然与社会的全局优化问题方面取得了成功的应用，并受到了人们的 广泛关注。我国有关遗传算法的研究，从2 0 世纪9 0 年代以来一直处于不断上升 的时期，特别是近年来，遗传算法的应用在许多领域取得了令人瞩目的成果。可 以预测，随着遗传算法理论研究的不断深入和应用领域的不断拓宽，遗传算法必 将取得更大的成功【1 m 1 2 1 。 3 2 遗传算法的基本概念 由于遗传算法是自然遗传学和计算机科学相互结合渗透的产物，因此借用了 许多自然进化的基础术语。认知生物遗传学上的基本概念与术语对于理解遗传算 法非常重要。下面列举在遗传算法中常用到的几个术语及其定义【1 0 j 3 j 4 j 。 染色体( c h r o m o s o m e ) ：是遗传物质的主要载体，由多个遗传因子基因 组成。 个体( i n d i v i d u a l ) ：指染色体带有特征的实体。 种群( p o p u l a t i o n ) ；染色体带有特征的个体组成了种群。种群中个体数目大 小称为群体大小( p o p u l a t i o ns i z e ) 。 遗传因子( g e n e ) ：染色体中一定位置的基本遗传单位，也称基因。 1 8 浙江大学硕士学位论文 基因型( g e n et y p e ) ：遗传因子组合的模型，是性状染色体的内部表现。 表现型( p h e n o t y p e ) ：有染色体决定性状的外部表现。 适应度( f i m e s s ) ：各个体对环境的适应程度。 编码( c o d i n g ) ：遗传编码可看成是从表现型向基因型的映射。 解码( d e c o d i n g ) ：是基因型向表现型的映射。 选择( s e l e c t i o n ) ：指决定以一定概率从种群中选择若干个体的操作。一般 而言，选择过程是一种基于适应度的优胜劣汰的过程。 交叉( c r o s s o v e r ) ：两个染色体之间通过交叉和重组形成新的染色体。 变异( m u t a t i o n ) ：染色体的某一基因发生变化，产生新的染色体，表现出 新的性状。 在遗传算法中，代表问题的可能潜在解集的一个种群是由基因编码的一定数 目个体组成。每个个体其实是染色体带有特征的实体。染色体作为遗传物质的主 要载体，即多个基因的集合，其内部表现是某种基因的组合，它决定了个体的外 部性状。实现从表现型到基因型的编码工作及第一代种群产生后，按照适者生存 和优胜劣汰的原理，逐代演化出越来越好的近似解。在每一代，根据问题域中个 体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异 产生出代表新的解集的种群。这个过程将导致种群像自然进化一样使后代种群比 前代更加适应于环境，末代种群的最优个体经过解码，可以作为问题的近似最优 解。 3 3 遗传算法的实现流程 遗传算法的一般流程如图3 1 所示： 第l 步：随机产生初始种群，个体数目一定，每个个体表示为染色体的基因 编码； 第2 步：计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳 个体及其代表的最优解，并结束计算；否则转入第3 步； 第3 步：依据适应度选择再生个体，适应度高的个体被选中的概率高，适应 度低的个体可能被淘汰； 第4 步：按照一定的交叉概率和交叉方法，生成新的个体； 第5 步：按照一定的变异概率和变异方法，生成新的个体； 浙江大学硕士学位论文 第6 步：由交叉和变异产生新一代的种群，返回到第2 步。 图3 1 遗传算法的流程图 3 4 遗传算法的基本要素 遗传算法中包含五个基本要素：编码方法的选择、初始种群的设定、适应度 函数的设计、遗传操作的设计和遗传参数的设定( 主要指群体大小和使用遗传算 子的概率) 。这五个要素构成了遗传算法的主要内容 1 1 - 1 3 , 1 5 - i 叼。 3 4 1 编码 问题空间指有遗传算法表现型个体集所组成的空间，而遗传算法空间是指由 基因型个体所组成的空间。由问题空间向遗传算法空间的映射称为编码( c o d i n g ) ， 而由遗传算法空间向问题空间的映射称作译码( d e c o d i n g ) 。遗传算法采用的编码 方法很多，有二进制编码，实数表示和格雷码表示等。h o l l a n d 提出的遗传算法 是采用二进制编码来表现个体的遗传基因型，它使用的编码符号集由二进制符号 0 和l 组成。二进制编码是目前常用的编码方法，其优点是编码、解码操作简单， 而且交叉、变异操作易于计算机实现。二进制编码的一个缺点是汉明悬崖 浙江大学硕士学位论文 ( h a m m i n ge l i 胁，就是在某些相邻整数的二进制代码之间有很大的汉明距离，使 g a 的交叉和突变都难以跨越。为克服此问题而提出的格雷码( g r a yc o d e ) 在相 邻整数之间汉明距离都为1 。然而汉明距离在整数之间的差并非单调增加，由此 引入了另一层次的汉明悬崖。 3 4 2 初始种群的产生 遗传操作在多个个体组成的种群中进行。在遗传算法处理流程中，继编码设 计后的任务是初始种群体设定，并以此为起点，一代代地进化直到按某种进化准 则终止进化过程，由此得出最后一个种群。在种群初始生成过程中，需要考虑种 群的规模和初始种群的产生方法，种群规模越大，群体中个体的多样性就越丰富， 这样算法陷入局部最优的可能性就越小，但是，若种群规模过大，从计算效率考 虑，增加了计算量降低了算法效率，因此在设置种群大小时要综合考虑多样性和 效率两方面的因素：而对于初始种群的产生方法，一般来说，遗传算法中初始群 体中的个体均为随机产生，这样可使初始种群尽量在解空间均匀分布，在一定程 度上防止了陷于局部最优的问题。 3 4 3 适应度函数 遗传算法在搜索进化过程中一般不考虑其他外部信息，仅用评估函数值即适 应度函数来评估个体或解的优劣，并作为以后遗传操作的依据，评估函数值又称 适应度( f i t n e s s ) 。遗传算法的适应度函数不受连续可微的约束，定义域为任意集 合。对适应度函数唯一的要求是输入可计算出能加以比较的非负结果。适应度函 数基本上有以下三种： ( 1 ) 直接以待求解的目标函数转化为适应度函数： 若目标函数为最大化问题：f ( 矽= ，o ) ； ( 3 1 ) 若目标函数为最小化问题：f ( x ) = 一f ( x ) ( 3 2 ) 这种适应度函数简单直观，但存在两个问题：其一是可能不满足常用的轮盘 赌选择中概率非负的要求；其二是某些待求解函数在函数值分布上相差很大，由 此得到的平均适应度可能不利于体现种群的平均性能，影响算法性能。 ( 2 ) 界限构造法：若目标函数为最小问题，则： 2 1 浙江大学硕士学位论文 m ) = 伊嚣q ( 3 3 ) 式中c m 戡为他) 的最大值估计。 若目标函数为最大问题，则： 荆= 詈八力 ( 3 4 ) 式中c 二。为f ( x ) 的最小值估计。该方法是直接法的一个改进，但是有时候又存 在边界值无法精确估计的问题。 ( 3 ) 去倒数法：若目标函数为最小问题，则： 以功2 丽7 丽( c “删o ) 。j 若目标函数为最大问题，则： 凡力2 丽号丽( c , c - 八啦o ) o 石 其中c 是目标函数界限的保守估计值。 适应度函数的设计一般需要尽量满足以下条件：单值、连续、非负；合 理、一致性，要求适应度反映对应解的优劣程度；计算量小，适应度函数设计 应尽可能简单，减少计算时间和空间上的复杂性；通用性强，适应度对某类具 体问题，应尽可能通用。 3 4 4 遗传操作 遗传算法中的遗传操作是模拟生物基因遗传的操作，在遗传算法中，通过编 码组成初始群体后，遗传操作的任务是对群体的个体，按照它们环境适应程度施 加一定操作，从而实现优胜劣汰的进化过程。从优化搜索而言，遗传操作可使问 题的解一代一代地优化，并逼近最优解。遗传操作包含三个基本遗传算子( g m e t i c q 埘a t o 呦：选择、交叉、变异。遗传算子的操作都是按随机扰动情况进行，即遗 传操作是随机操作，因此群体中个体向最优解迁移的规则是随机的。 ( 1 ) 选择( s e l e c t i o n ) 选择是从群体中选择优胜个体、淘汰劣质个体的操作。选择算子有时又称为 浙江大学硕士学位论文 再生算子( r e p r o d u c t i o no p e r a t o r ) 。选择是用来确定重组或交叉个体，以及被选个 体将产生多少个予代个体，其目的是把优胜的个体直接传到下一代或通过交叉配 对再遗传到下一代。选择过程的第一步是计算适应度，选择操作建立在群体中个 体适应度评估的基础上，即个体适应度越高，其被选择的机会越多，目前常用的 选择算子有：适应度比例方法、最佳个体保存方法，期望值方法，排序选择方法 等。 ( 2 ) 交叉( c r o s s o v e r ) 在自然界生物进化过程中起核心作用的是生物遗传基因的重组。同样，遗传 算法中起核心作用的是遗传操作的交叉算子。基因重组是结合来自父代交配种群 中的信息产生新个体。遗传算法中的交叉是指把两个父代个体的部分结构加以替 换、重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。 交叉是遗传算法获取新优良个体的重要手段。各种交叉算子( 对二值编码而言) 一 般都包含两个基本内容：一是从上一代种群中按照一定的规则或者随机选择出两 个父代个体，按照预先设定的交叉概率来决定每对是否需要进行交叉操作；二是 设定配对个体的交叉点，并对这些点前后配对个体部分结构( 或基因) 进行相互 配对。通常也是用随机的方法来确定交叉点。 常用的交叉方法有单点交叉和两点交叉。单点交叉是在个体串中随机设定一 个交叉点，交叉时，该点前后两个部分分别交换，并生成两个新的个体；两点交 叉与单点交叉类似，区别只是随机设置两个交叉点。两点交叉产生新个体的几率 要大于单点交叉。但是交叉点过多，会破坏优势个体的基因片段，导致交叉产生 的子个体无法继承父个体的优势基因。因此，并非交叉点越多越好。 ( 3 ) 变异( m u t a t i o n ) 变异就是对群体中个体染色体的某些基因座上的基因值做变动。依据个体编 码表示方法的不同，可以有以下算法：实值变异和二进制变异。对于基于0 ，l 字符的二进制值码而言，变异操作就是把某些基因座上的基因值取反，即0 变l 或1 变0 。变异操作由一个专门的变异概率来指导这一操作。变异本身是一种局 部随机搜索，与选择和交叉算子结合在一起，保证了遗传算法的有效性，使遗传 算法具有局部的随机搜索能力；同时使得遗传算法保持种群的多样性，以防止出 现非成熟收敛。 浙江大学硕士学位论文 在遗传算法中，遗传算法通过交叉和变异这一对相互配合又相互竞争的操作 而使其具备兼顾全局和局部的均衡搜索能力：当群体在进化中陷入搜索空间中某 个超平面而仅靠交叉不能解脱时，通过变异操作有助于摆脱；当通过交叉已形成 所期望积木块时，变异操作有可能破坏这些积木块( 具有低阶，短定义距及高适 应度的模块称作积木块) 。 3 5 遗传算法的优缺点【1 8 。2 0 】 3 5 。l 遗传算法的优点 ( 1 ) 对可行解表示的广泛性。遗传算法的处理对象不是参数本身，而是针对那 些通过参数集进行编码得到的基因个体。此编码操作使得遗传算法可以直接对结 构对象进行操作。这一特点使遗传算法具有广泛的应用领域。 ( 2 ) 群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜索方 法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相反，遗传 算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进 行评估。这一特点使遗传算法具有较好的全局搜索性能，也使得遗传算法本身易 于并行化。 ( 3 ) 不需要辅助信息。遗传算法仅用适应度函数的数值来评估基因个体，并在 此基础上进行遗传操作。更重要的是，遗传算法的适应度函数不仅不受连续可微 的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，编码必须与 可行解空间对应，不能有死码。由于限制条件缩小，使得遗传算法的应用范围大 大扩展。 ( 4 ) 内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用概率 的变迁规则来指导它的搜索方向。概率仅仅是作为一种工具来引导其搜索过程朝 着搜索空间的更优解的区域移动。虽然表面上它是一种盲目搜索方法，实际上它 有明确的搜索方向。遗传算法具有固有的并行性和并行计算的能力，并且具有可 扩展性，易于同其他技术混合。 ( 5 ) 遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数 不是连续的，非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。 遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困 浙江大学硕士学位论文 难的问题。 3 5 2 遗传算法的缺点 遗传算法作为一种优化方法，它存在自身的局限性： ( 1 ) 编码不规范及编码存在表示的不准确性。 ( 2 ) 单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的 一个方法就是对不可行解采用阀值，这样，计算的时间必然增加。 ( 3 ) 遗传算法通常的效率比其他传统的优化方法低。 ( 4 ) 遗传算法容易出现过早收敛。 ( 5 ) 遗传算法在算法的精度、可信度、计算复杂性等方面，还没有有效的定量 分析方法。 3 6 在线性能和离线性能 如前所述，遗传算法的评估指标大多采用适应值，且一般采用各代中最优个 体的适应度值和群体的平均适应度值。以此为依据，d ej o n g 提出了两个用于定 量分析遗传算法的钡4 度：离线性能( o f f - l i n ep e r f o r m a n c e ) 测度和在线性能( o n - l i n e p a - f o r n l a n c e ) 测度，得到了两个评估准则。 ( 1 ) 在线性能评估准则 设置( s ) 为环境p 下策略j 的在线性能，正o ) 为时刻埔e 第t 代中相应于环境 p 的目标函数或平均适应度函数，则五( 力可以表示为： 置o ) ：昙壹工( f ) t s l ( 3 7 ) 式( 3 7 ) 表明，在线性能可以用从第一代到当前的优化过程的平均值来表示。 ( 2 ) 离线性能评估准则 设z ( s ) 为环境p 下策略j 的离线性能，则有 z ( s ) ：昙壹r o ) ( 3 8 ) 式中，f ( f ) = 6 耐 z ( 1 ) ，z ( 2 ) ，z ( f ) ) ( 3 9 ) 式( 3 8 ) 表明，离线性能是特定时刻或特定代的最佳性能的累计平均。具体地 浙江大学硕士学位论文 说，在进化过程中，每进化一代就统计目前为止的各代中的最佳适应度或最佳平 均适应度，并计算对进化代数的平均值。 3 7 电磁场逆问题分析计算的改进遗传算法 电磁场逆问题在解空间一般都多于一个局部极值，即具有多峰性。一般情况 下，s g a 可以成功地找到其中一个极值，但却无法找到全部或大部分极值，因 为每当s g a 发现了一个极值，它就引导搜索朝着这个点进行，而将其他信息丢 弃。理论上的种群无限大无法实现，使得一方面，对模式平均值基于有限种群的 估计与模式真实值差距较大；另一方面，每个亲代只能生成整数个后代，有限种 群中模式的整数个例子不能精确反映此模式应该占的比例。随着s g a 的运行， 这两种偏差迅速累积扩大，导致s g a 的搜索轨迹与理论预测相去甚远，产生了 遗传漂移现象，因而导致未成熟收敛现象。过早收敛总是和多样性的迅速下降有 关，因此，如何保持群体的多样性成为解决这一问题的途径之一。 维持群体多样性通常可以用如下方法：增加种群规模，但是要考虑计算量 增加的因素；实施单一化，即不允许种群中有若干个相同的个体出现；实施 局部化，即把种群分割成若干子群体，每个小群体独立地进行遗传操作，这样可 以使由于出现不适当个体而产生未成熟收敛的现象局部化；增大配对的个体的 海n ( h a m n f i n g ) 距离，因为相似的个体配对会导致近亲繁殖而使得交叉结果不能 产生新的个体，可以用海明距离来定义两个父个体的相似度，并由此来判断是否 配对；根据进化的不同阶段动态的改变遗传参数中的交叉概率和变异概率，即 所谓的白适应遗传算法。 本文主要采用划分迭代阶段、自适应遗传算法和适应值比例变换法等机制对 基本遗传算法( s g a ) 进行改进。 ( 1 ) 划分迭代阶段 为提高搜索效率，将优化过程划分为两个不同的阶段，即随机搜索和局部优 化两个阶段。这样就可以通过在不同阶段设置不同的参数值，使算法兼备了均匀 搜索未访问过的空间和加快局部优化速度的两重特点。 ( 2 ) 自适应遗传算予 遗传参数中的交叉概率只和变异概率巴的选取会直接影响到算法的收敛性 浙江大学硕士学位论文 和遍历性，只和己越大，产生新个体的速度越快，同时具有高适应度的个体也 越容易遭到破坏，种群容易产生波动，算法不易收敛；而若二者过小，则搜索变 慢，且易产生局部最优，基本遗传算法是反复验证来确定和只。而本文所采 用的自适应遗传算法对于交叉概率和变异概率只采用动态值，根据适应度的 大小来改变取值。即当种群各个体适应度