（电机与电器专业论文）改进遗传算法及在电器产品优化设计中的研究.pdf

改进遗传算法及在电器产品优化设计中的研究 i n v e s t i g a t i o no fm o d i f i e dg e l l e t i c 舢g o r i t l l i n 撒di t sa p p l i c a t i o ni i l o p t i i l l i z a t i o nt oe l e 硎ca p p a r a ：t i l s a b s tr a c t n 们a d a ) ，sw i mt h em p i dd e v e l o p m c n to f i e n 钺l d 钯c h o l o i ；y i n v t i g a 聒f i e i do f e i e 曲沁d e 、，i c 嚣i sa l ch a _ 咖g 触d e s i 弘o f m o d e me i 洲c 印例鹏d e m 柚d s 矧c t l yi n t h ev o l 啪e ，曲m c 岫8 l l di n s l l l a “c h a 髓c t c r i s t i c so fe l e c 廿i cd e _ v i c 岛m b d e mo l ，t i m 跏 t h 州yi si n 仃l u c e dt o l v et i l em l l l 6 枷a b l 髓p f o b l e mf b rw l l i c hh 鹤b 鲫b e y o n dt l l e p a c 埘o f 仃a d m 伽l a lo p d m a lm e t h o d t h 璐，m o ( i c mo l 蚯m i z a 舡册t h e o 巧h 豁h naf b c 啦i n t l l ea c a d 锄i c 丘e l da th 舢a n d 曲重d ，a l l d ，k i n d so f o p 喊m i z a 缸a l g o f i t h l n sa d e v e l o p e d g e 硎ca l 鲥t h mi s 觚i a p d v ed l l r i n gt l l ea p p l i 硎雅di t sm e 山d d 粕ds 虹l la 北i na d i 幅锄妇出燃、i 也d i 岱珊毗p r 曲l e m s kt h i sp a p e f b a s e do nt h c 饿l d i 删 f e s 黜ho f 簪m 甜ca l g o d t h m ，am o d i f i e dg m e d ca l g 删_ i l l mi sp mf 0 盯掰d 姐dt l l ed e f i ：n i 缸 o fp o p u 晰捌咄i sa l i n t 蛾l u o 缸b ys n i d i 器t h ep 0 | 叫甜m n l 【蜘n gl l 把 哪i n 蜥o n 弘n 够，出= c i s i f i l l l c d 蚰u s o dt oj u 姆t h eg 跖e 6 ca 1 9 0 r i t l l m sp 咒m a h i s g i v 矾b a s e d w h i c h t h c o p 血i i z 啦i o n 洲i s 伽r i c d o 幢 m a ，a bl a n g u a g ci sa d o p f c dt op f o g r a mt l 坤c o d e s b 鹪e d 蛐s p e c i f i c d 删o n ，t t 蝣 他l a 虹s h i pb = t 】嘴nm n ka i l d 誉m e 石ca l 誉矗，m ，刚a t i o ns l ei sg a i n e d 锄dw h e t l l 盯t h e p 叩i i l a t i p r 锄a l i 鹏o rn o ti s s i l y j u d g 缸t l l ei 咖d u o e dm o d i f i c dg e d ca l 鲥t h l nd e a l s 谢t ht l l ep r 蜘啮t l l 佗p f o b l 锄w e i l ，w l l i c ha l i i l c 他雠st l l ep ( 唧l 蛳o nd i v 粥i t ya n d 科o i d s e a l l y 删咖r i n 晷t h i s m e l h o d p r o 、髑t o b e f e 船i b l e 瓶d c o 饿 c t b ya p p l y i n gt h em o d i 丘e dm e 山d dt o 血ee i 训c a la p p a m l 腿e l 删e0 i ，t i ：m i 刎o n t l l e o l m m i 蒯f 龉l i l t s 眦g m ，f 吣mw h i c ht l l ee l 仃i c - f i e l ds 呦g i hi sl h l i f b n n c d 啪b e e n l 蛔rw o r d 5 ：鲫e 啦a i g o r i 伍m p 他m 埘u 代，n n k ，o p t i m i z a t i o no f e l e c t r o d e i i 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 一l 签名： 星! f 盈五日期：型1 2 ：芝。 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名： 至k 导师签名：【尘：z 日期：竺三z 三：! q 签名： 丝l 盈导师签名：【：l ：竺 日期：竺三z 三：! q 沈阳工业大学硕士学位论文“ 1 绪论 随着科学技术的发展，优化设计应用的范露越来越广，特别是在科学研究、工程技 术和经济管理等诸多领域，小到产品部件，大到资源分配，都需要优化。例如：结构设 计要在满足强度要求等条件下所用材料的总质量最轻；编制生产计划要按照产品工艺流 程和顾客需求，尽可能降低人力、设备、原材料等成本而使患利润最高：资源分配应该 使各用户在利用有限资源的情况下产生的总效率最大等。在优化中，寻求最好结果或最 优目标，这就是最优化j 但是在很多实际的情况下；无法或很难找到最优解。因此，把 寻求接近或比较接近最优解的过程，也称之为优化。优化技术是一种以数学为基础，用 于求解各种工程问题优化解的应用技术。优化的首要任务是要找出最优解，其次，是要 快速地找到最优解。随着科学技术尤其是计算机技术的不断发展、数学理论与方法向各 门学科及各个应用领域更广泛和更深入地渗透，有理由相信，作为一个重要的科学分支 的优化技术必将在社会的众多方面发挥越来越大的作用。 目前，各类产品的优化设计越来越显现出它的重要地位。其主要原因是更多的生产 企业已清醒地认识到：占领市场的关键就在于提高产品的竞争能力，缩短产品的开发周 期。而要达到这一目的，就必须对产品进行优化设计，提高产品的性能，并降低产品的 成本。因此，优化算法作为一种得力工具被越来越频繁地引入了产品的优化设计中。特 ， 别是近几年发展起来的遗传算法i g 傩e t i ca l g o f ! i t l l m s ，g a ) j 以它特有的长处，受到了 人们的亲睐，并被广泛地应用在计算机科学、工程技术和社会科学等领域。 一 f 1 课题的国内外现状及发展趋势 一 r。 ， ， 遗传算法是借鉴生物界自然选择和进化机制发展起来的“一种高度并行、随机和白 适应的优化算法”。简单而言，它使用了群体搜索技术，将种群代表一组问题解，通 过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新一代的种群，并逐 步使种群进化到包含近似最优解的状态。由于其思想简单，易于实现以及表现出来的健 壮性，遗传算法赢得了许多应用领域，特别是近年来在问题求解、优化和搜索、机器学 习、智能控制、模式识别和人工生命等领域取得了许多令人鼓舞的成就。以遗传算法为 改进遗传算法及在电器产品优化设计中的研究 核心的进化算法，已与模糊系统理论、人工神经网络等一起成为计算智能研究中的热点， 受到广泛的关注。 t 1 1 遗传算法的产生和发展 一tj 遗传算法起源于对生物系统所进行的计算机模拟研究。 j t i一 1 9 世纪中叶，查尔斯达尔文( c h a r l e sd a h i n ) 在总结前人进化思想的基础上， 用大量的科学事实证明了生物进化过程在总体上表现为；从低级到高级，从简单到复杂， 从不完善形式到完善形式，从单一适应到多种适应，从低的有序性到高的有序性，以及 沿着物种数目日益增多的方向发展进化。达尔文认为，生物进化的动力和机制在于自然 选择。自然选择是用变异作材料，通过生存斗争实现的。凡是具有适应环境的有利变异 的个体，在生存斗争中将有更多机会生存和繁衍后代，而适应性较差的个体将被淘汰。 ， 因此。生物进化便是“物竞天择，适者生存”的过程。 早在本世纪4 0 年代，就有学者开始研究如何进行生物模拟的技术，他们从生物学 的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。5 0 年代后期，一些生物 学家着手采用电子计算机模拟生物的遗传系统，尽管开始的这些工作纯粹是研究生物现 象，但其中已使用了现代遗传算法的一些标识方式，如：“美国九s f r a s e r 于1 9 6 0 年 为了建立生物的表现型方程，用3 组5 位的o l 字符串表示方程的三个参数”“。 进入6 0 年代后，美国密执安大学的h o l l a l i d 教授及其学生们受到这种生物模拟技 术的启发，创造出了一种“基于生物遗传和进化机制的、适合于复杂系统优化设计计算 的、自适应概率优化技术一遗传算法”啪h 0 1 1 a n d 认识到了生物的遗传和自然进化 现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适 应系统的生成以及它们与环境的关系，提出“在研究和设计人工自适应系统时，可以借 鉴生物遗传的机制，以群体的方法进行自适应搜索”咖，并且充分认识到了交叉、变 ， ， 异等运算策略在自适应系统的重要性。 1 9 6 7 年。h 0 1 1 卸d 的学生b a g l e y 在其博士论文中首次提出了“遗传算法”一词， 并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等 遗传算子，在个体编码上使用了双倍体的编码方式。这些都与目前遗传算法中所使用的 沈阳工业大学硕士学位论文 。 算子和方法相类似。他还敏锐的意识到了在遗传算法执行的不同阶段可以使用不同的选 择率，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算法的概念。：t 7 0 年代，h o l l 柚d 教授提出了遗传算法的基本定理模式定理( s c h 鲫a t h e o r 钮) ， 从而奠定了遗传算法的理论基础。 1 9 7 5 年，d ej o n g 在其博士论文中结合模式定理进行了大量的纯数值函数优化计算 试验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。 1 9 8 9 年，g 0 1 d b e r g 出版了专著搜索、优化和机器学习中的遗传算法( g e n e t i c 舡9 0 r i t i m si ns e a r c h ，0 p t i m i z a t i o n 锄dm a c h i n el e a r n i n g ) 。该书系统总结了 遗传算法的主要研究成果，全面而完善的论述了遗传算法的基本原理及其应用，奠定了 现代遗传算法的科学基础，为众多研究和发展遗传算法的学者所瞩目。 1 9 9 1 年，d a v i e s 编辑出版了遗传算法手册( h a n d b o o ko fg e n e t i ca 1 9 0 r i t h m s ) 一书，书中包括了遗传算法在科学计算、工程技术和社会经济重的大量应用实例，、为推 广和普及遗传算法的应用起到了重要的指导作用。 9 0 年代以后，遗传算法不断地向广度和深度发展，它在机器学习、过程控制、经济 预测、工程优化等领域取得了成功，“国际上也多次举行学术会议( i n t e 玎l a t i o n a l f e r 朗c eo ng e n e t i ca l g o r i t h m s ) 交流遗传算法的经验”嘲在我国关于遗传算法、 进化计算的研究始于9 0 年代，近几年来，遗传算法、进化计算的应用在许多领域都取 得了令人瞩目的成果。 1 1 2 遗传算法的应用! 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领 域，对问题的种类有很强的鲁棒性，所以广泛的应用于很多学科。随着遗传算法的不断 完善和发展，人们已经将其应用于求解许多领域中的难题，并取得了卓越的成就。 一”“函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算 例。特别是对于一些非线形、多模型、多目标的函数优化问题，当利用其他优化方法较 难求解，遗传算法却可以方便地得到较好的结果”嘲。组合优化问题一致是人们关注的 热点。实践证明，遗传算法对于组合优化中的n p 完全问题非常有效，在求解旅行商问 改进遗传算法及在电器产品优化设计中的研究 题、背包问题、装箱问题、图形划分问题等方面都得到了成功的应用。生产调度问题也 是遗传算法一个研究重点。在许多情况下，生产调度问题所建立起来的数学模型难以精 确求解，在现实生产中主要靠一些经验进行调度。目前，遗传算法已成为解决复杂调度 问题的有效工具。此外，在结构优化设计、自动控制领域、图像处理、模式识别、神经 网络、机器学习等方面遗传算法也显示出较好的应用效果。_ 1 3 电器优化设计的发展 电器设计的发展大致经过了三个阶段。 第一阶段是经济设计阶段。从1 9 世纪到本世纪4 0 年代中期，电器产品的设计是以 物理基本定律和生产经验为基础，应用一些具有经验系数的公式，完成典型计算。样机 图样产生后，试制成样机，进行反复试验和多次修改，直到满足原定技术条件，试制才 告完成m 、第二阶段是科学试验阶段。从4 0 年代后期到6 0 年代后期，国外技术先进的电器企 业都只是致力予改进和充实试验手段，提高测试技术水平，不断改进模拟技术及模型试 验。 第三阶段是计算机辅助设计阶段。自7 0 年代初，随着计算机的迅猛发展和功能的 日益完善，计算机的应用也进入了电器产品的设计领域，用以帮助设计人员完成电器产 品的结构分析、设计、测试、检验等各项操作。电器计算机辅助设计根据其数学模型的 建立程度大致可分为两个层次：其一是以等效路的方式为基础构造的数学模型，主要应 用于一些结构较为简单、较易等效处理的产品设计中；其二是以兰维或三维场的方式为 基础构造的数学模型，运用的等效方法更为精确，主要进行结构更为复杂的产品设计。 1 1 4 _ t l a b 简介， 在遗传算法的研究中，要实现遗传过程，编程是必不可少的一部分，“由美国m a t h _ o r k 公司推出的姒t l b ，是一种集数值计算、符号运算、可视化建模、仿真和图形处 理等多种功能于一体的优秀的图形化语言”哪，它在包括小到方程的求解、多项式的运 算( 如因式分解) 。数学的极值计算，大到金融，工业系统仿真和统计等诸多领域都得 到了广泛的应用。与其他的计算机高级语言相比，姒t l a b 的优点在于容易使用、可以由 沈阳工业大学硕士学位论文 多种操作系统支持、提供了丰富的内部函数和强大的图形和符号功能、可以自动选择算 法以及与其他软件和语言有良好的对接性等。因此，它己成为当今国际科学与工程领域 中应用最广，最受人们喜爱的一种软件环境。 姒t l a b 是t r i xl a b o r a t o r y 的缩写，它的首创者c l e v e l e r 教授在数值分析， 特别是在数值线性代数的领域中很有影响。1 9 8 0 年前后，时任新墨西哥大学计算机系主 任的m o l e r 教授在讲授线性代数课程时，发现了用其他高级语言编程极其不方便，便构 ， ， 思并开发了姒t l a b ，这一软件利用了他研制的在国际上颇有影响的e i s p a c k ( 基于特征 值计算的软件包) 和l i n p a c k ( 线性代数软件包) 两大软件包中可靠的子程序，用f o r t r 卸 语言编写了集命令翻译、科学计算于一身的一套交互式软件系统。这里所谓交互式语言， 。 i 是指用户给出一条命令，立即就可以得出该命令的结果。该语言无需像c 和f o r t r 雠语 ， 言那样，首先要求使用者去编写源程序，然后对其进行编译、连接，最终形成可执行文 件，这无疑给使用者带来极大的方便。在m a t l a b 下，矩阵的运算变的异常容易，所以 它一出现就广受欢迎，这一系统逐渐发展、完善，逐步走向成熟，形成今天的模样。早 期的姒t l a b 语言只能作矩阵运算，绘图也只能用极其原始的方法，即用星号描点的形 式画图，内部函数也只提供了几十个。但即使当时功能十分简单，但当它作为免费软件 出现以后，还是吸引了大批的使用者。1 9 8 4 年，c l e v em o l e r 等教授成立了一个名叫t h e m a t h w o r k s 的公司，同年，该公司于推出了第一个姒t l b 的商业版本。当时的l l a t l b 版本已经用c 语言作了完全的改写，其后又增添了丰富多彩的图形图像处理、多媒体功 能、符号运算和它与其他流行软件的接口功能，使得姒t l a b 的功能越来越强大。在以 后的十几年，经过不断的更新设计，陆续推出的新版姒t l a b ，无论是其模型输入的方式、 还是用户图形界面设计以及与c 语言接口及转换的兼容性方面都更加完善，令人耳目一 新。2 0 0 2 年6 月正式推出了。采用最新的j i t ( j u s t i n t i 舱) 加速技术、支持多领 ， ， 域的模块设计( 如：机械、电力及无线系统等) 及嵌入式目标的仿真、微控制器的程序 代码产生及d s p 程序代码产生方面具有重大革新”叫的姒t l a br e l e a s e1 3 ，即 1 姒t l a b 6 5 s i 眦l i n k 5 0 版。 改进遗传算法及在电器产品优化设计中的研究 目前，姒t l a b 语言已成为当今国际上科学界( 尤其是自动控制领域) 最具影响力、 也最有活力的软件。现在的姒t l a b 已经不仅仅是一个“矩阵实验室”了，它已经成为 了一种具有广泛应用前景的全新的计算机高级编程语言。可以预见，在科学运算与系统 仿真领域姒t l a b 语言将长期保持独一无二的地位。 1 2 本课题研究的意义 本课题是在电器结构优化设计中应用遗传优化算法，利用改进后的遗传算法对电器 产品进行优化，使其结构更趋于合理，提升产品的性能。 对电器产品结构进行优化设计，是电器产品从设计、制造、装配、销售到使用各个 环节中较重要的一环。利用计算机辅助设计，帮助设计人员完成电器产品的结构分析、 设计、测试、检验等各项操作，可以使电器产品更加适应市场需求。一些人认为：“在 电器优化设计中应用遗传算法，通过优化计算得到电器设备的优化结构，改善电场分布， 可以减少电场强度和电场畸变度，达到提高绝缘性能的目的”n 。1 随着电子计算技术的发展，许多数学最优化方法应运而生。人们将这些数学最优化 方法应用于各个领域，取得节省人力、物力，财力等最佳效益。但是，随着研究问题越 来越复杂，设计变量数量的增加及目标函数高度的非线性，“当采用传统优化方法( 如： 消去法、黄金分割法、多项逼近法、外推法、n e - t o n 法、共轭剃度法等) 时。效率较低， 寻优速度慢、时间长，将不能保证得到的结果是全局最优解”“”，因此，需要改进和发 展。“而高级优化方法，如禁忌搜索法( t a b us e a r c h ) 、遗传算法( g e n e t i ca 1 9 0 r i t t l m ) 、 ， 模拟退火法( s i 删1 a t e da i l n e a l i n g ) 、人工神经网络( a r t i f i c i a ln e u r a ln e t 们r k ) j 等弥补了传统优化方法的不足，经常用来优化变量较多，峰值较多的实际问题”“。 在电器问题求解中，由于设计变量较多，通常具有多个局部最优解，为了得到更为 精确的全局最优解，对优化算法提出了较高的要求，即：要求算法必须是一种全局优化 的算法，不会陷入局部最优解或落入局部最优解的概率很小。正因为如此，近几年发展 起来的遗传算法才以其特有的群体搜索、较好的全局寻优能力、不需要目标函数的导数、 概率转移准则等优势，被频繁地应用于电器产品的优化设计中。同时，由于遗传算法允 沈阳工业大学硕士学位论文 许所求解的问题是非线性的和不连续的，并能从整个可行解空间寻找全局最优解，所以 其搜索最优解的过程是有指导性的，也避免了一般优化算法的维数灾难问题。 本文在研究传统的遗传算法理论的基础上，提出一种改进的遗传算法，较好地解决 早熟等影响收敛速度和质量问题。利用改进后的遗传算法对电器产品进行优化，提高遗 传算法的运行效率和最优解的质量，使其结构更趋于合理，提升了产品的性能，增强产 品的竞争能力在当今讲求竞争，讲求效率与效益的时代，对遗传算法的改进及其应用 的研究具有十分重要的现实意义和应用价值。 1 3 课题的实现 一 本文用姒t l a b 软件设计遗传算法程序，在此基础上采用“优秀个体选择策略”。 对遗传优化算法的早熟问题进行深入研究和改进，使算法获得稳定、良好的全局搜索性 ， 能，从而实现对电器结构的高效，准确的优化设计。 ， 主要工作包括以下几个方面： l h ( 1 ) 学习遗传算法的基本思想、基本方法，熟练掌握遗传算法的应用。 k 。 ( 2 ) 利用姒t l a 8 语言进行遗传算法改进研究和优化设计等工作。也就是用姒t l a b 一 语言将算法程序化，来实现遗传算法对具体产品结构的优化设计研究。 r ， ( 3 ) 研究解决遗传算法的早熟问题：评价一个优化方法的好坏主要有两个方面，一 是能否找到最优解，这是最主要的，也是我们最终的目的。其次就是计算速度，同样能 找到最优解的情况下，速度越快越好，效率越高越好。 在对遗传算法研究的基础上，分析遗传算法早熟的内部规律，建立考虑到种群规模、 优化进程等影响的判定数学模型，形成改进早熟的策略和实现方法，并通过对具体函数 的优化，来验证改进的遗传算法的效果，是本课题最主要的工作。 ：。 ( 4 ) 利用改进的遗传算法进行电器产品的优化设计，以验证其可行性和有效性。 改进遗传算法及在电器产品优化设计中的研究 2 遗传算法的基本理论 2 1 遗传算法基本思想 遗传算法的基本思想基于d 啪i n 进化论和m e n d e l 的遗传学说。 一众所周知，d 铘i n 进化论最重要的是适者生存原理。它认为每一物种在发展中越来 越适应环境。物种中每个个体的基本特征由后代所继承，但后代又会产生一些有异于父 代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来，并得以继 续繁衍发展。 而m e n d e l 遗传学说最重要的是基因遗传原理，它认为遗传以密码方式存在于细胞 中，并以基因形式包含在染色体内。每个基因都有其特殊的位置并控制某种特殊性质。 所以，每个基因产生的个体对环境都具有某种适应性。而基因突变和基因杂交则可以产 生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 在模拟d a n i n 的进化论和m e n d e l 的遗传学理论基础上，遗传算法( g a ) 把问题的 解表示成“染色体”。在执行遗传算法之前，随机给出一群“染色体”，也就是假设解。 然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应 环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体” 群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，这个“染 色体”就是问题的最优解。也就是说，应用遗传算法寻求最优解的基本思想“2 3 是先将问 题的侯选解进行编码，相当于选择遗传物质，。遗传编码可以看作从表现型到遗传子型 的映射”“”，即一个侯选解对应一个编码，经过编码后的侯选解称为个体，许多这样的 个体组成群体。然后，对群体象生物进化那样进行选择、交叉和变异的操作，产生新一 代群体。选择的基础是适应度值，即：个体对环境的适应程度。它是反映问题的目标函 数，也是遗传算法中评价个体优劣的指标。不同的问题有不同的适应度函数，对于适应 度函数值高的个体在下一代有较多的选择机会，而适应度函数值低的个体，则在下一代 产生数目较少的后代，最后逐渐被淘汰。通过这样的筛选，使得整个群体一代比一代优 良尽管选择操作提高了群体的平均适应度值，但没有产生新的个体。新个体的产生是 通过交叉和变异操作实现的。交叉通过双亲编码的随机交换产生新一代的群体，体现了 沈阳工业大学硕士学位论文 自然界信息交换的思想。交叉操作产生的新一代的个体，既保留了双亲的部分基因，又 引入新的基因。变异操作是模拟生物进化过程中基因突变现象，虽然发生变异的概率很 小，但这种变异在优化过程中非常有意义，。它可以防止求解过程中过早收敛产生局部 最优解而非总体最优解。经过上述多代操作，即可最终获得问题的最优解”呻1 。 2 2 基本遗传算法介绍 遗传算法( g a ) 是一种基于种群搜索的优化算法，它以群体中的所有个体为研究对 象，通过编码、产生群体、计算适应度、复制、交叉、变异等操作来实现。 2 2 1 遗传算法的流程 7 “ 遗传算法包含了如下五个基本要素：( 1 ) 可行解编码；( 2 ) 初始群体的设定；( 3 ) 适应度函数的选取；( 4 ) 遗传操作设计；( 5 ) 控制参数设定( 主要是指群体的大小和 遗传操作的概率等) 。这五个要素构成遗传算法核心内容”n 羽。而“设计一个好的遗 传算法，共有三个关键步骤，即：染色体的编码、染色体的选择与评估、遗传算子的设 计”嘲 简单遗传算法的应用步骤是： ( 1 ) 在定义域范围内随机生成一定数量( 规模n ) 的初始值，构成初始群体： ( 2 ) 以一定的概率( p c ) 使群体中的个体两两随机交叉，新个体取代父代个体： ( 3 ) 以较小的概率( 咖使群体中的少数个体发生变异： ( 4 ) 以适应度函数计算每个个体的适应值：t ( 5 ) 根据适应值选择复制较好的个体，组成同样规模的新一代群体： ( 6 ) 重复进行( 2 卜_ ( 5 ) 直至满足结束条件”l 切。 遗传算法基本流程【1 羽【1 研如图2 1 所示。 2 2 2 编码 编码( c o d i n g ) 相当于选择遗传物质，每一个字符串对应一个染色体。编码其实就是 原码的影子。例如；某个建筑物的高度如果不能用尺测量出来的话，可以测量它的影子， 然后折算出建筑物的高度。建筑物的实际高度就是原码，影子的长度就是经过编码处理 过的。编码的作用就是把不可能的计算变成可能，把复杂的计算变的简单。利用遗传算 9 一 改进遗传算法及在电器产品优化设计中的研究 法进行问题求解时，首先要确定问题的目标函数和变量，然后对变量进行编码。这样做主 要是因为在遗传算法中，问题的解是用数字串来表示的。而且遗传操作算子也是直接对 串进行操作的。 图2 1 遗传算法基本流程图 f i 9 2 1f l a w 出a r t o f g 嘶嘶c 咄孵i 血衄 编码方式可分为二进制编码和实数编码( 即：十进镑0 编码) ， 遗传算法的创始人h 0 1 l a i l d 认为：“将一个十进制数利用= 进制编码后，其占的位 数增多，描述的比较细致，相当于加大了搜索范围，从而能以较大的概率搜索到全局最优 解“捌。同时，通过一些简单的变换规则就可以逐步地改进这些二进制编码表示的结构， 使之往好的方向“进化”。因此，在他的专著中基本上采用这种传统的编码方式。 沈阳工业大学硕士学位论文 ，二当染色体的编码方法是使用固定长度的二进制符号来表示群体中的个体时，二进制 码o ，l 就表示基因。初始群体中各个个体的基因值都可用均匀分布的随机数来生成 如：x = 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 就表示一个个体，该个体的染色体长度是n _ 1 8 只 - 具体地说，根据排列计算，长度为的串能表达尹种情况，如果取值范围介于u 赫 ，1_ 、 u 一之间。采用映射的方法，用个二进制数表示妙血，u 一】，令工个。表示u 墒， 、 f l， 二j，。i，j、+，。 个l 表示c ，。，其中乓大小取决于眇曲，u 一】，其余的数则用线性插值决定。插值误差 艿：型譬二垡堕j 。，严一l( 2 1 ) ， 例如：目标函数厂在其定义域里只取正值，若为负，可通过加入某个正常数c 使之 、 1 。 b。 r 、 为正。现在，假设预求一个有七个变量的函数几。，靶n ) 在忍j r 时厂的最大值，进 ” ，i 。，： 。， 一。 ，口 一步假设每个变量毛为域凸= h ，6 f 】内的个值，且对所有 o 。 假定以某个要求的精度优化，：这里取自变量小数点后6 位 很明显，要达到这样的精度：每个域西应该被分割成锄一口，) 1 0 6 个等尺寸的区间， 这里用珊。表示使g 一曲) 1 0 6 2 聃一l 成立的最小整数。这样，对每个变量而，由串长为 砌的二进制编码表达显然能满足要求，每个串对应的自变量的值为： 唧+ 竽掣拦掣，。如， 其中如曲删慨) 2 表示二进制串的十进制值。 ；r，_ 通过以上分析可见，二进制编码方式有如下优点：它与计算机码制相一致，编码、 f 解码操作简单易行，适于计算机应用；对于码串的每一位，只有1 和0 两个码值，在交叉 和变异等操作中原理清晰，操作简单；表示的变量范围大，如。长为l 的码串最多可表示 2 l 个不同的变量；适合于表示离散变量，而对于连续变量，只要群体总数取足够多，就可 改进遗传算法及在电器产品优化设计中的研究 以达到足够的精度”啪1 ；便于利用模式定理对算法进行理论分析。因此，当问题比较 简单时，每一位0 或l 就代表一个性质；当问题的性质要用数值描述时，则编码用二进 制表示十进制数。 但是，利用二进制编码方式也存在着缺点。对于一些大规模的多变量的优化问题，如 果其各变量用二进制表示，同时为了保证问题的解具有一定的精度。那么得到的数字串 将会很长，这就使得遗传操作算子的计算量较大，计算时间增多，同时占用了较大的计算 机内存空间：此外。用二进制来表示问题的解。在优化过程中就需要对参数进行编码和译 码，以进行二进制和十进制之间的数据转换，这就存在数据之间的转换误差( 引入了量化 误差) 。如果目标函数值在最优点附近变化较快的话就可能会错过最优点。因此，采用实 数编码的方式被提出。利用实数进行编码，表示问题解的数字串将会比用二进制表示的 数字串短得多，相应的遗传操作算子的计算量也会减少，所需的计算时间也降低。利用实 数编码来表示解，在优化过程中不需对参数进行编码和译码，相应地就不存在解的精度 问题。综上所述。采用实数编码要比二进制编码计算量小，不会存在编码、译码造成解的 误差。但是，具体使用哪种编码方式，要根据实际的优化问题来确定。 2 2 3 适应度函数的选择 在遗传算法中，衡量个体优劣的尺度是适应度。根据适应度的大小，决定某些个体 是繁殖或是消亡。适应度较高的个体遗传到下一代的概率较大，而适应度较低的个体遗 传到下一代的概率就相对小一些。通常取高于群体平均适应度值的个体做交叉、低于平 均适应度值的个体做变异。从而一代一代地提高群体的平均适应度值和最优个体的性 能。可见，适应度函数在遗传算法中起着决定性作用。 基本遗传算法的个体适应度评价是按与个体适应度成正比的概率来决定当前群体 中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，要求所有个体的适 应度必须为正数或零。这样，根据不同种类的问题，预先确定好由目标函数值到个体适 应度之间的转换规则，以及当目标函数值为负值时的处理办法。 评价个体适应度的一般过程： ( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型。 沈阳工业大学硕士学位论文 ( 2 ) 由个体的表现型可计算出对应个体的目标函数值。 ( 3 ) 根据最优化问题的类型，由目标函数按一定的转换规则求出个体的适应度。 一一般来说r 最优化问题分两类，类为求目标函数的全局最大值，另一类为求目标 函数的全局最小值，两类适应度函数和目标函数间的转换方法可为： 。对于求最大值问题，作如下转换：” 凇) = + c 血：善猫笔 c 如， 女中，。c 血为一个适当的相对较小的数。 对于求最小值的问题，作如下转换： 掘铲i 停? 小，慧粥乏= 注4 ， 式中，c 一为一个适当的相对较大的数。 遗传算法中，群体的进化过程就是以群体中各个个体的适应度为依据，通过一个反 复迭代的过程，不断寻求出适应度较大的个体，最终得到问题最优解或近似最优解。对 同一群体采用不同的适应度函数将直接决定优于群体平均适应度的个体和其数目。势必 影响遗传算法的整体性能”嘲。因此，适应度函数的研究设计十分重要。 2 3 遗传操作 遗传操作是模拟生物基因的操作一它的任务就是根据个体的适应度对其施加一定的 操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使阿题的解逐 代地优化，逼近最优解。 遗传操作包括以下三个基本遗传算子( g 朗e t i 脚r ) ：选择、交叉、变异。选择和 交叉基本上完成了遗传算法的大部分搜索功能，而变异则增加了遗传算法找到接近最优 解的能力。通常选择运算使用比例选择算子；交叉运算使用均匀交叉算子；变异运算使 用基本位变异算子。 改进遗传算法及在电器产品优化设计中的研究 2 3 1 选择( l e c t i o n ) 选择是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在对个体的适应 度评价的基础上，其主要目的是为了避免基因缺失、提高全局收敛性和计算效率。适应 度越大的个体，被选择的可能性就越大，个体被遗传到下一代群体中的概率也就较大j 从这个角度来看，选择操作体现了“适者生存”原理。“好”的个体被选择用来复制， 而。坏”的个体则被淘汰，然后选择出来的个体经过交叉和变异算子进行再组合生成新 的一代。这一群新个体由于继承了上一代的一些优良性状。因而在性能上要优于上一代， 这样逐步朝着更优解的方向进化。所以说，选择操作是用来确定如何从父代群体中按某 种方式选取那些个体遗传到下一代群体中的一种遗传运算因此，遗传算法可以看作是 一个由可行解组成的群体逐代进化的过程。 目前常用的选择方法有。轮盘赌方法( r o u l e t t c w h e c l m o d e l ) 、最佳个体保存法 ( e l i d s n i l o d e l ) 、竞争法( t o 啪锄e m s e l e c 哟n ) 、窗口( w i n d 0 咖鲫e l h c 曲和线性标准化方法 ( 1 i n 锄。衄a i i 盟t i o n m e t h o d ) 等” 恻。 其中轮盘赌方法( r o u l e t i 妇l l l l o d e l ) ：又称为适应度比例法，是目前遗传算法中最基 本、最常用的选择方法。本文使用的也是比例选择算子编程。它的基本思想是：各个个 t 体被选中的概率与其适应度大小成正比，其基本原理与赌博中的赌盘操作原理颇为相 似。如图2 2 所示为一赌盘示意图，与赌盘类似，在遗传算法中，整个种群被各个个 体所分割，各个个体的适应度在全部个体的适应度之和中所占的比例也大小不一，这个 比例值瓜分了整个赌盘面，它们也决定了各个个体被遗传到下一代种群中的概率。o - 一设群体的大小为n ，个体的适应度为z ，则个体f 被选择的概率只为 只= 缝乃 ( 2 5 ) 从式( 2 5 ) 可以看出，概率只反映了个体f 的适应度值在整个群体适应度总和中所 一 。 +， 占的比例，如前所述，个体的适应度值越大，它被选中的概率就越高，体现了“适者生存， 不适者被淘汰”这一自然选择原理。被选中的个体被放入配对库中，随机地进行配对，以 进行下面的交叉操作。 一1 4 沈阳工业大学硕士学位论文 比例选择算子的具体执行过程是： ( 1 ) 首先，计算出种群中所有个体的适应度的总和。 ( 2 ) 其次，计算出每个个体的相对适应度的大小它即为各个个体被遗传到下一代 种群的概率。 ( 3 ) 最后，再使用模拟赌盘操作( 即o 到1 之间的随机数) 来确定各个个体被选中 的次数。 图2 2 赌盘 f i 9 2 2g a n l b l i n gp 2 3 2 交叉( c r o s s o v e r ) 在遗传算法中，交叉是产生新个体的重要手段，仿照生物中交叉的原理，将两个个 体( 染色体) 的部分字符( 基因) 互相交叉，使遗传算法的搜索能力得到飞跃性的提高。 在交叉操作之前，必须先对种群中的个体进行配对，交叉操作是按照一定的概率p c ( 即 交叉概率，也称交叉率) 在配对库中随机地选取两个个体进行的。交叉的个体是随机的， 交叉的位置也是随机确定的。目前常用的配对策略是“随机配对，即将种群中的m 个 个体以随机的方式组成m 2 对配对个体组，而交叉率p c 的值一般取的很大，在0 6 到o 9 之间”啪1 。 改进遗传算法及在电器产品优化设计中的研究 根据交叉点的数目不同，交叉可分为单点交叉、两点交叉和多点交叉。单点交叉又 称为简单交叉，在个体编码串中只随机设置一个交叉点，该点之后的字符全部参加交叉 两点交叉在个体编码串中随机设置两个交叉点，然后进行部分基因交叉( 图2 3 ) 。多点 交叉又称为广义交叉，在个体编码串中随机设置多个交叉点，然后进行基因交叉( 如图 2 4 ) 。 a ：x xlx x x x xlx x x b ：y yiy y y y y1y y y 交叉点1交鬟点2 两点交叉 a ：x xl b ：y yi 图2 3 两点交叉 f 啦3t h o p o i n t sc r o s s x x x y y y 交叉点l交叉点2 a ：x xix xlx x xx x x 兰点交叉 a ：x xiy yix x xly y y b ：y yly yly y yly y y b ：y yfx xfy y ylx x x il _ii 交叉点l 交叉点2 交叉点3 交叉点1 交叉点2 交叉点3 图2 4 三点交叉 f i 9 24t h r c ep o i n bc r o s s 通过交换，子代的字符串不同于亲代。亲代与子代的差距不可预测，所以交叉是遗 传算法产生新个体的主要手段，正是有了交叉操作，种群的形态才多种多样。传统的优 化算法只能在原有的个体种群里择优，从而限制了搜索寻优的范围。所以，如果没有交 叉，遗传算法就失去其优越性。 在交叉过程中，单一的采用一点交叉，寻优的速度缓慢，所以适当的采用多点交叉 和变量内交叉等交叉方式，可以大大提高寻优速度。还可以加入适当的人工作用成分， 限定某些适应值高的个体，按某种规则互相交叉，快速得到适应值更高的个体，或者只 沈阳工业大学硕士学位论文 对一部分适应值较差的个体进行交叉和变异操作，产生更好的新个体来代替这部分个 体。变异也有一点变异和多点变异，有利的变异会得到遗传和保留，而不利的变异则会 被淘汰 2 3 3 变异r 一 遗传算法中的变异运算是指将各个染色体编码串中的某些基因座上的基因值用该 座的其他等位基因来替换从而形成一个新的个体i 具体的说，变异就是以很小的概率 p l n ( 变异概率，即变异率) 随机地改变群体中个体( 染色体) 的某些基因的值，变异操作的基 本过程是对于交叉操作中产生的后代个体的每一基因值，产生一个【0 ，l 】之间的伪随机数 棚讧如果瑚d 四i m ，就进行变异操作。在二进制编码方式中，变异算子随机地将某个基因 值取反，即“o ”变成“l ”，或“1 7 变为“o ”。例如：个体s = l o l o l l 0 0 l l l o o l ，对其 ， t， 的第1 、4 、1 1 位置的基因进行变异，则有= 0 0 1 1 1 1 0 0 “0 0 0 l 。 变异本身是一种局部随机搜索，变异的目的在于改善遗传算法的局部搜索能力。由 于变异算子用新的基因值替换原有的基因值，可以改变个体编码串的结构，维持群体的 多样性，因此，变异操作也是一种防止算法早熟的措施。事实上，遗传算法采用交叉算 子已经从全局的角度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问 t 题的最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。此时，使用变异 算予来调整个体编码串中的部分基因值，就可以从局部的角度出发使个体更加逼近最优 ， 、 解，从而提高了算法的局部搜索能力。同时，变异算子与选择、交叉算子结合在一起。 能避免由于选择和交叉算子而引起的某些信息的永久性丢失，保证了遗传算法的有效性， 使遗传算法保持群体的多样性，防止出现未成熟收敛。在变异操作中，变异率不能取的太 大，如果p m 0 5 ，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特性和搜索 能力也就不复存在了。 2 3 4 遗传算法的运行参数 遗传算法控制参数一般有群体大小，交换概率，变异概率等，这些参数对遗传算 法的求解结果和求解效率都有一定的影响。 p o p - s i 霉：种群大小，即种群中所含个体的数量，。般取为2 0 1 0 0 。 改进遗传算法及在电器产品优化设计中的研究 e m n 眦 ：遗传运算的终止进化代数，