资源预览内容
第1页 / 共85页
第2页 / 共85页
第3页 / 共85页
第4页 / 共85页
第5页 / 共85页
第6页 / 共85页
第7页 / 共85页
第8页 / 共85页
第9页 / 共85页
第10页 / 共85页
亲,该文档总共85页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
Lchming ,、借助最优化数值计算方法与计算机技术,求取工程问题的最优设计方案(最优设计参数)。包括:(1)建立数学模型;(2)运算求解。, 一、设计变量(参数):可以进行调整和优选的独立参数 连续变量和离散变量,二、约束条件:对设计变量的取值加以某些限制的条件,三、目标函数:设计中所追求的目标,且可由设计变量表示的函数。,、设计变量的数目称为优化问题的维数 设计空间:由n个设计变量为坐标所组成的实空间。所有设计点的集合。 等值线或等值面:具有相等目标函数值的设计点构成的线或面。 可行域 :在设计空间中,由满足所有约束条件的设计点组成的区域。,、寻优思路,极值,极值,新点的可行性条件、适用性条件。 收敛精度指相邻两次寻优的设计点或目标函数值的接近程度。寻优是逐渐逼近极值点的过程。,梯度方向是函数值增加最快的方向,方向导数,目标函数和不等式约束函数都是凸函数,则该约束优化问题为凸规划。,目标函数在极值点附近是二次函数,泰勒展开式,海森矩阵正定,无约束优化问题的极值条件,题 目,1、泰勒展开式,将高次函数简化 2、二次型 3、判断海森矩阵是否正定,第4章 一维优化方法,4-1 确定极值点所在区间的进退法 4-2 一维盲人探路优化方法 4-3 区间消去类优化方法 4-4 插值类优化方法 4-5 C语言调试的要点 4-6 小结,基本假设:单峰函数。方法适合于复杂区间,只要是连续变量的函数,只一极小点。,在给定区间内仅有一个极小点的函数称单峰函数。下图为单峰函数的几种情况:,图中可以看出,单峰函数可以是不可微或甚至是不连续函数。,4-0 引言,优化问题的解法:解析法和数值近似法。 当采用数学规划法(有方向)寻求多元函数的极值点时,一般要进行一系列如下格式的迭代计算:,当方向 给定,求最佳步长 就是求一元函数 :,的极值问题。这一过程也是一维搜索。,一维搜索方法分类: (a) 区间消去类方法; (b)函数逼近(插值)类方法,搜索方向是根据几何概念和数学原理,由目标函数和约束条件的局部信息状态形成的。,向左走,向右走Si prioche, Si loin,只研究单谷(峰)区间,因为其它的可切割 在给定区间内仅有一个谷值的函数称为单谷函数,其区间称为单谷区间。,4-1 确定极值点所在区间的进退法,特点: 函数值:“大小大” 图形:“高低高”,单谷区间中一定存在极小点,其寻找步骤:,第一步:确定初始单谷区间; 第二步:使区间缩小。,(1)选定初始点a1, 初始步长hh0,a2=a1+h, 计算 y1f(a1), y2f(a2)。 (2)比较y1和y2。 (a)如y1y2, 向右前进; 转(3)向前, (b)如y10时,a,b=a1,a3; hy3, a1=a2, a2=a3, 转(3)继续探测。,(1)选定初始点a1, 初始步长hh0,a2=a1+h, 计算 y1f(a1), y2f(a2)。 (2)比较y1和y2。 (a)如y1y2, 向右前进; 转(3)向前, (b)如y10时,a,b=a1,a3; hy3, a1=a2, a2=a3,加倍步长 h2 h, 转(3)继续探测。,进退法,每跨一步为前一次步长的2倍,直至函数值增加为止。,二、用进退法确定最小值所在区间的程序框图,int JT(double x3,double h) /*进退法确定区间子程序(返回计算目标函数值的次数):x1 x2 x3,初始*/ double y3,dum; /*函数值,中间变量*/ int k=0; /*步数,保证适用性*/ y0=func(x0); /*初始点函数值*/ x1=x0+h; y1=func(x1); if(y0y1) /*如果 ,则反向,调头*/ h=-h; dum=x0;x0=x1;x1=dum; dum=y0;y0=y1;y1=dum; ,for(;) /*计算循环*/ h=2*h; /*步长加速*/ x2=x1+h; y2=func(x2); /*第三点及其目标函数值*/ if(y1x2) /*如果是退的,则调整*/ dum=x0;x0=x2;x2=dum; return(K); /*返回计算目标函数值的次数*/ else /*否则,弃去第一点,重新找*/ x0=x1;x1=x2; y0=y1;y1=y2; /*end for(;)*/ /*结束JT*/,三、关于用进退法求函数最小值所在区间的说明,该求最小值所在区间的方法思想简单、思路明确,但是,多数优化问题的目标函数并非单谷函数,如果初始步长太大,就有可能出现不收敛的情况。 为了保证收敛和所确定的区间较小,同时考虑到多维寻优时,给出的初值点一般靠近极值点,区间确定的初始步长值应给出较小的值,如取收敛精度值的 10 倍左右。,X0=1, h=1,1,h=1,4,8,21,2,12,9,10.5,h=2,h=4,x0 x1 x2,x0 x1,x2,x,4-2 一维盲人探路优化方法,基本思想 盲人走路时,往往拿根竹竿试探前面的路面,在确保安全之后再迈出或大或小的脚步。先探路再迈步的思想用于多维优化方法即得出爬山类方法,用于一维优化问题极值点所在区间的确定即得出进退法。如果还将调整脚步大小的思想用于一维优化方法即得出“一维盲人探路优化设计方法”。 为提高寻优效率,以步长增倍提高接近极值点的速度,以步长减半提高收敛速度,以符合适用性条件作为更新当前点的前提。,算法步骤,(1)选定初始点x1为当前点,初始步长hh0,收敛精度值(=y2,,则y1=y2,x1=x2,h=h+h; (b)如y1=y2,,则y1=y2,x1=x2,h=h+h; (b)如y1=y2,,则y1=y2,x1=x2,h=h/2; (b)如y1,则转(7)继续。 (9)取x1、x2中目标函数值最小的点作为最优点,返回;,算法的程序流程图,一阶导数法,适当增减步长。非首点换方向后每步减小步长。,平分法,设目标函数在极值点所在区间a,b上为下单峰函数且具有连续一阶导数,根据区间中点目标函数的导数值,确定去掉的一半区间。把保留下来的区间仍计为a,b,重复前面的过程,直到区间a,b的长度充分小,满足所要求的精度为止。该方法是线性收敛的,收敛比为1/2。,4-3 区间消去类优化方法,搜索区间确定之后,采用区间消去法逐步缩短搜索区间,从而找到极小点的数值近似解。 假定在搜索区间内a,b 任取两点a1,b1,f1f(a1), f2f(b1),在极值点所在的区间中,取两点,将区间分为三段,根据目标函数的单峰特点,极值点不在目标函数值较大的点外侧,因此搜索区间得以缩短。,f1f(a1), f2f(b1) (1)如f1f2, 则缩小的新区间为a1,b; (3)如f1=f2, 则缩小的新区间为a1,b1,综合为两种情况: 若 则取 为缩短后的搜索区间。 若 则取 为缩短后的搜索区间。,一、黄金分割法Golden Section Method的基本思想,黄金分割法是建立在区间消去法原理基础上的试探方法。 在搜索区间内a,b适当取两点 ,将区间分成三段; 两个分割点相对于区间两端对称,在保留下来的区间内再找一分割点所形成的三段,与原区间的三段具有相同的比例分布。即每次区间削去只须计算一个分割点。,将区间分成三段,黄金分割法还要求在保留下来的区间内再找一点所形成的三段区间,与原来的三段区间具有相同的比例分布 。,四个点三段。削去一段后,剩下三个点。 再找一个点组成的三段与原来的三段成比例,f(a1),f(a2),f(a1),f(a2),黄金分割法要求两个分割点:,黄金分割法区间消去示意:,区间缩短率,黄金分割法应该是计算量小 收敛准则 (1)区间绝对精度 ; (2)区间相对精度 ; (3)函数值绝对精度 ; (4)函数值相对精度 一)黄金分割法特点 (1)不必要求目标函数连续可微,只要利用函数值大小的比较,即可很快地找到最优点; (2)除了第一次缩小区间要计算两个点及其函数值以外,其余每次只要计算一个点及其函数值; (3)可靠性好(掉进井里不会出来),二、黄金分割法的迭代过程和程序框图 1)给出初始搜索区间及收敛精度 ,将 赋以0.618。 2)按坐标点计算公式计算 , ;并计算其对应的函数值。 3)根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式,需进行区间名称的代换,并在保留区间中计算一个新的试验点及其函数值。 如果 ,则新区间 令 ,记N0=0; 如果 ,则新区间 , 令 , 记N0=1; 4)检查区间是否缩短到足够小和函数值收敛到足够精度,如果收敛条件满足,则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5)。,5)产生新的分割点: 如N0=0,则取 ; 如N0=1,则取 , 转向3)进行新的区间缩小。,a x1 x2 b a x1 x2 b,例 3-1 用黄金分割法求函数 f ( x ) = 3 x 2 4 x + 2 的极小点,给定 x 0 = 0 , h = 1, = 0 . 2。,解: 1)确定初始区间 x1=x0=0, f1=f(x1)=2 x2=x1+h=0+1=1, f2=f(x2)=1 由于f1f2, 应加大步长继续向前探测。h=2h,x3= x2+h=1+2=3, f3=f(x3)=17 由于f2f3,可知初始区间已经找到,即a,b=x1,x3=0,3,2)用黄金分割法缩小区间 第一次缩小区间(分割点): x1=0+0.382 (3-0)=1.146, f1=1.356 x2=0+0.618 (3-0)=1.854, f2=4.896 f10.2,第二次缩小区间:指出区间、分割点即可 令 x2=x1=1.146, f2=f1=1.356 x1=0+0.382(1.854-0)=0.708, f1=0.672 由于f1f2, 故新区间a,b=x1,b=0.708, 1.854 因为 b-a=1.236-0.472=0.7640.2, 应继续缩小区间。,第三次缩小区间: 令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618 (1.236-0.472)=0.944, f2=0.747 由于f1 0 . 2 , 应继续缩小区间。,第四次缩小区间: 令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382 (0.944-0.472)=0.652, f1=0.223 由于f10.2, 应继续缩小区间。,第五次缩小区间: 令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382(0.764-0.472)=0.584, f1=0.262 由于f1f2, 故新区间a,b=x1,b=0.584, 0.764 因为 b-a=0.764-0.584=0.180.2, 停止迭代。,极小点与极小值: x*=0.5 (0.584+0.764)=0.674, f(x*)=0.222,int golden(a, b, e, x, y) double x1,x2,y1,y2; x1=a+0.382*(b-a); y1=func(x1); x2=a+0.618*(b-a); y2=func(x2); for(;) /*区间消去循环*/ if(y1y2) /*如果须消去右边*/ b=x2;x2=x1;y2=y1; x1=a+0.382*(b-a); y1=func(x1); ,else /*消去左边*/ a=x1;x1=x2;y1=y2; x2=a+0.618*
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号