机械优化设计课件(新).ppt

1、机械优化设计,授课教师：张华 授课时间: 2013年10月,教学目标,掌握机械优化设计的基础知识，熟练掌握MATLAB优化工具箱的使用方法，掌握基于导数和非导数的优化方法并能选择运用，掌握智能优化算法及其应用，能够运用MATLAB进行工程优化。,主要内容,优化设计建模、优化设计数学基础、MATLAB优化工具箱，基于导数的优化算法、基于非导数的优化算法、智能优化算法的原理及其MATLAB实现、机械优化设计实例。,难点与重点,难点：优化算法的MATLAB实现； 重点：各种优化算法的合理选用及具体应用。,授课方式,理实结合、教学做一体。,考核要求,对上学期完成的机械原理机械设计综合设计中的减速器进行

2、参数优化。 要求： （1）对该问题进行分析，写出该问题的物理模型； （2）将物理模型转化为优化模型（包括设计变量、目标函数、约束条件）； （3）将优化模型转化为matlab程序（m文件）； （4）利用matlab软件求解该优化问题，写出最优解。 （5）用A4打印纸，写出问题和上述4个过程，条理清晰。1.问题分析2.优化模型3.matlab程序4.最优解和结果分析,学习参考书,陶栋材.现代设计方法.中国石化出版社（教材） 龚纯 ,王正林.精通MATLAB最优化计算 孙靖民. 机械优化设计. 机械工业出版社 陈立周. 机械优化设计方法. 冶金工业出版社 刘惟信. 机械最优化设计. 清华大学出版社

3、陈秀宁.机械优化设计.杭州：浙江大学出版社 田福祥.机械优化设计理论与应用. 冶金工业出版社. ,目 录,绪论 第一节 优化设计概述 第二节 优化设计数学基础 第三节 基于导数的优化算法 第四节 基于非导数的优化算法 第五节 基于MATLAB优化工具箱的优化设计,绪 论,一、优化相关概念 二、机械的传统设计到优化设计 三、机械优化设计的发展 四、机械优化设计的应用概况 五、机械优化设计的作用,来源：优化一语来自英文Optimization，其本意是寻优的过程，最优化可简写为Opt； 优化过程：是寻找约束空间下给定函数取极大值或极小值的过程。,例如, 在右图中，求得一维函数 f(x) 最小值的条

4、件为：若取 x*，则 f(x) 取得最小值 f(x*)。 目的是为了在完成某一任务时所作的努力最少、付出最小，而使其收益最大、效果最好。,优化是万物演化的自然选择和趋势,例如，要求设计一个如右下图所示的防洪堤坝。为了能防洪水，高度必须足以保证洪峰到来时，洪水不会漫入堤岸；堤坝的强度足以保证巨浪不会冲垮堤坝。同时希望得到一个省时省力省经费的设计方案。,获得设计方案的过程是一个决策的过程，也是优化的过程。,优化过程就是求解一个付出最小、获得效益最大的方案。,优化方法,实际问题表达成的函数类型很多： 确定型、不确定型函数； 线形、非线形（二次、高次、超越）函数。 变量类型也很多： 连续、离散、随机变

5、量等等。 产生很多的优化算法： 无约束优化、约束优化： 单目标函数优化、多目标函数优化； 连续变量优化、离散变量优化、随机变量优化。,机械设计方法,传统设计方法 基于手工劳动或简易计算工具。方法低效，一般只能获得一个可行的设计方案。 传统机械设计理论与方法包括疲劳寿命理论、强度理论、振动理论 常凭经验、试算、校核等方法。 现代优化方法 基于计算机的应用，设计过程包括： 从实际问题中抽象出数学模型； 选择合适的优化方法求解数学模型。 特点：以人机配合或自动搜索方式进行，能从“所有的”的可行方案中找出“最优的”的设计方案。,传统设计到优化设计,人工试凑和定性分析的比较过程，被动的重复分析产品的性能

6、经验设计、近似计算、一般的安全寿命可行设计。,图2: 优化设计过程框图,利用电子计算机主动的设计产品参数，获得最优方案理论设计、精确计算、优化设计,优化设计的一般过程 1）建立确切反映问题实质并适合于优化计算的优化设计数学模型； 2）选择恰当的优化方法，编写计算机语言程序； 3）求得数学模型的最优解。,机械优化设计是使某项机械设计在规定的各种设计限制条件下，优选设计参数，使某项或几项设计指标获得最优值。,工程设计上的“最优值”(Optimum)或“最佳值”系指在满足多种设计目标和约束条件下所获得的最令人满意和最适宜的值。,工程案例,1、利用一化工优化系统，对一化工厂进行设计。根据给定数据，在1

7、6小时内，进行16000个可行性设计的选择，从中选择一成本最低、产量最大的方案，并给出必须的精确数据。 传统设计：一组工程师，一年时间，仅仅3个方案，且并非最优。 2、美国BELL飞机公司利用优化方法解决450个设计变量的大型结构优化问题。一个机翼质量减轻35%。 3、波音公司，在747的机身设计中收到了减轻质量、缩短生产周期、降低成本的效果。 4、武汉钢铁公司从德国引进的1700薄板轧机，经该公司自主优化后，就多盈利几百万马克。,优化设计的作用（优点）：,使传统机械设计中，求解可行解上升为求解最优解成为可能； 使传统机械设计中，性能指标的校核可以不再进行； 使机械设计的部分评价，由定性改定量

8、成为可能； 大大提高了产品的设计质量，从而提高了产品的质量； 提高生产效率，降低产品开发周期； ,机械优化设计的发展,1、古典优化思想: 17世纪，利用微分学和变分学的解析解法。 仅能解决简单的极值问题 2、经典优化方法：20世纪40年代，数学规划方法 可求解包含等式约束和不等式约束的复杂优化问题。,3、现代优化设计： 20世纪80年代出现许多现代优化算法：模拟退火算法、遗传算法、人工神经网络算法、蚁群优化算法等。 并从狭义优化设计（零部件参数）转向广义优化设计（面向产品的全系统、设计全过程、全寿命周期）。例如,针对涉及多领域复杂系统的多学科设计优化。,线性规划、非线性规划、几何规划、动态规划

9、和混合离散规划等。优化设计从无约束有约束优化问题；连续变量离散变量；确定型随机型模型；单目标优化多目标优化。,优化设计：优化原理与方法，在科学、工程和社会的实际问题中的应用，即为优化设计。 机械优化设计：即把机械设计与优化设计理论及方法相结合，借助电子计算机，自动寻找实现预期目标的最优设计方案和最佳设计参数。,机构运动参数的优化设计是机械优化设计发展较早的领域。国内近年来才开始重视，但发展迅速，在机构综合、机械的通用零部件的设计、工艺设计方面都得到应用。,在机械设计方面的应用较晚，从国际范围来说，是在上世纪60年代后期才得到迅速发展的。,机械优化设计的应用概况,优化设计本身存在的问题和某些发展

10、趋势主要有以下几方面：,1、目前优化设计多数还局限在参数最优化这种数值量优化问题。结构型式的选择还需进一步研究解决； 2、优化设计这门新技术在传统产业中普及率还不高； 3、把优化设计与CAD、专家系统结合起来是优化设计发展的趋势之一。,优化设计的思想广泛的应用于工业、农业、商业和国防等各部门，解决诸如生产规划、经济管理、能源利用、产品设计、工艺过程设计、控制系统等方面的最优化问题，它是促进技术进步和国民经济发展的一种有效方法。,第一节 优化设计概述,一、优化设计问题引例 二、优化设计问题的数学模型 三、优化设计问题的基本解法,一、引例,现用薄板制造一体积为100m3，长度不小于5m的无上盖的立

11、方体货箱，要求该货箱的钢板耗费量最少，试确定货箱的长、宽、高尺寸。,分析： （1）目标：用料最少，即货箱的表面积最小。 （2）设计参数确定：长x1 、宽x2 、高x3； （3）设计约束条件： （a）体积要求 （b）长度要求,货箱的优化设计,数学模型,设计参数：,设计目标：,约束条件：,已知：传动比i，转速n，传动功率P，大小齿轮的材料，设计该齿轮副，使其重量最轻。,直齿圆柱齿轮副的优化设计,（1）目标：圆柱齿轮的体积V或重量w最小； （2）设计参数确定：模数m、齿宽b、齿数z1 （3）设计约束条件： （a）大、小齿轮满足弯曲强度要求； （b）齿轮副满足接触疲劳强度要求； （c）齿宽系数要求；

12、（d）最小齿数要求,分析：,数学模型,设计参数：,设计目标：,约束条件：,二、优化设计问题的数学模型,优化设计的数学模型是描述实际优化问题的设计内容、变量关系、有关设计条件和意图的数学表达式，它反映了物理现象各主要因素的内在联系，是进行优化设计的基础。,优化设计数学模型的三大要素： 设计变量 约束条件 目标函数,1、设计变量,一个设计方案可以用一组基本参数的数值来表示，这些基本参数可以是构件几何量（如尺寸、位置等），也可以是物理量（如质量、频率等），还可以是应力、变形等表示工作性能的导出量以及非物理量（如寿命、成本等）。 在设计过程中进行选择并最终必须确定的各项独立的基本参数，称作设计变量，又

13、叫做优化参数。在优化设计过程中设计变量是不断修改、调整，一直处于变化状态。,设计变量的全体实际上是一组变量，可用一个列向量表示。设计变量的数目称为优化设计的维数，如n个设计变量，则称为n维设计问题。,只有两个设计变量的二维设计问题可用图1中（a）所示的平面直角坐标表示；有三个设计变量的三维设计问题可用图1中（b）所表示的空间直角坐标表示。,图1 设计变量所组成的设计空间 （a）二维设计问题 （b）三维设计问题,当设计点连续时, 为直线; 为平面; 为立体空间; 为超越空间.,设计空间的维数表征设计的自由度，设计变量愈多，则设计的自由度愈大，可供选择的方案愈多，设计愈灵活，但难度亦愈大，求解亦愈

14、复杂。 小型设计问题：一般含有210个设计变量； 中性设计问题：1050个设计变量； 大型设计问题：50个以上的设计变量。 目前已能解决200个设计变量的大型最优化设计问题。,如何选定设计变量？,任何一项产品，是众多设计变量标志结构尺寸的综合体。变量越多，可以淋漓尽致地描述产品结构，但会增加建模的难度和造成优化规模过大。所以选择设计变量时应注意以下几点： 抓主要，舍次要 对产品性能和结构影响大的参数可取为设计变量，影响小的可先根据经验取为试探性的常量，有的甚至不考虑； 根据要解决的设计问题的特殊性来选择设计变量。,2、约束条件,设计空间是所有设计方案的集合，但这些设计方案有些是工程上不能接受的

15、。如一个设计满足所有对它提出的要求，就称为可行设计。 一个可行设计必须满足某些设计限制条件，这些限制条件称作约束条件，简称约束。, 根据约束性质分： 性能约束针对性能要求而提出的限制条件。如选择某些结构必须满足受力的强度、刚度或稳定性要求等； 侧面约束（边界约束）针对设计变量的取值 范围加以限制的约束。如允许机床主轴选择的尺寸范围，对轴段长度的限定范围等。,分类, 显式约束和隐式约束 约束函数有的可以表示成显式形式，即反映设计变量之间明显的函数关系，有的只能表示成隐式形式，如复杂结构中的性能约束函数（变形、应力、频率等），需要通过有限元等方法计算求得。, 根据数学表达式的形式分：,等式约束：,

16、不等式约束：,可行域：凡满足所有约束条件的设计点，它在设计空间的活动范围。（对应不可行域）,如右下图所示满足两项约束条件的二维设计问题的可行域D为ABC涵盖区域，包括线段AC和圆弧ABC在内。,约束条件：,一般情况下，设计可行域可表示为：,不可行域: 可行点和不可行点 D内的设计点为可行点,否则为不可行点（外点）。 边界点与内点 约束边界上的可行点为边界点,其余可行点为内点。 起作用的约束与不起作用的约束,满足 的约束为起作用约束,否则为不起作用的约束.(等式约束一定是起作用约束),3、目标函数,为了对设计进行定量评价，必须构造包含设计变量的评价函数，它是优化的目标，称为目标函数。用它可以评价

17、设计方案的好坏，所以它又被称作评价函数。记作：,在优化过程中，通过设计变量的不断向f(x)值改善的方向自动调整，最后求得的f(x)最好或最满意的x值。在构造目标函数时，应注意目标函数必须包含全部设计变量。在机械设计中，可作为参考目标函数的有： 最小体积，最轻重量，最高效率，最大承载能力，最小振幅或噪声，最小成本，最高利润等等。,通常,在最优化设计问题中，可以只有一个目标函数称为单目标函数。当在同一设计中要提出多个目标函数时，这种问题称为多目标函数的最优化问题。在一般的机械最优化设计中，多目标函数的情况较多。目标函数愈多，设计的综合效果愈好，但问题的求解亦愈复杂。,在实际工程设计问题中，常常会遇

18、到在多目标的某些目标之间存在矛盾的情况，这就要求设计者正确处理各目标函数之间的关系。 目前处理多目标设计问题常用的方法是组合成一个复合的目标函数，如采用线性加权的形式，即,目标函数的等值线（面）,c为一系列常数，代表一族n维超曲面。如在二维设计空间中，f（x1，x2）=c代表x1-x2设计平面上的一族曲线。对于具有相等目标函数值的设计点构成的平面曲线或曲面称为等值线或等值面。,目标函数是n维变量的函数，它的函数图形只能在n+1维空间中描述出来。为了在n维设计空间中反映目标函数的变化情况，常采用目标函数等值线（面）的方法。 目标函数的等值线（面）的数学表达式为：,如上图表示目标函数f(x)与两个

19、设计变量x1和x2所构成的关系曲面上的等值线，它是由许多具有相等目标函数值的设计点构成的平面曲线。当给目标函数以不同值时，可得到一系列的等值线，它们构成目标函数的等值线族。在极值处目标函数的等值线聚成一点，并位于等值线族的中心。当目标函数值的变化范围一定时，等值线愈稀疏说明目标函数值的变化愈平缓。利用等值线的概念可用几何图形形象地表现出目标函数的变化规律。,函数,的等值线图。从等值线上，可以清楚地看到函数值的变化情况。其中f=40的等值线就是使 各点所组成的连线。,等值线,等值线的“心”（以二维为例）,一个“心”：是单峰函数的极（小）值点，是全局极（小）值点。 没有“心”：例，线性函数的等值线

20、是平行的，无“心”，认为极值点在无穷远处。 多个“心”：不是单峰函数，每个极（小）值点只是局部极（小）值点，必须通过比较各个极值点和“鞍点”（须正确判别）的值，才能确定极（小）值点。,等值（线）面：,4、优化设计问题的一般数学形式,求设计变量向量,使目标函数,满足约束条件,设可以同时满足上述约束条件的设计点的集合为R，则可简化为求X使,最优化设计的目标函数通常为求目标函数的最小值。若目标函数的最优点为可行域中的最大值，则可以看成是-f(x)的最小值，当然也可看成是求1/f(x)的极小值。,对于复杂的问题，要建立能反映客观工程实际的、完善的数学模型往往会遇到很多困难，有时甚至比求解更为复杂。这时

21、要抓住关键因素，适当忽略不重要的成分，使问题合理简化，以易于列出数学模型，这样不仅可节省时间，有时也会改善优化结果。,建立优化设计问题的数学模型的一般步骤,根据设计要求，应用专业范围内的现行理论和经验等，对优化对象进行分析； 对设计问题各参数进行分析，以确定设计的原始参数、设计常数和设计变量； 根据设计要求，确定并构造目标函数和相应的约束条件，有时要构造多目标函数； 必要时对数学模型进行规范化，以消除各组成项间由于量纲不同等原因导致的数量悬殊的影响。,5、优化设计数学模型的分类,（1）按有无约束条件分： 无约束优化问题 约束优化问题 （2）按约束条件和目标函数是否同时为线性分： 线性规划问题

22、非线性规划问题（居多） （3）按问题规模的大小分： 大型：设计变量和约束条件的个数在50以上 中型：设计变量和约束条件的个数在1050 小型：设计变量和约束条件的个数在10个以下,三、优化设计问题的基本解法,1、解析解法：根据函数极值的必要条件和充分条件求得其最优解析解的求解方法，适用于目标函数比较简单的情况。,2数值的近似解法：又称为数值迭代方法，它是根据目标函数的变化规律，以适当的步长沿着能使目标函数值下降的方向，逐步向目标函数值的最优点进行探索，逐步逼近到目标函数的最优点或直至达到最优点。数值解法是优化设计问题的基本解法，其中也可能用到解析解法。 数值解法更能适应计算机的工作特点： 1）

23、数值计算而不是数学分析； 2）具有简单逻辑结构并能进行反复的同样的算术计算； 3）最后得到的是逼近精确解的近似解。,数值迭代法的基本思路：搜索、迭代、逼近即进行反复数值计算，寻求目标函数值不断下降的可行计算点，直到最后获得足够精度的最优点。该方法的求优过程可归纳为以下步骤：,1）首先初选一个尽可能靠近最小点的初始点X(0)，从初始点出发按照一定的原则寻找可行方向和初始步长，向前跨出一步，达到X(1)； 2）得到新点X1后再选择一个新的使函数值迅速下降的方向及适当步长，从X(1)点出发再跨出一步，达到X(2)点。以此类推，一步一步地向前探索并重复数值计算，最终达到目标的最优点。,优化设计的两类方

24、法：优化准则法，数学规划法,数值迭代法的迭代格式,-第k步迭代计算所得到的点。称为第k步迭代点，亦第k步设计方案。,其中：,-第k步迭代计算的搜索方向。,-第k次迭代计算的步长。,每次迭代所得新点的目标函数值应满足函数值下降的要求：,收敛：,数值迭代法关键要解决的问题：,1）怎样确定搜索方向 2）如何确定迭代步长 3）如何判断是否找到最优点，以终止迭代,迭代计算的终止准则,1）点距准则,2）函数值下降量准则,3）梯度准则,即,或,- 绝对下降量,- 相对下降量,采用哪种收敛准则，可视具体问题而定。可取,上述准则都在一定程度上反映了逼近最优点的程度，但都有一定的局限性。在实际应用中，可取其中一种

25、或多种同时满足来进行判定。,4.2.1 基本概念 函数的方向导数 一个二元函数 ，在点 处沿某一方向 的方向导数(即变化率)可定义如下：,第2节 优化设计的数学基础,二元函数 ，在点 处的偏导数（即沿坐标轴方向的变化率，或称坐标轴方向的方向导数）如下：,方向导数与偏导数之间的数量关系 二元函数,三元函数,n元函数,式中，,为S方向与坐标轴方向xi 夹角的余弦。,函数的梯度,函数F(X)在某点X 方向导数表明函数沿某一方向S的变化率。一般说来，函数在某一确定点沿不同方向的变化率是不同的。 为求得函数在某点X 方向导数为最大的方向，引入梯度的概念。 以二元函数为例,函数F(X)在点X处的梯度F(X

26、), 可记作grad F(X),方向S的单位向量,n元函数,的梯度:,说明： 梯度 F(X) 是一个向量，梯度方向是函数具有最大变化率的方向（方向导数最大的方向），即： 梯度 F(X)方向是函数F(X) 的最速上升方向； 负梯度- F(X)方向是函数F(X) 的最速下降方向。,分析:,函数F(X)沿S方向的方向导数等于向量 F(X)在S方向上的投影。 当cos（ F(X) ， S ）1时，即S 与 F(X)方向相同时，向量 F(X) 在 S 方向上的投影最大，其值为,凸集,凸函数,凸规划,4.2.2 最优点性质 局部及全局最优点概念 最优设计点可分为：局部最优点、全局最优点。,目标函数Y=G(

27、X)， 设计变量X, 取值区间a，b即 优化问题的可行区域D=XaXb。,3和3分别为闭区间上设计端点； 2为开区间内极大点（或称局部极值点或局部最优点）; 1为可行区域D内全局最大点（全局最优点）; 1为开区间内极小点; 2为可行区域D内全局最小点。,局部及全局最优点性质讨论 全局最优点一定也是局部最优点，而局部最优点不一定是全局最优点。 判断是否全局、局部最优点的依据和最实用方法是高等数学中的极值原理（开区间上讲极值，闭区间上讲最值）。 全局最优求解方法 最优化问题常要求求解全局最优点，然而由于优化算法本身结构、优化问题本身的复杂性等原因，传统优化算法（如黄金分割法或0.618法，单纯形法

28、、复合形法、最小二乘法等）以及新发展的模糊优化法、神经网络优化法都很难直接求出全局最优点。 目前，求解全局最优点的有效方法主要有：遗传优化法、多个局部最优点比较综合法。,遗传优化法GA （genetic algorithm) GA总能解决传统优化法难以解决的问题。 当优化问题存在若干个“山峰或极值点”（即多极值问题）时，传统优化法很容易陷入或收敛于局部最优点，而GA则不然。 GA最擅长于求解大型且复杂的优化问题，求解简单优化问题反而效率不高（此时还不如选用传统优化法）。 GA法不存在如何选择搜索初始点问题，总能搜索到全局最优点附近。,多个局部最优点比较综合法 先取若干个相距较远的初始点，再从各

29、个初始点出发用选择的优化算法来求出最优点。,全局最优点的判断： 在上述基础上，观察求解结果是否趋向同一点？ 若从不同初始点出发搜索的结果是同一个最优点，则认为所得点是全局最优点； 若从不同初始点出发搜索的结果不是同一个点，则需要进一步比较这些结果值，从中找出目标函数值最小或最大的那个作为全局最优点。,4.2.3 最优化算法的类型*, 4.3.1 最速下降法(梯度法）,第三节 基于导数的最优化方法,问题提出,问题：,在点,处，,沿什么方向,下降最快?,分析：,考查：,显然当,时，,取极小值,因此：,结论：,负梯度方向使,下降最快，,亦即最速,下降方向,教：,最速下降法算法,Step1:,给出,S

30、tep2:,计算,如果,停,Step3:,计算下降方向,Step4:,计算步长因子,Step5:,令,转步.,function x,minf = minFD(f,x0,var,eps) format long; if nargin = 3 eps = 1.0e-6; end syms l; tol = 1; gradf = - jacobian(f,var); while toleps v = Funval(gradf,var,x0); tol = norm(v); y = x0 + l*v; yf = Funval(f,var,y); a,b = minJT(yf,0,0.1); xm =

31、minHJ(yf,a,b); x1 = x0 + xm*v; x0 = x1; end x = x1; minf = Funval(f,var,x); format short;,学：算法的MATLAB实现,做：算法举例,最速下降法求解无约束多维极值问题实例。用最速下降法求函数 解：在MATLAB命令窗口中输入： syms t s; f=(t-4)2+(s+2)2+1 x,mf=minFD(f,1 -3,t s) 所得结果为： X=4.0000 -2.0000 Mf=1,最速下降法优点,(1),程序设计简单，计算量小，存储量小，,对初始点没有特别要求,(2),有着很好的整体收敛性，即使对一般的

32、,目标函数，它也整体收敛,最速下降法缺点,(1),最速下降法是线性收敛的，并且有时是,很慢的线性收敛,原因：,仅反映,在,处,的局部性质,相继两次迭代中搜索,方向是正交的,小结,(1),最速下降法是基本算法之一，而非有效,的实用算法,最速下降法的本质是用线性函数来近似,目标函数，,要想得到快速算法，需要考,虑对目标函数的高阶逼近, 4.3.2 牛顿法,牛顿迭代法也称为牛顿-拉夫森(Newton-Raphson)迭代法，它是数值分析中最重要的方法之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。,基本思想,利用目标函数,在点,处的二阶Taylor,展开式去近似目标函数，,用二

33、次函数的极小点,去逼近目标函数的极小点,教：,Newton迭代法的基本思想,设 是f(x)=0的一个近似根，把f(x)在 处作泰勒展开 若取前两项来近似代替f(x)(称为f(x)的线性化)，则得近似的线性方程 设 ,令其解为 ,得 (1) 这称为f(x)=0的牛顿迭代格式。,它对应的迭代方程为 显然是f(x)=0的同解方程， 故其迭代函数为 在 f(x)=0的根 的某个邻域 内, 在 的邻域R 内，对任意初值 ，应用由公式（1）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一.,牛顿法的几何意义,由（1）式知 是点 处 的切线 与X轴的交点的横坐标（如图）。也就是说，新的

34、近似值 是用代替曲线y=f(x)的切线与x 轴相交得到的。继续取点 ,再做切线与x轴相交，又可得 。由图可见，只要初值取的充分靠近 ,这个序列就会很快收敛于 。 Newton迭代法又称切线法,牛顿迭代法的步骤,步一、准备。选定初始近似值 ，计算 步二、迭代。按公式 迭代一次，得到新的近似值 ，计算 步三、控制。如果 满足 。 则终止迭代，以 作为所求的根；否则转步四。此处 是允许误差,而 。其中c是取绝对值或相对误差 的控制常数，一般可取c=1。 步四、修改。如果迭代次数达到预定指定的次数N，或者 则方法失败；否则以 代替 转步二继续迭代。,牛顿迭代法的优缺点,1、优点：牛顿迭代法具有平方收敛

35、的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方。 2、缺点：选定的初值要接近方程的解，否则有可能得不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。,设(x )在有根区间 (a,b)上存在二阶导数，且满足 （1）(a)(b)0。 则牛顿迭代序列xi收敛于 (x)=0 在 (a,b) 内唯一的根。,判别Newton 法收敛的充分条件,function x,minf = minNT(f,x0,var,eps) format long; if nargin = 3 eps = 1.0e-6; end tol = 1;

36、x0 = transpose(x0); gradf = jacobian(f,var); jacf = jacobian(gradf,var); while toleps v = Funval(gradf,var,x0); tol = norm(v); pv = Funval(jacf,var,x0); p = -inv(pv)*transpose(v); p = double(p); x1 = x0 + p; x0 = x1; end x = x1; minf = Funval(f,var,x); format short;,学：牛顿迭代法的MATLAB实现,做：算法举例,牛顿法求解无约束多

37、维极值问题实例。用牛顿法求函数 解：在MATLAB命令窗口中输入： syms t s; f=(t-4)2+(s+2)2+1 x,mf=minNT(f,0 0,t s) 所得结果为： X=4.0000 -2.0000 Mf=1,练习 1 用牛顿迭代法求方程 在 附近的近似根，误差不超过10-3 。,牛顿迭代法的迭代函数为：,练习2 用牛顿迭代法求方程 的正根。 牛顿迭代法的迭代函数为 如果取初值为 ，相应的MATLAB代码为,clear x=0; for i=1:6 x=x-(x*exp(x)-1)/(x+1)*exp(x) end 可得迭代数列前6项为1.0000 ，0.6839， 0.577

38、5 0.5672， 0.5671，0.5671，说明迭代实收敛的。 如果取初值为10，相应的MATLAB代码为 clear; x=10.0; for i=1:20 x=x-(x*exp(x)-1)/(x+1)*exp(x) y(i)=x; end,可算得迭代数列的前20项为9.0909 ，8.1900 7.2989 ， 6.4194 ， 5.5544 ， 4.7076，3.8844 ， 3.0933 ， 2.3487 1.6759 ， 1.1195 ， 0.7453，0.5902 0.5676 ， 0.5671 ，0.5671 ， 0.5671 ， 0.5671， 0.5671 ， 0.567

39、1,说明迭代是收敛的。 如果取初值 或 ，可算得迭代数列是发散 的，根据函数图形分析原因。 练习3 求方程 在 附近的根，精确到10-5 先直接使用 的迭代格式，相应的MATLAB代码为 n=0;esp=1.05e-5;x=0.5; while abs(x-exp(-x)esp x=exp(-x);n=n+1; end x,n 结果为x=0.5671,n=17,说明迭代17次后达到精度要求。,为加快收敛速度，用 构造迭代格式，由实验的预备知识中可知，取 相应的MATLAB代码为 n=0;eps=1.0e-5; x=0.5; while abs(x-0.625*exp(-x)-0.375*x)e

40、ps x=0.625*exp(-x)+0.375*x;n=n+1; end x,n 结果为0.5671，n=3,说明迭代三次后达到精度要求。 练习4 对练习中方程 ，用加快后的迭代格式 求x=0.5附近的根，精确到10-5,计算 可得 ，相应的MATLAB代码为 n=0;eps=1.0e-5;x=0.5; while abs(x-(x+1)*exp(-x)/(1+exp(-x)eps x=(x+1)*exp(-x)/(1+exp(-x);n=n+1; end x,n 结果为x=0.5671,n=2,说明迭代2次后达到精度要求。, 4.3.3 共轭梯度法,算法特点,（）建立在二次模型上，具有二次

41、终止性,（）有效的算法，克服了最速下降法的慢,收敛性，又避免了牛顿法的计算量大和局部收,性的缺点,（）算法简单，易于编程，需存储空间小等,优点，是求解大规模问题的主要方法,教：,共轭梯度法,记：,左乘,并使,得：,（Hestenes-Stiefel公式）,取：,共轭梯度法基本性质,定理3:,对于正定二次函数，,采用精确线搜索,的共轭梯度法在,步后终止，,且对,成立下列关系式：,（共轭性）,（正交性）,（下降条件）,系数的其他形式,（）FR公式,（1964）,（2）PRP公式,（1969）,FR共轭梯度法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,Step4:,由精确线

42、搜索求,Step5:,转Step2.,学：共轭梯度法的MATLAB实现,function x,minf = minGETD(f,x0,var,eps) format long; if nargin = 3 eps = 1.0e-6; end x0 = transpose(x0); n = length(var); syms l; gradf = jacobian(f,var); v0 = Funval(gradf,var,x0); p = -transpose(v0); k = 0; while 1 v = Funval(gradf,var,x0); tol = norm(v); if tol

43、=eps x = x0; break; end,y = x0 + l*p; yf = Funval(f,var,y); a,b = minJT(yf,0,0.1); xm = minHJ(yf,a,b); x1 = x0 + xm*p; vk = Funval(gradf,var,x1); tol = norm(vk); if tol=eps x = x1; break; end if k+1=n x0 = x1; continue; else lamda = dot(vk,vk)/dot(v,v); p = -transpose(vk) + lamda*p; k = k+1; x0 = x1

44、; end end minf = Funval(f,var,x); format short;,做：共轭梯度法求解无约束多维极值问题举例,用共轭梯度法求函数 解：在MATLAB命令窗口中输入： syms t s; f=(t-3)2+s2 x,mf=minGETD(f,-2 6,t s) 所得结果为： x=3.0000 0.0000 mf=2.0116e-037,第四节基于非导数的优化方法,一般工程实际优化问题绝大多数属于约束非线性规划问题，其一般数学模型如下：,(6-1),求解上述问题的方法称为约束优化方法。,根据约束条件处理方法的不同，约束优化方法可分为以下类型：,直接法 即直接从可行域中寻

45、找它的约束最优解。如： 约束坐标轮换法、随机方向搜索法、复合形法及可行方向法等等。 特点： 优点：算法简单、直观性强、对函数无特殊要求。 缺点：计算量大、收敛慢，因而效率低。 适用场合：维数低、函数复杂、精度要求不高的问题。,间接法 即将复杂的原优化问题转化为一系列简单的容易解决的子问题，用这一系列子问题的解去逼近原问题的解。如： 简约梯度法、惩罚函数法等等。,本章主要介绍几种常用的约束优化方法： 随机方向搜索法、复合形法。,图4.1约束随机方向搜索法基本原理,4.4.1 约束随机方向搜索法 基本原理 约束随机方向搜索法是解决小型约束最优化问题的一种常用的直接求解方法。其基本原理如下：,约束随

46、机方向搜索法中的两个关键问题,初始点的选择,(4-2),随机搜索方向的产生,(4-3),图4.2二维随机向量,(4-4),迭代步骤,4.4.2 复合形法 基本原理,图4.3 复合形法的基本原理,(4-5),初始复合形的产生,(4-6),(4-7),(4-8),图4.4 非可行点如何调入可行域示意图,图6.4 非可行点如何调入可行域示意图,迭代步骤,图4.5 可行域是非凸集的情况,4.4.3遗传算法,传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 漫步法（Random Walk）、模拟退火法、GA,关于优化问题,比较：,传统的优化方法,1）依赖于初始条件。 2）与求解

47、空间有紧密关系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。 3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数； 共轭梯度法隐含地依赖于梯度。,全局优化方法,1）不依赖于初始条件； 2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况, 选择运算 交换操作 变异,遗传算法的基本运算,遗传算法基本原理,模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传 空间，把可能的解编码成一个向量染色体，向量的每个 元素称为基因。 通过不断计算各染色体的适应值，选择最好

48、的染色体，获 得最优解。,选择运算 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲 区），为以后染色体交换、变异，产生新的染色体作准备。,选择方法适应度比例法（转轮法） 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率：Pc,xi 为种群中第i个染色体，,具体步骤,1）计算各染色体适应度值 2）累计所有染色体适应度值，记录中间累加值S - mid 和最 后累加值 sum = f(xi) 3） 产生一个随机数 N，0 N sum 4） 选择对应中间累加值S - mid 的第一个染色体进入交换集 5） 重复（3）和（4），直到获得足够的染色体。,举例： 具有6个染色体的二

49、进制编码、适应度值、Pc累计 值。,染色体的 适应度和所占的比例,用转轮方法进行选择,染色体被选的概率,被选的染色体个数,10个染色体种群按比例的选择过程,交换操作,方法:随机选择二个染色体(双亲染色体),随机指定一点或多点, 进行交换,可得二个新的染色体(子辈染色体).,新的子辈染色体: A 11010001 B 01011110,模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.,变异,复制不能创新,交换解决染色体的创新,GA的流程,简单遗传算法（GA）的基本参数,种群规模 P:

50、 参与进化的染色体总数. 代沟G: 二代之间不相同的染色体数目,无重叠G = 1; 有重叠 0 G 1 选择方法: 转轮法,精英选择法,竞争法. 交换率: Pc 一般为60100%. 变异率: Pm 一般为0.110%,举例:,变异概率取0.001,初始种群和它的适应度值,染色体的交换操纵,举例：,14,步骤1）编码：确定二进制的位数；组成个体（染色体）,步骤2）选择种群数P 和初始个体，计算适应度值， P = 20；,步骤3）确定选择方法；交换率PC；变异率Pm。 选择方法用竞争法； PC = 0.7, Pm = 0.05,计算结果： 8代后，f(x,y) =0.998757, 41代后，f

51、(x,y) =1.00000, x =3.000290, y =2.999924. 160次适应度计算，达到最优值。,遗传算法的基本数学问题,一个重要的定理图式定理,什么叫图式？,描述种群中染色体相似性的字符串。,（*为通配符）,图式的描述：, 定义长度（H)H左右二端有定义位置之间的距离；, 图式的阶次(或固定长度)O(H）H中非*位（有定义位） 的个数。,图式定理的推导,图式在选择过程中的增加.,经过选择,在t+1代,图式H的数量m(H,t+1)为:,图式在交换中的破坏,图式在变异中的破坏,经过选择、交换、变异后在t+1中，图式H的数量：,图式定理：在选择、交换、变异的作用下，阶次低、定义

52、长度短、适应度高的图式（模块）将按指数增长的规律，一代一代地增长。,遗传算法在应用中的一些基本问题,1）知识的编码,2）适应度函数。 a) 适应度函数值必须非负。根据情况做适当的处理,二进制和十进制的比较：二进制有更多图式和更大的搜索范围；十进制更接近于实际操作。,3）全局最优和收敛性。 根据图式定理，对于具有“欺骗性”函数，GA有可能落入局部最优点。,b）为保持种群的多样性，防止“超级”染色体“统治”种群。,欺骗性函数,图式划分：指引相互之间竞争的定义位为同一集合的一组图式。 如#表示定义位，则H1=*1*0*，H2=*0*1* ，H3=*1*1*， H4=*0*0* 同属于划分*#*#*。

53、,总平均适应度（OAF）：对一个给定图式，OAF即为其成员 的平均适应度。,欺骗性函数包含全局最优的图式其OAF不如包含局部最优的OAF，这种划分称为欺骗划分，它会使GA陷入局部最优。如最高阶欺骗函数有k个定义位，则此函数称k阶欺骗。,举例：3位欺骗函数, 高级GA算法,1）操作的改进,2）算法的改进,选择方法改进：精英法（竞赛法）、置换式和非置换式 随机选择法，排序法。,交换方法的改进：多点交换；重组运算,微种群遗传算法（GA）,双种群遗传算法（DPGA）,重组运算：解决染色体分布过于集中问题。把适应度函数做进一步处理。,终止条件：1）达到预定指标；2）达到预定代数。,GA算法,双种群算法（

54、 DPGA）,基本思想：利用人类社会分工合作的机理。,分成：全局种群粗搜索，寻找可能存在的最优区域； 局部种群 精搜索在全局划定的区域内，寻找最优点。,测试函数：,遗传算法的应用：1）神经网络结构参数的选择 2）滑模控制中应用 3）倒立摆控制中应用,4.5 基于MATLAB优化工具箱的优化计算,4.5.1 MATLAB优化工具箱,一、常用的优化功能函数 求解线性规划问题的主要函数是linprog。 求解二次规划问题的主要函数是quadprog。 求解无约束非线性规划问题的主要函数是fminbnd、fminunc和fminsearch。 求解约束非线性规划问题的主要函数fmincon. 求解多目

55、标约束非线性规划问题的主要函数是fgoalattain和fminimax。,二、一般步骤,建立目标函数文件,针对具体工程问题建立优化设计的数学模型,不等式约束条件表示成g(X)0的形式,建立调用优化工具函数的命令文件,文件内容：必须的输入参数、描述标函数表达式等 存储：以自定义的目标函数文件名存储在文件夹中,建立约束函数文件,文件内容：必须的输入参数、约束函数表达式等 存储：以自定义的约束函数文件名存储在文件夹中,将优化设计的命令文件复制到MATLAB命令窗口中进行运算求解。,分析优化设计的数学模型，选择适用的优化工具函数 文件内容：初始点，设计变量的边界约束条件， 运算结果输出等内容 存储：

56、以自定义的命令文件名存储于文件夹中。,4.5.2 线性规划问题,一、线性规划数学模型,1.主要应用对象： （1）在有限的资源条件下完成最多的任务； （2）如何统筹任务以使用最少资源。 2.数学模型形式： min f TX s.t. AXb （线性不等式约束条件） AeqX=beq （线性等式约束条件） lb X ub （边界约束条件）,约束条件,决策变量,目标函数,非负数,线性,3.MATLAB中函数调用格式 xopt, fopt=linprog( f, A, b, Aeq, beq, lb, ub, x0, options),最优解,最优值,目标函数各维变量系数向量,初始点,可选项,二、例题

57、,生产规划问题：某厂利用a,b,c三种原料生产A,B,C三种产品，已知生产每种产品在消耗原料方面的各项指标和单位产品的利润，以及可利用的数量，试制定适当的生产规划使得该工厂的总利润最大。,x1,x2,x3,2x1,4x2,3x3,3x1,4x2,2x3,2x1,x1,x2,3x2,2x3,2x3,+,+,+,+,+,+,+,+,3.确定约束条件：,X=x1,x2,x3T,4.编制线性规划计算的M文件 f= - 2, -4, -3; A=3,4,2;2,1,2;1,3,2; b=600;400;800; Aeq=;beq=; lb=zeros(3,1); xopt,fopt=linprog(f,

58、A,b,Aeq,beq,lb),二、例题,解： 1.确定决策变量：,max2x1+4x2+3x3,3x1+4x2+2x3600,2x1+x2+2x3400,x1+3x2+2x3800,设生产A、B、C三种产品的数量分别是x1,x2,x3，决策变量：,根据三种单位产品的利润情况，按照实现总的利润最大化，建立关于决策变量的函数：,2.建立目标函数：,根据三种资料数量限制，建立三个线性不等式约束条件,5.M文件运行结果： Optimization terminated successfully. xopt =0.0000 66.6667 166.6667 fopt=-766.6667,x1,x2,x30,xopt, fopt=linprog( f, A, b