改進(jìn)的粒子群算法

宋繼紅

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

1 粒子群算法概述

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

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

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

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

2 模擬火退算法概述

模擬退火算法的基本思想是從一給定解開始的，從鄰域中隨機(jī)產(chǎn)生另一個解，接受準(zhǔn)則允許目標(biāo)函數(shù)在有限范圍內(nèi)變壞，以一定概率接受新的解。

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

3 粒子群算法的優(yōu)化策略

基于這種思想進(jìn)行了兩種方法的改進(jìn):

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

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

2)根據(jù)當(dāng)前位置和速度產(chǎn)生這個粒子的新位置;

While(迭代次數(shù)＜規(guī)定迭代次數(shù))do

3)計算每個粒子新位置的適應(yīng)值;若粒子的適應(yīng)值優(yōu)于原來的個體極值pbest，設(shè)置當(dāng)前適應(yīng)值為pbest;

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

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

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

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

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

End

方法2:接受準(zhǔn)則允許目標(biāo)函數(shù)有限范圍內(nèi)變壞，并不按概率取舍，直接按△E＜e，e為按允許目標(biāo)函數(shù)變壞范圍，具體算法如下:

1)對每個粒子初始化，設(shè)定粒子數(shù)n，隨機(jī)產(chǎn)生n個初始解或給出n個初始解，隨機(jī)產(chǎn)生n個初始速度;

2)根據(jù)當(dāng)前位置和速度產(chǎn)生這個粒子的新位置;

While(迭代次數(shù)＜規(guī)定迭代次數(shù))do

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

4)對某個粒子，若粒子的適應(yīng)值優(yōu)于原來的個體極值pbest，設(shè)置當(dāng)前適應(yīng)值為pbest;

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

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

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

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

4 數(shù)值模擬

分別選用上文中的方法1，方法2和原始PSO算法對下面兩個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行計算，并對其結(jié)果進(jìn)行分析。

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

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

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

由于此函數(shù)較復(fù)雜，因此將循環(huán)次數(shù)設(shè)為30次，測試結(jié)果如表1所示。

表1 三種策略對F2的測試結(jié)果

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

表2 三種策略對F3的測試結(jié)果

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

圖1 三種算法的收斂圖

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

對于表2中的粒子群算法，我們?yōu)榱俗屍涫諗恳舶裍限定了范圍這種思想正是本文方法1算法的思想，現(xiàn)在我們把粒子群算法中的X范圍擴(kuò)大到，我們把循環(huán)次數(shù)降低到20次得到表3。

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

續(xù)表

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

5 結(jié)語

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

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

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

［2］白莉媛，胡聲艷，劉素華.一種基于模擬退火和遺傳算法的模糊聚類方法［J］.計算機(jī)工程與應(yīng)用，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.