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

張鴻強 曾 斌 羅春華

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

1 引言

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

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

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

2 不確定性分析

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

2.1 限定時間的概率求解

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

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

2.2 給定概率的時間求解

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

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

3 算法求解

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

3.1 種群初始化

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

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

3.2 染色體交叉

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

圖1 染色體交叉

3.3 染色體變異

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

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

3.4 染色體選擇

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

3.5 模擬退火法解最短機動路線

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

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

3.6 遺傳算法改進

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

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

3.7 算法流程

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

圖2 流程圖

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

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

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

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

4 仿真驗證

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

4.1 參數(shù)設置

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

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

4.2 結(jié)果分析

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

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

圖4 算法改進前

圖5 算法改進后

5 結(jié)語

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

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

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

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