改進的粒子群算法

宋繼紅

(長春大學 電子信息工程學院，長春 130022)

1 粒子群算法概述

粒子群優化算法(PSO)中是，Kennedy和Eberhait提出的一種基于群體智能的演化計算技術，它初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優解，在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pbest，另一個極值是整個種群目前找到的最優解，這個極值是全局極值gbest。它沒有遺傳算法用的交叉(crossover)以及變異(mutation)，而是粒子在解空間追隨最優的粒子進行搜索。

在找到這兩個最優值時，粒子根據如下的公式來更新自己的速度和新的位置:

V是粒子的速度，pbest和gbest如前定義，rand是介于(0，1)之間的隨機數，c1，c2是學習因子，通常c1=c2=2。每一位粒子的速度都會被限制為不高于一個最大速度Vmax，如果某一位更新后的速度超過用戶設定的Vmax，那么這一位的速度就被限定為Vmax。

在標準PSO算法中，慣性權重是控制歷史速度對當前速度的影響程度，平衡PSO算法的全局搜素和局部搜索能力。當w較大時，算法具有較強的全局搜索能力;當w較小時，算法的局部搜索能力強，而且PSO算法后期粒子容易在全局最優解附近出現震蕩現象，我們通常需要反復試驗才能確定w最大值wmax，Wmin和最大迭代次數。而且找到適應每個問題的最佳值也比較困難，所以有必要對更新的位置作一定的限制，限制的思路多種多樣，既可以采用速度限制的方法，也可以采用模擬退火思想的方法，本文將模擬退火思想運用到粒子群算法中去，以解決局部最優和速度收斂緩慢的問題。

2 模擬火退算法概述

模擬退火算法的基本思想是從一給定解開始的，從鄰域中隨機產生另一個解，接受準則允許目標函數在有限范圍內變壞，以一定概率接受新的解。

退火溫度是跳出局部極值的關鍵參數，退火溫度直接影響接受準則，因此退火溫度一定要選好初值。當算法接近收斂時，局部最大適應值和個體適應值之比逐漸減少并趨向于1，退火溫度t隨之逐漸接近0。這樣，在全局最優解附近的溫度下降速率足夠慢，接受惡化解概率也逐漸減少，所以粒子群定會形成最低能量的基態。

3 粒子群算法的優化策略

基于這種思想進行了兩種方法的改進:

方法1:按(2)式計算新的位置，計算兩個位置所引起的適應值的變化量△E;若△E≤0，接受新值，否則若exp(－△E/T)＞rand(0，1)，也接受新值，否則就拒絕，xk+1仍為xk具體步驟如下:

1)對每個粒子初始化，設定粒子數n，隨機產生n個初始解或給出n個初始解，隨機產生n個初始速度，給定起止“溫度”T、T0和退火速度α;

2)根據當前位置和速度產生這個粒子的新位置;

While(迭代次數＜規定迭代次數)do

3)計算每個粒子新位置的適應值;若粒子的適應值優于原來的個體極值pbest，設置當前適應值為pbest;

4)根據各個粒子的個體極值pbest找出全局極值gbest;

5)按(1)式，更新自己的速度，并把它限制在Vmax內;

6)按(2)式，更新當前的位置;

7)計算兩個位置所引起的適應值的變化量△E;△E≤0，接受新值，否則若exp(－△E/T)＞rand(0，1)，也接受新值，否則就拒絕，xk+1仍為xk;

8)若接受新值，降溫T←αT，否則不降溫。

End

方法2:接受準則允許目標函數有限范圍內變壞，并不按概率取舍，直接按△E＜e，e為按允許目標函數變壞范圍，具體算法如下:

1)對每個粒子初始化，設定粒子數n，隨機產生n個初始解或給出n個初始解，隨機產生n個初始速度;

2)根據當前位置和速度產生這個粒子的新位置;

While(迭代次數＜規定迭代次數)do

3)計算每個粒子新位置的適應值;

4)對某個粒子，若粒子的適應值優于原來的個體極值pbest，設置當前適應值為pbest;

5)根據各個粒子的個體極值pbest找出全局極值gbest;

6)按(1)式，更新自己的速度，并把它限制在Vmax內;

7)按(2)式，更新當前的位置;

8)計算兩個位置所引起的適應值的變化量△E;若△E ＜e，接受新值，否則就拒絕，xk+1仍為xk。End

4 數值模擬

分別選用上文中的方法1，方法2和原始PSO算法對下面兩個標準測試函數進行計算，并對其結果進行分析。

參數設置如下:在基本的粒子群算法中，粒子數n=40，Vmax=1，Vmin=－1，初始速度都為0。

方法1的參數與基本粒子群算法相同，起始溫度T=100，退火溫度α=0.99。

方法2的參數與基本粒子群算法相同，xmax=10，xmin=－10;e=1。

由于此函數較復雜，因此將循環次數設為30次，測試結果如表1所示。

表1 三種策略對F2的測試結果

由于這個函數的特殊性參數設置如下:Vmax=0.3，Vmin=－0.3;xmax=2，xmin=－2;允許的最大適應值為9.999;初始溫度T=100，退火溫度α=0.99，e=1;一個循環內最大迭代次數為5000，各種策略循環1000次的結果如表2所示。

表2 三種策略對F3的測試結果

仍然針對函數F3，現在我們想比較一下各種方法的收斂快慢，我們跟蹤粒子的每次迭代的位置，每隔5ms紀錄一次粒子的位置，三種算法都只運行一次的詳細跟蹤圖如圖1所示。

圖1 三種算法的收斂圖

從表1中我們可以看出，方法1和方法2的總運行時間和總迭代次數都少于原始的粒子群算法。但在表2中方法2的總運行時間卻比原始粒子群算法的總運行時間長。原始的粒子群算法迭代了不到60次最先停止，方法2迭代了接近100次最后停止。出現這種情況的原因在于方法1和方法2在一定程度上接受了惡化解，而基本粒子群算法不接受惡化解，因此基本粒子群算法的運行時間快。但是這種快是有一定的前提的，那就是算法一定收斂到最優解，而不是局部最優。

對于表2中的粒子群算法，我們為了讓其收斂也把X限定了范圍這種思想正是本文方法1算法的思想，現在我們把粒子群算法中的X范圍擴大到，我們把循環次數降低到20次得到表3。

表3 不同的x范圍的粒子群算法運行結果

續表

再把表3細化，當xmax=5，xmin=－5時基本粒子群算法程序運行詳細結果，我們可以看出第三次和第四次循環程序迭代次數為5000次，而5000正是我們程序所規定的最大迭代次數，最優值分別為9.311330和9.102719，這說明第三次和第四次循環基本粒子群算法陷入了局部最優。當xmax=10，xmin=－10時，程序的20次循環中的18次都陷入了局部最優。經過上述的測試和分析，本文的兩種改進策略都能在一定程度上避免陷入局部最優，并且在大多數情況下其運行時間和迭代次數比原始粒子群算法少。

5 結語

通過本文的測試結果，并加以分析，我們可以得出如下結論:

方法1算法和方法2算法都能在一定程度上有效的避免了陷入局部最優，這也是本文最重要的結論;當三種算法都收斂時，用他們來計算同一函數并循環n次(n很大)，絕大多數情況下方法2算法的迭代次數最少，然后是方法2算法，最后是基本粒子群算法;而總運行時間則是方法2算法最少，然后是方法21算法，最后是基本粒子群算法;方法2算法的總運行時間和迭代次數隨x范圍的增大而增大并且這種增大的趨勢越來越迅速。

［1］Kennedy J，Eberhart R.Particle Swarm Optimization［J］.In:IEEE Int1 Conf on Neural Network，Perth，Australia，1995:1942 －1948.

［2］白莉媛，胡聲艷，劉素華.一種基于模擬退火和遺傳算法的模糊聚類方法［J］.計算機工程與應用，2005(9):56－58.

［3］謝曉峰，張文俊，楊之廉.微粒子群算法綜述［J］.控制與決策，2003(2):129－134.

［4］Clerc M，The Swarm and the Queen:Towards a Deterministic and Adaptive Particle Swarm Optimization，In:Proc of the C t R，A modified particle swarm optimizer［J］.In:IEEE World Congress on Computational Intelligence，1999:1951 － 1957.