引入四元數(shù)理論的改進(jìn)粒子群算法

張曉聞, 任勇峰

(中北大學(xué)儀器與電子學(xué)院， 太原 030051)

粒子群算法(particle swarm optimization, PSO)[1]是一種模擬鳥群覓食行為的優(yōu)化算法，近年來，由于該算法簡單，參數(shù)設(shè)置少，容易跳出局部最優(yōu)，搜索到全局解被廣泛應(yīng)用。傳統(tǒng)粒子群算法為不同的交互對象構(gòu)造兩種不同的版本，全局最好模型(globalbest，Gbest)及局部最好模型(localbest，Lbest)。而近年來，學(xué)者們研究了很多不同的改進(jìn)算法，文獻(xiàn)[2]中以Shi和Eberhart的粒子多樣性為基礎(chǔ)，給出了多種求解位置多樣性、速度多樣性及種群多樣性的方法，都取得了很好的效果。其他方面，文獻(xiàn)[3]中提出一種融合優(yōu)質(zhì)粒子分布的粒子群優(yōu)化算法，在“社會”部分加入以分布估計(jì)算法為基礎(chǔ)的優(yōu)質(zhì)粒子，該優(yōu)質(zhì)粒子是根據(jù)統(tǒng)計(jì)學(xué)習(xí)概率模型而產(chǎn)生的。文獻(xiàn)[4]為了在擴(kuò)大粒子搜索空間時(shí)避免陷入局部最優(yōu)，利用了正弦函數(shù)獨(dú)有的振動特性，在位置公式中加入正弦三角函數(shù)因子。有的學(xué)者根據(jù)反推理論，從反向?qū)W習(xí)的角度出發(fā)，文獻(xiàn)[5]利用反向?qū)W習(xí)策略進(jìn)行改進(jìn)，用反向解代替當(dāng)前解，擇優(yōu)進(jìn)行下一次迭代。文獻(xiàn)[6]在反向?qū)W習(xí)的基礎(chǔ)上，引入折射原理思想，對粒子群算法進(jìn)行改進(jìn)。還有研究學(xué)者利用小生境鄰域[7]的思想進(jìn)行改進(jìn)粒子群算法，其思想是粒子的鄰域結(jié)構(gòu)隨著迭代次數(shù)的變化而變化。因此針對不同的問題提出適合該問題的鄰域結(jié)構(gòu)，如文獻(xiàn)[8]提出了利用拓?fù)浣Y(jié)構(gòu)構(gòu)造局部鄰域解。文獻(xiàn)[9]提出了一種帶有粒子聚合度的改進(jìn)粒子群算法，該算法中融合了聚合度和慣性權(quán)重的概念，聚合度反映粒子聚集的程度，作用是使粒子跳出局部最優(yōu)。文獻(xiàn)[10]針對PSO算法的不確定動態(tài)多目標(biāo)優(yōu)化問題，在位置更新公式中引入動態(tài)變異算子，通過分段線性函數(shù)參數(shù)化實(shí)現(xiàn)不確定動態(tài)多目標(biāo)優(yōu)化。文獻(xiàn)[11]通過歷史數(shù)據(jù)學(xué)習(xí)模型避免算法陷入局部最優(yōu)。文獻(xiàn)[12-14]通過聚類模型和自適應(yīng)模型改進(jìn)算法，從而實(shí)現(xiàn)算法的收斂速度和搜索精度的平衡。

在以上改進(jìn)算法中，都忽略了一個(gè)問題，無論學(xué)習(xí)機(jī)制、拓?fù)浣Y(jié)構(gòu)、引入算子模型及鄰域思想如何等，只是將各項(xiàng)學(xué)習(xí)之間看作相互獨(dú)立的個(gè)體，都忽略了學(xué)習(xí)機(jī)制之間的關(guān)系。為了使粒子的多樣性得到進(jìn)一步利用，避免粒子群體過早收斂，現(xiàn)在樹狀拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，將空間中的粒子利用拓?fù)浣Y(jié)構(gòu)分類，得到局部最優(yōu)解，利用四元數(shù)理論，將3種學(xué)習(xí)機(jī)制：自身最優(yōu)、全局最優(yōu)和局部最優(yōu)作為四元數(shù)的3個(gè)虛部向量，將四元數(shù)項(xiàng)作為相關(guān)項(xiàng)信息加入到粒子群算法中，用于調(diào)節(jié)3種記憶粒子之間的相互關(guān)系。粒子群算法的應(yīng)用廣泛，可用于信號處理、圖像處理、濾波器等多個(gè)領(lǐng)域。

1 相關(guān)理論

1.1 樹狀拓?fù)浣Y(jié)構(gòu)

文獻(xiàn)[15]提出一種逐級尋優(yōu)拓?fù)浣Y(jié)構(gòu)(Tree-PSO，TPSO)，主要是一種基于樹狀的拓?fù)浣Y(jié)構(gòu)，如圖1所示，該結(jié)構(gòu)中由子節(jié)點(diǎn)之間交流比較，得到上一層父節(jié)點(diǎn)，直到找到全局最優(yōu)值。

圖1 TPSO拓?fù)浣Y(jié)構(gòu)及節(jié)點(diǎn)分布Fig.1 TPSO topology and node distribution

1.2 四元數(shù)理論

四元數(shù)[16]是一個(gè)表示超復(fù)數(shù)的數(shù)學(xué)概念，它的構(gòu)成是實(shí)部加上3個(gè)虛部單位i、j、k。每個(gè)四元數(shù)都可由1、i、j、k線性表出，則四元數(shù)的一般表達(dá)式為q=a+bi+cj+dk，其中a、b、c、d都為實(shí)數(shù)。當(dāng)a=0時(shí)，q=bi+cj+dk稱為純四元數(shù)。近些年，四元數(shù)的應(yīng)用廣泛，現(xiàn)利用四元數(shù)虛部的相關(guān)關(guān)系，對粒子群算法進(jìn)行改進(jìn)，無論在理論創(chuàng)新和實(shí)際應(yīng)用中，都提供了新思路。

2 算法原理

2.1 基本思想

樹狀拓?fù)浣Y(jié)構(gòu)是結(jié)合粒子的3個(gè)最優(yōu)值來改變粒子的飛行方向，但無論是個(gè)體、局部還是全局的記憶適應(yīng)值，都忽略了一個(gè)問題，就是三者之間的相關(guān)性，為了將三者之間的聯(lián)系用來調(diào)節(jié)粒子的飛行方向，提出了一種結(jié)合四元數(shù)理論的改進(jìn)粒子群算法，利用TPSO作為模型，將個(gè)體最優(yōu)、局部最優(yōu)和全局最優(yōu)作為四元數(shù)的3個(gè)虛部，將四元數(shù)作為關(guān)聯(lián)項(xiàng)加入粒子群速度公式的“社會”部分。同時(shí)在公式中使用了慣性權(quán)重和收縮因子，以保證群體可收斂到全局最優(yōu)值。

當(dāng)a=0,b=c=d=1時(shí)，將單位純四元數(shù)q=i+j+k代入PSO公式，則改進(jìn)算法的速度與位置公式為

vi+1,j=χ[wvi,j+c1r1(pi,j-xi,j)+c2r2(pn,j-xi,j)+

c3r3(pg,j-xi,j)+c4r4(qi,j-xi,j)]

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

式中：x為位置；v為速度；i為當(dāng)前粒子；j為當(dāng)前維數(shù)；t為當(dāng)前迭代數(shù)；qi,j=pi,j+pn,j+pg,j，pi,j記錄粒子個(gè)體的最佳解，pn,j記錄局部鄰域內(nèi)的粒子最佳解，pg,j記錄全局粒子的最佳解；χ為收縮因子；w為慣性權(quán)重；c1為調(diào)節(jié)個(gè)體最優(yōu)的加速系數(shù)；c2為調(diào)節(jié)局部最優(yōu)的加速系數(shù)；c3為調(diào)節(jié)全局最優(yōu)的加速系數(shù)；c4為調(diào)節(jié)三者關(guān)系的加速系數(shù)；r1、r2、r3、r4∈(0,1)且相互獨(dú)立。

2.2 算法步驟

根據(jù)改進(jìn)算法的設(shè)計(jì)，下面給出算法的步驟。

步驟1對算法的基本參數(shù)進(jìn)行初始化。

步驟2根據(jù)優(yōu)化函數(shù)，計(jì)算適應(yīng)值，并比較記錄pi,j、pn,j和pg,j。

步驟3根據(jù)步驟2中記錄的pi,j、pn,j和pg,j，計(jì)算四元數(shù)項(xiàng)。

步驟4將四項(xiàng)記錄值代入式(1)、式(2)，得到最新迭代次數(shù)下的粒子速度和位置。

步驟5根據(jù)循環(huán)終止條件判斷是否滿足終止，否則返回步驟2。

在每次迭代中，粒子向全局最優(yōu)、局部最優(yōu)及個(gè)體最優(yōu)學(xué)習(xí)的同時(shí)，還保留著三者之間的相關(guān)性，此方法使粒子的多樣性得到充分利用，避免種群陷入了局部最優(yōu)而導(dǎo)致無法找到最優(yōu)解。

2.3 算法收斂性證明

基本微粒群算法中給出了判斷PSO收斂性的兩個(gè)假設(shè)條件及全局收斂準(zhǔn)則[17-19]。在保證算法有效的前提下，設(shè)D為算法迭代方式，用來得到下一次的迭代值，則由D得到的當(dāng)前迭代值應(yīng)優(yōu)于前一次迭代值。因此，提出下列假設(shè)以滿足算法。

假設(shè)1f[D(z,ξ)]≤f(z)，并且如果ξ∈S，S∈Rn，則f[D(z,ξ)]≤f(ξ)。

假設(shè)2對于樣本空間S的任意Borel子集A，若其測度v(A)>0，則有

(3)

式(3)中：μk(A)為由測度μ(k)所得到的A的概率。

由假設(shè)1和假設(shè)2給出算法為全局收斂的充要條件。

(4)

式(4)中：P[zk∈Rε]為第k步算法生成的解zk∈Rε的概率。

根據(jù)以上假設(shè)及定理，證明改進(jìn)的PSO算法的收斂性。

證明：定義函數(shù)D為

(5)

式(5)中：g(xi,k)為改進(jìn)PSO算法的更新方程。具體為

xi,k+1=g(xi,k)=g1(xi,k)+g2(xi,k)+g3(xi,k)+g4(xi,k)+g5(xi,k)

(6)

式(6)中：g1(xi,k)=xi,k+ωvi,k，g2(xi,k)=c1r1(pi,k-xi,k)，g3(xi,k)=c2r2(pn,k-xi,k)，g4(xi,k)=c3r3(pg,k-xi,k)，g5(xi,k)=c4r4(qi,k-xi,k)，xi,k為第k代時(shí)的微粒i的位置，則由定義函數(shù)D可知，改進(jìn)PSO滿足假設(shè)1。

Mi,k=(1+ω-φ1-φ2-φ3-φ4)x(t)-ωx(t-1)+piφ1+pnφ2+pgφ3+qφ4=xi,j,k-1+ω(xi,j,k-1-xi,j,k-2)+φ1(pi-xi,j,k-1)+φ2(pn-xi,j,k-1)+φ3(pg-xi,j,k-1)+

φ4(q-xi,j,k-1)

(7)

3 仿真實(shí)驗(yàn)

3.1 測試函數(shù)

選擇的6個(gè)基準(zhǔn)測試函數(shù)(其中兩個(gè)單峰值函數(shù)，兩個(gè)多峰值函數(shù)及兩個(gè)多峰固定維度測試函數(shù))如表1所示，對算法進(jìn)行驗(yàn)證，尋找函數(shù)的最小值，并將基本PSO、EDAPSO、TPSO和本文算法對基準(zhǔn)函數(shù)優(yōu)化的結(jié)果進(jìn)行比較分析。通過實(shí)驗(yàn)的數(shù)據(jù)來觀察在同一測試函數(shù)下算法的收斂效率和搜索精度。

3.2 參數(shù)設(shè)置

根據(jù)實(shí)驗(yàn)所需參數(shù)，對參數(shù)的設(shè)置如下：最大迭代次數(shù)為1 000,慣性權(quán)重ω=0.8，收縮因子χ=0.729。粒子規(guī)模=30。經(jīng)實(shí)驗(yàn)得到，在本文算法中，c1、c2、c3代表粒子分別向個(gè)體最優(yōu)、局部最優(yōu)和全局最優(yōu)學(xué)習(xí)的隨機(jī)數(shù)，c4代表向三種粒子相關(guān)項(xiàng)學(xué)習(xí)的隨機(jī)數(shù)。當(dāng)c1=1.4,c2=1.4,c3=1.8,c4=1.4時(shí)，取得的效果較好。

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 仿真實(shí)驗(yàn)分析

為了便于考查不同算法的性能，將PSO、EDAPSO、TPSO和本文算法進(jìn)行比較，將每個(gè)算法分別對表1的6個(gè)測試函數(shù)獨(dú)立運(yùn)行30次，記錄每種算法在各個(gè)函數(shù)下的最大值、最小值、平均值及平均時(shí)間，具體實(shí)驗(yàn)結(jié)果如表2所示。對比表2中數(shù)據(jù)，表明本文算法相對于PSO、EDAPSO和TPSO具有明顯的優(yōu)勢。由于在本文算法中加入了四元數(shù)為關(guān)聯(lián)的三個(gè)記錄值，比較表中的數(shù)據(jù)可以發(fā)現(xiàn)，對比最小值結(jié)果和函數(shù)的最優(yōu)值，本文算法尤其在F1、F3、F5和F6中可收斂于全局最優(yōu)值。對于單峰值函數(shù)，比較幾種算法的平均值可以得出，平均值至少提高10倍，對于F2函數(shù)，收斂的平均值有了質(zhì)的提升，即本文算法在搜索的精度上比其他三種算法高，粒子的多樣性得到充分利用。

表1 基準(zhǔn)測試函數(shù)Table 1 Benchmark function

表2 函數(shù)測試結(jié)果Table 2 Function test results

對于多峰值函數(shù)，在整個(gè)函數(shù)搜索空間中會包含大量的局部極值，對于PSO算法來說，容易使其陷入局部極值，而本文算法由于利用了TPSO的樹狀結(jié)構(gòu)，同時(shí)加入了四元數(shù)項(xiàng)，以使粒子的多樣性得到充分利用，使得算法在學(xué)習(xí)過程中達(dá)到了平衡，更容易跳出局部最優(yōu)值，從而能繼續(xù)搜索全局最優(yōu)值。對于多峰固定維測試函數(shù)，因其解空間維度較低，不同算法得到的解差異不大，雖然都沒有找到真值，但本文算法搜索結(jié)果更優(yōu)。通過幾種算法應(yīng)用于同一約束函數(shù)的收斂曲線如圖2所示，明顯看出本文算法的收斂性優(yōu)于其他3種算法。

圖2 算法的收斂曲線對比Fig.2 Convergence curves comparison of algorithms

3.3.2 物理實(shí)驗(yàn)分析

文獻(xiàn)[20]中利用粒子群優(yōu)化算法結(jié)合伽馬校正，來評估所獲得的紅外圖像增強(qiáng)結(jié)果。借鑒此經(jīng)驗(yàn)，選取圖像集中的3幅圖像進(jìn)行對比度增強(qiáng)實(shí)驗(yàn)，增強(qiáng)后效果如圖3所示：將本文算法與PSO算法進(jìn)行對比度圖像增強(qiáng)算法比較，采用5個(gè)圖像質(zhì)量準(zhǔn)則進(jìn)行性能評價(jià)，評價(jià)結(jié)果如表3～表5所示。評價(jià)準(zhǔn)則包括：峰值信噪比(peak signal to noise ratio, PSNR)；結(jié)構(gòu)相似度指數(shù)測度(structural similarity, SSIM)；信息保真度準(zhǔn)則(information fidelity criterion, IFC)；視覺信息保真度(visual information fidelity, VIF)；特征相似性(feature similarity, FSIM)。所有這些準(zhǔn)則都被廣泛應(yīng)用于圖像對比度增強(qiáng)領(lǐng)域，對各種圖像對比度增強(qiáng)方法進(jìn)行性能評價(jià)。物理實(shí)驗(yàn)中PSO算法的參數(shù)設(shè)置如下:種群大小為30，最大迭代次數(shù)為1 000，c1、c2、c3代表粒子分別向個(gè)體最優(yōu)、局部最優(yōu)和全局最優(yōu)學(xué)習(xí)的隨機(jī)數(shù)，取c1=1.4,c2=1.4,c3=1.8。

圖3 測試圖像對比Fig.3 Test image comparison

表3 測試圖像1對兩種方法性能評估Table 3 The performance evaluation of two approaches using test images 1

表4 測試圖像2對兩種方法性能評估Table 4 The performance evaluation of two approaches using test images 2

4 結(jié)論

改進(jìn)的粒子群算法在TPSO樹狀結(jié)構(gòu)的基礎(chǔ)上，選擇局部最優(yōu)的粒子節(jié)點(diǎn)，與個(gè)體最優(yōu)粒子和全局最優(yōu)粒子之間相關(guān)聯(lián)，通過四元數(shù)的數(shù)學(xué)概念，將這三者設(shè)為四元數(shù)的三個(gè)虛部向量，作為社會部分，加入速度公式中。對改進(jìn)的算法通過理論證明算法具有全局收斂性，通過仿真實(shí)驗(yàn)對算法的收斂性進(jìn)行可視化說明，改進(jìn)的PSO算法不但減緩粒子群優(yōu)化算法的收斂，而且有效地解決了搜索精度不高和容易陷入局部最優(yōu)值的問題。在算法效率上通過與PSO、EDAPSO和TPSO進(jìn)行分析比較，具有顯著的算法性能，既驗(yàn)證了它的理論可行性，又仿真了算法的實(shí)驗(yàn)可行性。對所提算法與其他進(jìn)化算法優(yōu)化對比度增強(qiáng)進(jìn)行比較，選擇兩個(gè)不同數(shù)據(jù)集中的圖像進(jìn)行主觀與客觀評價(jià)，最后結(jié)果得出，無論在主觀定性方面還是客觀定量方面，本文算法的效果都要優(yōu)于其他算法。