一维搜索法课件

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