一種新的基于正弦自適應權重的模擬退火粒子群優化算法

甘 地

（中南大學機電工程學院，湖南 長沙 410000）

粒子群算法[1]是模擬群體智能所建立起來的一種算法，最早在1995 年由美國的Eberhart 和Kennedy 兩人提出。由于它運行邏輯簡單、需要調試的參數少、容易實現，因此受到大量學者的研究與應用。如今，在NP 問題求解、圖像處理[2]、人工神經網絡建模[3]和車輛路徑優化[4]等領域時常可以見到對粒子群算法的使用。然而粒子群優化算法也存有一些缺點，如，易陷入局部最優解，運行末期收斂速度減緩、收斂精度低等。為改善這些缺陷，學者們進行了大量的研究。文獻[5]將研究重心放置在粒子群算法的慣性權重上，提出一種按正弦變化慣性權重的粒子群優化算法。文獻[6]提出對慣性權重的自適應變化方案，即自適應權重的粒子群算法。文獻[7]在研究了細菌覓食算法（BFO）的特點后，將BFO 算法中的趨化和遷徙算子引入粒子群算法，提出了PSO-BFO 混合算法。文獻[8]將模擬退火的思想融入粒子群算法中，提出了基于模擬退火的粒子群算法。上述文獻通過改善權重系數，或將粒子群算法與其他算法相結合，或多或少地對算法性能進行了加強。

本文在分析了粒子群算法的優缺點，以及模擬退火算法的運算原理后，將模擬退火的思想引入粒子群算法中，提出基于模擬退火的粒子群算法。基于慣性權重對算法運行效果的重要作用，提出一種正弦自適應變化的慣性權重。該算法結合了粒子群優化算法的全局搜索能力模擬退火算法的一定概率跳出局部最優解的優點以及正弦自適應變化的慣性權重，改善了粒子群算法易陷入局部最優解的問題，增強了運算末期的收斂速度和收斂精度。

1 標準粒子群算法

Eberhart 博士和Kennedy 博士基于對鳥群覓食行為的學習和模擬，創建了粒子群優化算法。該算法的核心思想是在問題求解空間中，通過個體間信息互相流通，使得群體的運動逐漸從無序演化為有序，從而求解出最優值。在運算前，粒子群算法會初始化若干個粒子，每個粒子都代表目標函數的一個解，具有位置向量和速度向量。將粒子的位置向量帶入目標函數，求得的值被稱為粒子的適應度值。在每次迭代中，群體中粒子位置的更新會受到自身歷史最優解和群體當前最優解的影響，有朝向這兩個最優解移動的趨勢，從而確定粒子在下一次迭代時的位置和速度如何改變，并更新自身歷史最優解以及群體當前最優解。最終通過不斷地迭代，尋得目標函數的最優值。

假設在一個D 維空間中有N 個粒子，粒子i 在t 時刻的位置為xi（t）=[xi1（t），xi2（t），...xiD（t）]，飛行速度為vi（t）=[vi1（t），vi2（t），...viD（t）]。將粒子i 的位置xi帶入目標函數得到適應度值，對比該粒子歷史最佳適應度值，得到該粒子從迭代運算以來的歷史最優解，記為pi=（pi1，pi2，…piD）。比較空間中所有粒子的個體最優解，取最小的那個粒子的位置作為整個粒子群迄今為止的群體最優解，記為pg=（pg1，pg2，...pgD）。粒子群算法對粒子速度和位置的更新采用以下公式：

式中：i=1，2，3...N；d=1，2，3...D；ω 為慣性權重因子；C1和C2為學習因子，也稱加速因子，一般取負數；r1和r2為兩個介于[0，1]的隨機數；

上式中，公式1 為速度更新公式，公式2 為位置更新公式。其中速度更新公式分為3 個部分，第1 部分是慣性部分，粒子受慣性影響，會向著粒子上一時刻的速度方向移動；第2 部分是自我認知部分，由于受到自身歷史最優位置的影響，粒子有回到該位置的傾向；第3 部分是社會認知部分，粒子處在種群中，受到當前最優粒子的吸引，有去到當前最優粒子位置的趨勢。種群中的粒子通過公式1 和2 進行更新，經過多次迭代，逐漸向全局最優解靠近，最終在粒子空間中搜索到函數最優解。

2 模擬退火算法

1953 年，N.Metropolis 等人提出模擬退火算法，隨后S.Kirkpatrick 等人在1983 年首次將其引入組合優化問題的求解之中。由于一般組合優化問題類似于物理中固體的退火過程，從而以此為出發點引出該算法。算法起初給定一個較高的溫度T0，隨機生成一個初始解，然后采用Monte-Carlo 迭代求解策略不斷產生新解，利用Metropolis 準則有一定概率接收較差的解的方法，判斷是否用產生的新解代替上一代的舊解，并在迭代過程中不斷降低退火溫度，最終得到問題的最優解。Metropolis 準則定義了在某個溫度T 下物體從狀態i 轉移到狀態j 的能量概率：

式中：Ei和Ej分別為固體在狀態i 和j 下的內能；K 為玻爾茲曼常數。

全局搜索算法一般都會有陷入局部最優解的問題的存在，而模擬退火算法采用Metropolis 準則，使得算法在搜索運行過程中有接收較差解可能性，從而有利于算法跳出局部最優解，克服該問題。然而，模擬退火算法收斂速度慢、參數調整困難等缺點，使其應用并不普遍。

3 基于模擬退火的粒子群算法

3.1 正弦自適應權重

慣性權重是粒子群算法中需要調節的重要參數。慣性權重值越大，粒子在更新過程中的搜索步長越大，全局搜索能力越強；反之，粒子的局部搜索能力越強。因此為提高粒子的搜索能力，使用正弦自適應權重的策略如下：

式中，wmax和wmin為慣性權重的最大值與最小值；f 為粒子的當前適應度值；favg為當前全部粒子的平均適應度值；fmin為當前全部粒子適應度值的最小值。

正弦變化的慣性權重[5]讓算法在運算初期能夠有較小的權重值，粒子具有較強的局部搜索能力，使得粒子獲得個體最優解。在算法運行的中期，隨著正弦函數的變化特性，權重值慢慢變大，粒子開始進行全局最優解的搜索。而在算法運行的后期，慣性權重又慢慢變小，粒子進行細致的局部搜索，尋找該區域的最優解，及全局最優解。自適應變化是指在每一次迭代過程中，以每個粒子的適應度值和所有粒子的平均適應度值的大小做判斷，決定該粒子的權重該如何變化的方式。引入正弦自適應權重策略，有利于粒子在局部和全局空間中動態的搜索。

3.2 算法流程

由于粒子群算法存在易陷入局部最優解的問題，而模擬退火算法具有一定概率接收較差解的特性，因此將其與粒子群算法進行融合，提出基于正弦自適應權重的模擬退火粒子群算法，該算法融合方式有利于改善粒子群算法的全局搜索能力。采用正弦自適應權重策略，提高收斂速度和精度。該算法基本流程如下：

（1）設置種群大小N、粒子維度D，初始化粒子的速度和位置；

（2）計算每個粒子的適應度值fitness（xt），并將每個粒子的個體最優解存儲在pi中，所有粒子中的全局最優解存儲在pg中；

（3）設置初始溫度T0=pg/ln5；

（4）根據式（4）對慣性權重進行更新；

（5）依據公式1 和2 對粒子進行更新，并計算適應度值fitness（xt+1）；

（6）采用模擬退火算法的Metropolis 機制，若fitness（xt+1）fitness（pi），但exp（（fitness（pi）-fitness（xt+1））/Tt）>random，其中random 為0～1 之間的隨機數，則也接受xt+1作為粒子新的個體最優解pi。同理更新生成種群的全局最優解pg；

（7）進行退溫操作Tt+1=0.9*Tt；

（8）判斷是否滿足終止條件，如果滿足則輸出pg；否則，轉到第4 步。

4 仿真實驗

為驗證上述基于正弦自適應權重的模擬退火粒子群算法（SASAPSO）的性能，采用文獻[1]的4 個基準函數對其進行測試，并與標準粒子群算法（PSO）、一種改進的粒子群算法[9]（SAPSO）和基于自適應權重的粒子群算法[6]（AWPSO）進行仿真實驗比較。分別利用這4 種算法對每個基準函數進行50 次最優值求解，通過實驗仿真得到4 種算法下各個基準函數的平均適應度值與迭代次數的關系。

4 個基準函數如下。

其仿真結果如圖1、圖2、圖3、圖4 所示。

圖1 Griewank 函數的迭代曲線

圖2 Rastringin 函數的迭代曲線

圖3 Sphere 函數的迭代曲線

圖4 Schaffer 函數的迭代曲線

由圖示可以看出，在Griewank 函數的迭代曲線中，SASAPSO 算法收斂到最優值的迭代次數為20 次，收斂的迭代次數略大于AW-PSO 算法，但SASAPSO 算法的收斂精度是4 個算法中最高的；在Rastringin 函數的迭代曲線中，SASAPSO 算法收斂到最優值的迭代次數為100次，是4 個算法中最少的，并且收斂精度最高；在Sphere函數的迭代曲線中，4 個算法的收斂精度相當，但SASAPSO 算法收斂到最優值的迭代次數為18 次，是4 個算法中最少的；在Schaffer 函數的迭代曲線中，AW-PSO 算法和SASAPSO 算法收斂到最優值的迭代次數同為200次，但SASAPSO 算法的收斂精度明顯高于AW-PSO 算法。因此，綜合4 個算法在4 個測試函數下的仿真結果，SASAPSO 算法的收斂速度和收斂精度是4 個算法中最高的。

5 結論

本文提出的基于模擬退火的粒子群算法（SASAPSO），以粒子群算法為主體框架，為改善粒子群算法易陷入局部最優解的問題，引入模擬退火機制，增強了粒子群算法的全局搜索能力。采用正弦自適應慣性權重的策略，有效地提高了算法的收斂速度和收斂精度。在4 種基準函數的仿真測試下，與他人提出的3 種算法進行對比。仿真結果表明，SASAPSO 算法的收斂速度和收斂精度更高。