《现代设计方法优化设计一维搜索.pptx》由会员分享，可在线阅读，更多相关《现代设计方法优化设计一维搜索.pptx（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本章主要内容 优化设计概述 优化设计的数学基础 一维探索优化方法 无约束优化方法 约束问题优化方法 优化设计若干问题第1页/共38页 优化设计概述 优化设计的数学基础 一维探索优化方法 无约束优化方法 约束问题优化方法 优化设计若干问题 一维搜索的概念 单峰区间 进退法 黄金分割法 平分法 切线法 二次插值法 一维搜索优化方法第2页/共38页数值迭代过程中，任何一次迭代，总是从某个已知点 出发，沿着给定的方向 （用某种优化方法确定）搜索到目标函数在该方向上的极小值点 ，这个过程称为一维搜索。一维搜索不仅可以求解一维优化问题，同时也是求解多维优化问题的基本步骤。怎么理解“一维”的含义？一维搜索的
2、概念第3页/共38页对“一维”的理解寻找目标函数在指定方向上的极小点，在计算上就是从 沿 前进多少的问题，即求步长因子 的问题。从这个意义上讲，一维搜索是一个求解关于 的单元目标函数的过程。一维搜索寻找合适的 ，使 最小“一维”是指“一个方向”（）；第4页/共38页任一次迭代，都是求使得即其中：表示步长因子 表示最优步长因子一维搜索的数学形式 第5页/共38页一维搜索的几何意义 从 出发，沿方向 一维搜索，就是求方向 与等值线的切点，此时的步长因子即为最优步长因子。第6页/共38页子优化问题:Find Minimize ()=f(x(k)+s(k)fs(k)X(k)子优化问题的一阶必要条件:(
3、)=0 f(x(k)+s(k)Ts(k)=0一维搜索的几何意义 第7页/共38页假设第k次得到的区间 ，若 ，则可取 作为极小点。一维搜索的基本思想 一维搜索就是要在初始单峰区间中求单峰函数的极小点。所以找初始单峰区间是一维搜索的第一步，然后将初始单峰区间逐步缩小，直至包括极小点的区间长度小于给定的一个正数 ，此 称为收敛精度或迭代精度。第8页/共38页缩小区间的区间消去法 第9页/共38页 对于所有的一维搜索方法，首先遇到的共同问题是：如何确定一个初始搜索区间，使该区间内含有函数的极小点，且在该区间内函数有唯一的极小点 ，这个初始搜索区间就是单峰区间。单峰区间第10页/共38页 设函数f(x
4、)在区间 内有定义，且(1)在区间内存在极小点 ，即有 (2)区间 上的任意x，均满足 ；区间上的任意x，有 用解析法给单峰区间下一个定义：则称闭区间 为函数f(x)的单峰区间。第11页/共38页单峰区间的特点：单峰区间内，在极小点的左边，函数是严格减少的，在极小点的右边，函数是严格增加的；如果区间 是一个单峰区间，x是区间内的一点，则 两个不等式中必有一个成立；单峰区间内的函数图形表现为“高低高”的形态。应用这一特征可以确定单峰区间。第12页/共38页如果函数具有多个极小点，则表现为多峰函数。此时，需要对变量取值范围进行适当的划分，使每一个子空间只包含一个极小点，才能进行一维搜索。一维搜索时
5、，同样需要在每个子空间内寻找单峰区间。注意：第13页/共38页确定单峰区间的进退法确定单峰区间的进退法区间搜索的终止条件:找到三点a,c,b,满足 (a)(c)(b),输出a,b.acb算法思想先在初始点的左右方向中确定一个下降方向.沿着下降方向向前搜索,直到遇到上升点.搜索的前一点与上升点构成所求区间.另外,用到步长加倍,提高搜索效率.第14页/共38页进退法进退法算法 1.初始化.k=0,k=0,hk=h0,t=t01.计算0=(0).2.比较目标值.k+1=k+hk,计算k+1=(k+1).若k+1k,转步3;否则,转步4.3.加大步长.hk+1=thk,=k,k=k+1,k=k+1,k
6、=k+1,转步2.4.反向搜索.若k=0,转换搜索方向,hk=-hk,=k+1,转步2;否则,停止.输出a=min,k+1,b=max,k+1.k-迭代变量;k-当前点;-前一点;k+1-后一点;hk-步长t-步长加倍系数 第15页/共38页进退法进退法举例 k-迭代变量;k-当前点;-前一点;k+1-后一点;hk-步长t-步长加倍系数()014235t=1.5 a=3 b=5 第16页/共38页例：例：试用进退算法确定函数 的初始搜索区间 ，设初始点 ，初始步长h=1。采用不同的初始点、不同的初始步长得到的初始单峰区间可能不一样，但只要这个单峰区间包含极小点，就是正确的。第17页/共38页基
7、本原理 对于目标函数f(x)，在区间a,b内，适当插入两个内分点x1和x2(x1 f(x2)时，极小点必在x1,b中；当f(x1)f(x2)时，极小点必在a,x2中。黄金分割法第18页/共38页无论发生在那种情况，都将包含极小点的区间缩小，即可删去最左段或最右段，然后在保留下来的区间上做同样的处理，如此迭代下去，将使搜索区间逐步减小，直到满足预先给定的精度（终止准则）时，即获得一维优化问题的近似最优解。消去函数值大的内分点到同一侧端点之间的区间第19页/共38页黄金分割法要求在区间a,b中插入的两点位置是对称的，如图所示，ax1=x2b。设区间长为L，插入的两个点把区间分成较长的一段和较短的一
8、段(L )。这样，无论删去那一段，保留区间长度总是。第20页/共38页第21页/共38页 黄金分割法的迭代步骤 （1）给定初始单峰区间a,b及允许误差0；（2）计算内分点及其函数值（3）比较函数值f1和 f2的大小；根据比较结果缩短搜索区间第22页/共38页A.当 f1 f2 时，极小点必在a,x2中，则B.当 f1 f2 时，极小点必在x1,b中，则第23页/共38页（4）判断是否满足精度要求。若新区间已缩短至预定精度要求，即 ，则转第5）步；否则转第3）步，进行下一次迭代计算。（5）输出最终区间的中点作为近似最优点，其对应的函数值即为最优值，他们组成的最优解为：第24页/共38页a11b1
9、1a22b22只计算一个新点就能将区间缩小倍.bk+1-ak+1=(bk-ak)另外,设,在a,b中对称 bk-k=k-ak1=a1+(1-)(b1-a1)1=a1+(b1-a1)2=a2+(b2-a2)=a1+(1-a1)=a1+(a1+(b1-a1)-a1)=a1+2(b1-a1)由1=2,1-=2,=(5-1)/2=0.618 算法特点：第25页/共38页(2)算法 1.初始化.a1,b1,1=a1+0.382(b1-a1),1=a1+0.618(b1-a1),k=1.计算(1),(1).取0.2.比较目标值.若(k)(k)转步3;否则,转步4.3.若bk-k,停止,输出k.否则,ak+
10、1=k,bk+1=bk,k+1=k.k+1=ak+1+0.618(bk+1-ak+1),计算(k+1),转步2.4.若k-ak,停止,输出k.否则,ak+1=ak,bk+1=k,k+1=k.k+1=ak+1+0.382(bk+1-ak+1),计算(k+1),转步2.第26页/共38页【例8】试用黄金分割法求解优化问题：Nabx1x2f1f20-3.0005.0000.0561.9440.1157.6671-3.0001.944-1.1110.056-0.9860.1152-3.0000.056-1.832-1.111-0.306-0.9873-1.8320.056-1.111-0.665-0.
11、987-0.8884-1.832-0.665-1.386-1.111-0.851-0.9875-1.386-0.665-1.111-0.940-0.997-0.9966-1.111-0.665-0.940-0.835-0.966-0.9737-1.111-0.835-1.006-0.940-0.999-0.9968-1.111-0.940-1.046-1.006-0.996-0.999循环迭代历次结果教材P100例3-5,自己对照学习第27页/共38页适于目标函数易求一阶或二阶导数的情形。平分法是取具有极小点的单峰函数的探索区间s,e的中点m作为计算点，并根据函数在m处的一阶导数 来判断应该消
12、去 m 点左右哪一半探索区间，收缩探索区间。平分法的收缩率约为0.5。给定k=0,s(0),e(0),1,2 时，平分法的迭代步骤如下：平分法第28页/共38页1）计算 m(k)=(s(k)+e(k)/2,如 ，则终止迭代，并取*=s(k)，否则转下一步；2）计算 ，如 ，则终止迭代，并取*=s(k)，否则转下一步；3）如 0，则取新区间为s(k),m(k),否则为m(k),e(k)，当k=k+1后转 1）。第29页/共38页适于目标函数 f(x)的二阶导数均大于0的情形。方法：采用目标函数的 曲线上某点 x(k)的切线代替该点附近的导函数弧来逼近一阶导函数根*。切线法第30页/共38页切线法
13、的原理图ya(1)(0)b(2)*y=f(x(k)+(k)s)0第31页/共38页经过有限次迭代，当 k 足够大时，总可以满足：此时可近似认为*=(k)第32页/共38页例：采用切线法求一元函数 f(x)=x2-7x+10在初始区间1,7内，迭代精度=0.35 下的最优解。解：（1）则 f(x)为区间1,7内的凸函数，存在最小值。（2）取 x(0)=1,得 存在 （3）取 x*=x(1)=3.5，则 f(x*)=-2.25。第33页/共38页 适于目标函数易求一阶或二阶导数的情形。插值法：当目标函数比较复杂，不易通过 lim f(x(k)+(k)s)=f(*)使目标函数达到极小值时，可以采用一个容易求解极小值的较低次函数 p(x)，在满足一定的条件下来近似代替 f(x)。p(x)为二次函数时称为二次插值法，p(x)为三次函数时称为三次插值法。二次插值法第34页/共38页三点二次插值123二次极值点下一循环以23为插值点收敛阶为1.32,比0.618方法速度快.|xk+1-x*|C|xk-x*|aa为收敛阶第35页/共38页优化问题一维优化问题（1个设计变量）多维优化问题（多个设计变量）无约束多维问题单目标函数的优化问题多目标函数的优化问题有约束多维问题第36页/共38页作作 业业P59:2-10第37页/共38页谢谢您的观看！第38页/共38页