基于貪婪算法的機動雷達陣地選擇

2021-12-28 00:55:12何文思李宏權師維克簡久生

艦船電子對抗 2021年6期

何文思，李宏權，師維克，趙卿，簡久生

(1.解放軍95445部隊，云南大理 671000；2.空軍預警學院，湖北武漢 430019)

0 引言

機動雷達作為預警裝備的補充力量，陣地的選擇對其充分發揮探測性能、滿足防空作戰需求有決定性作用。隨著部隊裝備發展和體制調整，機動雷達具有裝備型號多、戰技術性能優、適應性強、調整部署快等特點，往往成建制出動多部機動雷達，因此其調整部署的陣地選擇問題也越來越突出，快速進行多部機動雷達陣地選擇，確保遇有突發情況能及時解決成建制機動雷達的最優部署問題顯得尤為重要。

一般在進行雷達陣地選擇時，根據任務需求確定部署區域，先綜合考慮地形條件，進行圖上初步選點，再有重點地進行實地勘測，提出陣地選擇方案建議。傳統的雷達陣地選擇方法主要有層次分析法、模糊綜合評價法、灰色關聯分析法等[1-4]，對單部雷達陣地選擇研究多，對多部雷達陣地選擇運用少，決策指標多，不能滿足新型機動雷達裝備的現實需要。文獻[5]綜合闡述了選址問題中確定性覆蓋和概率覆蓋問題，對集合覆蓋模型(LSCP)給出了標準型的公式。文獻[6]提出了一種改進的貪婪算法來彌補最優解搜索不足的問題，為區域覆蓋問題提供了新思路。文獻[7]提出了一種將監測區域按照均勻離散點的網格劃分方法來解決感知區域覆蓋面積計算難的方法。本文結合實戰化條件下機動雷達補盲作戰部署意圖，從雷達探測效能的角度，圍繞對盲區空域全覆蓋的決策指標，引入集合覆蓋模型，采用貪婪算法，進行陣地選點決策，并結合Python編程語言實現仿真驗證，速度快，操作簡單，在解決機動雷達陣地快速選擇問題上提供了一種新的解決方法。

1 相關原理

1.1 貪婪算法

貪婪算法也叫貪心算法，它以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解[8]。貪婪算法具有自頂向下的處理問題方式，采取分而治之的思想通過局部最優解來求解整體最優解，是一種啟發式算法，主要在求解非確定性多項式完全問題如集合覆蓋、旅行商問題上具有很好的效果。對于集合覆蓋問題，利用貪婪算法求解，實現過程較簡單，時間性能最好[6]。貪婪算法解決問題的思路大致分為三部分：

(1) 首先對問題進行分析，明確問題的總目標；

(2) 然后對總目標分而治之，進一步細化分解成為分支目標；

(3) 最后設置目標達成的貪婪策略，圍繞貪婪策略進行不斷迭代求解問題，其中找到問題的貪婪策略是關鍵。

貪婪算法的優點在于求解問題的每一步都是去選擇符合貪婪策略的最優解為出發點，易于實現，在計算機執行過程中，時間成本低。

1.2 集合覆蓋選址

集合覆蓋最早于1971年正式提出，用于應急服務設施選址規劃的模型，此類問題可以表述為：以服務需求點和可選設施點的集合為前提，給出指定的服務覆蓋距離，當設施點的數量未給定且未受限制時，需要尋求一種最好的配置方案，確保建設最少的服務設施完成對所有服務需求點的全覆蓋。它要求建立最少的服務設施點以覆蓋所有的需求點[7]。集合具有易操作、交互性好和去重復性的特點，對集合進行運算操作時如交集、并集、差集等比較方便和容易理解。集合覆蓋選址屬于選址問題的一個分支，且已被廣泛運用于解決消防點、醫院定點、應急避難場所等應急服務設施和公共設施點的選址問題中。

機動雷達的陣地選擇，根據任務需要，往往存在多個可選陣地和多型雷達裝備的情況。在同型雷達裝備數量充足的情況下，篩選最優的部署方案是一個精確計算需要耗費大量時間的問題，且隨著雷達型號和可選陣地點的增加，計算時間成冪數級增長。此類問題可以簡化為集合覆蓋模型求解，即選擇最少的陣地選點使其雷達探測范圍覆蓋任務部署要求的目標空域[9-10]。

1.3 基于集合覆蓋的陣地選擇模型

當前，機動雷達對陣地環境適應性強、戰技術性能好，重點要關注對作戰部署意圖的契合度。機動雷達陣地的選擇目的是在短時間內篩選出符合任務需求的雷達部署方案，是一個綜合性軍事問題，實際中往往是多部雷達和多陣地的優化組合決策。機動雷達的陣地選擇可以簡化為實現任務空域的覆蓋，即實現對某一確定高度層空域的完全覆蓋，同時能夠對重點空域實現多重覆蓋，為模型搭建設立如下規則：

規則1：雷達的探測空域為任務要求的指定高度層之間的整個空域，可劃分為重點空域和一般空域。

規則2：陣地選址要體現對重點空域的探測能力，即在雷達架設后，對重點空域的低空、超低空目標的預警探測能力。

規則3：機動雷達部署任務對陣地的總要求,是在責任區內針對固定雷達的低空探測盲區，部署機動雷達對盲區目標盡可能全部探測覆蓋。

為了綜合考慮雷達陣地和責任區內各因素的影響，用預先計算的陣地對目標空域覆蓋能力作為陣地選擇的決策指標，覆蓋能力表示為：

(1)

式中：VE為目標空域E的體積；VA(E)為空域E內，第A個陣地選擇方案的雷達探測覆蓋空域與任務空域E的交集。

如果QA≥1，則表明陣地方案能夠對空域E全覆蓋。

任務需求的補盲區域，按高度層轉化為平面空域，空域邊界可以由經緯度表示，對于預選陣地MI上部署PJ型雷達的部署計劃記為部署方案AN，將任務空域E網格化以任務空域集合Ω表示，若目標空域網格集合Ω內任一網格的中心點β在部署雷達探測距離內，則定義該網格被陣地部署方案AN覆蓋，那么雷達部署方案AN覆蓋的所有網格點集合SN即為：SN={β1,β2,…,βX}，如圖1所示。

圖1 陣地選點雷達對目標空域覆蓋情況

顯而易見，每一個網格集合SN對應一陣地選點部署雷達方案的目標空域覆蓋情況，且SN是目標空域E的子集。尋找最優的SN集合Q，確保部署最少的雷達并覆蓋任務確定的高度層重點空域Eh，表達式為：

Qmin=min{Qs}

(2)

式中：Qs表示Q中含有的子集合。

那么，基于集合覆蓋的陣地選擇模型可以表述如下：

(3)

(4)

Xk∈{0,1},?k∈A

(5)

式中：k為可選陣地序號；n為需要探測或補盲的任務空域網格點序號；A為所有可選陣地集合；E為任務空域網格集合；Xk為第k個陣地部署雷達情況；On為可以探測覆蓋任務空域網格點n的陣地雷達部署方案集合。

式(3)規定服務可選陣地數量最小，式(4)規定對空域網格點n,必須有雷達達到一次以上覆蓋；式(5)規定變量取值范圍。

2 算法設計

雷達陣地選擇涉及定性分析多，影響因素受主觀影響指標評判不統一。對此，在指定部署區域內，計算選擇盡量少的雷達陣地，實現雷達對任務部署要求的目標探測區域達到探測范圍最大化。

使用貪婪算法求解時，首先根據地理高程數據測算各陣地選點方案AN的探測范圍內對目標空域E的覆蓋情況，以網格集合的形式表示。然后逐次迭代選取其中覆蓋網格最多者，循環處理至滿足全覆蓋要求，當陣地選點雷達探測范圍覆蓋所有的網格點，即認為覆蓋了任務需求的所有目標空域。盡量找到最少數量的陣地點來覆蓋所有的網格點。

通過采集數字高程數據來表征目標空域和陣地探測覆蓋空域，在數字高程數據中，存儲有地形的經緯度和高度信息，并以柵格形式存儲，從而能有效量化地形對陣地的影響。分高度層計算目標空域E的方法是：先對目標空域進行柵格化處理，按照固定步長劃分網格的方法來近似計算雷達覆蓋空域情況，根據地形數據，剔除地形高程中超過任務空域高程的網格點，則高度為h的目標探測空域Eh,可以用集合表示為：

(6)

式中：X，Y，Z為空域E中網格的中心坐標；a，b，c為空域E的邊界。

有了目標空域網格集合后，那么第P部雷達部署在第M個陣地時，雷達在h高度層的探測網格集合Apmh計算方法是：先提取陣地選點在數字高程中三維坐標數據P(Xi,Yi,Zi)，根據歷史積累的雷達探測能力數據，對于任一空域網格中心點β，只要滿足在雷達探測距離內，則判斷雷達覆蓋該空域。為簡化模型，主要考慮最大探測距離的影響，根據雷達方程,雷達最大探測距離與自身性能相關，在確定檢測概率和虛警概率下,就可以確定在高度層h上雷達最大探測距離Rmax和最小探測距離Rmin。計算h高度層的探測網格集合表達式為：

(7)

式中：Rmax和Rmin為陣地雷達在高度層h上的最遠探測距離和最近探測距離；d，e，f為陣地選址范圍。

Rmin是雷達頂空盲區，表示為：

(8)

依據公式(6)、(7)、(8)計算得到，任一可選部署方案AN對任務空域覆蓋情況的網格集合SN。

算法具體步驟如下：

(1) 根據任務需求，網格化任務需求的目標空域E。按照網格的步長越小則雷達覆蓋面積與真實覆蓋面積越近似的原則，取方位步長為 0.01°，具體步長參照地理高程數據的分辨率選取。

(2) 根據具體雷達性能參數，運用歷史積累的雷達探測數據近似計算探測能力的方法，可以得出所有可行陣地點AN上雷達對目標空域E的覆蓋情況SN，即能探測到的空域網格。

(3) 遍歷所有候選陣地點，比較找出一個對現有目標空域覆蓋最大的陣地選點SN_max,將該陣地選點加入到一個選點結果集合C中，把該陣地覆蓋的網格在下次比較時從現有網格集合E中去掉；

(4) 重復上一步的查找，直到覆蓋了目標空域E的全部網格或者無陣地選點可比較，記錄當前雷達陣地選點結果。

(5) 采用隨機跳坑處理，隨機移除一定百分比的陣地選點，將剩下的雷達陣地選點作為新的候選陣地點。重復第(3)、(4)步。

(6) 重復迭代該策略一定次數后，最后比較輸出最優雷達陣地選點。

3 仿真試驗

3.1 數據準備

需要采集記錄可選陣地的基本信息，如遮蔽角、高度、探測威力等，既可以依據先期人工初步勘察的陣地資料，也可以根據圖上作業法完成數據的準備。主要數據包含目標空域經緯度、陣地點經緯高以及遮蔽地物經緯高數據。另外還需要雷達技術性能參數，既可以依據雷達出廠性能指標數據，還可以收集雷達平時積累的實測數據，主要數據包含檢測概率、虛警概率、波長、目標截面積、雷達峰值功率、天線方向圖函數、接收機靈敏度、實測垂直威力圖、實測不同目標最遠探測距離等。為計算方便，直接給出雷達最大探測距離，主要數據采集樣表如表1、表2、表3和表4所示，探測威力圖如圖2樣表采集。

表1 陣地選點三維地理坐標

表2 目標空域地理坐標

表3 雷達最大探測距離情況(Pd=0.5,Pf=10-6,δ=2 m2)

表4 雷達遮蔽角數據采集格式

圖2 探測威力圖

根據數字高程數據，可以實現可視化的陣地點顯示，如圖3所示。

圖3 數字高程數據中陣地候選點

3.2 環境條件

計算雷達探測威力時，不考慮因天氣、氣候、周邊電磁環境等因素造成的影響。雷達陣地數據由數字高程數據計算得出，假設數據精度滿足分析需求，實驗平臺為64位Windows7系統，Intel(R)Core(TM)i7-3770CPU，主頻3.4 GHz，內存8 GB，用Python語言編程仿真實現。

3.3 實驗驗證

準備在某地區進行雷達陣地選擇，在確定的部署區域內，實現對3 000 m高度層的目標空域的補網。羅列所有可行陣地選點，利用數字地形高程數據計算分析，得出所有可行點陣地雷達探測情況數據，例如：對300 km×100 km的部署區域，按照任務條件篩選，羅列選出7個可行陣地點。

將任務部署要求的目標空域網格化，使其由5×5 個網格組成，每個網格20 km×20 km，要求補網覆蓋其中的12個網格點(a,b,c,d,e,f,g,h,i,j,k,l)，對羅列選出的7個陣地可行點進行貪婪算法運算，求解得出以最少陣地點部署雷達后能達到對目標空域12個網格點的覆蓋最大化。計算分析得出7個陣地點雷達探測覆蓋情況,如表5所示。

表5 每個陣地選點的雷達探測覆蓋情況

在該任務中，假設由任務需求的目標空域組成的網格集合為E={a,b,c,d,e,f,g,h,i,j,k,l}。

現在考慮7個待選陣地的集合S={A1,…，A7}。S中每個待選陣地在確定高度層上對目標空域覆蓋的網格集合為：A1={a,b,c,d}，A2={e,f,g,h}，A3={j,k,l}，A4={a,e}，A5={b,f,g}，A6={c,d,g,h,k,l}，A7={l}。最少覆蓋集應該是QE={A1,A2,A3}。這里給出的算法選擇的集合是QG={A2,A1,A3}。通過貪婪算法結合Python編程實現，有效得到陣地選擇中空域覆蓋的近似解。對于求得P種型號雷達在M個陣地選點中的最小覆蓋任務的陣地選擇，整個計算過程需要計算次數為(P×M)2次。若需要篩選符合任務要求的3型雷達在4個陣地上選點決策，則精確算法是貪婪算法耗時的28倍。在實際應用中，可選陣地和雷達型號的數量要多得多且方案變化大，采用貪婪算法能較好體現出時間運行上的優勢，算法運算時間與陣地選點數和雷達型號數關系如圖4所示。