（工程力学专业论文）免疫遗传算法研究及其在桁、框架结构优化设计中的应用.pdf

山东建筑大学硕士学位论文 摘要 结构优化设计迄今已有近百年的历史。在最近的四十年内，无论从其理论、算法还 是在应用方面，结构优化设计都取得了很大的进展。特别是近年来遗传算法在结构优化 设计领域的广泛应用，更使得结构优化设计水平达到一个新的高度。 遗传算法是一种模拟自然界生物进化的搜索算法，由于它简单易行、鲁棒性强，尤 其是不需要专门的领域知识而仅用适应值函数作评价来指导搜索过程，因而成为近年来 在优化领域中受到广泛关注的一种新型智能优化方法。但是在利用遗传算法进行结构优 化设计时，常常存在早熟收敛和收敛性能差等问题。很多学者和研究人员都尝试采取各 种措施来改进遗传算法，其中，近年来出现的免疫算法为改进遗传算法的上述缺陷提供 了一条新途径。 本文尝试利用免疫算法的相关理论对遗传算法进行改进，并将改进后的算法应用到 土建结构优化设计当中。为此，本文做了如下工作： 1 首先介绍了遗传算法的原理，分析了其缺陷及产生原因，进而根据生物免疫系 统的抗原识别、保持抗体的多样性和免疫记忆的特性，将免疫算法引入到遗传算法中。 这样就构成了一种混合优化算法一免疫遗传算法，它通过免疫算法中的浓度调节机制 对抗体进行促进和抑制，这样既保留了进化种群中的较优抗体又保证了抗体的多样性， 从而避免遗传算法在进化过程中的过早收敛问题。本文采取了一种基于抗体矢量距的浓 度构成方式，对选择概率进行了改进；此外本文还对遗传算法中的交叉和变异概率进行 了自适应调整，进一步提高了算法的效率和性能。 2 其次对结构优化问题中的约束条件和离散变量问题提出了相应的处理方法：采 用一种直接比较比例法( d c p m ) 对约束条件进行处理；采用计算适应度的个体与进化个 体相分离的方法来处理离散变量和整型变量。 3 然后综合上述改进，应用免疫遗传算法对经典的d ej o n g 优化测试函数和几类 有约束优化问题分别进行了数值测试，并与其他算法的运算结果进行比较，分析结果表 明，本文的免疫遗传算法具有较强的全局寻优能力、较高的稳定性和计算效率。 4 最后将本文的免疫遗传算法结合杆系结构有限元分析原理，分别对土建结构中 常见的桁架结构和框架结构进行了优化设计。并且将本文算法得到的优化结果同基本遗 传算法的优化结果进行了对比，分析表明本文免疫遗传算法相比基本遗传算法有着更好 山东建筑大学硕士学位论文 的收敛特性，迭代次数减少，优化设计结果也好于基本遗传算法。因此，本文算法用于 此两类结构的优化设计是可行的和高效的。 关键词：结构优化设计，免疫算法，遗传算法，离散变量、桁架结构，框架结构 i i 山东建筑大学硕士学位论文 s t u d yo ni m m u n eg e n e t i ca l g o r i t h ma n dt h ea p p l i c a t i o nt o s t r u c t u r a lo p t i m u md e s i g n y a h f e i ( e n g i n e e r i n gm e c h a n i c s ) d i r e c t e db yl ux i a oy a n g 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 i nr e c e n t4 0y e a r s r e g a r d l e s so ff r o mi t st h e o r y , t h ea l g o r i t h mo ri nt h ea p p l i c a t i o n ，t h es t r u c t u r eo p t i m i z a t i o n d e s i g nh a sa l lm a d et h ev e r yb i gp r o g r e s s e s p e c i a l l yi nr e c e n ty e a r s ，g e n e t i ca l g o r i t h m ( g a ) i nt h es t r u c t u r eo p t i m i z a t i o nd e s i g nd o m a i nw i d es p r e a da p p l i c a t i o n , c a u s e dt h es t r u c t u r e o p t i m i z a t i o nd e s i g nl e v e lt oa c h i e v ean e wa l t i t u d e g e n e t i ca l g o r i t h m ( g a ) i sak i n do fe m u l a t i o nb i o l o g yt oe v o l v eo fs e a r c hm e t h o d s ， b e c , a u s ei t sb r i e f , e a s y , a n dm o r er o b u s t ，p a r t i c u l a r l yi td o e s n tn e e ds p e c i a l i z e dk n o w l e d g e b u to n l ym a k e sw i t ht h eo r i e n t a t i o nv a l u ef u n c t i o ne v a l u a t i o nt og u i d et os e a r c hp r o c e s s ，s o g ab e c o m e so n eo ft h en e wi n t e l l e c t u a lo p t i m a lm e t h o d si nt o d a y sc o m p u t es c i e n c ea n di n t h ed e s i g no fs t r u c t u r eo p t i m i z a t i o n b u ti nt h eo p t i m u md e s i g no fs t r u c t u r e s ，g au s u a l l y e x i s tl o ws e a r c h i n ge f f i c i e n c ya n dp r e m a t u r ee t c a c c o r d i n gt ot h i s ，t h i st e x td i d t ow o r ka sf o l l o w s ： 1 i ti n t r o d u c e dt h ep r i n c i p l eo fg aa n da n a l y z e di t sb l e m i s h ，a c c o r d i n gt ot h ei d e n t i f yo f a n t i g e n , k e e pt h ec h a r a c t e r i s t i co fd i v e r s i t ya n di m m u n i t ym e m o r yo fa n t i b o d yi m m u n e s y s t e m ，l e a dt h ei m m u n i t ya l g o r i t h mi n t og a , r e g u l a t eam e c h a n i s m t or e s i s tab o d yt oc a r r y o np r o m o t i n ga n dr e p r e s st h r o u g had e n s i t y , i tr e s e r v e dt h em o r ee x c e l l e n ta n t i b o d yi nt h e k i n d sa n dp r o m i s e dd i v e r s i t yo fa n t i b o d y , a v o i dp r e m a t u r e a d d i t i o n ，m a k i n gt h eg r o s sa n d v a r i a t i o np r o b a b i l i t ys e l f - a d j u s t i n g ，r a i s i n gt h ee f f i c i e n c ya n di m p r o v et h ep e r f o r m a n c e 2 t h i st e x tp u tf o r w a r dap r o c e s s i n gm e t h o df o rt 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 e p r o b l e m ：i ta d c l p t e da k i n do fd i r e c tc o m p a r i s o nm e t h o dt oc a r r yo nt h ec o n s t r a i n t ，p r o c e s s e d t h ed i s c r e t ev a r i a b l ea n dt h ei n t e g e rv a r i a b l et h r o u g hs e p a r a t i n gt h ei n d i v i d u a lo fc a l c u l a t i n g a d a p t a b l ed e g r e ea n dt h ee v o l v e di n d i v i d u a l 3 s y n t h e s i z et h e s ei m p r o v e m e n t s ，b yt e s t i n gd ej o n gc l a s s i cf u n c t i o na n ds e v e r a lt y p e i i i 山东建筑大学硕士学位论文 c o n s t r a i n tp r o b l e m ，a n dc o m p a r i s o nw i t ho t h e ro p t i m u mm e t h o d t h er e s u l ti n d i c a t e st h e i g ah a ss t r o n g e rg l o b a ls e a r c ha b i l i t ya n dh i g h e ra c c u r a c y 4 c o m b m et h ei m m u n i t yg e n e t i ca l g o r i t h m ( i g a ) w i t ht h el i m i t e de l e m e n tm e t h o d ( f e a ) ，c a r r y i n go nt h eo p t i m u md e s i g nt ot h et r u s ss t r u c t u r e sa n df r a m es t r u c t u r e s r e s p e c t i v e l y , t h e nc o n t r a s tt h er e s u l tw i t hs g a t h ea n a l y z ee n u n c i a t i o ni n d i c a t e st h a tt h e i g ai sf e a s i b l ea n de f f i c i e n t l y i th a sb e t t e rc o n v e r g e n tc h a r a c t e r i s t i c , l e s si t e r a t i v et i m e s ， m o r ee x c e l l e n tt h a ns g a k e y w o r d ：o p t i m u md e s i g no fs t r u c t u r e s ，i m m u n i t ya l g o f i t l u n ，b a s i cg e n e t i c a l g o r i t h m ，d i s c r e t eo p t i m u m ，t r u s ss t r u c t u r e s ，f r a m es t r u c t u r e 原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究 取得的成果。除文中已经注明引用的内容外，论文中不舍其他人已经发表或撰 写过的研究成果，也不包含为获得山东建筑大学或其他教育机构的学位证书而 使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确 方式标明。本人承担本声明的法律责任。 学位论文作者签名： 学位论文使用授权声明 本学位论文作者完全了解山东建筑大学有关保留，使用学位论文的规定， 即：山东建筑大学有权保留并向国家有关部门或机构送交学位论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权山东建筑大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印，缩印或其它手段保存， 汇编学位论文。 保密论文在解密后遵守此声明。 学位论文作者签名：1 至 ：日期2 2 z ! 立砭 导 师签名： 山东建筑大学硕士学位论文 第1 章绪论 1 1 引言 传统的结构设计，实际上指的是结构分析，其过程是假设一分析一校核一重新设计， 具体来说就是工程师根据自己的理论知识和设计经验首先针对用户的需要进行概念设 计，定出结构的类型和形式，按规定要求和标准给出受力情况，提出初始设计方案；然 后进行结构分析，再根据分析结果进行强度、刚度、稳定等方面的校核；如果不符合经 济与安全的要求，则修改设计，再进行结构的重分析、重校核，直到满足为止。传统设 计的这种重分析、重校核过程最多为两三次，否则工作量太大，难以承受。这种设计的 一个主要缺点是难以找到材料的合理分布。 结构优化设计指的是结构综合，其过程是假设一分析一搜索一最优设计，搜索过程 也是修改设计的过程，这种修改是按一定的优化方法使设计方案达到最佳的目标，是一 种主动的、有规则的搜索过程并以达到预定的最优目标为满足【1 1 。作为近四十年发展起 来的一门新技术，结构优化设计使设计者能从被动的分析、校核进入主动的设计。优化 设计能最合理的利用材料的性能，使结构内部各单元得到最好的协调，并具有规范所规 定的安全度。同时，它还为整体性方案进行合理的决策，优化设计是实现设计的最终目 标适用、安全与经济的有效途径。 随着科技的进步，工程结构日趋复杂，许多问题用传统的优化方法难以求解，需要 一种全新的优化方法来处理这类问题。近年来，随着计算机技术、仿生学、人工智能等 学科的飞速发展，一些借鉴和利用自然现象或生物体各种原理的优化算法被相继提出， 克服了传统优化方法在结构优化设计中的一些局限性，取得了良好的效果。像基于大脑 神经网络原理开发的神经网络具有良好的非线性映射和学习能力，己经广泛的应用在机 器人、模式识别等领域。进化算法则是模仿了生物体的生存演化，广为应用的遗传算法 是进化算法的一种，它是模拟生物自然环境中的遗传和进化而形成的一种自适应启发式 概率性搜索算法。另外，生物的免疫系统也已成为一个新兴的生物信息研究课题。越来 越多的研究人员模拟和应用免疫系统的信息处理能力解决工程和科学问题，并且免疫算 法作为一种与以往方法截然不同的新方法，为结构优化设计开辟了一条新思路。 山东建筑大学硕士学位论文 1 2 结构优化设计理论发展概况 结构优化设计大体上可分为三个阶段【2 l 。第一阶段是建立数学模型，把一个工程结 构的设计问题变成一个数学问题；第二个阶段是选定一个合理的、有效的优化方法；第 三个阶段是编制通用的计算机程序或者开发相应的软件，使同一类型的结构，都可以由 计算机给出最优设计方案。 优化理论和方法的起源可以追溯到微积分诞生的年代。然而，直n - 十世纪三、四 十年代，由于军事、航天等方面的迫切需要，才使得它得到了蓬勃的发展。后来，由于 电子计算机的问世和计算机软硬件的迅猛发展，使得进行优化计算的费用大幅度下降， 于是基于迭代原理的各种数值优化方法得以产生并在工业生产、工程设计、经济等领域 得到广泛的应用。目前常见的优化方法主要可分为两大类，一类是非直接法即在求极值 的过程中，不仅要计算目标函数的值，而且还需要计算函数的导数值，也就是说，要依 赖目标函数的解析性质来确定极值的搜索方向，如最快下降法、共轭梯度法和非线性最 小二乘法等都属于这类方法。另一种方法称为直接法，即只需要计算目标函数值，并根 据函数值的变化进行试探性搜索，确定搜索方向，如单纯形法、模式搜索法等。 结构优化设计从马克斯威尔理论( m a x w e l l ，1 8 9 0 ) 和米歇尔( m i c h e l l e ，1 9 0 4 ) 关于最小 体积构架结构设计问题的论文出现起至今已有百余年，从史密特( s c h m i t t ) 用数学规划来 解决结构优化设计至今也已有4 5 年的历史，特别是过去3 0 年内，结构优化设计在理论、 算法和应用方面都取得了长足的发展。应用优化的领域涉及到了航空航天、机械、土木、 水利、桥梁、汽车、铁路、轻工纺织、能源工业以及军事工业等诸多方面，主要处理那 些具有复杂结构系统的设计，如飞机、卫星、机器人、射电远望镜等，或者大规模的工 程建设，如大坝、桥梁、核电站，或者产量大的汽车、机械和轻工产品以及创新型的产 品设计。 在六十年代，有两门学科的发展给结构优化设计的发展给予了莫大的动力吼其一 是有限元法解决了复杂结构的分析问题。要优化设计必须先会正确的分析，有限元法就 为发展优化设计提供了良好的条件；其二是运筹学中的数学规划方法的发展，把结构设 计作为非线性规划的一个命题，看来是最恰当不过的了，只要把优化追求的目标和设计 应受的种种约束做出数学描述，剩下的问题仅需把数学家研究出来的数学规划方法搬出 来求解。丽电子计算机的发展，又为结构优化提供了高效能的计算工具，使得对大型工 程结构进行优化没计成为可能。在上述三个因素的促进下，结构优化在近二十年发展的 很快。 山东建筑大学硕士学位论文 实际结构的优化问题是一个极其复杂的过程。设计的过程中不但要对结构进行细致 的分析，建立合理、有效、适合于求解的优化数学模型，还要应用优化方法进行求解并 对优化的结果进行合理的评价与修正。因此优化建模的过程需要综合考虑问题的物理力 学模型是否能反映结构设计的主要特征，数学模型是否适合于优化求解。所以优化建模 的过程需要将力学、结构、数学和计算机科学等知识进行综合运用。结构优化设计的数 学模型往往是比较复杂的，它一般具有离散、多峰、不可微、非凸等很多不利于求解的 因素。传统的优化方法相对于实际优化问题的求解要求，存在以下的主要缺点【4 j ： ( 1 ) 一般对目标函数都有较强的限制性要求，如连续，可微、单峰等。这些要求对 于实际结构的优化设计问题是很苛刻的。 ( 2 1 在实现算法之前，要进行大量的准备工作，例如求函数的一阶和二阶导数，某 些矩阵的逆等。在目标函数较为复杂的情况下，这一工作是很困难的，甚至是不可能的。 ( 3 ) 算法结果一般与初始值的选取有较大的关系，不同的初始值可能导致不同的结 果。初始值的选取较大地依赖于优化者对问题背景的认识及所掌握的知识。 ( 4 ) 算法缺乏简单性与通用性。针对一个问题，优化方法的使用者需要有相当的知 识去判定使用哪一种优化方法较为合适，这困难是优化设计广泛应用的主要障碍。 ( 5 ) 结构优化设计的数学模型一般都是约束优化问题，而且约束条件常为隐式约 束，求解时需要做大量的结构重分析工作，计算量很大。 1 3 免疫及遗传算法的发展概况 早在2 0 世纪5 0 年代和6 0 年代，就有计算机科学家进行了所谓的“人工进化系统” 的研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形 成了遗传算法的雏形。6 0 年代，美国m i c h i g a n 大学的h o l l a n d 教授在a s f r a s e r 和h j b r a k e m a n 等人工作的基础上，提出了位串编码技术。随后，h o l l a n d 将该算法用于自 然和人工系统的自适应行为的研究中，并于1 9 7 5 年发表了自然系统和人工系统中的 适应问题( 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 ”) 一书，该书系统地阐述了遗传 算法的基本理论和方法，为其奠定了数学基础，该书的出版标志着遗传算法的诞生。 h o l l a n d 等人在以后的应用研究中，将遗传算法推广到优化以及机器学习等闯题的应用 中，遗传算法的通用编码技术和简单有效的遗传操作为其成功地广泛应用奠定了基础 5 - s l 。 继h o l l a n d 之后，越来越多的学者开始致力于g a 的研究与应用，其中有d ej o n g 山东建筑大学硕士学位论文 ( 1 9 7 5 ) 对g a 各种策略的性能和机理进行了大量而细致的实验和分析，并完成了具有指 导意义的博士学位论文遗传自适应系统的行为分析( a n a n a l y s i so f t h eb e h a v i o r o f a c l a s s o f g e n e t i c a d a p t i v e s y s t e m ”) ，他深入领会了模式定理并把h o l l a n d 的模式理论与计 算实验结合起来。将选择、交叉和突变操作进一步完善和系统化，同时又提出了诸如代 沟( g e n e r a t i o ng a p ) 等新的遗传操作技术。他还建立了著名的五函数测试平台，定义了评 价遗传算法性能的在线性能和离线性能，并以函数优化为例，对遗传算法的六种方案的 性能及机理进行了详细的实验和分析。他的研究工作为遗传算法及其应用打下了坚实的 基础，得出的结论迄今仍具有普遍的指导意义，在一定程度上是d ej o n g 的工作使人们 开始看到了g a 的应用价值l ”。在h o l l a n d ( 1 9 7 5 ) 的书中还给出了一个自适应的规则学习 系统( c l a s s i f i e rs y s t e m ) ，g o l d b e r g 将它成功地应用于天然气管道系统的控制规则的优化 问题上1 1 0 1 ；b e t h e k e 的博士论文提出了用w a l s h 函数来研究g a 的方法；a l b e r t 大学的 b r i n d l e 在博士论文中对选择策略进行了研究 1 1 1 。这一时期的研究成果主要是回答了g a 到底有何意义，有何价值。由于他们的研究工作，很多人的注意力逐渐转向了g a 。1 9 8 5 年召开了第一届g a 的国际会议，以后每隔一年举行一次。 自8 0 年代中期以来，是g a 的蓬勃发展期，研究者对遗传算法的应用研究不断扩 大和深入。1 9 8 7 年，美国l a w r e n c ed a v i s 出版了遗传算法与模拟退火c g e n e t i c a l g o r i t h ma n ds i m u l a t e da n n e a l i n g ”) 一书，以论文集形式用大量的实例介绍遗传算法的 使用。1 9 8 9 年，美国亚拉巴马大学的d a v i dg o l d b e r g 出版了搜索、优化和机器学习 中的遗传算法( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o n ，a n dm a c h i n el e a r n i n g ”) ， 为遗传算法这个领域奠定了坚实的科学基础。1 9 9 1 年，l a w r e n c ed a v i s 出版了遗传算 法手册( h a n d b o o ko fg e n e t i c a l g o r i t h m ) - - 书，书中包括了遗传算法在科学计算，工程 技术和社会经济中的大量应用实例，这本书为推广和普及遗传算法的应用起到了重要的 指导作用【1 2 】。1 9 9 2 年，k o z a 将遗传算法应用于计算机程序的优化设计及自动生成，提 出了遗传编程( g e n e t i cp r o g r a m m i n g ) 的概念 1 ，他成功的把提出的遗传编程的方法应 用于人工智能、机器学习、符号处理等方面。 传统的遗传算法虽然自成体系且使用广泛，但是依然有许多不足，例如对于局部空 问的搜索问题不是很有效、个体的多样性减少得很快等。这些缺陷的存在限制了遗传算 法的应用。于是，人们丌始研究如何改进算法以及采用合适的算法加快寻优速度和改善 山东建筑大学硕士学位论文 寻优质量。 免疫遗传算法是近几年来发展起来的一种改进型遗传算法，它是将生物学中生物免 疫机制和遗传算法相结合而形成的一种优化算法。生物进化和生物免疫从不同角度说明 了适者生存的自然规律。进化是从总体上生物种群的进化，而免疫则通过“疫苗”的作 用，更注重提高个体的环境适应能力。将进化与免疫结合起来考虑，能得到更有效的优 化算法。另一方面，多样性是免疫系统的重要特征之一，利用抗体多样性保持机制改进 传统的遗传算法，可提高算法的群体多样性，有效地抑制早熟现象，使免疫遗传算法具 有较好的全局收敛性，有效地提高寻优能力。 1 9 9 3 年，美国新墨西哥大学的s f o r r e s t 和洛斯阿拉莫斯实验室的ap e re s o n 首先提出了免疫系统的遗传建模方法。1 9 9 7 年，c h u n 等基于体细胞理论和免疫网络理 论提出了一种免疫算法，t a z a w a t ”1 等提出了一种结合免疫系统与遗传特性的免疫遗传 算法用于超大规模集成电路的设计，其中主要利用了小生境技术。1 9 9 8 年，j a n g - s u n k c h u n 等基于熵理论设计了一种免疫优化算法( i a ) 并应用于永磁同步电机的优化设计中。 1 9 9 9 年，k a z u y u k i “1 等提出了免疫优化算法并用于解决自适应调度问题，该算法中使 用了传统遗传算法的交叉和变异算子生成新个体以保持抗体的多样性。2 0 0 1 年， s h y h - j i e r t ”1 利用平均信息熵计算了抗体的亲和力，再结合简单遗传算法( s g a ) 的交叉和 变异算子设计了免疫算法优化燃料调配和热量生成问题。2 0 0 4 年，g a o ”1 等提出一种 基于免疫多样性的选择算子，该选择算子依赖于串的稠密度和适应值，串的稠密度越大， 其保留下来的可能性越小，实验结果证明改进算法是有效的。在国内，最早开展免疫优 化算法研究的是西安电子科技大学的王雷、焦李成等j k ( 1 9 9 8 ) i ”】，他们设计了一种模拟 自我免疫机铸l j ( s e l f - i m m u n i t y ) 的免疫遗传算法i g a 应用于t s p 问题的优化求解，并证明 了算法的全局收敛性，其算法的核心就是加入了最优保持操作。其后，王煦法等( 1 9 9 9 ) t ”l 模拟免疫行为中的抗原识别、抗原记忆和抗体的抑止、促进等免疫行为而设计出相应的 免疫模块，从而构成完整的免疫遗传算法并应用于t s p 优化，实验研究表明：该方法 提高了遗传算法的全局和局部搜索能力，并能够改善未成熟收敛的缺陷；周伟良等( 2 0 0 0 年1 【2 1 1 提出了基于浓度控制的i g a 并应用于b p 网络的辅助设计和解决x o r 问题。 山东建筑大学硕士学位论文 1 3 本论文研究的内容 根据在遗传算法中引入的免疫机制的不同，免疫遗传算法大致可以分为利用疫苗的 免疫遗传算法和利用抗体多样性的免疫遗传算法等。本文正是尝试利用免疫算法中抗体 多样性原理及抗体浓度策略对标准遗传算法的缺陷进行改进，并探讨免疫遗传算法在结 构优化设计领域中的应用。 首先介绍了遗传算法的原理并分析了其缺陷，并根据生物免疫系统的抗原识别、保 持抗体的多样性和免疫记忆的特性，将免疫算法引入到遗传算法中，通过浓度调节机制 对抗体进行促进和抑制，这样既保留了种群中的较优抗体又保证了抗体的多样性，从而 避免进化过程中的过早收敛。此外对遗传算法中的交叉和变异概率进行了自适应调整， 进一步提高了算法的效率和性能。 其次对优化问题中约束条件和离散变量问题提出了相应的处理方法：采用一种直接 比较法对约束进行处理，采用计算适应度的个体与进化个体相分离的方法来处理离散变 量和整型变量。 然后综合上述改进，对经典的d ej o n g 测试函数和几类有约束优化问题进行了数值 测试，并与其他算法的结果进行比较。 最后将免疫遗传算法结合有限元分析原理，编制了结构优化程序，并运用该程序分 别对桁架结构和框架结构进行了优化设计，将该算法得到的优化结果同基本遗传算法的 优化结果进行了对比，分析表明该算法用于此类结构优化设计是可行的和高效的，克服 了基本遗传算法在实际的应用中收敛速度慢和稳定性差的缺陷，提高了遗传算法的效率 和可靠性。 1 5 研究的目的和意义 本文在研究分析基本的遗传算法原理和缺陷的基础上，结合免疫算法的浓度调节机 制，对遗传算法采用了若干改进措施并进行了数值测试，说明了本文采用的免疫遗传算 法是可行、有效的。利用免疫遗传算法对建筑工程中桁架及框架结构进行优化设计研究， 为该类结构的优化设计提供理论依据，这对节约工程投资。改进设计的合理性，提高建 筑工程的投资效益有一定的现实意义。总之，采用免疫遗传算法对建筑结构进行优化设 计的过程就是利用合理的优化方法，进行结构的有限元分析，寻求最优截面尺寸，达到 降低工程造价之目的。因此，本课题的研究不仅为实际工程设计提供一种可行的方法， 而且可产生较为明显的经济效益，具有一定的理论与现实意义。 山东建筑大学硕士学位论文 第2 章遗传算法原理与生物免疫学原理 2 1 遗传算法的原理及缺陷 遗传算法( g e n e t i c a l g o r i t h m ，g a ) 是由美国密西根大学h o l l a n d 教授于1 9 7 5 年提出 的。它是一种基于自然选择和基因遗传学原理的搜索算法，它根据“优胜劣汰，适 者生存”的生物进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决的复 杂问题，特别是最优化问题，遗传算法提供了一个行之有效的途径。但是，遗传算法自 身存在许多难以解决的问题，如早熟收敛、随机漫游等。这些问题的存在，给遗传算法 的实际应用带来了极大的不便。为了解决这些问题，提高优化效率，我们需要先对基本 遗传算法的原理进行研究。 2 1 1 遗传算法中的基本概念 由于遗传算法是自然遗传学和计算机科学相互渗透的产物，因此借用了许多自然进 化论中的基本术语。 ( 1 ) 种群( p o p u l a t i o n ) 和个体( i n d i v i d u a l ) 遗传算法处理的是表示问题可行解的编码串，对应于生物体中的染色体，或者叫 基因型个体。一定数量的个体组成了种群。 ( 2 ) 种群规模( p o p u l a t i o ns i z e ) 种群中个体的数目称为种群大小，也叫种群规模。 ( 3 ) 适应度函数( f i t n e s sf u n c t i o n ) 各个个体对环境的适应程度叫做个体的适应度。对于优化问题，适应度函数就是 目标函数。遗传算法有时要求适应度函数为可加以比较的非负函数。 ( 4 ) 编码( c o d i n g ) 、译码( d e c o d i n g ) 把搜索空间中的参数或解转换成遗传空间中的染色体编码，称为编码操作；反之， 称为译码操作。 ( 5 ) 遗传操作( g e n e g eo p e r a t i o n ) 遗传算法包括三个主要的遗传操作：选择( 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 ) 。 2 1 2 标准遗传算法的流程 利用遗传算法解最优化问题，首先应对可行域中的点进行编码( 一般采用二进制或者 山东建筑大学硕士学位论文 十进制编码) ，然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组， 并计算每个编码的目标函数值，也就是编码的适应值。接着就像自然界中一样，利用选 择机制从编码组中按某种规律挑选编码作为繁殖过程前的编码样本。选择机制应保证适 应值较高的解能够保留较多的样本，而适应值较低的解则保留较少的样本，甚至被淘汰。 在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交 换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机 挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和 繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法 解最优化问题所得到的最终结果。 具体步骤如下： ( 1 ) 对所解决的问题进行编码； ( 2 ) 产生规模为n 的初始群体； ( 3 ) 对当前群体x ( t y p 的每个个体t ；计算其适应度， ) ，适应度大小表示了该个 体的好坏。 ( 4 ) 若终止条件满足则算法终止，否则计算概率只 ( 2 1 ) 并以概率只，从x ( t ) 中随机选择一些个体构成一个种群a e ( t ) ； ( 5 ) 对种群应用交叉算予，交叉概率为，得到一个规模为n 的交叉后群体，然后 以一个较小的概率巴对交叉后群体做变异运算，生成一个新的群体x ( t + 1 ) g ( 6 ) t = t + l ，如果不满足终止条件转( 3 ) 。 遗传算法的流程框图如下： 乒酗 一 只 山东建筑大学硕士学位论文 图2 1 遗传算法的流程框图 2 1 3 标准遗传算法的基本操作 遗传算法包含5 个基本要素：参数编码、适应度函数( f i t n e s sf u n c t i o n ) 的设计、选择算 子( r e p r o d u c t i o n ) 、交叉算子( c r o s s o v e r ) 和变异算子( m u t a t i o n ) 。这5 个要素构成了遗传算 法的核心内容。 ( 1 ) 参数编码 编码就是把参数空间的点转换成字符串来表示。编码方案有二进制编码、g r e y 编码 和实数编码，若采用二进制码表示实数，每个二进制位即为一个基因。 设参数x 【口，b 】， 妣+ 攀 。) ( 2 2 ) 其中，f 是串的长度，是第i 个基因。 山东建筑大学硕士学位论文 ( 2 ) 适应度函数( f i t n e s sf u n c t i o n ) 的设计 遗传算法在进化搜索中基本很少利用外部信息，仅以适应度函数为依据。因此适应 度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。适应度 函数要求是非负的，而目标函数有正有负，甚至可能是复数值；且目标函数和适应度函 数间的关系也多种多样，如求最大值对应点时，目标函数和适应度函数变化方向相同： 求最小值对应点时，变化方向恰好相反。因此，存在目标函数向适应度函数映射的问题。 对最大化问题，一般采用如下适应度函数： m 吖l 善拣乏 对最小化问题 m ，t p 雾拣乏 式中c 二。，c o 既可以是输入参数也可以是进化过程中最近k 代的最小( 大) 值。 ( 3 ) 选择算子 选择算子是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群 体中的一种遗传运算，它也被称为复制操作。为了避免有效基因的丢失，选择操作使适 应度高的个体得以更大的概率生存，从而提高全局收敛性和计算效率。适应度高的个体 被选中的可能性大，有可能被多次复制；而适应度低的个体被选中的概率小，有可能一 次也未被选中。选择算子是建立在对个体的适应度进行评价的基础之上，选择操作的主 要目的是为了避免基因缺失、提高全局收敛性和计算效率。 最常用和最基本的选择算子是比例选择算子。所谓比例选择算子，是指个体被选 中并遗传到下一代群体中的概率与该个体的适应度大小成正比。比例选择实际上是一种 有退还随机选择，也叫做赌盘( r o u l e t t ew h e e l ) 选择，因为这种选择方式与赌博中的赌盘 操作原理颇为相似。其具体执行过程是： a 1 先计算出群体中所有个体的适应度的总和； b ) 依次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代的 概率： 曲根据个体的相对适应度大小确定它们在盘面中所占扇面大小及位置，使用模拟 赌盘操作( 即0 到1 之问的随机数) 来确定各个个体被选中的次数。 除了比例选择法外，还有排序选择、确定式采样选择、随机联赛选择等方法。 山东建筑大学硕士学位论文 可以发现影响模式生存的主要因素是包含该模式的个体平均适应度。如果包含该模 式的个体适应度高于整个群体的平均适应度，该个体存活的概率大，反之，则个体存活 概率将很小。 在选择算子的作用下，优秀个体会大量增加，低劣个体会迅速减少，整个群体向好 的方向进化，但同时群体却丧失了多样性。如果选择算子的选择压力过大的话，那么群 体就有可能还未搜索足够多的模式算法便己收敛，不再进行优化，从而导致了“早熟” 现象的产生。 ( 4 ) 交叉算子 在自然界中生物迸化过程中起核心作用的是生物遗传基因的重组。同样，在遗传算 法中，起核心作用的是遗传操作的交叉算子。所谓交叉就是指把两个父代个体的部分结 构加以替换重组，而生成新的个体的操作。交叉算子用来组合新的个体，在可行解空间 中进行有效搜索，同时降低有效模式的破坏概率。 各种交叉算子一般包括两个基本内容：一是从由选择操作所形成的新一代个体中， 随机配对并按预先设定的交叉概率来决定是否进行交叉操作；二是随机产生个体交叉 点，并对交叉点前后个体部分结构进行互换。 交叉算子包括单点交叉、多点交x ( g 括两点交叉) 、均匀交叉，算术交叉等。 a 1 单点交叉：它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交 换两个配对个体的部分染色体。例如： a ：101101 1 1 0 ；0 垒盛窒墨。a ：10110101 0 1 1 b ：0001 1 1001 j l b ：0001 1 1001 ；0 双点交叉：双点交叉是在相互配对的两个染色体编码串中随机设置两个交叉点， 然后交换两个个体在所设定的两个交叉点之间的部分染色体。例如： a ：10111 011 ；10o 巫盛窑墨4 ：101 1 ；110i 000 b ：0001 j l101 01 1 b 。：00011 011 ；11 1 交叉点1交叉点2 交叉点1 交叉点2 曲均匀交叉：它是指两个配对个体的每一个基因位置上的基因以相同的交叉概率 进行交换，从而形成两个新的个体，其具体运算可通过设置一屏蔽字w 一w j m 来确定，其中f 为编码串的长度，根据屏蔽字上的基因来交叉形成a ，口+ ，若。0 则a 在第i 基因位置上的基因值继承a 的对应基因，b 。在第i 基因位置上的基因继承8 的对 山东建筑大学硕士学位论文 应基因值；若则眦一1 ，a 在第i 个基因座上的基因值继承b 的对应基因值，b 在第i 个 基因座的基因值继承a 的对应基因值。例如： a ：10l1o1110o 塑鱼銮墨a ：1 01101100 1 b ：0001110 011 w - 0 1 0 1 0 1 0 1 0 1 b ：00011 10110 d ) 算术交叉：它是指由两个个体的线性组合而产生出两个新的个体。假设在两个 个体e 、e 之间进行算术交叉，则交叉运算后所产生出两个新个体是： i 翟硝詈+ p 著 ( 2 5 ) 1 x f l 一口影+ ( 1 一a ) 以 7 式中口为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀算术交叉；它也 可以是一个变量，此时所进行的是非均匀交叉运算。 直观来讲，选择算予将原有的优良模式遗传给下一代，而交叉算子则必须保证优 良模式在下一代中有一定的遗传和继承的机会，并且通过交叉操作可以生成包含更多优 良模式的个体。 大量关于交叉算子对模式的生存能力与破坏能力的分析及实验表明，交叉算子在破 坏现有模式的同时，也通过模式重组生成新的高阶模式瞄j 。对于交叉算子，存在着这 样一个结论：若某类交叉算子的模式生存概率大，则其模式重组能力较差，反之亦然。 这说明交叉算子不具备同时提供强大模式生存能力和重组能力的功能叫1 。 虽然在交叉算子的作用下会逐渐生成高阶的模式串，但交叉算子的作用对群体的多 样性并没有影响。所以无论模式重组能力强的或者模式生存能力强的交叉算予，都不会 增加群体多样性。但交叉算子可以改变当前群体搜索的子空间，可以使群体跳出不利于 全局收敛的局部搜索环境，所以交叉算子的模式重组能力可以使算法跳出局部最优解， 在群体多样性没有完全丧失时，可以帮助算法摆脱“早熟”现象。 ( 5 ) 变异算子 遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值 用该基因座上的其他等位基因来代替，从而形成新的个体。我们知道在遗传算法中，交 叉算子决定了遗传算法的全局搜索能力，而变异算子改善了遗传算法的局部搜索能力， 并维持群体的多样性，防止早熟现象。 最简单的变异算子是基本位变异，基本位变异操作改变的只是个体编码串中个别几 山东建筑大学硕士学位论文 个基因座上的基因值，并且变异发生的概率也比较小，所以其发挥的作用比较慢，作用 的效果也不明显。 除基本位变异外，还有均匀变异、边界变异和高斯变异等其他变异操作方法口1 。 a ) 均匀变异：是指定个体编码串中的每个基因座为变异点，对每一个变异点，以变 异概率从对应基因的取值范围内取以随机数来代替原有基因值。假使有一个体 x 一气而，若毪为变异点， 其取值范围为【屹，吃】，在该点对个体x 进行 均匀变异操作后，可得到一新的个体x 一墨t t 而，其中变异点的新基