有限探測區域最大概率探測點尋優算法

張　馳,陳建勇

(海軍航空工程學院 電子信息工程系,山東 煙臺　264001)

?

有限探測區域最大概率探測點尋優算法

張馳,陳建勇

(海軍航空工程學院 電子信息工程系,山東 煙臺264001)

摘要：研究了二維空間有限區域目標探測的最大概率探測點的計算問題。任意分布密度條件下目標的空間發現概率是空間面積上的積分,推導了發現概率對探測點梯度的一元積分的表達式，用于最大發現概率探測點的尋優計算，能夠縮短計算時間，提高計算精度。

關鍵詞：最優搜索；梯度；直升機；吊放聲納

在一般的最優搜索理論研究中，對于連續空間中的連續運動目標，往往考慮的是連續空間的連續探測路徑[1-2]；對于離散空間中的目標，其離散空間單元是確定的單元[3]。在離散確定的單元中，找到目標概率分布最大的點進行探測能夠提高搜索效率。直升機吊放聲吶搜潛是一種在連續空間對不確定的離散區域在離散時刻進行搜索的問題[4]。吊放聲吶的探測范圍一般是圓形探測域。直升機吊放聲納按照時間順序進行多點探測目標的計算，涉及到任意目標分布密度下局部最大探測點的尋優計算。傳統的目標尋優方法是運用直接法，本研究提出了一種基于梯度的尋優算法，比傳統的算法效率更高。依據建立起的單點探測發現概率模型[4]，推導出了發現概率對探測點梯度的一元積分表達式，并用于尋優計算中。

傳統的直接法在二維空間中進行目標的局部探測搜索，是將該區域中劃分的單元格中進行依次的概率求解，比較該區域概率最大點。存在著一定的缺陷與不足，其搜索時間將會受到區域大小，劃分精度的影響，若區域范圍較大或者劃分精度高則會使計算效率變小。采用梯度算法將會避開對區域中所有的單元格進行求解，且初始探測點的位置可以隨機選取，在最大發現概率的數值尋優計算中將會提高解算效率，梯度向量的計算也將在多點探測以及全局探測中起到非常重要的作用[5-7]。

1梯度尋優算法基本模型

1.1參數定義和概率模型

(1)

發現概率對探測點a的梯度為

(2)

1.2基于梯度尋優算法計算

得到梯度的計算式后，接下來將求解梯度分量的計算方法。將探測點周圍的探測范圍設為凸集Ω。假設凸集Ω的非0邊界曲線y=φ1(x)和y=φ2(x)是連續封閉可導的。假設φ1(x)>φ2(x)，x∈[mx,Mx]；φ1(mx)=φ2(mx)，φ1(Mx)=φ2(Mx)。

同樣有Ω的非0邊界曲線x=h1(y),x=h2(y)是連續封閉可導的。假設h1(y)>h2(y)，y∈[my,My]；k1(my)=k2(my)，h1(My)=h2(My)。

定義(ξ,η)為發現目標時目標所處的位置，定義概率函數F(x,y)=P{ξ

P(a) = ?Ωb(x-a,y-b)ρ(x,y)dxdy=

(3)

令fx[x,φ1(x)]關于x的原函數為F1(x,a,b)，fx[x,φ2(x)]關于x的原函數為F2(x,a,b)，則：

(4)

因為a∈Ω，所以有常數rx>0,Rx>0，ry>0,Ry>0使：

a-rx=mx,a+Rx=Mx，b-ry=my,b+Ry=My。則有：

(5)

P(a)對a的偏導數可以表示為：

fx[Mx,φ1(Mx)]-fx[mx,φ1(mx)] +

{fx[Mx,φ2(Mx)]-fx[mx,φ2(mx)] +

變換其中的微分變量，得到：

(6)

同理

(7)

當a為局部最大點時，有▽aP(a)=0，即：

(8)

2算例仿真

由于吊放聲吶的探測范圍一般為圓形區域[8]，所以設探測域Ω是半徑為R的圓型域。令a表示Ω的圓心，同時也是探測點的位置。

對于半徑為R的圓域邊界曲線，Ω邊界的上半圓、下半圓和左半圓、右半圓可以用圓心和半徑表示為：

由式(6)、式(7)可得到圓形區域下的具體表達式

(9)

(10)

式(9)中：第一項為探測函數與分布密度的乘積在Ω右邊界上的積分；第二項為在Ω左邊界上的積分。式(10)中：第一項為探測函數與分布密度的乘積在Ω上邊界上的積分；第二項為在Ω下邊界上的積分。

陳律師沉思著答道：“剛得到她過世的消息，我很震驚，因為幾天前她剛叫我去修改了遺囑，那時候她還好好的，這實在是很蹊蹺。但她是因為和她侄子發生爭執過于激動引發心臟病而死，是正常死亡，我就想不出這還有什么解釋了，只能說是那個保姆命太好了。”

圖1　下一點前進的方向

最優計算的具體步驟：

第1步，確定探測精度和相關參數

將60×60的海域按照精度0.5 n mile的間隔劃分成單位點。

對區域內的某一點進行探測，根據初始目標分布和初始速度分布，可以得到初始時刻的目標分布概率如圖2所示。

圖2　目標分布概率

第2步，以區域內任意一點作為起始探測點

該區域的目標分布中假設任找一點(25,30)作為起始探測點，如圖3所示。

圖3　隨機選取的探測點

圖3中紅色邊界即為距離探測圓心點為6 n mile的邊界圓，下一步找到對應的點坐標。根據式(10)，以圓的左上半部分為例，將其劃為A部分，如圖4所示。x的取值從19到31，按照間隔0.5劃分，能夠求出對應的y點值。由于y方向的取值也是按照步長0.5 n mile劃分，所以需將y的值進行近似，將y的值近似成0.5的倍數得到y′值。該部分各點的對應關系如表1所示。

表1　對應的坐標點

第4步，找到相關點所在區域數組中對應的目標概率密度值

圖4　A部分對應的目標概率密度值

同理，可以得到其余B，C，D三部分的取值。分別得到4個區域中圓域邊界上對應的位置坐標，得到坐標點后根據其在數組中尋址就能找到對應點處的目標概率密度值，對于按照第一部劃分好的數組，將i,j分別表示行、列的索引，該數組尋址可以表示為A(i,j)。點坐標(x,y′)與數組的(i,j)存在以下對應關系：

例如，(x,y′)=(19,30)點出對應的行和列(i,j)=(61,39)，第61行39列中的概率分布值為ρ(61,39)=9.22×10-4。

第5步，對探測點處的梯度進行求解

(11)

(12)

將式(11)、式(12)分別進行數值積分然后求差值。式(9)同理可得。

式(10)中，當b(x-a,y-b)關于x=b對稱，有：

當探測函數b(x-a,y-b)在Ω的邊界上有b(x-a,y-b)≡Β，則：

(12)

若Β>0，則按照式(12)進行求解，當Β=0，令β=1，可得

(13)

同理，

(14)

量值在設β=1造成的差異，可以在梯度方向的步長上進行調整。

在點(25,30)處求出c1=0.052，c2=0.052，c3=0.026 6，c4=0.086 2，得到d1=0.059 6，d2=0(注意，這里d1的正負號代表左右方向上的移動，正號向右，負號向左；d2的正負號代表上下方向上的移動，正號向上，負號向下)，則下一點的方向向右移動，經計算，移動3次后到達最優點(30,30)。如圖5所示，尋優點軌跡。

圖5　起始點在(25,30)的尋優路線

此算例中，起始點尋找最優點只做了水平方向上的移動，現假設一個更具有一般性的點(24,20)，在其他初始條件不變的情況下求得尋優軌跡如圖6所示，經過6步后找到最優探測點位置。

圖6　起始點在(24,20)的尋優路線

經驗證，點(30,30)確實為該區域分布函數中目標概率最大的點。

3結論

通過算例可以得出梯度尋優算法能夠很快的找到區域內探測概率最大點，計算速度遠快于傳統的直接求解法。本文研究了在建立的有限區域探測的模型中，求離散點搜索探測概率最大點的尋優算法問題。將二維空間最大發現概率探測點的尋優問題，轉化為發現概率對探測點的梯度計算問題，而該問題在二維空間是一個一元積分的表達式，可以較快地計算出概率梯度，進而使用最速下降法等方法，數值計算逼近最優探測點。

參考文獻：

[1]肖斌，徐宏飛.搜索力最優配置的求解與收斂性分析[J].火力與指揮控制,1998,23(4):36-39.

[2]王景奇，范奎武，張最良.機動目標對搜索的最優規避[J].軍事系統工程,2001,11(1):4-9.

[3]李長明，楊健.準最優增量搜索效率分析[J].火力與指揮控制,2000,25(4):49-51.

[4]陳建勇，王健，單志超.離散時間探測隨機恒速目標的最優搜索算法[J].系統工程與電子技術，2013,35(8):1627-1630.

[5]解可新,韓健,林友聯.最優化方法[M].天津:天津大學出版社,2004:94-96.

[6]MANGEL M.Search for a randomly moving object[J].SIAM Journal of Applied Mathematics,1981(40):327-338.

[7]吳滄浦，夏元清，楊毅.最優控制的理論與方法[M].北京：國防工業出版社,2013:147-161.

[8]陳建勇,冷江,于傳健.使用吊放聲納的直升機應召搜潛發現概率[J].海軍航空工程學院學報,2004,19(5):559-561.

(責任編輯周江川)

本文引用格式：張馳,陳建勇.有限探測區域最大概率探測點尋優算法[J].兵器裝備工程學報，2016(4):118-122.

Citation format:ZHANG Chi,CHEN Jian-yong.Optimize Algorithm of the Maximum Probability of Detection Points in Limited Detection Area[J].Journal of Ordnance Equipment Engineering,2016(4):118-122.

Optimize Algorithm of the Maximum Probability of Detection Points in Limited Detection Area

ZHANG Chi, CHEN Jian-yong

(Department of Electronic and Information Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China)

Abstract:This dissertation researched calculation problem about the maximum probability of detection points of limited detection area in a two dimensional space. Under the condition of arbitrary distribution density, the discovering probability in space equals to integral on the space area. This thesis deduced one dimension integral expression of discovering probability to detection point of the gradient, which was used to the optimizing calculation of the maximum probability of detection point. It can reduce calculation time and improve calculation accuracy.

Key words:optimal search; gradient; helicopter; dipping sonar

文章編號：1006-0707(2016)04-0118-05

中圖分類號：O229

文獻標識碼：A

doi:10.11809/scbgxb2016.04.029

作者簡介：張馳(1990—)，男，碩士研究生，主要從事航空搜潛建模與仿真研究。

收稿日期：2015-09-18；修回日期：2015-10-21

【信息科學與控制工程】