基于0.618法的改進區(qū)間插值法

宗鈺涵，張彥博

(北京郵電大學 理學院，北京 100876)

0 引言

現(xiàn)實中大多數(shù)函數(shù)的導數(shù)是不可用或極難求得的，這時候直接法的應用便廣泛起來。從上述直接法的思想可以看出，決定直接法性能的關鍵有兩點：一是初始區(qū)間的選取，二是包含極小值點子區(qū)間的縮小[4]。

0.618法是一維直接搜索中應用最為廣泛的一種方法，其優(yōu)點是對函數(shù)的連續(xù)性不做要求；每次迭代只計算一個新的試探點，另一個是重復利用的；具有良好的收斂性，收斂速度是線性的。但缺點是收斂太慢。本文在0.618法的基礎之上，提出了一種改進的優(yōu)化方法。其并將其與0.618法比較，通過數(shù)值計算證明了此種方法收斂速度快，迭代步數(shù)少。

1 0.618法

0.618法也稱黃金分割法，其基本思想[5]是：通過對每步試探點函數(shù)值的比較，使包含極小值點的搜索區(qū)間（不確定區(qū)間）不斷縮小，當達到某種準則時，可以找到極小值點的近似。

0.618法取試探點的規(guī)則為：

其計算步驟如下：

2 基于區(qū)間插值的優(yōu)化算法

文獻[ 6][ 7]提出了基于區(qū)間縮小的不同改進算法，它們分別利用區(qū)間一端一階導數(shù)和二階導數(shù)，進一步縮小區(qū)間，但對于導數(shù)不可求或極難求得時，上述方法就不再適用。因此在本文中，我們希望通過利用當前搜索區(qū)間兩端點的函數(shù)值及此區(qū)間上任意一點的函數(shù)值，構造出一種一維線搜索的加速算法，來改進0.618法。

3 數(shù)值實驗

為驗證改進算法的效果，我們選取一個簡單的一維單峰函數(shù)和兩個較復雜的單峰函數(shù)[9]來比較改進的算法與0.618法，將它們對例1、2、3中目標函數(shù)在指定區(qū)間進行搜索，通過對比兩算法的迭代步數(shù)和輸出結果精度，衡量新算法的優(yōu)勢。其中精度我們分別選取10-2，10-4，結果如表2、表3、表4所示。

表2 函數(shù)2在兩種算法下的結果比較

表3 函數(shù)3在兩種算法下的結果比較

表1 函數(shù)1在兩種算法下的結果比較

通過觀察三個函數(shù)的測試結果，改進算法的迭代步數(shù)不僅比0.618法的要小得多，而且最優(yōu)值點精度也有明顯改進，同時構造出的點列能夠在有限步內得到達到所要求精度的最優(yōu)化問題的最優(yōu)解。因此改進算法不僅有穩(wěn)定的收斂性，而且在各種情況下也能保持較快的收斂速度。

同時經(jīng)過分析可知，0.618法每步迭代只計算一個函數(shù)值，而改進的算法每步計算兩個函數(shù)值，但因為迭代步數(shù)減少不止一半，因此改進算法也是有一定提高的。我們通過測試函數(shù)說明這一結論，針對例1在不同長度的區(qū)間上的區(qū)間縮短率，對0.618法和改進算法進行比較，結果如表4所示。

表4 兩算法對于不同區(qū)間的計算

觀察表4，當初始區(qū)間是[-1,500]時，迭代步數(shù)是0.618法的三分之一，同時區(qū)間縮短率減小了28%；當初始區(qū)間是[-1,0.01]時，迭代步數(shù)是0.618法的四分之一，同時區(qū)間縮短率減小了36%；而當初始區(qū)間是[-1,1]時，迭代步數(shù)雖然是0.618法的五分之二，但是區(qū)間縮短率只減小了6%。因此我們可以發(fā)現(xiàn)當初始區(qū)間兩端函數(shù)值相差較大或很大的情況下，比如初始區(qū)間兩端點相差100倍左右時，改進的算法可以較快的減小區(qū)間范圍，以較快的速度收斂到最小值點。

當區(qū)間長度慢慢變小時，0.618法的迭代步數(shù)變化很小，或者幾乎不變，但是相比較而言，改進的算法在區(qū)間長度減小時，不會出現(xiàn)停滯的現(xiàn)象，且迭代步數(shù)還會偶爾成倍減小，因此改進的算法可以顯現(xiàn)出很好的性能。

4 結論

本線搜索算法是單因素實驗設計中最常用的一種方法，其收斂速度直接影響算法的效率。如何利用函數(shù)在搜索區(qū)間的信息，提高算法的收斂速度是相關研究的重點。本文通過利用目標函數(shù)在搜索區(qū)間端點處的函數(shù)值信息，不斷縮小每步迭代區(qū)間，獲得了具有普適性的加速策略，進行的數(shù)值實驗表明本研究所給出的算法能夠加快現(xiàn)有線搜索算法的收斂速度。