基于改進的復合自適應遺傳算法的UUV水下回收路徑規(guī)劃

趙鵬程，宋保維，毛昭勇，丁文俊

(1.西北工業(yè)大學 航海學院，陜西 西安 710072；2.西北工業(yè)大學 無人水下運載技術工信部重點實驗室，陜西 西安 710072；3.西北工業(yè)大學 無人系統技術研究院，陜西 西安 710072)

0 引言

海洋占據著地球70%以上的面積，隨著當前科技的發(fā)展，社會勘探開發(fā)海洋資源的需求越發(fā)迫切。無人水下航行器(UUV)一般攜帶能源在水下執(zhí)行任務，完成任務后再通過回收完成能源補充以及其他操作。UUV的回收方式[1-2]分為水面回收方式和水下回收方式，水下回收中的平臺式水下回收方式續(xù)航時間較長、隱蔽性強，因此成為國內外UUV回收研究熱點。

靜態(tài)路徑規(guī)劃是水域中UUV回收工作的重要組成部分。UUV的靜態(tài)路徑規(guī)劃是在水域環(huán)境及障礙物已知的情況下，航行器服從一定的約束條件和性能指標求解出無碰撞的最優(yōu)路徑。相比于一般機器人的路徑規(guī)劃，UUV在水下工作環(huán)境的運動約束條件更高。水下流體阻力大，UUV機動轉向時會受自身最小回轉半徑的機動性限制，因此進行UUV的水下回收路徑規(guī)劃時，還要考慮UUV的機動約束條件。

目前關于路徑搜索優(yōu)化的算法研究有許多，例如A*算法[3]、粒子群優(yōu)化算法[4]和遺傳算法[5]等，還有一些相應的改進和結合算法[6-9]。其中遺傳算法具有良好的靜態(tài)搜索能力和進化能力，在處理靜態(tài)路徑規(guī)劃問題上表現突出。但是遺傳算法求解時易發(fā)生早熟，即在算法早期出現性能優(yōu)良的局部最優(yōu)解，局部最優(yōu)解使種群多樣性迅速降低，算法難以跳出局部最優(yōu)解擴大有效搜索范圍，群體進化能力基本喪失，最終使算法較早收斂于局部最優(yōu)解。

對于遺傳算法路徑規(guī)劃的早熟問題，許多學者都提出了一些比較成熟的改進。有學者從算法結合的方向進行改進：孫波等[10]提出了一種結合模擬退火思想進行選擇操作的改進自適應遺傳算法，有效增強了遺傳算法跳出局部最優(yōu)解的能力；宋宇等[11]提出的改進遺傳算法，結合快速擴展隨機樹(RRT)算法進行種群初始化，結合A*算法設計一種新的插入算子，提高了遺傳算法的收斂速度和尋優(yōu)能力。也有學者通過改進遺傳算法的算子提高算法的性能：劉志海等[12]提出了一種遺傳算法的種群初始化改進方法，使生成的初始種群路徑均為可行路徑，有效提高解的質量和進化速度；針對遺傳算法的早熟收斂和隨機變異導致不可行路徑的問題；閆雪超等[13]提出一種新的路徑規(guī)劃變異算子，保證隨機突變產生可行路徑，明顯提高了算法的全局收斂性，避免過早收斂。

盡管上述創(chuàng)新在遺傳算法的性能改進方面取得了不錯的進展，但仍然存在以下問題尚未解決：上述改進采用遺傳算法求解路徑時仍通過柵格法進行環(huán)境建模，而柵格法占用資源較多，且對路徑質量有明顯影響。構建的柵格過大，求解所得路徑與最優(yōu)路徑偏差較大，柵格過小時又存在UUV的機動性不能實現所得最優(yōu)路徑的問題。上述改進都從遺傳算法的算子著手進行自適應改進，沒有考慮在障礙物較多的環(huán)境下，遺傳算法自適應改進后仍有較高幾率陷入局部最優(yōu)的問題。

考慮到上述問題，結合UUV自身的運動特性，本文設計一種改進的自適應遺傳算法，首先對水域進行二維定深平面上的障礙物建模，分析UUV的機動性對路徑規(guī)劃的影響表現，在遺傳算法中提出機動性約束條件，減少算法占用資源，同時使路徑更具有實用性；針對遺傳算法易陷入局部最優(yōu)的問題，提出了自適應的變異策略，在變異操作中引入方向控制項、基因位控制項和遺傳代數控制項，有效地增加了算法的全局尋優(yōu)能力；此外，為避免障礙物多的環(huán)境下自適應遺傳算法陷入早熟，本文針對性地提出雙階段自適應變異方法，解決了自適應遺傳算法中種群當前最優(yōu)路徑位于障礙物附近導致的種群進化停滯、難以找到更優(yōu)個體的問題，不僅能刺激種群繼續(xù)進化，而且可以引導最優(yōu)個體向全局最優(yōu)解的方向進化。仿真結果表明，改進的遺傳算法在搜索能力和收斂性方面都有明顯提升。

1 障礙物環(huán)境的建模

本文中UUV回收所在的水域環(huán)境建立為二維坐標系下的靜態(tài)環(huán)境模型，設UUV在水下一固定深度的平面上運動，水域中障礙物信息已知，障礙物的尺寸取障礙物在定深平面上的橫截面形狀尺寸，設置的水域環(huán)境要求盡可能包含UUV起始位置、終點位置及以始末點連線作圓包含到的障礙物全貌。以水域左下角為坐標系原點，水平向右為x軸正方向，垂直向上為y軸正方向。

環(huán)境中的障礙物橫截面一般可用多邊形簡單表示外形特性，考慮到UUV航行過程中的安全性問題，且多邊形障礙物環(huán)境會顯著提高路徑規(guī)劃的復雜度[14]，因此本文對全局環(huán)境已知的水域中的固定障礙物作圓化處理，即使用多邊形障礙物的外接圓代替障礙物。UUV自身具有一定尺寸，為確保航行中UUV不會與障礙物出現碰撞現象，需要對障礙物圓再進行一次膨化處理，在障礙物已有的尺寸上加上一個安全閾值dsec。安全閾值dsec的寬度與UUV的直徑尺寸有關，一般取UUV直徑尺寸的倍數，障礙物的擴大方法如圖1所示。

2 機動性約束條件

UUV的機動性[15]是指UUV改變航行狀態(tài)的能力，即航行器操舵后改變其航向、深度的能力，主要體現為兩項性能：最大法向過載和最小回轉半徑，其中最小回轉半徑是UUV在定深平面上能轉過的最小圓的半徑，通常這一參數用來衡量UUV的回轉性優(yōu)劣。本文研究內容為二維定深平面上的路徑規(guī)劃，因此只對UUV最小回轉半徑進行航向角和路徑長度兩方面的約束條件分析。

假設UUV在一段時間內都沿某一方向作直線運動，這一過程稱為UUV回收過程中的一個路徑階段，第i個路徑階段的路徑長度(簡稱路長)為li?；赨UV的最小回轉半徑約束，提出UUV每一路徑階段的路長約束，設置每一路徑階段路長基因的上下限約束為li∈[lmin，lmax]。

設UUV回收的始末位置間直線距離為dsum，單一路徑階段的路長基準d具體設置值如(1)式所示：

(1)

式中：n為UUV回收過程中自由路徑階段的總個數。lmin、lmax的大小是d的倍數，由于本文提出的回收路徑由自由路徑階段和唯一給定路徑階段組成，一般情況下lmin取0.7d～0.9d，lmax關于d的具體倍數取值與環(huán)境復雜度有關。

基于UUV的最小回轉半徑考慮，在路長約束的條件下再提出航向角約束。設置單一階段航向角基因上下限，其中第i個路徑階段的航向角θi應在第i-1階段航向角θi-1左右轉向上限α的范圍內，即航向角增值Δθ∈[-α，α]。

α的具體取值與最小回轉半徑R和路長約束中的下限lmin相關。如圖2所示，圖中的正多邊形是半徑為R的最小回轉圓的外切正多邊形，正多邊形的邊長為lmin。

(2)式是正多邊形的邊長與內切圓半徑R的關系，由此推導得正多邊形的邊數m，當m有小數部分時向上取整。

(2)

需要注意的是，當lmin明顯大于最小回轉半徑R時，求解出的α會超過π/2 rad，這與UUV航行的實際情況不符，應對該情況下的航向角進行修正，由此得到航向角增值上限α的修正計算公式為

(3)

3 環(huán)境復雜度

環(huán)境復雜度是對障礙物環(huán)境模型復雜程度的評估，在路徑規(guī)劃中需要參考其結果進行規(guī)劃算法的參數設置。本文以障礙物占域比作為衡量環(huán)境復雜度的主要參考量。因為用于評估的是二維環(huán)境模型，計算采用的障礙物是指經過兩次膨化處理的障礙物圓。

障礙物占域比是指UUV工作水域中障礙物的面積占水域面積的近似比。為便于計算，同時為獲得合適的近似估算結果，本文提出障礙物等效數目的概念用來估算障礙物占域比。

障礙物等效數目的計算方法為：障礙物在水域內面積超過自身面積50%時，該障礙物等效數目記為1；水域內面積超過自身面積25%但不足50%時，記為0.5；不足25%記為0。

障礙物占域比根據水域中每個障礙物自身的障礙物等效數目進行計算，計算式為

(4)

式中：La、Lw分別為選定水域的長和寬；p為所選水域中存在的障礙物實際數目；rx為第x個障礙物的半徑值；numx為第x個障礙物的等效數目值，numx∈[0,1]。

障礙物占域比Pob的數值大小會主導每一路徑階段路長上限lmax的取值，這是因為通常情況下，環(huán)境中障礙物數量越多，障礙物占域比越高，相應生成的路徑會越復雜，總路長也會增加，因此分配到每個路徑階段的路長上限lmax也應該相應地提高。

經計算得到Pob與lmax的取值關系如下：

(5)

本文以障礙物占域比作為環(huán)境復雜度主要參考量，在下一步研究中，可以用水域中障礙物數目和障礙物占域比兩方面綜合評估環(huán)境復雜度，并研究綜合評估結果和路徑規(guī)劃算法之間的關系。

4 改進遺傳算法的主要步驟

4.1 遺傳算法原理

20世紀70年代Holland[16]提出了遺傳算法，該算法的核心思想是模擬自然界種群繁衍、個體遺傳信息交叉及變異的進化。用遺傳算法求解時，問題可能的解集稱為種群，種群中的一個解被稱為一個個體(又稱染色體)。

傳統遺傳算法一般有以下步驟：編碼、初始種群生成、適應度函數評估、選擇、交叉、變異、解碼，重復直至滿足終止條件[16]，如圖3所示。

4.2 單鏈編碼

UUV的回收路徑由若干個路徑階段相連組成，一條回收路徑視為一個個體。改進的遺傳算法采用單鏈實數編碼：每一個體由組成個體的單一路徑階段所給定，單一路徑階段由兩個基因信息確定：航向角和路長。

由于UUV水下回收通常需要與平臺進行對接，對UUV的路徑末端姿態(tài)提出了要求。但本文假設平臺回收裝置位于平臺頭部，如果對UUV從起始點到平臺頭部附近位置的整體路徑進行規(guī)劃，則需要考慮末端UUV姿態(tài)約束、UUV在平臺附近處的路徑安全性等眾多約束條件，約束過于復雜且互相影響，會使遺傳算法難以發(fā)揮自身優(yōu)勢，甚至可能陷入局部最優(yōu)陷阱。因此將UUV的整體回收路徑拆分為兩段進行規(guī)劃：一段是UUV從初始位置到平臺尾部附近位置；二段是UUV從平臺尾部附近到指定的對接回收位置。本文主要研究UUV從初始位置到平臺尾部附近位置的回收路徑路徑規(guī)劃問題，該段的末位置不設置UUV姿態(tài)約束。

設n為自由回收路徑階段總數，始末兩位置點已給定的回收路徑的階段總數為n+1，其中路長和航向角均未確定的自由路徑階段是n個，連接末位置的最后的一路徑階段航向角和路長已被前面n個階段所給定。因此，一條回收路徑的染色體應為[n個航向角基因，n個路長基因]。

種群和個體分別表示如下：

(6)

(7)

4.3 種群初始化

初始種群的優(yōu)劣對遺傳算法最終解的性能有一定的影響。在UUV起始位置允許轉向的航向角范圍內，等角間距生成直線路徑組成初始直線種群；種群中每一個體隨機選擇組成個體的某些路徑階段發(fā)生航向角轉向，盡可能完成對整個水域空間的搜索，從而加快尋找最優(yōu)路徑的效率。

4.4 適應度函數

適應度函數[17]是評估種群中每一個體對環(huán)境適應情況的唯一標準，是評價路徑好壞的核心準則，其實質等效于目標函數。考慮到UUV的安全性、路徑的可行性和盡早回收的要求，適應度函數包括以下3個部分：回收路徑的總長度、路徑碰撞障礙的次數、第n+1個路徑階段的航向角是否符合約束。用適應度函數評估種群中個體的優(yōu)劣，適應度函數FCDP見(8)式。(8)式的值越小，路徑個體表現越好。

(8)

式中：pel為UUV航行全程的碰撞次數，對每一路徑階段的終點進行該階段的碰撞判斷，第n+1路徑階段的碰撞判斷是從該階段起點開始以路長基準d為間距依次選擇監(jiān)測點；C1、C2為懲罰系數，與選取的水域尺寸和環(huán)境復雜度相關；delθ用于判定第i+1個路徑階段航向角是否偏離約束范圍。設第i+1階段相對于第i階段轉向Δθ角，航向角的過約束懲罰判定如下：

(9)

當個體的路徑階段具有違規(guī)行為(碰撞或航向角超出約束)時，個體的適應度值會隨進化代數的增加而不斷增加，這使算法在進化過程中有效地篩查出違規(guī)個體并在進化前期進行淘汰。

4.5 選擇、交叉和變異操作

選擇操作在得到種群適應度后，根據個體適應度值選擇優(yōu)良的個體進行保留，一般采用輪盤賭法進行操作[18]。但由于輪盤賭法的隨機性會引入較大的選擇誤差，不利于保留種群適應度小的個體，改進的遺傳算法使用該方法選擇用于交叉的個體，把適應度相對好的個體直接從父代傳遞至子代，以此保留每一代的優(yōu)良個體。

在改進遺傳算法中，按某一較小比例保留父代優(yōu)良個體至子代后，在余下的父代個體中按給定的交叉?zhèn)€體比例(又稱交叉概率)挑出交叉?zhèn)€體，最后剩余的是按變異個體比例篩選留下的用于執(zhí)行變異的個體。子代種群由父代優(yōu)良個體組、交叉組和變異組共同組成。

交叉操作是兩個選定染色體互換一部分基因信息，由此生成兩個新的路徑解，擴大種群的搜索區(qū)域。該操作可以采用單點交叉、兩點交叉或多點交叉等方式[19]。本文算法采用兩點交叉的方式對選定的路徑階段同時進行航向角和路長的交叉，交叉點的選取范圍分別為染色體長度的1/2n～(n-1)/2n及相應(n+1)/2n～(2n-1)/2n處。

變異操作是個體中的某一段染色體發(fā)生了突變，突變后個體成為一個全新的個體[20]。通過變異操作可以二次搜索前代種群未搜索的區(qū)域，保證個體多樣性和全局最優(yōu)性；但一般的遺傳算法盲目要求變異過程的隨機性，使算法退化成隨機搜索求取最優(yōu)解。

4.6 改進遺傳算法流程圖

本文提出的具有UUV機動性約束條件的改進遺傳算法流程圖如圖4所示。

5 復合自適應變異策略

針對遺傳算法存在的變異能力不足的問題，本文提出一種復合型的自適應變異運算策略，隨進化過程對變異幅度及方向進行適當的調控。相比于一般遺傳算法的隨機進化，改進后的算法進化過程更為智能，其收斂能力和全局尋優(yōu)能力也明顯提高。

變異運算的改進包括兩部分：自適應變異強度控制和雙階段自適應變異控制。

5.1 自適應變異控制

自適應變異控制的變異效果可參考圖5。

主要思路如下：

1)自適應地控制回收路徑中不同次序路徑階段的變異幅度。圖5中1～4分別表示4條不同的路徑，路徑2～路徑4是路徑1采用不同變異方向的結果，Ⅰ、Ⅱ、Ⅲ、Ⅳ依次表示組成路徑的4個路徑階段。路徑2、3分別是路徑1在階段Ⅱ發(fā)生φ角幅度變異和Δl路長幅度變異得到的新路徑；路徑4是路徑1在階段Ⅳ航向角發(fā)生β角幅度變異的結果。

對比路徑2和路徑3相比于路徑1的變異效果，路徑3和路徑1的涉及的空間區(qū)域較重合，可見航向角變異相比于路長變異對路徑的影響更為顯著。對比路徑2和路徑4，可得對前期的路徑階段進行航向角變異，回收路徑的探尋范圍影響相對更大。但在障礙物較多的環(huán)境中，前期階段的搜索范圍過大會使后期路徑階段難以收束在末位置附近，對種群的性能產生不利影響。因此，應根據基因類型及其所在階段序號，自適應調整和控制基因變異的幅度。

2)變異強度隨種群進化迭代進行自適應控制。在種群進化早期，變異有效提高種群多樣性且明顯增強遺傳算法的全局搜索性能；在進化后期，種群優(yōu)良個體已經較為趨近最優(yōu)解，此時需要避免強烈變異對優(yōu)良個體產生不利影響[21]。因此隨遺傳代數逐漸增加，應自適應地降低變異幅度，同時降低變異發(fā)生的概率。

因此，本文對變異操作進行了一些調整和改進，提出了自適應變異控制方法：

(10)

式中：A1和A2為變異幅度項，通常取一固定常數值；D為方向控制項；λ(i)為基因位控制項；δ(k)為遺傳代數控制項；Rand1、Rand2均表示[0，1]范圍內的隨機實數。

若經變異操作后，變量超出了允許范圍，則通過(11)式調整：

(11)

(10)式中的各項參數值如下：

(12)

方向控制項D的目的是使子代個體的變異階段上的基因隨機選擇變異進行的方向，航向和路長的方向控制項具體取值如(13)式所示：

D1=±1，D2=±1

(13)

用于變異的個體在種群中通常表現較差，為增強算法尋優(yōu)的速度，改進算法在變異操作中將父代的最優(yōu)個體復制并加入變異種群中，隨機替換掉變異種群的任意個體。用最優(yōu)個體進行變異尋優(yōu)，可以提高子代得到更優(yōu)個體的概率，從而加快算法的收斂速度。

改進的遺傳算法加入控制項λ(i)和δ(k)，提出一種新的自適應變異方法。(10)式中，由參數項D決定個體變異是否沿正向進行，參數項A1、A2、λ(i)、δ(k)共同決定個體變異的幅度上下限?；蛭豢刂祈棪?i)使變異幅度隨基因順序線性增大，路徑階段越早，航向的變異范圍越小，從而避免次序靠后的路徑階段難以收束在末位置附近，UUV探尋的路徑范圍遠離目標路徑所在區(qū)域的問題；遺傳代數控制項δ(k)可隨遺傳代數增加降低變異幅度，進化早期允許存在大的變異幅度，可以盡可能搜索解空間，快速找到性能良好的可行路徑；進化后期種群已經趨近收斂，δ(k)自適應降低變異幅度，使種群個體逐漸趨近最優(yōu)解。

5.2 雙階段自適應變異控制

如果在若干代內最優(yōu)個體仍未進化，通常情況為當前最優(yōu)個體的部分路徑節(jié)點位于障礙物附近，此時任意路徑階段的變異均有可能導致路徑與障礙物發(fā)生碰撞，使最優(yōu)個體變異產生的子代路徑為不可行路徑。種群迭代的進化效果不佳，難以找到更優(yōu)個體，進化陷入停滯。

對此，本文提出一種雙階段自適應變異控制的變異策略，具體如圖6所示。

圖6(a)、圖6(b)分別為對接近障礙物圓的回收路徑采用雙階段自適應變異策略和單階段自適應變異控制的結果，兩圖的變異幅度值均為β。圖6中，a、b、c、d、e分別為原路徑的不同路徑階段，A、B為路徑階段a、b的末端路徑節(jié)點，A′、B′為a、b階段發(fā)生航向角變異后產生的新的末端路徑節(jié)點。原路徑用黑色實線表示，變異后的新路徑以虛線表示。

圖6(b)在a階段發(fā)生變異生成新節(jié)點A′后，相連的后續(xù)階段b、c、d、e的節(jié)點也隨之改變，更新為B′、C′、D′、E′，而各階段的航向角和路長保持不變，從圖6(b)可以看出，該情況下的新生成路徑與障礙物圓會發(fā)生碰撞，導致新生成路徑不可行，此次變異失效。這是自適應變異控制中種群進化陷入停滯的主要原因。

針對圖(b)中的問題，圖6(a)的雙階段自適應變異策略在a路徑階段發(fā)生變異生成新節(jié)點A′后，b路徑階段末端節(jié)點位置不變，首端節(jié)點更新為A′，即b路徑階段的路長和航向角發(fā)生了確定的改變。新的變異策略把路徑階段的變異控制在了局部路徑中，避免變異對后續(xù)的路徑階段產生干擾，保證了后續(xù)路徑仍具有可行性，有效地解決了自適應變異的問題。從圖6(a)知，新路徑可行且優(yōu)于原路徑，變異沒有影響路徑的可行性，并且產生了更優(yōu)的個體。

雙階段自適應變異策略的主要思路如下：

考慮到第i階段的微小變異作用到第i+1階段的影響會放大，雙階段自適應變異中第i階段的變異只進行航向角變異，且變異幅度項A1的取值調整為

(14)

作為評估標準的代數間隔根據種群目標迭代代數Gmax進行設置。

在種群迭代進化過程中，比較當代種群最優(yōu)個體與Δk代前種群最優(yōu)個體，若最優(yōu)個體適應度值在Δk代間未進化，則考慮此時單一的自適應變異不能有效引導種群進化，從而改用雙階段自適應變異策略對個體進行變異，促使包含父代最優(yōu)個體的變異種群進行有效的進化生成子代種群，相關過程如圖4所示。

雙階段自適應變異策略解決了自適應算法因種群當前最優(yōu)路徑位于障礙物附近而產生的種群進化停滯、難以找到更優(yōu)個體的問題，使位于障礙物附近的局部路徑階段不會受到其他路徑階段變異的影響，一定程度上保證子代變異路徑的可行性；對算法的當前最優(yōu)路徑解進行雙階段自適應變異，產生性能更好的子代路徑最優(yōu)解，從而引導種群參考新的最優(yōu)解進化；在迭代后期當前最優(yōu)解趨于全局最優(yōu)解的時候，對當前最優(yōu)解進行局部路徑階段的優(yōu)化。綜合上述，雙階段自適應變異策略明顯增強了算法的進化尋優(yōu)能力。

6 仿真與分析

本文使用MATLAB軟件進行模擬仿真實驗，分別建立一個具有一般環(huán)境復雜度的水域環(huán)境模型和一個具有較高環(huán)境復雜度的水域環(huán)境模型進行分析。設置種群規(guī)模為100，個體的回歸路徑階段總數為20，種群目標迭代代數為1 000代，精英個體選擇概率為0.20，交叉概率為0.20，變異概率為0.60。適應度函數中的懲罰系數取值C1=15，C2=15。

實驗將路徑規(guī)劃的終點放在回收平臺的尾部圓形區(qū)側方，選取該位置可以避免遺傳算法規(guī)劃時由于接近平臺障礙路徑最優(yōu)解難以收斂的問題，同時也是為下一段路徑UUV姿態(tài)調整提供空間，保障UUV姿態(tài)調整過程的安全。

6.1 一般復雜水域環(huán)境

一般環(huán)境復雜度水域模型中的UUV起始位置坐標為[200 m，200 m]，起始的航向角為π/6 rad，回收的終點位置坐標為[1 652 m，1 630 m]，UUV的最小回轉半徑為55 m。

通過計算得到路徑規(guī)劃的機動性約束條件為li∈[0.8d，1.35d]，Δθ∈[-2π/5 rad,2π/5 rad]。

給定的水域障礙物圓參數如表1所示。

表1 一般復雜水域障礙物圓參數

圖7為在UUV的一般復雜水域中，通過1 000代獨立仿真實驗后，遺傳算法、改進的自適應遺傳算法和改進的復合自適應遺傳算法分別得到的UUV最優(yōu)回收路徑。其中左下方為UUV的起始所在位置，紅色扇形為初始允許的航向角范圍，右上角的黑色圖標為潛艇所在位置，紅色圓形圖標是潛艇的尾部回收區(qū)，紅色圖標下方的圓環(huán)標志是UUV回收路徑的終點位置。

遺傳算法求解得到的UUV最優(yōu)回收路徑總長為2 219.95 m，迭代時間為15.49 s；改進的自適應遺傳算法求解得到的UUV最優(yōu)回收路徑總長為2 126.33 m，迭代時間為15.38 s；改進的復合自適應遺傳算法求解得到的UUV最優(yōu)回收路徑總長為2 111.98 m，迭代時間為15.47 s。3種算法的迭代時間沒有明顯區(qū)別。從圖7中可以看出：自適應遺傳算法和復合自適應遺傳算法的路徑平滑程度和路徑長度都明顯優(yōu)于遺傳算法；復合自適應遺傳算法的輸出路徑在保持較好平滑度的同時，路長優(yōu)于自適應遺傳算法。

圖8為3種算法的種群最優(yōu)適應度進化曲線。由圖8明顯可以看出：在進化前期的0～200代內算法最佳適應度均呈振蕩下降，這一階段種群都在嘗試進化獲得符合機動性約束的最優(yōu)個體，且都獲得了可行個體；200次迭代以后，算法的進化速度明顯放緩，最終都實現了收斂。遺傳算法在300代以后進化停滯，表明遺傳算法陷入了局部最優(yōu)；自適應遺傳算法和復合自適應遺傳算法在進行有效進化以逼近全局近似最優(yōu)解。從圖8中可以看出，二者都較好地逼近了近似最優(yōu)解，而復合自適應遺傳算法趨近收斂的速度更快，得到的路徑也更短，表明復合自適應變異策略有效地引導種群最優(yōu)個體緩慢逼近全局近似最優(yōu)解。

6.2 高復雜水域環(huán)境

高環(huán)境復雜度水域模型中的UUV起始位置坐標為[305 m，365 m]，起始的航向角為π rad，回收的終點位置坐標為[1 452 m，1 595 m]，UUV的最小回轉半徑為55 m。通過計算得到路徑規(guī)劃的機動性約束條件為：li∈[0.8d，1.5d]，Δθ∈[-π/3 rad，π/3 rad]。

給定的水域障礙物圓參數如表2所示。

表2 復雜水域障礙物圓參數

圖9為在UUV的高復雜水域中，通過1 000代獨立仿真實驗后，遺傳算法、改進的自適應遺傳算法和改進的復合自適應遺傳算法分別得到的UUV最優(yōu)回收路徑。

遺傳算法求解得到的UUV最優(yōu)回收路徑總長為2 024.44 m，迭代時間為18.0 s；改進的自適應遺傳算法求解得到的UUV最優(yōu)回收路徑總長為1 876.31 m，迭代時間為17.83 s；改進的復合自適應遺傳算法求解得到的UUV最優(yōu)回收路徑總長為1 851.93 m，迭代時間為18.1 s。3種算法的迭代時間沒有明顯區(qū)別。從圖中可以看出，自適應遺傳算法和復合自適應遺傳算法的路徑平滑程度和路徑長度都明顯優(yōu)于遺傳算法；其中復合自適應遺傳算法的輸出路徑在保持較好平滑度的同時，路長優(yōu)于自適應遺傳算法。

圖10為高復雜水域中3種算法的種群最優(yōu)適應度進化曲線。

從圖10中明顯可以看出：在進化前期的100代內最佳適應度均呈振蕩下降，在這一階段種群都在嘗試進化獲得符合機動性約束的最優(yōu)個體，且都獲得了可行個體；200次迭代以后，算法的進化速度明顯放緩，最終都實現了收斂。遺傳算法在200代以后進化停滯，陷入了局部最優(yōu)解；遺傳算法陷入了局部最優(yōu)解；自適應遺傳算法和復合自適應遺傳算法200代以后仍在進化以逼近全局近似最優(yōu)解，二者都較好地逼近了近似最優(yōu)解，其中復合自適應遺傳算法趨近收斂的速度明顯優(yōu)于自適應遺傳算法，得到的路徑也更短，表明復合自適應變異策略的確在自適應遺傳算法的基礎上進行了優(yōu)化，算法尋優(yōu)能力有了明顯提升。

7 結論

本文針對遺傳算法用于UUV水下路徑規(guī)劃時可能陷入局部最優(yōu)的問題，提出一種復合自適應變異運算策略，通過引導路徑變異進化的方向，使生成的路徑解盡可能搜索整個解空間，解決了進化后期的種群進化有一定可能陷入停滯、難以找到更優(yōu)個體的問題，使種群最優(yōu)解持續(xù)進化，更加逼近全局近似最優(yōu)解；針對柵格法進行環(huán)境建模會使所得最優(yōu)路徑與實踐所用路徑偏差較大，且所得的最優(yōu)路徑可能不符合UUV的機動能力，在建模時直接采用對障礙物進行處理后的水域二維坐標圖進行分析，并對路徑規(guī)劃提出基于UUV機動性的航向角約束和路長約束，使最終生成的路徑更具有高效性、實用性。

算法使用MATLAB軟件進行遺傳算法、自適應遺傳算法和復合自適應遺傳算法3種算法的仿真驗證，仿真結果表明，相比于其他兩種算法，改進的復合自適應遺傳算法在UUV水下路徑規(guī)劃方面的收斂速度和全局尋優(yōu)能力更優(yōu)，在復雜水域環(huán)境更具有可行性和優(yōu)越性。

一般而言，出于水下回收對接的需要，UUV的水下回收路徑末端還需兼顧UUV的姿態(tài)約束，但限于篇幅以及需要保證遺傳算法的性能發(fā)揮并未展開研究，本文為這一內容的研究預留了空間，并將其作為下一階段的研究工作進行。