黃金分割法,進(jìn)退法,基礎(chǔ)原理及經(jīng)過(guò)流程圖

1、*1黃金分割法的優(yōu)化問(wèn)題(1)黃金分割法基本思路：黃金分割法適用于a , b區(qū)間上的任何單股函數(shù)求極小值問(wèn)題， 對(duì)函 數(shù)除要求“單谷”外不做其他要求，甚至可以不連續(xù)。因此，這種方 法的適應(yīng)面非常廣。黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的 試探方法，即在搜索區(qū)間a, b內(nèi)適當(dāng)插入兩點(diǎn)al, a2,并計(jì)算其 函數(shù)值。al, a2將區(qū)間分成三段，應(yīng)用函數(shù)的單谷性質(zhì)，通過(guò)函數(shù) 值大小的比較，刪去其中一段，是搜索區(qū)間得以縮小。然后再在保留 下來(lái)的區(qū)間上作同樣的處理，如此迭代下去，是搜索區(qū)間無(wú)限縮小， 從而得到極小點(diǎn)的數(shù)值近似解。(2)黃金分割法的基本原理一維搜索是解函數(shù)極小值的方法之一，其解法思想為

2、沿某一已知方向 求目標(biāo)函數(shù)的極小值點(diǎn)。一維搜索的解法很多，這里主要采用黃金分 割法(0.618法)。該方法用不變的區(qū)間縮短率 0.618代替斐波那契 法每次不同的縮短率，從而可以看成是斐波那契法的近似， 實(shí)現(xiàn)起來(lái) 比較容易，也易于人們所接受。rl=a+0,382(>-a) r2=a+0,618Cb-a) 如圖班2戶(hù)母4) 所以新區(qū)間為a ,于2以為新區(qū)間，繼域求新的試點(diǎn)黃金分割法是用于一元函數(shù)f(x)在給定初始區(qū)間a,b內(nèi)搜索極 小點(diǎn)* *的一種方法。它是優(yōu)化計(jì)算中的經(jīng)典算法，以算法簡(jiǎn)單、收 斂速度均勻、效果較好而著稱(chēng)，是許多優(yōu)化算法的基礎(chǔ)，但它只適用 于一維區(qū)間上的凸函數(shù)6,即只在單峰

3、區(qū)間內(nèi)才能進(jìn)行一維尋優(yōu)，其 收斂效率較低。其基本原理是：依照“去劣存優(yōu)”原則、對(duì)稱(chēng)原則、 以及等比收縮原則來(lái)逐步縮小搜索區(qū)間7。具體步驟是：在區(qū)間a,b 內(nèi)取點(diǎn)：al , a2把a(bǔ),b分為三段。如果f(a1)>f(a2),令 a=a1,a1=a2,a2=a+r*(b-a);如果 f(a1)<f(a2),令 b=a2,a2=a1,a1=b-r*(b-a), 如果 | (b-a)/b | 和 | (y1-y2)/y2| 都大于收斂精度e重新開(kāi)始。因?yàn)閍,b為單峰區(qū)間，這樣每次可將搜索區(qū)間 縮小0.618倍或0.382倍，處理后的區(qū)間都將包含極小點(diǎn)的區(qū)間縮小， 然后在保留下來(lái)的區(qū)間上作同

4、樣的處理，如此迭代下去，將使搜索區(qū)a,b逐步縮小，直到滿(mǎn)足預(yù)先給定的精度時(shí)，即獲得一維優(yōu)化問(wèn)題 的近似最優(yōu)解。黃金分割法原理如圖1所示，(3)程序流程如下:*4實(shí)驗(yàn)所編程序框圖結(jié)束#include math.h#include «stdio.h»#define f(x) x*x+2*xdouble calc(double *a,double *b,double e,int *n) double x1,x2,s;if(fabs(*b-*a)<=e)s=f(*b+*a)/2);else x1=*b-0.618*(*b-*a);x2=*a+0.618*(*b-*a);if(

5、f(x1)>f(x2)*a=x1;else*b=x2;*n=*n+1;s=calc(a,b,e,n);return s;main() double s,a,b,e;int n=0;scanf("%lf %lf %lf",&a,&b,&e);s=calc(&a,&b,e,&n);printf("a=%lf,b=%lf,s=%lf,n=%dn",a,b,s,n);5程序運(yùn)行結(jié)果如下圖:2進(jìn)退法（1）算法原理進(jìn)退法是用來(lái)確定搜索區(qū)間（包含極小值點(diǎn)白區(qū)間）的算法，其理論依據(jù)是：f（x）為單谷函數(shù)（只有一個(gè)極值

6、點(diǎn)），且a,b為其極小值點(diǎn)的一個(gè)搜索區(qū)間，對(duì)于任意xla,b,如果f k fX2，則a, X2為極小值的搜索區(qū)間，如果fxifX2,則xi,b為極小值的搜索區(qū)間。因此，在給定初始點(diǎn)xo,及初始搜索步長(zhǎng)h的情況下，首先以初始步長(zhǎng)向前搜索一步，計(jì)算f x0 h。(1)如果 f x0f x0 h則可知搜索區(qū)間為%x0 h,其中%寺求，為確定 %后退一步計(jì)算f(x°h),為縮小系數(shù)，且01,直接找到合適的，使得f(xoh) f xo ,從而確定搜* .索區(qū)間xoh, xo h。(2)如果 f % f x0 h則可知搜索區(qū)間為xo,%,其中%寺求，為確定 前進(jìn)一步計(jì)算f (xoh), 為、，a

7、一，、 a 4、一*放大系數(shù)，且 1 ,知道找到合適的，使得f % hf (xoh),從而確定搜索*.區(qū)間xo, %h。進(jìn)退法求極值基本思想:對(duì)f(x)任選一個(gè)初始點(diǎn)xi及初始步長(zhǎng)ho,通過(guò)比較這兩點(diǎn)函數(shù)值的大 小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為“高一低-高”形態(tài)。 算法原理 1.試探搜索：選定初始點(diǎn)(a)(b)x1, x2= x 1+ ho,計(jì)算 y1=f(x1)，y2=f(x2)如y1>y2,轉(zhuǎn)2向右前進(jìn)；如 y1<y22.前進(jìn)搜索加大步長(zhǎng) h=2 h ,廣生新點(diǎn) x3= x2+ 2h o ;*(a)如y2<y3,則函數(shù)在xi,x3內(nèi)必有極小點(diǎn)，令 a

8、=xi,b= x3搜索區(qū)間為a, b;(b)如 y2>y3,令 xi=x2 , y產(chǎn)y2 ；x2=x3 , y2=y3 ； h=2h重新構(gòu)造新點(diǎn) x3=x2+h,y2<y3。圖8.23.后退搜索令h = -ho，令x3=x 1產(chǎn)生新點(diǎn)x3= x 2+ h ；(a)如y2<y3,則函數(shù)在為a, b(b)如 y2>y3,y3=yi ； xi=x2 , yi=y2 ；xi, x3內(nèi)必有極小點(diǎn),x2=x3 , y2=y3 ； h=2h；a= x3, b= x i,搜索區(qū)間令 xi=x2 , yi=y2 ； x2=x3 , y2=y3 ； 重新構(gòu)造新點(diǎn)x3=x2+h,并比較y2、

9、y3的大小， 搜索區(qū)間為a, b;h=2h直至ij y2<y3。令 a= xi, b= x 3,圖8.3(2)算法步驟用進(jìn)退法求一維無(wú)約束問(wèn)題min f(x),x R的搜索區(qū)間(包含極小值點(diǎn)的區(qū)間)的基本算法步驟如下：(1) 給定初始點(diǎn)x(0),初始步長(zhǎng)ho,令hho, x(i)x(0), k 0 ；(2) 令xxh,置k k 1；(3) 若f xf x，則轉(zhuǎn)步驟(4),否則轉(zhuǎn)步驟(5);(4)令 x(2)x x(1)x(4), f x(2)f x(1) , f x f x(4),令 h 2h,轉(zhuǎn)步驟(2);(5) 若k 1 ,則轉(zhuǎn)步驟(6)否則轉(zhuǎn)步驟(7);(6)令h h, xx，f

10、x f x，轉(zhuǎn)步驟(2)； 令xx，xx，xx，停止計(jì)算，極小值點(diǎn)包含于區(qū)間x(1),x(3)或x(3),x(1)(3)算法的MATLAB 實(shí)現(xiàn)在MATLAB中編程實(shí)現(xiàn)的進(jìn)退函數(shù)為：min JT功能：用進(jìn)退法求解一維函數(shù)的極值區(qū)間。調(diào)用格式：min x,max x min JT( f, x0, h0,eps)其中，f :目標(biāo)函數(shù)；x0：初始點(diǎn)；h0：初始步長(zhǎng)；eps :精度；minx：目標(biāo)函數(shù)取包含極值的區(qū)間左端點(diǎn)； maxx：目標(biāo)函數(shù)取包含極值的區(qū)間又端點(diǎn)。進(jìn)退法的MATLAB 程序代碼如下：function minx,maxx=minJT(f,x0,h0,eps)%目標(biāo)函數(shù)：f;%初始點(diǎn)：x0;%初始步長(zhǎng)：h0;%精度:eps;%目標(biāo)函數(shù)取包含極值的區(qū)間左端點(diǎn)：minx;%目標(biāo)函數(shù)取包含極值的區(qū)間又端點(diǎn)：maxx;format long;if nargin=3eps=1.0e-6;endx1=x0;k=0;h=h0;while 1x4=x1+h;%試探步k=k+1;f4=subs(f,findsym,x4);f1=subs(f,findsym,x1);