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

工程優(yōu)化設(shè)計(jì)內(nèi)容提要工程優(yōu)化問題建模優(yōu)化數(shù)學(xué)理論一維搜索方法無約束問題直接搜索方法無約束問題間接接搜索方法約束問題直接搜索方法線性規(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ū)間的進(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ū)間.另外,用到步長加倍,提高搜索效率.一維搜索方法(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.加大步長.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-步長t-步長加倍系數(shù)

一維搜索方法(2)舉例

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

()014235t=1.5

a=3

b=5

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