王宇杰，李 宇，黃海寧

(1. 中國科學院聲學研究所，北京100190；2. 中國科學院先進水下信息技術重點實驗室，北京100190；3. 中國科學院大學，北京100049)

0 引 言

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

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

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

(1) 對于每一個量測，最多只有一個目標與其關聯(lián)。

(2) 對于每一個目標，也只有一個量測與其關聯(lián)。

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

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

由上述兩個假設得到的約束條件為

由uij組成關聯(lián)矩陣U，uij的值為0 或1，當量測與第i 個目標關聯(lián)時，uij為1，否則為0，u0j表示第j 個量測來源于雜波信號。關聯(lián)矩陣U 的表達式為

對于量測與目標之間的關聯(lián)程度gi,j，本文使用似然函數(shù)來評價：

其中：

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

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

2 蝙蝠算法描述

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

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

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

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

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

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

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

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

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

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

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

(12) n=n+1；

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

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

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

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

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

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

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

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

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

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

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

運算⊕參照以下規(guī)則進行：

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

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

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

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

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

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

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

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

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

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

(12) n=n+1；

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

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

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

4 仿真實驗與實測數(shù)據(jù)處理

4.1 仿真實驗

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

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

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

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

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

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

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

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

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

圖3 基于BADA 算法六目標跟蹤結果Fig.3 Tracking results of six targets based on BADA algorithm

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

表3 6 個目標情況下3 種算法性能比較Table 3 Performance comparison of three algorithms in the case of six targets

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

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

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

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

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

5 結 論

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