一種基于蝙蝠算法的多目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)方法

王宇杰，李 宇，黃海寧

(1. 中國(guó)科學(xué)院聲學(xué)研究所，北京100190；2. 中國(guó)科學(xué)院先進(jìn)水下信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100190；3. 中國(guó)科學(xué)院大學(xué)，北京100049)

0 引 言

數(shù)據(jù)關(guān)聯(lián)問題一直是多目標(biāo)跟蹤方法中關(guān)鍵性的問題，它決定了目標(biāo)更新時(shí)所使用的探測(cè)信息，所以數(shù)據(jù)關(guān)聯(lián)算法的性能直接決定了多目標(biāo)跟蹤算法的跟蹤性能。國(guó)內(nèi)外學(xué)者對(duì)數(shù)據(jù)關(guān)聯(lián)的方法進(jìn)行了深入的研究，其中最早提出的數(shù)據(jù)關(guān)聯(lián)方法是最近鄰算法 (Nearest Neighbor, NN)[1]，它直接將量測(cè)與距離最近的目標(biāo)關(guān)聯(lián)，方法簡(jiǎn)單，運(yùn)算量小，但在處理多目標(biāo)關(guān)聯(lián)問題時(shí)，關(guān)聯(lián)正確率低。在理想化的建模假設(shè)下，多假設(shè)跟蹤算法 ( Multiple Hypothesis Tracking, MHT)[1-3]被認(rèn)為是在貝葉斯角度的最優(yōu)方法，但當(dāng)目標(biāo)數(shù)目增加時(shí)，它需要很大的計(jì)算量和內(nèi)存。概率數(shù)據(jù)關(guān)聯(lián)算法(Probabilistic Data Association, PDA)[1,3]計(jì)算落入目標(biāo)跟蹤門內(nèi)的所有量測(cè)的關(guān)聯(lián)概率，依據(jù)概率進(jìn)行關(guān)聯(lián)，但在目標(biāo)數(shù)目增加時(shí)，PDA 難以滿足關(guān)聯(lián)性能要求。在此基礎(chǔ)上發(fā)展出的聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)算法 (Joint Probabilistic Data Association,JPDA)[3]將PDA 推廣到了多個(gè)目標(biāo)的情況，使用所有觀測(cè)值和所有目標(biāo)進(jìn)行概率計(jì)算，是對(duì)多目標(biāo)進(jìn)行跟蹤的比較優(yōu)秀的方法，但是需要的計(jì)算量極大。

數(shù)據(jù)關(guān)聯(lián)問題和組合優(yōu)化問題具有很高的類似度，對(duì)多目標(biāo)數(shù)據(jù)關(guān)聯(lián)問題建模，演化為組合優(yōu)化問題，再利用一些智能優(yōu)化算法進(jìn)行最優(yōu)估計(jì)是解決多目標(biāo)數(shù)據(jù)關(guān)聯(lián)問題的一個(gè)方向[4-5]，一些仿生優(yōu)化算法[6]在多目標(biāo)關(guān)聯(lián)領(lǐng)域也取得了較好的效果。蝙蝠算法(Bat Algorithm, BA)[7-9]是Yang于2010 年提出的一種仿生優(yōu)化算法，近幾年蝙蝠算法已經(jīng)在很多領(lǐng)域取得了應(yīng)用。本文通過對(duì)數(shù)據(jù)關(guān)聯(lián)問題進(jìn)行建模，并對(duì)蝙蝠算法的搜索更新規(guī)則進(jìn)行改進(jìn)，提出了一種適用于數(shù)據(jù)關(guān)聯(lián)的改進(jìn)蝙蝠算法(Bat Algorithm Data Association,BADA)，使其可以成功應(yīng)用于數(shù)據(jù)關(guān)聯(lián)問題。經(jīng)過仿真驗(yàn)證，改進(jìn)的蝙蝠算法應(yīng)用于數(shù)據(jù)關(guān)聯(lián)切實(shí)可行，并且有比較好的效果，在計(jì)算復(fù)雜度上也遠(yuǎn)低于傳統(tǒng)算法。

1 數(shù)據(jù)關(guān)聯(lián)優(yōu)化形式

(1) 對(duì)于每一個(gè)量測(cè)，最多只有一個(gè)目標(biāo)與其關(guān)聯(lián)。

(2) 對(duì)于每一個(gè)目標(biāo)，也只有一個(gè)量測(cè)與其關(guān)聯(lián)。

數(shù)據(jù)關(guān)聯(lián)的目標(biāo)函數(shù)可以表示為

式中：gi,j表示目標(biāo)i 和量測(cè)j 的關(guān)聯(lián)程度；uij為目標(biāo)i 和量測(cè)j 關(guān)聯(lián)情況。

由上述兩個(gè)假設(shè)得到的約束條件為

由uij組成關(guān)聯(lián)矩陣U，uij的值為0 或1，當(dāng)量測(cè)與第i 個(gè)目標(biāo)關(guān)聯(lián)時(shí)，uij為1，否則為0，u0j表示第j 個(gè)量測(cè)來源于雜波信號(hào)。關(guān)聯(lián)矩陣U 的表達(dá)式為

對(duì)于量測(cè)與目標(biāo)之間的關(guān)聯(lián)程度gi,j，本文使用似然函數(shù)來評(píng)價(jià)：

其中：

式(5)、(6)中：zi表示第i 個(gè)目標(biāo)該時(shí)刻的預(yù)測(cè)值；yj表示第j 個(gè)目標(biāo)的測(cè)量值。t 時(shí)刻目標(biāo)一步預(yù)測(cè)的狀態(tài)矩陣為，S 表示殘差。

當(dāng)目標(biāo)的預(yù)測(cè)值和目標(biāo)該時(shí)刻回波正確關(guān)聯(lián)時(shí)，則似然函數(shù)gi,j的值最大。在理想情況下，當(dāng)所有目標(biāo)的預(yù)測(cè)值都和目標(biāo)該時(shí)刻的回波正確關(guān)聯(lián)，則目標(biāo)函數(shù)J 的值最大。所以，通過將數(shù)據(jù)關(guān)聯(lián)問題建模成組合優(yōu)化問題，最大化目標(biāo)代價(jià)函數(shù)J，可以解決數(shù)據(jù)關(guān)聯(lián)問題。

2 蝙蝠算法描述

蝙蝠算法是模仿蝙蝠回聲定位系統(tǒng)提出的一種仿生算法。在自然界，蝙蝠通過向四周發(fā)射超聲波脈沖進(jìn)行捕獵和定位。在接收到回波之后，它們可以確定自己的位置，并且發(fā)現(xiàn)周圍的獵物和障礙。再者，在蝙蝠群中，每一只蝙蝠都可以通過獨(dú)立搜索發(fā)現(xiàn)最有營(yíng)養(yǎng)的區(qū)域，或者和種群中其它個(gè)體交流，向其它個(gè)體發(fā)現(xiàn)的最有營(yíng)養(yǎng)的區(qū)域移動(dòng)。蝙蝠算法最重要的思想是蝙蝠的定位系統(tǒng)運(yùn)作方式，為了對(duì)其有一些合適的調(diào)整，Yang 提出了以下規(guī)則[7-9]：

(1) 所有的蝙蝠都使用回聲定位系統(tǒng)對(duì)目標(biāo)位置進(jìn)行探測(cè)，并且可以區(qū)分獵物和障礙。

(2) 所有的蝙蝠在一定的位置以一定的速度隨機(jī)飛行去搜索目標(biāo)，它們發(fā)射的聲波頻率、聲強(qiáng)和聲脈沖發(fā)射頻率以一定的規(guī)律變化。在理想化的規(guī)則里，假設(shè)每一個(gè)蝙蝠都可以自動(dòng)地調(diào)整聲波頻率和脈沖發(fā)射的頻率，這種自動(dòng)調(diào)節(jié)系統(tǒng)依據(jù)離目標(biāo)獵物的遠(yuǎn)近進(jìn)行調(diào)節(jié)。

(3) 在真實(shí)的環(huán)境中，蝙蝠發(fā)聲聲強(qiáng)的變化可以依據(jù)多種方式。而我們假設(shè)聲強(qiáng)是從最大聲強(qiáng)向最小的聲強(qiáng)變化。

由上述規(guī)則，Yang 提出的經(jīng)典蝙蝠算法，算法如下：

(1) 定義目標(biāo)函數(shù)ξ ( x)；

(3) 對(duì)蝙蝠群中的每一只蝙蝠的位置xi進(jìn)行步驟(4)；

(5) 對(duì)蝙蝠群中的每一只蝙蝠位置ix 進(jìn)行步驟(6)～(11)；

(6) 使用式(7)、(8)、(9)產(chǎn)生新的蝙蝠位置；

(8) 本地搜索：在最優(yōu)蝙蝠位置附近更新該只蝙蝠；

(10) 接受該蝙蝠為當(dāng)前最優(yōu)蝙蝠x?；

(12) n=n+1；

(13) 循環(huán)執(zhí)行步驟(5)～(12)，直至達(dá)到結(jié)束條件；

(14) 排序蝙蝠群中的蝙蝠，輸出最優(yōu)蝙蝠位置x?。在步驟(7)、(9)中rand[0,1]表示取0～1 之間的隨機(jī)數(shù)。

在每一次循環(huán)中，蝙蝠群中的每一只蝙蝠都會(huì)進(jìn)行移動(dòng)，對(duì)于每次移動(dòng)，使用式(7)～(9)進(jìn)行更新：

其中：β 是一個(gè)0～1 之間的隨機(jī)數(shù)；在算法流程中x?是蝙蝠群中當(dāng)前時(shí)刻最優(yōu)蝙蝠位置；和代表了第i 只蝙蝠在第n 次迭代中的速度和位置。式(7)被使用來限制蝙蝠移動(dòng)的范圍和速度。算法流程中第(8)步本地搜索部分，是從當(dāng)前時(shí)刻蝙蝠群中選擇最優(yōu)蝙蝠，使用隨機(jī)漫步在最優(yōu)蝙蝠附近生成新的蝙蝠方案更新該只蝙蝠。

這里 的α 和γ 是固定值，并且0＜α ＜1 ，γ＞ 0。從式(10)和(11)中可以看出，隨著n 趨向于無窮大時(shí)，趨向于0，趨向于。在很多文章中，為了簡(jiǎn)化算法，α 和γ 的取值一般是相同的，在0.90～0.99 范圍內(nèi)，本文選取α =γ = 0.98。

3 適用于數(shù)據(jù)關(guān)聯(lián)的蝙蝠算法

經(jīng)典蝙蝠算法主要用于解決連續(xù)性優(yōu)化問題，而組合優(yōu)化問題是一種離散優(yōu)化問題。受蝙蝠算法解決旅行商問題(Traveling Salesman Problem, TSP)[10]的啟發(fā)，需要對(duì)經(jīng)典蝙蝠算法進(jìn)行一些改進(jìn)，以使其可以適用于數(shù)據(jù)關(guān)聯(lián)問題。

在本文所提出的算法中，蝙蝠群的每一只蝙蝠都代表一種可能的關(guān)聯(lián)方案。比如某時(shí)刻存在4個(gè)目標(biāo)，傳感器探測(cè)到了9 個(gè)量測(cè)，則蝙蝠群中的第i 只蝙蝠位置可能為xi= (2,5,3,9)，其第一個(gè)位置的2 表示第二個(gè)量測(cè)和第一個(gè)目標(biāo)關(guān)聯(lián)，其余類似。經(jīng)典蝙蝠算法中的一些參數(shù)ri、 Ai、fi和iv 也并不都適用于離散的數(shù)據(jù)關(guān)聯(lián)，需要進(jìn)行一些新的定義。

在經(jīng)典的算法中，速度vi的更新由聲波頻率if 和該蝙蝠與最優(yōu)蝙蝠之間的距離共同決定，如式(8)所示，其顯然是無法應(yīng)用于離散的數(shù)據(jù)關(guān)聯(lián)問題。從式(8)中可以看出，速度的大小是依賴于該蝙蝠與最優(yōu)蝙蝠之間的距離再乘上一個(gè)系數(shù)，聲波頻率fi。針對(duì)數(shù)據(jù)關(guān)聯(lián)問題，本文對(duì)其進(jìn)行了調(diào)整，使用漢明距離DHamming來定義兩只蝙蝠的距離，定義該蝙蝠的速度為1 到漢明距離之間的一個(gè)隨機(jī)整數(shù)，表達(dá)式為

式中，rand[]?表示取隨機(jī)數(shù)。

式(9)是蝙蝠算法中蝙蝠的更新運(yùn)算，該式同樣無法應(yīng)用于數(shù)據(jù)關(guān)聯(lián)問題中，本文定義運(yùn)算⊕進(jìn)行蝙蝠的更新，公式為

運(yùn)算⊕參照以下規(guī)則進(jìn)行：

(1) 如某一蝙蝠為(2,5,3,9)，首先隨機(jī)確定一個(gè)位置，比如第三個(gè)位置，然后隨機(jī)生成一個(gè)量測(cè)編號(hào)，比如4，使用新生成的量測(cè)編號(hào)代替原來位置的量測(cè)編號(hào)，則該只蝙蝠的鄰近蝙蝠就是(2,5,4,9)。

(2) 如果隨機(jī)產(chǎn)生的量測(cè)編號(hào)發(fā)生重復(fù)，比如第三個(gè)位置隨機(jī)生成的量測(cè)編號(hào)為2，而(2,5,2,9)不滿足前文提出的第二條假設(shè)。這時(shí)對(duì)調(diào)產(chǎn)生重復(fù)的兩個(gè)量測(cè)編號(hào)的位置，則該只蝙蝠的鄰近蝙蝠就是(3,5,2,9)。

使用上述提出的產(chǎn)生鄰近蝙蝠位置的方法，在每一次迭代過程中，產(chǎn)生個(gè)該蝙蝠的鄰近蝙蝠，在其中選擇最優(yōu)的一只更新位置，得到位置。

下面給出了適用于數(shù)據(jù)關(guān)聯(lián)的改進(jìn)后的蝙蝠B(yǎng)ADA 算法如下：

(1) 使用式(1)定義目標(biāo)函數(shù)J ( x )；

(3) 對(duì)蝙蝠群中的每一只蝙蝠ix 進(jìn)行步驟(4)；

(5) 對(duì)蝙蝠群中的每一只蝙蝠位置ix 進(jìn)行步驟(6)～(11)；

(6) 使用式(12)、(13)產(chǎn)生新的蝙蝠；

(8) 本地搜索：在最優(yōu)蝙蝠位置附近更新該只蝙蝠位置；

(10) 接受該蝙蝠位置為最優(yōu)蝙蝠位置x?；

(12) n=n+1；

(13) 循環(huán)執(zhí)行步驟(5)～(12)，直至達(dá)到結(jié)束條件；

(14) 排序蝙蝠群中的蝙蝠位置，輸出最優(yōu)蝙蝠位置x?。

結(jié)束條件一般為目標(biāo)函數(shù)達(dá)到要求或者循環(huán)次數(shù)到達(dá)預(yù)設(shè)值。在本文中，設(shè)置當(dāng)循環(huán)次數(shù)n達(dá)到15 次時(shí)，算法結(jié)束，排序蝙蝠群中的蝙蝠位置，輸出的最優(yōu)蝙蝠位置x?為最終的數(shù)據(jù)關(guān)聯(lián)結(jié)果。

4 仿真實(shí)驗(yàn)與實(shí)測(cè)數(shù)據(jù)處理

4.1 仿真實(shí)驗(yàn)

為驗(yàn)證BADA 算法的性能，仿真了雙目標(biāo)情況下的方位歷程信息。兩個(gè)目標(biāo)起始方位分別為250°和280°，在65 s 附近發(fā)生了一次交叉，如圖1 所示。圖1 中圓圈和三角分別表示目標(biāo)1 和目標(biāo)2 的回波，干擾回波沒有在圖中體現(xiàn)。設(shè)檢測(cè)概率Pg=0.95，干擾回波在觀測(cè)門限內(nèi)均勻分布，雜波密度為0.1，目標(biāo)回波服從正態(tài)分布，存在均值為0，標(biāo)準(zhǔn)差為0.6 的加性高斯白噪聲，使用卡爾曼濾波進(jìn)行跟蹤。用NN 算法和JPDA 算法進(jìn)行對(duì)比，結(jié)果如圖2 所示。JPDA 算法和BADA 算法在兩個(gè)目標(biāo)發(fā)生交叉時(shí)都可以進(jìn)行正確的關(guān)聯(lián)，而NN 算法在目標(biāo)發(fā)生交叉時(shí)，發(fā)生關(guān)聯(lián)錯(cuò)誤的概率較大。

圖1 兩目標(biāo)回波仿真數(shù)據(jù)Fig.1 Echo simulation data of two targets

圖2 NN 算法、JPDA 算法和BADA 算法仿真結(jié)果比較Fig.2 Comparisons between the simulation results of NN algorithm, JPDA algorithm and BADA algorithm

分別使用BADA 算法、JPDA 算法和NN 算法進(jìn)行1 000 次的獨(dú)立重復(fù)試驗(yàn)，統(tǒng)計(jì)其平均絕對(duì)誤差、平均運(yùn)算時(shí)間和正確關(guān)聯(lián)概率。一次正確的關(guān)聯(lián)為兩個(gè)目標(biāo)的跟蹤結(jié)果始終保持在目標(biāo)真實(shí)位置的附近，如圖2 中JPDA 算法和BADA 算法的結(jié)果，而NN 算法對(duì)于目標(biāo)2 的跟蹤在交叉時(shí)發(fā)生了錯(cuò)誤。兩個(gè)目標(biāo)中只要存在一個(gè)目標(biāo)發(fā)生關(guān)聯(lián)跟蹤錯(cuò)誤，即認(rèn)為關(guān)聯(lián)跟蹤錯(cuò)誤。正確關(guān)聯(lián)概率使用式(14)計(jì)算：

其中：η 為正確關(guān)聯(lián)概率；l 為正確關(guān)聯(lián)跟蹤次數(shù)；K 為獨(dú)立重復(fù)試驗(yàn)總數(shù)，本文中取1 000 次。

在當(dāng)高斯噪聲均值為0、標(biāo)準(zhǔn)差為0.3 時(shí)的情況下，3 種算法都有很高的正確關(guān)聯(lián)概率，NN 算法的運(yùn)算時(shí)間最短，誤差最大，比較結(jié)果列于表1中。當(dāng)高斯噪聲均值為0、標(biāo)準(zhǔn)差為0.6 時(shí)算法性能比較結(jié)果見表2。BADA 算法在誤差和正確關(guān)聯(lián)概率與JPDA 算法相近的情況下，運(yùn)算時(shí)間極大的減小，而NN 算法雖然運(yùn)算時(shí)間極快，但其誤差較大，正確關(guān)聯(lián)概率過低，在應(yīng)用中會(huì)出現(xiàn)大量的關(guān)聯(lián)錯(cuò)誤。

表1 雙目標(biāo)情況下3 種算法性能比較(噪聲標(biāo)準(zhǔn)差=0.3)Table 1 Performance comparison of three algorithms in the case of two targets ( noise standard deviation = 0.3)

表2 雙目標(biāo)情況下3 種算法性能比較(噪聲標(biāo)準(zhǔn)差=0.6)Table 2 Performance comparison of three algorithms in thecase of two targets ( noise standard deviation = 0.6)

為驗(yàn)證更為復(fù)雜情況下的算法性能，仿真了同時(shí)存在6 個(gè)目標(biāo)的方位歷程數(shù)據(jù)，6 個(gè)目標(biāo)發(fā)生了多次交叉，復(fù)雜度較高。圖3 是使用BADA 算法的關(guān)聯(lián)跟蹤結(jié)果，不同標(biāo)記分別代表不同目標(biāo)的回波。干擾回波在觀測(cè)門限內(nèi)均勻分布，雜波密度為0.1，目標(biāo)回波服從正態(tài)分布，存在均值為0，標(biāo)準(zhǔn)差為0.35 的加性高斯白噪聲，干擾回波同樣存在但未在圖中體現(xiàn)，不同顏色的軌跡是使用BADA 算法對(duì)不同目標(biāo)進(jìn)行關(guān)聯(lián)跟蹤的結(jié)果?？梢钥闯鲈谲壽E更為復(fù)雜的多目標(biāo)情況下，BADA算法對(duì)6 個(gè)目標(biāo)進(jìn)行了準(zhǔn)確的關(guān)聯(lián)，未出現(xiàn)關(guān)聯(lián)跟蹤錯(cuò)誤。

圖3 基于BADA 算法六目標(biāo)跟蹤結(jié)果Fig.3 Tracking results of six targets based on BADA algorithm

同樣，用上述的6 個(gè)目標(biāo)方位仿真數(shù)據(jù)，分別對(duì)BADA 算法、JPDA 算法和NN 算法進(jìn)行1000 次獨(dú)立、重復(fù)試驗(yàn)，計(jì)算3 種算法的平均絕對(duì)誤差、平均運(yùn)算時(shí)間和正確關(guān)聯(lián)概率。在正確關(guān)聯(lián)概率的計(jì)算中，只要有一個(gè)目標(biāo)關(guān)聯(lián)錯(cuò)誤即為錯(cuò)誤關(guān)聯(lián)。算法性能比較結(jié)果見表3，BADA 算法的運(yùn)算時(shí)間相較于JPDA 算法有了明顯的降低，只有不到后者的10%，具有更好的實(shí)時(shí)運(yùn)算性能，且正確關(guān)聯(lián)概率也處于較高水平。

表3 6 個(gè)目標(biāo)情況下3 種算法性能比較Table 3 Performance comparison of three algorithms in the case of six targets

4.2 實(shí)測(cè)數(shù)據(jù)處理

圖4 是對(duì)某次海試的某段數(shù)據(jù)進(jìn)行頻域波束形成之后的結(jié)果。在這段時(shí)間內(nèi)存在多個(gè)目標(biāo)并且目標(biāo)的方位軌跡之間存在交叉、平行和逐漸靠近，也存在有大量的干擾和噪聲，復(fù)雜度極高，且具有一定代表性。閾值檢測(cè)之后使用BADA 算法進(jìn)行關(guān)聯(lián)跟蹤，結(jié)果如圖5 所示。圖5 中白色圓圈是對(duì)方位歷程圖進(jìn)行閾值檢測(cè)的結(jié)果，閾值檢測(cè)過程中每10 s 得到一個(gè)方位檢測(cè)結(jié)果，不同顏色分別代表不同目標(biāo)的跟蹤結(jié)果。

由圖5 可見，BADA 算法對(duì)6 個(gè)較強(qiáng)目標(biāo)進(jìn)行了正確的關(guān)聯(lián)，在復(fù)雜軌跡情況和干擾回波影響下都沒有發(fā)生關(guān)聯(lián)跟蹤錯(cuò)誤。

圖4 某次海試的某段方位歷程圖Fig.4 A section of bearing-time-record in a certain sea trial

圖5 BADA 算法關(guān)聯(lián)跟蹤結(jié)果Fig.5 Tracking results of the BADA algorithm

5 結(jié) 論

針對(duì)多目標(biāo)跟蹤中的數(shù)據(jù)關(guān)聯(lián)問題，本文提出了一種基于蝙蝠算法的數(shù)據(jù)關(guān)聯(lián)方法。將數(shù)據(jù)關(guān)聯(lián)問題建模成組合優(yōu)化問題，然后通過改進(jìn)蝙蝠算法，使其可以適用于解決多目標(biāo)跟蹤中的數(shù)據(jù)關(guān)聯(lián)問題，并且取得了較好的效果。該方法本質(zhì)上是一種近似最優(yōu)的方法。通過仿真結(jié)果可以看出，該方法在多目標(biāo)、多雜波、多航跡交叉的情況下可以正確地關(guān)聯(lián)目標(biāo)，關(guān)聯(lián)跟蹤性能與JPDA 處于同一級(jí)別，運(yùn)算復(fù)雜度迅速減小，實(shí)時(shí)性更好。通過對(duì)試驗(yàn)數(shù)據(jù)的分析，證明基于蝙蝠算法的數(shù)據(jù)關(guān)聯(lián)方法應(yīng)用于真實(shí)情況是切實(shí)可行的，并且有較好的關(guān)聯(lián)跟蹤效果。