李 輝

（福建水利電力職業(yè)技術(shù)學(xué)院 福建 永安 366000）

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

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

幾種優(yōu)化算法的基本思想

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

（一）最速下降算法

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

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

（二）阻尼牛頓法

阻尼牛頓法是以二次近似來逼近函數(shù)的牛頓法，在該算法中，取下降方向?yàn)?dk=-▽2f（xk）-1▽f（xk），即xk+1=xk+αkdk=xk-αk▽2f（xk）-1▽f（xk），當(dāng) αk=1 時(shí)，該算法稱為牛頓法。

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

（三）粒子群算法

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

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

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

（四）禁忌搜索算法

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

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

幾種算法的比較分析

（一）最速下降算法

該算法是1847年由著名數(shù)學(xué)家柯西 （Cauchy）給出的。它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到的。它的優(yōu)點(diǎn)在于操作簡單，所需存儲空間少，對初始點(diǎn)要求較低，在最初階段的搜索速度快，可以很快到達(dá)函數(shù)極值附近。但在搜索的最后階段，由于步長的影響，算法的搜索路線常呈現(xiàn)“鋸齒狀”，使得算法不能很快達(dá)到最優(yōu)值，而且由于該算法是按照負(fù)梯度的方向不斷搜索的，當(dāng)達(dá)到函數(shù)的某一極值點(diǎn)后，算法很難跳出極值點(diǎn)，從而會使得找到的點(diǎn)只是某個(gè)極值點(diǎn)，并不是函數(shù)的整體最優(yōu)點(diǎn)，即算法容易陷入局部最優(yōu)。該算法是以一次近似來逼近函數(shù)的，因此得到的最優(yōu)解精度不高。因此該算法常用于比較簡單的、連續(xù)的、單極值目標(biāo)函數(shù)，這一類函數(shù)用該算法通常會在很短的迭代次數(shù)后產(chǎn)生最優(yōu)點(diǎn)?；蛘呖梢栽谒阉鞯某跏茧A段使用該算法，并在后期結(jié)合另一種算法計(jì)算。

（二）阻尼牛頓法

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

（三）粒子群算法

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

（四）禁忌搜索算法

禁忌搜索算法最早由美國工程院院士，科羅拉多大學(xué)教授福瑞德·格洛弗（Fred Glover）提出，它是一種亞啟發(fā)式算法，它在搜索過程中避免重復(fù)工作，禁忌當(dāng)前較優(yōu)解，可以很好地跳出局部最優(yōu)，提高算法的搜索精度。同時(shí)，該算法所需參數(shù)少，操作簡單，適合求解較復(fù)雜的多極值函數(shù)最優(yōu)值。禁忌搜索算法在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計(jì)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了很大的成功，近年來又在函數(shù)全局優(yōu)化方面得到較多的研究。但是，該算法對初始解的依賴性較強(qiáng)，初始解的選取會影響到算法的搜索速度甚至精度。同時(shí)，該算法更新機(jī)制不是很完善，理論證明方面也很欠缺，因而單獨(dú)使用時(shí)靈活度較差，成功率也較低，通?？梢詫⒃撍惴ㄅc其他算法（如粒子群算法）結(jié)合，在每次迭代的后期使用禁忌搜索算法，既可保證算法的靈活度，提高其搜索速度，又可提高算法的收斂精度。

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

[1]陳開周.最優(yōu)化計(jì)算方法[M].西安：西安交通大學(xué)出版社，2003:53-55.

[2]徐成賢，陳志平，李乃成.近代優(yōu)化方法[M].北京:科學(xué)出版社，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]陳冬芳，薛繼偉，張漫.全局最優(yōu)化算法及其應(yīng)用[J].大慶石油學(xué)院學(xué)報(bào)，2005（1）:23-25.

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

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

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

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