一種改進的0.618法

董媛媛,謝承蓉 (鄖陽師范高等專科學校數學與財經系,湖北十堰 442000)

一種改進的0.618法

董媛媛,謝承蓉 (鄖陽師范高等專科學校數學與財經系,湖北十堰 442000)

0.618法是一種極為常用的一維搜索方法,具有良好的的收斂性,但其收斂的速度太慢,且隨著最優解精度要求的提高,其收斂速度會越來越慢。提出了一種改進的0.618法。數值試驗結果表明,與原0.618法和牛頓法相比,改進的0.618法不但總能收斂到一個局部極小點,而且在各種情況下都能保持較快的收斂速度,克服了原0.618法收斂速度慢的缺點。

0.618法;改進算法;穩定性;收斂性

1 0.618法

定理1[5]設f是區間[a,b]上的單峰函數,x(1),x(2)∈[a,b],且x(1)＜x(2),如果f(x(1))＞f(x(2)),則對每一個x∈[a,x(1)],有f(x)＞f(x(2));如果f(x(1))≤f(x(2)),則對于每一個x∈[x(2),b],有f(x)≥f(x(1))。

0.618法又叫黃金分割法,其基本思想如下:根據定理1,通過取試探點使包含極小點的區間(不確定區間)不斷縮短,當區間長度小到一定程度時,區間上各點的函數值均接近極小值,因此任意一點都可作為極小點的近似。

0.618法是將每次迭代區間的縮短率定為0.618,所以每次迭代的試點分別為:

對于預先給定的精確度ε＞0,當保留的區間長度|b-a|≤ε時,停止迭代。此時可取保留區間[a,b]內任一點作為極小點的近似值。

0.618法的算法步驟如下:

給定a,b(a＜b)及ε＞0;

步4 若f1＜f2,b=x2,x2=x1,f2=f1,轉步2;

若f1=f2,a=x1,b=x2,轉步1;

若f1＞f2,a=x1,x1=x2,f1=f2,轉步5;

步5 令x2=a+0.618(b-a),f2=f(x2),轉步3。

2 改進

設f(x)在區間[ak,bk]內是連續的單峰函數,x0是極小點。若f(x)函數值較小的端點為ak,過點ak作f(x)的一條與x軸平行的線,該平行線與點x0的另一側曲線y=f(x)有一個交點,設此交點的橫坐標為m,可以稱點m為點ak的平行點[4]。由此過程知[ak,m]?[ak,bk],而且點x0落在區間[ak,m]內。從而比較與精度要求l的大小。

計算函數值f(λk+1)和f(μk+1),得到一個新的搜索區間且x0仍落在新的搜索區間內(ak+1,bk+1[

],其中ak+1=ak,bk+1=μ)。重復上述過程,則搜索區間長度會不斷縮小且趨近0,最后可穩定地收斂到極小點x0。

改進0.618法的算法步驟如下:

步1 給定初始搜索區間[a,b]及精度要求l＞0,計算函數值f a()和f b();

3 數值試驗

為了檢驗改進的算法的效果,設計了函數f(x)=2x2-x-1,分別用改進的算法、0.618法、牛頓法對它們在指定區間的極小點進行了搜索,結果如表1所示。

從表1中可以看出,0.618法總能收斂到一個局部極小點,但收斂速度與改進的0.618法相比較慢,且隨精度要求的增加迭代次數明顯增加;牛頓法在初始點的位置較好時,收斂速度快,但初始點的位置選得不好時,其收斂速度就可能變慢,甚至不收斂或收斂到一個非局部極小點;而改進的0.618法不但總能收斂到一個局部極小點,即具有穩定的收斂性,而且在各種情況下都能保持較快的收斂速度。

表1 改進的算法與0.618法、牛頓法的比較

[1]鄧乃揚.無約束最優化方法[M].北京:科學出版社,1982.

[2]陳寶林.最優化理論與算法[M].北京:清華大學出版社,2005.

[3]薛嘉慶.最優化原理與方法[M].北京:冶金工業出版社,1983

[4]徐望寶,陳雪波.快速穩定收斂的一維搜索算法[J].鞍山科技大學學報,2006(3):18-20.

[5]李慶揚.數值分析[M].北京:清華大學出版社,2001.

[編輯] 張濤

O242

A

1673-1409(2014)22-0004-03

2014-04-12

湖北省教育廳青年科研項目(Q20145001);鄖陽師范高等專科學校校級項目(2012B08)。

董媛媛(1 9 8 3-),女,碩士,講師,現主要從事最優化理論方面的教學與研究工作。