混合粒子群和差分進化的定位算法*

吳 斌，金潔麗

（1.浙江郵電職業技術學院，浙江 紹興 312016；2.吉首大學信息科學與工程學院，湖南 吉首 416000）

0 引 言

智能優化算法模擬地球上生物的行為，是一類具有自我學習、自我組織的方法，適合大規模問題求解，眾多學者將該類算法應用于求解定位問題[1]。

林鳳德等人[2]針對經典DV-Hop 方法定位精度低且計算復雜度高等難題提出一種利用遺傳與蟻群混合優化算法的DV-Hop 定位方法。該方法中除利用遺傳方法搜找最優解外，還利用蟻群進一步搜找，增強了定位精度和迭代速度，測試表明該算法增加了計算效率，迭代速率和定位適應度值。面對Amprphous 算法存在較低的定位精度的缺點，胡偉等人[3]利用遺傳-禁忌搜索算法求解該問題。首先修正最小跳數的估計值然后經過遺傳算法優化，優化后的解在經過禁忌搜索策略進一步增強了算法的精度。靳春景等人[4]通過大量的實驗仿真發現單一算法定位精度容易受環境等因素的影響較大，提出一種利用DVC-Hop 的算法，它修正了平均跳距，并引入PSO 優化方法加快尋優速度，因為PSO 方法較易陷入局部解空間卻無法跳出等缺點，因此提出隨機擾動策略解決PSO的早熟難題。姚汝賢等人[5]提出一種利用改進量子PSO 的RSSI 測距方法，為了加快PSO 優化算法的收斂速率，在算法中引入學習自動機，粒子在獲得自學習能力以后可以自適應的選擇相應的動作。實驗論證顯示該方法具有較高的定位質量，并且速度快。

上述算法雖然有效的求解節點定位問題，但是在實時性和定位精度上仍有待改善，因此本文提出融合粒子群和差分進化算法的HPSO-DE 算法，并和文獻[6]的PSO、文獻[7]的DFOA 等方法進行比較，證明本文算法在適應度函數值和收斂速度方面的優勢。

1 節點定位問題建模及目標函數

設 錨P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)和 未 知 節 點P(x,y)的實際真實長度分別是r1,r2,…,rn，測距誤差分別是ε1,ε2,…,εn，則滿足|ri-di|<εi，其中i=1,2,…,n，那么未知節點P(x,y)約束條件：

解(x,y)，使得：

由此節點定位問題轉換成求如式2 中測距誤差最小值的優化問題，本文將改進智能優化算法應用于節點位置估計的優化問題，以降低誤差對定位性能的干擾，提高定位的精度。

2 粒子群算法及差分進化算法

2.1 粒子群算法（PSO）

PSO 算法的核心思想是粒子的在解空間里面隨意飛行，然后在每次迭代過程中通過和其他粒子進行信息交互，然后根據個人經驗和其他粒子的影響決定下一次飛行的位置。受到其他優秀的個體的影響，粒子從最初無序的狀態朝著熵減狀態轉變，直至最終搜索到食物位置。

假設一個種群規模為N 的粒子群在解空間里面搜索最優解，搜索維度為D。粒子i 在t 時刻的狀態屬性設置如下：

則在t+1 代更新過程里，個體的速度和位置更新公式分別為：

式中，u1,u2為介于（0,1）內隨機服從uniform分布的數；c1,c2分別表示個體認知因子和社會認知因子（二者統稱加速度因子），一般取c1=c2=2.0。

2.2 差分進化算法(DE)

（1）種群初始化

DE 算法的種群由NP 個D 維向量個體組成。記xi為一個D 維向量，則一個種群可以表示為Pop={x1.x2,…,xNP}。其中，NP 是種群的規模大小，該值在每次迭代過程中保持不變。種群的初始化應在符合邊界約束的條件下盡可能均勻覆蓋全部區域，假設個體第j 維的上下邊界分別為和那么個體按下面的方式進行初始化：

式 中，i=1,2,…,NP；j=1,2,…,D。randj（0,1）是一個在（0,1）上服從uniform 分布的隨機數。

（2）變異操作

種群經過初始化賦值后，利用差分變異操作產生變異矢量。常見的差分變異操作有DE/rnad/1、DE/best/1、DE/rand-to-best/1、DE/best/2、DE/rand/2、DE/current-to-best/1、DE/current-to-rand/1等。其中，經典的“DE/rand/1”變異策略如式（6）所示：

式中，r1,r2,r3 ∈[1,2,….NP]為兩兩不相同的整數，縮放因子F 是（0，1）區間內的常數，用于控制差分向量的大小。

（3）交叉操作

在進行變異操作之后，需要將目標向量xi,g與變異向量vi,g進行二項式交叉生成最終的試驗向量ui,g=[ui1,g,ui2,g,uiD,g]，按照公式（7）執行交叉操作。

式中，jrand是從集合{1,2,…,D}內隨機選擇的一個整數，以保證變異向量vi,g至少有一維信息被保留下來。交叉概率CR 是區間（0,1）內的一個常數。

（4）選擇操作

試驗向量與對應的目標向量之間執行一對一的錦標賽選擇。對試驗向量ui,g與vi,g目標向量的目標函數值進行比較，如果試驗向量具有更優的目標函數，則將目標向量替換成試驗向量；否則，該目標向量保持不變。以目標函數最小化為例，選擇操作可用公式（8）來表示：

式中，f(·)為優化問題的目標函數。

3 節點定位的HPSO-DE 算法

粒子群算法較易出現局部最小[8]，主要因為該算法優化過程中，種群的差異性喪失，趨向于同一性，但是粒子群收斂速度快，差分進化算法雖然全局探索能力強，但是其在進化的前提和中期一般都探索解空間，而未對較優解的局部空間進行細致的開發，導致尋優速度慢，因此本文提出混合粒子群和差分進化算法HPSO-DE 以平衡算法的局部尋優和全局探索的能力，其中自適應慣性權重更新策略和混合進化策略使得該算法不僅尋優能力強而且尋優速度快。

3.1 自適應慣性權重更新策略

粒子群算法中的w 衡量了前一時刻的速度對當前速度的影響[9]，用于平衡算法的局部搜索能力和全局搜索能力。傳統的粒子群算法將w 設置為固定值，導致該算法無法在不同的優化階段下相應的做出調整導致陷入局部最優。本文在計算w 時考慮到每次迭代過程中種群的分布情況，首先定義第i 個粒子距離其他N-1 個粒子的平均距離di為：

其中，N 和D 分別表示種群規模大小和編碼維度。然后定義進化因子δ 如式（10）所示：

其中，dg表示為全局最優個體的平均距離，dmax、dmin分別表示種群中最大和最小的平均距離。最終w 的更新公式如式（11）所示：

其中w 隨著δ 的增加而增加，變化范圍是[0.4 0.9]，在早期的迭代過程中，δ 較大，此時w 也較大，有利于粒子快速找到最優解的大致位置區域，在迭代后期，w 較小，此時檢測到種群趨于同一開始收斂，減小w 有利于進行精準的局部搜索。

3.2 混合優化策略

如前文所述，粒子群算法容易陷入局部最優，全局搜索能力差，但是差分進化算法的搜索能力卻很強，因此可以將經過PSO 進化的種群再經過DE算法進化，同時為了減少算法的復雜度，我們設定了閾值，將種群劃分為優等群和劣等群，只將劣等群中的個體經過差分進化，然后將進化后的種群和優秀群合并繼續進行下一次迭代。即，首先設定閾值favg，計算公式如式（12）所示：

然后將每個粒子的適應度值與之比較，若小于該值，表示該個體較優秀，即歸入優等群，反之，如果該粒子的適應度值大于該值意味著該個體當前解較差，因此要歸入到劣等群中通過DE 算法進一步優化。

在經過DE 進化后，利用貪婪選擇機制，確定當前種群中的最優解。

綜上所述可得HPSO-DE 算法的步驟如下：

（1）初始化粒子群中的粒子的速度和位置，設置迭代次數I=1.

（2）利用式2 計算每個粒子的適應度值。

（3）利用式12 計算種群的閾值favg，將種群劃分為優等群Su 和劣等群In。

（4）將In 中的個體依次利用式6、7 和8 進行變異和交叉和選擇操作，進一步提高劣等群中個體的適應度值。

（5）將優等群和劣等群合并，并更新全局最優值和個體最優值

（6）若I 等于最大迭代次數則進行步驟7，否則轉步驟2

（7）輸出最優個體的位置作為對未知節點的位置估計。

4 仿真實驗與分析

4.1 參數設置

在PSO 算法中，設置學習因子c1=c2=1.4945，在DFOA[7]算法中,設置搜索步長radiusX 為0.1，本文HPSO-DE 算法中，設置常數交叉概率cr=0.6。三種算法中設置種群規模大小為30，最大迭代次數設置為80。

4.2 實驗仿真分析

本文參考文獻[10]以平均定位誤差（average location error，AVE）為評價標準。其公式如式（13）所示：

式中：M 為已知節點的總個數，(x,y)為預測位置，(xi,yi)為實際位置。

首先設置網絡節點的通信半徑為10 m，隨機將30 個傳感器置于30 m×30 m 的區域中，隨機挑選10 個節點為錨節點，設置算法的最大迭代次數為200 次，每一個未知節點的坐標估計值都是20 次獨立實驗的平均。將HPSO-DE 算法與參考文獻[7]中的DFOA 算法進行節點定位結果的對比，見表1。

表1 給出了在HPSO 算法和DFOA 算法下，挑選的10 個無法測量自身坐標的節點的預測值比較，由表可以看出（1）首先兩種算法都可以應用于WSN 網絡的定位場景中，同時，由10 個未知點的預測誤差來看，HPSO-DE 的AVE 比DFOA 要低很多，證明了本文所提算法的優勢。

PSO、DFOA 和HPSO-DE 等算法在已知自身精確位置信息的節點個數為10 個時的AVE 隨測距誤差關系圖如圖1 所示。圖中的每條曲線均進行了20 次獨立重復實驗而得到。由圖1 可知：（1）由圖中的三條曲線的走向可以看出總體定位精度是HPSO-DE>DFOA>PSO（2）本文提出的HPSO-DE隨著迭代次數自適應的變化慣性權重的值和混合進化策略使得該算法不僅定位能力強而且尋優速度快，在測距誤差為30%時，HPSO-DE 的定位誤差分別比DFOA 和PSO 降低2 m 和1 m。（3）由表可以看出當測距誤差由25%增加到30%時，PSO算法和DFOA 算法的曲線的斜率顯著增大，說明該兩種算法的魯棒性能差，但是所提HPSO-DE 算法卻增加的很平緩，說明在較大測距誤差情況下，HPSO-DE 也可以有較高的定位精度。

圖1 平均定位誤差與測距誤差關系

如圖2 給出了PSO、DFOA 和HPSO-DE 在測距誤差為10%時的AVE 和已知自身精確位置信息的節點個數變化關系。由圖可以看出，（1）由圖中的三條曲線表示的平均定位誤差與錨節點個數的關系圖走向可以看出總體定位精度是HPSODE>DFOA>PSO，（2）雖然PSO 算法的誤差在信標節點的數目增加的時候而下降，但是AVE 仍然高于DFOA 算法和HPSO-DE 算法，說明該算法很敏感，和對成本要求較高。（3）本文在仿真場景中設置相同數量的已知個體坐標精確位置的節點的情況下，HPSO-DE 具有最小的誤差性能，例如當錨節點個數為4 個時，HPSO-DE、DFOA 和PSO 算法的定位誤差分別是1.5 m、2.2 m 和3.35 m。

圖2 平均定位誤差與錨節點個數關系

PSO、DFOA 和HPSO-DE 在定位誤差為10%，信標節點個數為10 個時，AVE 與種群規模的關系如圖3 所示。由圖可知，（1）隨著種群規模的增大，有更多的個體在搜索空間里尋找更優解，因此三種算法的定位誤差都在逐漸減小。（2）HPSO-DE、DFOA 和PSO 算法在達到最小的定位誤差時需要的種群個體數量分別是20、20 和47。說明HPSODE 和DFOA 的尋優能力強，同時算法復雜度低，特別是HPSO-DE 算法，在個體數量為10 時平均定位誤差就很小，而PSO 達到同等的平均定位誤差，需要的種群個體數量為37。這是因為本文提出的HPSO-DE 算法的自適應慣性權重更新策略和混合進化策略使得該算法同時擁有PSO 的開采性能高和DE 的勘探能力強的特點，在保持較快收斂速度的同時具有更高的優化性能。

圖3 平均定位誤差與種群規模大小關系

4.3 實測分析

上述理論仿真表明所提算法具有良好的定位性能，為了實測算法定位效果，搭建了如圖4 所示的實驗平臺，在一塊6 m×6 m 的正方形操場上，按圖5 設置8 個錨節點（T1～T8），然后測量未知節點（1～9）的位置信息。

圖4 定位實驗點實測

將實測數據與參考文獻[11]中的改進PSO 算法測得的數據進行比較，得到結果對比如圖6 所示。由圖可以看出，本文所提HPSO-DE 算法約比改進PSO 算法的平均定位誤差低0.1 m。

圖5 定位實驗點布置

圖6 錨節點為8 時平均誤差對比圖

5 結 語

如何確定傳感器節點的精確位置是WSN 網絡技術需要解決的重要難題之一。針對由測量誤差造成的精度不高的問題，本文首先改進PSO 的固定權重為自適應變化方式，增強了PSO 優化的整體勘探能力，然后改進差分進化算法的變異策略，增強DE 算法的局部尋優能力，然后將經過粒子群優化后的較差個體繼續通過差分進化算法優化，得到混合粒子群與差分進化的HPSO-DE 算法，將該算法應用于本文建模的WSN 定位場景中，仿真實驗和實測實驗結果表明，HPSO-DE 算法不僅提高了定位精度而且減少了定位需要消耗的時間。