黃金分割法進退法原理及流程圖

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

2、極小值點。一維搜索的解法很多，這里主要采用黃金分割法（0.618法）。該方法用不變的區(qū)間縮短率0.618代替斐波那契法每次不同的縮短率，從而可以看成是斐波那契法的近似，實現(xiàn)起來比較容易，也易于人們所接受。 黃金分割法是用于一元函數(shù)f(x)在給定初始區(qū)間a,b內(nèi)搜索極小點*的一種方法。它是優(yōu)化計算中的經(jīng)典算法，以算法簡單、收斂速度均勻、效果較好而著稱，是許多優(yōu)化算法的基礎(chǔ)，但它只適用于一維區(qū)間上的凸函數(shù)6，即只在單峰區(qū)間內(nèi)才能進行一維尋優(yōu)，其收斂效率較低。其基本原理是：依照“去劣存優(yōu)”原則、對稱原則、以及等比收縮原則來逐步縮小搜索區(qū)間7。具體步驟是：在區(qū)間a,b內(nèi)取點：a1 ，a2 把a,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都大于收斂精度重新開始。因為a,b為單峰區(qū)間，這樣每次可將搜索區(qū)間縮小0.618倍或0.382倍，處理后的區(qū)間都將包含極小點的區(qū)間縮小，然后在保留下來的區(qū)間上作同樣的處理，如此迭代下去，將使搜索區(qū)a,b逐步縮小，直到滿足預(yù)先給定的精度時，即獲得一維優(yōu)化問題的近似最優(yōu)解。黃金分割法原理如圖所示， （3） 程序流程如下：4 實驗所編程序框圖開始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 程序運行結(jié)果如下圖：2進退法 （1）算法原理進退法是用來確定搜索區(qū)間（包含極小值點的區(qū)間）的算法，其理論依據(jù)是：為單谷函數(shù)（只有一個極值點），且為其極小值點的一個搜索區(qū)間，對于任意，如果，則為極小值的搜索區(qū)間，如果，則為極小值的搜索區(qū)間。因此，在給定初始點，及初始搜索步長的情況下，首先以初始步長向前搜索一步，計算。（1） 如果則可知搜索區(qū)間為，其中待求，為確定，后退一步計算，為縮小系數(shù)，且，直接找到合適的，使得，從而確定搜索區(qū)間。（2） 如果則可知搜索區(qū)間為，其中待求，為確定，前進一步計算，為放大系數(shù)，且，知道找到合適的，使得，從而確定搜索區(qū)間。進退法求極

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

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

9、）算法步驟用進退法求一維無約束問題的搜索區(qū)間（包含極小值點的區(qū)間）的基本算法步驟如下：（1） 給定初始點，初始步長，令，；（2） 令，置；（3） 若，則轉(zhuǎn)步驟（4），否則轉(zhuǎn)步驟（5）；（4） 令，令，轉(zhuǎn)步驟（2）；（5） 若，則轉(zhuǎn)步驟（6）否則轉(zhuǎn)步驟（7）；（6） 令，轉(zhuǎn)步驟（2）；（7） 令，停止計算，極小值點包含于區(qū)間（3）算法的MATLAB實現(xiàn)在MATLAB中編程實現(xiàn)的進退函數(shù)為：功能：用進退法求解一維函數(shù)的極值區(qū)間。調(diào)用格式：其中，：目標函數(shù)； ：初始點； ：初始步長； ：精度； ：目標函數(shù)取包含極值的區(qū)間左端點； ：目標函數(shù)取包含極值的區(qū)間又端點。進退法的MATLAB程序代碼如下：function minx,maxx=minJT(f,x0,h0,eps)%目標函數(shù):f;%初始點:x0;%初始步長:h0;%精度:eps;%目標函數(shù)取包含極值的區(qū)間左端點:minx;%目標函數(shù)取包含極值的區(qū)間又端點: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=