基于麻雀算法優化GRNN的三維定位算法

高 媛，陽 媛，凌啟東

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

0 引 言

為提高定位精度，近年來，人工智能理論被應用于室內定位領域[1]。文獻[2]使用BP神經網絡定位，效率較低。文獻[3]使用RBF神經網絡定位，訓練中存在病態問題。文獻[4]提出一種粒子群優化RBF的定位模型，定位精度有所提高。研究發現，廣義回歸神經網絡(gene-ralized regression neural network，GRNN)具有很強的非線性映射能力和較快的學習速度[5]，強于BP和RBF。但其平滑因子σ的取值一般依據個人經驗并手動設置[6]，主觀影響較大。因此，需找到一種合適的方法來優化σ的取值。群智能優化算法具有良好的搜索能力，目前成為研究熱點[7]。其中，粒子群算法(particle swarm optimization，PSO)和灰狼優化算法(grey wolf optimizer，GWO)基于自身優勢應用較多。文獻[8]采用PSO優化BP神經網絡建立粗糙度預測模型，文獻[9]提出一種RBF-GWO網絡混沌同步控制器。文獻[10]將熱門的幾種群智能優化算法進行對比研究，從實驗結果來看，2020年由Xue和Shen提出的一種最新的群智能優化算法麻雀算法(sparrow search algorithm，SSA)[11]，局部搜索能力極強，收斂速度很快，各方面性能都優于PSO算法和GWO算法。但SSA容易陷入局部最優，全局搜索能力較差[10]。

本文提出一種基于改進麻雀算法-廣義回歸神經網絡(MSSA-GRNN)的室內三維定位算法，首先改進麻雀算法為多種群麻雀算法(multi-population sparrow search algorithm，MSSA)，把麻雀種群分成數量相同的若干個子種群，每個子種群各自獨立迭代尋優，增強全局搜索能力；根據適應度值的排名，選出優勝子種群和輔助子種群，經過群內競爭和群間競爭，最終求得全局最優；種群初始化時采用佳點集及反向學習策略，可獲得更高質量的初始種群分布；在子種群個體更新時，引入漸變加權系數，算法能夠更快地收斂。再利用MSSA優化平滑因子σ的取值，建立最優GRNN神經網絡模型，提高了定位精度及尋優效率。

1 GRNN模型及問題描述

GRNN神經網絡由輸入層、模式層、求和層和輸出層4部分組成[12]，結構如圖1所示。模型的輸入向量為RSSI=[RSSI1,RSSI2,…RSSIn]T， 輸出向量為A=[A1,A2,…Ak]T。

圖1 GRNN神經網絡結構

聯合概率密度函數表示為f(RSSI,A)， 公式如式(1)所示

(1)

式中：m為學習樣本的個數；n為網絡輸入層神經元的個數；σ為GRNN網絡的平滑因子(σ>0)。RSSIi為第i個輸入向量，Ai為第i個輸出向量。在已知概率密度函數的前提下，將室內定位時實際測量到的RSSI值作為GRNN模型的輸入向量，則可根據式(2)預測出被測目標的真實三維位置

(2)

GRNN模型結構比較簡單、容易運算，且具有很強的逼近能力和學習速度。在網絡中只需確定平滑因子σ即可獲得準確的輸出，極大地簡化了網絡運算，增加了模型的魯棒性。但是，光滑因子σ的選擇主觀影響因素較大，σ值越大，預測結果越接近所有樣本的均值，泛化能力高但精度較低；當σ值接近0時，如果樣本中存在未包含進去的點，則預測效果較差，且泛化能力低，會出現過擬合現象[13]。所以，適中的σ取值極其重要。本文采用改進的麻雀算法MSSA來優化平滑因子σ的取值。

2 MSSA-GRNN三維定位算法

2.1 麻雀算法

自然界的麻雀在覓食過程中，每只麻雀有3種可能的行為：①作為發現者，負責為整個種群尋找食物，并提供覓食方向和區域；②作為加入者，利用發現者來獲取食物；③警戒偵查，有危險時會做出反捕食行為。

SSA算法[11]的數學模型具體描述如下：

(1)發現者位置更新

發現者具有較好的適應度值，在探索過程中會優先獲取食物，同時擁有比加入者更大的搜索范圍。在每次迭代的過程中，發現者的位置按以下公式進行更新

(3)

其中，t是當前迭代數，tmax是一個常數，表示最大迭代次數。d=1,2,3,…,D，D是待優化問題變量的維數，xi,d表示第i個麻雀個體在第d維中的位置。α(α∈(0,1]) 是均勻隨機數，Q是服從正態分布的隨機數，L是一個1×D的矩陣，該矩陣內所有元素全為1。R2(R2∈(0,1]) 表示預警值，ST(ST∈(0.5,1]) 表示安全值。當R2

(2)加入者位置更新

加入者會因為覓食位置差或者搜索到了提供最好食物的發現者而改變自身位置，以求獲取到食物。加入者的位置更新描述如下

(4)

(3)偵查預警

在覓食的時候，有部分麻雀負責警戒，在危險靠近時，發現者和加入者都將更換位置。其位置更新公式如下

(5)

其中，β是正態分布隨機數，服從均值為0，方差為1，用于控制步長。K是一個值在[-1,1]內的隨機數，ε是最小常數，可避免分母出現零。fi表示當前麻雀個體的適應度值，fg表示當前全局最佳適應度值，fw則表示當前全局最差適應度值。

2.2 改進的麻雀算法MSSA

2.2.1 佳點集反向學習的多種群初始化

麻雀算法采用單種群方式進行尋優，在一個種群內搜索時，按照一定的規則形成發現者-加入者模型，同時加入一定的偵察預警機制。不斷迭代更新向食物靠近，如果麻雀個體趨向一致，算法極易陷入局部最優。為降低陷入局部最優的可能性，本文將單種群平均劃分成多種群進行搜索，每個子種群在各自搜索域內進行尋優，最終達到對整個搜索空間全面搜索，增強全局搜索能力。

整個麻雀種群數量為S，將整個麻雀種群均分為M個子種群，每個麻雀子種群初始種群數為N，如取S=100， 麻雀個體的1維值分布在(0,1]中。對整個種群進行均分時，考慮每個子種群的大小只能是5,10,20,25，所以N的取值范圍為 {5,10,20,25}，M的取值范圍為 {20,10,5,4}。 在均分時，為確保每個麻雀個體在且僅在一個子種群里，將以Δ為1維值區間間隔進行劃分

(6)

其中，u1和l1分別為麻雀種群麻雀個體的1維空間的上下限。取M=4， 則Δ=0.25， 各子種群的麻雀個體1維初始值分別分布在 (0,0.25]、 (0.25,0.5]、 (0.5,0.75]、 (0.75,1] 中。

麻雀算法的初始種群是隨機產生的，種群的隨機分布會使得初始解的個體不能遍歷整個搜索空間，導致種群的多樣性差，可能造成較優解的丟失，降低算法的尋優能力。所以應盡可能使個體在搜索空間內均勻分布，提高算法尋優效果。本文采用文獻[14]提出的佳點集方法對每個麻雀子種群進行初始化，以獲得更均勻穩定的初始種群分布。

1維搜索空間下，由佳點集方法可得

r1=e

(7)

將佳點集映射到每一個麻雀初始子種群，子種群中第i個點的第1維可表示為

(8)

每個子種群中第i個麻雀的1維空間的值為

Xij=l1j+rij1(u1j-l1j)，i=1,2,…,N，j=1,2,…,M

(9)

其中，u1j和l1j分別為第j個麻雀子種群麻雀個體的1維空間的上下限。

以1維值分布在(0,0.25]區間的子種群為例，使用隨機生成法和佳點集方法的子種群分布如圖2所示。

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

由圖2可以看出，佳點集方法初始種群后，個體分布更加均勻，從而更有助于算法遍歷整個解空間，提高種群多樣性。

本文在多種群佳點集初始化的基礎上添加反向學習策略進一步初始化子種群，其基本思想是在利用佳點集初始化子種群，生成N個麻雀個體后，再產生其對立個體，此時子種群個體數量為2N，在該子種群內將所有個體進行適應度評價對比，選出適應度最優的N個麻雀個體作為算法的初始種群。對立個體數學表達式如下

X′ij=l1j+u1j-Xij，i=1,2,…,N，j=1,2,…,M

(10)

將1維值分布在(0,0.25]區間的子種群在佳點集初始化后進行反向學習，佳點集初始個體及對立個體見表1，反向學習分布情況如圖3所示。

表1 佳點集初始個體及對立個體

圖3 反向學習分布

對比圖2圖3，反向學習使麻雀個體探索了更多的初始位置，增加了種群多樣性，提高了初始種群質量，為算法奠定了更好的迭代基礎。

2.2.2 種群競爭及加權比重漸變的位置更新

本文提出的多種群競爭的基本思想如下：子種群初始化完成后，計算整個種群所有個體的適應度值，并進行排序，適應度最高的個體，其所在的子種群作為優勝子種群，用于記錄全局競爭中優勝者的信息；其余M-1個子種群作為輔助子種群，用于記錄并輔助完成全局競爭的過程。本文構造的適應度計算公式如下

fi=RMSE(p-p′)

(11)

RMSE為均方根誤差函數，p為實際坐標 (x,y,z)，p′為每次迭代后的輸出坐標 (x′,y′,z′)。

優勝子種群和輔助子種群在迭代時個體的位置更新公式具體如下：

(1)優勝子種群個體位置更新

1)發現者位置更新

(12)

2)加入者位置更新

原公式稍有偏差，修改為下式

(13)

(14)

(15)

3)偵查預警者位置更新

按照以上思路，偵查預警者的位置更新公式為

(16)

(2)輔助子種群個體位置更新

輔助子種群中的麻雀個體應向著整個種群最優位置逐步逼近，隨著迭代次數的增加，與整個種群最優位置的逼近度也應隨著增加，整個種群最優位置的權重逐漸增大，輔助完成全局競爭。

1)發現者位置更新

(17)

2)加入者位置更新

(18)

則加入者位置更新公式為

(19)

3)偵查預警者位置更新

將整個種群最優位置和最差位置漸變加權引入，得到偵查預警者位置更新如下

(20)

2.3 MSSA優化的GRNN模型

將平滑因子σ映射為麻雀種群中的麻雀,即MSSA算法中的麻雀代表了GRNN網絡的平滑因子，而每只麻雀的位置則對應了平滑因子的每一個值，第i個麻雀個體表示為Xi={σi}，i=1,2,…,N， 本文建立基于MSSA-GRNN算法的室內三維定位模型。定位過程由訓練和預測兩個階段組成。在訓練階段，使用在定位現場測量的RSSI值及對應測試節點的實際三維坐標樣本數據訓練網絡，建立MSSA-GRNN定位模型；在預測階段，將待定位節點與信標節點間的RSSI值輸入MSSA-GRNN定位模型中，模型輸出即是待定位節點的三維坐標預測值，比較預測值與實際值是否一致。算法的整體流程如圖4所示。

圖4 MSSA-GRNN流程

步驟1 參數設置及多種群劃分。麻雀種群規模記為S，最大迭代次數記為tmax， 搜索空間維數記為D，均分為K個子種群。

步驟2 各子種群的初始化。首先采用佳點集方式初始化各子種群，然后各子種群分別進行反向學習，通過適應度排序，每個子種群按照適應度排名選擇前一半個體作為子種群成員。

步驟5 更新麻雀位置。優勝子種群和輔助子種群分別根據式(12)、式(15)、式(16)、式(17)、式(19)、式(20)更新發現者、加入者和偵察預警者的位置。

步驟6 循環迭代步驟3～步驟5，直到迭代結束，得到最優個體，即最優平滑因子值。

步驟7 訓練定位模型。將最優平滑因子值作為GRNN網絡模型的參數，使用訓練集樣本數據訓練室內三維定位模型。

步驟8 坐標預測。將測試集樣本中的RSSI值輸入訓練好的三維定位模型中，計算預測坐標值，將預測值與實際值進行比較，評估MSSA-GRNN定位模型性能。

3 實驗及結果分析

為了驗證MSSA算法的性能，本文設計了基準函數對比實驗，旨在從通用性角度驗證MSSA算法的可行性和優越性；以及基于MSSA-GRNN的三維定位算法與其它定位算法的對比實驗，旨在驗證基于MSSA-GRNN的三維定位算法的優越性。

3.1 基準函數對比實驗

基于10個基準測試函數，比較MSSA與3種基本群智能算法PSO[8]、GWO[9]和SSA[11]的性能。如表2所示，4個高維單峰函數F1～F4，4個高維多峰函數F5～F8，2個低維函數F9～F10。為保證公平性，仿真在同一電腦同一運行環境下進行，處理器：Inter(R) Core(TM) i5-4300M CPU @ 2.50 Hz，內存4.00 GB，操作系統：Windows10，使用MATLAB2019a完成實驗，選取種群數量為100，最大迭代次數為500，各算法獨立運行30次的實驗結果作為實驗數據。

表2 基準函數

(1)參數設置

各算法的參數設置見表3。

表3 參數設置

(2)算法性能結果對比分析

通過對比各算法的平均值、標準差、運行時間3項指標來檢驗算法的尋優能力、穩定性以及尋優速度，具體結果見表4。

由表4的實驗結果可知，對于高維單峰函數F1～F4，MSSA在尋優精度和尋優穩定度上相對于其它3種算法，都有較大的提升，其中，函數F3和F4，平均值均能達到理論最優值，且穩定性較強。對于高維多峰函數F5～F8，函數F5，MSSA算法尋優性能不突出；F6和F8，MSSA算法均能有效跳出局部最優，取得最優值；對于F7，MSSA算法在尋優能力方面相較于SSA算法沒有明顯提升，但是標準差為0，說明尋優的穩定性能較好。對于低維函數F9，MSSA算法尋優性能不突出；但是F10，MSSA算法的平均值達到理論最優值，且標準差最小。從運行時間上看，對于函數F1～F10，MSSA算法尋優速度相對于PSO和GWO算法較慢，但是相對于SSA算法有一定提升，運行時間整體減少了8.1%。綜上所述，MSSA算法在進行10個基準函數測試時，尋優精度大多數明顯提高，能夠有效避免陷入局部最優，且尋優穩定性好，在運行速度上優于SSA算法。

表4 基準測試函數優化結果比較

3.2 基于MSSA-GRNN的室內三維定位實驗

為了驗證MSSA-GRNN在室內三維定位中的準確性和優越性，將MSSA-GRNN與文獻[6]的AGA-GRNN三維定位算法、文獻[4]的K-M模型三維定位算法以及GRNN神經網絡算法進行比較。本文實驗選擇在一個12 m×10 m×3.3 m的教室內進行，測試場所內存在各種障礙物，將5個CC2530 ZigBee節點作為信標節點分別放置在實驗場所天花板的4個角落及中心位置，用來接收定位節點發來的數據，5個信標節點間通過有線方式連接到網關。把測試區域均勻劃分成120個大小為1 m×1 m的小區域，每個小區域的中心位置作為測試點。測試時，實驗人員隨身攜帶CC2530 ZigBee節點作為定位節點，從第一個小區域出發，遍歷每個測試小區域。在每個測試點處，實驗人員將定位節點分別放置在距離地面1 m處、1.5 m處和2 m處，不同高度放置的定位節點分別向5個信標節點各發送50個數據包，信標節點根據接收到的數據解析出RSSI值，并傳送到網關，去除最大值最小值后使用卡爾曼濾波處理，然后求平均值，最終生成 [RSSI1,RSSI2,RSSI3,RSSI4,RSSI5,(xi,yi,zi)] 樣本集數據，i=1,2,3,…,360。 從360組樣本集數據中抽取340組數據作為訓練集，剩余20組作為測試集。將訓練集中的RSSI值輸入網絡模型，訓練神經網絡，模型輸出的坐標滿足誤差要求后，得到最優定位模型，最后用測試集數據來驗證該網絡模型的定位效果。

測試中，仿真實驗環境與3.1節基準函數對比實驗的軟硬件環境相同，處理器：Inter(R) Core(TM) i5-4300M CPU @ 2.50 Hz，內存4.00 GB，操作系統：Windows10，使用MATLAB2019a完成實驗。MSSA-GRNN、K-M模型、AGA-GRNN這3種算法的種群規模設置為100，最大迭代次數設為300，MSSA-GRNN、AGA-GRNN兩種算法中光滑因子σ的取值范圍設置為(0,2]，K-M模型、AGA-GRNN兩種算法的初始參數設置與參考文獻[4,6]中的實驗設置一致，4種算法的具體參數設置見表5。

MSSA不斷迭代更新，在尋優結束時，得到最優平滑因子σ=0.322。GRNN、K-M、AGA-GRNN和MSSA-GRNN這4種算法的定位效果如圖5所示。

將4種算法的定位誤差進行對比，如圖6所示，K-M模型的最大定位誤差是0.94 m，最小定位誤差是0.53 m，預測坐標誤差較大；GRNN模型的最大定位誤差是0.62 m，最小定位誤差是0.37 m，定位效果有所提升，但誤差仍然較大；AGA-GRNN算法的最大定位誤差是0.39 m，最小定位誤差是0.18 m，實際坐標與預測坐標差在0.3 m內的點有14個；而MSSA-GRNN模型的最大定位誤差是0.28 m，最小定位誤差是0 m，實際坐標與預測坐標差在0.3 m內的點有20個，也就是說所有測試點的坐標預測誤差都小于0.3 m，沒有誤差較大的點，預測結果趨于穩定。由此可見，本文提出的MSSA-GRNN模型網絡定位精度明顯提高，定位效果更好。

表5 各算法參數

圖5 4種算法的定位效果

圖6 4種模型定位誤差對比

為更進一步地對比定位效果，本文采用均方根誤差(RMSE)和平均絕對誤差(MAE)兩個統計指標對模型的預測效果進行評價,各統計指標的對應公式如下

(21)

(22)

式中： (xi,yi,zi) 為測試樣本集第i個樣本的真實三維坐標， (x′i,y′i,z′i) 為預測坐標，以上兩種統計指標都是其值越小，模型的預測性能越好，精度越高。如表6所示，通過本文提出的MSSA算法對σ值進行優化，得到的RMSE為0.0507，MAE為0.0625，兩個指標明顯低于其它算法的優化結果，本文構建的模型定位效果顯著提高，全局搜索能力明顯增強，避免了原未改進麻雀算法容易陷入局部最優的問題。

表6 樣本統計指標對比結果

下面來對比4種算法訓練樣本數量與定位精度的關系。當訓練樣本數量發生改變時，從圖7可以看出，隨著樣本數量的增加，K-M算法的均方根誤差無規律變化，在樣本數為140個時，均方根誤差最小為0.5136 m；GRNN、AGA-GRNN、MSSA-GRNN這3種算法在樣本數量為100個時已經具有較高的定位精度，隨著樣本數量的增加，3種算法的均方根誤差趨于穩定，不再有較大的變化，說明了GRNN網絡模型的優越性，在少量樣本下就可以獲得較高的定位精度，將GRNN、AGA-GRNN、MSSA-GRNN這3種算法進行對比，在相同樣本數量的情況下，MSSA-GRNN算法的定位精度最高，說明MSSA算法的尋優效果更好。

圖7 均方根誤差與訓練樣本數量的關系

分別用4種算法訓練定位模型所需的時間見表7，樣本數量均取各自均方根誤差最早出現最小值時的樣本數量。由于GRNN不需要尋優，所以耗時最少，效率最高，但精度較差；其它3種算法均需要尋優，對比訓練時間可以發現，其中，MSSA-GRNN算法尋優效率最高。

表7 4種算法的效率對比

4 結束語

本文提出了一種MSSA-GRNN三維定位算法，使用室內RSSI值作為GRNN神經網絡的輸入，實際三維坐標作為網絡的輸出，建立三維定位模型，利用改進的麻雀算法MSSA優化GRNN網絡的平滑因子。通過仿真可以看出，MSSA-GRNN算法和GRNN、K-M、AGA-GRNN這3種算法相比，定位精度顯著提高，且定位誤差比較穩定，相對K-M、AGA-GRNN兩種算法有更快的尋優速度，整體性能更好，基本滿足定位要求，為室內定位提供了一種新方法，具有很好的應用前景。但是對于定位實時性要求較高的系統來說，本文提出的算法定位所需時間仍然較長，下一步將考慮在提高定位精度的同時，減少定位時間，使該算法應用范圍更廣。