《维搜索法》PPT课件.ppt

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