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

1、會計學(xué)1一維搜索法一維搜索法31 概述一、問題的提出1、實際設(shè)計工作中會遇到一維優(yōu)化設(shè)計問題在長為350cm、寬為260cm的長方形不銹鋼板的四角，各剪去一個小正方形，做成一個無蓋的儲水箱，試確定正方形的邊長，使儲水箱的容積最大。 f xxxxmax( )(3502 ) (2602 )s t x. .0130 x第1頁/共29頁2、多維優(yōu)化設(shè)計轉(zhuǎn)化為一維優(yōu)化設(shè)計問題多維優(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è)*是()的極小點，若存在閉區(qū)間a，b，使得*a，b，且使函數(shù)值呈“高低高”的形態(tài)，即函數(shù)()在閉區(qū)間a，b中有唯一極小點，則

3、稱a，b是()單峰區(qū)間.一、單峰區(qū)間的定義非單峰區(qū)間單峰區(qū)間第4頁/共29頁二、單峰區(qū)間的確定確定搜索區(qū)間的一種簡單的方法是進(jìn)退法，其基本思想是從某一點出發(fā)，按一定的步長，確定函數(shù)值呈“高低高”的三點。如果一個方向不成功，就退回來，再沿相反的方向?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, 停止計算.(1)取初始步長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ū)間長舊區(qū)間長第8頁/共29頁黃金分割法(GoldenSectionMethod)又稱為0.618法，是用于在單峰函數(shù)區(qū)間上求極小的一種方法。其基本思想是通過取試探點和進(jìn)行函數(shù)值比較，使包含極小點的搜索區(qū)間不斷減少，當(dāng)區(qū)間長度縮短到一定程度時，就得到函數(shù)極小點的近似值。

5、33 黃金分割法一、黃金分割法的取點原則1. 對稱取點2. 等區(qū)間收縮率3. 留點可用第9頁/共29頁(1)()ba2()ba210 510.618210.382()aaba20.618()aaba二、黃金分割法的區(qū)間收縮率()ba(1)()ba11a22aababa1a2a(1)()ba2()bab第10頁/共29頁(1)置初始搜索區(qū)間a,b，并置精度要求，并計算左右試探點 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， 停止計算(*作為問題的

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

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

8、)，去掉區(qū)間a, r,令a= l，b=b,再計算新的試探點第17頁/共29頁所以Fibonacci方法與0.618法一樣,除第一次外,以后每次只計算一個點處的函數(shù)值.Fibonacci方法每次保留的區(qū)間長度為Fk-1Fk,因此若計算n個試驗點,最終的區(qū)間長度。因此,任給一精度要求,要求最終的區(qū)間長度小于,即有因此,任給一精度要求,要求最終的區(qū)間長度小于,即有那么選擇n滿足第18頁/共29頁(1)置初始搜索區(qū)間a，b，并置精度要求，選取分離間隔（b-a），并計算左右試探點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,則計算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 ，停止計算(作為問題的極小點)。否則轉(zhuǎn)(2)。第19頁/共29頁 插值法是一類重要的一維搜索方法，其基本思想是利用搜索區(qū)間上

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

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