第一章绪论§1 ．1 引言在工程实践中，结构优化设计的思想由来已久，结构优化设计的方法一直是科学工作者和工程技术人员最为关注的问题之一为了解决结构优化设计闯题，人们发展了许多有效的算法，单纯形法、梯度法、动态规划法等，这些传统的优化方法具有一定的局限性，如需要梯度信息、凸规划、单峰问题等等而在实际应用领域中存在着各种高度复杂的优化问题，其目标函数可能表现为非连续或非处处可微、非凸、多峰和带噪声等各种形式，这类复杂优化问题用传统的方法难以求解，因此多年来人们一直在努力寻找能够处理这类问题的新的、更稳健的优化技术近年来，人们提出了～些不依赖于具体问题的直接搜索方法，遗传算法( G e n e t i c A l g o r i t h m ，C A ) 作为其中一种，在许多领域得到了广泛的应用和研究§1 ．2 课题研究背景及其意义本文在研究分析基本的遗传算法原理和综合近期关于遗传算法研究进展的基础上，针对结构优化问题的特殊性质和要求，提出了遗传算法在结构优化设计中算法设计和算子设计的特点和方法，并对基本遗传算法的算法和算子设计提出了若干改进措旌分别求解了连续和离散变量的桁架尺寸优化问题，并设计实现了遗传算法( 见附录I ) 。
表明本文提出的算法是可行和有效的传统设计是设计工程师根据自己的理论知识和丰富的工程实际设计经验，首先针对用户的需要进行概念设计，定出结构的类型和形式，最终提出设计方案，然后进行结构分析，再根据分析结果进行强度、剐度、第1 页第一章绪论稳定( 局部和全局稳定) 、振动频率等各方面进行校核：如果方案不符合经济与安全的要求，则修改初始设计方案，再进行分析、校核直到找到一个可行方案为止这个设计过程周期长，工作量大，难以找到既经济又安全的设计方案而且传统的设计中，初始方案很重要，这对缺少设计经验的年轻工程师来说比较困难传统设计的模式是工程理论和经验、初始设计理论分析、校核、修改设计、再分析、再校核在现代社会，工程结构越来越复杂，要求也越来越高传统的设计方法己经不能满足工程的需要五十年代初，有限元法解决了复杂结构的分析问题，同时数学规划的引入也为发展优化设计提供了良好的条件优化设计是根据既定的结构类型和形式、工况、材料和规范所规定的各种约束条件( 例如强度、刚度、稳定、频率、尺寸以及结构构件的许用离散集等等) ，提出优化的数学模型( 目标函数、约束条件和设计变量) ，其模式是根据优化设计的理论和方法求解优化模型，即进行结构分析、优化设计。
这种设计能够使结构达到经济、安全的要求所以优化设计的新发展、新成就，具有重要的工程意义、广泛的应用前景结构优化设计的模型往往比较复杂，它一般具有离散、多峰、不可微、非凸等很多不利于求解的因素随着问题种类的不同以及问题规模的扩大，要寻求到一种能以有限的代价来求解最优化问题的通用方法仍是一个难题，建立以最大可能( 概率) 求解全局解仍是一个重要问题传统优化方法相对于实际优化问题的求解要求，存在如下缺点：1 ．一般对目标函数都有较强的限制性要求，在处理目标函数为非连续或非处处可微或具有多个极值、非凸、不连通、离散整型的变量等问题时则比较困难而连续、可微、单峰这些要求对于实际结构的优化设计问题是苛亥0 的2 ．大多数优化方法都有根据目标函数的局部展开性质来确定下一步搜第2 页北京交通大学硕士学位论文索的方向，这与搜索函数的整体最优解的目标在一定程度上是抵触的3 ．算法的结果一般与初始值的选取有较大的关系，不同的初始值可能导致不同的结果4 ．缺乏简单性与通用性针对一个问题，优化方法的使用者需要有相当的知识去判断使用哪一种优化方法较为合适这一困难是优化设计的主要障碍之一而遗传算法为求解上述传统方法难处理的问题提供了一个有效的途径和通用的框架。
遗传算法是6 0 年代由H o l l a n d 首次提出的，并逐渐发展成一种迭代自适应启发式概率性搜索算法用以求解不同的非线性问题：对不可微甚至不连续的函数优化，G A 能以较大概率求得全局解；具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性；并且能处理不同类型的优化变量( 离散的、连续的和混合型的) ；不需要任何的辅助信息遗传算法的提出与发展是优化方法的一大进步，研究遗传算法在结构优化中的应用显得尤为重要§1 ．3 遗传算法的发展及其现状本节从遗传算法的发展历史、遗传算法的特点两个方面进行介绍§1 ．3 ．1 遗传算法的历史回顾1遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法遗传算法起源于对生物系统所进行的计算机模拟研究早在本世纪4 0 年代，就有学者开始研究如何和用计算机迸行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作，其出发点是进化的思想可以发展成为许多工程问题的优化工具早期的第3 页第一章绪论研究形成了遗传算法的雏形，如大多数系统都通行“适者生存”的仿自然法则，有些系统采用了基于种群的设计方案，并且加入了自然选择和变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用二进制编码。
进入6 0 年代后，美国密执安大学的H o l l a n d 教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术——遗传算法6 0 年代，H o l l a n d 认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性1 9 6 7 年，H o l l a n d 的学生B a g l c y 在其搏士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法这些都与日前遗传算法中所使用的算子和方法相类似他还敏锐地意识到了在遗传算法执行的不同阶段可以使用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创下了自适应遗传算法的概念7 0 年代初，H o l l a n d 教授提出了遗传算法的基本定理——模式定理( s c h e m a T h e o r e m ) ，从而奠定了遗传算法的理论基础。
模式定理揭示出了群体中的优良个体( 较好的模式) 的样本数将以指数级规律增长，因而从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程1 9 7 5 年，H o l l a n d 出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性( A d a p 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 ) 》1 3 l 8 0 年代，H o l l a n d 教授实现了第一个基于遗传算法的机器学习系统一第4 页北京交通大学硕士学位论文一分类器系统( C l a s s i f i e rS y s t e m s 简称c s ) ，开创了基于遗传算法的机器学习的新概念，为分类器系统构选出了一个完整的框架1 9 7 5 年，D eJ o n g 在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了～些重要且具有指导意义的结论f 羽例如，对于规模在5 0 ～1 0 0 的群体，经过1 0 ～2 0代的进化，遗传算法都能以很高的概率找到最优或近似最优解。
他推荐了在大多数优化问题中都较适用的遗传算法的参数，还建立了著名的D eJ o n g 五函数测试平台，定义了评价遗传算法性能的指标和离线指标1 9 8 9 年，G 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 na n dM a c h i n eL e a r n i n g ) ) > [ 1 1该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用可以说这本书奠定了现代遗传算法的科学基础，为众多研究和发展遗传算法的学者所瞩目1 9 9 1 年，D a v i s 编辑出版了《遗传算法手册( H a n d b o o ko fG e n e t i cA l g o r i t h m s ) } 一书，书中包括了遗传算法在科学计算、工程技术和社会经济下的大量应用实例这本书为推广和普及遗传算法的应用起到了重要的指导作用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 ，简称G P ) 的概念。
他将一段L I S P语言程序作为个体的基因型，把问题的解编码为一棵树，基于遗传和进化的概念，对由树组成的群体进行遗传运算，最终自动生成性能较好的计算机程序K o z a 成功地把他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等方面从此，遗传算法迎来了兴盛发展时期无论是理论研究还是应用研究都成了十分热门的课题尤其是遗传算法的应用研究显得格外活跃第5 页第一章绪论不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高：同时产业应用方面的研究也在摸索之中此外一些新的理论和方法在应用研究中得到了迅速的发展由于遗传算法能有效地求解属于N P C 类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视一些学者也认识到求解复杂问题最优解是不现实的，故丽寻求满意解，而遗传算法是最佳工具之一§1 ．3 ．2 遗传算法的特点1在工程技术、经济、科学和社会等许多领域，存在着大量的以各种形式出现的整体优化问题，物理上表示为费用、时问、风险的整体极小化，以及质量、利润和效率的整体极大化因此，针对具体问题研究的需要，发展了一般性的优化求解策略整体优化问题的搜索技术主要包括基于微分的搜索技术、随机搜索技术、启发式搜索技术和枚举技术，图卜1 对有关具体搜索技术进行了大致分类，进化算法及其中的每一个分支均属于启发式搜索技术。
搜索技术 ————7 —≮≮之～基于微分的搜索技术启发式随机搜索枚举技术随机搜索 t ／／＼／＼心 l 直接方法间接方法模拟退火算法进化算法完全枚举法动态规划＼■＼／、≮：＼lF 泐n a “tI №w t o ml 进化策略l 遗传算法I 进化规划图卜1遗传算法和搜索技术的分类传统的基于微分的搜索技术，包括直接法( 如爬山法) 和问接法( 如求第6 页北京交通大学硕士学位论文导数法) 对问题性质有较高的要求，或者是针对特定问题形式而设计的，这种方法对于单峰性质的解空间可以进行行之有效的搜索，而对于多峰空间它们甚至连局部最优解都很难找到枚举法是一种解空间的遍历搜索方法，包括动态规划和完全枚举法等其特点是可以发现问题的全局最优解，但是计算效率太低f 存在维数灾难) 且每次只计算空间内的一个目标函数值，鲁棒性不强，不适用于大型优化问题随机搜索方法比起上述搜索方法有所改进，但它的搜索效率依然不高，一般而言，只有解在搜索空间中形成紧致分布时，它的搜索才有效但这一条件在实际中难以满足启发式随机搜索方法是目前关于复杂优化问题求解的一类有效方法，不需要或者需要很少的关于问题的先验信息其次，该类算法具有很强的鲁棒性，即能适应不同领域的优化问题求解，并在大多数情况下都能得到比较满意的解。
G A 与模拟退火法、爬山法等搜索方法相比，具市独特算法形式和运行机理，在复杂优化问题中有比较显著的优势遗传算法是在计算机上模拟生物进化过程。