工程優化設計內容提要工程優化問題建模優化數學理論一維搜索方法無約束問題直接搜索方法無約束問題間接接搜索方法約束問題直接搜索方法線性規劃與二次規劃問題求解約束問題間接搜索方法啟發式算法優化軟件系統一維搜索方法一.問題的提出子優化問題:FindMinimize()=f(x(k)+s(k))子優化問題的一階必要條件:’()=0[f(x(k)+s(k))]Ts(k)=0fs(k)一維搜索方法二.確定搜索區間的進退法區間搜索的終止條件:找到三點a,c,b,滿足

(a)(c)

(b),輸出[a,b].acb(1)算法思想先在初始點的左右方向中確定一個下降方向.沿著下降方向向前搜索,直到遇到上升點.搜索的前一點與上升點構成所求區間.另外,用到步長加倍,提高搜索效率.一維搜索方法(2)算法

初始化.k=0,k=0,hk=h0,t=t0>1.計算0=(0).2.比較目標值.k+1=k+hk,計算k+1=(k+1).若k+1<k,轉步3;否則,轉步4.3.加大步長.hk+1=thk,=k,k=k+1,k=k+1,k=k+1,轉步2.4.反向搜索.若k=0,轉換搜索方向,hk=-hk,=k+1,轉步2;

否則,停止.輸出a=min{,k+1},b=max{,k+1}.k-迭代變量;k-當前點;-前一點;k+1-后一點;hk-步長t-步長加倍系數

一維搜索方法(2)舉例

k-迭代變量;k-當前點;-前一點;k+1-后一點;hk-步長t-步長加倍系數

()014235t=1.5

a=3

b=5

一維搜索方法三.黃金分割法(0.618法)acb(1)算法思想逐步縮小區間[a,b].一般來說,在[a,b]中只增加計算一個點,難以確定極點所在的較小區間.可是,0.618法通過合理選擇加計算點,能夠達到增一點來縮小區間.aμbacb一維搜索方法a1μ1b11a2μ2b22目標:希望只計算一個新點就能將區間縮小倍.bk+1-ak+1=(bk-ak)另外,設,μ在[a,b]中對稱

bk-μk=k-ak1=a1+(1-)(b1-a1)μ1=a1+(b1-a1)μ2=a2+(b2-a2)=a1+(μ1-a1)=a1+(a1+(b1-a1)-a1)=a1+2(b1-a1)由1=μ2,1-=2,=5-1/2=0.618

一維搜索方法(2)算法

初始化.a1,b1,1=a1+0.382(b1-a1),μ1=a1+0.618(b1-a1),k=1.計算(1),(μ1).取>0.2.比較目標值.若(k)>(μk)轉步3;否則,轉步4.3.若bk-k<,停止,輸出μk.否則,ak+1=k,bk+1=bk,k+1=μk.

μk+1=ak+1+0.618(bk+1-ak+1),

計算(μk+1),轉步2.4.若μk-ak<,停止,輸出k.否則,ak+1=ak,bk+1=μk,μk+1=k.

k+1=ak+1+0.382(bk+1-ak+1),

計算(k+1),轉步2.一維搜索方法四.Fibonacci法(1)算法思想逐步縮小區間[a,b].一般來說,在[a,b]中只增加計算一個點,難以確定極點所在的較小區間.可是,Fibonacci法通過Fibonacci數列選擇新計算點,能夠達到增一點來縮小區間目的.Fibonacci數列F0=F1=1,Fk+1=Fk+Fk-1,k=1,2,…1,1,2,3,5,8,13,….k=ak+(1-k)(bk-ak)μk=ak+k(bk-ak),k=Fn-k/Fn-k+1,每次縮小k倍.一維搜索方法四.Fibonacci法k=ak+(1-k)(bk-ak)μk=ak+k(bk-ak),k=Fn-k/Fn-k+1μk+1=ak+1+k+1(bk+1-ak+1)=ak+k+1(μk-ak)=ak+k+1[(ak+k(bk-ak))-ak]=ak+k+1[k(bk-ak)]=ak+k+1k(bk-ak)k+1=Fn-k-1/Fn-k=(Fn-k+1-Fn-k)/Fn-k

=(Fn-k+1/Fn-k-1)k+1k=(Fn-k+1/Fn-k-1)(Fn-k/Fn-k+1)=1-k所以每次也只需計算一個新點akμkbkkak+1μk+1bk+1k+1kk+1一維搜索方法四.Fibonacci法k=ak+(1-k)(bk-ak)μk=ak+k(bk-ak),k=Fn-k/Fn-k+1μn=bn+1,an+1=anbn+1=an+1+n(bn-an),

bn+1-an+1=n(bn-an),=nn-1n-2…1(b1-a1)=(F0/F1)(F1/F2)…(Fn-1/Fn)(b1-a1)=(1/Fn)(b1-a1),所以,取n使Fn>(b1-a1)/,即可得逼近精度為.另外,Fk-1/Fk->=0.618a1μ1b11a2μ2b22一維搜索方法四.Fibonacci法算法與黃金分割法類似.(2)算法(3)算法分析收斂速度與黃金分割法同為線性收斂,實際速度比黃金分割法稍快,但黃金分割法更容易實現.一維搜索方法bn+1-an+1=(bn-an)=n(b1-a1)bn+1-an+1=n(bn-an),=

nn-1n-2…1(b1-a1)=(1/Fn)(b1-a1)一維搜索方法五.逐次插值方法(三點二次插值)123二次極值點下一循環以23為插值點收斂階