蟻群算法的路徑規劃改進策略

施建禮，劉志浩，潘 爽

（海軍潛艇學院，山東 青島 266199）

0 引言

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

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

1 路徑規劃問題的描述

軍事應用中路徑規劃的目的是使被規劃目標能夠安全可靠及時地抵達目的地，并根據任務空間的不同屬性，在行進機動過程中選擇性地執行作戰任務。根據航行器功能和作戰地理環境的不同，路徑規劃可分為二維空間路徑規劃和三維空間路徑規劃。本文以潛艇航渡目標海區為例進行分析，著重研究二維空間內的路徑優化問題。

假設潛艇的航渡任務如圖1 所示，任務海區為S，潛艇由A 點出發機動到B 點執行某項作戰任務，AB 兩點之間存在若干不同類型的礙航區域及敵方設定的防御威脅區域，則該種約束下，路徑規劃的主要任務就是根據某種優化需求，為潛艇選擇一條滿足優化指標的可行路徑。

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

圖2 柵格化后的任務空間

柵格化后路徑規劃問題就可簡化為在MN下的搜索滿足相應指標的最優路徑，可用式（1）表示為：

其中，E 為最優路徑，f 為代價評估函數，Ek為所有的可由初始點行動至終止點的柵格序列。

2 改進蟻群算法模型描述

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

1）潛艇導航定位準確，忽略導航定位問題引起的誤差；

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

3）任務海區內礙航物及敵方防御威脅兵力配置固定，位置不隨時間發生變化；

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

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

2.1 任務空間柵格模型

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

圖3 柵格編號位置分布

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

2.2 路徑搜索算法模型

在柵格化后的任務空間中，假設初始點A 為蟻穴，路徑終點B 為食物源，則路徑規劃問題可類比為蟻群在任務空間中尋找食物源的過程［3］。經過大量螞蟻群體反復搜尋，通過信息素的反饋作用，最終選擇一條最優路徑。根據蟻群算法一般流程，結合潛艇路徑優化問題的分析，對算法中涉及的相關變量定義如下：

2.3 路徑選擇模型

2.3.1 路徑轉移模型

每個柵格的選擇概率由啟發信息和信息濃度確定。由于路徑規劃問題總是企圖使規劃目標安全地向終點移動，因此，啟發信息可由當前柵格與終點相對關系及安全性確定，本文中采取相對距離與柵格區域的威脅程度作為啟發因子η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 中的暴露概率，當作戰任務對安全隱蔽性需求較大時，增大μ 以調節路徑代價指標，反之當作戰任務對時間敏感性較強時則需調低μ 取值。路徑L 的暴露概率表示為

2.4 基于遺傳算法的改進策略

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

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

結合遺傳算法與蟻群算法二者在搜索算法方面不同的優勢及特點，執行以下的改進策略。

2.4.1 轉移算法改進策略

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

一旦柵格信息濃度超過一定閾值TH，則產生一個隨機數h，當h 超過預置的參數h0時，柵格轉移過程將不以信息濃度概率為準則，而將在可達柵格集Aj中隨機選擇一個柵格，該策略可表示為

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

2.4.2 交叉路徑改進策略

2.5 算法流程

2）初始化路徑規劃初始點與終止點信息；

3）根據路徑轉移模型及回退模型開始選擇柵格，進行路徑轉移；

4）判斷是否抵達終止點柵格，若是，執行5），否則執行3）；

5）根據途徑柵格，進行交叉路徑處理，求解代價函數，更新信息濃度，更新最優路徑；

6）判斷是否完成最大迭代次數，若達到，輸出最優路徑及相關指標信息，反之退至2）。

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

3 仿真結果分析

3.1 仿真設定及參數取值

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

圖4 算法流程圖

圖5 仿真任務空間

結合文獻研究，本文仿真參數選取如下：

表1 仿真參數取值表

3.2 仿真結果分析

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

圖6 最優路徑圖

圖7 迭代速率對比圖

表2 最優解更新迭代數

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

4 結論

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