一维搜索法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,大家好,*,第三章 常用的一维优化方法,3,1,概述,3,2,单峰区间的确定,3,3,黄金分割法,3,5,二次插值法,3,4,Fibonacci,法,作业,1,大家好,3,1,概述,一、问题的提出,1,、实际设计工作中会遇到一维优化设计问题,在长为,350cm,、宽为,260cm,的长方形不锈钢板的四角，各剪去一个小正方形，做成一个无盖的储水箱，试确定正方形的边长，使储水箱的容积最大。,2,大家好,2,、多维优化设计转化为一维优化设计问题,多维优化问题求解过程：,3,大家好,二、一维优化方法的分类,1.,解析法,2.,数值法,由,方程求根法,区间收缩法,二分法、切线法、割线法等,分数（,Fibonacci,）,法、黄金分割（,0.618),法、插值法等,得,4,大家好,3,2,单峰区间的确定,定义 设,*,是,(),的极小点，若存在闭区间,a,，,b,，使得,*a,，,b,，且使函数值呈“高,低,高”的形态，即函数,(),在闭区间,a,，,b,中有唯一极小点，则称,a,，,b,是,(),单峰区间,.,一、单峰区间的定义,非单峰区间,单峰区间,5,大家好,二、单峰区间的确定,确定搜索区间的一种简单的方法是进退法，其基本思想是从某一点出发，按一定的步长，确定函数值呈“高,低,高”的三点。如果一个方向不成功，就退回来，再沿相反的方向寻找。具体算法步骤如下：,(4),如果,k=1,则置,2,=,2,=,和,h=-h,转,(2);,否则置,1,=,2,1,=,2,2=3,2,=,3,3=,3,=,并令,a=min,1,3,b=max,1,3,停止计算,.,(1),取初始步长,h,，置初始值,3,=0,，,3,=,(,3,),，并置,k=0.,(2),置,=,3,+h,，,=,(),和,k=k+1.,(3),如果,3,则置,2,=,3,2,=,3,3,=,3,=,和,h=2h,k=k+1,转,(2);,6,大家好,二、单峰区间的确定,7,大家好,开始,输入：,h,置,3,=0,，,3,=,(,3,),，,k=0,置,=,3,+h,，,=,(),k=k+1,2,=,3,2,=,3,3,=,3,=,h=2h,k=k+1,2,?,yes,no,a=a,1,b,=,b,a=a,b,=a,2,9,大家好,黄金分割法,(Golden,Section,Method),又称为,0.618,法，是用于在单峰函数区间上求极小的一种方法。其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断减少，当区间长度缩短到一定程度时，就得到函数极小点的近似值。,3,3,黄金分割法,一、黄金分割法的取点原则,1.,对称取点,2.,等区间收缩率,3.,留点可用,10,大家好,二、黄金分割法的区间收缩率,11,大家好,(1),置初始搜索区间,a,b,，并置精度要求,，并计算左右试探点,a,l,=a+0.382(b-a),a,2,=a+0.618(b-a),及相应的函数值,l,=,(a,l,),，,2,=,(a,2,).,三、黄金分割法的步骤,(3),若,|b-a|,做,:,如果,l,2,，则置,*,=a,1,；否则置,*,=a,2,，停止计算,(,*,作为问题的解,),。否则转,(2).,(2),如果,l,2,，去掉区间,1,，,a,l,.,详细计算结果见下表,14,大家好,不要求每次迭代区间的收缩比不变,而希望在试验点个数相同的情况下，找出一种选取试验点的最佳策略，使得最终的极小区间的长度达到最小，换句话说，如果规定试验点的个数为,n,，且最终区间长度为,1,，,问如何选取这,n,个点，使得原始区间的长度最大？,令,L,n,表示试验点数为,n,、最终区间长度为,1,时，原始区间,a,b,的最大可能长度。,设,l,为左试探点，,r,为右试探点，如果极小点,*,位于区间,a,，,l,，则在此区间内至多还可以有,n-2,个试验点，因此,l,-a,L,n,2,.,3,4 Fibonacci,法,15,大家好,另一方面,如果极小点,*,位于区间,l,b,内,则包括,r,在内,还可以作,n-1,个试验点，所以,b-,l,L,n-1,.,因此,b-a=(b-,l,)+(,l,-a),L,n,2,+L,n-1,故有如下关系式,:,L,n,L,n,2,+L,n-1,显然,不计算函数值和仅计算一点处的函数值都不能使极小区间缩小，即,L,0,=,L,1,=1.,由此可得，如果原始区间长度满足递推关系,F,0,=,F,1,，,F,n,=,F,n,2,+F,n-1,则,F,n,将是最大原始区间的长度,.,16,大家好,F,n,称为,Fibonacci,数。,Fibonacci,方法的基本思想与,0.618,法相同,.,在搜索区间,a,b,上,先取左、右试验点,l,和,r,比较函数值,f,(,l,),和,f,(,r,),重新确定搜索区间,.,(1),若,f,(,l,),f,(,r,),，去掉区间,a,r,令,a=,l,，,b=b,再计算新的试探点,18,大家好,所以,Fibonacci,方法与,0.618,法一样,除第一次外,以后每次只计算一个点处的函数值,.Fibonacci,方法每次保留的区间长度为,F,k-1,F,k,因此若计算,n,个试验点,最终的区间长度。因此,任给一精度要求,要求最终的区间长度小于,即有,因此,任给一精度要求,要求最终的区间长度小于,即有,那么选择,n,满足,19,大家好,(1),置初始搜索区间,a,，,b,，并置精度要求,，选取分离间隔,（,b-a,）,，并计算左右试探点,l,=a+,F,n-2,/,F,n,(b-a),，,r,=a+,F,n-1,/,F,n,(b-a),及相应的函数值,f,l,f,(,l,),f,r,f,(,r,),。,算法步骤,(2),置,n=n-1,。,(3),如果,f,r,f,(,r,),，则置,b=,r,，,r,=,l,，,f,r,f,l,，。如果,n2,则计算,l,=a+,F,n-2,/,F,n,(b-a),，,f,l,f,(,l,),；否则计算,l,=,r,-,，,f,l,f,(,l,),。,(4),f,l,f,r,，置,a=,l,，,l,=,r,，,f,l,f,r,；如果,n2,，则计算,r,=a+,F,n-1,/,F,n,(b-a),，,f,r,f,(,r,),；否则计算,r,=,l,+,，,f,r,f,(,r,),。,(5),若,n=1,，做：如果,f,r,f,(,r,),，则置,=,r,；否则置,=,r,，停止计算,(,作为问题的极小点,),。否则转,(2),。,20,大家好,插值法是一类重要的一维搜索方法，其基本思想是利用搜索区间上某些点的信息构造插值多项式,(,通常不超过三次,)p(),，逐步用,p(),的极小点来逼近,(),的极小点,*,。当,(),有比较好的解析性质时,插值法比区间收缩法,(,如,0.618,法,),的效果好,.,本节介绍三种较为常见的插值法,.,3,4,二次插值法,在单峰区间,a,b,中，已知函数在三点,1,、,2,、,3,（,1,2,2,、,3,2,，即三点满足“两端高中间低”。,这三个点可由得到：,一、二次插值法的思想,21,大家好,由数值分析的知识,得到过三个点,(,1,，,1,),、,(,2,，,2,),、,(,3,，,3,),的二次插值公式为,对上式求导数，并求解方程,p()=0,，得到,p(),的极小点,22,大家好,用,作为,*,的估计值,并计算,处的函数值,=,(),。,第一次的近似结果往往不够理想，需要作进一步的近似。,现已得到四个点,(,1,，,1,),、,(,2,，,2,),、,(,3,，,3,),和,(,，,),如何选取三个点呢,?,仍然按照最初的原则，选取满足“两端高中间低”的三个点。,二、二次插值法的区间收缩过程,23,大家好,(1),取初始点,1,2,2,，,2,3,，置精度要求,.,三、二次插值法算法步骤：,(2),计算,A=2,1,(,2,-,3,)+,2,(,3,-,1,)+,3,(,1,-,2,),若,A=0,，则置,=,2,=,2,停止计算,(,输出,的信息,).,(3),计算,=,1,(,2,2,-,3,2,)+,2,(,3,2,1,2,)+,3,(,1,2,-,2,2,)/A,若,3,，,则置,=,2,=,2,，,停止计算,(,输出,的信息,),。,24,大家好,(4),计算,=,(),。若,|-,2,|,则停止计算,(,作为极小点,),。,(5),如果,(2,3),，则,:,若,2,，则置,1,=,2,，,1,=,2,，,2,=,，,2,=,；,否则置,3,=,3,=,;,否则,(1,2):,若,2,，则置,3,=,2,3,=,2,，,2,=,2,=,；,否则置,1,=,2,=,，,转,(2).,25,大家好,四、二次插值法程序框图：,26,大家好,27,大家好,作业,用黄金分割法编程求解函数,的极小点,X,（,1,）,。,28,大家好,优化方法程序实现之一,用黄金分割法编程求解函数,的极小点,X,（,1,）,。,29,大家好,结束,30,大家好,