基于模擬退火的粒子群算法在函數優化中的應用*

李淑香

(重慶郵電大學移通學院 數理教學部，重慶 401520)

近年來，優化問題在很多行業越來越受到關注和重視，同時也發揮著重要作用.目前，優化對象變得越來越復雜，傳統優化方法在解決這些問題時顯得很困難，甚至無能為力.因此，越來越多的研究人員將思路轉變到群智能算法中，從自然界中生物的群體行為得到啟發，提出將新型智能算法(如遺傳算法、細菌算法，狼群算法和粒子群算法等[1-2])應用在函數優化中，并得到了一定效果.上述算法在解決函數優化問題時表現出強大的能力和優勢，但仍有不足，因此，人們仍在繼續探索研究新的啟發式智能優化算法或混合算法等.

粒子群算法被廣泛應用的原因是相較于其他群智能算法，粒子群算法具有結構簡單，參數易調整，優化結果明顯等優點.當然，粒子群搜索算法也存在一些不足，如PSO算法易進入早熟和局部最優等[3].然而由于PSO算法在很多領域內總體上都表現出了強大能力，其理論和應用方面受到國內外許多學者的重視和進一步研究.文獻[4]采用新的粒子編碼方式與位置更新方式，提高了標準粒子群算法的收斂速度；文獻[5]更改了傳統慣性權重，依據粒子本身的進化經驗，實現自適應調整，提高了算法的多樣性和算法的尋優能力；文獻[6]有效改變了粒子數目和算法中的速度位移方程，使得改進算法的收斂速度和收斂精度都得到了明顯改善和提高.隨著多種群智能算法的不斷發展，由兩種或多種算法的相結合達到相互取長補短的混合算法得到廣泛應用.文獻[7]將量子行為思想引入到PSO系統中，通過改變粒子更新方式，改進了PSO算法.改進PSO算法雖能在一定程度上改善標準粒子群算法的不足，但效果仍不理想，為了能夠進一步提高PSO算法的收斂精度，本文在對粒子群算法和模擬退火算法進行了進一步研究后，提出了基于模擬退火的粒子群算法，該算法具有較強的全局搜索能力，在接受新解時既可以接受好解又可以接受差解.將本文算法應用到標準粒子群算法中，可以保證種群的多樣性，有利于跳出局部最優解，提高算法的收斂速度和尋優精度，并避免“早熟”現象的發生.

1 基本粒子群算法

粒子群(PSO)算法是應用較廣的一種算法，最早是在1995年由Kennedy和Eberhart提出來的，該算法是一種對自然界鳥群、魚群等在群體生活中的捕食與移動過程的一種近似模擬[2].粒子群算法通過不斷迭代來搜尋目標函數的最優值，初始化一組隨機解，而每個粒子都可看成是問題的潛在解.鳥群能否成功捕獲到食物不僅與過去積累的經驗和認知有關，同時還和群體中的其它個體之間存在聯系[8].在粒子群算法中粒子在解空間追隨最優粒子進行搜索，在搜索過程中速度和位置信息是在不斷調整改變的，其主要依據是粒子過去積累的經驗和群體中的其它個體信息等.在PSO算法初始化過程中隨機產生粒子群的種群，其中每個粒子都是目標函數的解，為了尋找函數的最優解，每個粒子會根據個體歷史最優位置和種群的最優位置來多次調整自身的速度和位置更新策略，并經多次迭代尋優最終找到問題的最優解.

在PSO算法中，每個粒子都可以看作多維搜索空間中優化問題的解.假設在一個D維搜索空間中某群體中共有n個粒子，第i個粒子在D維搜索空間中的位置向量Xi=(xi1，xi2，…，xiD)，每個粒子的位置代表一個潛在解，代入目標函數就可以計算其適應度值.第i個粒子的速度向量為Vi=(vi1，vi2，…，viD)，利用目標函數求解其適應度值，確定個體最優位置向量Pi=(pi1，pi2，…，piD)與當前情況下群體所經歷的歷史最優位置向量Pg=(pg1，pg2，…，pgD).粒子群算法對粒子操作時涉及的更新公式[9]為

vij(t+1)=ωvij(t)+c1r1(pij(t)-xij(t))+

c2r2(pgj(t)-xij(t))

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

式中：c1和c2為加速常數，分別調節粒子向自身最優位置與向全局最優位置飛行的步長，通常c1+c2≤4；r1和r2為兩個相互獨立的隨機函數；ω為慣性常數，可以平衡全局與局部搜索能力；xij(t)為第i個粒子在t時刻的第j維位置分量；vij(t)為第i個粒子在t時刻的第j維速度分量；pij(t)為第i個粒子的第j維分量更新前的歷史最優位置；pgj(t)為t時刻種群所經歷的最優位置.

式(1)由三項組成：第一項為粒子的當前速度，即現在狀態部分；第二項為粒子從自身出發的自我認知部分；第三項為粒子在整個群體中與其它粒子間進行協調的社會部分.通過公式(1)、(2)不斷更新，粒子不斷向全局最優解靠攏，尋找搜索空間中的最佳值.基本粒子群算法需要用戶確定的參數并不多，而且操作簡單，故使用比較方便.但是它的缺點是易陷入局部極值點，搜索精度不高，因此，人們提出了許多改進算法，從而在一定程度上改進了基本粒子群算法的性能[10].

2 模擬退火算法

模擬退火(SA)算法不僅是一種統計優化方法，還是一種全局優化算法.該算法從物理退火原理得到啟發，最早由Metropolis提出.當固體物質不斷升溫時，隨著溫度的增加，物質內部的粒子變得活躍起來并處于不穩定狀態；與之相反，當溫度不斷降低時，物質內部粒子的活躍度又在不斷下降，從不穩定狀態變成穩定狀態.依照固體物質退火過程和組合優化問題的共性特點，將模擬退火算法應用于各種組合優化問題中.

SA算法在對目標問題進行迭代優化尋找最優解時，首先需要確定一個初始溫度，并在問題解空間上生成一個初始狀態作為初始解，然后對當前初始狀態進行干擾，模擬固體內部粒子在一定溫度下的狀態轉移過程.之后評估由干擾得出的新解，將新解和當前解進行比較并根據Metropolis準則進行替換.SA算法以概率1來接受最優解，以某種概率來接受較差解.正因為具有這種能力，所以該算法不易陷入局部最優陷阱，從而可以跳出局部最優解.Metropolis準則定義了物體在某一溫度T下從狀態i轉移到狀態j的內能概率，其表達式為

(3)

式中：E(i)和E(j)分別為固體在狀態i和j下的內能；ΔE為內能增量；K為波爾茲曼常數.

由式(3)可知，當E(j)

3 模擬退火粒子群算法

粒子群算法在函數優化過程中主要依賴粒子之間的信息不斷更新粒子的位置和速度，使其不斷向最優解方向靠攏.PSO算法存在易早熟，易陷入局部最優，后期收斂速度較慢，搜索精度較差等缺點.模擬退火算法具有很強的全局搜索能力，存在接受較差解的可能，在運算時遇到較差解能夠以一定的概率接受，從而可以跳出局部最優解陷阱，收斂于全局最優解區域，擁有較高的搜索精度.但在算法運算時，因其需要非常高的退火溫度，故收斂速度十分緩慢.

PSO算法和SA算法各具優缺點，結合SA算法中的Metropolis準則并與PSO算法相互融合形成一種模擬退火粒子群混合優化(SAPSO)算法.該混合算法以基本粒子群算法運算流程作為主體流程，把模擬退火機制引入其中并實現取長補短，明顯克服PSO算法早熟收斂的弊端，改善SA算法收斂速度慢的缺點，從而提升了算法的整體性能.模擬退火粒子群算法流程如圖1所示.

圖1 模擬退火粒子群算法流程Fig.1 Flow chart of SAPSO algorithm

利用模擬退火粒子群算法進行函數優化時的具體步驟為：

1)對粒子群里的相關參數進行初始化，如種群、迭代次數、粒子維度、粒子速度和位置等，并計算初始粒子群的適應度及相關參數.

2)模擬退火初始化過程，設置初始溫度，生成初始解S，求出評價函數C(S)，并令C(S)為全局最優解.

3)生成新解S′.

4)按照式(1)、(2)更新粒子的速度和位置，并計算適應度值.

5)求得C(S′)=min{f(xi)}，ΔC=C(S′)-C(S)，其中，f(xi)為最小適應度值.若ΔC<0或exp(-ΔC/T)>rand(0，1)，C(S)=C(S′)，S=S′，并接受由S′所更新的速度和位置；否則將拒絕S′的值，采用當前時刻值來更新速度和位置，并計算適應度值.

6)根據適應度值來更新全局最優解和局部最優解.

7)判斷是否滿足結束條件，若滿足，輸出最優值；若不滿足，轉到步驟3).

4 仿真實驗

4.1 測試函數

為了檢驗SAPSO混合算法的優化效果，選取了PSO和GA算法進行對比實驗，并引入5個非線性函數進行測試.5個測試函數分別為Sphere、Rosenbrock、Ackley、Griewank和Rastrigrin函數.除了Rosenbrock函數在全局最優解[1，1，…，1]處具有極小值外，其余測試函數均在全局最優解[0，0，…，0]處具有極小值，且極小值均為0，函數最優值也均為0.測試函數具體表達式如表1所示.

表1 測試函數Tab.1 Test functions

4.2 結果與分析

利用SAPSO、PSO和GA算法對上述5個測試函數進行數值模擬來驗證本文算法可行性.主要參數設置為：種群規模40；最大迭代次數1 000；函數維度30.PSO算法中慣性權重初始最大值為0.9，慣性權重初始最小值為0.4；c1=1.49，c2=1.49.退火算法中K=0.7，初始溫度為10 000 ℃；遺傳算法中交叉概率為0.7，變異概率為0.3.

為了驗證模擬退火粒子群混合算法的優越性和可行性，通過對表1中的5個非線性測試函數進行對比分析，得出Sphere、Griewank、Rosenbrock、Ackley和Rastrigrin函數的優化曲線，結果如圖2～6所示.

圖2 Sphere函數優化曲線Fig.2 Optimization curves of Sphere function

由圖2～6可見，與粒子群算法和遺傳算法相比，基于模擬退火的粒子群混合算法在高維函數優化中具有明顯優勢，混合算法易跳出局部最優解，避免“早熟”現象且具有收斂速度快等優點，克服了傳統PSO算法和GA算法中出現的不足和缺點.

圖3 Griewank函數優化曲線Fig.3 Optimization curves of Griewank function

圖4 Rosenbrock函數優化曲線Fig.4 Optimization curves of Rosenbrock function

圖5 Ackley函數優化曲線Fig.5 Optimization curves of Ackley function

圖6 Rastrigrin函數優化曲線Fig.6 Optimization curves of Rastrigrin function

5 結 論

針對傳統PSO算法易出現局部最優等缺點，在標準粒子群算法的基礎上引進模擬退火算法思想，提出了模擬退火粒子群混合算法.該混合算法利用模擬退火算法的概率突變能力，不僅能接受最優解，還能以某種概率來接受較差解.因此，混合算法不易陷入局部最優的陷阱，從而具有跳出局部最優解的能力.該混合算法不僅基本保持了粒子群優化算法簡單易實現的特點，而且能夠增強粒子群算法的全局尋優能力，加快了算法的進化速度，提高了算法的收斂精度.利用5個測試函數對模擬退火粒子群混合算法進行測試后發現，與PSO和GA算法相比，本文算法具有較快的收斂性和較好的穩定性，從而驗證了本文算法的有效性.