華中科技大學(xué)工程優(yōu)化設(shè)計(jì)-一維搜索

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

(a)(c)

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

初始化.k=0,k=0,hk=h0,t=t0>1.計(jì)算0=(0).2.比較目標(biāo)值.k+1=k+hk,計(jì)算k+1=(k+1).若k+1<k,轉(zhuǎn)步3;否則,轉(zhuǎn)步4.3.加大步長(zhǎng).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-當(dāng)前點(diǎn);-前一點(diǎn);k+1-后一點(diǎn);hk-步長(zhǎng)t-步長(zhǎng)加倍系數(shù)

一維搜索方法(2)舉例

k-迭代變量;k-當(dāng)前點(diǎn);-前一點(diǎn);k+1-后一點(diǎn);hk-步長(zhǎng)t-步長(zhǎng)加倍系數(shù)

()014235t=1.5

a=3

b=5

一維搜索方法三.黃金分割法(0.618法)acb(1)算法思想逐步縮小區(qū)間[a,b].一般來(lái)說(shuō),在[a,b]中只增加計(jì)算一個(gè)點(diǎn),難以確定極點(diǎn)所在的較小區(qū)間.可是,0.618法通過(guò)合理選擇加計(jì)算點(diǎn),能夠達(dá)到增一點(diǎn)來(lái)縮小區(qū)間.aμbacb一維搜索方法a1μ1b11a2μ2b22目標(biāo):希望只計(jì)算一個(gè)新點(diǎn)就能將區(qū)間縮小倍.bk+1-ak+1=(bk-ak)另外,設(shè),μ在[a,b]中對(duì)稱

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.計(jì)算(1),(μ1).取>0.2.比較目標(biāo)值.若(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),

計(jì)算(μ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),

計(jì)算(k+1),轉(zhuǎn)步2.一維搜索方法四.Fibonacci法(1)算法思想逐步縮小區(qū)間[a,b].一般來(lái)說(shuō),在[a,b]中只增加計(jì)算一個(gè)點(diǎn),難以確定極點(diǎn)所在的較小區(qū)間.可是,Fibonacci法通過(guò)Fibonacci數(shù)列選擇新計(jì)算點(diǎn),能夠達(dá)到增一點(diǎn)來(lái)縮小區(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所以每次也只需計(jì)算一個(gè)新點(diǎn)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)算法分析收斂速度與黃金分割法同為線性收斂,實(shí)際速度比黃金分割法稍快,但黃金分割法更容易實(shí)現(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)一維搜索方法五.逐次插值方法(三點(diǎn)二次插值)123二次極值點(diǎn)下一循環(huán)以23為插值點(diǎn)收斂階