（固体力学专业论文）改进的遗传算法及其在工程优化中的应用.pdf

西南交通大学博士研究生学位论文第1 页 摘要 进化计算，作为一种新兴的强大的智能优化技术，已经广泛地应用在工程 科学的几乎所有的领域。与传统优化方法相比，进化计算在全局优化、复杂设 计区域、复杂目标函数及易用性等方面都显示出了其优越性。遗传算法是进化 计算中最重要的算法之一，本文主要研究了改进的遗传算法及其在工程优化领 域中的应用。 本文的主要研究内容分章介绍如下： 第一章首先简要介绍了进化计算的基本知识，在工程优化领域的历史与研 究现状。本章的最后给出了本论文的基本框架。 第二章介绍了遗传算法的基本理论与方法。首先给出了遗传算法的基本流 程，然后介绍了染色体的编码方法及遗传算子，最后分析了遗传算法的搜索机 理与收敛性。 第三章提出了一种新的遗传算法基于子域搜索的遗传算法( 简称为 s b g a ) 。s b g a 将设计区域分成多个小的子域，根据已搜索过的样本点在这些 子域内的分布情况来指导后续的搜索。同时，s b g a 还提供了一种新的处理约 束的方法。应用s b g a 进行了复杂函数和杆系结构的优化，数值实验还发现它 能够有效地抑制早熟现象的发生。 第四章研究了基于遗传算法的连续体结构拓扑优化问题。提出了一种新的 变长的紧凑编码方式链码编码方法，用四方向链码的组合来描述结构拓 扑。以机器学习中的范例推理为原型，设计出一种基于范例推理的遗传算法。 在该算法中，根据多尺度变换的原理，提出了结构拓扑的“目标向量”描述方 式，从而可能定量地描述不同拓扑的相似性。研制了上述方法的计算机软件 g a t o c s ，并利用该软件对多工况连续深梁和自行车框架进行拓扑优化，取得 了较为满意的结果，从而说明了应用遗传算法进行连续体结构拓扑优化是完全 可行的。 第五章研究了多目标遗传算法及其并行实现。实际的工程优化问题通常都 是多目标的，而且计算量很大。因此，本文研究了并行虚拟机( 高速互联机 第1 i 页 西南交通大学博士研究生学位论文 群) 环境下的多目标遗传算法s p e a 2 的分布式实现，开发了并行的s p e a 2 的 算法，并且完成了深梁的多目标拓扑优化。 第六章研究小生境技术在遗传算法中的应用。设计了基于小生境技术和局 部搜索算法的混合遗传算法，应用“互信息”作为目标函数实现了多模态医学 图像的配准。 第七章是全文的结论、创新点与展望。 关键词： 遗传算法并行计算拓扑优化 图像配准 西南交通大学博士研究生学位论文 第1 i i 页 a b s t r a c t e v o l u t i o n a r yc o m p u o n ( e c ) ，船an o v e la n dp o w e r f i l l i n t e i l i g e n to p t i m i z a t i o n t e c l l l l o l o gy ，h a sb e e nu t i l i z e de x t e n s i v e l yi na l m o s te v e r yb r a n c hi ne n g i n e e r i n g s c i e n c e i tl l a sm o r ea d v a n t a g e so v e rt r a d i t i o n a lo p t i m i z a t i o nm e t l l o d sw h e ns o l v i n g p r o b l e m sw i mg l o b a ls e a r c h ，c o m p l e xd e s i g nd o m a i n拍dc o m p l i c a t e dt 雏g e t f h n c t i o n s ，a n di ti se a s i e rt ou s e g e n e t i ca l g o r i t l l m ( 0 a ) i so n eo f t l l em o s ti m p o r t 锄t a 1 9 0 r i t l l m si ne v o l u t i o n a r yc o m p u t a t i o n a ne x t e f l s i v es t u d yo fi m p r 0 v e dg e n e t i c a i g o r i t h m si nm ec o m e x to fe n g i n e e r 抽go p t i m i z a t i o nd e s i g nh a sb e e nc o n d u c t e di n t h i sd i s s e r t a t i o n t h ed i s s e n a t i o ni so r g a n i z e da sf o l l o 谢n gc h a p t e r s f i r s t ，ag e n e r a li n t r o d u c t i o nt og e n e t i ca l g o r i t l l m si sp r e s e n t e di nc h 印t e r1 ，趾d t l l ep a s ta 1 1 dr e c e n td e v e l o p m e n t si nt h i sf i e l da r eb r i e n yd e s c r i b e d t h ef h m e w o r ko f t h ed i s s e r t a t i o ni sa i s of i g u r c do u ti nt h ee n do f c h a p t e r1 n e x t ，t h e o r e t i c a la s p e c t sa n di m p l e m e n t a t i o no fg e n e t i ca l g o r i m m sa r ef o c u s e d o ni nc h a p t e r2 t h eb a s i cw o r k f l o wo fg e n e t i ca l g o r i 血m si sd e s c r i b e da tt h e b e g i 皿i n go ft l l i sc h 印t c r ，蛐dt h e nt y p i c a lr e p r c s e n t a t i o na l l dg e n e t i co p e r a t o r sa r c d i s c u s s e d f i n a l l y ，t l l es e a r c hm e c h a m s m 缸dc o r e r g e i l c e 甜ei n v e s t i g a t e di n 出ee n d o f t l l ec h a p t e r n e x t ，an o v e lg e n e t i ca l g o r i c a l l e ds u b d o m a i nb 踮e dg e n e t i ca l g o r i m m s ( s b g a ) i sp r o p o s e di nc h a p t e r3 i ns b g a ，d e s i g ns p a c ei sd i v i d e di n t om a n ys m a i l 趾di s o l a t es d b d o m a i n s 强dd i s t r i b u t i o ni n f o n n 砒i o ni nt h e s es b d o m a i n sw i ub e t r a c e di n 也ep r o c e s so f “o l u l i o n ，w i l i c h 、v i l lb eu s c dt og u i d es u b s e q u e n ts e 盯c h a t m es 锄et i m e ，s b g aa l s op r o v i d e san e wm e t l l o dt oh a n d l ec o m p l i c a t e dc o n s t r 证n 乜 t 1 1 en 啪e r i c a l 他s u l t sd e m o n s 仃a t et l l a ts b g ai se f f c c t i v ea n de 瓶c i e n tt oa l l e v i a t e p r e m a t u r ec o n v e r g e n c e n e x t ，g ab a s e dt o p o i o g yo p t i m i z a t i o nm e m o d so fc o m i 肌呦s 仇l c t u r e sa r e s t u d i e di nc h a p t e r4 an e wc o m p a c tr e p r e s e n t a t i o nc a l l e df o u rd i r e c t i o nc h a i nc o d e r e p r e s e n t a t i o ni sp r o p o s e di n “sc h 印t e r ，她dc 船e b 觞e dg e n e t i ca l g o r i t h n l s e n l i g h t e n e db ym a c l l i n el e 锄i n ga r cd e v e l o p e d ，i n 、v h i c han c wc o n c e p tn a m e d t 盯g e tv e c t o r i su t i l i z e dt oc a l c u l a t et h ed i s t a l l c eb e t w e e nt w os t n l c t u r e sw i t l l 第1 v 页西南交通大学博士研究生学位论文 d i 航吲吐t o p o l o g y t h ee x p e c t e dr e s u l t sa r eo b t a i n e dw h e na p p l y i n ga b o v e 印p r o a c h t oc o n t i n u u mb e a ma n db i k ef r a m e 、v o r kt o p o l o g yo p t i m i z a t i o n n e x t ，p r a c t i c a le n g i i ”e r m g 叩t i m 砌p m b l e m sa r eo fm o r et l l 孤o n et a r g e t f h n c t i o n sa n dc o m p u t a t i o n a lc o s ti sv e r yh i g h ，s om u l t i o b j e c t i v eo p t i m i z a t i o nm e t l l o d s a r ed i s c u s s e di nc h a p t c r5 t oi m p r o v ec o m p u t i n gp e f f o r n l a i l c e ，ap a r a u e lv e r s i o no f i m p m v c ds t r e n g 廿1e v o l u t i o n a r ya l g o r i t 啦s ( s p e a 2 ) i sp r e s e n t e dt oo p t i m i z eb e a i l l t o p o l o g yw i mt w oc o n n i c t i i l gt a r g e t so nt t l ee n v i r o 呲e n to fc l u s t e ro fw o r k s t a t i o n s c o n n e c t e dw i t l le a c ho t l l e r n e x t ，ah y b r i dg e n c t i ca l g o r i t h mi sp r o p o s e dw h i c hc o m b i n en i c h ea n dl o c a l s e 挑ht e c h n i q u e si nc h a p t e r6 “m u t u a li n f b 瑚a t i o n ”i si “呐d u c e dt oc a l c u l a t et l l e m a t c h i n gd e g r e eo ft w om e d i c a ii m a g e sf b md i 庙：r c n tm o d a l m e sa i l dv e r yg o o d r e s u l t sa r eo b t a i n e d f i 砌l y ，as 啪m 舡yo f 廿l e s e 甜c hc o n c l u s i o n s ，al i s to fi 衄o v a t i o np o i n t sa n da d i s c u s s i o no nt h em o s tp r o m i s 洫gp a t h so f 如t u r er e s e a r c ha r ea l s op 陀s e n t e di n c l l a p t e r7 k e yw o r d s ：g e n e t i c 舢g o r i t h m s ，p 盯a l l e lc o m p u t i n g ，t o p o l o g y0 p t i m i 豫t i o n ，i m a g e r e g i s t 髓血o n 西南交通大学曲南父通大罕 学位论文版权使用授权书 本学位论文作者完全了解西南交通大学有关保留、使用学位论 文的规定，同意学校保留并向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可以 将本学位论文的的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文授予 1 保密口，在一年解密后适用本授权书； 2 不保密翻，适用本授权书。 ( 请在以上方框内打“”) 学位论文作者签名：葛舞碉指导溯签名： 日期：妒6 年月f 珀日期：_ 年6 月日 西南交通大学博士研究生学位论文 第l 页 1 1 遗传算法概述 第1 章绪论 1 1 1 遗传算法的仿生学基础 根据达尔文的进化论i “，生物种群从低级、简单的类型逐羹鎏垂莛霎蒌 裁，髫螽警谶遵，秘皖”酗* 薯蘸蜒蓁囊耍熏萋薹霎囊鬟泰：a 暂篓囊蕊枣藉 羲i 萎羹点塞萋刘蜜謇萎司二毒嚣銎萋耄萎萃蠹辇蠹霉；萋霎蓉翼蓊萎a 篓葡 皤攀耄藉茎壅；霎墓墓委霎霎荔墓羹襄鍪羹奏囊i 誊m 誊1 柏0 4 0 h ，s p s d1 女s p c r 2 ls ub a d d r ，s p s a l 撑0 0 4 1 h ，s ps d l 4 4 。4a i c 23 的初始化及应用 g r s t = 1 ，启动采样率发生器 ；x r s t = 1 ，启动m c b s p l 的发 送端 t l v 3 2 0 a1 c 2 3 内部有1 1 个可编程控制寄存器( 参见表4 2 ) ，通过不同设 置，可以改变芯片的工作状态，如采样率、左右声道音量等。在本系统中， 这些寄存器都是以s p i 接口方式通过a 1 c 2 3 的控制接口来编程的。s p i 接口 模式是三线串行传输方式，s d l n 为输入串行数据，s c l k 为串行时钟，控 制字共1 6 位，由高位开如传输，在时钟的上升沿锁存每一位数据。控制字分 为两个部分：高7 位b 1 5 b 9 是寄存器地址，低9 位b 8 - b 0 是写入寄存器中 的控制数据。寄存器设置完成后，再通过m c b s p o 读写转换的数据。 表4 2a j c 23 寄存器控制模式 地址寄存器 0 0 00 0 0 0左输入声音量控制 0 00 0 0 0 1 西南交通大学博士研究生学位论文第5 页 于复杂的应用问题，我们需要遗传算法同时具备这两种能力。因此，遗传策略 的研究与设计是一个极为重要的研究方向。根据目前的研究状况，我们可以将 之分为微观遗传和外；矍- 蹩斛；? 亘一f 萎窆耄薹辇霎霭| 丑g i 餐i i ； i 塞誊。黟自霎磊塑薛； 红魁露语首处理番统语音珏醺酮罐雏酣霉羹鲋酬静i 得葵叁爱禽培垤蜇 潞模 块、逻辑控制模块等功能部 分。在使用汇编语言仿真该声回波抵消算法性能的基系统进行了实时实现。 x 第6 页西南交通大学博士研究生学位论文 拓扑优化的研究可以追溯到二十世纪七十年代末，主要以传统的确定性算 法为主。通常拓扑优化可以分为连续体拓扑优化( c o m i n u u mt o d ) 和离散拓 扑优化( d i s c r e l et o d ) 两大类。在连续拓扑优化里，一般将设计区域离散成 很多小的矩形单元格，单元格里可能填充材料，也可能不填充，根据材料的分 布情况可以抽象出结构的拓扑。传统的连续体拓扑优化方法主要有均匀化方法 【蚓( h o m o g e n i z a t i o nm e t i l o d ) 和进化结构优化方法1 3 7 l ( e v o l u t i o n a r ys t n l c t t l r a l o 舐m i 孤t i o nm e t h o d ) 。均匀化方法假设在单元格里填充具有0 1 之间连续密度 的材料，然后优化材料的密度分布，最终通过设置一个阈值以确定哪些单元格 里有材料，哪些单元格里无材料。均匀化法只能用于线弹性结构，很难处理承 受多个荷载的结构，而且也不能应用于受到连续边界荷载的结构。进化结构优 化方法的名字容易引起误解，其实它并不是基于进化计算的，而是逐渐删除应 力较小的材料从而形成优化的拓扑。 当遗传算法应用于结构优化设计时，有三个主要的问题需要解决： i ) 选择合适的结构表达方法( r e l 玳s e n t a t i o n ) ； 2 ) 定义有效的遗传算子( o p e r a t o r ) ： 3 ) 有效的结构分析技术。 结构表达方式是应用遗传算法进行结构设计时遇到的第一个重要问题。设计 结构的合适的表达方式是一个相当复杂的问题，它不仅要考虑搜索空间与设计 空间的映射关系，包含关系，还要考虑结构的可拓展性以及搜索的有效性等。 遗传算子的设计高度依赖于结构的表达方式( 编码方案) ，对于遗传算法的成 功执行起着至关重要的作用。结构分析技术一般都采用有限元方法，对于连续 体结构拓扑优化，自适应网格划分技术的性能至关重要。 s 锄d g r e n 和j e n s c n 哪”l 应用遗传算法进行了连续t o d 方面的研究，他们用 二进制编码对具有位移和应力约束的悬臂梁进行了拓扑优化，取得了较好的结 果。c h 印m a n 【3 9 】等扩展了他们的研究，用遗传算法获得了一系列的满意解。近 几年来，人们对更加高级的结构拓扑表达方式进行了研究，其中最为著名的有 基于v o r o n o i 图的拓扑描述方式【4 “4 2 l 和基于分形理论的i f s 拓扑描述方式、 v o m n o i - b a r 拓扑描述方式阳j 。应用多目标遗传算法和并行遗传算法等高级遗传 算法进行连续t o d 的研究不多m 。综上。应用遗传算法进行连续t o d 的研究 不多，尚处于研究的初级阶段。 西南交通大学博士研究生学位论文第7 页 图1 1 二进制编码表示结构拓扑图mv o m n o i 图表示结构拓扑 图l _ 3v o r o n o i - b a r 表不结构拓扑 离散t o d 问题是确定有限数目单元的可能连接的数目及方式，主要应用于 框架结构的拓扑优化。在早期的研究中主要用传统的线性规划法，并取得了 不错的效果【4 5 】。但随着问题规模的不断增加，线性规划法的表现也越来越差 劲。离散t o d 问题中变量的不连续性也使得传统算法无法发挥作用。早在 1 9 8 6 年g o l d b e r g 和s 锄t 觚i 就用遗传算法进行了十杆桁架结构的优化【6 9 】。 s h a l l l 【一4 6 】和h a j e l a 【4 7 l 等将遗传算法应用于桁架结构拓扑优化，k o u m o u s i s 和 g e o r 西o u 【4 8 】应用g a 优化了钢结构的拓扑。b o h n e n b e r g e r 【4 9 1 等应用g a 对铁塔的 结构拓扑进行了优化。r 司a n 【5 0 】应用遗传算法对桁架进行了拓扑、形状和尺寸优 化。r 旬e e v 【5 l l 应用了变长二进制串的编码方案进行了桁架的拓扑优化。肠d 等 p 2 j 应用实数编码方案对三维桁架进行了拓扑优化。基于遗传算法的离散t o d 的 研究要相对成熟一些，已有多种编码方案的研究，不仅涉及二维问题，还有不 少三维问题方面的研究。 在t o d 实际应用方面，多年来一直偏重于理论和方法，疏于软件系统的开 发，尽管已有b a n h o l o m e w 的s t a r s 系统降3 1 。国内的d d d u 系统【5 4 1 ，p a i m 和 y a l l g 用遗传算法开发了系统t i 认d e s 【5 5 】，并介绍了共享、等同串去除和紧缩膨 胀三个新的遗传算子。l 涵和h a j e l a 也开发了基于遗传算法的优化设计工具并 称之为e v o l v e 【5 6 1 ，具有自动编码和解码的能力，能够处理整形、连续型和离 第8 页西南交通大学博士研究生学位论文 散型混合变量。但总体来讲，实际应用远远落后于理论。从c a d ( 计算机辅助 设计) 到c a e ( 计算机辅助工程) 、c a m ( 计算机辅助制造) ，计算机就为我 们提供了巨大帮助。但它们都只应用于详细设计阶段。近年来，在欧美国家发 明问题解决理论( t l l et h e o r yo fi n v e n t i v ep r o b l e ms o l v i n g ，t r i z ) 得到了迅猛 发展，以此为基础的计算机辅助创新c a i ( c o m p u t e ra i d e dl 衄o v a t i o n ) 技术在 在概念设计阶段对设计加以支持。遗传算法在c a i 将扮演非常重要的角色。 1 3 进化结构优化中的约束处理方法 无论是拓扑优化，还是形状和尺寸优化，绝大多数问题都是带约束条件 的。约束的正确处理对于搜索机制的正常发挥有着重大影响。但另一方面，遗 传算法执行的是一个非约束的优化过程，因而需要将约束处理方法融进遗传算 法。c o e l l o 呻1 将遗传算法中已有的约束处理方法分为五类： 1 ) 罚函数法( p e n a l t yf u n c t i o n s ) 2 ) 特殊的编码方案与遗传算子( s p e c i a lr 印r e s e n t a t i o na n do p e r a t o r s ) 3 ) 修卒h 算法( r e p a i ra l g o r i t h m s ) 4 ) 目标函数与约束分离法( s e p a r a t i o no fo b j e c t i v ea n dc o n s t r a i n t s ) 5 ) 混合方法( h y b r i dm e t h o d s ) 在g a 中，罚函数法是最常用的约束处理方法啪1 。罚函数法最早是由 c 0 u r a n t 引入并应用在传统的数学优化方法中嘲1 。在8 0 年代罚函数法被引入 遗传算法。自此以后便成为遗传算法约束处理方法中不是最好，但是应用最 广泛的方法1 。罚函数法通过对目标函数施加惩罚项从而将约束问题转化为非 约束问题。到目前为止，已提出了很多种罚函数方法，列举如下： 1 ) 静态罚函数“。：进化过程中罚因子保持不变； 2 ) 动态罚函数旧1 ：进化过程中罚因子不断变化。通常随进化时间的增加而 增大： 3 ) 退火罚函数m 1 ：运用模拟退火的技术： 4 ) 自适应罚函数“”：根据进化过程的反馈来设定罚因子的大小； 5 ) 协同进化罚函数汹1 ：目标函数和罚因子分别在两个群体中各自独立进 化： 6 ) 直接拒绝罚函数“”：直接删除不可行解。 西南交通大学博士研究生学位论文 第9 页 罚函数的设计是一个富有挑战性的问题，r i c h a r d s o n 等1 进行了大量的数 值实验研究，并提出了几点经验： 罚函数可以是到可行域的距离，也可以是违反约束的程度，但通常情况 下前者的效果要好于后者； 对于约束较少、可行解也较少的问题，仅靠罚函数法不太可能找到最优 解： 高性能的罚函数可以依据到可行域的最远距离和期望距离来构建； 但是，很多的实际应用也表明基于罚函数的约束处理法还存在许多困难， 例如合适的罚因子难以确定等8 “。 通过设计特殊的编码方案和遗传算子保证产生的所有个体都在可行域内从 而使约束得到处理“。m i c h a l e w i c z 建议搜索仅限制在可行域的边界，因为很 多情况下全局最优解位于可行域的边界处。但这种方法不太适合结构优化，因 为约束条件的值通常是通过有限元软件包计算出来的，很难事先确定可行域的 边界。m i c h a l e w i c z 等m 1 用解码器来处理约束，这种方法要求染色体编码要包 含如何创建可行解的规则，解码时建立解个体与可行解的映射关系。 修补算法特别适合于组合优化问题“，尤其适合于当一个不可行解可以很 容易地转化为可行解的问题。d ej o n g 等”在高层建筑的钢结构进化设计中应 用了修补算法来此法处理对称性约束条件。 基于目标函数与约束分离的约束处理酬方法是近年来的研究热点之一。 p a r e d i s ”用竞争协同进化策略处理约束，一个群体用于潜在解的进化，另一个 群体用于约束条件的进化。s u r r y 等1 将约束条件视为进化的目标从而将带约 束的目标优化问题转化为多目标优化问题。 约束处理的混合方法中，最有影响力的当属模糊逻辑法”和免疫法”。前 者是将遗传算法与模糊逻辑相结合，用模糊约束取代原来的确定性约束，从而 使算法对约束有一定的容忍性。免疫法最初是在多目标优化中用于保持个体间 的多样性，后被扩展用于处理约束问题。“。 1 4 多目标遗传算法与结构优化 多目标遗传算法( m u l t i p l e0 b j e c t i v eg e n e t i ca l g o r i t h m ，简称m o g a ) 是近 年来的比较活跃的研究领域之。m o g a 可以应用予结构优化，因为实际的结构 第1 0 页西南交通大学博士研究生学位论文 优化问题常常需要同时考虑两个或更多个相互冲突的目标函数，例如同时要求 结构的重量最轻、位移最小。 多目标优化( m u n i p l eo b j e c t i v eo p t i m i z a t i o n ，简称m o d ) 有两个主要目 标，其一是给出尽量多的p a r e t o 解，其二是p a r e t o 解集具有良好的分布性。 传统的加权和法“”不能满足这两点要求，因为算法运行一次只能给出一个解， 不能保证解的分布性。而遗传算法基于群体的特性使得遗传算法特别适合于 m 问题。 早在1 9 8 5 年，s c h a f f e r 就提出了向量评估遗传算法m 1 ( v e c t o re v a l u a t e d g e n e t i ca 1 9 0 r i t h m ，简称v e g a ) ，v e g a 改变了简单遗传算法的选择机制从而同 时处理多个目标，c v e t k o v i c 等m 1 在飞机结构的概念设计阶段应用了v e g a 方法。 f o n s e c a 等“提出了多目标遗传算法( m u l t io b j e c t i v e g e n e t i c a l g o r i t h m ，简称m o g a ) ，在m o g a 中，给每个个体都分配一个级，当前代同一 级中的个体互为非劣( n o n d o m i n a t e d ) 。c h i p p e r f i e l d 等o ”应用m o g a 进行蒸 汽涡轮引擎控制器的优化设计。超音速飞机的机翼优化设计也有m o g a 的身影 m 1 。对m o g a 的一个改进算法用于办公楼的概念设计m 1 。 s r i n i v a s 和d e b 于1 9 9 4 年提出了非劣排序遗传算法( n o n d o m i n a t e d s o r t i n gg e n e t i ca l g o r i t h m ，简称n s g a ) ，该算法借用了g 0 1 d b e r g 提出的非 劣顺序”1 的概念。d e b 等人在2 0 0 0 年改进了n s g a 算法，将精英策略和参数共 享的方法融入其中，并称这种改进过的算法为n s g a i i 。”。n s g a i i 应用于悬臂 深梁结构的拓扑优化，目标是使其重量和最大位移同时最小化呻1 。 n p g a ( n i c h e dp a r e t og e n e t i ca l g o r i t h m ) 也是一种得到广泛应用的多目 标遗传算法旧3 。n p g a 采用基于p a r e t o 支配的锦标赛选择策略。两个竞争个体 和一个比较集( 大小由一预定义的参数决定) 是从群体中随机选择的，如果第 一个竞争个体被比较集中某一个体支配，而第二个竞争个体不被比较集中任一 个体所支配，则第二个竞争个体取胜。如果两个竞争个体都没被支配，则根据 共享原则决定胜负：个体所在的小生境个体数目最小的取胜。 1 5 并行遗传算法 随着科学技术的不断发展，所求解的问题的规模也越来越大。面对复杂而 庞大的探索空间，遗传算法从优化效率和求解质量上都有点“力不从心”。幸 酉南交通大学博士研究生学位论文 第1 5 页 第2 章遗传算法的基本理论与方法 2 1 遗传算法的基本流程 遗传算法是一种基于自然选择和遗传机理的具有统计特性的现代优化算 法。和传统优化算法不同，遗传算法的搜索过程是基于群体的。遗传算法从一 组随机产生的初始解群体开始搜索，通过交叉和变异算子来产生后代，通过选 择算子进行优胜劣汰。每一代中都仅仅依靠适应值来衡量个体的好坏。经过若 干代以后，算法收敛至搜索到的最优个体。简单g a 的基本流程可用下图描述： 图2 1 遗传算法的基本流程 简单g a 的有几个不同于传统优化方法的显著特征： 1 ) 遗传算法在编码空问内执行，而非解本身所在的空间 2 ) 遗传算法的搜索始于一个种群，丽非单个解： 第2 0 页西南交通大学博士研究生学位论文 通过上式可以得到下述结论： 定理2 1 ( 模式定理) 在标准遗传算法中，具有低阶、短定义长度j 离 爨斩 薛断品琴舒筵辖箨蒹寺翕笨重话疆璎要章。 隧璎缮薹目节目e l 藿i l 型一酲即r ：溺艘醐趟髓羹箨躺蚤毫理蟆灌耀翻峨i 暇型匕种群薹镯添蹈攫薹孽矗潜。* 嚣警撵次霉耋凳霉豫峨薏t 珥缨毯鳟堪濡 嗡噬速1 蓬曦逝睡噬投翼嘱合 交叉和单峰正态交叉等，它们 与二进制编码的交叉方案不同，二进制编码交叉算子的搜索能力仅限于当前种 群所诱导的模式，而从理论上可设计出能够搜索整个设计空间的交叉算子，但 已经失去交叉的意义而变为随机搜索。变异算子可按某概率对某基因做随机或 正态的变异。一般而言，如果变异概率很小，则不足以使种群发生显著改变。 基于以上几点认识，我们认为，当交叉和变异的作用不足以抵消选择算子所引 起的种群多样度的减少时，过早收敛就会发生。 g a 在找到最优解之前往往要进行成千上万次的适应度计算，如果求解的 问题目标函数的计算复杂度很大，会导致g a 收敛的时间不可接受。除了采用 并行计算以外，还要想办法减少一些不必要的计算，如重复的适应度计算，非 可行解的适应度计算等。然而，如何判断某个个体或其相似的个体的适应度已 经在前面的搜索过程中计算过，并不是一个容易的问题，除非记录下所有已搜 索过的个体，但由于空间和时间的有限性，这个目标不可能达成。如何判断某 个体是否在非可行域也是一个很难的问题，因为通常只有计算完所有的约束条 件以后才能知道该个体是否在非可行域。 本章提出了子域搜索的遗传算法，在某种程度上可以克服上述两个问题。 3 2 2s b ga 的基本思想及其实现 由于g a 搜索存在随机性，新产生的个体可能会更好，不好不坏，也可能 会更坏。第1 代到第1 0 0 代的进化和第1 0 0 0 代到第1 1 0 0 代的进化本质上并无 多少不同，因为ga 对其前面已搜索过的路线没有记忆性。由于某种原因，g a 可能在某一小块没有潜力的区域做很多无效的运算，或者频繁地在非可行域内 产生新个体，从而 x 西南交通大学博士研究生学位论文第2 l 页 成立： 3 ) 称 k ) 依概率收敛到o ，如果对v f o ，有嫩p 以( 脚) 占) = o 成 立。 上述定义的三种收敛形式中，完全收敛最强，它蕴涵了以概率1 收敛和依 概率收敛，而依概率收敛最弱，因为由以概率1 收敛可推出依概率收敛。如果 再定义 d ，= d ( x ，) = ，一e x 第2 2 页西南交通大学博士研究生学位论文 则遗传算法以概率1在有限次进化后访问到整体极值点，亦即尸(丁o=兀(1一p(f)(2一lo)当r斗o。时，由假设21可得：limp口o=o，即谨明了ga依概率收敛。 西南交通大学博士研究生学位论文第2 3 页 如果存在一个常数p “ 0 ，使得对所用的f ，成立p ( ，) p “，式( 2 1 0 ) 可变 为 i p d | 蓦辇& 琴薹l | 一萋g ：雾i 一囊g i i | 一g ! | 裂翳剿蚓馨蓁i i 一雾。i ；薅哩- 剥既登鲧| 薹接暨葚誊姜箱- 酣甜谳招萎习忽喙 一理嘱哩强l 錾丢芫羹u 需赛篓孬简篓j 增堡i 霆疆必明缎释驷秘掣勰雒；堡童p 戡影f 画刊孵副雾厂() 占， 又因为，( 而) 厂( ) ，所以 ，( 工) 一厂(一) ，( x + ) 一厂( z o ) 占， 所以z 。也是，(功的一个任意满意解。证毕。 定理3 2 ：采用s b g a 求解最大值优化问题，( x ) 时，如果子域无限小且目标函数 在最优点可导，且满足三终止条件，则s b g a 可以找到任意满意解。 证明：设x 为问题的最优解，包含在子域e 内，因为算法满足三终止条件，故 e 内至少有一个样本点，并假设e 内最好的样本点为。因为和z 在同一个 无穷小子域内，它们之间的欧氏距离为 o “ f x 。j 蔓、( “一) 2 x 时，有 ，(x ) 一，( x 。) = d i x + 一x 。i d 占 0 ，并根据以下几条启发式规 则确定落在该子域内的一个新样本点是否需要评估： 规则1 )如果该子域内的样本数小于 况，新点需要评估； 规则2 )如果该子域内的样本数等于【，新点不需要评估，寻找样本点 数量最小的子域，并在该子域内随机产生一个样本点； 规则3 ) 如果该子域内的样本数大于 配同时小于u ，则寻找该子域内已 有点的最大适应值，如果该最大适应值超过预先设定的某个阈值 7 ，则新点需要评估，否则，新点不需要评估。 规则4 )如果某子域内m 个点均为不可行点，则将该子域标记为b a d 子 域，以后产生的新样本点如果落入该子域内，均视为不可行点， 并寻找样本点数量最小的子域，并在该子域内随机产生一个样本 点。 规则1 ) ，2 ) 和规则3 ) 使群体中的个体具有适当的分散性，避免过早收 敛，同时诱导算法不断探索新的子域；如果待求问题评估个体适应度计算量很 大，可以变通规则2 ) 的内容，利用响应面近似的相关技术获得适应度的近似 值，提高计算的效率；规则4 ) 提供了一种处理复杂约束的有效方法，同时也 有助于找到更稳定的个体。根据上述规则可建立一个可行的终止条件：如果包 含最少个体数的子域中所包含的个体数达到上( 三为一自然数) 即终止搜索， 称之为三终止条件。 西南交通大学博士研究生学位论文第2 9 页 解的传递性，x 。是，( 曲的任意满意解。证毕a 3 3 数值仿真 3 3 1 复杂函数优化 文献 7 0 提供了几个典型的优化测试问题，它们都是高维的并且带有复杂 的等式或不等式约束条件，本章运用s b g a 进行了四个测试问题( f l f 4 ) 的求 解，并与文献 7 0 的优化结果进行了对比。 1 ) 测试问题f l ： 最，j 、化： f 1 ( 砷= 3 z l + o 0 0 0 0 0 1 石1 3 + 2 x 2 + ( 0 0 0 0 0 0 2 3 ) x 2 3 约束条件为： 工4 一x 3 + 0 5 5 0 ， 一x 4 + x 3 + o 5 5 0 1 0 0 0 s i n ( 一工3 0 2 5 ) + 1 0 0 0 s i n ( x 4 一o 2 5 ) + 8 9 4 8 一x i = o l o o o s i n ( x 4 一o 2 5 ) + 1 0 0 0 s i n ( x 4 一x 3 0 2 5 ) + 1 2 9 4 8 = 0 1 0 0 0 s i n ( z 3 一o 2 5 ) + 1 0 0 0 s m ( b x 4 一o 2 5 ) + 8 9 4 8 一z 2 = 0 o 蔓工l ，x 2 1 2 0 0 ，一o 5 5 工3 ，z 4so 5 5 2 ) 测试问题f 2 ： 最小化 f 2 ( x ) = ( 石i 一1 0 ) 2 + 5 ( x 2 一1 2 ) 2 + 工，4 + 3 ( x 4 1 1 ) 2 + 1 0 x s 6 + 7 x 6 2 + x 7 4 4 x 6 x 7 一l o x 6 8 x 7 约束条件为： 1 2 7 2 x l2 3 工2 4 一x 3 4 x 4 2 5 x 5 0 1 9 6 2 3 x l x 2 2 6 x 6 2 + 8 x 7 o 2 8 2 7 x i 一3 x 2 1 0 x 3 2 一h + x 5 o 一4 x 1 2 一x 2 2 + 3 x l x 2 2 x 3 2 5 x 6 + 1 1 x 7 o 一1 0 x l o ( i = l ，7 ) 3 ) 测试问题f 3 ： 最，j 、化f 3 ( 工) = 工- + x 2 + x 3 约束条件为： 一1 + 0 0 0 2 5 ( x 4 + x 6 ) o ， 一l + o 0 0 2 5 ( x 5 + x 7 一x 4 ) s o l + o 0 1 ( x b x j ) s 0 ， 一而x 6 + 8 3 3 3 3 2 5 2 x 4 + 1 0 0 而一8 3 3 3 3 3 3 3s o x 2 x 7 + 1 2 5 0 x 5 + x 2 x 4 一1 2 5 0 x 4 o ， 一x 3 x 。+ 1 2 5 0 0 0 0 + x 3 工s 一2 5 0 0 x 5 o 1 0 0 _ s 1 0 0 0 0 ，1 0 0 0 工2 ，x 3 1 0 0 0 0 ，1 0 s x ，s 1 0 0 0o = 4 ，- ，8 ) 4 ) 测试问题f 4 ： 最小化 f 4 ( x ) ：x l2 + x 2 2 + x i x 2 一1 4 t 1 6 x 2 + ( 屿一1 0 ) 2 + 4 ( x 4 5 ) 2 + ( x s 一3 ) 2 十2 ( 一1 ) 2 + 5 x 7 2 十7 ( x 8 1 1 ) 2 + 2 ( x 9 1 0 ) 2 + ( x l o 一7 ) 2 + 4 5 约束条件为：1 0 5 4 z l 一5 x 2 + 3 x 7 9 x 8 o ， 一3 ( x l 一2 ) 2 4 ( x 2 3 ) 2 2 x 3 2 + 7 x 4 + 1 2 0 o 一1 0 x l + 8 x 2 + 1 7 x 7 2 x l o ， 一x 1 2 2 ( x 2 2 ) 2 + 2 _ x 2 一1 4 工5 + 6 x 6 o 8 x t 一2 x 2 5 h + 2 x l o + 1 2 o ， 一5 x 1