蟻群算法的路徑規(guī)劃改進(jìn)策略

施建禮，劉志浩，潘 爽

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 柵格編號(hào)位置分布

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

2.2 路徑搜索算法模型

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

2.3 路徑選擇模型

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

每個(gè)柵格的選擇概率由啟發(fā)信息和信息濃度確定。由于路徑規(guī)劃問(wèn)題總是企圖使規(guī)劃目標(biāo)安全地向終點(diǎn)移動(dòng)，因此，啟發(fā)信息可由當(dāng)前柵格與終點(diǎn)相對(duì)關(guān)系及安全性確定，本文中采取相對(duì)距離與柵格區(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 路徑代價(jià)模型

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

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

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

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

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

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

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

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

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

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

2.5 算法流程

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

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

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

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

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

流程圖表示如下頁(yè)圖4 所示。

3 仿真結(jié)果分析

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

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

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

圖7 迭代速率對(duì)比圖

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

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

4 結(jié)論

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