華中科技大學工程優(yōu)化設計-一維搜索

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

(a)(c)

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

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

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

一維搜索方法(2)舉例

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

()014235t=1.5

a=3

b=5

一維搜索方法三.黃金分割法(0.618法)acb(1)算法思想逐步縮小區(qū)間[a,b].一般來說,在[a,b]中只增加計算一個點,難以確定極點所在的較小區(qū)間.可是,0.618法通過合理選擇加計算點,能夠達到增一點來縮小區(qū)間.aμbacb一維搜索方法a1μ1b11a2μ2b22目標:希望只計算一個新點就能將區(qū)間縮小倍.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)轉(zhuǎn)步3;否則,轉(zhuǎn)步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),轉(zhuǎn)步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),轉(zhuǎn)步2.一維搜索方法四.Fibonacci法(1)算法思想逐步縮小區(qū)間[a,b].一般來說,在[a,b]中只增加計算一個點,難以確定極點所在的較小區(qū)間.可是,Fibonacci法通過Fibonacci數(shù)列選擇新計算點,能夠達到增一點來縮小區(qū)間目的.Fibonacci數(shù)列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)算法分析收斂速度與黃金分割法同為線性收斂,實際速度比黃金分割法稍快,但黃金分割法更容易實現(xiàn).一維搜索方法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二次極值點下一循環(huán)以23為插值點收斂階