一種改進的一維搜索指數優化算法

張志彬，金福江，湯儀平

（1.華僑大學信息科學與工程學院，福建廈門361021；2.華僑大學機電及自動化學院，福建廈門361021；3.福建鳳竹紡織科技股份有限公司，福建泉州362200）

一種改進的一維搜索指數優化算法

張志彬1，金福江1，湯儀平2，3

（1.華僑大學信息科學與工程學院，福建廈門361021；2.華僑大學機電及自動化學院，福建廈門361021；3.福建鳳竹紡織科技股份有限公司，福建泉州362200）

在分析黃金分割法基本原理的基礎上，通過改變以指數收斂的區間長度縮短比率得到一種新的一維搜索指數優化算法.實例結果表明：該算法的收斂速度要比黃金分割法的收斂速度要快，同時最優解的區間精度也比黃金分割法的要精確；然而，該算法只適用于單峰函數局部最優解的求取.

一維搜索；黃金分割法；加速收斂；指數優化算法

一維搜索中的黃金分割法［1－4］是在一元單峰函數所定義的區間上，按黃金分割率對稱取得一系列黃金分割點，然后對分割點所對應的函數值進行計算和比較，利用區間縮小的序列消去原理，最終確定函數的最優解和對應的最優值.最后，穩定地收斂到一個局部極小點.然而，由于區間的長度縮短比率為常數，故其收斂速度較慢.本文根據黃金分割法的基本原理，提出一種改進的一維搜索指數優化算法.

1 指數優化算法

指數優化算法與黃金分割法同樣也只適用于單峰函數.在計算過程中，第1次迭代需要計算2個試探點，以后每次迭代只需新算一點，另一點取自上次迭代［1］.其與黃金分割法的主要區別在于區間的長度縮短比率不是以常數進行收斂，而是以計算兩次區間差值的指數值進行收斂，由于指數函數的引用，因此構造出一個具有更加光滑的收斂趨勢并且更快收斂速度的指數優化算法.

指數優化算法有如下5個主要步驟.

步驟1 給定初始區間［a1，b1］及精度要求ε＞0，計算試探點λ1，μ1，有

然后，計算函數值f（λ1），f（μ1），置y1＝b1－a1，e1＝0，并令k＝1.

步驟2 若bk－ak＜ε，停止計算；否則當f（λ1）＞f（μ1）時，轉步驟3，當f（λ1）≤f（μ1）時，轉步驟4.

步驟3 置ak＋1＝λk，bk＋1＝bk，λk＋1＝μk，yk＋1＝bk＋1－ak＋1，ek＋1＝yk＋1－yk，并判斷ek＋1大小.如果ek＋1＜0.694，有

否則，有

計算函數值f（μk＋1），轉步驟5.否則，有λk＋1＝ak＋1＋exp（－ek＋1）（bk＋1－ak＋1）.然后，計算函數值f（μk＋1），轉步驟5.

步驟5 置k＝k＋1，返回步驟2.

2 指數系數確定及靈敏度分析

由式（1），（3）可知：指數系數的確定相直接關系到區間收斂的速度.為了確定exp（－Kek＋1）中系數K的大小，可通過MATLAB畫出K在區間［0.1，4］，遞增量為0.1的一簇負指數曲線.單峰函數的性質區間差呈遞減趨勢，且當接近最優值的迭代ek基本取于［0，1］區間內，故為了加快收斂速度，取在區間［0，1］值變化比較大的曲線，通過對指數曲線簇進行觀察，最終將系數K的取值確定在區間［1，3］之間.對于實例min f（x）＝2x2－x－1，初始區間［a1，b1］＝［－1，1］，精度要求ε≤0.16，對系數K的收斂速度及最優區間的靈敏度進行分析，結果如表1所示.

表1依次計算了K取不同值情況下最優區間和最優解，并最終確定當K＝1.9時為最優，此時最優區間為［0.203 138 02，0.299 143 52］，最優解為0.250 11.據此確定算法中指數系數，并通過以下實例驗證，該方法對其他目標函數也是同樣適用的.

表1 系數的靈敏度分析Tab.1 Sensitivity analysis of Index coefficient

3 算法收斂性證明

定理1［1］設f是區間［a，b］上的單峰函數，x（1），x（2）∈［a，b］且x（1）＜x（2）.如果f（x（1））≤f（x（2）），則對每個x∈［x（2），b］，有f（x）＞f（x（1））；如果f（x（1））＞f（x（2）），則對每個x∈［a，x（1）］，有f（x）≥f（x（2））.

證明 若f（x（1））≤f（x（2）），設極小點為ˉx.若x（1），x（2）在ˉx的同一側，根據單峰函數的定義，只有在ˉx的右側，而由于x（1）＜x（2），x∈［x（2），b］，有x（1）＜x（2）≤x，故根據單峰函數定義有f（x）≥f（x（1））；若x（1），x（2）在ˉx兩側，因為x∈［x（2），b］，則x與x（2）同側，故根據單峰函數定義可知f（x）＞f（x（1）），由于f（x（1））≤f（x（2）），則可以推出對每一個x∈［x（2），b］，有f（x）＞f（x（1））.

對于f（x（1））＞f（x（2））情況，同理可證明對每一個x∈［a，x（1）］，有f（x）＞f（x（1））.

定理2 設目標函數f（x）為單峰函數，x∈［a，b］?R1，區間縮小的相對精度為ε（ε＞0），經過第k次計算所得到的新的搜索區間為［ak，bk］，記Δk＝bk－ak，則有limΔk＝lim bk－ak≤ε，并且極小點x0在區間［ak，bk］內.

4 實例驗證

為了驗證指數優化算法的可行性、精度及運算速率，將指數優化法與黃金分割法轉化成MATLAB程序加以驗證，結果如表2所示.表2中：目標函數為f（x）；實例1為min f（x）＝2x2－x－1，初始區間［a1，b1］＝［－1，1］，精度要求ε≤0.16；實例2為min f（x）＝e－x＋x2，初始區間［a1，b1］＝［－1，1］，精度要求ε≤0.2；程序的運算時間為運行30次的平均值.

表2 指數優化算法和黃金分割法的比較Tab.2 Comparison between exponential optimization method and golden section method

由表2可知：對于實例1，指數優化算法的收斂速度要比黃金分割法的收斂速度要快，同時最優解的區間精度也比黃金分割法的要精確；對于實例2，在最優解區間相近的情況下，指數收斂法的收斂速度依然比黃金分割法的要快.

5 結束語

以黃金分割法的基本原理為基礎，提出了一種用于一維搜索的改進的算法——指數優化算法.該方法結合黃金分割法并對其改進，繼承了黃金分割法的計算簡單的優點，并改善了其收斂速度慢的不足，從而取得了較好的效果.但本算法依然只適用于單峰函數局部最優解的求取，下一步的工作是克服此算法的缺陷，并將算法推廣到全局的最優化領域中.

［1］ 陳寶林.最優化理論與算法［M］.北京：清華大學出版社，2005：256－263.

［2］ 徐望寶，陳雪波，李小華，等.快速穩定收斂的一維搜索算法——水平割線法［J］.鞍山科技大學學報，2006，30（2）：356－359.

［3］ 馬昌鳳.最優化方法及其Matlab程序設計［M］.北京：科學出版社，2008：18－21.

［4］ 王曉陵，陸軍.最優化方法與最優控制［M］.哈爾濱：哈爾濱工程大學出版社，2006：10－16.

An Improved Exponential Optimization Algorithm of One－Dimensional Search

ZHANG Zhi－bin1，JIN Fu－jiang1，TANG Yi－ping2，3
（1.College of Information Science and Engineering，Huaqiao University，Xiamen 361021，China；2.College of Mechanical Engineering and Automation，Huaqiao University，Xiamen 361021，China；3.Fujian Fengzhu Textile Science ＆Technology Co.，Ltd.，Quanzhou 362200，China）

Based on the analysis of the basic principle of the golden section method，a new method called exponential optimization algorithm for one－dimensional search was presented by changing the interval length ratio of the exponential convergence.The results show that the method has faster convergence rate than that of the golden section method and the precision interval of the optimal solutions are also better than that of the golden section method.However，this algorithm applies only to calculate the local optimal solution of one－humped function.

one dimension search；golden section method；convergence acceleration；exponential optimization algorithm

O 232

A

（責任編輯：黃曉楠 英文審校：吳逢鐵）

1000－5013（2012）05－0503－03

2011－11－22

金福江（1965－），男，教授，主要從事復雜系統建模、仿真與控制的研究.E－mail：jinfujiang＠163.com.

福建省產學研重大科研基金資助項目（2011H6019）