现代设计理论与方法-优化设计.ppt

《现代设计理论与方法-优化设计.ppt》由会员分享，可在线阅读，更多相关《现代设计理论与方法-优化设计.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、机械优化设计机械优化设计宁波大学机械工程与力学学院宁波大学机械工程与力学学院邓益民教授邓益民教授短号短号:695648)Email:一、优化设计的基本概念一、优化设计的基本概念优化设计要解决两个关键问题（1 1）建立优化设计数学模型）建立优化设计数学模型 它包括三个要素，即优化设计的目标函数、设计变量和约束条件；（2 2）选择适合的优化方法）选择适合的优化方法/算法算法解析法数值计算法优化方法微分求极值迭代逼近最优值各种算法1 1设计变量设计变量 1 1）概念）概念 在设计中，通常用对设计性能指标有影响的一在设计中，通常用对设计性能指标有影响的一组基本参数来表示某个设计方案，这组参数根据其组基

2、本参数来表示某个设计方案，这组参数根据其特点又分为特点又分为 设计常量：设计常量：可以根据客观规律或具体条件预先确可以根据客观规律或具体条件预先确定的参数，如材料的力学性能，机器的工况系数等。定的参数，如材料的力学性能，机器的工况系数等。设计变量：设计变量：在设计过程中不断变化，需要在设计在设计过程中不断变化，需要在设计过程中进行选择的基本参数，称为设计变量，如几过程中进行选择的基本参数，称为设计变量，如几何尺寸、速度、加速度、温度等。何尺寸、速度、加速度、温度等。优化设计实例优化设计实例 设计一密闭矩形容器，其容积为设计一密闭矩形容器，其容积为3m3m3 3，容器的，容器的宽度不小于宽度不小

3、于1.5m1.5m，以便于装卸车搬运，为使成，以便于装卸车搬运，为使成本最低，要求用料最省。本最低，要求用料最省。这项设计的设计变量是矩形容器的长这项设计的设计变量是矩形容器的长l l、宽、宽w w、高高h h。2 2）对设计变量的要求）对设计变量的要求 相互独立的参数，其取值都是实数。相互独立的参数，其取值都是实数。有界连续变量，称为连续量，如温度。有界连续变量，称为连续量，如温度。跳跃式的量，称为离散量，如齿轮的齿数、模跳跃式的量，称为离散量，如齿轮的齿数、模数，丝杆的螺距等。数，丝杆的螺距等。对离散变量，在优化设计时，常常先看作连续量，对离散变量，在优化设计时，常常先看作连续量，在求得连

4、续量的优化结果后在进行圆整或标准化，在求得连续量的优化结果后在进行圆整或标准化，以求得一个实用的最优方案。以求得一个实用的最优方案。一项设计，若有一项设计，若有n n个设计变量个设计变量1 1，2 2，n n 可以按一定次序排列，用可以按一定次序排列，用n n维向量来表示：维向量来表示：=1 1，2 2，n n T T RRn n 它表示了设计空间的概念，即以它表示了设计空间的概念，即以n n个设计变量个设计变量为坐标轴组成的实空间，为坐标轴组成的实空间，R Rn n代表代表n n维空间维空间2 2目标函数目标函数 1）概念概念 目标函数是指根据特定目标建立起来的、目标函数是指根据特定目标建立

5、起来的、以设计变量为自变量的一个可计算的数学函以设计变量为自变量的一个可计算的数学函数。它是设计方案评价的标准。数。它是设计方案评价的标准。2 2）目标函数的描述）目标函数的描述 优化设计的过程实际上是求目标函数优化设计的过程实际上是求目标函数极小值极小值或极大值（最值）或极大值（最值）的过程，而求目标函数极大值的过程，而求目标函数极大值的问题可转化为求目标函数极小值的问题。优化的问题可转化为求目标函数极小值的问题。优化设计数学模型中通常规定求目标函数的极小值。设计数学模型中通常规定求目标函数的极小值。故目标函数统一描述为：故目标函数统一描述为：min min F F（）=F=F（1 1，2

6、2，n n ）前例中密闭容器优化设计的目标函数可表示为：前例中密闭容器优化设计的目标函数可表示为：minmin F F（）=F F（l,w,hl,w,h）=2=2（lh+wh+lwlh+wh+lw）3 3）分类）分类 单目标优化：单目标优化：如果优化问题只有一个目标如果优化问题只有一个目标函数，则称为单目标优化函数，则称为单目标优化.多目标优化：多目标优化：如果优化问题有几个目标函如果优化问题有几个目标函数，则称为多目标优化。数，则称为多目标优化。多目标优化可以通过数学方法转化为单目标问多目标优化可以通过数学方法转化为单目标问题，常用方法是加权法（其他如范数法、级数题，常用方法是加权法（其他如

7、范数法、级数法、乘积法等）法、乘积法等）加权前往往需要进行归一或正则化处理加权前往往需要进行归一或正则化处理（Normalization Normalization 属于定标的一种）属于定标的一种）3 3约束条件约束条件 1 1）概念）概念 为产生一个可接受的设计，设计变量本身或为产生一个可接受的设计，设计变量本身或相互间应该遵循的限制条件，称为约束条件。相互间应该遵循的限制条件，称为约束条件。2 2）表示方法）表示方法 约束条件一般可表示为设计变量的不等式约束函数约束条件一般可表示为设计变量的不等式约束函数形式和等式约束函数形式，即形式和等式约束函数形式，即 gi（）=gi（1，2，n）0

8、或者或者 gi（）=gi（1，2，n）0 （i=1，2，m）hj（）=hj（1，2，n）=0 （j=1，2，p）式中式中m m，p p分别表示施加于该项设计的不等式约束数分别表示施加于该项设计的不等式约束数目和等式约束数目。目和等式约束数目。一个等式约束可能通过代入法消去一个设计变量。一个等式约束可能通过代入法消去一个设计变量。3 3）分类）分类 按约束条件，又可分为性能约束和边界约束按约束条件，又可分为性能约束和边界约束。（1 1）性能约束）性能约束 是针对设计对象的某种性能或指标而给出是针对设计对象的某种性能或指标而给出的一种约束条件。如零件的计算应力不大于许的一种约束条件。如零件的计算应

9、力不大于许用应力，轴的扭转变形应小于许用扭转角等。用应力，轴的扭转变形应小于许用扭转角等。一般这类约束条件总可以根据设计规范中的设一般这类约束条件总可以根据设计规范中的设计公式或通过物理学和力学的基本分析导出的计公式或通过物理学和力学的基本分析导出的约束函数来表示。约束函数来表示。（2 2）边界约束）边界约束 又称区域约束（书中的常量约束），表又称区域约束（书中的常量约束），表示设计变量的物理限制和取值范围。如前例中示设计变量的物理限制和取值范围。如前例中的边界约束条件为：的边界约束条件为：g1（）=g1（l，w，h）=w 1.5 0 g2（）=g2（l，w，h）=l 0g3（）=g3（l，w

10、，h）=h 0 约束条件是以设计变量为自变量一个函数，约束条件是以设计变量为自变量一个函数，各个约束条件之间不能彼此矛盾。各个约束条件之间不能彼此矛盾。1 1数学模型的描述数学模型的描述 数学模型的规范化描述形式为：数学模型的规范化描述形式为：min F（）=1，2，nT Rn gi（）=gi（1，2，n）0 i=1，2，m hj（）=hj（1，2，n）=0 j=1，2，p二、优化设计的数学模型二、优化设计的数学模型 2 2线性规划线性规划 当目标函数当目标函数F F（）、约束条件）、约束条件g gi i（）和）和h hj j（）是设计变量的线性函数时，称该优化问题）是设计变量的线性函数时，称

11、该优化问题为线性规划问题；如果为线性规划问题；如果只能取整数，则是整数规只能取整数，则是整数规划（经常优化后取整）划（经常优化后取整）3 3非线性规划非线性规划 当目标函数当目标函数F F（）、约束条件）、约束条件g gi i（）和）和h hj j（）中有一个或几个是设计变量的非线性函数）中有一个或几个是设计变量的非线性函数时，称该优化问题为非线性规划问题；机械设计时，称该优化问题为非线性规划问题；机械设计中，绝大多数优化设计问题的数学模型都属于非中，绝大多数优化设计问题的数学模型都属于非线性规划问题。线性规划问题。前例中的优化设计问题可建立如下的数学模型：前例中的优化设计问题可建立如下的数学

12、模型：min F（）=F（l,w,h）=2（lh+wh+lw）g1（）=g1（l，w，h）=w 1.5 0 g2（）=g2（l，w，h）=l 0 g3（）=g3（l，w，h）=h 0 g4（）=g4（l，w，h）=l w h=3 可见，这是一个三维非线形规划问题。为了简可见，这是一个三维非线形规划问题。为了简化问题，可根据等式约束条件消去一个设计变量：化问题，可根据等式约束条件消去一个设计变量：h=3/h=3/（l wl w）则该问题从原来的三维问题转化为二维问题。则该问题从原来的三维问题转化为二维问题。4 4建立数学模型的一般过程建立数学模型的一般过程 1 1）分析设计问题，初步建立数学模型

13、）分析设计问题，初步建立数学模型 即使是同一设计对象，如果设计目标和设计即使是同一设计对象，如果设计目标和设计条件不同，数学模型也会不同。因此，要首先弄条件不同，数学模型也会不同。因此，要首先弄清问题的本质，明确要达到的目标和可能的条件，清问题的本质，明确要达到的目标和可能的条件，选用或建立适当的数学、物理、力学模型来描述选用或建立适当的数学、物理、力学模型来描述问题问题 2 2）确定设计变量）确定设计变量 通常应参照以往的设计经验和实际要求，将通常应参照以往的设计经验和实际要求，将那些对目标函数影响不大的参数取为常量，以那些对目标函数影响不大的参数取为常量，以减少设计变量的个数，有利于设计问

14、题数学模减少设计变量的个数，有利于设计问题数学模型的简化。型的简化。3 3）根据工程实际，提出约束条件）根据工程实际，提出约束条件 约束条件是对设计变量的限制，这种限制必约束条件是对设计变量的限制，这种限制必须要根据工程实际情况来制订，以便使设计方须要根据工程实际情况来制订，以便使设计方案切实可行。约束条件的数目越多，则可行的案切实可行。约束条件的数目越多，则可行的设计方案就越少，优化设计的难度也越大。设计方案就越少，优化设计的难度也越大。4 4）模型前处理）模型前处理 简化模型：划分子结构、子阶段；简化模型：划分子结构、子阶段；简化处理：变量变换，如倒数、平方等简化处理：变量变换，如倒数、平

15、方等 定标处理：消除变量、约束、目标函数在大小、定标处理：消除变量、约束、目标函数在大小、量纲上的差别量纲上的差别5 5）选择正确的计算方法，确定计算误差）选择正确的计算方法，确定计算误差 如果数学模型的数学表达式比较复杂，无法求如果数学模型的数学表达式比较复杂，无法求出精确解，则需采用近似的数值计算方法，并估计出精确解，则需采用近似的数值计算方法，并估计计算误差。计算误差。6 6）进行结果分析，审查模型灵敏度（鲁棒性检查）进行结果分析，审查模型灵敏度（鲁棒性检查）数学模型求解后，还应进行灵敏度分析，即在数学模型求解后，还应进行灵敏度分析，即在优化结果的最优点处，稍稍改变某些条件，检查目优化结

16、果的最优点处，稍稍改变某些条件，检查目标函数和约束条件的变化程度。若变化大，则说明标函数和约束条件的变化程度。若变化大，则说明灵敏度高，就需要重新修正模型。某些问题需要进灵敏度高，就需要重新修正模型。某些问题需要进一步进行稳健设计一步进行稳健设计单变量（一维）方法单变量（一维）方法一维搜索法一维搜索法一维函数黄金分割法一维函数黄金分割法（0.6180.618法）法）二次插值法二次插值法（近似抛物线法）（近似抛物线法）无约束问题搜索方法无约束问题搜索方法坐标轮换法坐标轮换法鲍威尔法（鲍威尔法（PowellPowell法）法）梯度法梯度法牛顿法牛顿法变尺度法（变尺度法（DRPDRP）三常用优化设计

17、方法三常用优化设计方法有约束问题搜索方法有约束问题搜索方法复合形法复合形法拉格郎日乘子法拉格郎日乘子法惩罚函数法惩罚函数法（罚函数法）（罚函数法）现代优化方法现代优化方法遗传算法遗传算法粒子群算法粒子群算法蚁群算法蚁群算法鱼群算法鱼群算法【神经网络法神经网络法】传统搜索方法传统搜索方法 遗遗传传算算法法简简称称GA（Genetic Algorithm），最最早早由由美美国国MichiganMichigan大大学学的的J.J.HollandHolland教教授授提提出出（于于上上世世纪纪60-7060-70年年代代，以以19751975年年出出版版的的一一本本著著作作为为代代表表）,模模拟拟自自

18、然然界界遗遗传传机机制制和和生生物物进进化化论论而成的一种并行随机搜索最优化方法。而成的一种并行随机搜索最优化方法。遗遗传传算算法法是是以以达达尔尔文文的的自自然然选选择择学学说说为为基基础础发发展起来的。自然选择学说包括以下三个方面：展起来的。自然选择学说包括以下三个方面：遗传算法简介遗传算法简介（1 1）遗遗传传：这这是是生生物物的的普普遍遍特特征征，亲亲代代把把生生物物信信息息交交给给子子代代，子子代代总总是是和和亲亲代代具具有有相相同同或或相相似似的的性性状状。生生物物有有了了这个特征，物种才能稳定存在。这个特征，物种才能稳定存在。（2 2）变变异异：亲亲代代和和子子代代之之间间以以及

19、及子子代代的的不不同同个个体体之之间间的的差差异异，称称为为变变异异。变变异异是是随随机机发发生生的的，变变异异的的选选择择和和积积累累是生命多样性的根源。是生命多样性的根源。（3 3）生生存存斗斗争争和和适适者者生生存存：具具有有适适应应性性变变异异的的个个体体被被保保留留下下来来，不不具具有有适适应应性性变变异异的的个个体体被被淘淘汰汰，通通过过一一代代代代的的生生存存环环境境的的选选择择作作用用，性性状状逐逐渐渐与与祖祖先先有有所所不不同同，演演变变为为新的物种。新的物种。遗遗传传算算法法将将“优优胜胜劣劣汰汰，适适者者生生存存”的的生生物物进进化化原原理理引引入入优优化化参参数数形形成

20、成的的编编码码串串联联群群体体中中，按按所所选选择择的的适适应应度度函函数数并并通通过过遗遗传传中中的的选选择择、交交叉叉及及变变异异对对个个体体进进行行筛筛选选，使使适适应应度度高高的的个个体体被被保保留留下下来来，组组成成新新的的群群体体，新新的的群群体体既既继继承承了了上上一一代代的的信信息息，又又优优于于上上一一代代。这这样样周周而而复复始始，群群体体中中个个体体适适应应度度不不断断提提高高，直直到到满满足足一一定定的的条条件件。遗遗传传算算法法的的算算法法简简单单，可可并并行行处处理理，并并能能到到全全局局最优解。最优解。遗传算法的基本操作（算子）有：遗传算法的基本操作（算子）有：（

21、1 1）选择（）选择（Selection OperatorSelection Operator）选选择择是是从从一一个个旧旧种种群群中中选选择择生生命命力力强强的的个个体体位位串串产产生生新新种种群群的的过过程程。具具有有高高适适应应度度的的位位串串更有可能在下一代中产生一个或多个子孙。更有可能在下一代中产生一个或多个子孙。选选择择操操作作可可以以通通过过随随机机方方法法来来实实现现。首首先先产产生生0101之之间间均均匀匀分分布布的的随随机机数数，若若某某串串的的选选择择概概率率为为40%40%，则则当当产产生生的的随随机机数数在在0.401.00.401.0之之间时，该串被选择，否则被淘汰

22、。间时，该串被选择，否则被淘汰。（2 2）交叉（）交叉（Crossover OperatorCrossover Operator）选选择择操操作作能能从从旧旧种种群群中中选选择择出出优优秀秀者者，但但不不能能创创造造新新的的染染色色体体。而而交交叉叉模模拟拟了了生生物物进进化化过过程程中中的的繁繁殖殖现现象象，通通过过两两个个染染色色体体的的交交换换组组合合，来来产生新的优良品种。产生新的优良品种。交交叉叉的的过过程程为为：在在匹匹配配池池中中任任选选两两个个染染色色体体，随随机机选选择择一一点点或或多多点点交交换换点点位位置置；交交换换双双亲亲染染色色体体交交换换点点右右边边的的部部分分，即

23、即可可得得到到两两个个新新的的染染色色体体数字串。数字串。交交叉叉体体现现了了自自然然界界中中信信息息交交换换的的思思想想。交交叉叉有有单单点点交交叉叉、多多点点交交叉叉、还还有有一一致致交交叉叉、顺顺序序交交叉叉和和周周期期交交叉叉。单单点点交交叉叉是是最最基基本本的的方方法法，应应用用较较广。它是指染色体切断点有一处，例：广。它是指染色体切断点有一处，例：（3 3）变异）变异(Mutation Operator)(Mutation Operator)变变异异运运算算用用来来模模拟拟生生物物在在自自然然的的遗遗传传环环境境中中由由于于各各种种偶偶然然因因素素引引起起的的基基因因突突变变，它它

24、以以很很小小的的概概率率随随机机地地改改变变遗遗传传基基因因（表表示示染染色色体体的的符符号号串串的的某某一一位位）的的值值。在在染染色色体体以以二二进进制制编编码码的的系系统统中中，它它随随机机地地将将染染色色体体的的某某一一个个基基因因由由1 1变为变为0 0，或由，或由0 0变为变为1 1。若若只只有有选选择择和和交交叉叉，而而没没有有变变异异，则则无无法法在在初初始始基基因因组组合合以以外外的的空空间间进进行行搜搜索索，使使进进化化过过程程在在早早期期就就陷陷入入局局部部解解而而进进入入终终止止过过程程，从从而而影影响响解解的的质质量量。为为了了在在尽尽可可能能大大的的空空间间中中获获

25、得得质量较高的优化解，必须采用变异操作。质量较高的优化解，必须采用变异操作。遗传算法的特点遗传算法的特点（1 1）遗遗传传算算法法是是对对参参数数的的编编码码进进行行操操作作，而而非非对对参参数数本本身身，这这就就是是使使得得我我们们在在优优化化计计算算过过程程中中可可以以借借鉴鉴生生物物学学中中染染色色体体和和基基因因等等概概念念，模模仿仿自自然界中生物的遗传和进化等机理然界中生物的遗传和进化等机理（2 2）遗遗传传算算法法同同时时使使用用多多个个搜搜索索点点的的搜搜索索信信息息。传传统统的的优优化化方方法法往往往往是是从从解解空空间间的的单单个个初初始始点点开开始始最最优优解解的的迭迭代代

26、搜搜索索过过程程，单单个个搜搜索索点点所所提提供供的的信信息息不不多多，搜搜索索效效率率不不高高，有有时时甚甚至至使使搜搜索索过过程程局限于局部最优解而停滞不前局限于局部最优解而停滞不前 遗遗传传算算法法从从由由很很多多个个体体组组成成的的一一个个初初始始群群体体开开始始最最优优解解的的搜搜索索过过程程，而而不不是是从从一一个个单单一一的的个个体体开开始始搜搜索索，这这是是遗遗传传算算法法所所特特有有的的一一种种隐隐含含并并行行性，因此遗传算法的搜索效率较高性，因此遗传算法的搜索效率较高（3 3）遗传算法直接以目标函数作为搜索信息。传）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要

27、利用目标函数值，而且需统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助索范围，无需目标函数的导数值等其他一些辅助信息信息 遗传算法可应用于目标函数无法求导数或导遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题数不存在的函数的优化问题，以及组合优化问题等等（4 4）遗传算法使用概率

28、搜索技术。遗传算法的）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的方式选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体体会更多地产生出许多新的优良的个体（5 5）遗传算法在解空间进行高效启发式搜索，）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索而非盲目地穷举或完全随机搜索（6 6）遗传算法对于待寻优的函数基本无限制，）遗传算法对于待寻优的函数基本无限制

29、，它既不要求函数连续，也不要求函数可微，既可它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较矩阵甚至是神经网络的隐函数，因而应用范围较广广（7）遗传算法具有并行计算的特点，因而可通）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，适合大规模过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。复杂问题的优化。遗传算法的应用领域遗传算法的应用领域（1 1）函数优化）函数优化 函函数数优优化化是是遗遗传传算算法法的的经经典典应应用用领领域域，也也是是遗遗传

30、传算算法法进进行行性性能能评评价价的的常常用用算算例例。尤尤其其是是对对非非线线性性、多多模模型型、多多目目标标的的函函数数优优化化问问题题，采采用用其其他他优优化化方方法法较较难难求求解解，而而遗遗传传算算法法却却可可以以得得到到较较好的结果。好的结果。（2 2）组合优化）组合优化 随随着着问问题题的的增增大大，组组合合优优化化问问题题的的搜搜索索空空间间也也急急剧剧扩扩大大，采采用用传传统统的的优优化化方方法法很很难难得得到到最最优优解解。遗遗传传算算法法是是寻寻求求这这种种满满意意解解的的最最佳佳工工具具。例例如如，遗遗传传算算法法已已经经在在求求解解旅旅行行商商问问题题、背背包包问问题

31、题、装装箱问题、图形划分问题等方面得到成功的应用。箱问题、图形划分问题等方面得到成功的应用。（3 3）生产调度问题）生产调度问题 在在很很多多情情况况下下，采采用用建建立立数数学学模模型型的的方方法法难难以以对对生生产产调调度度问问题题进进行行精精确确求求解解。在在现现实实生生产产中中多多采采用用一一些些经经验验进进行行调调度度。遗遗传传算算法法是是解解决决复复杂杂调调度度问问题题的的有有效效工工具具，在在单单件件生生产产车车间间调调度度、流流水水线线生生产产车车间间调调度度、生生产产规规划划、任任务务分分配配等等方方面面遗传算法都得到了有效的应用。遗传算法都得到了有效的应用。（4 4）自动控

32、制）自动控制 在在自自动动控控制制领领域域中中有有很很多多与与优优化化相相关关的的问问题题需需要要求求解解，遗遗传传算算法法已已经经在在其其中中得得到到了了初初步步的的应应用用。例例如如，利利用用遗遗传传算算法法进进行行控控制制器器参参数数的的优优化化、基基于于遗遗传传算算法法的的模模糊糊控控制制规规则则的的学学习习、基基于于遗遗传传算算法法的的参参数数辨辨识识、基基于于遗遗传传算算法法的的神神经经网网络络结结构构的的优化和权值学习等。优化和权值学习等。（5 5）机器人）机器人 例如，遗传算法已经在移动机器人路径规划、例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优

33、化和行关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。为协调等方面得到研究和应用。（6 6）图像处理）图像处理 遗遗传传算算法法可可用用于于图图像像处处理理过过程程中中的的扫扫描描、特特征征提提取取、图图像像分分割割等等的的优优化化计计算算。目目前前遗遗传传算算法法已已经经在在模模式式识识别别、图图像像恢恢复复、图图像像边边缘缘特特征征提提取取等等方面得到了应用。方面得到了应用。（1 1）染色体编码及解码方法）染色体编码及解码方法）染色体编码及解码方法）染色体编码及解码方法 基基基基本本本本遗遗遗遗传传传传算算算算法法法法使使使使用用用用固固固固定定定定长长长长度度度度的

34、的的的二二二二进进进进制制制制符符符符号号号号来来来来表表表表示示示示群群群群体体体体中中中中的的的的个个个个体体体体，其其其其等等等等位位位位基基基基因因因因是是是是由由由由二二二二值值值值符符符符号号号号集集集集0,10,1所所所所组组组组成成成成。初初初初始始始始个个个个体体体体基基基基因因因因值值值值可可可可用用用用均均均均匀匀匀匀分分分分布布布布的的的的随随随随机值生成，如机值生成，如机值生成，如机值生成，如就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是1818。解码方法示例：解

35、码方法示例：解码方法示例：解码方法示例：其中，其中，其中，其中，x x的范围为的范围为的范围为的范围为a,b,da,b,d为其二进制为其二进制为其二进制为其二进制码串码串码串码串(长度为长度为长度为长度为k k)所对应的十进制数所对应的十进制数所对应的十进制数所对应的十进制数遗传算法的实施步骤遗传算法的实施步骤（2 2）个个个个体体体体适适适适应应应应度度度度评评评评价价价价：基基基基本本本本遗遗遗遗传传传传算算算算法法法法与与与与个个个个体体体体适适适适应应应应度度度度成成成成正正正正比比比比的的的的概概概概率率率率来来来来决决决决定定定定当当当当前前前前群群群群体体体体中中中中每每每每个个

36、个个个个个个体体体体遗遗遗遗传传传传到到到到下下下下一一一一代代代代群群群群体体体体中中中中的的的的概概概概率率率率多多多多少少少少。为为为为正正正正确确确确计计计计算算算算这这这这个个个个概概概概率率率率，要要要要求求求求所所所所有有有有个个个个体体体体的的的的适适适适应应应应度度度度必必必必须须须须为为为为正正正正数数数数或或或或零零零零。因因因因此此此此，必必必必须须须须先先先先确确确确定定定定由由由由目目目目标标标标函函函函数数数数值值值值J J到到到到个个个个体体体体适适适适应应应应度度度度f f之间的转换规则。之间的转换规则。之间的转换规则。之间的转换规则。（3 3）遗传算子：基本

37、遗传算法使用下述三种遗）遗传算子：基本遗传算法使用下述三种遗）遗传算子：基本遗传算法使用下述三种遗）遗传算子：基本遗传算法使用下述三种遗传算子：传算子：传算子：传算子：选择运算选择运算选择运算选择运算:使用比例选择算子使用比例选择算子使用比例选择算子使用比例选择算子 交叉运算交叉运算交叉运算交叉运算:使用单点交叉算子使用单点交叉算子使用单点交叉算子使用单点交叉算子 变异运算变异运算变异运算变异运算:使用基本位变异算子或均匀变异算使用基本位变异算子或均匀变异算使用基本位变异算子或均匀变异算使用基本位变异算子或均匀变异算子子子子（4 4）基本遗传算法的运行参数）基本遗传算法的运行参数）基本遗传算法

38、的运行参数）基本遗传算法的运行参数 有下述有下述有下述有下述4 4个运行参数需要提前设定：个运行参数需要提前设定：个运行参数需要提前设定：个运行参数需要提前设定：MM：群群群群体体体体大大大大小小小小，即即即即群群群群体体体体中中中中所所所所含含含含个个个个体体体体的的的的数数数数量量量量，一一一一般般般般取为取为取为取为2010020100；GG：遗遗遗遗传传传传算算算算法法法法的的的的终终终终止止止止进进进进化化化化代代代代数数数数，一一一一般般般般取取取取为为为为5050050500；PcPc：交叉概率，一般取为：交叉概率，一般取为：交叉概率，一般取为：交叉概率，一般取为0.40.990

39、.40.99；PmPm：变异概率，一般取为：变异概率，一般取为：变异概率，一般取为：变异概率，一般取为0.00010.10.00010.1。对对对对于于于于一一一一个个个个需需需需要要要要进进进进行行行行优优优优化化化化的的的的实实实实际际际际问问问问题题题题，一一一一般般般般可可可可按按按按下述步骤构造遗传算法：下述步骤构造遗传算法：下述步骤构造遗传算法：下述步骤构造遗传算法：第第第第一一一一步步步步：确确确确定定定定决决决决策策策策变变变变量量量量及及及及各各各各种种种种约约约约束束束束条条条条件件件件，即即即即确确确确定定定定描描描描述述述述个个个个体体体体的变量的变量的变量的变量X X

40、和问题的解空间范围；和问题的解空间范围；和问题的解空间范围；和问题的解空间范围；第第第第二二二二步步步步：建建建建立立立立优优优优化化化化模模模模型型型型，即即即即确确确确定定定定目目目目标标标标函函函函数数数数的的的的类类类类型型型型及及及及数数数数学学学学描描描描述形式或量化方法；述形式或量化方法；述形式或量化方法；述形式或量化方法；遗传算法的应用步骤遗传算法的应用步骤第三步：确定表示可行解的染色体编码方法；第三步：确定表示可行解的染色体编码方法；第三步：确定表示可行解的染色体编码方法；第三步：确定表示可行解的染色体编码方法；第第第第四四四四步步步步：确确确确定定定定解解解解码码码码方方方

41、方法法法法，即即即即确确确确定定定定由由由由基基基基因因因因到到到到个个个个体体体体的的的的对对对对应应应应关关关关系或转换方法；系或转换方法；系或转换方法；系或转换方法；第第第第五五五五步步步步：确确确确定定定定个个个个体体体体适适适适应应应应度度度度的的的的量量量量化化化化评评评评价价价价方方方方法法法法，即即即即确确确确定定定定由由由由目目目目标函数值到个体适应度的转换规则；标函数值到个体适应度的转换规则；标函数值到个体适应度的转换规则；标函数值到个体适应度的转换规则；第第第第六六六六步步步步：设设设设计计计计遗遗遗遗传传传传算算算算子子子子，即即即即确确确确定定定定选选选选择择择择运运

42、运运算算算算、交交交交叉叉叉叉运运运运算算算算、变异运算等遗传算子的具体操作方法。变异运算等遗传算子的具体操作方法。变异运算等遗传算子的具体操作方法。变异运算等遗传算子的具体操作方法。第第第第七七七七步步步步：确确确确定定定定遗遗遗遗传传传传算算算算法法法法的的的的有有有有关关关关运运运运行行行行参参参参数数数数，即即即即M,G,Pc,PmM,G,Pc,Pm等等等等参数。参数。参数。参数。利用遗传算法求利用遗传算法求利用遗传算法求利用遗传算法求RosenbrockRosenbrock函数的极大值函数的极大值函数的极大值函数的极大值例题：例题：遗传算法求函数极值遗传算法求函数极值 用用用用长长长

43、长度度度度为为为为1010位位位位的的的的二二二二进进进进制制制制编编编编码码码码串串串串来来来来分分分分别别别别表表表表示示示示两两两两个个个个决决决决策策策策变变变变量量量量x1,x1,x2x2。1010位位位位二二二二进进进进制制制制编编编编码码码码串串串串可可可可以以以以表表表表示示示示从从从从0 0到到到到10231023之之之之间间间间的的的的10241024个个个个不不不不同同同同的的的的数数数数，故故故故将将将将x1,x1,x2x2的的的的定定定定义义义义域域域域离离离离散散散散化化化化为为为为10231023个个个个均均均均等等等等的的的的区区区区域域域域，包包包包括括括括两

44、两两两个个个个端端端端点在内共有点在内共有点在内共有点在内共有10241024个不同的离散点。个不同的离散点。个不同的离散点。个不同的离散点。从从从从离离离离散散散散点点点点-2.0482.048到到到到离离离离散散散散点点点点2.0482.048，分分分分别别别别对对对对应应应应于于于于从从从从0000000000(0)0000000000(0)到到到到1111111111(1023)1111111111(1023)之之之之间间间间的的的的二二二二进制编码。进制编码。进制编码。进制编码。将将将将x1,x2x1,x2分别表示的两个分别表示的两个分别表示的两个分别表示的两个1010位长的二进制编

45、位长的二进制编位长的二进制编位长的二进制编码串连接在一起，组成一个码串连接在一起，组成一个码串连接在一起，组成一个码串连接在一起，组成一个2020位长的二进制编码位长的二进制编码位长的二进制编码位长的二进制编码串，它就构成了这个函数优化问题的染色体编码串，它就构成了这个函数优化问题的染色体编码串，它就构成了这个函数优化问题的染色体编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法，解空间和遗传算法的方法。使用这种编码方法，解空间和遗传算法的方法。使用这种编码方法，解空间和遗传算法的方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。搜索空间就具有一一对应的

46、关系。搜索空间就具有一一对应的关系。搜索空间就具有一一对应的关系。例如：例如：例如：例如：表示一表示一表示一表示一个个体的基因型，其中前个个体的基因型，其中前个个体的基因型，其中前个个体的基因型，其中前1010位表示位表示位表示位表示x1x1，后，后，后，后1010位表位表位表位表示示示示x2x2。（4 4）确确确确定定定定解解解解码码码码方方方方法法法法：解解解解码码码码时时时时需需需需要要要要将将将将2020位位位位长长长长的的的的二二二二进进进进制制制制编编编编码码码码串串串串切切切切断断断断为为为为两两两两个个个个1010位位位位长长长长的的的的二二二二进进进进制制制制编编编编码码码码

47、串串串串，然然然然后后后后分分分分别别别别将将将将它它它它们们们们转转转转换换换换为为为为对对对对应应应应的的的的十十十十进进进进制制制制整整整整数数数数代代代代码码码码，分分分分别记为别记为别记为别记为y y1 1和和和和y y2 2。依依依依据据据据个个个个体体体体编编编编码码码码方方方方法法法法和和和和对对对对定定定定义义义义域域域域的的的的离离离离散散散散化化化化方方方方法法法法可可可可知，将代码知，将代码知，将代码知，将代码y y转换为变量转换为变量转换为变量转换为变量x x的解码公式为的解码公式为的解码公式为的解码公式为 例如，对个体例如，对个体例如，对个体例如，对个体 它由两个代

48、码所组成它由两个代码所组成它由两个代码所组成它由两个代码所组成 上述两个代码经过解码后，可得到两个实际的上述两个代码经过解码后，可得到两个实际的上述两个代码经过解码后，可得到两个实际的上述两个代码经过解码后，可得到两个实际的值值值值（5 5）确定个体评价方法：由于）确定个体评价方法：由于）确定个体评价方法：由于）确定个体评价方法：由于RosenbrockRosenbrock函数的函数的函数的函数的值域总是非负的，并且优化目标是求函数的最大值域总是非负的，并且优化目标是求函数的最大值域总是非负的，并且优化目标是求函数的最大值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对

49、应的目标函值，故可将个体的适应度直接取为对应的目标函值，故可将个体的适应度直接取为对应的目标函值，故可将个体的适应度直接取为对应的目标函数值，即数值，即数值，即数值，即选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数（6 6）设设设设计计计计遗遗遗遗传传传传算算算算子子子子：选选选选择择择择运运运运算算算算使使使使用用用用比比比比例例例例选选选选择择择择算算算算子子子子，交交交交叉叉叉叉运运运运算算算算使使使使用用用用单单单单点点点点交交交交叉叉叉叉算算算算子子子子，变变变变异异异异运运运运算算算算使使使使用用用用基本位变

50、异算子。基本位变异算子。基本位变异算子。基本位变异算子。（7 7）确确确确定定定定遗遗遗遗传传传传算算算算法法法法的的的的运运运运行行行行参参参参数数数数：群群群群体体体体大大大大小小小小M=80M=80，终终终终止止止止进进进进化化化化代代代代数数数数G=100G=100，交交交交叉叉叉叉概概概概率率率率Pc=0.60Pc=0.60，变变变变异概率异概率异概率异概率Pm=0.10Pm=0.10。上上上上述述述述七七七七个个个个步步步步骤骤骤骤构构构构成成成成了了了了用用用用于于于于求求求求函函函函数数数数极极极极大大大大值值值值的的的的优优优优化化化化计算基本遗传算法。计算基本遗传算法。计算