基于IGWO-GRNN的室內(nèi)3D定位算法

高 媛，陽 媛，王鴻磊

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

0 引 言

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

1 GRNN模型及問題描述

GRNN神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)如圖1所示，由輸入層、模式層、求和層和輸出層4部分構(gòu)成[10]。

圖1 GRNN神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

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

(1)

式中：m為輸入向量X的維度；n為學(xué)習(xí)樣本數(shù)；σ為高斯函數(shù)的寬度系數(shù)，即GRNN網(wǎng)絡(luò)的平滑因子。Xi為第i個(gè)輸入向量，Yi為第i個(gè)輸出向量。

y相對于X的回歸為

(2)

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

(3)

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

2 IGWO-GRNN室內(nèi)3D定位算法

2.1 傳統(tǒng)灰狼算法

灰狼算法是一種根據(jù)灰狼群體捕食而提出的智能算法，獵物代表最優(yōu)解，每只灰狼的位置代表一個(gè)可能的解[12]?；依侨涸诓东C過程中有著嚴(yán)格的社會(huì)等級制度，領(lǐng)導(dǎo)能力最強(qiáng)的灰狼被記為α，是適應(yīng)度最佳、離最優(yōu)解最近的狼；β狼和δ狼是適應(yīng)度次于α狼的兩種個(gè)體，獵捕過程中它們會(huì)協(xié)助α狼管理狼群以及決策出現(xiàn)的問題，同時(shí)也是α狼的候選者；剩余的狼記為ω，負(fù)責(zé)平衡狼群內(nèi)務(wù)關(guān)系以及協(xié)助攻擊獵物[13,14]。

GWO算法的數(shù)學(xué)模型具體描述如下：

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

(4)

C=2·r2

(5)

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

狼群要根據(jù)獵物方位對自己位置進(jìn)行更新，其數(shù)學(xué)描述如下

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

(6)

A=2a·r1-a

(7)

a=2-t/tmax

(8)

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

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

(9)

(10)

(11)

在一次捕獵的過程中，伴隨著參數(shù)和迭代次數(shù)的不斷調(diào)整，最終找到全局最優(yōu)解。

2.2 改進(jìn)的灰狼算法IGWO

2.2.1 種群初始化的改進(jìn)

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

設(shè)狼群初始種群數(shù)為N，搜索空間的維數(shù)為D，則有

rd=ed,1≤d≤D

(12)

佳點(diǎn)集中第i個(gè)點(diǎn)的第d維可表示為

(13)

將佳點(diǎn)集映射到灰狼初始種群，搜索空間為1維，則第i個(gè)灰狼的1維空間的值為

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

(14)

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

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

表1 佳點(diǎn)集獲取初始分布數(shù)據(jù)

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

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

2.2.2 控制參數(shù)的對數(shù)式調(diào)整

對群體智能優(yōu)化算法來說，全局和局部探索能力的協(xié)調(diào)至關(guān)重要。全局探索是群體需要搜索更廣泛的區(qū)域，避免算法陷入局部最優(yōu)[8]；局部探索則是利用已有信息對某些鄰域進(jìn)行密集搜索，決定著算法的收斂速度。使兩者協(xié)調(diào)的算法才能具備較強(qiáng)的魯棒性和較快的收斂速度。

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

(15)

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

圖3 控制參數(shù)a隨迭代次數(shù)t的變化

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

2.2.3 適應(yīng)度權(quán)值的引入

在α、β、δ狼隨著獵物的移動(dòng)而更新自身的位置后，其它灰狼個(gè)體ω則根據(jù)α、β、δ狼的位置來調(diào)整自己的位置，由傳統(tǒng)灰狼算法可知，當(dāng)?shù)螖?shù)達(dá)到規(guī)定次數(shù)時(shí)，將α狼的位置作為全局最優(yōu)解輸出。所以，α狼的位置是最接近獵物的位置，ω狼位置更新時(shí)應(yīng)著重傾向于向α狼的位置移動(dòng)，故本文引入適應(yīng)度權(quán)值。將α、β、δ狼的位置加權(quán)一定的系數(shù)后，得到ω狼的位置，這樣，能夠縮短整個(gè)狼群和獵物間的距離，增大捕獲的成功率，提高算法的尋優(yōu)效率。首先構(gòu)造適應(yīng)度函數(shù)計(jì)算灰狼個(gè)體的適應(yīng)度值，本文構(gòu)造適應(yīng)度函數(shù)為

(16)

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

(17)

(18)

(19)

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

(20)

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

2.3 IGWO-GRNN室內(nèi)3D定位流程

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

圖4 IGWO-GRNN室內(nèi)3D定位算法流程

其中，改進(jìn)的灰狼優(yōu)化算法IGWO調(diào)整平滑因子的流程如圖5所示。

圖5 IGWO調(diào)整平滑因子的流程

本文將定位過程分為兩個(gè)階段：模型訓(xùn)練階段和三維坐標(biāo)預(yù)測階段。在模型訓(xùn)練階段，利用在測試場所采集到的RSSI值和對應(yīng)的測試節(jié)點(diǎn)實(shí)際三維坐標(biāo)樣本數(shù)據(jù)訓(xùn)練網(wǎng)絡(luò)并建立IGWO-GRNN模型；在三維坐標(biāo)預(yù)測階段，將待定位節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間采集到的RSSI值輸入訓(xùn)練好的IGWO-GRNN模型中，神經(jīng)網(wǎng)絡(luò)的輸出即為待定位節(jié)點(diǎn)的三維坐標(biāo)。

具體步驟如下：

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

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

步驟3按照式(16)構(gòu)造適應(yīng)度函數(shù)并計(jì)算所有灰狼個(gè)體的適應(yīng)度值。

步驟4根據(jù)計(jì)算出的適應(yīng)度值選出值最小的3個(gè)灰狼個(gè)體，并將其位置分別保存為Xα、Xβ、Xδ。

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

(21)

C=2rand(0,1)

(22)

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

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

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

步驟8輸入訓(xùn)練樣本集數(shù)據(jù)對神經(jīng)網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練，如滿足誤差要求，則訓(xùn)練完成，得到最優(yōu)GRNN定位模型，終止訓(xùn)練并保存模型，否則，重復(fù)步驟8。

步驟9將測試樣本集數(shù)據(jù)輸入最優(yōu)GRNN定位模型，獲得待定位節(jié)點(diǎn)三維坐標(biāo)。

3 實(shí)驗(yàn)及結(jié)果分析

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

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

圖6 GWO、GA、CGWO和IGWO尋優(yōu)對比

通過上面4種算法不斷迭代更新，在尋優(yōu)結(jié)束時(shí)，得到各自最優(yōu)平滑因子σ。其中，GWO算法得到σ=0.572，GA算法得到σ=0.667，CGWO算法得到σ=0.407，IGWO算法得到σ=0.336。各自構(gòu)建神經(jīng)網(wǎng)絡(luò)模型，進(jìn)行定位效果的比較。

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

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

圖7 4種模型的定位效果

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

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

(23)

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

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

4 結(jié)束語

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