一種新的基于模擬退火的粒子群算法

趙乃剛

摘要：鑒于標準粒子群優化算法易陷入局部最優、收斂精度低，我們提出了一種改進的基于模擬退火的粒子群算法（NPSO）。將模擬退火算法的思想引入粒子群算法中，并對更新公式進行簡化；提出了一種自適應隨機慣性權重，實現了自適應平衡局部搜索和全局搜索的能力；提出了“優勝劣汰”的更新機制，加快了算法的收斂速度。與其它幾種粒子群算法在4個基準測試函數上的實驗比較，實驗研究表明，NPSO算法的性能很好。

關鍵詞：粒子群優化算法；慣性權重；優勝劣汰

中圖分類號：TP18

文獻標識碼：A

DOI： 10.3969/j.is sn.1003-6970.2015.07.001

0 引言

粒子群算法（particle swarm optimizer）是1995年由美國的Kennedy博士和Eberhart博士首次提出的一種基于群智能的優化技術。盡管它與別的進化計算技術有很多相似處，但標準的粒子群優化算法并沒有用到交叉、變異等進化算子。由于粒子群算法原理簡單、需要調節的參數少、實現容易，如今已經受到了海內外學者和學術界的廣泛關注，并對它進行了許多方面的改進。而且它已經在軌道電路補償電容故障診斷、求解整數和混合整數約束優化問題、人臉識別、車牌定位、機位分配等許多領域得到了廣泛應用。然而標準粒子群算法也存在如下缺點：尋找到的最優位置可能是局部最優位置而不是全局最優位置；參數的選擇存在很大的不確定性；算法尋優初期收斂速度快而尋優后期收斂速度變慢。鑒于粒子群算法的這些缺點，很多學者對粒子群算法做了大量的改進。文獻中提出了慣性權重因子并將它引入粒子群算法中，提高了算法的收斂速度和收斂精度；文獻在分析了不確定性參數對算法影響的基礎上，提出了基于維數選擇策略的粒子群算法，并通過數值實驗證明了它們有關隨機參數的分析是正確可行的。文獻分析了慣性權重、學習因子對粒子群算法的影響，構造了隨機慣性權重，并在算法中引入了平均個體最優位置，提高了算法的性能；文獻提出了基于模擬退火的粒子群算法，有效地對粒子群算法和模擬退火算法兩種算法的優點分析并進行了融合，有利的提高了算法的全局尋優性能。

我們在分析了慣性權重的取值對粒子群算法影響的基礎之上，將模擬退火算法的思想引入粒子群算法中，并引入了自然界“優勝劣汰”的更新機制。新算法結合了粒子群算法容易實現、全局尋優能力強及模擬退火算法具有概率突跳能力的優點，使得算法有效地降低了在搜索過程中陷入局部最優的可能性。

1 基本粒子群算法

粒子群算法是一種基于群體智能的具有全局搜索能力的優化方法。它通過粒子群體中不同微粒之間的相互合作和競爭來實現在尋優空間中的搜索過程以找到問題的最優解。系統首先隨機的初始化一組微粒，然后微粒在搜索空間中跟隨兩個極值位置來進行搜索。假設粒子群的搜索空間為m維，微粒的個數為popsize，第i個微粒在t時刻的飛行速度和在搜索空間中的位置分別為

，微粒在f時刻的個體極值位置和群體極值位置分別為

其中ω國為慣性權重；C₁，c₂是學習因子，一般取非負數；r₁，r₂是介于[0，1]之間的隨機數。對于算法的迭代終止條件，我們一般會根據不同的具體問題而設定不同的值。通常將上面描述的帶有慣性權重系數的粒子群算法稱為標準的粒子群算法。

2 模擬退火算法

模擬退火算法是模擬金屬在高溫狀態下緩緩降溫的熱學過程而提出的，如今已經大量的應用于許多現實問題中。模擬退火算法首先給定一個初始溫度，隨機選擇一個初始狀態并對它的目標函數值進行評估；對當前所處的狀態微擾，計算新狀態的目標函數值；以100%的概率接收較好的值，而以事先給定的概率P接受較差的值，直到算法冷卻。模擬退火算法在空間搜索時擁有按照一定概率進行突跳的能力，在整個退火的過程中不但能接受較好的值，而且可以按照事先給定的概率P接收較差的值，能防止算法陷入局部最優。

3 改進的粒子群算法

3.1 簡化的粒子群算法

標準粒子群算法同時具有速度更新和位置更新兩項，使得粒子的搜索方向和步長的大小存在不確定性，導致算法的進化后期收斂速度很慢，搜索精度降低。并且，模擬退火算法在尋找最優位置的過程中擁有按照給定概率進行突跳的能力，可以有效的降低算法陷入局部最優位置的概率。鑒于上述分析，為了盡量避免粒子群算法所擁有的缺點并同時結合模擬退火算法所擁有的優點，我們對標準粒子群算法省略了速度更新部分，使得二階迭代方程降為一階，并結合模擬退火算法對位置更新部分進行了改進，如下：

其中，T（pbest_i）表示在模擬退火中當前溫度狀態下第i個粒子的適配值，zbest是采用輪盤賭策略從所有pbesti中選擇出的全局最優點gbest的一個替代值。

3.2 自適應隨機慣性權重系數

慣性權重系數是粒子群算法中一個極其重要的系數，它的取值大小在一定程度上影響了當前粒子的前一時刻迭代信息對當前飛行狀態的影響程度。在粒子群算法中，如果慣性權重系數選擇合適的值，則有利于平衡算法全局搜索和局部搜索之間的矛盾。在大多數的粒子群改進算法中采用了慣性權重線性遞減的策略，在算法搜索初期，選擇較大的慣性權重值可以使得算法獲得較強的全局搜索能力，而在算法搜索后期，選擇較小的慣性權重值可以使得算法漸進收斂到全局最優。本文中，我們提出了如下的自適應隨機慣性權重：

其中：wmax是慣性權重系數所能取到的最大值；wmln為慣性權重系數所能取到的最小值；rand為[0，1]之間的隨機數；randn為服從正太分布的隨機數；gen和maxgen分別為算法的當前迭代次數和迭代總次數。σ為方差，用于衡量當前慣性權重與其數學期望的偏離程度。

3.3 “優勝劣汰”更新機制

為了提高粒子群算法的收斂速度，我們提出了“優勝劣汰”的更新策略。具體方式為：當更新完所有粒子的位置后，根據粒子適應度值的大小對粒子進行排序。在算法中將最差的S個粒子用最好的S個粒子代替。若S取值越大，則替換的粒子越多，不利于保持種群的多樣性。但如果S的取值很大，則會使算法喪失很多粒子的有效信息，使算法趨于局部搜索；若R取值越小，算法的收斂速度會降低。因此這里的R取

改進的粒子群算法的流程描述如下：

（1）給定算法的參數，如慣性權重、學習因子、變量范圍等，隨機初始化粒子的位置；

（2）計算每個粒子的適應度值，將第i粒子的位置存儲在個體最優位置pbest_i中，將整個粒子群的最好位置存儲在群體最優極值gbest中；

（3）給出初始溫度；

（4）計算當前時刻溫度下所有pbest_i的適配值，并采用輪盤賭方法從pbest_i中選擇一個全局最優位置gbest的替代值，并按照式（3）、（4）、（5）對所有粒子的位置進行迭代更新；

（5）分別對粒子的個體最優位置pbest_i和群體最優位置gbest進行更新，并對算法執行降低溫度的操作；

（6）判斷算法開始時設置的終止條件是否滿足。如果滿足，結束算法的此次尋優，輸出我們需要的數值結果，否則轉步驟（4）繼續尋優。

5 數值實驗

為了驗證NPSO算法的可行性及有效性，我們在4個標準測試函數上進行了測試。并與其它三種改進算法，即基于慣性權重遞減策略的粒子群優化（LDWPSO）算法、一種更簡化而高效的粒子群優化（SSPSO）算法、基于隨機慣性權重的簡化粒子群優化（SIWSPSO）算法進行了數值實驗比較。主要比較以下四個方面：最優解、最差解、平均值、方差。

4個經典測試函數如下：

從表1中可以看出IPSO算法在迭代次數為30時就已經找到了全局最優位置，比其它三種算法的收斂速度快，尋優精度高。而從最優值、最差值、均值和方差四個方面來看，它都遠遠優于其它三種算法，故該算法的魯棒性較好。

6 結論

針對標準粒子群算法收斂精度低、容易早熟等缺點，在粒子群算法中引入了模擬退火算法的有效思想，并對算法的迭代方式進行了有效簡化；為平衡算法全局和局部搜索能力之間的矛盾，提出了一種新的自適應隨機慣性權重；采用“優勝劣汰”的更新機制來加快算法的收斂速度。實驗結果驗證了本文算法的可行性和高效性。