基于排斥作用的改進(jìn)粒子群算法

楊洪濤 丁烽

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

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

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

1.1 算法描述

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

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

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

1.2 算法偽代碼

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

2 改進(jìn)模型

2.1 模型背景

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

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

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

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

圖1 粒子斥力作用圖

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

2.3 改進(jìn)PSO算法

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

2.4 改進(jìn)算法偽代碼

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

3 算法仿真

為了比較改進(jìn)算法的性能，選取了如下8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)。

表1 算法性能對(duì)比

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

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

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