黃金分割法進(jìn)退法原理及流程圖

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

2、極小值點(diǎn)。一維搜索的解法很多，這里主要采用黃金分割法（0.618法）。該方法用不變的區(qū)間縮短率0.618代替斐波那契法每次不同的縮短率，從而可以看成是斐波那契法的近似，實(shí)現(xiàn)起來比較容易，也易于人們所接受。 黃金分割法是用于一元函數(shù)f(x)在給定初始區(qū)間a,b內(nèi)搜索極小點(diǎn)*的一種方法。它是優(yōu)化計(jì)算中的經(jīng)典算法，以算法簡(jiǎn)單、收斂速度均勻、效果較好而著稱，是許多優(yōu)化算法的基礎(chǔ)，但它只適用于一維區(qū)間上的凸函數(shù)6，即只在單峰區(qū)間內(nèi)才能進(jìn)行一維尋優(yōu)，其收斂效率較低。其基本原理是：依照“去劣存優(yōu)”原則、對(duì)稱原則、以及等比收縮原則來逐步縮小搜索區(qū)間7。具體步驟是：在區(qū)間a,b內(nèi)取點(diǎn)：a1 ，a2 把a(bǔ),b分為

3、三段。如果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都大于收斂精度重新開始。因?yàn)閍,b為單峰區(qū)間，這樣每次可將搜索區(qū)間縮小0.618倍或0.382倍，處理后的區(qū)間都將包含極小點(diǎn)的區(qū)間縮小，然后在保留下來的區(qū)間上作同樣的處理，如此迭代下去，將使搜索區(qū)a,b逐步縮小，直到滿足預(yù)先給定的精度時(shí)，即獲得一維優(yōu)化問題的近似最優(yōu)解。黃金分割法原理如圖所示， （3） 程序流程如下：4 實(shí)驗(yàn)所編程序框圖開始r=0.618給定a=-3,b=5,收斂精

4、度=0.001結(jié)束a*=(a+b)/2a1=b-r*(b-a)y1=f(a1)b=a2a2=a1 y2=y1a2=a+r*(b-a)y2=f(a2)a=a1a1=a2 y1=y2y1>=y2a1=b-r*(b-a) y1=f(a1)a2=a+r*(b-a) y2=f(a2)否是(b-a)/b<和 （y2-y1）/y2<?否是#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

5、-*a)<=e) s=f(*b+*a)/2); else x1=*b-0.618*(*b-*a); x2=*a+0.618*(*b-*a); if(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

6、",a,b,s,n); 5 程序運(yùn)行結(jié)果如下圖：2進(jìn)退法 （1）算法原理進(jìn)退法是用來確定搜索區(qū)間（包含極小值點(diǎn)的區(qū)間）的算法，其理論依據(jù)是：為單谷函數(shù)（只有一個(gè)極值點(diǎn)），且為其極小值點(diǎn)的一個(gè)搜索區(qū)間，對(duì)于任意，如果，則為極小值的搜索區(qū)間，如果，則為極小值的搜索區(qū)間。因此，在給定初始點(diǎn)，及初始搜索步長(zhǎng)的情況下，首先以初始步長(zhǎng)向前搜索一步，計(jì)算。（1） 如果則可知搜索區(qū)間為，其中待求，為確定，后退一步計(jì)算，為縮小系數(shù)，且，直接找到合適的，使得，從而確定搜索區(qū)間。（2） 如果則可知搜索區(qū)間為，其中待求，為確定，前進(jìn)一步計(jì)算，為放大系數(shù)，且，知道找到合適的，使得，從而確定搜索區(qū)間。進(jìn)退法求極

7、值基本思想： 對(duì)f(x)任選一個(gè)初始點(diǎn)x1及初始步長(zhǎng)h0， 通過比較這兩點(diǎn)函數(shù)值的大小，確定第三點(diǎn)位置，比較這三點(diǎn)的函數(shù)值大小，確定是否為 “高低高” 形態(tài)。算法原理1.試探搜索： 選定初始點(diǎn)x1, x2= x1+ h0，計(jì)算 y1f(x1)， y2f(x2) （a）如y1>y2,轉(zhuǎn)2向右前進(jìn)； （b）如y1<y2, 轉(zhuǎn)3向左后退；圖8.12.前進(jìn)搜索 加大步長(zhǎng) h2 h ，產(chǎn)生新點(diǎn)x3= x2+ 2h0 ；（a）如y2<y3，則函數(shù)在x1，x3內(nèi)必有極小點(diǎn)，令a= x1，b= x3搜索區(qū)間為a，b ；(b)如y2>y3， 令x1=x2 ，y1=y2 ； x2=x3 ，

8、y2=y3 ； h=2h 重新構(gòu)造新點(diǎn)x3=x2+h，并比較y2、y3的大小，直到y(tǒng)2<y3。 圖8.23.后退搜索 令 h-h0 ，令x3=x1 ，y3=y1 ；x1=x2 ，y1=y2 ；x2=x3 ，y2=y3 ；h=2h；產(chǎn)生新點(diǎn)x3= x2+ h ； （a）如y2<y3，則函數(shù)在x1，x3內(nèi)必有極小點(diǎn)，令a= x3，b= x1，搜索區(qū)間為a，b （b）如y2>y3， 令x1=x2 ，y1=y2 ； x2=x3 ，y2=y3 ；h=2h重新構(gòu)造新點(diǎn)x3=x2+h，并比較y2、y3的大小，直到y(tǒng)2<y3。令a= x1，b= x3，搜索區(qū)間為a，b ； 圖8.3（2

9、）算法步驟用進(jìn)退法求一維無約束問題的搜索區(qū)間（包含極小值點(diǎn)的區(qū)間）的基本算法步驟如下：（1） 給定初始點(diǎn)，初始步長(zhǎng)，令，；（2） 令，置；（3） 若，則轉(zhuǎn)步驟（4），否則轉(zhuǎn)步驟（5）；（4） 令，令，轉(zhuǎn)步驟（2）；（5） 若，則轉(zhuǎn)步驟（6）否則轉(zhuǎn)步驟（7）；（6） 令，轉(zhuǎn)步驟（2）；（7） 令，停止計(jì)算，極小值點(diǎn)包含于區(qū)間（3）算法的MATLAB實(shí)現(xiàn)在MATLAB中編程實(shí)現(xiàn)的進(jìn)退函數(shù)為：功能：用進(jìn)退法求解一維函數(shù)的極值區(qū)間。調(diào)用格式：其中，：目標(biāo)函數(shù)； ：初始點(diǎn)； ：初始步長(zhǎng)； ：精度； ：目標(biāo)函數(shù)取包含極值的區(qū)間左端點(diǎn)； ：目標(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=3 eps=1.0e-6;endx1=x0;k=0;h=h0;while 1 x4=x1+h; %試探步 k=k+1; f4=subs(f,findsym(f),x4); f1=subs(f,findsym(f),x1); if f4<f1 x2=x1; x1=x4; f2=