李承 許江寧 張文成

（海軍工程大學(xué)導(dǎo)航工程系，武漢 430033）

0 引 言

粒子群優(yōu)化算法[1]（PSO）是由 Kennedy與Eberhart于1995年提出的一種群體智能算法，用來(lái)模擬鳥(niǎo)群覓食的過(guò)程。PSO概念簡(jiǎn)單易懂，收斂速度快且代碼實(shí)現(xiàn)容易，在優(yōu)化及演化計(jì)算等領(lǐng)域引起許多學(xué)者的關(guān)注，成為一種解決非線性優(yōu)化問(wèn)題、組合優(yōu)化問(wèn)題與混合非線性問(wèn)題等方面的重要優(yōu)化工具和優(yōu)化方法。針對(duì)粒子群算法本身存在的不足，學(xué)者們提出了很多改進(jìn)方法[2-7]，通過(guò)引入慣性權(quán)重的概念，發(fā)展出來(lái)的標(biāo)準(zhǔn)粒子群算法成為最通用的一種。標(biāo)準(zhǔn)粒子群算法在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模式分類和模糊控制等方面得到了廣泛的應(yīng)用，國(guó)內(nèi)相關(guān)研究則始于2001年。

本文提出的利用算法的初始化策略提高算法的性能，并不改變算法的尋優(yōu)策略和基本原理，因而對(duì)各種改進(jìn)的粒子群算法有普適性。經(jīng)實(shí)驗(yàn)仿真證明，該方法能夠改善幾種改進(jìn)粒子群算法的尋優(yōu)成功率和收斂速度，明顯提高了算法性能。

1 標(biāo)準(zhǔn)粒子群優(yōu)化算法概述

粒子群優(yōu)化方法提出之后，有很多學(xué)者都對(duì)基本算法進(jìn)行了大量的研究。針對(duì)粒子群算法容易陷入局部最優(yōu)的問(wèn)題，提出了很多的改進(jìn)方法。Shi與Eberhart提出了帶慣性權(quán)重的粒子群算法，此種改進(jìn)方法被學(xué)者稱為標(biāo)準(zhǔn)粒子群算法[2-4]（Standard Particle Swarm Optimization，SPSO），是目前粒子群算法研究和改進(jìn)的基礎(chǔ)。設(shè)一個(gè)D維目標(biāo)空間，群體規(guī)模為 m，xi=(zi1,zi2,…,ziD)為第i個(gè)粒子的D維位置矢量，vi=(vi1,vi2,…,viD)為粒子i的D維速度矢量，pBesti是粒子當(dāng)前最優(yōu)位置，gBesti是群當(dāng)前最優(yōu)位置，SPSO算法的可表示為：

其中，i=1,2,…,m，d=1,2,…,D。慣性權(quán)重ω作為慣性部分，可以權(quán)衡算法全局能力和局部能力。r1、r2是[0,1]之間的隨機(jī)數(shù)，用來(lái)保持群體的多樣性。c1、c2被稱為學(xué)習(xí)因子，代表粒子的自身部分和社會(huì)認(rèn)知部分。

慣性權(quán)重的引入使粒子群算法的性能大大提高。SPSO算法的特點(diǎn)是原理簡(jiǎn)單，易于實(shí)現(xiàn)，需要調(diào)整的參數(shù)少，也不需要任何的梯度信息，特別是在非線性優(yōu)化、組合優(yōu)化和混合整數(shù)非線性優(yōu)化上具有很大的優(yōu)勢(shì)。

2 幾種改進(jìn)的粒子群優(yōu)化算法

2.1 線性遞減慣性權(quán)重粒子群算法

Shi將慣性權(quán)重取值為常數(shù)，仿真結(jié)果表明，ω在[0.8，1.2]之間時(shí)，PSO 算法有更快的收斂速度，而當(dāng)ω>1.2時(shí)，算法則較多地陷入局部極值。由于在一般的全局優(yōu)化算法中，希望前期具有較高的全局搜索能力，而在后期有較高的開(kāi)發(fā)能力，所以動(dòng)態(tài)慣性權(quán)重隨著算法迭代的進(jìn)行而線性減小，算法的收斂性能得以改善。目前采用較多的慣性權(quán)重策略，是 Shi 建議的線性遞減權(quán)值(linearly decreasing weight，簡(jiǎn)稱 LDW)策略[1]。

式中，ωmax和ωmin是慣性權(quán)重的最大值與最小值；kmax和 k分別是最大迭代次數(shù)和當(dāng)前迭代次數(shù)。慣性權(quán)重取值由式（3）給出，Shi等通過(guò)實(shí)驗(yàn)證明，將ω設(shè)置為從0.9到0.4線性下降，可以使PSO算法更好的控制全局搜索能力和局部搜索能力，加快了收斂速度，能夠提高算法性能。目前這種慣性權(quán)重線性遞減策略應(yīng)用最為廣泛，除此之外還有很多學(xué)者提出多種不同慣性權(quán)重策略，如線性微分遞減策略、帶閥值的非線性遞減策略、非線性動(dòng)態(tài)改進(jìn)慣性權(quán)重策略、基于正切和反正切函數(shù)的慣性權(quán)重改進(jìn)策略和模型調(diào)整ω的策略等，這些改進(jìn)都使算法性能在不同方面有所提高。

通過(guò)調(diào)整慣性權(quán)重可以改進(jìn)算法的性能，ω的大小決定了算法的全局搜索能力和局部搜索能力。ω較大則算法全局搜索能力強(qiáng)，ω較小則算法局部開(kāi)發(fā)能力強(qiáng)，因此控制ω是改進(jìn)算法的一種重要途徑。

2.2 自適應(yīng)慣性權(quán)重粒子群算法

APSO算法的基本思想是通過(guò)追蹤粒子當(dāng)前目標(biāo)適應(yīng)值和全局最優(yōu)值，控制每個(gè)粒子的慣性權(quán)重。離當(dāng)前最優(yōu)解遠(yuǎn)的粒子獲得的慣性權(quán)重值就大，從而加快粒子的飛行速度及算法的開(kāi)拓能力；而離當(dāng)前最優(yōu)解近的粒子獲得的慣性權(quán)重值就小，從而增加粒子的發(fā)掘能力。自適應(yīng)慣性權(quán)重策略可由式（4）給出：

3 利用初始化提高算法性能

3.1 初始化策略

在對(duì)各種改進(jìn)的粒子群優(yōu)化算法進(jìn)行大量實(shí)驗(yàn)測(cè)試過(guò)程中，發(fā)現(xiàn)了一些對(duì)算法尋優(yōu)能力有影響的其他因素，比如粒子群位置的初始化和求解問(wèn)題的維數(shù)。各種粒子群算法一般對(duì)粒子初始位置和速度沒(méi)有特殊要求，但是在已知優(yōu)化問(wèn)題的搜索范圍時(shí)，可以通過(guò)調(diào)整粒子初始位置和速度達(dá)到提高算法收斂速度的目的。

經(jīng)過(guò)大量實(shí)驗(yàn)發(fā)現(xiàn)，對(duì)于限定搜索范圍的優(yōu)化問(wèn)題，在粒子初始化時(shí)以位于搜索空間內(nèi)的隨機(jī)數(shù)對(duì)其初始位置賦值，這樣既縮小了粒子起飛時(shí)到最優(yōu)位置的距離，又保證了粒子群在搜索空間內(nèi)充分發(fā)散，可以節(jié)約飛行時(shí)間，并提高尋優(yōu)能力。因此，在已知算法搜索范圍的情況下，本文用 xmax×rand()或者 xmax/2×rand()代替 randn()對(duì)粒子的初始位置進(jìn)行賦值，用 vmax×rand()代替randn()對(duì)粒子初始化粒子速度。

3.2 實(shí)驗(yàn)驗(yàn)證

為了更好的反應(yīng)粒子位置新的初始化策略對(duì)算法性能的影響，實(shí)驗(yàn)采用給定最大迭代次數(shù)和最優(yōu)解的模式，以算法精確找到最優(yōu)解為終止條件，執(zhí)行測(cè)試算法。當(dāng)達(dá)到最大迭代次數(shù)時(shí)或達(dá)到最大迭代次數(shù)前，算法找到最優(yōu)解，則認(rèn)為算法尋優(yōu)成功。改進(jìn)算法初始化策略的目的是提高算法的尋優(yōu)能力，即算法搜索最優(yōu)解的成功率、收斂速度和準(zhǔn)確度。因此采用如下指標(biāo)[8]：搜索成功率、平均迭代次數(shù)和平均最優(yōu)適應(yīng)值。

搜索成功率：進(jìn)行T次實(shí)驗(yàn)，如果有t次實(shí)驗(yàn)成功，則成功率可表示為t/T×100%，此處所說(shuō)的搜索成功是指成功搜索到精確解，不是表示算法的收斂概率。

平均迭代次數(shù)：T次實(shí)驗(yàn)中，所有成功實(shí)驗(yàn)迭代次數(shù)算術(shù)平均值。

平均最優(yōu)適應(yīng)值：T次實(shí)驗(yàn)所得目標(biāo)函數(shù)最優(yōu)值的算術(shù)平均值。

標(biāo)準(zhǔn)差：T次實(shí)驗(yàn)中算法所得最優(yōu)解的標(biāo)準(zhǔn)差。

表示算法尋優(yōu)結(jié)果的斂散性；選取一個(gè)典型單峰函數(shù) Sphere函數(shù)和一個(gè)典型多峰函數(shù) Rastrigrin函數(shù)，測(cè)試不同改進(jìn)粒子群算法采用本文提出的初始化方法時(shí)的性能。

(1)Sphere函數(shù)

(2)Rastrigrin函數(shù)

Sphere函數(shù)是非線性對(duì)稱的單峰函數(shù)，不同維之間是可分離的。Rastrigrin函數(shù)是非線性多極值函數(shù)，存在大量按余弦排列的、很深的局部最優(yōu)點(diǎn)。變量之間無(wú)任何相關(guān)性，其局部最優(yōu)點(diǎn)隨著余弦波動(dòng)，很容易使算法陷入到局部最優(yōu)點(diǎn)，而得不到全局最優(yōu)解。

測(cè)試時(shí)不仿選取LWPSO和APSO兩種算法，分別將其初始化策略改進(jìn)前后的算法性能進(jìn)行對(duì)比，進(jìn)行 10次運(yùn)算求平均值。令問(wèn)題維度為D=20，種群規(guī)模M=30，最大迭代次數(shù)為N=2000，學(xué)習(xí)因子c1=2，c2=2，測(cè)試結(jié)果見(jiàn)表1。

為了更直觀的反映不同算法的性能，圖 1～圖4分別給出了LWPSO和APSO算法初始化策略改進(jìn)前后，對(duì)文中兩個(gè)函數(shù)進(jìn)行測(cè)試時(shí)的平均適應(yīng)度值收斂情況（為了便于觀察只給出了迭代早期變化明顯的部分）。

圖1和圖2所示為L(zhǎng)WPSO算法采用不同初始化策略時(shí)，對(duì)Sphere函數(shù)和Rastrigrin函數(shù)的尋優(yōu)結(jié)果。

圖3和圖4所示為 APSO算法采用不同初始化策略時(shí)，對(duì)Sphere函數(shù)和Rastrigrin函數(shù)的尋優(yōu)結(jié)果。

表1 Sphere函數(shù)測(cè)試結(jié)果對(duì)比

表2 Rastrigrin函數(shù)測(cè)試結(jié)果對(duì)比

圖1 LWPSO對(duì)Sphere函數(shù)的優(yōu)化過(guò)程

圖2 LWPSO對(duì)Rastrigrin函數(shù)的優(yōu)化過(guò)程

圖3 APSO對(duì)Sphere函數(shù)的優(yōu)化過(guò)程

圖4 APSO 對(duì)Rastrigrin函數(shù)的優(yōu)化過(guò)程

由表1、表2和圖1-圖4的結(jié)果可以看出，在本文提出的算法初始化策略下，LWPSO和APSO算法對(duì)典型單峰函數(shù)和多峰函數(shù)尋優(yōu)時(shí)，算法的收斂速度和搜索成功率，都得到了大大提高。

4 結(jié)論

本文針對(duì)解決控制領(lǐng)域優(yōu)化問(wèn)題的粒子群算法存在的問(wèn)題，提出了一種算法的初始化策略，以提高優(yōu)化算法的性能。通過(guò) LWPSO和 APSO算法對(duì)典型函數(shù)的測(cè)試，結(jié)果證明在本文提出的初始化策略下，算法收斂速度、搜索成功率和搜索精度得到了大大提高，這說(shuō)明本文提出的方法是有效的。

[1]紀(jì)震，廖惠連，吳青華. 粒子群優(yōu)化算法及應(yīng)用[M].北京: 科學(xué)出版社, 2009:16-80.

[2]Zhang L P,Yu H J, Hu S X. A new approach to improve particle swarm optimization [C]. Lecture Notes in Computer Science. Chicago: Springer Verlag,2006: 1036-1043.

[3]鄧愛(ài)萍，王會(huì)芳. 動(dòng)態(tài)改變慣性權(quán)重的自適應(yīng)粒子群算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2010, 31(13):3062-3065.

[4]潘峰,陳杰,甘明剛等. 粒子群優(yōu)化算法模型分析[J].自動(dòng)化學(xué)報(bào), 2006, 32(3): 368-377.

[5]林川,馮全源. 粒子群優(yōu)化算法的信息共享策略[J].西南交通大學(xué)學(xué)報(bào), 2009, 44(3): 437-441.

[6]張朝龍，江巨浪，江善和等. 一種自適應(yīng)混合粒子群優(yōu)化算法及其應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用研究, 2011,28(5): 1696-1698.

[7]張頂學(xué). 遺傳算法與粒子群算法的改進(jìn)及應(yīng)用[D].武漢：華中科技大學(xué)， 2007.

[8]F V den Bergh, A P Engelbrecht. A study of particle swarm optimization particle trajectories [J]. Inf. Sci.,2006, 176(8): 937-971.