機械優(yōu)化設計第三章

1、：對于：對于單個變量單個變量（一維問題一維問題）的直接探索（搜索）的直接探索（搜索 或尋查）?；驅げ椋６嗑S多維問題的數(shù)值迭代法問題的數(shù)值迭代法1(0,1,2,)kkkkxxdk1()()()minkkkkkf xf xd 每步為每步為一維一維搜索搜索*()0 1 1）解析法解析法：2 2）數(shù)值解法數(shù)值解法的基本思想：確定的基本思想：確定 * *所在的搜索區(qū)間，所在的搜索區(qū)間， 然后根據(jù)區(qū)間消去原理不斷縮小區(qū)間，然后根據(jù)區(qū)間消去原理不斷縮小區(qū)間， 從而獲得從而獲得 * *的數(shù)值近似解。的數(shù)值近似解。函數(shù)在該區(qū)間只有函數(shù)在該區(qū)間只有一個極值點一個極值點。12xxx12()( )()f xf xf

2、 x“高高低低高高”（進退法（進退法/成功失敗法）：成功失敗法）：12x x x 12( )( )( )f xf xf x“高高低低高高”的基本步驟：的基本步驟：10210112212320332332123132300122312231.()()(),2hhyfyfyyhyfyyyyyyyyyhhyyyy 選定初始點，初始步長 ，計算點，然后比較函數(shù)值和的大小。2.若，則試探方向正確，計算點和，比較 和 的大小。如果，則形成，找到所需的區(qū)間，即；如果，則需要繼續(xù)向前搜索，這時候令，同時令，開01231313 , min(,),max(,)hyyya b 始新一輪的試探（這時候的是原來的二倍，

3、步長加長了），直到找到時，新的搜索區(qū)間是。的基本步驟：的基本步驟：1200121233313112122323122320333.,()yyhhyyyyyyyyyhff 若，則試探方法錯誤，需要反向，即令，并且將和交換，同時交換 和 ，在程序中，如果用替換，則另一個函數(shù)值就沒有了，所以加入和 做中間變量，即：；。然后得到新的和后，用新的向前推出（這里的已經(jīng)反向了）。這時就得到了新的三個點，以及三個試探點的函數(shù)231231313 , min(,),max(,)yyyyya b 值，則繼續(xù)前面的比較 與 ，直至找到時，新的搜索區(qū)間是。的程序流程圖：的程序流程圖：例：例：210( )710 , 01

4、f xxxa bh試用進退法確定函數(shù)的一維優(yōu)化的初始搜索。其中，設初始點，初始搜索步長。通過通過外推法外推法，我們可以確定一個包含一元函數(shù)極值點的，我們可以確定一個包含一元函數(shù)極值點的搜索區(qū)間搜索區(qū)間，為了進一步找到極小點，我們需要不斷的縮小，為了進一步找到極小點，我們需要不斷的縮小搜索區(qū)間，消去不可能包含極小點的區(qū)間，使區(qū)間在縮小搜索區(qū)間，消去不可能包含極小點的區(qū)間，使區(qū)間在縮小的過程中逐步向極小點靠攏，最后縮小到極小點附近一個的過程中逐步向極小點靠攏，最后縮小到極小點附近一個極小的領域內。極小的領域內。 這個時候，如果我們規(guī)定一個足夠小的正數(shù)這個時候，如果我們規(guī)定一個足夠小的正數(shù) ，稱為收

5、斂，稱為收斂精度。則當區(qū)間長度達到足夠小，即精度。則當區(qū)間長度達到足夠小，即 取該區(qū)間取該區(qū)間的中點的中點 作為極值點，這才能完成整個一維作為極值點，這才能完成整個一維搜索搜索 。kkba*1()2kkxab：不斷縮小區(qū)間所用的原理。：不斷縮小區(qū)間所用的原理。 包括：包括：1）直接法直接法：直接比較試選點的函數(shù)值；：直接比較試選點的函數(shù)值； 2）間接法間接法：利用函數(shù)導數(shù)值的變化信息。：利用函數(shù)導數(shù)值的變化信息。111111 , ()( )a bababf af b假定在搜索區(qū)間內任取兩點 和 ，且，并計算和，可能出現(xiàn)三種情況：11111111111. ()( ) ,2. ()( ), 3.

6、()( ),f af ba bf af ba bf af ba b，由于函數(shù)的單峰性，極小點一定在內；，極小點一定在內；，極小點一定在內。111111 , ()( )a bababf af b假定在搜索區(qū)間內任取兩點 和 ，且，并計算和，可能出現(xiàn)三種情況：1111111.()( ) ,2.()( ), f af ba bf af ba b若，則取為縮短后的搜索區(qū)間；若，則取為縮短后的搜索區(qū)間。 , ,( )a bxfx假定在搜索區(qū)間內取一點 并計算它的導數(shù)值，可能出現(xiàn)三種情況：*1. ( )0 , 2. ( )0 , 3. ( )0fxx bfxa xfxxx，則新區(qū)間是；，則新區(qū)間是；，則在

7、此點就是極小點。x fxabxx0 x fxabxx0 fxxabx0： 縮短后的新區(qū)間長度（0 1）縮短前的原區(qū)間長度：它是按照：它是按照某種給定的規(guī)律某種給定的規(guī)律來確定區(qū)間內插入點來確定區(qū)間內插入點的位置的。插入點位置的確定是為了使區(qū)間縮短的更快，的位置的。插入點位置的確定是為了使區(qū)間縮短的更快，而而不管函數(shù)值的分布規(guī)不管函數(shù)值的分布規(guī)律。它律。它包括包括：黃金分割法（：黃金分割法（0.6180.618法）、裴波納契（法）、裴波納契（FibonacciFibonacci）法等。）法等。：這種方法是根據(jù)某點處的某些：這種方法是根據(jù)某點處的某些信息（如信息（如函數(shù)值函數(shù)值、一階導數(shù)一階導數(shù)、

8、二階導數(shù)二階導數(shù)等）來構造一個等）來構造一個差值函數(shù)差值函數(shù)來逼近原來的函數(shù)，用來逼近原來的函數(shù)，用插值函數(shù)的極小點插值函數(shù)的極小點作為作為區(qū)間的插入點。它區(qū)間的插入點。它包括包括：二次差值法、三次插值法等。：二次差值法、三次插值法等。通過比較單峰區(qū)間內通過比較單峰區(qū)間內兩個內分點兩個內分點的的函數(shù)值函數(shù)值，不斷舍棄，不斷舍棄單峰區(qū)間的左端或者右端的一部分，使區(qū)間按照單峰區(qū)間的左端或者右端的一部分，使區(qū)間按照固定區(qū)間固定區(qū)間縮短率縮短率（=0.618=0.618）逐步縮短，直到極小點所在的區(qū)間縮）逐步縮短，直到極小點所在的區(qū)間縮短到短到給定的誤差范圍給定的誤差范圍內，而得到內，而得到近似最優(yōu)解

9、近似最優(yōu)解。 每次區(qū)間縮短都取每次區(qū)間縮短都取相等相等的的區(qū)間縮短率區(qū)間縮短率（ ），同時插入點距離兩個端點有），同時插入點距離兩個端點有對稱性對稱性。 0.61812()0.618()()0.618()bbabbaabaaba121211221 , 2 , ()0.618() ()0.618()()()a ba bbbabbaabaabayfyf）給定初始單峰區(qū)間和收斂精度 ，將 賦值為0.618；）在區(qū)間內，取兩個內分點和，并計算其函數(shù)值： 和，12221221211111211211213 , ,()(), , ,yybyybbayfyybbay ）比較函數(shù)值大小，根據(jù)區(qū)間消去法原理縮短

10、區(qū)間：若，則極小點必在區(qū)間內，即為新區(qū)間,則為新區(qū)間內的第一個試驗點，即令，而另一個試驗點可按下式算出，它的函數(shù)值為；若，則極小點必在區(qū)間內，即為新區(qū)間，則為新區(qū)間內的第一個試驗點，即令2222(),()yabayf，而另外一個試驗點可以按下式給出。212*4315()()2yybabyxabyf x）進行迭代終止條件檢驗，檢查區(qū)間是否縮短到足夠小和函數(shù)值是否收斂到足夠近，即和，如果不滿足條件，則轉到第 ）步；滿足條件則繼續(xù)執(zhí)行下一步。）輸出最優(yōu)解和最優(yōu)函數(shù)值。2*( )2 ,35f如圖所示，對函數(shù)當給定搜索區(qū)間時，試用黃金分割法求極小點。 和黃金分割法和黃金分割法相似相似，都是在搜索區(qū)間內，

11、都是在搜索區(qū)間內對稱的取點對稱的取點，通過，通過比較兩點函數(shù)值逐步縮小初始單峰區(qū)間來搜索出滿意的極小比較兩點函數(shù)值逐步縮小初始單峰區(qū)間來搜索出滿意的極小點點x x* *。 與黃金分割法與黃金分割法不同不同的是：的是：黃金分割法黃金分割法每次迭代式按照同一每次迭代式按照同一區(qū)間縮短率區(qū)間縮短率=0.618=0.618來縮短區(qū)間，而來縮短區(qū)間，而斐波那契法斐波那契法每次迭代的區(qū)每次迭代的區(qū)間縮短率是不同的，它是按間縮短率是不同的，它是按斐波那契數(shù)列斐波那契數(shù)列FnFn產生的分數(shù)序產生的分數(shù)序列為縮短率來縮短區(qū)間的。列為縮短率來縮短區(qū)間的。， ，011FF12(2,3,)nnnFFFn斐波那契數(shù)：斐

12、波那契數(shù)： 凡是滿足遞推關系而產生的正數(shù)序列Fn，就稱為斐波那契數(shù)。n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 ，n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 區(qū)間縮短率區(qū)間縮短率用相鄰兩數(shù)的用

13、相鄰兩數(shù)的前一數(shù)前一數(shù)與與后一數(shù)后一數(shù)之之比比產生，如計產生，如計算五個點的函數(shù)值（即迭代四次，每次區(qū)間縮短率分別為算五個點的函數(shù)值（即迭代四次，每次區(qū)間縮短率分別為123412514342134233253 8521 32nnnnnnnnFFFFFFFFFFFFFFFF11234518FF ，n n0 0 1 1 2 23 34 45 56 67 78 89 910101111121213131414FnFn1 1 1 1 2 23 35 58 813132121343455558989144144233233377377610610 推廣到計算推廣到計算n n個點的函數(shù)值，經(jīng)過個點的函數(shù)值

14、，經(jīng)過n-1n-1次迭代所獲得的次迭代所獲得的區(qū)間總縮短率區(qū)間總縮短率為為11211nnnFFF ，11(1)1/n21/0.61830.618nnnnFFF）斐波那契法開始計算第一個內點（即第一次縮短率）就要用到，也就是首先要確定計算函數(shù)的次數(shù)（即計算的總點數(shù) ），否則無法確定縮短率）與黃金分割法相比，收斂效果好，即計算相同試點數(shù)，斐波那契法總區(qū)間縮短率。黃金分割法的區(qū)間總縮短率。）斐波那契法每次的區(qū)間縮短率是變化的，當計算函數(shù)值的點數(shù)較多時，其區(qū)間縮短率將逼近。 ，11111101121a,b2nn11|()()Fn1,(2,3,)nnnnnnnnnnnnbababababaFbaFFFF

15、FFn）由外推法（進退法）選定初始單峰區(qū)間。）確定所需計算的試點總數(shù)（即計算函數(shù)的次數(shù)） 。當給定區(qū)間縮短率的絕對精度 時，經(jīng)過次迭代，最后獲得的新區(qū)間長度（）必須滿足。而，故。由即可從斐波那契數(shù)列表或按推算出相應的 。112111223a,b(), (), (), ()nnnnFFxabaxbbaff xff xFF）確定試點并計算相應的函數(shù)值，在區(qū)間內的兩個試點： ，212221211211211112122122*114 ,() , ,()15(),()2nnffa xbx xxffxabxff xffx bax xxffxabxff xbaxabff x）比較函數(shù)值的大小后進行區(qū)間縮短

16、。若，即為新區(qū)間，并作如下置換：即令若時，得新區(qū)間，并作如下置換：）檢查迭代終止條件：，若滿足，則輸出最優(yōu)解，若不滿足，則轉入（4），繼續(xù)進行迭代。 我們就可以根據(jù)我們就可以根據(jù)幾個試驗點的函數(shù)值幾個試驗點的函數(shù)值，利用插值方法建立，利用插值方法建立函數(shù)的某種函數(shù)的某種近似表達式近似表達式，進而求得函數(shù)的極小值，并用它作，進而求得函數(shù)的極小值，并用它作為為原函數(shù)極小點的近似值原函數(shù)極小點的近似值。這種方法稱為插值法，或函數(shù)逼。這種方法稱為插值法，或函數(shù)逼近法近法 。利用一點的函數(shù)值，一階導數(shù)值和二利用一點的函數(shù)值，一階導數(shù)值和二階導數(shù)值來構造此二次函數(shù)。階導數(shù)值來構造此二次函數(shù)。利用三點的函數(shù)

17、值形成一個拋利用三點的函數(shù)值形成一個拋物線來構造二次函數(shù)物線來構造二次函數(shù) 。 ，用用切線切線代替代替弧弧逐漸逼近函數(shù)極值的一種方法。逐漸逼近函數(shù)極值的一種方法。 ，1() (0,1,2,)()kkkkfkf ，01*11k01()()()2()3|4411kkkkkkkkkffffkk給定初始點，控制誤差 ，令。）計算和；）求。）若，則求得近似解，停止計算，否則轉到第（ ）步；）令轉到第（ ）步。 ，： 1 1）每一次迭代都要計算函數(shù)的二階導數(shù)，增加了計）每一次迭代都要計算函數(shù)的二階導數(shù)，增加了計算工作量；算工作量； 2 2）對初始點的要求較高，如果選不好，可能使數(shù)列發(fā)）對初始點的要求較高，

18、如果選不好，可能使數(shù)列發(fā)散或收斂到一個不是極小點的點上。散或收斂到一個不是極小點的點上。 ，43212( )27843f例：試用牛頓法求的近似極小值，已知探索區(qū)間為a,b=3,4, =0.05。 ，在給定的單峰區(qū)間在給定的單峰區(qū)間a,ba,b內，利用函數(shù)上的內，利用函數(shù)上的三個點三個點來構來構造一個造一個二次插值函數(shù)二次插值函數(shù)p()p()，以近似地表達原目標函數(shù)，以近似地表達原目標函數(shù)f()f()，并求這個插值函數(shù)的極小點近似作為原目標函數(shù)的極小并求這個插值函數(shù)的極小點近似作為原目標函數(shù)的極小點。它是以點。它是以目標函數(shù)的二次插值函數(shù)目標函數(shù)的二次插值函數(shù)的的極小點極小點作為作為新的新的中間

19、插入點中間插入點，進行區(qū)間縮小的一維搜索方法。，進行區(qū)間縮小的一維搜索方法。 ， 2012Paaa210112111220122222230132333PaaayfPaaayfPaaayf123123fff113212pcc31131yyc21121223yycc12/ 2paa ， ，2()0paa h2pyy2pyy ，2pyy2()0paa h2pyy ，123132112233211312112312311321,1(),(),(),();22( ):,1(),2ppppababyfyfyfyycyyaapccaaaacaaayfc）給定初始搜索區(qū)間a,b和迭代精度 ，取點時令求）計算