基于演化算法的魯棒性AUV分配方法研究?

張鴻強(qiáng) 曾 斌 羅春華

（1.海軍工程大學(xué)管理工程與裝備經(jīng)濟(jì)系 武漢 430030）（2.海軍工程大學(xué)教學(xué)保障中心 武漢 430030）

1 引言

當(dāng)前，我國(guó)面臨的安全威脅主要來自海上。美軍為了搜聽情報(bào)，監(jiān)視我方艦艇的活動(dòng)，在關(guān)鍵的航道或水域布設(shè)聲吶探測(cè)器，其中比較著名的就是以SOSUS為代表的水下警戒系統(tǒng)，具備主、被動(dòng)聲吶探測(cè)手段，能夠探測(cè)到幾十千米外的水中目標(biāo)，進(jìn)而識(shí)別和定位［1］。這些固定式水聲系統(tǒng)與美軍反潛飛機(jī)、攻擊型核潛艇和水面艦艇一道，能對(duì)各主要海峽通道進(jìn)行實(shí)時(shí)監(jiān)控，封堵我方潛艇兵力的水下航路。隨著科學(xué)技術(shù)的發(fā)展，利用自主式水下航行器（AUV）搜索、發(fā)現(xiàn)并拔出這些“釘子”成為可能，也變得緊迫且必要。

水下搜索任務(wù)日益增多，復(fù)雜度不斷提高，如何在限定的時(shí)間內(nèi)達(dá)成目標(biāo)，科學(xué)合理高效地分配有限的AUV搜索資源是關(guān)鍵。這些AUV的速度、續(xù)航能力、搜索效率和環(huán)境適應(yīng)度各不相同，需要合理搭配并規(guī)劃好路線才能高效完成搜索任務(wù)［2］。文獻(xiàn)［3］介紹的基于Dubins曲線及遺傳算法的AUV路徑規(guī)劃方法針對(duì)的是單個(gè)AUV的運(yùn)動(dòng)，解決路徑轉(zhuǎn)角大不平滑的問題。文獻(xiàn)［4］提供的基于振蕩型IWO算法的AUV路徑規(guī)劃方法，是在考慮障礙物、敵情和自身任務(wù)情況下，尋找AUV運(yùn)動(dòng)的較短路徑。文獻(xiàn)［5］提到的基于D-S證據(jù)論的多AUV協(xié)同搜索決策方法，通過引入各AUV之間“競(jìng)爭(zhēng)力”的概念，來避免重復(fù)搜索減少任務(wù)時(shí)間。這些方法研究重點(diǎn)是單個(gè)AUV的優(yōu)化路徑，沒有從整體考慮不同AUV的任務(wù)分配及路徑規(guī)劃問題［6］。同時(shí)，沒有充分考慮環(huán)境中的不確定因素，如洋流、天氣、水溫等對(duì)搜索任務(wù)的影響［7］。

針對(duì)上面存在的問題，本文采用改進(jìn)模擬退火及遺傳算法的魯棒AUV搜索分配方法。首先，在分析搜索問題時(shí)引入魯棒性的概念，來應(yīng)對(duì)環(huán)境的不確定性，使問題更貼合實(shí)際。其次從整體出發(fā)，將任務(wù)區(qū)域劃分成若干子區(qū)域，利用遺傳算法給各AUV分配合適的任務(wù)量，然后用模擬退火算法參考多旅行商問題［8］進(jìn)行最短路徑的規(guī)劃。

2 不確定性分析

魯棒性是指系統(tǒng)受到某些因素干擾時(shí)仍能維持自身穩(wěn)定的特征。AUV在進(jìn)行水下搜索時(shí)，會(huì)受到很多不確定因素的影響，包括水下復(fù)雜地形、天氣、敵情以及機(jī)械故障等。當(dāng)這些不確定因素結(jié)合在一起時(shí)，很難找到精確最優(yōu)解。因此，本文提出針對(duì)水下搜索問題的近似最優(yōu)的資源分配方式，來解決這些不確定性問題。在計(jì)劃進(jìn)行水下搜索時(shí)，軍事參謀人員必須針對(duì)任務(wù)進(jìn)行資源分配，估算完成任務(wù)的時(shí)間，為突發(fā)事件做好預(yù)案?？紤]到戰(zhàn)場(chǎng)的不可預(yù)測(cè)性及任務(wù)的時(shí)限性，這是一項(xiàng)繁瑣艱巨的任務(wù)［9］。本文用隨機(jī)魯棒性指標(biāo)來描述搜索任務(wù)完成情況，該指標(biāo)有兩種表示方法，一是在限定時(shí)間內(nèi)完成搜索任務(wù)的概率，二是在指定概率（如90%）下完成搜索任務(wù)的時(shí)間［10］。

2.1 限定時(shí)間的概率求解

首先對(duì)第一種魯棒性指標(biāo)進(jìn)行研究，分析在限定的時(shí)間內(nèi)完成搜索任務(wù)的概率。本文將任務(wù)完成時(shí)限記為DT，第一種魯棒性指標(biāo)即表示在DT內(nèi)完成搜索任務(wù)的概率。水下搜索模型包含用概率質(zhì)量函數(shù)pmf描述的擾動(dòng)，本文考慮的擾動(dòng)因素包括第i型AUV搜索效率 μi，以及移動(dòng)速率 λi等，這些值可作為影響搜索時(shí)間函數(shù)的輸入變量。水溫、洋流和密度等因素對(duì)搜索時(shí)間的影響可以體現(xiàn)在μi和λi等數(shù)值的變化上。本文將RM定義為所有搜索資源在DT內(nèi)完成搜索其目標(biāo)集的概率，可表示為

對(duì)于AUV執(zhí)行目標(biāo)區(qū)域搜索任務(wù)問題，存在多種搜索資源分配方案，利用第一種魯棒性評(píng)價(jià)指標(biāo)，通過比較各種方案的RM值大小，就能確定魯棒性較好的方案。

2.2 給定概率的時(shí)間求解

第二種魯棒性指標(biāo)是在給定概率前提下，求出完成搜索任務(wù)的時(shí)間。假定在當(dāng)前環(huán)境條件下，某3個(gè)型號(hào)AUV正常工作達(dá)成目標(biāo)的概率為90%。在此概率前提下，任務(wù)時(shí)間T可表示為機(jī)動(dòng)時(shí)間與搜索時(shí)間之和。假定以柵格左下角頂點(diǎn)為坐標(biāo)原點(diǎn)，水平方向和垂直方向分別構(gòu)建兩個(gè)坐標(biāo)軸，以每個(gè)方格的中心點(diǎn)坐標(biāo)表示所代表區(qū)域的位置，機(jī)動(dòng)距離即為兩個(gè)中心點(diǎn)之間的距離。搜索這兩個(gè)柵格的時(shí)間就等于移動(dòng)距離與航行器移動(dòng)速度之比加上柵格面積與搜索效率之比。

每個(gè)AUV負(fù)責(zé)搜索的柵格區(qū)域不重復(fù)，搜索不同位置以及不同數(shù)量的區(qū)域所需要的時(shí)間也不同，最后一個(gè)完成任務(wù)的AUV的時(shí)間就是整個(gè)目標(biāo)區(qū)域的搜索時(shí)間。為了從若干的分配方案中找出搜索時(shí)間最短的，可以考慮采用遺傳算法，模擬自然選擇過程進(jìn)行啟發(fā)式尋優(yōu)。

3 算法求解

遺傳算法借鑒了生物進(jìn)化的規(guī)律方法，通過交叉、選擇和變異等操作，產(chǎn)生新的更優(yōu)的個(gè)體［11］。其操作簡(jiǎn)便，算法易于理解，但也存在容易陷入局部最優(yōu)的問題，需要通過操作方法的改進(jìn)，以及輸入?yún)?shù)的調(diào)整，來達(dá)到較好的效果。

3.1 種群初始化

種群的每個(gè)染色體代表一種解，本文要設(shè)計(jì)染色體的編碼方式，使得所有的區(qū)域都能被搜索到。由于AUV和目標(biāo)子區(qū)域構(gòu)成對(duì)應(yīng)關(guān)系，此處采用2行n列二維數(shù)組的編碼方式［12］。如式（1）所示。

式（1）中n為待搜索子區(qū)域的數(shù)量，x的取值為1，2，3，y的取值為［1，n］。數(shù)組一一對(duì)應(yīng)，表示Ⅰ型AUV被派往搜索區(qū)域A1，Ⅱ型AUV被分配到待搜索區(qū)域A2；Ⅲ型AUV被分配到待搜索區(qū)域Ah。染色體的長(zhǎng)度由待搜索區(qū)域大小和劃分的搜索子區(qū)域的數(shù)量決定。為了更科學(xué)地劃分區(qū)域，本文引入搜索同步線和分界線。搜索同步線控制AUV之間的協(xié)同，當(dāng)搜索快的AUV到達(dá)同步線后，需要停下等待其他AUV全部到達(dá)后再搜索下一區(qū)域，以免搜索目標(biāo)利用各AUV之間的時(shí)間差實(shí)施規(guī)避。考慮到復(fù)雜地形的限制以及任務(wù)劃分，利用搜索分界線控制不同分組的AUV不越線搜索，其與同步線是交叉的。二者所分區(qū)域數(shù)量的乘積決定了染色體鏈的數(shù)量。當(dāng)搜索同步線和分界線數(shù)量為1時(shí)，整個(gè)搜索區(qū)域被分成四塊，每塊區(qū)域都會(huì)形成一條染色體鏈，最后組成一條染色體。

3.2 染色體交叉

為了使種群中的個(gè)體多樣化，采用基于位置的交叉操作。根據(jù)該問題中染色體的特點(diǎn)，交叉應(yīng)在相對(duì)應(yīng)的染色體鏈上進(jìn)行，否則得到的就是非法染色體。此處對(duì)傳統(tǒng)的染色體交叉方法進(jìn)行改進(jìn)，使得親本染色體特性能既有部分保留，同時(shí)能夠產(chǎn)生足夠變化。交叉操作在親本染色體A和B的鏈上進(jìn)行，基本方法（如圖1）首先選擇要進(jìn)行交叉操作的鏈，此處選擇鏈2。然后在該鏈上隨機(jī)選擇一個(gè)交叉點(diǎn)，圖中選的是第三和第四之間的點(diǎn)，親本染色體鏈中該點(diǎn)左側(cè)部分進(jìn)行保留，再將右側(cè)部分去除現(xiàn)有基因后交叉依次填入子代染色體鏈中，那么根據(jù)規(guī)則，即可得到新的子代染色體鏈。

圖1 染色體交叉

3.3 染色體變異

獲得新的子代染色體的方式還有變異，其方法是隨機(jī)選擇父代染色體的基因位置，然后將染色體編碼串中選定的基因座上的基因值用給定邊界區(qū)域內(nèi)運(yùn)行的搜索資源集合中一個(gè)隨機(jī)選擇的新搜索資源等位基因來替換形成新的個(gè)體。引入變異算子能讓種群的多樣性增加，這時(shí)遺傳算法具有局部搜索尋優(yōu)能力。在進(jìn)化過程開始時(shí)，p選取較大的值，隨著搜索過程的進(jìn)行，p逐漸縮小到0附近。當(dāng)變異概率選擇較大時(shí)，搜索能力會(huì)增加但搜素速率會(huì)變慢，而概率選擇較小時(shí)，搜索速率變快，但容易陷入局部最優(yōu)。所以這里選擇動(dòng)態(tài)的概率值：

其中，式（2）中fmax為種群適應(yīng)度的最大值，fave為種群適應(yīng)度的平均值，其中h1、h2的取值為（0，1）。

3.4 染色體選擇

在已知適應(yīng)度函數(shù)求解方法的基礎(chǔ)上，傳統(tǒng)方法一般采用輪盤賭選擇法來進(jìn)行操作。該方法根據(jù)每個(gè)個(gè)體的適應(yīng)度值來計(jì)算其在子代中出現(xiàn)的概率，并以此為依據(jù)選擇子代染色體［13］，這樣選擇容易使問題陷入局部最優(yōu)解。本文對(duì)常規(guī)方法進(jìn)行改進(jìn)，引入排序選擇的方法。具體操作是將種群個(gè)體的適應(yīng)度值按大小進(jìn)行排列，相應(yīng)地產(chǎn)生一個(gè)概率分配向量：C=（c1，c2，…，cn），將概率分配向量具體對(duì)應(yīng)的值分配給個(gè)體，這個(gè)值就是個(gè)體能被遺傳到下一代的概率。很明顯計(jì)算出的適應(yīng)度值越大，其相對(duì)應(yīng)的選擇概率也就越大，被選中進(jìn)入子代染色體的次數(shù)也更多。

3.5 模擬退火法解最短機(jī)動(dòng)路線

某型AUV從起點(diǎn)開始搜索分配給它的n個(gè)區(qū)域，求最后回到起點(diǎn)的最短路徑。首先設(shè)置一個(gè)初始溫度，隨機(jī)初始化一組解，進(jìn)入循環(huán)，在各區(qū)域訪問排列中，以一定的規(guī)則進(jìn)行隨機(jī)擾動(dòng)，產(chǎn)生新的解。判斷是否達(dá)到溫度閥值，根據(jù)規(guī)則是否接受這個(gè)解，若未達(dá)標(biāo)繼續(xù)進(jìn)行外循環(huán)［14］。為了防止“早熟”現(xiàn)象，對(duì)模擬退火進(jìn)行改進(jìn)，加入自適應(yīng)的升溫控制因子，在出現(xiàn)過早收斂時(shí)，增高溫度，加強(qiáng)擾動(dòng)隨機(jī)性。

式（4）中，M為降溫次數(shù)，l為升溫次數(shù)，K1為控制升溫的參數(shù)因子，能控制全局尋優(yōu)能力。式（5）中β是升溫系數(shù)，Tnew為自適應(yīng)擾動(dòng)控制因子的參數(shù)，其值越大時(shí)，擾動(dòng)增加幅度也會(huì)變大。

3.6 遺傳算法改進(jìn)

按照采取的編碼方式，每條染色體代表一種分配方式，每種分配方式明確了各型AUV搜索的子區(qū)域，而且已知每個(gè)區(qū)域中心點(diǎn)的坐標(biāo)，那么就可以規(guī)劃出最短路徑。通過最短路徑與AUV移動(dòng)速度的比值就可以求出機(jī)動(dòng)時(shí)間，加上搜索每個(gè)子區(qū)域的時(shí)間，得出該型AUV搜索總時(shí)間。三種型號(hào)的AUV用時(shí)最長(zhǎng)的即為完成任務(wù)的時(shí)間，將這個(gè)時(shí)間作為遺傳算法的適應(yīng)度值。

當(dāng)經(jīng)過交叉操作得到的A鏈已經(jīng)是最佳最佳染色體鏈時(shí)，常規(guī)做法還要進(jìn)行變異操作，得到新的染色體鏈。這樣將會(huì)錯(cuò)過最佳方案，影響算法的收斂速度，以及出現(xiàn)早熟的情況。為了提高算法效率，對(duì)常規(guī)算法進(jìn)行改進(jìn)，加入限制條件，每次進(jìn)行交叉和變異操作后，都進(jìn)行適應(yīng)度計(jì)算，如果適應(yīng)度值變大，則交叉變異操作無效，反之，更新結(jié)果。

3.7 算法流程

綜上，整體算法的流程表示如圖2。

圖2 流程圖

步驟1：初始化種群。將待搜索的子區(qū)域按隨機(jī)對(duì)應(yīng)的關(guān)系分配給AUV，形成初始種群。

步驟2：利用模擬退火方法，找出AUV搜索若干個(gè)子區(qū)域的最優(yōu)路徑，并將結(jié)果作為適應(yīng)度函數(shù)的解。

步驟3：進(jìn)行染色體交叉和變異操作。從初始種群中選擇親本染色體進(jìn)行交叉和變異操作得到子染色體，同時(shí)，計(jì)算出子染色體的適應(yīng)度值，并與親本染色體進(jìn)行比較，判斷應(yīng)保留或者更新［15］。

步驟4：重復(fù)步驟2，得到新的適應(yīng)度值，利用改進(jìn)選擇方法進(jìn)行染色體優(yōu)選。當(dāng)滿足終止條件時(shí)，得到適應(yīng)度最小的染色體，輸出其對(duì)應(yīng)的分配方案，即各AUV應(yīng)搜索的區(qū)域和路徑。

4 仿真驗(yàn)證

仿真平臺(tái)為 Intel? Core（TM）i7 CPU 4GB 內(nèi)存，64位Win7操作系統(tǒng)的聯(lián)想筆記本。編程工具為Matlab R2019b（64位）。

4.1 參數(shù)設(shè)置

現(xiàn)有一待搜索區(qū)域，將其劃分為10*10柵格，假設(shè)搜索同步線和分界線數(shù)量為1，則柵格被分為四個(gè)區(qū)域，其中一區(qū)域參數(shù)如表1。共有3型AUV協(xié)同搜索，進(jìn)行仿真演示。

表1 搜索區(qū)域參數(shù)

4.2 結(jié)果分析

通過仿真，得到Ⅰ、Ⅱ、Ⅲ型AUV搜索路徑，圖3即為Ⅰ型AUV搜索路徑示意，其他兩型AUV路徑此處省略。從結(jié)果分析，該改進(jìn)算法能夠?qū)崿F(xiàn)不同型號(hào)AUV任務(wù)分配，并得出最優(yōu)搜索路徑。圖4和圖5對(duì)比表明，算法改進(jìn)前最優(yōu)路徑距離長(zhǎng)度為1118m，改進(jìn)后的最優(yōu)路徑長(zhǎng)度為1089m，縮短了2.6%。同時(shí)，改進(jìn)之后的算法其收斂速度更快，魯棒性更好，尋找最優(yōu)解的精度更高，更能適應(yīng)復(fù)雜且計(jì)算量大的情況。

圖3 Ⅰ型AUV軌跡規(guī)劃結(jié)果

圖4 算法改進(jìn)前

圖5 算法改進(jìn)后

5 結(jié)語

為了解決多型AUV水下搜索任務(wù)分配問題，將任務(wù)區(qū)域進(jìn)行劃分，并對(duì)每種型號(hào)AUV航跡進(jìn)行規(guī)劃，通過仿真驗(yàn)證改進(jìn)遺傳算法和模擬退火的可行性，觀察其收斂效果。得出結(jié)論：

1）本文提出的基于改進(jìn)遺傳算法和模擬退火算法的多AUV資源分配方法，能夠有效地對(duì)任務(wù)區(qū)域進(jìn)行分配并規(guī)劃出各型AUV的最優(yōu)路徑，且算法的精度和收斂性有保證。

2）改進(jìn)的適應(yīng)度更新策略能夠較好地提升算法的全局尋優(yōu)能力和收斂速度，克服了容易陷入局部最優(yōu)的不足。

3）通過該方法，提高了搜索任務(wù)分配的科學(xué)性，能夠提供科學(xué)的搜索輔助決策。