改進PSO算法的性能分析與研究

摘 要:分析了粒子群優化(PSO)算法的進化式，針對其容易發生早熟、收斂速度慢、后期搜索性能和個體尋優能力降低等缺點，結合遺傳算法的思想，提出一種新的混合PSO算法——遺傳PSO(GAPSO)。該算法是在PSO算法的更新過程中，對粒子速度引入遺傳算法的變異操作，對粒子位置引入遺傳算法交叉操作。對速度的變異降低了算法后期因種群過于密集而陷入局部最優的可能，對位置的交叉使得父代中優良個體的基因能夠更好地遺傳給下一代，從而得到更優、更多樣化的后代，加快進化過程，提高了收斂速度和群體搜索性能。選取了其他幾種典型的改進PSO算法，從算法執行過程、參數設置及優化性能等方面對各算法進行全面的分析比較，其中對模擬退火PSO算法采用了一種新的可提高算法執行速度的退火方式。最后針對選取的六個Benchmark函數優化問題進行數值仿真實驗。仿真結果表明了所提出的遺傳PSO算法不但收斂速度加快，而且后期搜索性能提高，能更有效地收斂到全局最優。為了形象地顯示粒子的收斂過程，還仿真了GAPSO算法對二維多模態Griewank函數的動態尋優過程。

關鍵詞:粒子群優化(PSO); 遺傳PSO; 二階振蕩PSO; 量子PSO; 模擬退火PSO

中圖分類號:TP301.6

文獻標志碼:A

文章編號:1001-3695(2010)02-0453-06

doi:10.3969/j.issn.1001-3695.2010.02.013

Performance analyzing and researching of improved PSO algorithm

LEI Xiu-juan， FU A-li， SUN Jing-jing

(School of Computer Science， Shaanxi Normal University， Xi’an 710062， China)

Abstract:To deal with the slow search speed， premature convergence and lower search performance and individual optimizing ability in late stage， this paper proposed a new PSO called genetic PSO. Produced mutation and crossover of GA into velocity and position updating of PSO. The mutation to velocity could reduce the possibility of the algorithm trapping in the local optimal because of the over dense of the population in late stage. The crossover to position could make the gene of excellent elder individuals passed down to the next generation， and by doing so， attained the more excellent and more various next generations， so increased the evolution and search performance of the population. Selected several other typical improved PSO algorithms for comparing and analyzing from implementing process， setting of parameters and optimization performance. To simulated annealing PSO， proposed a new annealing method which could increase the speed of implementation of the algorithm. The simulation experiments were done to the six selected Benchmark functions. The results show that the proposed algorithm not only speeded up the convergence， but also improved the search performance in late stage and could converge to the global optimal solution more efficiently. And lastly， presented the simulation of dynamic optimizing process of genetic PSO to the Griewank functionso that converging process of the particles could be viewed vividly.

Key words:particle swarm optimization(PSO); genetic PSO; SOPSO; QPSO; SAPSO

0 引言

粒子群優化(PSO)算法是由Kennedy等人[1]于1995年提出的一種基于種群搜索的自適應進化計算技術。PSO算法實現容易、參數較少，能有效解決復雜優化任務[2]，在過去幾年中得到了飛速發展，并在圖像處理、模式識別、優化等領域得到了廣泛應用。

PSO算法作為一種嶄新的隨機搜索算法存在著易陷入局部極值點、進化后期收斂速度慢、精度較差等不足。針對這些問題，研究人員從各個方面對PSO算法進行了改進，涌現了大量的研究成果。主要的改進方法表現為改變參數、 改變進化方程以及與其他智能優化算法的融合等。文獻[3]給出了一種自適應逃逸粒子群算法，算法中的逃逸行為是一種簡化的速度變異操作，通過速度的自適應變化改變微粒在搜索空間內的飛行速度，使得PSO算法收斂速度得到提高。但是該變異操作[3]僅僅增加了個體微粒的搜索性能，在算法迭代后期沒有充分利用種群間的相互信息，對于Schaffer問題仍然存在收斂速度較慢、不能快速逃出局部極小點的缺點。

本文結合遺傳算法的思想和文獻[3]中的逃逸思想，提出一種新的融合PSO算法——遺傳PSO。該算法是在速度變異的同時，對粒子位置執行一種交叉操作，通過交叉將上一代種群優良個體的基因遺傳給下一代，使得一次進化得到的新種群趨于更優、更多樣化狀態。新算法和其他幾種典型改進PSO算法，包括標準PSO(SPSO)、帶收縮因子的PSO(KPSO)、二階振蕩PSO(SOPSO)、量子PSO(QPSO)和模擬退火PSO(SAPSO)，對典型復雜函數優化的仿真結果進行對比，充分顯示了新算法的快速收斂性和全局收斂性。

1 基本粒子群優化(PSO)算法[1]

PSO算法最初是為了圖形化地模擬鳥群優美而不可預測的運動。PSO初始化為一群隨機粒子，然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己:第一個就是粒子本身所找到的最優解，這個解叫做個體極值pbest;另一個極值是整個種群目前找到的最優解，這個極值是全局極值gbest。在找到上述兩個最優值時，粒子根據如下公式來更新自己的速度和新的位置:

vk+1id=vkid+c1r1(pbestkid-xkid)+c2r2(gbestkid-xkid)(1)

xk+1id=xkid+vk+1id(2)

其中:c1和c2為加速常數(acceleration constants)，通常c1、c2在[0，4]，一般取c1=c2=2;r1和r2為兩個在[0，1]內服從均勻分布的隨機變量。每個粒子的位置和速度都以隨機方式進行初始化，而后粒子的速度就朝著全局最優和個體最優的方向靠近。

2 各種改進PSO算法

2.1 標準PSO算法(SPSO)

為了使粒子保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區域。Shi等人[4]提出了對基本粒子群算法的改進，即對速度更新方程加慣性權重w:

vk+1id=wvkid+c1r1(pbestkid-xkid)+c2r2(gbestkid-xkid)(3)

分析式(3)可以發現，粒子群到達局部最優附近時，粒子速度的更新主要由第一項來決定。由于固定參數的PSO算法的慣性權重w通常小于1，粒子的速度將會越來越小，甚至停止運動，發生早熟收斂。對此，很多學者研究了自適應改變慣性權重，如線性遞減慣性權重。

2.2 帶收縮因子的PSO算法(KPSO)

文獻[5]的研究發現，壓縮因子k有助于確保PSO算法收斂，它將速度更新方程描述為

vk+1id=k[vkid+c1r1(pbestkid-xkid)+c2r2(gbestkid-xkid)](4)

其中:k=22-φ-φ2-4φ，φ=c1+c2。

收縮因子法控制系統行為最終收斂，且可以有效搜索不同的區域，該算法能得到高質量的解。

將這兩種改進策略綜合到一起形成帶收縮因子和線性遞減慣性權重的粒子群優化算法(KPSO)，此算法目前效果較其他改進算法好。在進行速度更新時，將慣性權重和收縮因子同時用在速度更新方程中:

vk+1id=k[wvkid+c1r1(pbestkid-xkid)+c2r2(gbestkid-xkid)](5)

2.3 二階振蕩PSO算法(SOPSO)

為了便于分析，在式(1)中取φ1=c1r1，φ2=c2r2，將式(3)和(2)寫成式(6)和(7):

vi(t+1)=wvi(t)+φ1(pi(t)-xi(t))+φ2(pg(t)-xi(t))(6)

xi(t+1)=xi(t)+vi(t+1)(7)

從控制論的角度分析，式(6)相當于分別以pi和pg為輸入的兩個慣性環節的并聯。為了增加種群多樣性，采用二階振蕩環節來代替慣性環節，那么，粒子群算法的進化方程式(6)和(7)可描述為

vi(t+1)=wvi(t)+φ1[pi(t)-(1+ξ1)xi(t)+ξ1xi(t-1)]+φ2[pg(t)-(1+ξ2)xi(t)+ξ2xi(t-1)](8)

xi(t+1)=xi(t)+vi(t+1)(9)

即為二階振蕩粒子群算法[6]。

文獻[6]已證明，當ξ1≥2φ1-1φ1，ξ2≥2φ2-1φ2時，算法漸進收斂;當ξ1<2φ1-1φ1，ξ2<2φ2-1φ2時，算法振蕩收斂。在全局搜索算法中，一般地，希望算法前期有較高的探測能力以得到合適的粒子，而在后期有較高的開發能力以加快收斂速度。假設算法的最大迭代次數為MaxIt，本文經過多次實驗測試，在前MaxIt/8取ξ1<2φ1-1φ1，ξ2<2φ2-1φ2，使得算法有較強的全局搜索能力;之后取ξ1≥2φ1-1φ1，ξ2≥2φ2-1φ2，增強算法的局部搜索能力。

2.4 量子PSO算法(QPSO)

在量子物理學中，具有動量和能量的粒子狀態可以用波動函數來表示。因此在QPSO模型[7]中，將粒子的運動狀態用其波動函數Ψ來表示，代替了標準PSO中粒子的速度和位置。QPSO將每個個體看做是Nd維搜索空間中的一個沒有重量和體積的微粒在搜索空間中以一定的速度飛行，該飛行速度由個體的飛行經驗和群體的飛行經驗動態調整。每個粒子代表Nd維空間中的一個位置，朝著個體最優和全局最優兩個方向調整自己的位置。

QPSO算法中粒子的更新式[7]為

mbest=1M∑Mi=1pi=1M∑Ni=1Pi1，1M∑Ni=1Pi2，…，1M∑Ni=1Pid(10)

p=(pbest×φ1+gbest×φ2)/(φ1+φ2)(11)

x(t+1)=p±α×mbest-x(t)×ln (1/u)(12)

其中:φ1、φ2、u是在(0，1)均勻分布的隨機數，叫做收縮—膨脹因子，是該算法中惟一的參數，對這個參數的取值文獻[7]作了詳細討論。本文中設置α的取值在1.0~0.5，呈線性遞減。

2.5 模擬退火PSO算法(SAPSO)

SAPSO[8]是在PSO的每次迭代過程中加入模擬退火的思想，使得粒子i在第t+1步時，按照某一概率用xi(t+1)取代xi(t)，保證粒子不易陷入局部最優;同時采用溫度T來控制這一概率，溫度T隨著算法的執行緩慢下降;若f(xi(t+1))差于f(xi(t))，隨著溫度的下降，用xi(t+1)取代xi(t)的概率不斷減小，從而控制粒子使之不能從有“希望”的搜索區域中跳出。文獻[8]中的退火參數由β決定，β是一個取值在(0，1)的常數。本文結合PSO算法的執行過程，提出一種新的退火方式:讓溫度隨迭代次數的增加從初始溫度線性遞減到最低溫度。假設初始溫度和最低溫度分別為T0和Tend，最大迭代次數和當前迭代次數分別為MaxIt和iter，則當前溫度:

Ti=(T0-Tend)×(MaxIt-iter)/MaxIt+Tend(13)

這樣在PSO算法的開始，溫度較高種群以較大概率接受差解，保證粒子可以跳出局部最優;隨著迭代次數增加，溫度降低，接受差解的概率較低，可以保證算法后期粒子在某個局部空間進行細致搜索。算法描述如下:

Initialize Population，T0，Tend，MaxIt and so on;

do

for iter=1 to MaxIt

Ti=(T0-Tend)×(MzaIt-iter)/MaxIt+Tend;

for i=1 to Population Size

iff(xi)

pg=min(pi);

for d=1 to Dimension

vtemp-d=wvid+c1r1(pid-xid)+c2r2(pgd-xid);

ifvtemp-d>Vmax thenvtemp-d=Vmax;

xtemp-d=xid+vtemp-d;

next d;

iff(xtemp)≤f(xi) then xi=xtemp;

else

xi=xtemp with Probability:pT=e-Δf(#8226;)/Ti

next i;

next iter;

if termination criterion is met then stop;

3 新的具有遺傳特性的PSO算法(GAPSO)

文獻[3]結合生物界中物種發現生存密度過大時會自動分家遷移的習性，給出了一種自適應逃逸微粒群算法。本文在文獻[3]算法思想的基礎上，結合生物進化特征，給出一種不僅可以提高收斂速度，而且可增加種群多樣性，提高種群進化質量的新型混合PSO算法——GAPSO算法。

GAPSO算法是對文獻[3]中速度變異操作進行改進的同時引入對位置的一種交叉操作。該交叉操作可使PSO算法更好地擺脫局部極值點，提高算法的收斂速度和全局收斂性。該交叉操作的思想如下:

對一次更新后的種群，從中隨機挑出m個粒子，將這m個粒子的當前位置Xi與其當前個體極值pi及按適應度值排序后的個體極值中的前m個極值(spi)進行交叉，得到m個新的粒子位置X′i。如果新位置的適應值f(X′i)優于排序后對應個體極值的歷史最優適應值f(spi)，則用f(X′i)取代f(Xi)，同時用X′i取代Xi。顯然，這樣的交叉使得粒子在一次進化中不但利用了自己的歷史經驗信息，而且利用了種群中優良個體的經驗信息，增加了粒子的多樣性，更增加了種群的進化質量，使粒子找到全局最優的可能性增大。

假定粒子的維數為d，種群規模為Popsize，則交叉操作的偽碼如下:

M=floor(d/3);N=floor(2d/3);

隨機產生m個大小在1~Popsize的整數存放于J中;

for i=1:m

X′i=(pJ(i)1，pJ(i)2，…，pJ(i)M，XJ(i)(M+1)，XJ(i)(M+2)，…，XJ(i)N，spi(N+1)，spi(N+2)，…，spid);

if f(X′i)

XJ(i)=X′i;

f(XJ(i))=f(X′i);

end

end

分析式(3)，迭代后期，當某些粒子的位置xi及其pbest接近群體的gbest時，其速度更新由wv決定。由于w<1，粒子的運行速度將迅速趨于0，粒子運行出現惰性。隨著迭代的進行，其他粒子將很快聚集到這些惰性粒子的周圍，使粒子過早地收斂于gbest而停止運動(粒子速度變為0)，而gbest只是種群目前找到的最好點，并不能保證一定是優化問題的全局最優解。

從以上分析可見，要讓算法收斂到全局最優，就要使惰性粒子逃離局部最優點，而粒子接近gbest的程度與其速度大小有關，即可通過干擾惰性粒子速度使其跳出局部最優。

要使優化算法擺脫局部最優，首先要判斷在什么情況下算法可能陷入局部最優。本文認為:當種群目前全局極值的適應值f(gbest)>Err(Err為給定誤差精度)且種群中有惰性粒子出現時，算法有可能陷入局部最優。這時，對惰性粒子，即速度小于某個閾值的粒子速度進行變異，降低算法陷入局部最優的可能性。

假定速度閾值為Vth=(Vth1，Vth2，…，Vthd)，種群規模為Popsize，則本文速度變異的設計思路如下:

for j=1:d

for i=1:Popsize

ifVid

temp(j)=temp(j)+1;

if f(gbest)>Err

flag=ture;

Vid=Vmax×(2×rand-1); (Vmax為粒子的最大速度值，rand為(0，1)均勻分布的隨機數)

pid=Xid

end

end

end

end

if flag=true

Err=Err/10;

end

t=find(temp>C1);

(C1為一個閾值常數，視種群的規模而定)

Vtht=Vtht/C2;

end.

4 仿真實驗及結果分析

為了顯示新的GAPSO的高效性，本文選擇了PSO算法和遺傳算法(genetic algorithm，GA)經常使用的六個Benchmark函數問題[3]。根據函數性質分為具有單一極小點(單模態)(f1~f3)和多個局部極小點(多模態)(f4~f6)兩大類，每類三個函數，如表1所示。Tablet和Quadric函數是Spherical函數的變形，增加了函數各維之間的相互作用(Spherical函數是一個連續的、簡單單模態函數，通常用來分析算法的執行性能)。Rosenbrock函數是一個經典復雜優化問題，它的全局最優點位于一個平滑、狹長的拋物線形山谷內。由于此函數僅僅為優化算法提供了少量信息，使算法很難辨別搜索方向，找到全局最小點的機會微乎其微，Rosenbrock函數通常用來評價優化算法的執行效率[3]。函數f4~f6是典型的非線性多模態函數，它們具有廣泛的搜索空間、大量的局部極小點和高大的障礙物，通常被認為是遺傳算法很難處理的復雜多模態問題。本文的實驗運行平臺是MATLAB 7.0，在內存為1 GB，CPU速度為1.86 GHz的雙核PC機上運行。

表1 用于測試的六個Benchmark函數

FunctionNameDimSearch SpaceMin\\Best position

f1(x)=106x21+∑ni=2x2iTablet30(-100，100)0 (0，…，0)

f2(x)=∑Di=1(∑ij=1xj)2Quadric30(-100，100)0 (0，…，0)

f3(x)=∑D-1d=1[100(xd+1-x2d)2+(1-xd)2]Rosenbrock30(-5.12，5.12)0 (1，…，1)

f4(x)=(1/4000)∑Dd=1x2d-ΠDd=1cosxdd+1Griewank30(-300，300)0 (0，…，0)

f5(x)=∑Dd=1[x2d-10cos](2πxd)+10]Rastrigin30(-5.12，5.12)0 (0，…，0)

f6(x)=∑D-1i=1(x2i+x2i+1)0.25[sin2(50(x2i+x2i+1)0.1)+1.0]Schaffer’s f730(-100，100)0 (0，…，0)

4.1 參數設置

所有實驗的最大迭代次數均設為2 000次。除QPSO算法外，其他算法均采用阻尼墻策略[9]處理超出邊界問題;對于SAPSO采用本文提出的線性遞減退火策略。經過參數分析和多次實驗，最終對各個算法的相關參數的設置如表2所示，其中慣性權重w的取值:SPSO、KPSO和SAPSO，單模態函數取0.6，多模態函數取[0.9，0.4]線性遞減;GAPSO，單模態函數取0.6，多模態函數取[0.6，0.5]線性遞減;SOPSO均取[0.9，0.4]線性遞減。GAPSO對每個函數的初始誤差精度Err和速度閾值Vth的設定如表3所示，Vth=rand×Mvth。

表2 實驗中各個算法的參數設置

Algorithmw1c1c2αT0TendmC1C2Popsize

SPSO0.6/[0.9，0.4]1.71.7------30

KPSO0.6/[0.9，0.4]1.71.7------30

SOPSO[0.9，0.4]0.40.8------30

2PSO---[1.0，0.5]-----30

SAPSO0.6/[0.9，0.4]1.71.7-leb----30

GAPSO0.6/[0.6，0.5]1.71.7---10101030

表3 GAPSO針對各函數的初始誤差精度和速度閾值

FunctionTabletQuadricRosenbrockGriewankRastriginSchaffer’s f7

Err1e-501e-51e-51e-501e-51e-5

Mvth1e-401e-81e-81e-401e-81e-8

對每個測試函數分別用每種算法做10次獨立實驗，圖1～6分別表示七種算法對六個函數進行優化時10次實驗的平均種群適應值變化趨勢(圖中為了曲線變化對比明顯，縱軸是對平均種群適應值取了自然數對數，橫軸是種群的進化代數)。SAPSO算法采用兩種退火策略的結果對比如表4所示。對于各測試函數每種優化算法，運行10次求得的結果的最小值(fMin)、最大值(fMax)、平均值(fMean)以及所得的最小運行時間(tMin)、最大運行時間(tMax)、平均運行時間(tMean)，如表5和6所示。

表4 SAPSO算法采用兩種退火策略的結果對比

Function

線性遞減退火策略的SAPSO算法

fMinfMaxfMeantMean/s

β參數控制退火的SAPSO算法

fMinfMaxfMeantMean/s

Tablet4.3547e-0373.6908e-0303.7552e-0313.05319.4209e-2939.3300e-0239.3300e-02417.0500

Quadric0.035214.38572.75723.72972.693735.159215.202021.4875

Rosenbrock0.711922.805916.34712.637515.350024.102719.414414.5594

Griewank00.09570.01843.114100.07360.016217.3016

Rastrigin15.219238.172828.00683.34228.021116.914313.751318.5297

Schaffer’f70.004113.82933.11823.982811.582e-0045.15921.971834.0547

4.2 兩種退火策略下SAPSO算法結果對比

對于文獻[8]中的β參數控制退火SAPSO(β-SAPSO)算法，取退火參數β=9.6，T0=100，Tend=0.1，c1=c2=1.8，種群最大迭代次數為100;對于本文提出的線性遞減退火策略的SAPSO(LD-SAPSO)算法，其參數設置同表2，最大迭代次數為3 000。用兩種方法對六個函數進行優化，對每個函數都做10次獨立實驗，得到10次結果的最小值(fMin)、最大值(fMax)、平均值(fMean)和算法平均運行時間(tMean)，結果如表4所示。

從表4可以看出，對于單模態函數，LD-SAPSO比β-SAPSO優化結果好;對于多模態函數，β-SAPSO比LD-SAPSO優化結果好一些。但β-SAPSO運行消耗的時間要比LD-SAPSO多幾倍。因此，在實際應用中，對于單模態和實時性要求較高的多模態優化問題，選擇本文提出的LD-SAPSO效果更理想。

表5顯示了單模態Benchmark問題的實驗結果對比。從表5的實驗結果中各個算法的最優值、最差值和平均值可以看出，GAPSO算法在各個函數上都具有較快的收斂速度和全局搜索能力，特別是Quadric函數所得到的優化結果明顯好于其他算法。對于復雜Rosenbrock函數優化問題，由于很難辨別搜索方向，其他算法單次實驗結果存在較大差異，而GAPSO算法單次實驗結果比較穩定，數據差異相對較小，在Rosenbrock函數優化問題上具有更好的穩定性和健壯性。

4.3 各種改進PSO算法對單模態Benchmark函數問題的實驗結果比較分析

表5 改進PSO算法在單模態Benchmark函數問題上的優化對比

FunctionAlgorithmfMinfMaxfMeantMean/s

TabletSPSOKPSOSOPSOQPSOSAPSOGAPSO7.5978e-0392.4370e-0371.8096e-0255.7748e-0191.8476e-0372.1142e-0432.6945e-0296.9668e-0281.7728e-0201.8861e-0152.0319e-0293.1866e-0352.7140e-0306.9700e-0292.9188e-0215.2319e-0162.2543e-0303.2895e-0361.83281.78132.26252.64221.82502.0234

QuadricSPSOKPSOSOPSOQPSOSAPSOGAPSO0.00286.7760e-0040.01449.72950.07544.7928e-0040.03590.02800.784166.29944.06170.02030.01310.01050.270533.73820.79680.00852.25782.17972.94383.07502.23593.0906

RosenbrockSPSOKPSOSOPSOQPSOSAPSOGAPSO9.55188.380515.187225.261311.74066.917373.555576.067524.435025.727126.500421.277823.237621.843521.432425.555619.936017.30061.54381.52502.28282.35001.53912.2281

從圖1、2顯示的單模態30維Tablet和Quadric函數的優化實驗結果可以看出，GAPSO算法能夠保持較快的收斂速度，持續、有效地搜索全局最小點。最差的是QPSO算法，后期基本不再變化，這與其進化式中有對各粒子的極值取平均有關。SOPSO算法前期下降緩慢，中間還出現停滯，這是因為SOPSO前期的取值使算法振蕩收斂，微粒大幅度振動不能細致搜索，產生在最優點處振蕩的可能。

從圖3可看出，對于復雜單模態30維Rosenbrock函數問題，由于Rosenbrock山谷僅僅給算法提供了很少的信息，使算法不能有效地辨別搜索方向，圖3中的所有算法都具有一個相對穩定的階段，用來尋找搜索方向。在算法初始階段，SAPSO和GAPSO算法都具有較快的收斂速度，但由于SOPSO算法后期取漸進收斂，算法不能以相對大的步長進行搜索而導致出現穩定不再下降的局面;而GAPSO算法，由于后期的交叉和變異操作，使粒子在向全局方向進化的同時改變搜索步長，可在一個相對較短的時間內找到正確的搜索方向，從而保持繼續下降。表5中Rosenbrock函數的最好值、最差值和平均值的數據還顯示，GAPSO具有較好的穩定性，單次執行結果之間的相差小于其他算法。

4.4 各種改進PSO算法對多模態Benchmark函數問題的實驗結果比較分析

對于30維多模態Griewank函數優化問題，表6中的數據顯示，GAPSO算法以60%的幾率收斂到了全局最優值0，其全局搜索能力顯著優于其他改進算法。從圖4可以看出，對于Griewank函數，除GAPSO和QPSO，其他幾個算法容易發生早熟陷入局部極小值，這是因為Griewank函數各維之間顯著相關，存在多個極小值，某一維位置的變化并不能提高粒子的適應值，只有當各維同時發生變化時才有可能提高粒子的適應值，這使得粒子跳出極小點的概率非常小。GAPSO在位置更新中，加入了對各維的交叉操作，保持了各維之間的相關性，能夠有效跳出局部極小點在給定的迭代次數內找到近似全局最小點，顯示了該算法在Griewank函數優化問題上的穩定性與健壯性，QPSO雖然也可以跳出局部極小點，但其全局收斂速度很慢。

表6 各種改進PSO算法在多模態Benchmark函數問題上的優化對比

FunctionAlgorithmfMinfMaxfMeantMean/s

GriewankSPSOKPSOSOPSOQPSOSAPSOGAPSO0(20%)0(30%)0(10%)7.9425e-0130(40%)0(60%)0.03440.07640.10980.03800.04430.03690.01870.02090.03550.01270.01520.00791.90471.86252.33442.75631.91252.6625

RastriginSPSOKPSOSOPSOQPSOSAPSOGAPSO20.488212.660411.93958.086016.14055.986237.890040.268330.844915.915336.028715.936328.626126.534519.799811.256025.923910.35862.06562.18752.72662.75002.01722.7953

Schaffer’s f7SPSOKPSOSOPSOQPSOSAPSOGAPSO0.03320.05540.053811.07350.01240.01073.33836.19522.449650.01683.74931.79701.91651.72810.894932.39080.89850.43213.90313.85634.67504.75003.91715.3828

多模態Rastrigrin函數是一個典型的用來測試算法全局搜索性能的函數。從表5和圖5中可以看出， GAPSO算法具有良好的全局搜索性能和較快的搜索速度，在文中給定的迭代次數下能找到近似全局最優值。同時，圖5還顯示SOPSO算法在搜索前期收斂速度較快，搜索后期由于漸進收斂，搜索步長較短，導致粒子很難跳出局部最優而陷入局部極小點，不能進一步向全局極小點收斂。QPSO算法雖然可以向全局小點收斂，但其全局收斂速度很慢，需要給予足夠長的迭代次數才能找到近似全局最優解。

圖6顯示了30維Schaffer函數的運行結果，可以看出GAPSO算法不論是在搜索的初期階段還是在后期階段都具有較快的收斂速度，能保持正確的搜索方向，持續地尋找全局最優點，顯著優于其他算法。前期除QPSO外，各算法都具有較快的收斂速度，但在后期收斂其他算法收斂速度明顯下降，原因在于SAPSO后期溫度降低使其接受差解的概率變小，降低了搜索性能;SOPSO后期漸進收斂，搜索步長相對小，很難跳過局部極值點。Schaffer函數在向全局極小值靠近的過程中，有無窮多個極小值點。與Griewank函數一樣，由于粒子沒有充分利用各維之間的信息，其他算法在后期都需要一個緩慢的過程才能找到全局最優點。

從以上對比分析可看出，不論是對于單模態還是多模態Benchmark問題， GAPSO算法均具有較高全局搜索能力，幾乎可以在有限代數內找到函數近似理論最優值。從時間消耗上來看，雖然GAPSO相對于其他算法稍微有所增加，這是由于其在每一代粒子更新過程中加入了遺傳和變異操作而增大了時間消耗，但是從平均消耗時間的結果來看，這種增加是在可以接受的范圍之類。從算法設計的理論來講，如果增加較小的時間消耗可以換取理想的效果，這種時間消耗就是值得的。

4.5 GAPSO對2維Griewank函數的動態尋優過程

由于多模態函數存在大量的局部極小點，可以很好地檢驗一個算法是否具有跳出局部極值的能力。為了形象地看出PSO算法進行優化的動態過程， 本文仿真了GAPSO算法對二維多模態Griewank函數的動態尋優過程。仿真取群體規模為30，最大迭代次數為200，解空間邊界為[-5，5]。

圖7是整個動態過程的部分動態截圖， 其中圖7(a)~(d)分別為第1、50、100、200次尋優的結果。從圖中可以看出粒子在第一代時隨機地分布在函數的各個部位，隨著迭代次數的增加逐漸向最小值位置(0，0，0)處移動，最終整個種群都收斂到最小點。

5 結束語

本文分析了微粒群算法速度、種群最優值以及全局最優解之間的關系，將遺傳算法的交叉和變異思想引入到粒子的位置和速度更新過程中，給出了一種解決數值優化問題的新的GAPSO算法。實驗結果顯示:

a)新算法不論是在單模態還是多模態Benchmark問題上均好于現存PSO及其改進算法，對位置更新引入的交叉思想增加了粒子的多樣性和種群的進化質量，使粒子更容易找到正確的搜索方向，從而在多模態問題上易越過局部極值而向全局極值收斂;對速度變異加上判定條件，保證了變異操作不會使粒子遠離全局極值，從而在單模態問題上能快速地向全局極值收斂。

b)新的GAPSO算法提高了整個種群后期的搜索性能和最優個體的尋優能力，進一步提高了算法收斂速度，在Shaffer問題上表現出了良好的性能。

c)交叉和變異操作的引入所增加的時間消耗在可接受的范圍之內。

d)在多模態問題上QPSO表現出的性能僅次于GAPSO，但在單模態問題上性能卻很差，其他改進算法針對不同函數表現出了各自的特點，但優化性能都不如提出的GAPSO好。

本文不僅提出了一種新型改進GAPSO，對模擬退火PSO算法提出了一種新的退火方式，并對改進算法的關鍵參數作了深入分析，給出了PSO算法優化的動態過程，并對目前的各種典型改進PSO方法的仿真結果作了綜合對比，選取的優化函數既有單模態又有多模態，也是優化問題的典型代表，以期對PSO的深入研究作好前期的實驗仿真基礎和分析，并對以后研究PSO算法在各種實際問題中的應用有所幫助。

參考文獻:

[1]KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Piscataway，NJ:IEEE Press， 1995:1942-1948.

[2]PARSOPOULOS K E， VRAHATI M N. On the computation of all global minimizers through particle swarm optimization[J]. IEEE Trans on Evolutionary Computation， 2004， 8(3):211-224.

[3]赫然，王永吉，王青，等. 一種改進的自適應逃逸微粒群算法及實驗分析[J]. 軟件學報， 2005， 16(12):2036-2044.

[4]SHI Y， EBERHAART R C. A modified particle swarm optimizer[C]//Proc of Congress on Evolutionary Computation. Piscataway:IEEE Press， 1998:69-73.

[5]CLERC M. The swarm and the queen:towards a deterministic and adaptive particle swarm optimization[C]//Proc of the ICEC.[S.l.]:IEEE Press， 1999:1951-1957.

[6]胡建秀， 曾建潮. 二階振蕩微粒群算法[J].系統仿真學報， 2007，19(5):997-999.

[7]SUN Jun， FENG Bin， XU Wen-bo. Particle swarm optimization with particles having quantum behavior[C]//Proc of Congress on Evolutionary Computation. 2004:325-331.

[8]竇全勝， 周春光， 馬銘. 粒子群優化的兩種改進策略[J]. 計算機研究與發展， 2005，42(5):897-904.

[9]HUANG T， MOHAN A S. A hybrid boundary condition for robust particle swarm optimization[C]//Proc of IEEE Conference on Antennas and Wireless Propagation Letters. 2005:112-117.

[10]SUN JUN， XU Wen-bo， FENG Bin. Adaptive parameter control for quantum-behaved particle swarm optimization on individual level[C]//Proc of IEEE International Conference on Systems， Man and Cybernetics. 2005:3049-3054.

[11]宋潔，董永峰，侯向丹，等. 改進的粒子群優化算法[J].河北工業大學學報， 2008， 37(4):55-59.

[12]符楊，徐自力，曹家麟. 混合粒子群優化算法在電網規劃中的應用[J].電網技術， 2008， 32(15):31-35.