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

趙乃剛

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

關(guān)鍵詞：粒子群優(yōu)化算法；慣性權(quán)重；優(yōu)勝劣汰

中圖分類號：TP18

文獻標識碼：A

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

0 引言

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

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

1 基本粒子群算法

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

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

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

2 模擬退火算法

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

3 改進的粒子群算法

3.1 簡化的粒子群算法

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

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

3.2 自適應(yīng)隨機慣性權(quán)重系數(shù)

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

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

3.3 “優(yōu)勝劣汰”更新機制

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

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

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

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

（3）給出初始溫度；

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

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

（6）判斷算法開始時設(shè)置的終止條件是否滿足。如果滿足，結(jié)束算法的此次尋優(yōu)，輸出我們需要的數(shù)值結(jié)果，否則轉(zhuǎn)步驟（4）繼續(xù)尋優(yōu)。

5 數(shù)值實驗

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

4個經(jīng)典測試函數(shù)如下：

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

6 結(jié)論

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