《维搜索法》PPT课件.ppt

《《维搜索法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《维搜索法》PPT课件.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 常用的一维优化方法常用的一维优化方法331 1 概述概述332 2 单峰区间的确定单峰区间的确定333 3 黄金分割法黄金分割法335 5 二次插值法二次插值法334 4 FibonacciFibonacci法法作业作业331 1 概述概述一、问题的提出一、问题的提出1 1、实际设计工作中会遇到一维优化设计问题、实际设计工作中会遇到一维优化设计问题在长为在长为350cm350cm、宽为、宽为260cm260cm的长的长方形不锈钢板的四角，各剪去一方形不锈钢板的四角，各剪去一个小正方形，做成一个无盖的储个小正方形，做成一个无盖的储水箱，试确定正方形的边长，使水箱，试确定正方形的边长

2、，使储水箱的容积最大。储水箱的容积最大。2 2、多维优化设计转化为一维优化设计问题、多维优化设计转化为一维优化设计问题多维优化问题求解过程：多维优化问题求解过程：二、一维优化方法的分类二、一维优化方法的分类1.1.解析法解析法2.2.数值法数值法由由方程求根法方程求根法区间收缩法区间收缩法二分法、切线法、割线法等二分法、切线法、割线法等分数（分数（FibonacciFibonacci）法、黄金法、黄金分割（分割（0.618)0.618)法、插值法等法、插值法等得得332 2 单峰区间的确定单峰区间的确定定定义义 设设*是是()()的的极极小小点点，若若存存在在闭闭区区间间aa，bb，使使得得*

3、aa，bb，且且使使函函数数值值呈呈“高高低低高高”的的形形态态，即即函函数数()()在在闭区间闭区间aa，bb中有唯一极小点，则称中有唯一极小点，则称aa，bb是是()()单峰区间单峰区间.一、单峰区间的定义一、单峰区间的定义非单峰区间非单峰区间单峰区间单峰区间二、单峰区间的确定二、单峰区间的确定确确定定搜搜索索区区间间的的一一种种简简单单的的方方法法是是进进退退法法，其其基基本本思思想想是是从从某某一一点点出出发发，按按一一定定的的步步长长，确确定定函函数数值值呈呈“高高低低高高”的的三三点点。如如果果一一个个方方向向不不成成功功，就退回来，再沿相反的方向寻找。具体算法步骤如下：就退回来，

4、再沿相反的方向寻找。具体算法步骤如下：(4)(4)如如果果k=1,k=1,则则置置 2 2=,=,2 2=,和和h=-h=-h,h,转转(2);(2);否否则则置置 1 1=2 2,1 1=2 2,2=3,2=3,2 2=3 3,3=,3=,3 3=,并并 令令a=mina=min1 1,3 3,b=maxb=max1 1,3 3,停停止止计计算算.(1)(1)取取初初始始步步长长h h，置置初初始始值值 3 3=0=0，3 3=(3 3)，并置，并置k=0.k=0.(2)(2)置置=3 3+h+h，=()()和和k=k+1.k=k+1.(3)(3)如如果果 3 3,则则置置 2 2=3 3,

5、2 2=3 3,3 3=,=,3 3=和和 h=2h,k=k+1,h=2h,k=k+1,转转(2);(2);二、单峰区间的确定二、单峰区间的确定开始开始输入：输入：h h置置 3 3=0=0，3 3=(3 3)，k=0k=0置置=3 3+h+h，=(),k=k+1(),k=k+1 2 2=3 3,2 2=3 3,3 3=,=,3 3=,h=2h,k=k+1 h=2h,k=k+1 2 2?yesyesnonoa=aa=a1 1b b=b ba=aa=ab b=a=a2 2黄黄金金分分割割法法(Golden(GoldenSectionSectionMethod)Method)又又称称为为0.618

6、0.618法法，是是用用于于在在单单峰峰函函数数区区间间上上求求极极小小的的一一种种方方法法。其其基基本本思思想想是是通通过过取取试试探探点点和和进进行行函函数数值值比比较较，使使包包含含极极小小点点的的搜搜索索区区间间不不断断减减少少，当当区区间间长长度度缩缩短短到到一一定定程程度度时时，就就得得到到函函数数极极小小点的近似值。点的近似值。333 3 黄金分割法黄金分割法一、黄金分割法的取点原则一、黄金分割法的取点原则1.1.对称取点对称取点2.2.等区间收缩率等区间收缩率3.3.留点可用留点可用二、黄金分割法的区间收缩率二、黄金分割法的区间收缩率(1)(1)置初始搜索区间置初始搜索区间a,

7、ba,b，并置精度要求，并置精度要求，并计算左右试探点，并计算左右试探点 a al l=a+0.382(b-a)=a+0.382(b-a)a a2 2=a+0.618(b-a)=a+0.618(b-a)及相应的函数值及相应的函数值 l l=(a(al l)，2 2=(a(a2 2).).三、黄金分割法的步骤三、黄金分割法的步骤(3)(3)若若|b-a|,|b-a|,做做:如如果果 l l 2 2，则则置置*=a=a1 1；否否则则置置*=a=a2 2，停止计算停止计算(*作为问题的解作为问题的解)。否则转。否则转(2).(2).(2)(2)如果如果 l l 2 2，去掉区间，去掉区间11，a

8、al l.详细计算结果见下表详细计算结果见下表 不不要要求求每每次次迭迭代代区区间间的的收收缩缩比比不不变变,而而希希望望在在试试验验点点个个数数相相同同的的情情况况下下，找找出出一一种种选选取取试试验验点点的的最最佳佳策策略略，使使得得最最终终的的极极小小区区间间的的长长度度达达到到最最小小，换换句句话话说说，如如果果规规定定试试验验点点的的个个数数为为n，且且最最终终区区间间长长度度为为1，问问如如何选取这何选取这n个点，使得原始区间的长度最大？个点，使得原始区间的长度最大？令令Ln表表示示试试验验点点数数为为n n、最最终终区区间间长长度度为为1 1时时，原原始始区间区间a,ba,b的最

9、大可能长度。的最大可能长度。设设 l为为左左试试探探点点，r r为为右右试试探探点点，如如果果极极小小点点*位位于于区区间间aa，l，则则在在此此区区间间内内至至多多还还可可以以有有n-2n-2个个试验点，因此试验点，因此 l-a-aLn2.334 Fibonacci4 Fibonacci法法另另一一方方面面,如如果果极极小小点点 *位位于于区区间间 l,b,b内内,则则包包括括 r在在内内,还可以作还可以作n-1n-1个试验点，所以个试验点，所以 b-b-l Ln-1n-1.因此因此 b-a=(b-b-a=(b-l)+()+(l-a)-a)Ln2+Ln-1n-1,故有如下关系式故有如下关系式

10、:Ln Ln2+Ln-1n-1显显然然,不不计计算算函函数数值值和和仅仅计计算算一一点点处处的的函函数数值值都都不不能能使使极小区间缩小，即极小区间缩小，即 L0=L1=1.=1.由此可得，如果原始区间长度满足递推关系由此可得，如果原始区间长度满足递推关系 F0=F1，Fn=Fn2+Fn-1n-1则则Fn将是最大原始区间的长度将是最大原始区间的长度.Fn称称为为FibonacciFibonacci数数。FibonacciFibonacci方方法法的的基基本本思思想想与与0.6180.618法法相相同同.在在搜搜索索区区间间a,ba,b上上,先先取取左左、右右试试验验点点 l 和和 r 比较函数

11、值比较函数值f(l)和和f(r)重新确定搜索区间重新确定搜索区间.(1)(1)若若f(l)f(r)，去去掉掉区区间间a,a,r,令令a=a=l，b=b,b=b,再计算新的试探点再计算新的试探点所所以以FibonacciFibonacci方方法法与与0.6180.618法法一一样样,除除第第一一次次外外,以以后后每每次次只只计计算算一一个个点点处处的的函函数数值值.Fibonacci.Fibonacci方方法法每每次次保保留留的的区区间间长长度度为为F Fk-1k-1F Fk k,因因此此若若计计算算n n个个试试验验点点,最最终终的的区区间间长长度度。因因此此,任任给给一精度要求一精度要求,要

12、求最终的区间长度小于要求最终的区间长度小于,即有即有因此因此,任给一精度要求任给一精度要求,要求最终的区间长度小于要求最终的区间长度小于,即有即有那么选择那么选择n n满足满足(1)(1)置置初初始始搜搜索索区区间间aa，bb，并并置置精精度度要要求求，选选取取分分离离间间隔隔（b-ab-a），并计算左右试探点，并计算左右试探点 l =a+=a+Fn-2/Fn(b-a)(b-a)，r =a+=a+Fn-1/Fn(b-a)(b-a)及及相相应应的的函函数数值值flf(l),),frf(r)。算法步骤算法步骤(2)(2)置置n=n-1n=n-1。(3)(3)如如果果frf(r)，则则置置b=b=r

13、，r =l ，fr fl ，。如如果果n2,n2,则则计计算算 l =a+=a+Fn-2/Fn(b-a)(b-a)，flf(l)；否否则则计计算算 l =r -，flf(l)。(4)(4)fl fr ，置置a=a=l ，l =r ，fl fr ；如如果果n2n2，则则计计算算 r =a+=a+Fn-1/Fn(b-a)(b-a)，frf(r)；否否则则计计算算 r =l +，frf(r)。(5)(5)若若n=1n=1，做做：如如果果frf(r)，则则置置=r ；否否则则置置=r ，停停止计算止计算(作为问题的极小点作为问题的极小点)。否则转。否则转(2)(2)。插插值值法法是是一一类类重重要要的

14、的一一维维搜搜索索方方法法，其其基基本本思思想想是是利利用用搜搜索索区区间间上上某某些些点点的的信信息息构构造造插插值值多多项项式式(通通常常不不超超过过三三次次)p()p()，逐逐步步用用p()p()的的极极小小点点来来逼逼近近()()的的极极小小点点*。当当()()有有比比较较好好的的解解析析性性质质时时,插插值值法法比比区区间间收收缩缩法法(如如0.6180.618法法)的的效效果果好好.本本节节介介绍绍三三种种较较为为常见的插值法常见的插值法.334 4 二次插值法二次插值法 在在单单峰峰区区间间a,ba,b中中，已已知知函函数数在在三三点点 1 1、2 2、3 3 （1 12 2 2

15、 2、3 3 2 2，即三点满足，即三点满足“两端高中间低两端高中间低”。这三个点可由得到：这三个点可由得到：一、二次插值法的思想一、二次插值法的思想由由数数值值分分析析的的知知识识,得得到到过过三三个个点点(1 1，1 1)、(2 2，2 2)、(3 3，3 3)的二次插值公式为的二次插值公式为对上式求导数，并求解方程对上式求导数，并求解方程p()=0p()=0，得到，得到p()p()的极小点的极小点用用 作为作为*的估计值的估计值,并计算并计算 处的函数值处的函数值=()()。第一次的近似结果往往不够理想，需要作进一步的近似。第一次的近似结果往往不够理想，需要作进一步的近似。现现已已得得到

16、到四四个个点点(1 1，1 1)、(2 2，2 2)、(3 3，3 3)和和(，),),如如何何选取三个点呢选取三个点呢?仍然按照最初的原则，选取满足仍然按照最初的原则，选取满足“两端高中间低两端高中间低”的三个点。的三个点。二、二次插值法的区间收缩过程二、二次插值法的区间收缩过程(1)(1)取取初初始始点点 1 12 2 2 2，2 2 3 3 ，置精度要求，置精度要求.三、二次插值法算法步骤：三、二次插值法算法步骤：(2)(2)计算计算 A=2 A=2 1 1(2 2-3 3)+)+2 2(3 3-1 1)+)+3 3(1 1-2 2)若若A=0A=0，则置，则置=2 2,=2 2,停止计

17、算停止计算(输出输出,的信息的信息).).(3)(3)计算计算 =1 1(2 22 2-3 32 2)+)+2 2(3 32 2 1 12 2)+)+3 3(1 12 2-2 22 2)/A)/A 若若3 3，则置则置=2 2,=2 2，停止计算停止计算(输出输出,的信息的信息)。(4)(4)计算计算=()()。若。若|-|-2 2|,|,则停止计算则停止计算(作为极小点作为极小点)。(5)(5)如果如果(2,3)(2,3)，则，则:若若 2 2，则置，则置 1 1=2 2，1 1=2 2 ，2 2=，2 2=；否则置否则置 3 3=,=,3 3=;否则否则(1,2):(1,2):若若 2 2，则置，则置 3 3=2 2,3 3=2 2 ，2 2=,=,2 2=；否则置否则置 1 1=,=,2 2=，转转(2).(2).四四、二二次次插插值值法法程程序序框框图图：作业作业用黄金分割法编程求解函数用黄金分割法编程求解函数的极小点的极小点X（1 1）。优化方法程序实现之一优化方法程序实现之一用黄金分割法编程求解函数用黄金分割法编程求解函数的极小点的极小点X（1 1）。