碩士研究生機械優(yōu)化設計作業(yè)

1、機 械 優(yōu) 化 設 計 報 告REPORT FOR OPTIMAL DESIGN OF MACHINE 作業(yè)題目 黃金分割一維搜索方法作者姓名 黎 原作者學號 學科專業(yè) 機械設計及理論指導教師 楊立坡教授 2012年12月研究生機械優(yōu)化設計報告黃金分割一維搜索方法碩士研究生：黎 原碩士生學號導師：楊利坡教授學科專業(yè)：機械設計及理論所 在 單 位：機械工程學院Report in Mechanical Design and TheoryTHE GOLDEN SPLITING ONE-DIMENSIONAL SEARCHING METHODby Li Yuan Supervisor: Profess

2、or Yang LipoYanshan UniversityDecember, 2012摘 要最優(yōu)化理論和方法日益受到重視，已經(jīng)滲透到生產(chǎn)、管理、商業(yè)、軍事、決 策等各個領(lǐng)域，而最優(yōu)化模型與方法廣泛應用于工業(yè)、農(nóng)業(yè)、交通運輸、商業(yè)、國防、建筑、同學、政府機關(guān)等各個部門及各個領(lǐng)域。伴隨著計算機技術(shù)的高速發(fā)展，最優(yōu)化理論與方法的迅速進步為解決實際最優(yōu)化問題的軟件也在飛速發(fā)展。其中，MATLAB軟件已經(jīng)成為最優(yōu)化領(lǐng)域應用最廣的軟件之一。有了MATLAB這個強大的計算平臺，既可以利用MATLAB優(yōu)化工具箱中的函數(shù)，又可以通過算法變成實現(xiàn)相應的最優(yōu)化計算。 在最優(yōu)化計算中一維最優(yōu)化方法是優(yōu)化設計中最簡單

3、、最基本的方法。一維搜索，又稱為線性搜索，一維問題是多維問題的基礎(chǔ)，在數(shù)值方法迭代計算過程中，都要進行一維搜索，也可以把多維問題化為一些一維問題來處理。一維問題的算法好壞，直接影響到最優(yōu)化問題的求解速度。而黃金分割法是一維搜索方法中重要的方法之一，它適用于任何單峰函數(shù)求最小值的問題，甚至于對函數(shù)可以不要求連續(xù)，是一種基于區(qū)間收縮的極小點搜索算法。關(guān)鍵詞：最優(yōu)化；黃金分割法；MATLAB；算法；一維搜索；AbstractOptimization theory and methods which have been paid more attention, have penetrated into

4、 the production, management, business, military, decision-making and other fields, and optimization models and methods widely used in industry, agriculture, transportation, commerce, defense, construction, students, government various departments and agencies and other fields. With the rapid develop

5、ment of computer technology, optimization theory and methods for the rapid progress of the optimization problem to solve practical software is also developing rapidly. MATLAB software has become the most optimization software is one of the most widely used. With this powerful computing platform MATL

6、AB, we can use not only MATLAB optimization toolbox in the function, but also can achieve the appropriate algorithm to optimize into the calculation. In the calculation of one-dimensional optimization method is to optimize the design of the simplest, most basic method. One-dimensional search, also k

7、nown as linear search, one-dimensional problem is multi-dimensional problem based on iterative methods in numerical calculation, should be one-dimensional search, can also multi-dimensional problem into a number of one-dimensional problem to deal with. One-dimensional algorithms are directly affecte

8、d by the speed of solving optimization problems. The golden section method as a one-dimensional search method is one important method, which applies to any single peak function for the minimum of the problem, even on the function that does not require a continuous. The golden section method is a ver

9、y small point search algorithm based on a interval-based contraction.Keywords: Optimization;Golden section method;MATLAB;Algorithm; One-dimensional search;目 錄摘 要IABSTRACTII第1章 緒 論1第2章 最優(yōu)化方法基本原理22.1 無約束問題的最優(yōu)性條件22.2 搜索區(qū)間的確定2第3章 黃金分割法的基本原理與思想43.1 黃金分割法的基本思路43.2 黃金分割法的基本原理與步驟43.3 黃金分割0.618算法53.4 算法流程圖6第

10、4章 優(yōu)化程序的計算結(jié)果及其分析74.1 用matlab編寫源程序74.2 源程序計算過程及結(jié)果7第5章 一維搜索優(yōu)化的比較和分析95.1 進退法的原理及特點95.1.1 算法思想95.1.2 計算步驟95.2 插值法的原理及特點95.2.1 算法原理簡介95.2.1 插值算法計算過程9總 結(jié)11附 錄12一、無約束優(yōu)化方法程序考核題121. 牛頓法的 Matlab編程源程序122. 牛頓法編程的計算結(jié)果14二、約束優(yōu)化方法程序考核題141. Matlab自帶函數(shù)編程的源程序142. 程序運行的結(jié)果16參考文獻17第1章 緒 論數(shù)學科學不僅是自然科學的基礎(chǔ)，也是一切重要技術(shù)發(fā)展的基礎(chǔ)。最優(yōu)化方

11、法更是數(shù)學科學里面的一個巨大的篇幅，在這個信息化的時代，最優(yōu)化方法廣泛應用于工業(yè)、農(nóng)業(yè)、國防、建筑、通信與政府機關(guān)、管理等各個部門、各個領(lǐng)域；它主要解決最優(yōu)計劃、最優(yōu)分配、最優(yōu)決策、最佳設計、最佳管理等最優(yōu)化問題。而最優(yōu)解問題是這些所有問題的中心，是最優(yōu)化方法的重中之重，在求最優(yōu)解問題中，有多種方法解決，我們在這里著重討論無約束一維極值問題，即非線性規(guī)劃的一維搜索方法之黃金分割法。黃金分割法也叫0.618法，屬于區(qū)間收縮法，首先找出包含極小點的初始搜索區(qū)間，然后按黃金分割點通過對函數(shù)值的比較不斷縮小搜索區(qū)間。當然要保證極小點始終在搜索區(qū)間內(nèi)，當區(qū)間長度小到精度范圍之內(nèi)時，可以粗略地認為區(qū)間端點

12、的平均值即為極小值的近似值。所以用0.618法得出的是比較精確的最優(yōu)解了。本次作業(yè)程序的運行環(huán)境是matlab7.0版本的運行環(huán)境。第2章 最優(yōu)化方法基本原理2.1 無約束問題的最優(yōu)性條件無約束問題的最優(yōu)解所要滿足的必要條件和充分條件是我們設計算法的依據(jù)，為此我們有以下幾個定理。定理1 設在點處可微。若存在，使 則向量是在處的下降方向。定理2 設在點處可微。若是無約束問題的局部最優(yōu)解，則由數(shù)學分析中我們已經(jīng)知道，使的點x為函數(shù)f的駐點或平穩(wěn)點。函數(shù)的一個駐點可以是極小點；也可以是極大點；甚至也可能既不是極小點也不是極大點，此時稱它為函數(shù)的鞍點。以上定理告訴我們，是無約束問題的局部最優(yōu)解的必要條

13、件是：是其目標函數(shù)的駐點。 現(xiàn)給出無約束問題局部最優(yōu)解的充分條件。定理 3 設在點處的海賽矩陣存在，若并且正定，則是無約束問題的嚴格局部最優(yōu)解。一般而言，無約束問題的目標函數(shù)的駐點不一定是無約束問題的最優(yōu)解。但對于其目標函數(shù)是凸函數(shù)的無約束凸規(guī)劃，下面定理證明了，它的目標函數(shù)的駐點就是它的整體最優(yōu)解。定理 4 設，是上的可微凸函數(shù)。若有則是無約束問題的整體最優(yōu)解。2.2 搜索區(qū)間的確定在一維搜索時，我們假設函數(shù)具有如單谷性，即在所考慮的區(qū)間內(nèi)部，函數(shù)有唯一的極小點*。為了確定極小點*所在的區(qū)間a,b，應使函數(shù)在a,b區(qū)間里形成“高低高”趨勢。為此，從=0開始，以初始步長h0向前試探。如若函數(shù)值

14、上升，則步長變號，即改變試探方向。如果函數(shù)值下降，則維持原來的試探方向，并將步長加倍。去鑒定的始點、中間點依次沿試探方向移動一步。此過程一直進行到函數(shù)值再次上升為止，即可找到搜索區(qū)間的終點。最后的得到的三點即為搜索區(qū)間的始點、中間點和終點，形成函數(shù)值的“高低高”趨勢。第3章 黃金分割法的基本原理與思想3.1 黃金分割法的基本思路黃金分割法適用于區(qū)間上的任何單股函數(shù)求極小值問題，對函數(shù)除要求“單峰”外不做其他要求，甚至可以不連續(xù)。因此，這種方法的適應面非常廣。黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法，即在搜索區(qū)間內(nèi)適當插入兩點、，并計算其函數(shù)值。、將區(qū)間分成三段，應用函數(shù)的單峰性質(zhì)，通

15、過函數(shù)值大小的比較，刪去其中一段，是搜索區(qū)間得以縮小。然后再在保留下來的區(qū)間上作同樣的處理，如此迭代下去，是搜索區(qū)間無限縮小，從而得到極小點的數(shù)值近似解。3.2 黃金分割法的基本原理與步驟一維搜索是解函數(shù)極小值的方法之一，其解法思想為沿某一已知方向求目標函數(shù)的極小值點。一維搜索的解法很多，這里主要采用黃金分割法（0.618法）。黃金分割法是用于一元函數(shù)在給定初始區(qū)間內(nèi)搜索極小點的一種方法。它是優(yōu)化計算中的經(jīng)典算法，以算法簡單、收斂速度均勻、效果較好而著稱，是許多優(yōu)化算法的基礎(chǔ)，但它只適用于一維區(qū)間上的凸函數(shù)，即只在單峰區(qū)間內(nèi)才能進行一維尋優(yōu)，其收斂效率較低。其基本原理是：依照“去劣存優(yōu)”原則、

16、對稱原則、以及等比收縮原則來逐步縮小搜索區(qū)間。具體步驟如下：在區(qū)間內(nèi)取點把分為三段。如果>,令=,=,=；如果<，令=,=,=,如果和都大于收斂精度，則重新開始。因為為單峰區(qū)間，這樣每次可將搜索區(qū)間縮小0.618倍或0.382倍，處理后的區(qū)間都將包含極小點的區(qū)間縮小，然后在保留下來的區(qū)間上作同樣的處理，如此迭代下去，將使搜索區(qū)逐步縮小，滿足預先給定的精度時，即獲得一維優(yōu)化問題的近似最優(yōu)解。3.3 黃金分割0.618算法（1）給定區(qū)間及>0； （2）計算，并計算；（3）若，轉(zhuǎn)（4），否則轉(zhuǎn)（5）；（4）若，則停止，輸出，否則a=r，r=u,轉(zhuǎn)（3）；（5）若，則停止，輸出，否則

17、b=u，u=r,轉(zhuǎn)（3）；3.4 算法流程圖圖3-1 黃金分割算法的流程圖第4章 優(yōu)化程序的計算結(jié)果及其分析4.1 用matlab編寫源程序syms x;f=inline('x4-5*x3+4*x2-6*x+60','x');a=0;b=10;epsilon=0.00001; x1=b-0.618*(b-a);f1=f(x1); x2=a+0.618*(b-a);f2=f(x2);while(abs(b-a)>epsilon) if f1<f2 b=x2;x2=x1;f2=f1; x1=a+0.382*(b-a); f1=subs(f,x,x1);

18、elseif f1=f2 a=x1;b=x2; x2=a+0.618*(b-a);f2=subs(f,x,x2); x1=a+0.382*(b-a);f1=subs(f,x,x1); else a=x1;x1=x2;f1=f2; x2=a+0.618*(b-a); f2=subs(f,x,x2); endenddisp('目標函數(shù)為：')f='x4-5*x3+4*x2-6*x+60'disp('最優(yōu)解為：')best_x=(a+b)/2disp('目標函數(shù)極小值為：')best_fx=subs(f,x,best_x)4.2 源程序

19、計算過程及結(jié)果1. 給定搜索區(qū)間0,10以及收斂精度epsilon=0.000012. 按坐標點計算公式，計算和，并計算其對應的函數(shù)值，。3. 根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標點計算公式，需進行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗點及其函數(shù)值。4. 檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠近，如果條件不滿足則返回到步驟2。5. 如果條件滿足，則取最后的兩試驗點的平均值作為極小點的數(shù)值近似解。6. 該程序運行的結(jié)果如下截屏所示。圖4-1 黃金分割法程序運行結(jié)果第5章 一維搜索優(yōu)化的比較和分析5.1 進退法的原理及特點 算法思想從某一點出發(fā)，任選一個方向和步長，向前試

20、探性的走一步，求出該點的函數(shù)值。如果有利（指該點函數(shù)值較?。拖蚯白咭徊?，并加大步長再向前試探一步；否則，就縮小步長反方向（后退方向）試探一步。如此反復搜索，當步長縮小到一定程度時停止。最后搜索到的點即為極值點。其特點為：結(jié)構(gòu)和程序簡單，但效率偏低。 計算步驟1. 給定初始點t0，初始點長h>0，允許誤差e>0，步長因子blpha屬于（0，1），alpha>1，計算f0=f(t0)。2. 令試算點t=xk+h，計算ft=f(t)。3. 若fk>f，則k=k+1，xk=t，h=alpha*h，轉(zhuǎn)第二步：否則，置h=-blpha*h，轉(zhuǎn)第 （4）步。4. 若|h|<

21、e，則停止計算，xk 為近似極小點：否則轉(zhuǎn)第二步。5.2 插值法的原理及特點 算法原理簡介在求解一元函數(shù)的極小點時，常常利用一個低次插值多項式來逼近原目標函數(shù)，然后求該多項式的極小點(低次多項式的極小點比較容易計算)，并以此作為目標函數(shù)的近似極小點。如果其近似的程度尚未達到所要求的精度時，可以反復使用此法，逐次擬合，直到滿足給定的精度時為止。其特點為搜索效率較高，收斂速度快。 插值算法計算過程圖5-1 插值算法的流程圖總 結(jié)一、 課程心得本人覺得優(yōu)化設計這門學科很有意義，很有價值，對整個機械行業(yè)以及其他的行業(yè)的幫助非常大，是難得的一門課程，當然自身的收獲也讓自己覺得研究生的生活是非常充實的，并

22、對以后的學習生活充滿了期待?？偟膩碚f，機械優(yōu)化設計的課程內(nèi)容是就如何求得機械設計過程中遇到的最優(yōu)值的選擇問題進行多方法多角度合理闡述。課程敘述了根據(jù)不同的約束模型而得到的不同的擇優(yōu)方法，以及列舉出了許多優(yōu)化算法在機械方面應用的實例，給我留下了深刻的印象，也使我學到了在本科及工作階段所沒有學到的新的知識。由于課時的關(guān)系和學習時間的有限，而且關(guān)于本課程編程所需要的Matlab軟件因為以前沒有接觸過而倍感生疏，故本次實驗報告的撰寫以及相關(guān)程序的編寫會顯得有些粗略和不足，希望老師您能夠批評指正。我會以后的研究生生活中，繼續(xù)對本課程進行研究和學習，爭取達到完全吸收和靈活運用的程度，扎實的打好研一的理論與

23、方法基礎(chǔ)，為今后的科研生活做好準備。二、內(nèi)容體會本人比較喜歡楊老師講課時嚴謹又不乏幽默的風格。本來這門課程講的都是一些優(yōu)化算法以及數(shù)學理論方面的東西，盡管意義重大，但不免會有些枯燥和乏味，但楊老師能夠在講理論、述方法的同時給我們講了許多歷史、地理、物理、政治、生活、工作、理想以及國內(nèi)外的相關(guān)事件，并對其進行解析和描述，讓我們在學習疲憊之時能夠及時得到放松，更重要的是，我們可以從中學到一些數(shù)學優(yōu)化方法之外的東西，我稱之為人生優(yōu)化方法。本人是工作了一年之后才選擇辭職回來讀研的，接觸過社會上的生活，也領(lǐng)教過一些社會上的生存之道，所以對楊老師就企業(yè)工作以及責任義務方面的觀點深表贊同，自然也深有體會。楊

24、老師有兩句話我深以為然：“中學時你可以逃避責任，因為你的父母可以原諒你；大學時你也可以逃避責任，因為你的老師可以原諒你；工作時你如果再逃避責任，沒人會原諒你，領(lǐng)導只會辭退你”，“要想生存，誰都不能依靠，只能靠自己”我對此深表贊同，生活是現(xiàn)實的，現(xiàn)實是競爭的，競爭是殘酷的，只有學得一身本事，才能在這個充滿競爭的現(xiàn)實社會中擁有立足之地。附 錄一、無約束優(yōu)化方法程序考核題1. 牛頓法的 Matlab編程源程序fx=sym('4*(x1-5)2+(x2-6)2');f1=diff(fx,'x1');diff(fx,'x2');ot1=diff(fx,&#

25、39;x1',2); ot2=diff(fx,'x2',1);ot2=diff(ot2,'x1',1);ot3=diff(fx,'x2',1);ot3=diff(ot3,'x1',1);ot4=diff(fx,'x2',2);f2=ot1,ot2;ot3,ot4; X=8;9; zz=8;9; while norm(double(zz)>0.001 yy=X; f3=subs(f1,'x1',X(1); f3=subs(f3,'x2',X(2); f4=subs(f2,

26、'x1',X(1); f4=subs(f4,'x2',X(2); g1=-inv(f4)*f3; b1=sym('b1'); X=yy+b1*g1; f5=subs(fx,'x1',X(1); f5=subs(f5,'x2',X(2); sw2=sym2poly(f5);sw1=polyder(sw2); if sw1=0 dwj=eval(f5);elsewe=roots(sw1);for t=1 : length(we) cc(t)=polyval(sw2,we(t);endhi=find(cc=min(min(cc); digits(8); qq=vpa(we(hi); end X=yy+qq*g1; zz=X