楊洪濤 丁烽

（第七一五研究所，杭州，310023）

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是由 Kenedy和Eberhart 于1995年提出的一種基于集體演化的隨機搜索優(yōu)化方法[1]。算法的基本思想是模仿鳥群的覓食特性，是群體中個體之間信息的社會共享和協(xié)同進化。PSO在諸多優(yōu)化領(lǐng)域取得了比較成功的結(jié)果，例如函數(shù)優(yōu)化[2]、系統(tǒng)辨識[3]、人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練[4]等。但是PSO容易發(fā)生早熟收斂而陷入局部最優(yōu)和在最優(yōu)值附近收斂緩慢。學(xué)者對于粒子群算法進行了改進：引入動態(tài)參數(shù)修正策略，對演化方程加入隨機擾動策略，而后其他算法進行融合，以及將以上改進相互混合。文獻[5]提出了基于自適應(yīng)觀點的慣性權(quán)重改進方式。文獻[6]考慮前兩代位置對速度方程進行改進。文獻[7]消除了方程的粒子速度項而使得原來的二階微分方程簡化為一階微分方程，避免有粒子速度項引起的粒子發(fā)散而導(dǎo)致收斂慢、精度低的問題。通過分析我們發(fā)現(xiàn)，粒子群算法對于初值的選取十分敏感，當(dāng)粒子集中于求解區(qū)域一端時間，對于另一端的空間的探測能力較弱，這極大的影響了粒子群算法的求解能力，尤其在求解空間較大且較為復(fù)雜的情況下。針對這一情況本文提出具有斥力-引力作用的粒子群優(yōu)化算法，使得粒子在下一步迭代過程中，主動避開已有粒子的探測具有增大粒子的空間拓展能力，降低算法對于初值的依賴性。

1 標準粒子群優(yōu)化算法

1.1 算法描述

假設(shè)在一個D維的空間進行搜索，粒子種群X有n個粒子，表示為(X1,X2,…Xn)，其中第i個粒子表示為一個D維向量Xi=(x1,x2,…xD)T，為搜索空間的一個探索解。根據(jù)目標函數(shù)即可算出每個粒子當(dāng)前位置的適應(yīng)度值。第i個粒子的速度為其個體經(jīng)驗極值為種群的群體經(jīng)驗極值為

在每個迭代過程中，粒子通過自身初始運動速度、自身經(jīng)驗極值和群體經(jīng)驗極值協(xié)同決定下一次的運動速度。并更新運動位置以及運動速度

其中，ω為慣性權(quán)重；k為當(dāng)前迭代次數(shù)；Vid為粒子的速度；c1和c2是非負常數(shù)，稱為加速度因子；r1和r是分布于[0,1]區(qū)間的隨機數(shù)。

1.2 算法偽代碼

經(jīng)典粒子群算法的通過迭代更新速度矢量和位移矢量（Algorithm 1:10-11），并通過不斷將粒子群當(dāng)前狀態(tài)與歷史狀態(tài)的個體最優(yōu)中和群體最優(yōu)，使得群體最優(yōu)值逐步收斂到全局最優(yōu)值（Algorithm 1: 6-7），偽代碼如下

2 改進模型

2.1 模型背景

我們通過對于鳥群覓食過程的分析可以發(fā)現(xiàn)，初期階段，每只鳥由于自身的“好奇心理”都會主動探索無“鳥”區(qū)域，并努力避開其他鳥類的探索位置，這種“好奇心理”使得種群更加快速高效全面的探索覓食區(qū)域。而隨著覓食時間的延續(xù)，“好奇心理”逐漸減弱。在覓食后期，鳥群更傾向于回歸種群，并在回歸過程中繼續(xù)探索覓食區(qū)域。次過程可以抽象為粒子間的吸引排斥作用。由經(jīng)典的分子力學(xué)可知，分子間同時存在吸引作用與排斥作用，這樣可以使得每個分子在自己的工作區(qū)域內(nèi)保持振動。我們將經(jīng)典的斥力作用和引力作用引入模型。

2.2 數(shù)學(xué)模型構(gòu)造

將單個個體在初期搜索階段的排它性表現(xiàn)為對于附近個體的斥力作用，并且要求當(dāng)兩個個體越近時斥力表現(xiàn)越明顯。在此基礎(chǔ)上，斥力作用應(yīng)當(dāng)隨著探索時間的延長逐漸減弱并且逐步轉(zhuǎn)化為引力作用。通過公式可以表示為：

其中：c3為某正常數(shù)參數(shù)；r3是分布于[0,1]區(qū)間的隨機數(shù)；Rn為衰減項，滿足n=1時R1=1，當(dāng)n達到最大迭代次數(shù)為第i個粒子和第j個粒子間的距離；為第i個粒子和第j個粒子間的位移差。由于斥力項具有較強的非線性結(jié)構(gòu)，斥力項的影響力強弱依賴于的選取，為了使得粒子群系統(tǒng)能夠穩(wěn)定迭代，在c3選取時應(yīng)使其遠小于c1、c2。

圖1 粒子斥力作用圖

粒子斥力作用示意圖見圖1。斥力因素的引入可以使得粒子更快的拓展求解區(qū)域，降低由于粒子的聚集狀態(tài)所導(dǎo)致的局部最優(yōu)。而后期引力因素將提高粒子群局部搜索能力并提升收斂速度。在此基礎(chǔ)上，有別于傳統(tǒng)粒子群算法對于初值的敏感性，新的粒子群算法對于初值的選擇并不敏感。即便初始粒子選擇區(qū)域較小，由于互斥效應(yīng)的影響，粒子群也將向著為空曠區(qū)域逐步擴散。

2.3 改進PSO算法

由于互斥效應(yīng)的引入，粒子迭代公式變?yōu)椋?/p>

2.4 改進算法偽代碼

在粒子群算法基礎(chǔ)上為使得粒子群在初始階段能夠快速擴張求解區(qū)域，我們在經(jīng)典算法中加入了斥力作用項(Algorithm2, 8)， 并使得斥力在粒子的速度迭代中發(fā)揮作用(Algorithm2, 12)。

3 算法仿真

為了比較改進算法的性能，選取了如下8個標準測試函數(shù)。

表1 算法性能對比

我們采用經(jīng)典的 LPOS（Linear Weighted Particle Swarm Optimization） 、QPOS（Quantum Particle Swarm Optimization） 和 IAPOS（Improved Adaptive Swarm Optimization） 作為比較算法，并分別設(shè)定搜索算法的維度為10和20做比較，見表1。通過比較我們可以得出改進算法對于高維問題具有較好的收斂性。

4 結(jié)束語

傳統(tǒng)的粒子群算法由于初值的隨機選取使得，當(dāng)粒子位置初始化比較集中時，粒子對于為探測區(qū)域的擴張性較差，而斥力項的引入使得，粒子可以主動拓展為探測區(qū)域。仿真結(jié)果表明，改進的粒子群算法對于初值的依賴性較低，對于大范圍且具有多局部最優(yōu)值的優(yōu)化問題具有較好的全局收斂性。本文方法可應(yīng)用于線性優(yōu)化、非線性優(yōu)化等數(shù)學(xué)經(jīng)典問題，同時也可應(yīng)用于信號處理、深度學(xué)習(xí)等工程問題，具有較好的應(yīng)用前景。