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

趙乃剛

摘要：鑒于標準粒子群優(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)外學(xué)者和學(xué)術(shù)界的廣泛關(guān)注，并對它進行了許多方面的改進。而且它已經(jīng)在軌道電路補償電容故障診斷、求解整數(shù)和混合整數(shù)約束優(yōu)化問題、人臉識別、車牌定位、機位分配等許多領(lǐng)域得到了廣泛應(yīng)用。然而標準粒子群算法也存在如下缺點：尋找到的最優(yōu)位置可能是局部最優(yōu)位置而不是全局最優(yōu)位置；參數(shù)的選擇存在很大的不確定性；算法尋優(yōu)初期收斂速度快而尋優(yōu)后期收斂速度變慢。鑒于粒子群算法的這些缺點，很多學(xué)者對粒子群算法做了大量的改進。文獻中提出了慣性權(quán)重因子并將它引入粒子群算法中，提高了算法的收斂速度和收斂精度；文獻在分析了不確定性參數(shù)對算法影響的基礎(chǔ)上，提出了基于維數(shù)選擇策略的粒子群算法，并通過數(shù)值實驗證明了它們有關(guān)隨機參數(shù)的分析是正確可行的。文獻分析了慣性權(quán)重、學(xué)習(xí)因子對粒子群算法的影響，構(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₂是學(xué)習(xí)因子，一般取非負數(shù)；r₁，r₂是介于[0，1]之間的隨機數(shù)。對于算法的迭代終止條件，我們一般會根據(jù)不同的具體問題而設(shè)定不同的值。通常將上面描述的帶有慣性權(quán)重系數(shù)的粒子群算法稱為標準的粒子群算法。

2 模擬退火算法

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

3 改進的粒子群算法

3.1 簡化的粒子群算法

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

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

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

慣性權(quán)重系數(shù)是粒子群算法中一個極其重要的系數(shù)，它的取值大小在一定程度上影響了當(dāng)前粒子的前一時刻迭代信息對當(dāng)前飛行狀態(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分別為算法的當(dāng)前迭代次數(shù)和迭代總次數(shù)。σ為方差，用于衡量當(dāng)前慣性權(quán)重與其數(shù)學(xué)期望的偏離程度。

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

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

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

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

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

（3）給出初始溫度；

（4）計算當(dāng)前時刻溫度下所有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é)果驗證了本文算法的可行性和高效性。