一維搜索法PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1一維搜索法一維搜索法31 概述一、問題的提出1、實(shí)際設(shè)計(jì)工作中會(huì)遇到一維優(yōu)化設(shè)計(jì)問題在長(zhǎng)為350cm、寬為260cm的長(zhǎng)方形不銹鋼板的四角，各剪去一個(gè)小正方形，做成一個(gè)無蓋的儲(chǔ)水箱，試確定正方形的邊長(zhǎng)，使儲(chǔ)水箱的容積最大。 f xxxxmax( )(3502 ) (2602 )s t x. .0130 x第1頁/共29頁2、多維優(yōu)化設(shè)計(jì)轉(zhuǎn)化為一維優(yōu)化設(shè)計(jì)問題多維優(yōu)化問題求解過程：(1)( )( )kk+kkXXd X(1)d(0)0 d(1)(2)d(3)d(2)X(3)X(4)XX(0)( )( )min()min()min ( )kkf Xf Xd 第2頁/共29頁二、一維優(yōu)化方法

2、的分類1.解析法2.數(shù)值法( )0dd ( )( )( )( )( )2( )( )( )( )()1()()()2kkkkTkk Tkkf Xdf Xf XddH Xd ( )( )( )( )( )()()0kTkk Tkkf XddH Xd由( )( )( )( )( )()()kTkk Tkkf XddH Xd 方程求根法區(qū)間收縮法二分法、切線法、割線法等分?jǐn)?shù)（Fibonacci）法、黃金分割（0.618)法、插值法等得第3頁/共29頁32 單峰區(qū)間的確定定義 設(shè)*是()的極小點(diǎn)，若存在閉區(qū)間a，b，使得*a，b，且使函數(shù)值呈“高低高”的形態(tài)，即函數(shù)()在閉區(qū)間a，b中有唯一極小點(diǎn)，則

3、稱a，b是()單峰區(qū)間.一、單峰區(qū)間的定義非單峰區(qū)間單峰區(qū)間第4頁/共29頁二、單峰區(qū)間的確定確定搜索區(qū)間的一種簡(jiǎn)單的方法是進(jìn)退法，其基本思想是從某一點(diǎn)出發(fā)，按一定的步長(zhǎng)，確定函數(shù)值呈“高低高”的三點(diǎn)。如果一個(gè)方向不成功，就退回來，再沿相反的方向?qū)ふ?。具體算法步驟如下：(4)如果k=1,則置2=,2= ,和h=-h,轉(zhuǎn)(2);否則置1=2, 1= 2,2=3, 2= 3, 3=, 3= ,并令a=min1,3, b=max1,3, 停止計(jì)算.(1)取初始步長(zhǎng)h，置初始值3=0，3= (3)，并置k=0.(2)置=3+h，= ()和k=k+1.(3)如果3,則置2=3, 2=3, 3=, 3=和

4、 h=2h,k=k+1,轉(zhuǎn)(2);3h2h4h12第5頁/共29頁二、單峰區(qū)間的確定3h2h4h124habhhab第6頁/共29頁開始輸入：h置3=0，3= (3)，k=0置=3+h，= (),k=k+12=3, 2=3, 3=, 3=, h=2h,k=k+12?yesnoa=a1b=ba=ab= a212a baaabab新區(qū)間長(zhǎng)舊區(qū)間長(zhǎng)第8頁/共29頁黃金分割法(GoldenSectionMethod)又稱為0.618法，是用于在單峰函數(shù)區(qū)間上求極小的一種方法。其基本思想是通過取試探點(diǎn)和進(jìn)行函數(shù)值比較，使包含極小點(diǎn)的搜索區(qū)間不斷減少，當(dāng)區(qū)間長(zhǎng)度縮短到一定程度時(shí)，就得到函數(shù)極小點(diǎn)的近似值。

5、33 黃金分割法一、黃金分割法的取點(diǎn)原則1. 對(duì)稱取點(diǎn)2. 等區(qū)間收縮率3. 留點(diǎn)可用第9頁/共29頁(1)()ba2()ba210 510.618210.382()aaba20.618()aaba二、黃金分割法的區(qū)間收縮率()ba(1)()ba11a22aababa1a2a(1)()ba2()bab第10頁/共29頁(1)置初始搜索區(qū)間a,b，并置精度要求，并計(jì)算左右試探點(diǎn) al=a+0.382(b-a) a2=a+0.618(b-a)及相應(yīng)的函數(shù)值l= (al)， 2= (a2).三、黃金分割法的步驟(3)若|b-a|,做:如果l 2，則置*=a1；否則置*=a2， 停止計(jì)算(*作為問題的

6、解)。否則轉(zhuǎn)(2).(2)如果l2，去掉區(qū)間1，al.詳細(xì)計(jì)算結(jié)果見下表第13頁/共29頁 不要求每次迭代區(qū)間的收縮比不變,而希望在試驗(yàn)點(diǎn)個(gè)數(shù)相同的情況下，找出一種選取試驗(yàn)點(diǎn)的最佳策略，使得最終的極小區(qū)間的長(zhǎng)度達(dá)到最小，換句話說，如果規(guī)定試驗(yàn)點(diǎn)的個(gè)數(shù)為n，且最終區(qū)間長(zhǎng)度為1，問如何選取這n個(gè)點(diǎn)，使得原始區(qū)間的長(zhǎng)度最大？ 令Ln表示試驗(yàn)點(diǎn)數(shù)為n、最終區(qū)間長(zhǎng)度為1時(shí)，原始區(qū)間a,b的最大可能長(zhǎng)度。 設(shè)l為左試探點(diǎn)， r為右試探點(diǎn)，如果極小點(diǎn)*位于區(qū)間a，l，則在此區(qū)間內(nèi)至多還可以有n-2個(gè)試驗(yàn)點(diǎn)，因此 l -aLn2.34 Fibonacci法第14頁/共29頁另一方面,如果極小點(diǎn) *位于區(qū)間l,

7、b內(nèi),則包括r在內(nèi),還可以作n-1個(gè)試驗(yàn)點(diǎn)，所以 b- l Ln-1. 因此 b-a=(b- l)+(l -a) Ln2 + Ln-1,故有如下關(guān)系式: Ln Ln2 + Ln-1顯然,不計(jì)算函數(shù)值和僅計(jì)算一點(diǎn)處的函數(shù)值都不能使極小區(qū)間縮小，即 L0 = L1 =1.由此可得，如果原始區(qū)間長(zhǎng)度滿足遞推關(guān)系 F0 = F1，F(xiàn)n = Fn2 + Fn-1則Fn將是最大原始區(qū)間的長(zhǎng)度.第15頁/共29頁Fn稱為Fibonacci數(shù)。Fibonacci方法的基本思想與0.618法相同.在搜索區(qū)間a,b上,先取左、右試驗(yàn)點(diǎn)l 和r 比較函數(shù)值f(l)和f(r)重新確定搜索區(qū)間.(1)若f(l) f(r

8、)，去掉區(qū)間a, r,令a= l，b=b,再計(jì)算新的試探點(diǎn)第17頁/共29頁所以Fibonacci方法與0.618法一樣,除第一次外,以后每次只計(jì)算一個(gè)點(diǎn)處的函數(shù)值.Fibonacci方法每次保留的區(qū)間長(zhǎng)度為Fk-1Fk,因此若計(jì)算n個(gè)試驗(yàn)點(diǎn),最終的區(qū)間長(zhǎng)度。因此,任給一精度要求,要求最終的區(qū)間長(zhǎng)度小于,即有因此,任給一精度要求,要求最終的區(qū)間長(zhǎng)度小于,即有那么選擇n滿足第18頁/共29頁(1)置初始搜索區(qū)間a，b，并置精度要求，選取分離間隔（b-a），并計(jì)算左右試探點(diǎn)l =a+ Fn-2/ Fn(b-a)， r =a+ Fn-1/ Fn(b-a)及相應(yīng)的函數(shù)值flf(l), frf(r) 。

9、算法步驟(2)置n=n-1。(3)如果frf(r) ，則置b= r， r = l ， fr fl ， 。如果n2,則計(jì)算l =a+ Fn-2/ Fn(b-a) ， flf(l) ；否則計(jì)算l = r -， flf(l) 。(4) fl fr ，置a= l ， l = r ， fl fr ；如果n2，則計(jì)算r =a+ Fn-1/ Fn(b-a) ， frf(r) ；否則計(jì)算r = l +， frf(r) 。(5)若n=1，做：如果frf(r) ，則置= r ；否則置= r ，停止計(jì)算(作為問題的極小點(diǎn))。否則轉(zhuǎn)(2)。第19頁/共29頁 插值法是一類重要的一維搜索方法，其基本思想是利用搜索區(qū)間上

10、某些點(diǎn)的信息構(gòu)造插值多項(xiàng)式(通常不超過三次)p()，逐步用p()的極小點(diǎn)來逼近()的極小點(diǎn)*。當(dāng)()有比較好的解析性質(zhì)時(shí),插值法比區(qū)間收縮法(如0.618法)的效果好.本節(jié)介紹三種較為常見的插值法.34 二次插值法 在單峰區(qū)間a,b中，已知函數(shù)在三點(diǎn) 1、2、3 （12 2、 3 2 ，即三點(diǎn)滿足“兩端高中間低”。 這三個(gè)點(diǎn)可由得到：一、二次插值法的思想13221322 3或1a3b第20頁/共29頁由數(shù)值分析的知識(shí),得到過三個(gè)點(diǎn)(1，1)、 (2，2) 、 (3，3)的二次插值公式為對(duì)上式求導(dǎo)數(shù)，并求解方程p()=0，得到p()的極小點(diǎn)222222123231312123231312()()

11、()2()()() 第21頁/共29頁用作為*的估計(jì)值,并計(jì)算處的函數(shù)值=()。 第一次的近似結(jié)果往往不夠理想，需要作進(jìn)一步的近似。 現(xiàn)已得到四個(gè)點(diǎn)(1，1)、 (2，2) 、 (3，3)和(，),如何選取三個(gè)點(diǎn)呢? 仍然按照最初的原則，選取滿足“兩端高中間低”的三個(gè)點(diǎn)。a123a123a123a123二、二次插值法的區(qū)間收縮過程第22頁/共29頁(1)取初始點(diǎn)12 2， 2 3 ，置精度要求.三、二次插值法算法步驟：(2)計(jì)算 A=21(2-3)+2(3-1)+3(1-2) 若A=0，則置=2, = 2, 停止計(jì)算(輸出,的信息).(3)計(jì)算 =1(22- 32)+ 2(32 12)+ 3(12- 22)/A 若3，則置=2,= 2， 停止計(jì)算(輸出,的信息) 。第23頁/共29頁(4)計(jì)算=()。若|-2|,則停止計(jì)算(作為極小點(diǎn))。(5)如果(2,3)，則: 若2，則置 1=2，1= 2 ，2=， 2= ； 否則置 3=, 3= ; 否則(1,2): 若2，則置3=2, 3= 2 ，2=, 2= ； 否則置 1=, 2= ，轉(zhuǎn)(2).第24頁/共29頁四、二次插值法程序框圖：第25頁/共29頁第26頁/共29頁作業(yè)用黃金分割法編程求解函