施建禮，劉志浩，潘 爽

（海軍潛艇學(xué)院，山東 青島 266199）

0 引言

路徑規(guī)劃問題在軍事作戰(zhàn)平臺的任務(wù)及攻擊籌劃中具有重要的影響作用。對于飛機(jī)、水面艦艇及潛艇等傳統(tǒng)意義上的載運(yùn)工具，乃至具有路徑規(guī)劃功能的導(dǎo)彈魚雷等兵器而言，性能優(yōu)良的路徑，能夠充分利用戰(zhàn)場態(tài)勢，通過規(guī)避探測，增大己方的防御能力，同時以增大搜索概率的方式強(qiáng)化己方攻擊能力，進(jìn)而增加整體的作戰(zhàn)效能。由于戰(zhàn)場態(tài)勢瞬息萬變，導(dǎo)致作戰(zhàn)過程對時間極為敏感，進(jìn)而使得作戰(zhàn)平臺路徑規(guī)劃算法的快速性成為衡量其性能優(yōu)異的重要標(biāo)準(zhǔn)。目前路徑規(guī)劃問題常采用的方法主要有圖論法、概率路線圖法、A*算法、蟻群算法、粒子群算法、模擬退火法等。蟻群算法的基本思想是由意大利Dorigo 在1991 年提出的一種智能算法，該方法通過模擬蟻群的社會行為完成對最優(yōu)解的動態(tài)篩選。在旅行商問題（TSP）和二次資源分析（QAP）問題等經(jīng)典的優(yōu)化問題求解中，蟻群算法均取得了較好的結(jié)果。隨時代進(jìn)步，在近年的互聯(lián)網(wǎng)通信、網(wǎng)絡(luò)優(yōu)化、物流調(diào)度等多種應(yīng)用領(lǐng)域中，蟻群算法都體現(xiàn)了其在求解復(fù)雜問題時的可行性和優(yōu)越性。在軍事領(lǐng)域中，蟻群算法也在機(jī)器人、無人機(jī)、飛機(jī)、水面艦艇、潛艇、魚雷和導(dǎo)彈等多種軍事平臺及兵器的路徑規(guī)劃中取得了很大的成就。但在大規(guī)模的軍事作戰(zhàn)空間分析中，受限于自身固有的初始信息匱乏及早熟性等特點(diǎn)，使得蟻群算法在面對數(shù)據(jù)量大的任務(wù)空間時存在一定的缺陷［1］。

本文以潛艇路徑規(guī)劃為例，基于蟻群算法，引入遺傳算法的變異策略，克服蟻群算法早熟及遺傳算法局部最優(yōu)的特點(diǎn)，提高搜索效率，對改進(jìn)的蟻群算法在路徑規(guī)劃中的應(yīng)用進(jìn)行了仿真研究。

1 路徑規(guī)劃問題的描述

軍事應(yīng)用中路徑規(guī)劃的目的是使被規(guī)劃目標(biāo)能夠安全可靠及時地抵達(dá)目的地，并根據(jù)任務(wù)空間的不同屬性，在行進(jìn)機(jī)動過程中選擇性地執(zhí)行作戰(zhàn)任務(wù)。根據(jù)航行器功能和作戰(zhàn)地理環(huán)境的不同，路徑規(guī)劃可分為二維空間路徑規(guī)劃和三維空間路徑規(guī)劃。本文以潛艇航渡目標(biāo)海區(qū)為例進(jìn)行分析，著重研究二維空間內(nèi)的路徑優(yōu)化問題。

假設(shè)潛艇的航渡任務(wù)如圖1 所示，任務(wù)海區(qū)為S，潛艇由A 點(diǎn)出發(fā)機(jī)動到B 點(diǎn)執(zhí)行某項(xiàng)作戰(zhàn)任務(wù)，AB 兩點(diǎn)之間存在若干不同類型的礙航區(qū)域及敵方設(shè)定的防御威脅區(qū)域，則該種約束下，路徑規(guī)劃的主要任務(wù)就是根據(jù)某種優(yōu)化需求，為潛艇選擇一條滿足優(yōu)化指標(biāo)的可行路徑。

一般而言，潛艇的路徑規(guī)劃問題需要考慮多種平臺動力性能指標(biāo)，如航速、回旋半徑、航程限制、導(dǎo)航性能、通信能力等，同時也需要考慮海區(qū)水文環(huán)境、敵方威脅兵力配置、己方戰(zhàn)術(shù)需求等多種環(huán)境及戰(zhàn)術(shù)指標(biāo)需求或約束。但在實(shí)際的作戰(zhàn)過程中，根據(jù)特定的戰(zhàn)術(shù)需求及戰(zhàn)場態(tài)勢，路徑規(guī)劃通常采用的指標(biāo)為航路安全指標(biāo)和航行時間指標(biāo)，其中，前者表示目標(biāo)需要以一定的安全隱蔽性抵達(dá)指定區(qū)域，后者表示目標(biāo)需在限定的時間內(nèi)抵達(dá)指定區(qū)域［2］。

圖2 柵格化后的任務(wù)空間

柵格化后路徑規(guī)劃問題就可簡化為在MN下的搜索滿足相應(yīng)指標(biāo)的最優(yōu)路徑，可用式（1）表示為：

其中，E 為最優(yōu)路徑，f 為代價評估函數(shù)，Ek為所有的可由初始點(diǎn)行動至終止點(diǎn)的柵格序列。

2 改進(jìn)蟻群算法模型描述

本文為在不失作戰(zhàn)使用背景的前提下簡化問題，在模型構(gòu)建中采取如下的假定：

1）潛艇導(dǎo)航定位準(zhǔn)確，忽略導(dǎo)航定位問題引起的誤差；

2）在單位步長內(nèi)，潛艇機(jī)動變向不受約束，即潛艇可確保完成任意角度變向；

3）任務(wù)海區(qū)內(nèi)礙航物及敵方防御威脅兵力配置固定，位置不隨時間發(fā)生變化；

4）潛艇電量充沛，能量對航程不存在限制；

5）忽略海況對潛艇航行影響，即潛艇航行過程中受洋流等因素造成的航速變化及航向航跡偏移忽略不計(jì)。

2.1 任務(wù)空間柵格模型

為簡化說明，假設(shè)潛艇路徑規(guī)劃的任務(wù)海區(qū)為長為X，寬為Y 的矩形區(qū)域，則任務(wù)空間劃分為m×n 的柵格后，每個柵格MN表示的區(qū)域長度為X/n，寬度為Y/m。對所有柵格MN按列由上至下，由左至右順序編號后，則編號為N 柵格至多與8 個柵格接觸，如圖3 所示。其中，編號為N 的柵格在任務(wù)空間中對應(yīng)第xN行，第yN列的柵格MN，其中

圖3 柵格編號位置分布

顯然由圖3 可得，以柵格MN為當(dāng)前柵格，則下一可達(dá)柵格MN'必須滿足條件

2.2 路徑搜索算法模型

在柵格化后的任務(wù)空間中，假設(shè)初始點(diǎn)A 為蟻穴，路徑終點(diǎn)B 為食物源，則路徑規(guī)劃問題可類比為蟻群在任務(wù)空間中尋找食物源的過程［3］。經(jīng)過大量螞蟻群體反復(fù)搜尋，通過信息素的反饋?zhàn)饔?，最終選擇一條最優(yōu)路徑。根據(jù)蟻群算法一般流程，結(jié)合潛艇路徑優(yōu)化問題的分析，對算法中涉及的相關(guān)變量定義如下：

2.3 路徑選擇模型

2.3.1 路徑轉(zhuǎn)移模型

每個柵格的選擇概率由啟發(fā)信息和信息濃度確定。由于路徑規(guī)劃問題總是企圖使規(guī)劃目標(biāo)安全地向終點(diǎn)移動，因此，啟發(fā)信息可由當(dāng)前柵格與終點(diǎn)相對關(guān)系及安全性確定，本文中采取相對距離與柵格區(qū)域的威脅程度作為啟發(fā)因子ηN'

2.3.2 路徑回退模型

2.3.3 信息濃度更新模型

Therapeutic drug(Yupingfeng granules,Z10930036)and placebo(placebo granules)were manufactured by Guangdong HuanQiu Pharmaceutical Company(Guangdong,China).

2.3.4 路徑代價模型

其中，Pf為在路徑L 中的暴露概率，當(dāng)作戰(zhàn)任務(wù)對安全隱蔽性需求較大時，增大μ 以調(diào)節(jié)路徑代價指標(biāo)，反之當(dāng)作戰(zhàn)任務(wù)對時間敏感性較強(qiáng)時則需調(diào)低μ 取值。路徑L 的暴露概率表示為

2.4 基于遺傳算法的改進(jìn)策略

雖然在路徑轉(zhuǎn)移模型及信息濃度更新模型中均有涉及避免系統(tǒng)早熟及收斂過快的因素，但是由于蟻群算法在概率轉(zhuǎn)移及信息濃度反饋中存在的固有特點(diǎn)，仍有可能使得系統(tǒng)信息濃度過快累積，影響全局搜索能力。一種解決方案是增大并行展開的搜索數(shù)量，但這將較大增大系統(tǒng)的計(jì)算量，降低搜索效率，這在時間敏感性較強(qiáng)的軍事作戰(zhàn)系統(tǒng)中存在較大應(yīng)用限制［4］。

遺傳算法是模擬生物進(jìn)化過程的一種智能算法。該算法引入變異遺傳的概念，合適的變異及遺傳方式將使得系統(tǒng)能夠有效地避免早熟及收斂過快。但遺傳算法卻有著局部收斂性的弊端，為解決局部收斂性的問題，需要適當(dāng)增加變異概率及遺傳代數(shù)，而這也將不可避免地增加了系統(tǒng)的計(jì)算量［5-6］。

結(jié)合遺傳算法與蟻群算法二者在搜索算法方面不同的優(yōu)勢及特點(diǎn)，執(zhí)行以下的改進(jìn)策略。

2.4.1 轉(zhuǎn)移算法改進(jìn)策略

在2.3.1 節(jié)中，路徑轉(zhuǎn)移模型主要通過概率方式進(jìn)行柵格選擇，一旦信息濃度 N 積累過高，搜索過程將會極有可能極大概率繼續(xù)指向該柵格，進(jìn)而導(dǎo)致累積。以遺傳算法的變異性為基礎(chǔ)，設(shè)計(jì)改進(jìn)策略如下：

一旦柵格信息濃度超過一定閾值TH，則產(chǎn)生一個隨機(jī)數(shù)h，當(dāng)h 超過預(yù)置的參數(shù)h0時，柵格轉(zhuǎn)移過程將不以信息濃度概率為準(zhǔn)則，而將在可達(dá)柵格集Aj中隨機(jī)選擇一個柵格，該策略可表示為

其中，“&”表示“邏輯與”，“|”表示“邏輯或”。

2.4.2 交叉路徑改進(jìn)策略

2.5 算法流程

2）初始化路徑規(guī)劃初始點(diǎn)與終止點(diǎn)信息；

3）根據(jù)路徑轉(zhuǎn)移模型及回退模型開始選擇柵格，進(jìn)行路徑轉(zhuǎn)移；

4）判斷是否抵達(dá)終止點(diǎn)柵格，若是，執(zhí)行5），否則執(zhí)行3）；

5）根據(jù)途徑柵格，進(jìn)行交叉路徑處理，求解代價函數(shù)，更新信息濃度，更新最優(yōu)路徑；

6）判斷是否完成最大迭代次數(shù)，若達(dá)到，輸出最優(yōu)路徑及相關(guān)指標(biāo)信息，反之退至2）。

流程圖表示如下頁圖4 所示。

3 仿真結(jié)果分析

3.1 仿真設(shè)定及參數(shù)取值

如圖5 所示，經(jīng)柵格化處理后，水面艦由A 點(diǎn)出發(fā)機(jī)動至B 點(diǎn)，任務(wù)空間內(nèi)有島嶼、淺灘、暗礁等礙航物，存在3 組防御兵力，防御柵格范圍內(nèi)兵力防御能力相等，威脅概率P=0.3。

圖4 算法流程圖

圖5 仿真任務(wù)空間

結(jié)合文獻(xiàn)研究，本文仿真參數(shù)選取如下：

表1 仿真參數(shù)取值表

3.2 仿真結(jié)果分析

在表1 參數(shù)取值設(shè)定的條件下，經(jīng)過仿真迭代15 000 次，最終得到最優(yōu)路徑如圖5 所示，其中，實(shí)線表示路徑品質(zhì)取決于時間的最優(yōu)路徑，即μ=0時；虛線表示路徑品質(zhì)主要取決于安全隱蔽性時的最優(yōu)路徑，即μ=0.99 時。變異策略的采取和不采取，均取得相同路徑，這表明兩種算法的有效性。從圖6可以看出，當(dāng)μ=0 時，路徑忽略防御威脅，選取了最短距離的路徑；當(dāng)μ=0.99 時，路徑主要注重避免行經(jīng)的威脅防御柵格，選取了安全隱蔽意義上的最優(yōu)路徑，需要說明的是μ 取值不為1 的原因是在以安全隱蔽性為代價指標(biāo)的路徑方案中，存在多組代價相同的最優(yōu)路徑，通過μ 取值為0.99 的方法，使得式（10）中路徑距離代價占有極小的權(quán)重，以保證在安全隱蔽性最優(yōu)條件下的路徑距離最優(yōu)。兩條路徑從直觀上符合戰(zhàn)場態(tài)勢判斷，驗(yàn)證了算法的有效性和可行性。

圖6 最優(yōu)路徑圖

圖7 迭代速率對比圖

表2 最優(yōu)解更新迭代數(shù)

表2 和圖7 是在μ=0.99 時，算法優(yōu)化性能關(guān)系對比。由表2 可知，在設(shè)定條件下，經(jīng)過變異策略改進(jìn)的算法，得到最終航路所需迭代次數(shù)遠(yuǎn)低于未經(jīng)改進(jìn)的路徑求解算法。圖7 表示的是在迭代代數(shù)基本相同條件下，采取變異策略的算法與未采取變異策略的算法的路徑代價取值，可以看出，在迭代代數(shù)差異不大的情況下，采取了變異策略的算法后，收斂速度有較大提高，通過交叉機(jī)制和路徑轉(zhuǎn)移的變異機(jī)制，能有效降低算法搜索停滯和早熟現(xiàn)象。

4 結(jié)論

蟻群算法是基于自然界蟻群社會現(xiàn)象的一種智能搜索優(yōu)化方法，其信息反饋及并行能力使得該方法有極強(qiáng)的應(yīng)用潛力［7］。本文結(jié)合潛艇路徑優(yōu)化問題的作戰(zhàn)特點(diǎn)和戰(zhàn)術(shù)需求，提出了基于遺傳變異的改進(jìn)策略和改進(jìn)方法。仿真結(jié)果表明，改進(jìn)后的蟻群算法，優(yōu)化的收斂速度和收斂性有了一定改善，在兩種不同代價指標(biāo)的模型下，算法也取得了直觀上戰(zhàn)術(shù)效果較好的路徑。由于本文模型中假定敵方防御兵力是靜止不動的，這與實(shí)際作戰(zhàn)中的固定防御兵力是等效吻合的，對于移動防御兵力威脅下的路徑優(yōu)化問題，可將算法擴(kuò)展至由二維空間加上時間所構(gòu)成的三維時空中進(jìn)行求解。