位置擾動(dòng)的粒子群算法

薛 敬，靳雁霞

（中北大學(xué) 電子與計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山西 太原030051）

0 引 言

粒子群優(yōu)化算法［1］（particle swarm optimization，PSO）是人類(lèi)受到自然界生物活動(dòng)規(guī)律的啟發(fā)而進(jìn)一步研究發(fā)展起來(lái)的全局隨機(jī)優(yōu)化算法，它又被稱為鳥(niǎo)群算法。PSO 算法自誕生以來(lái)，由于其具有的易于理解和操作、收斂速度較快、設(shè)置和調(diào)整的參數(shù)較少等優(yōu)點(diǎn)，在短期內(nèi)得到很大發(fā)展，目前該算法已經(jīng)在數(shù)字圖像處理［2，3］、神經(jīng)網(wǎng)絡(luò)訓(xùn)練［4］、無(wú)線通信技術(shù)［5］、虛擬碰撞檢測(cè)［6］等多個(gè)領(lǐng)域得到了成功應(yīng)用。然而，經(jīng)過(guò)研究人們發(fā)現(xiàn)傳統(tǒng)粒子群算法存在著粒子多樣性差、全局搜索能力差等缺陷和不足。針對(duì)這些問(wèn)題，研究人員提出了相應(yīng)的改進(jìn)算法。文獻(xiàn)［7］通過(guò)改變位置更新公式，使得算法更有效率的達(dá)到收斂。文獻(xiàn)［8］提供了新的學(xué)習(xí)策略，提高了算法全局搜索能力；文獻(xiàn)［9］分析了粒子群搜索的隨機(jī)行為，提出了更有穩(wěn)定性和收斂性的算法。

本文從優(yōu)化群體最優(yōu)位置的角度出發(fā)，提出了對(duì)基本粒子群算法的改進(jìn)算法。在粒子進(jìn)化過(guò)程中，群體最優(yōu)位置接受其它各粒子最優(yōu)位置在某些維上已經(jīng)搜索到的位置數(shù)據(jù)的擾動(dòng)，從而達(dá)到了跳出局部最優(yōu)和增強(qiáng)全局搜索能力的目的。

1 基本粒子群算法

基本粒子群算法采用的是群體和優(yōu)化的概念［10］，這也和其它很多優(yōu)化算法相類(lèi)似。PSO 算法區(qū)別于其它優(yōu)化算法的地方在于，它沒(méi)有針對(duì)個(gè)體使用淘汰的進(jìn)化算子，而是將所有個(gè)體都當(dāng)作是在空間內(nèi)飛行的鳥(niǎo)，它們不會(huì)被其它粒子替代，且以一定的速度在空間中飛行尋優(yōu)。在算法中，設(shè)Xi＝（xi1，xi2，…xin）來(lái)表示粒子i的在當(dāng)前搜索空間中的位置；Vi＝（vi1，vi2，…vin）來(lái)表示粒子i在當(dāng)前搜索空間中的速度；Pi＝（pi1，pi2，…pin）來(lái)表示粒子i自身最優(yōu)位置；Pg＝（pg1，pg2，…pgn）來(lái)表示群體經(jīng)歷最優(yōu)位置或者粒子i鄰域中的最優(yōu)位置。

PSO 算法中各個(gè)粒子將按式（1）、式（2）改變速度和位置

上述式（1）、式（2）中，c1為粒子向自身學(xué)習(xí)的權(quán)重系數(shù)，c2為粒子向群體經(jīng)驗(yàn)學(xué)習(xí)的權(quán)重系數(shù)；r1、r2一般為介于（0，1）之間相互獨(dú)立的正態(tài)隨機(jī)數(shù)，它們的共同作用是動(dòng)態(tài)隨機(jī)調(diào)節(jié)粒子向自身學(xué)習(xí)和向群體學(xué)習(xí)的權(quán)重，保證了算法的隨機(jī)性。通過(guò)設(shè)置各個(gè)粒子的速度范圍區(qū)間［vmax，vmin］和位置范圍區(qū)間［xmax，xmin］，便可以對(duì)粒子的搜索和移動(dòng)加以適當(dāng)?shù)南拗啤?/p>

2 改進(jìn)的位置擾動(dòng)粒子群算法

2.1 PDPSO 算法基本思想

粒子群算法在N 維空間搜索時(shí)，每次迭代后都會(huì)產(chǎn)生粒子i 自身最優(yōu)位置Pibest和群體經(jīng)歷的最優(yōu)位置Pgbest，Pgbest并不代表在搜索空間的每一維上都在最優(yōu)位置，相反，Pibest有時(shí)候可能會(huì)在某些維上比Pgbest更接近理論的最優(yōu)位置。通過(guò)對(duì)粒子自身位置隨機(jī)維的計(jì)算產(chǎn)生擾動(dòng)，可以在這些維上對(duì)Pgbest有積極的影響，使得搜索跳出局部最優(yōu)，同時(shí)提高了尋優(yōu)的收斂精度。

2.2 基于加權(quán)計(jì)算的擾動(dòng)

為了實(shí)現(xiàn)算法，一方面，抽出個(gè)體最優(yōu)位置適應(yīng)值僅次于P′gbest的M 個(gè)粒子作為擾動(dòng)粒子，M 可根據(jù)粒子總數(shù)目和具體研究問(wèn)題目標(biāo)而定。記下它們的自身最優(yōu)位置（gbest1，gbest2，……，gbestM）和所對(duì)應(yīng)的適應(yīng)值（fitgbest1，fitgbest2，……，fitgbestM）。隨機(jī)選取R 個(gè)不同的維，處理具體問(wèn)題時(shí)，可以通過(guò)搜索空間的維數(shù)N 來(lái)選擇R 的大小。通過(guò)分別對(duì)這些擾動(dòng)粒子R 個(gè)維上的加權(quán)計(jì)算，得到計(jì)算結(jié)果之后，以計(jì)算結(jié)果為均值，生成正態(tài)隨機(jī)擾動(dòng)對(duì)Pgbest的相應(yīng)的R 個(gè)維上擾動(dòng)。令生成的擾動(dòng)值代替Pgbest對(duì)應(yīng)維上的值，具體來(lái)說(shuō)，如果第n維屬于被選中的R 個(gè)維，那么對(duì)于第n 維而言，則有zbestn＝rn。若被擾動(dòng)后P′gbest的適應(yīng)值好于擾動(dòng)前Pgbest的適應(yīng)值，即f（P′gbest）優(yōu)于f（Pgbest），則接受擾動(dòng)進(jìn)化，令Pgbest＝P′gbest，并重新記下f（P′gbest）作為全局最優(yōu)值，反之，則拒絕擾動(dòng)進(jìn)化，保持原有數(shù)據(jù)。

其中，zbestn為粒子群體最優(yōu)位置第n 維上的值，式（3）為第n維上擾動(dòng)粒子的加權(quán)值μn 的計(jì)算公式，式（4）為第n維生成正態(tài)隨機(jī)擾動(dòng)rn的公式。R 是小于N 的正整數(shù)

式（3）中，gbesti，n為第i 個(gè)粒子個(gè)體最優(yōu)位置第n 維上的值。式（4）中，σ2為正態(tài)分布的方差，其取值規(guī)則滿足式（5）

2.3 基于平均值計(jì)算的擾動(dòng)

為了實(shí)現(xiàn)算法，另一方面，挑選出每一個(gè)粒子的自身最優(yōu)位置中隨機(jī)的Q 個(gè)維，分別求出Q 個(gè)維的算數(shù)平均值，處理具體問(wèn)題時(shí)，可以根據(jù)具體搜索空間的維數(shù)大小來(lái)選擇Q 值的大小。并通過(guò)這些算術(shù)平均值產(chǎn)生正態(tài)隨機(jī)擾動(dòng)值對(duì)Pgbest對(duì)應(yīng)的Q 個(gè)維上進(jìn)行擾動(dòng)，即令生成的Q 個(gè)維上擾動(dòng)值代替Pgbest對(duì)應(yīng)維上的值，具體來(lái)說(shuō)，如果第n維屬于被選中的Q 個(gè)維，那么對(duì)第n維而言，則有zbestn＝rn。若被擾動(dòng)后P′gbest的適應(yīng)值好于擾動(dòng)前Pgbest的適應(yīng)值，即f（P′gbest）優(yōu)于f（Pgbest），則接受擾動(dòng)進(jìn)化，令Pgbest＝P′gbest，并重新記下f（P′gbest）作為全局最優(yōu)值，反之，則拒絕擾動(dòng)進(jìn)化，保持原有數(shù)據(jù)。

其中，式（6）為第n 維上算術(shù)平均值averagen計(jì)算公式，式（7）為第n維生成正態(tài)隨機(jī)擾動(dòng)rn的公式。Q 是小于N 的正整數(shù)

式（6）中，sizepop 為群體的總粒子數(shù)。在式（7）中，σ2為正態(tài)分布的方差，其取值規(guī)則滿足式（5）。

2.4 算法實(shí)現(xiàn)步驟

步驟1 選定算法所必須的參數(shù)，隨機(jī)初始化各粒子的位置和速度參數(shù)。

步驟2 根據(jù)約束函數(shù)算出粒子的具體適應(yīng)值，并且記錄每個(gè)粒子的個(gè)體最優(yōu)位置和粒子群的群體最優(yōu)位置。

步驟3 選出個(gè)體最優(yōu)位置適應(yīng)值僅次于Pgbest的M 個(gè)粒子作為擾動(dòng)粒子，通過(guò)式（3）、式（4）、式（5）產(chǎn)生對(duì)Pgbest的R 個(gè)維上的擾動(dòng)值，若擾動(dòng)后P＇gbest的滿足進(jìn)化條件，則接受擾動(dòng)進(jìn)化，反之，則拒絕。

步驟4 隨機(jī)選出個(gè)體最優(yōu)位置的Q 個(gè)維，通過(guò)式（5）、式（6）、式（7）產(chǎn)生對(duì)Pgbest相應(yīng)維上的擾動(dòng)值，若擾動(dòng)后P′gbest滿足進(jìn)化條件，則接受擾動(dòng)進(jìn)化，反之，則拒絕。

步驟5 根據(jù)式（1）、式（2）在每一代進(jìn)化后更新粒子的速度與位置參數(shù)。

步驟6 判斷尋優(yōu)結(jié)果是否滿足尋優(yōu)停止條件，若不滿足條件，則重新返回去執(zhí)行步驟2；若滿足，則接著執(zhí)行步驟7。

步驟7 輸出最終尋優(yōu)結(jié)果。

3 算法仿真測(cè)試與實(shí)驗(yàn)

3.1 基本測(cè)試函數(shù)

測(cè)試實(shí)驗(yàn)選擇了幾個(gè)性質(zhì)不同的基本測(cè)試函數(shù)對(duì)PSO和PDPSO 兩個(gè)算法進(jìn)行了測(cè)試仿真，主要目標(biāo)是測(cè)試兩個(gè)算法對(duì)單峰值函數(shù)和多峰值函數(shù)，尤其是多峰值函數(shù)搜索精度和全局尋優(yōu)能力，并通過(guò)測(cè)試結(jié)果，對(duì)比兩個(gè)算法對(duì)相同函數(shù)的全局尋優(yōu)的精度和能力。

下面的F1、F2、F3、F4 是測(cè)試選擇的4 個(gè)用于兩個(gè)優(yōu)化算法進(jìn)行比較的基準(zhǔn)函數(shù)。

Sphere函數(shù)，它在（x1，x2…xi）＝0時(shí)達(dá)到全局的最小值0。

Ackley函數(shù)，函數(shù)在搜索空間中存在著大量的局部極小值點(diǎn)，當(dāng)（x1，x2…xi）＝0時(shí)達(dá)到全局的最小值0。

Rastrigrin函數(shù)，函數(shù)在搜索空間中有大量正弦凸起的局部極小值點(diǎn)，當(dāng)（x1，x2…xi）＝0時(shí)達(dá)到全局的最小值0。

Levy函數(shù)，函數(shù)是一個(gè)有著很多個(gè)局部最小值的多峰值函數(shù)。當(dāng)（x1，x2…xi）＝1時(shí)達(dá)到全局的最小值0。

3.2 測(cè)試參數(shù)

測(cè)試取最大迭代次數(shù)gen0＝2000，PSO 和PDPSO 算法中ω都取0.8，且c1＝c2＝2，粒子群規(guī)模sizepop＝30，搜索空間維數(shù)N＝10。PDPSO 算法中，擾動(dòng)粒子數(shù)目M＝2，擾動(dòng)維的數(shù)目R＝Q＝2，初始正態(tài)方差＝5，正態(tài)截止方差＝0.05。迭代結(jié)束條件是，當(dāng)進(jìn)化代數(shù)大于最大迭代次數(shù)時(shí)，停止迭代并輸出最終結(jié)果。

3.3 測(cè)試仿真結(jié)果

在測(cè)試環(huán)節(jié)中，為了方便在不同算法之間的考察比較，測(cè)試用每一種算法在同一個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行50次，記錄并且計(jì)算出這50次測(cè)試搜索尋優(yōu)結(jié)果中的最優(yōu)值、平均值、最差值，以及每種算法在各測(cè)試函數(shù)中的穩(wěn)定性，即算法滿足在誤差范圍的精度以內(nèi)的比例。

函數(shù)的最優(yōu)位置、最優(yōu)值和誤差范圍見(jiàn)表1。

表1 4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)最優(yōu)值及其誤差范圍

測(cè)試具體數(shù)據(jù)見(jiàn)表2。

表2 4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的測(cè)試結(jié)果對(duì)比

由表2可得到結(jié)論：一方面，雖然PSO 和PDPSO 兩種算法對(duì)于單峰值函數(shù)F1都具有很精確的收斂精度，但是PDPSO 算法卻有略高的收斂精度和穩(wěn)定性。另一方面，測(cè)試結(jié)果表明，對(duì)于多峰值函數(shù)F2、F3、F4，PSO 算法的搜索結(jié)果精度并不理想，而PDPSO 算法卻有著比較相對(duì)很高的收斂精度和穩(wěn)定性，也就是說(shuō)，在處理多峰值優(yōu)化問(wèn)題時(shí)，PDPSO 算法有著明顯優(yōu)于PSO 算法的尋優(yōu)精度和能力，針對(duì)于一些函數(shù)和問(wèn)題，它能夠讓收斂精度提高成千上萬(wàn)倍。

為了進(jìn)一步對(duì)比和說(shuō)明PDPSO 算法良好的尋優(yōu)能力，測(cè)試通過(guò)圖片對(duì)比了PSO 和PDPSO 算法應(yīng)用于同一約束函數(shù)的收斂曲線。如圖1～圖3所示，圖中坐標(biāo)軸橫半軸表示迭代次數(shù)，縱半軸表示適應(yīng)值。

由圖1～圖3可以看出：在尋優(yōu)過(guò)程中，當(dāng)PSO 算法處理多峰值函數(shù)出現(xiàn)了停滯，陷入了局部最優(yōu)值的時(shí)候，便已經(jīng)很難從局部最優(yōu)中跳出，結(jié)果只能收斂于局部極值點(diǎn)，這是由于其全局搜索能力不夠造成的。而PDPSO 有著更強(qiáng)的跳出局部最優(yōu)值的能力，它在進(jìn)化過(guò)程中，能夠讓粒子進(jìn)一步在解空間的其它區(qū)域中搜索尋優(yōu)，使得進(jìn)化繼續(xù)進(jìn)行下去，具有更強(qiáng)的全局搜索能力。

圖1 十維Ackley函數(shù)對(duì)比

圖2 十維Rastrigrin函數(shù)對(duì)比

圖3 十維Levy函數(shù)對(duì)比

4 結(jié)束語(yǔ)

PDPSO 算法通過(guò)采用個(gè)體最優(yōu)位置產(chǎn)生擾動(dòng)值對(duì)全局最優(yōu)位置擾動(dòng)進(jìn)化的思想方法，使得粒子群的粒子在每代更新時(shí)，全局最優(yōu)位置也能有條件的向個(gè)體最優(yōu)位置學(xué)習(xí)，充分發(fā)揮了粒子個(gè)體最優(yōu)位置的更大效用，達(dá)到了全局最優(yōu)位置和個(gè)體最優(yōu)位置互相學(xué)習(xí)的效果。有了這樣的改變，PDPSO 算法也克服了基本PSO 算法的全局搜索能力不強(qiáng)、容易陷入局部極值點(diǎn)而無(wú)法跳出、對(duì)于有些函數(shù)問(wèn)題搜索精度不高等不足之處。最后，測(cè)試實(shí)驗(yàn)的事實(shí)證明：PDPSO 的確比基本PSO 具有更強(qiáng)的全局搜索尋優(yōu)能力和收斂精度。

［1］JI Zhen，LIAO Huilian，WU Qinghua.The particle swarm optimization and application ［M］.Beijing：Science Press，2009：16－80 （in Chinese）.［紀(jì)震，廖惠連，吳青華.粒子群優(yōu)化算法及應(yīng)用 ［M］.北京：科學(xué)出版社，2009：16－80.］

［2］Muruganandham A，Wahida Banu Dr R S D.Adaptive fractal image compression using PSO ［J］.Procedia Computer Science，2010，2：338－344.

［3］WEI Ding.A new method for image noise removal using chaos－PSO and nonlinear ICA ［J］.Procedia Engineering，2011，24：111－115.

［4］YU Zhifu，LI Junwu，LIU Kai.Radar emitter recognition based on PSO－BP network ［J］.AASRI Procedia，2012 （1）：213－219.

［5］HU Yu，WANG Xiaohui.PSO－based energy－balanced double cluster－h(huán)eads clustering routing for wireless sensor networks［J］.Procedia Engineering，2011，15：3073－3077.

［6］LI Wenhui，WANG Tianzhu，WANG Yi，et al.Stochastic collision detection between deformable models using particle swarm optimization algorithm ［J］.Journal of System Simulation，2006，18 （8）：2206－2209 （in Chinese）. ［李文輝，王天柱，王祎，等.基于粒子群面向可變形物體的隨機(jī)碰撞檢測(cè)算法 ［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18 （8）：2206－2209.］

［7］ZHU Tong，LI Xiaofan，ZHU Mingwen.Improved particle swarln optimization algorithm with position weighted ［J］.Computer Engineering and Applications，2011，47 （5）：4－6（in Chinese）.［朱童，李小凡，朱明文.位置加權(quán)的改進(jìn)粒子群算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47 （5）：4－6.］

［8］XIE Zhenggui，ZHONG Shaodan，WEI Yuke.Modified particle swarm optimization algorithm and its convergence analysis［J］.Computer Engineering and Applications，2011，47 （1）：46－49 （in Chinese）.［謝錚桂，鐘少丹，韋玉科.改進(jìn)的粒子群算法及收斂性分析 ［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（1）：46－49.］

［9］WU Xiaojun，YANG Zhanzhong，ZHAO Ming.A uniform searching particle swarm optimization algorithm ［J］.Acta Electronica Sinica，2011，39 （6）：1261－1266 （in Chinese）.［吳曉軍，楊戰(zhàn)中，趙明.均勻搜索粒子群算法 ［J］.電子學(xué)報(bào)，2011，39 （6）：1261－1266.］

［10］ZENG Jianchao，JIE Jing，CUI Zhihua.Particle swarm optimization algorithm ［M］.Beijing：Science Press，2004 （in Chinese）.［曾建潮，介婧，崔志華.微粒群算法 ［M］.北京：科學(xué)出版社，2004.］