薛 敬，靳雁霞

（中北大學 電子與計算機科學技術學院，山西 太原030051）

0 引 言

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

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

1 基本粒子群算法

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

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

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

2 改進的位置擾動粒子群算法

2.1 PDPSO 算法基本思想

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

2.2 基于加權計算的擾動

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

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

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

2.3 基于平均值計算的擾動

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

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

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

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

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

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

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

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

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

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

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

3 算法仿真測試與實驗

3.1 基本測試函數(shù)

測試實驗選擇了幾個性質不同的基本測試函數(shù)對PSO和PDPSO 兩個算法進行了測試仿真，主要目標是測試兩個算法對單峰值函數(shù)和多峰值函數(shù)，尤其是多峰值函數(shù)搜索精度和全局尋優(yōu)能力，并通過測試結果，對比兩個算法對相同函數(shù)的全局尋優(yōu)的精度和能力。

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

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

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

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

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

3.2 測試參數(shù)

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

3.3 測試仿真結果

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

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

表1 4個標準測試函數(shù)最優(yōu)值及其誤差范圍

測試具體數(shù)據(jù)見表2。

表2 4個標準測試函數(shù)的測試結果對比

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

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

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

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

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

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

4 結束語

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

［1］JI Zhen，LIAO Huilian，WU Qinghua.The particle swarm optimization and application ［M］.Beijing：Science Press，2009：16－80 （in Chinese）.［紀震，廖惠連，吳青華.粒子群優(yōu)化算法及應用 ［M］.北京：科學出版社，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］.系統(tǒng)仿真學報，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）.［朱童，李小凡，朱明文.位置加權的改進粒子群算法 ［J］.計算機工程與應用，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］.計算機工程與應用，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］.電子學報，2011，39 （6）：1261－1266.］

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