基于QPSO優(yōu)化ELM算法的井下快速定位方法研究

高淑春, 于 蕾

(合肥職業(yè)技術(shù)學(xué)院 信息工程與傳媒學(xué)院, 安徽 合肥 230000)

高鐵、公路、煤礦、石油、天然氣等行業(yè)關(guān)乎國民經(jīng)濟(jì)命脈,是我國工業(yè)領(lǐng)域的重中之重,而在這些行業(yè)中或多或少會存在隧道施工、井下作業(yè)等特種工種,為避免特種作業(yè)時發(fā)生重大安全事故,以及在事故發(fā)生后能夠?qū)ψ鳂I(yè)人員進(jìn)行快速救援,需要準(zhǔn)確、迅速地掌握井下作業(yè)人員的位置,對此國內(nèi)外專家學(xué)者開展了一系列研究,分別提出了基于藍(lán)牙、WiFi、超寬帶、射頻識別、超聲波等技術(shù)的井下定位系統(tǒng)[1-4]。其中,基于 WiFi 的井下定位技術(shù)因具備定位范圍廣、速度快和硬件成本低等優(yōu)勢,受到了業(yè)界的廣泛關(guān)注。此外,近年來,井下信息化程度不斷提高,WiFi 網(wǎng)絡(luò)在礦井中的普及程度也隨之提高,為無需額外增加硬件設(shè)備的 WiFi 定位系統(tǒng)的推廣提供了便利條件。

基于 WiFi 的井下定位系統(tǒng)以無線接入點(Access Point, AP)的接收信號強(qiáng)度(Received Signal Strength, RSS)值為定位依據(jù)構(gòu)建位置指紋庫,通過對比采集到的 RSS 值與位置指紋庫中的數(shù)據(jù)來實現(xiàn)井下定位。一方面,為了保證井下定位的精度,位置指紋庫通常較為龐大,對比識別的復(fù)雜程度較高,速度較慢;另一方面,受井下多徑效應(yīng)、陰影效應(yīng)和非視距定位等多種因素的影響,現(xiàn)有定位識別模型的精度還有待進(jìn)一步提高。在提高定位效率方面,朱恒軍等[5]提出了基于改進(jìn) Kriging 插值的煤礦井下定位算法,該算法利用 Kriging 插值來估計其他位置指紋,降低了位置指紋庫的規(guī)模,提高了定位效率。MA 等[6]提出了一種基于 AP信號強(qiáng)度排序的定位算法,降低了定位計算耗時。金浩等[7]提出了一種基于改進(jìn)鯨魚優(yōu)化算法(Whale Optimization Algorithm, WOA)優(yōu)化極限學(xué)習(xí)機(jī)(Extreme Learning Machine, ELM)的煤礦井下定位算法,該算法選取了無需訓(xùn)練的 ELM 算法來構(gòu)建定位模型,極大地提高了學(xué)習(xí)和定位的效率。在提高定位精度方面,逄明祥等[8]提出了一種基于遺傳算法(Genetic Algorithm, GA)優(yōu)化 BP 神經(jīng)網(wǎng)絡(luò)(Back Propagation)的煤礦井下定位算法,利用 GA 算法優(yōu)化 BP 神經(jīng)網(wǎng)絡(luò)的非線性映射能力,有效提高了定位精度。史明泉等[9]提出了一種基于粒子群(Particle Swarm Optimization, PSO)優(yōu)化廣義回歸神經(jīng)網(wǎng)絡(luò)(Generalized Regression Neural Network, GRNN)的煤礦井下定位算法,與 BP 神經(jīng)網(wǎng)絡(luò)相比具有更高的學(xué)習(xí)效率。

綜上所述,結(jié)合優(yōu)化算法和機(jī)器學(xué)習(xí)算法構(gòu)建定位模型能夠有效實現(xiàn)對井下復(fù)雜環(huán)境的定位,但現(xiàn)有方法或精度不高或速度較慢。為此,本文提出一種基于量子粒子群(Quantum Particle Swarm Optimization,QPSO)優(yōu)化極限學(xué)習(xí)機(jī)的井下人員定位算法,利用量子粒子群算法更加優(yōu)越的優(yōu)化能力,提高極限學(xué)習(xí)機(jī)算法的定位精度。此外,本文將優(yōu)化的 K-means算法引入定位流程,將規(guī)模龐大的位置指紋庫劃分成若干個簇,每次定位識別時僅需要對一個簇中的位置指紋進(jìn)行對比識別,極大地降低了識別需要的時間,實現(xiàn)了快速定位,為提高井下作業(yè)人員的安全管理水平和發(fā)生事故時對作業(yè)人員快速救援的能力提供技術(shù)支持。

1 基于 WiFi 的井下定位方法

1.1 定位原理

基于 WiFi 的井下定位方法主要包括到達(dá)時間法(TOA)、到達(dá)時間差法(TDOA)、到達(dá)角度法(AOA)和信號強(qiáng)度(RSS)分析法,其中 RSS 分析法又可分為模型傳播法和位置指紋法。上述方法各有優(yōu)劣,區(qū)別在于在定位過程中采取了不同的信息。相比之下,位置指紋法精度高、成本低且無需硬件和 AP 的位置信息,適合大規(guī)模推廣,故本文選用位置指紋法來實現(xiàn)對井下人員的快速定位。

位置指紋技術(shù)的基本原理是:首先采集定位區(qū)域內(nèi)標(biāo)志點的 RSS 數(shù)據(jù),構(gòu)建位置指紋數(shù)據(jù)庫,在定位階段將實時采集到的 RSS 數(shù)據(jù)與指紋庫中的 RSS 數(shù)據(jù)進(jìn)行比對,以此來判斷待測的位置。其基本工作原理示意圖如圖1所示。

圖1 位置指紋算法的基本原理示意圖Fig.1 Basic principle of location fingerprint algorithm

1.2 定位流程

位置指紋法主要有離線訓(xùn)練和在線定位兩個實施階段。在離線訓(xùn)練階段進(jìn)行數(shù)據(jù)采集,建立指紋特征庫。首先在需要定位的區(qū)域,按照一定的距離均勻安裝好 AP 設(shè)備,然后在每個采樣位置采集不同 AP 發(fā)射的 RSS 數(shù)據(jù),將采樣點位置和 RSS 數(shù)據(jù)存入指紋特征庫。在在線定位階段,將實時采集到的 RSS 值與指紋庫中的位置信息進(jìn)行匹配,確定最終待測點所在位置。定位流程如圖2 所示。

圖2 位置指紋法的定位流程Fig.2 Locationing process of location fingerprint algorithm

2 基于QPSO優(yōu)化K-means的改進(jìn)位置指紋定位法

如前所述,位置指紋庫包含的信息越全,位置識別的精度越高,但在定位階段,則需要將待定位點的 RSS 數(shù)據(jù)與指紋庫中所有的指紋進(jìn)行比對,耗費(fèi)的時間也更高。為此,本文將 K-means 算法引入定位流程,用于降低位置指紋庫的規(guī)模,從而降低訓(xùn)練和定位所需的時間。然而,K-means 算法的性能在一定程度上取決于初始聚類中心位置的選擇,所以從某種程度上會導(dǎo)致聚類結(jié)果出現(xiàn)局部最優(yōu),而非全局最優(yōu)。為此,本文提出一種基于量子粒子群優(yōu)化的 K-means 算法,利用量子粒子群優(yōu)化聚類中心,能夠有效避免 K-means 算法對初始中心選擇的依賴,提高算法的聚類精度和速度。

2.1 K-means 聚類算法

K-means 聚類算法是最常見的算法,其基本原理是:根據(jù)數(shù)據(jù)之間的相似程度,將不帶有標(biāo)簽的數(shù)據(jù)分為K類,使得不同類的數(shù)據(jù)相似度最低而同類的數(shù)據(jù)相似度最高。該算法的基本流程如下:

(1)隨機(jī)選擇K個數(shù)據(jù)作為初始中心。

(2)計算其余數(shù)據(jù)到K個中心的歐式距離,公式如下:

(1)

式中,d(xi,xj)表示xi和xj兩個數(shù)據(jù)之間的距離。

(3)對任一數(shù)據(jù)xi,根據(jù)其與K個中心的歐式距離d的大小,將數(shù)據(jù)xi劃分至d最小的對應(yīng)中心,從而得到K組數(shù)據(jù)。

(4)重新計算每組數(shù)據(jù)的中心,并與上一次的中心位置進(jìn)行比較,若中心位置發(fā)生改變,則以新的中心為基準(zhǔn),重復(fù)步驟(2)～(3),直至中心位置不變。

2.2 量子粒子群算法

粒子群(PSO)算法是一種模擬鳥類覓食過程的進(jìn)化計算方法,通過在空間隨機(jī)生成若干個沒有質(zhì)量和體積,只有速度和位置的粒子,利用所有粒子的最佳適應(yīng)度值來更新粒子的速度和位置,使粒子不斷朝著種群中最佳位置的方向飛去,最終得到最優(yōu)結(jié)果。粒子速度和位置更新公式如式(2)和式(3)所示。

(2)

(3)

式中:xik和vik分別表示k時刻i粒子的位置和速度;xik+1和vik+1分別表示k+1 時刻i粒子的位置和速度;w表示慣性因子;c1 和c2 均表示學(xué)習(xí)因子;rand()表示[0,1]中的隨機(jī)數(shù);pbesti表示i粒子的歷史最優(yōu)位置;gbest表示i粒子的全局最優(yōu)位置。其中w反映了新的粒子方向受到粒子歷史方向的影響程度,即粒子在方向上的記憶性;c1 表示粒子在更新過程中受到局部最優(yōu)粒子的影響程度,即局部搜索能力;c2 表示粒子更新受到全局最優(yōu)粒子的影響程度,即全局搜索能力。

從式(2)不難看出,粒子群算法所需參數(shù)較多,且沒有遺傳算法的變異操作,因而在粒子更新的過程中缺少隨機(jī)性,容易陷入局部最優(yōu)。為此,本文采用量子粒子群算法(QPSO)來實現(xiàn)對 K-means 算法初始中心點的優(yōu)化選擇,QPSO 優(yōu)化算法的流程如下:

(1)初始化種群空間,生成初始粒子。

(2)計算所有粒子的適應(yīng)度,得到粒子最佳位置pbesti,計算平均最佳位置gbest,公式如下:

(4)

式中,n為粒子個數(shù)。

(3)更新粒子位置:

(5)

Pi=rand()×pbesti+(1-rand())×gbest

(6)

式中:xi表示第i個粒子的位置;pbesti表示粒子最佳位置;gbest表示全局最優(yōu)粒子位置;rand()表示[0,1]中的隨機(jī)數(shù);Pi為中間變量;α為學(xué)習(xí)率。

(4)判斷當(dāng)前粒子最佳適應(yīng)度是否滿足終止條件,若不滿足則返回步驟(2),否則結(jié)束。

2.3 基于QPSO優(yōu)化K-means的改進(jìn)位置指紋定位法

首先收集每個參考點收到的 RSS 信號,構(gòu)建初始指紋庫,再利用 QPSO 優(yōu)化 K-means算法將指紋庫劃分為K個子指紋庫,每個子指紋庫均有一個中心。在定位環(huán)節(jié),首先將移動終端采集到的位置指紋信息與各指紋庫的中心進(jìn)行初始匹配,再送入匹配度最高的子指紋庫中進(jìn)行精確定位,從而在保證定位精度的條件下最大程度地提高定位效率?；?QPSO優(yōu)化 K-means 的改進(jìn)位置指紋定位法流程如圖3 所示。

圖3 基于 QPSO 優(yōu)化 K-means 的改進(jìn)位置指紋定位法流程Fig.3 Process of improved location fingerprint locationing based on K-means optimized by QPSO

3 基于改進(jìn)極限學(xué)習(xí)機(jī)的位置指紋信號識別方法

3.1 極限學(xué)習(xí)機(jī)算法

極限學(xué)習(xí)機(jī)是一種運(yùn)用單隱含層前饋神經(jīng)網(wǎng)絡(luò)的快速學(xué)習(xí)方法,該方法不需要重復(fù)迭代訓(xùn)練,只需要設(shè)置隱含層節(jié)點個數(shù),繼而利用正則化最小二乘法得到輸出層權(quán)值的唯一解。因此,ELM 學(xué)習(xí)算法能以極快的速度進(jìn)行收斂,從而獲得良好的網(wǎng)絡(luò)性能。圖4 所示為含有l(wèi) 個隱含層節(jié)點的極限學(xué)習(xí)機(jī)結(jié)構(gòu)。

其中:[X1,X2,…,Xn]T為n維輸入向量;G(x) 為隱含層激勵函數(shù);{αij}n×l表示n行l(wèi)列的輸入層到隱含層權(quán)值矩陣;{βjk}l×m表示l行m列的隱含層到輸出層權(quán)值矩陣,bj,j=1,2,3,…,l表示每個隱含層節(jié)點對應(yīng)的閾值;n和m分別表示 ELM 的輸入、輸出節(jié)點數(shù)。則該 ELM 的m維輸出向量[Y1,Y2,…,Ym]T可以用公式(7)表示。

(7)

設(shè)T=[t1,t2,…,tm]T為極限學(xué)習(xí)機(jī)的目標(biāo)輸出值,若 ELM 能以 0 誤差逼近T,則有:

∑‖T-Y‖=0

(8)

聯(lián)立式(7)和式(8),有:

(9)

將隱含層輸出矩陣表示為H,則式(9)可以改寫為:

Hβ=T

(10)

一旦隱含層的權(quán)值和閾值隨機(jī)生成后,隱含層的輸出矩陣H也將隨之確定,ELM 的學(xué)習(xí)過程便會轉(zhuǎn)換為一個求解式(10)方程的最小二乘解的過程,則輸出層權(quán)值β可由下式得到:

β=H+T

(11)

其中,H+為矩陣H的 Moore-penrose 廣義逆。

由上述過程可以看出,在計算過程中 ELM 雖然可以迅速獲取輸出層權(quán)值的最優(yōu)解,但由于隱含層權(quán)值和閾值具有隨機(jī)性,會使得網(wǎng)絡(luò)的預(yù)測精度和泛化能力具有很強(qiáng)的不確定性。針對這一問題,本文將采用 2.2 節(jié)所述的 QPSO 算法對 ELM 的初始權(quán)值和閾值進(jìn)行優(yōu)化,以提高其預(yù)測精度和泛化能力。

3.2 基于 QPSO 優(yōu)化的 ELM 算法

利用 QPSO 算法對極限學(xué)習(xí)機(jī)的初始權(quán)值和閾值進(jìn)行優(yōu)化。首先,依據(jù) ELM 結(jié)構(gòu)參數(shù)確定個體編碼;然后,選取 3 m 以內(nèi)的定位精度作為得分函數(shù),不斷迭代得到最優(yōu)個體?；赒PSO優(yōu)化ELM 的井下人員定位算法流程如圖5 所示。

圖5 基于 QPSO優(yōu)化ELM 的井下人員定位算法流程圖Fig.5 Flow chart of underground personnel positioning algorithm based on ELM optimized by QPSO

4 實驗與分析

4.1 實驗環(huán)境與參數(shù)設(shè)置

本文采用井下 RSS 數(shù)據(jù)對所提出的改進(jìn)算法進(jìn)行井下驗證,采用射線追蹤算法進(jìn)行仿真模擬得到數(shù)據(jù)[10],并作為定位算法的訓(xùn)練集和測試集。仿真設(shè)置的井下區(qū)域為長 120 m、寬 6 m、高 4 m 的巷道,在兩側(cè)墻壁上每 30 m 布置 1 個無線 AP,AP 離地高度均為 1 m。井下巷道與無線 AP 布局示意圖如圖6 所示,射線追蹤算法參數(shù)如表1 所示,仿真結(jié)果如圖7 所示。

表1 射線追蹤算法參數(shù)設(shè)置Tab.1 Parameter setting of ray tracing method

圖6 基于射線追蹤法的井下巷道仿真示意圖Fig.6 Simulation diagram of underground roadway based on ray tracing method

(a) AP1 (b) AP3 (c) AP5

(d) AP2 (e) AP4 (f) AP6圖7 不同 AP 的 RSS 仿真結(jié)果Fig.7 RSS simulation results of different APs

4.2 實驗結(jié)果與分析

4.2.1 優(yōu)化聚類算法性能對比

本文分別采用優(yōu)化前后的 K-means 算法對初始位置指紋庫進(jìn)行聚類,并采用主成分分析法將數(shù)據(jù)壓縮至 3 維空間,以驗證聚類效果,效果對比如圖8 所示。由實驗結(jié)果可知,優(yōu)化后的聚類算法對位置指紋數(shù)據(jù)的劃分更加準(zhǔn)確,能夠提供更加高效的定位信息。

(a) K-means算法 (b) 優(yōu)化K-means算法圖8 優(yōu)化前后聚類效果對比Fig.8 Cluster performence comparison with and without optimization

為驗證本文提出的 QPSO 算法優(yōu)化 K-means 參數(shù)的能力,選取 PSO 和 GA 等常見優(yōu)化算法,在同等條件下進(jìn)行優(yōu)化能力對比,結(jié)果如圖9 所示。由圖9 可知,QPSO 在第 3次迭代時達(dá)到最優(yōu),3 m 內(nèi)定位精度達(dá)到 80.5%,GA 在第 8 次迭代時達(dá)到最優(yōu),但 3 m 內(nèi)定位精度僅有 75.2%。實驗結(jié)果表明,QPSO 算法在能夠?qū)崿F(xiàn)參數(shù)快速優(yōu)化的同時,還可以避免其陷入局部最優(yōu)的問題。

圖9 不同優(yōu)化算法的性能對比Fig.9 Performence comparison of different optimization method

4.2.2 優(yōu)化定位算法性能對比

為驗證基于優(yōu)化 K-means 和優(yōu)化 ELM 算法的井下人員定位算法的優(yōu)越性,本文采用同樣的實驗環(huán)境和軟硬件條件,在聚類中心數(shù)為 3、AP 數(shù)量為 6 的情況下,將它與支持向量機(jī)(Support Vector Machine,SVM)等常見機(jī)器學(xué)習(xí)算法進(jìn)行了對比實驗,圖10所示為不同算法在不同定位精度下的累計概率對比,表2 列出了不同算法在 3 m 以內(nèi)的精度累計概率和定位識別耗時。實驗結(jié)果表明,本文提出的定位算法精度高、速度快,能夠?qū)崿F(xiàn)對井下人員的準(zhǔn)確、高效定位。

表2 不同算法在 3 m 以內(nèi)的精度累計概率和定位識別耗時對比Tab.2 Comparison of cumulative probability of accuracy and location recognition time for different algorithms within 3 meters

圖10 不同算法在不同定位精度下的累計概率對比Fig.10 Comparison of cumulative probabilities of different algorithms with different positioning accuracy

5 結(jié)語

本文提出的基于量子粒子群優(yōu)化極限學(xué)習(xí)機(jī)的井下人員定位算法,一方面利用 QPSO算法優(yōu)越的優(yōu)化能力,提高了 ELM 算法的定位精度;另一方面利用 QPSO 算法優(yōu)化 K-means算法,降低了位置指紋庫聚類過程中對初始中心選擇的依賴性,進(jìn)一步提高了算法的聚類精度和速度。因此,本文提出的井下人員定位算法兼具定位精度和效率,具有一定的實用意義。