基于IGWO-GRNN的室內3D定位算法

高 媛，陽 媛，王鴻磊

(1.徐州工業職業技術學院 信息工程學院，江蘇 徐州 221000；2.東南大學 儀器科學與工程學院， 江蘇 南京 210096；3.中國礦業大學 信息與控制學院，江蘇 徐州 221000)

0 引 言

目前，為實現更加精準的室內定位，有研究人員開始應用人工神經網絡等人工智能理論結合接收信號強度RSSI(received signal strength indication)進行室內定位[1,2]。其中，廣義回歸神經網絡(generalized regression neural network，GRNN)非線性映射能力強，數據擬合能力和學習速度也更優[3]，十分適合室內定位。其模型結構簡單，預測性能很大程度上取決于參數σ的取值，而σ取值時主觀影響較大[4]，需要尋找一種優化σ取值的方法來實現高精度定位。灰狼優化算法(grey wolf optimizer，GWO)[5]是一種新興的群智能優化算法，收斂性能較強、參數少、易實現，可用于優化參數，被許多研究者廣泛采用，但GWO算法在尋優過程中容易陷入局部最優。為進一步提升GWO算法的性能，文獻[6]利用混沌Cat映射、粒子群算法個體記憶功能、高斯變異擾動和優勝劣汰選擇規則來優化算法。文獻[7]引入了混沌算法、改進了收斂因子，并對δ狼進行了融合變異。文獻[8]采用改進的精英反向學習策略產生精英反向個體，避免算法早熟收斂。文獻[9]在種群初始化、平衡全局和局部探索能力方面做出了改進，同時進行了Cauchy變異操作。但是以上4種改進算法并沒有對位置更新策略進行改進，且全局和局部搜索能力的協調不夠靈活，尋優能力和尋優效率還有待提高。本文提出一種改進的灰狼優化算法(improved grey wolf optimizer，IGWO)，通過對種群初始化的改進、控制參數的對數式調整以及適應度權值的引入，經過多次迭代，可獲得更佳的適應度值和更快的收斂速度。同時將IGWO引入到GRNN模型中，利用IGWO優化平滑因子σ的取值，建立最優GRNN神經網絡模型，準確定位待測節點的三維位置。

1 GRNN模型及問題描述

GRNN神經網絡的結構如圖1所示，由輸入層、模式層、求和層和輸出層4部分構成[10]。

圖1 GRNN神經網絡結構

將模型的輸入向量表示為X=[X1,X2,…Xm]T，輸出向量表示為Y=[y1,y2,…yn]T，聯合概率密度函數表示為f(X,y)，y的觀測值為Y，假定f(X,y)服從正態分布，則

(1)

式中：m為輸入向量X的維度；n為學習樣本數；σ為高斯函數的寬度系數，即GRNN網絡的平滑因子。Xi為第i個輸入向量，Yi為第i個輸出向量。

y相對于X的回歸為

(2)

在已知概率密度函數的情況下，由式(1)、式(2)計算可得

(3)

將室內定位時實際測量到的RSSI值作為輸入向量輸入GRNN模型，則可根據式(3)預測出被測目標的真實位置。GRNN模型結構簡單，當樣本數據確定后，綜上可知，進行網絡預測只需確定平滑因子σ，σ的取值直接影響著GRNN模型的泛化能力和預測精度[4,11]，所以適中的σ取值極其重要。本文采用改進的灰狼算法IGWO來優化平滑因子σ的取值。

2 IGWO-GRNN室內3D定位算法

2.1 傳統灰狼算法

灰狼算法是一種根據灰狼群體捕食而提出的智能算法，獵物代表最優解，每只灰狼的位置代表一個可能的解[12]。灰狼群在捕獵過程中有著嚴格的社會等級制度，領導能力最強的灰狼被記為α，是適應度最佳、離最優解最近的狼；β狼和δ狼是適應度次于α狼的兩種個體，獵捕過程中它們會協助α狼管理狼群以及決策出現的問題，同時也是α狼的候選者；剩余的狼記為ω，負責平衡狼群內務關系以及協助攻擊獵物[13,14]。

GWO算法的數學模型具體描述如下：

Di=|C·Xp(t)-Xi(t)|

(4)

C=2·r2

(5)

其中，Di為灰狼個體i與獵物間的距離，Xp(t)和Xi(t)分別為t次迭代時獵物和灰狼個體i所處的位置，C為擺動因子。

狼群要根據獵物方位對自己位置進行更新，其數學描述如下

Xi(t+1)=Xp(t)-A·Di

(6)

A=2a·r1-a

(7)

a=2-t/tmax

(8)

A為協同系數向量，變量a隨著迭代次數的增加從2線性減少到0，tmax為最大迭代次數，r1，r2表示[0,1]間的隨機數。

包圍獵物后，β狼和δ狼在α狼的帶領下開始追捕獵物，灰狼的位置會隨著獵物逃跑而改變，需要更新α、β、δ狼的位置來重新確定最優解，而其它灰狼個體則根據α、β、δ狼的位置來調整自己的位置，用Xi(t+1)表示。具體公式為

(9)

(10)

(11)

在一次捕獵的過程中，伴隨著參數和迭代次數的不斷調整，最終找到全局最優解。

2.2 改進的灰狼算法IGWO

2.2.1 種群初始化的改進

在傳統灰狼算法中，初始的狼群種群是隨機生成的[15]，種群的隨機分布會使得初始解的個體不能遍歷整個搜索空間，造成較優解的丟失，還可能會陷入局部最優值，降低了算法的尋優能力。而具有均勻分布的初始化種群可以一定程度上提高算法的尋優效果。本文采用文獻[16]提出的佳點集方法初始化灰狼種群，以獲得更均勻穩定的初始種群分布。

設狼群初始種群數為N，搜索空間的維數為D，則有

rd=ed,1≤d≤D

(12)

佳點集中第i個點的第d維可表示為

(13)

將佳點集映射到灰狼初始種群，搜索空間為1維，則第i個灰狼的1維空間的值為

Xi=l1+ri1(u1-l1),i=1,2,…,N

(14)

式中：u1和l1分別為灰狼個體的1維空間的上下限。

取灰狼種群數量為50，灰狼個體的1維值分布在[0,1]中，使用佳點集方法獲得的初始種群分布的數據見表1，使用隨機生成法和佳點集方法的種群分布如圖2所示。

表1 佳點集獲取初始分布數據

圖2 兩種方法獲取初始種群分布情況

從表1和圖2可以看出，佳點集構造的初始種群分布更加均勻，且沒有重復的個體，從而更有助于算法遍歷整個搜索空間，有效避免局部最優。

2.2.2 控制參數的對數式調整

對群體智能優化算法來說，全局和局部探索能力的協調至關重要。全局探索是群體需要搜索更廣泛的區域，避免算法陷入局部最優[8]；局部探索則是利用已有信息對某些鄰域進行密集搜索，決定著算法的收斂速度。使兩者協調的算法才能具備較強的魯棒性和較快的收斂速度。

由傳統灰狼位置更新公式可知，在平衡GWO算法的全局和局部探索能力方面，參數A的大小起到關鍵的作用。當|A|>1時，灰狼群體擴大搜索范圍；當|A|<1時，灰狼群體縮小搜索范圍。分別對應于GWO算法的全局探索能力和局部探索能力。由式(7)可知，控制參數a決定A的值，a值越大，算法的探索能力越強；a值越小，搜索精度越高。由式(8)可知，控制參數a隨迭代次數t的增加線性減小，由2變化到0。但是，結合實際，GWO算法的尋優過程是非常復雜的，尋優前期和后期的側重點不同，要求也不一樣，控制參數a僅隨迭代次數t線性遞減不能反映出實際的尋優過程。文獻[8]和文獻[9]提出了設計控制參數a隨迭代次數t進行非線性變化，由測試結果可知，改進后的GWO算法尋優效果更佳。因此本文提出一種基于對數函數且曲率可變的控制參數計算方法，其表達式為

(15)

式中：μ為曲率參數。選取不同μ值，令tmax取500，控制參數a隨迭代次數t的變化如圖3所示。

圖3 控制參數a隨迭代次數t的變化

從圖3中可以看出，該控制參數計算方法對應的曲線在尋優前期時，a的變化幅度不斷變緩，有利于狼群的部署以及擴大搜索范圍，以得到全局最優解；尋優后期曲線變得越來越陡峭，有利于加快算法的收斂速度，增加狼群捕獵精度。隨著μ取值的不斷增大，曲線的曲率也不斷增大，實際應用時，可根據實際需要適當調整μ值，計算出的a能更好地協調全局與局部探索能力。

2.2.3 適應度權值的引入

在α、β、δ狼隨著獵物的移動而更新自身的位置后，其它灰狼個體ω則根據α、β、δ狼的位置來調整自己的位置，由傳統灰狼算法可知，當迭代次數達到規定次數時，將α狼的位置作為全局最優解輸出。所以，α狼的位置是最接近獵物的位置，ω狼位置更新時應著重傾向于向α狼的位置移動，故本文引入適應度權值。將α、β、δ狼的位置加權一定的系數后，得到ω狼的位置，這樣，能夠縮短整個狼群和獵物間的距離，增大捕獲的成功率，提高算法的尋優效率。首先構造適應度函數計算灰狼個體的適應度值，本文構造適應度函數為

(16)

式中：(x′j,y′j,z′j)是GRNN模型的第j個預測位置，(xj,yj,zj)是第j個樣本實際位置，M為測試位置樣本數。根據計算出的適應度值選出值最小的3個灰狼個體，適應度值按從小到大分別記為fα、fβ、fδ，將α、β、δ狼的適應度權值分別記為：kα、kβ、kδ，數學表達式如式(17)～式(19)所示

(17)

(18)

(19)

由此計算ω狼的位置如式(20)所示

(20)

式中：X1i、X2i、X3i分別為α、β、δ狼更新后的位置。

2.3 IGWO-GRNN室內3D定位流程

將GRNN模型的參數平滑因子σ映射為灰狼種群中的灰狼，第i個灰狼個體表示為Xi={σi}，i=1,2,…,N，基于IGWO-GRNN室內3D定位算法的總體流程如圖4所示。

圖4 IGWO-GRNN室內3D定位算法流程

其中，改進的灰狼優化算法IGWO調整平滑因子的流程如圖5所示。

圖5 IGWO調整平滑因子的流程

本文將定位過程分為兩個階段：模型訓練階段和三維坐標預測階段。在模型訓練階段，利用在測試場所采集到的RSSI值和對應的測試節點實際三維坐標樣本數據訓練網絡并建立IGWO-GRNN模型；在三維坐標預測階段，將待定位節點與信標節點之間采集到的RSSI值輸入訓練好的IGWO-GRNN模型中，神經網絡的輸出即為待定位節點的三維坐標。

具體步驟如下：

步驟1初始化算法參數：灰狼種群規模N取值100，取值范圍介于[0,1]之間，最大迭代次數tmax=50，搜索空間維數D=1。

步驟2初始化灰狼個體位置Xi。采用式(14)的佳點集方法對狼群進行初始化，保證狼群較均勻分布。

步驟3按照式(16)構造適應度函數并計算所有灰狼個體的適應度值。

步驟4根據計算出的適應度值選出值最小的3個灰狼個體，并將其位置分別保存為Xα、Xβ、Xδ。

步驟5根據式(15)計算控制參數a，本文中曲率參數μ取值300，然后計算A、C

(21)

C=2rand(0,1)

(22)

rand(0,1)表示[0,1]上均勻分布的隨機數。

步驟6根據式(9)、式(10)、式(20)更新α、β、δ以及ω灰狼個體的位置。

步驟7判斷是否達到最大迭代次數tmax，如未達到，則返回步驟3，如達到，則輸出Xα作為最優解，即得到最優平滑因子σ。

步驟8輸入訓練樣本集數據對神經網絡模型進行訓練，如滿足誤差要求，則訓練完成，得到最優GRNN定位模型，終止訓練并保存模型，否則，重復步驟8。

步驟9將測試樣本集數據輸入最優GRNN定位模型，獲得待定位節點三維坐標。

3 實驗及結果分析

我們將實驗選擇在一個12 m×10 m的辦公環境內，基于Zigbee定位系統，準備5個信標節點(AP)，分別放置在測試場所天花板的4個角落和中心位置，用來接收定位節點發送的數據，測試場所內存在各種障礙物。將測試區域劃分為120個小區域，每個小區域大小為1 m×1 m，小區域中心位置作為測試點。測試人員隨身攜帶定位節點，從(0,0)位置出發，遍歷每個測試小區域。在每個測試點處，定位節點向5個信標節點分別發送100個數據包，形成[RSSI1,RSSI2,RSSI3,RSSI4,RSSI5,(xi,yi,zi)]樣本數據，i=1,2,3,…,120，作為樣本集數據。從120組樣本數據中抽取100組數據作為訓練樣本集，剩余20組作為測試樣本集。將訓練樣本集中的RSSI值作為網絡模型的輸入，訓練神經網絡，對應測試點的坐標作為輸出，滿足誤差要求后，則得到最優定位模型，再用測試樣本集數據來驗證該網絡模型的定位效果。

本文為了驗證IGWO-GRNN在室內3D定位中的準確性和優越性，將IGWO-GRNN與GWO-GRNN和文獻[11]中提出的GA-GRNN以及將文獻[9]中提出的一種改進非線性收斂方式的灰狼優化算法CGWO用于室內3D定位進行比較。初始種群規模N取值100，平滑因子σ取值范圍設置在[0,1]之間，最大迭代次數tmax=50。其中本文算法IGWO中曲率參數μ取值300，CGWO算法的非線性調節系數k值直接取自文獻[9]中實驗性能最佳時的值。GWO、GA、CGWO和IGWO這4種算法的尋優對比如圖6所示，從圖中可以看出，GWO算法在24代左右收斂，GA算法在34代左右收斂，CGWO算法在16代左右收斂，而IGWO算法在13代左右已經收斂。同時可以看到，4種算法尋優最終平穩下來的適應度值IGWO算法最低，GA算法最高。綜上表明，在算法的收斂速度方面和精準度方面，IGWO都要明顯優于另3種算法。

圖6 GWO、GA、CGWO和IGWO尋優對比

通過上面4種算法不斷迭代更新，在尋優結束時，得到各自最優平滑因子σ。其中，GWO算法得到σ=0.572，GA算法得到σ=0.667，CGWO算法得到σ=0.407，IGWO算法得到σ=0.336。各自構建神經網絡模型，進行定位效果的比較。

GWO-GRNN、GA-GRNN、CGWO-GRNN和IGWO-GRNN這4種模型的定位效果如圖7所示。

將4種模型的定位誤差進行對比，如圖8所示，GA-GRNN模型的最大定位誤差是0.86 m，最小定位誤差是0.07 m，實際坐標與模型輸出坐標差在0.3 m內的點只有8個，GWO-GRNN模型的最大定位誤差是0.61 m，最小定位誤差是0.03 m，實際坐標與模型輸出坐標差在0.3 m內的點有13個，CGWO-GRNN模型的最大定位誤差是0.46 m，最小定位誤差是0.02 m，實際坐標與模型輸出坐標差在0.3 m內的點有16個，而IGWO-GRNN模型的最大定位誤差是0.37 m，最小定位誤差是0 m，實際坐標與模型輸出坐標差在0.3 m內的點有18個。由以上數據可知，GA-GRNN模型定位精度明顯低于GWO-GRNN模型。由文獻[11]實驗結果可知，GA-GRNN模型在定位精度和收斂速度上都優于目前廣泛研究的FOA-GRNN以及BP神經網絡算法。所以利用灰狼算法優化GRNN平滑因子σ進而實現室內3D定位是有明顯優勢的。而將灰狼優化算法進行改進后，CGWO-GRNN與IGWO-GRNN模型定位精度顯著提高，本文提出的IGWO-GRNN模型定位精度最高。

圖7 4種模型的定位效果

圖8 3種模型定位誤差對比

本文選用均方根誤差(RMSE)對模型的預測效果進行評價，公式如下

(23)

式中：(xi,yi,zi)為測試樣本集第i個樣本的真實位置，(x′i,y′i,z′i)為預測值，n為測試樣本集樣本數，均方根誤差值越小，模型的預測性能越好。表2為4種模型的均方根誤差對比結果。可以看出，GA-GRNN模型的均方根誤差最大，IGWO-GRNN模型的最小，再次表明，利用IGWO優化GRNN平滑因子σ，可以獲得更好的定位效果。

表2 4種模型的均方根誤差對比結果

4 結束語

本文提出一種基于IGWO-GRNN的室內3D定位算法。該算法將待測節點與信標節點間的RSSI值作為GRNN的輸入，待測節點的三維坐標作為輸出，訓練神經網絡擬合RSSI值與三維坐標最終建立網絡模型。該算法引入改進的灰狼算法IGWO優化GRNN網絡的平滑因子σ，有效解決了因人為選擇參數不當而導致的預測效果不好和過擬合現象，提高了模型的預測精度。仿真結果表明，與GWO-GRNN、GA-GRNN、CGWO-GRNN相比，本文提出的算法定位精度更高且尋優速度更快，基本滿足定位要求，為室內定位提供了一種方法。