高職常用優化算法比較分析

李 輝

（福建水利電力職業技術學院 福建 永安 366000）

最優化問題是在有限或無限種可行方案 （決策）中挑選最優的方案（決策）。隨著高新技術、計算機及信息技術的不斷發展，優化在工農業、國防、交通、金融、能源、通信等眾多領域的應用越來越廣泛。優化方法也得到了長足發展，從傳統的利用梯度信息計算最優值，到現代啟迪式算法計算最優值，優化算法的種類越來越多，解決的問題越來越復雜，在實際問題的解決中發揮的作用也越來越大。

高職學生對優化算法的接觸普遍較少，但是在實際問題的解決中，一些較簡單的優化算法不僅能較好地解決復雜問題，而且可以提高問題的解決效率。筆者擬介紹幾種常用的比較簡單的優化算法，并對其性能進行比較分析。

幾種優化算法的基本思想

對于多元函數而言，最優值一般都會取在梯度為零的點附近。因此，傳統的優化算法就是利用梯度信息來求函數的最優值，常用的方法有最速下降法、牛頓法等。隨著實際問題規模的擴大、復雜程度的增加，很多問題的梯度比較難計算，隨之產生了啟迪算法，如遺傳算法、粒子群算法、禁忌搜索算法、模擬退火算法等。

（一）最速下降算法

最速下降算法是求解無約束優化問題最簡單的方法。利用函數的梯度信息，在其可行域內搜索可行點，使得該點處的梯度接近零，從而得到函數的最優值。該算法的思想是：以負梯度為方向（dk=-▽f（xk））作為搜索方向，按照迭代：xk+1=xk+αkdk尋找最優解。其中αk為搜索步長。

該算法的計算步驟如下：（1）取初始點x0∈Rn，精度 ε〉0，令 k:=0；（2）計算 dk=-▽f（xk），若 dk≤ε，則停，x*=xk，則轉；（3）線性搜索，令xk+1=xk+αkdk，k:=k+1，轉（2）。

（二）阻尼牛頓法

阻尼牛頓法是以二次近似來逼近函數的牛頓法，在該算法中，取下降方向為 dk=-▽2f（xk）-1▽f（xk），即xk+1=xk+αkdk=xk-αk▽2f（xk）-1▽f（xk），當 αk=1 時，該算法稱為牛頓法。

該算法的計算步驟如下：（1）取初始點 x0∈Rn，ε〉0，令 k:=0；（2）計算 gk=▽f（xk），若 gk≤ε，則停：x*=xk，否則，轉；（3）計算 dk=-▽2f（xk）-1▽f（xk）；（4）線性搜索：，轉（2）。

（三）粒子群算法

粒子群算法是一種隨機搜索的啟迪式算法。它將每一個可行解看做空間中的一個粒子，每個粒子代表空間中的一個候選解，解的優劣程度可根據目標函數計算其適應度來判斷。在D維空間中，種群由m個粒子組成，其中第i個粒子位置表示為xi=（xi1，xi2，…，xiD），它的速度為 vi=（vi1，vi2，…，viD），該粒子搜索到的當前個體最優值表示為：pi=（pi1，pi2，…，piD），整個粒子當前的最優值表示為：pg=（pg1，pg2，…，pgD）。 在每一次迭代中，粒子根據個體最優值和整個粒子群的最優值調整速度，由速度來調節粒子的位置，更新候選解。標準粒子群算法迭代公式為：

其中，i=1，2，…，m；d=1，2，…，D；r1和 r2都是服從U（0，1）分布的隨機數；c1，c2為非負常數，通常取值為：c1=c2=2；vid∈[-vmax，vmax]，vmax是由用戶根據實際問題設定的常數，粒子在每一維飛行的速度不能超過算法設定的最大速度vmax。

標準粒子群優化算法的計算步驟如下：（1）在可行域內，對粒子群進行隨機初始化，包括隨機初始位置和速度。（2）計算每個粒子的適應度值。（3）對于每個粒子，將其適應度值與所經歷過最好位置的適應度值進行比較，如果更好，則將其作為粒子的個體歷史最優值，用當前位置更新個體歷史最好位置。（4）對每個粒子，將其歷史最優適應度值與群體內或鄰域內所經歷的最好位置的適應度值進行比較，若更好，則將其作為當前的全局最好位置。 （5）根據式子（1）、（2）對粒子的速度和位置進行更新。（6）若達到終止條件，則停，否則，轉（2）。一般將終止條件設定為一個足夠好的適應值或達到一個預設的最大迭代次數。

（四）禁忌搜索算法

禁忌搜索算法是一種亞啟發式搜索算法，所謂禁忌就是禁止重復前面的工作。為了回避局部鄰域搜索陷入局部最優的主要不足，禁忌搜索算法用一個禁忌表記錄下已經到達過的局部最優點，在下一次的搜索中，利用禁忌表中的信息不再或有選擇地搜索這些點，以此來跳出局部最優點。就好比人的短時記憶，走過的路不再重復或有選擇地重復；同時“遺忘”又使得這些禁止是弱禁止，即在一定的時間之后這些禁止將失效，最終達到全局優化之目的。

禁忌搜索算法的計算步驟如下：（1）給定初始解x0，分配禁忌表長度L，設定初始解為當前的最優解xbest；（2）在初始解鄰域內產生n個測試解（n〉L），將測試解依次與禁忌表中的解比較，若測試解不在禁忌表中，計算其目標函數值，并求出這些解中的最優解，記為當前較優解xc；并將xc存入禁忌表，若禁忌表滿，則按先進先出的原則更新禁忌表；（3）若 f（xc）＜f（xbest），令 xc=xbest；（4）若滿足停止準則，則停，輸出最優解xbest；否則，返回（2）。

幾種算法的比較分析

（一）最速下降算法

該算法是1847年由著名數學家柯西 （Cauchy）給出的。它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發而得到的。它的優點在于操作簡單，所需存儲空間少，對初始點要求較低，在最初階段的搜索速度快，可以很快到達函數極值附近。但在搜索的最后階段，由于步長的影響，算法的搜索路線常呈現“鋸齒狀”，使得算法不能很快達到最優值，而且由于該算法是按照負梯度的方向不斷搜索的，當達到函數的某一極值點后，算法很難跳出極值點，從而會使得找到的點只是某個極值點，并不是函數的整體最優點，即算法容易陷入局部最優。該算法是以一次近似來逼近函數的，因此得到的最優解精度不高。因此該算法常用于比較簡單的、連續的、單極值目標函數，這一類函數用該算法通常會在很短的迭代次數后產生最優點。或者可以在搜索的初始階段使用該算法，并在后期結合另一種算法計算。

（二）阻尼牛頓法

該算法是牛頓法的改進。它以函數的二次逼近為基礎，因此較之最速下降算法，其搜索精度較高。而且對于嚴格凸函數，該算法可以搜索到其全局最優解，且有較快的收斂速度。但是該算法對目標函數要求較高，一般需要具有一階、二階偏導數，同時其海森陣必須正定且非奇異，在每次迭代中，計算量較大，對于較復雜的目標函數而言，搜索速度會受到嚴重影響。因而，此算法適用于一些精度要求較高，目標函數的梯度較簡單的問題，是傳統優化算法中性能較好的一種。

（三）粒子群算法

該算法是由肯尼迪（Kennedy）和埃伯哈特（Eberhart）于1995年提出的。它操作簡單，不需要目標函數的梯度信息，甚至不要求目標函數的連續性，對于復雜函數有很好的優化能力，有較快的收斂速度，且該算法所需參數少，易于實現，是最常用的優化算法之一。通過給定不同的參數值，可以靈活修正算法的搜索速度和收斂精度，且其搜索機制簡單，可以很容易地進行算法改進或者與其他算法結合解決大型復雜問題。目前，該算法已廣泛應用于函數優化、神經網絡訓練、模式分類、模糊系統控制，在其他應用領域也受到廣泛歡迎。但是基本粒子群算法的穩定性和全局搜索能力較差，很多學者從不同方面對基本粒子群算法進行了改進，如馬翠、周先東等人的分層粒子群優化算法，將搜索分為局部和全局同時并行進行；褚國娟、馬春麗等人的基于差分及模擬退火的混合粒子群算法，將模擬退火算法與粒子群算法結合，可以更好地提高算法的全局搜索能力。另外，粒子群算法的理論證明較少，參數對算法性能的影響、算法對不同問題解決能力的差異等問題都是通過實驗檢驗的，理論的證明幾乎沒有，這也是該算法未來研究的方向之一。

（四）禁忌搜索算法

禁忌搜索算法最早由美國工程院院士，科羅拉多大學教授福瑞德·格洛弗（Fred Glover）提出，它是一種亞啟發式算法，它在搜索過程中避免重復工作，禁忌當前較優解，可以很好地跳出局部最優，提高算法的搜索精度。同時，該算法所需參數少，操作簡單，適合求解較復雜的多極值函數最優值。禁忌搜索算法在組合優化、生產調度、機器學習、電路設計和神經網絡等領域取得了很大的成功，近年來又在函數全局優化方面得到較多的研究。但是，該算法對初始解的依賴性較強，初始解的選取會影響到算法的搜索速度甚至精度。同時，該算法更新機制不是很完善，理論證明方面也很欠缺，因而單獨使用時靈活度較差，成功率也較低，通常可以將該算法與其他算法（如粒子群算法）結合，在每次迭代的后期使用禁忌搜索算法，既可保證算法的靈活度，提高其搜索速度，又可提高算法的收斂精度。

綜上所述，前兩種是傳統優化算法，利用梯度信息進行求解，操作簡單，經理論證明，對于連續函數有較好的收斂性，但對于梯度信息較復雜甚至無法求梯度的目標函數而言，這兩種算法較難實現。后兩種算法屬于隨機搜索的啟迪式智能算法，通常是模擬自然界中動物的習性進行優化搜索，算法操作簡單，不需要梯度信息，易于實現，較易與其他算法結合，且有很強的解決大型復雜問題的能力，是目前工程、通信等領域廣泛使用的智能優化算法。但是現代的很多智能優化算法理論研究方面較薄弱，沒有辦法嚴格說明其收斂速度和精度的依賴因素，只能通過大量實驗進行驗證，這也極大地限制了算法的發展。

[1]陳開周.最優化計算方法[M].西安：西安交通大學出版社，2003:53-55.

[2]徐成賢，陳志平，李乃成.近代優化方法[M].北京:科學出版社，2002:85-88.

[3]Kennedy J，Eberhart R C.Particle swarm optimization[J].Proceedings of IEEE international Conference on Neural Networks，1995：1942-1948.

[4]陳冬芳，薛繼偉，張漫.全局最優化算法及其應用[J].大慶石油學院學報，2005（1）:23-25.

[5]馬翠，周先東，楊大地.分層粒子群優化算法[J].計算機工程，2009（20）:194-196.

[6]褚國娟，馬春麗，寧必鋒.基于差分及模擬退火的混合粒子群算法[J].計算機與現代化，2010（5）:19-20.

[7]劉嘉敏，董宗然，馬廣焜.基于禁忌搜索算法求解集裝箱裝載問題[J].沈陽工業大學學報，2009（2）:212-216.

[8]張玉芳，薛青松，熊忠陽.基于禁忌搜索的動態粒子群算法[J].計算機工程與應用，2008（24):56-58.