基于自適應A*算法和改進遺傳算法的反艦導彈航路規劃*

李紅亮，宋貴寶，劉 鐵

(海軍航空工程學院，山東煙臺 264001)

0 引言

航路規劃的主要目的就是在確保飛行器安全飛行的基礎上，以可實現的最優路徑飛向目標。針對航路規劃的求解，國內外學者已經做了大量的工作，比較成熟的算法主要有:動態規劃法[1]、A*搜索法[2]、人工勢場法[3]、遺傳算法[4]、蟻群算法[5]、粒子群算法[6]等。但是這些搜索算法本身計算量比較大，計算時間也比較長，算法的研究大多只限于理論上論證技術的可行性，難于在工程上實現。為此，文中提出兩種路徑規劃改進算法:自適應A*算法和改進遺傳算法，主要目的是為了最大限度的減少計算時間，且不退化解的次最優性。

航路規劃算法通常在所有可通行區域尋找全局最優路徑，如果搜索空間不能涵蓋全部可通行地區，該算法在搜索結束時可能會得不到全局最優軌跡[7]。文中提出的基于自適應的改進A*算法，解決了網絡在搜索時間內無法覆蓋所有可通行區域的難題，算法通過啟發式的搜索更大跨度的區間，降低了錯過最優解的可能性和縮短了收斂時間。經過改進的A*算法在搜索過程中根據當前作戰區域的復雜性而自適應的改變搜索參數，克服了運算時間和搜索空間巨大的難題。此外，為了防止算法搜索不必要的戰場區域，搜索空間是在搜索時智能產生的。搜索空間樹從發射平臺開始構造一直延伸到目標，延伸過程中考慮戰場地理環境、導彈機動性能和動力航程約束。

近年來，遺傳算法同A*算法一樣，被廣泛應用于解決復雜的優化問題。在路徑規劃問題，特別是在機器人應用技術中，頂點啟發式方法被主要用于染色體創建，原因是最短路徑必須通過起始點和目標點之間的所有障礙頂點。這個假設縮短了遺傳算法的收斂時間，因為它只需搜索頂點，而不用搜索整個環境[8]。然而，對于反艦導彈航路規劃問題，作戰區域中的圓形威脅區沒有任何頂點，并且地理海岸線非常復雜，只能由眾多給定頂點代表。因此，頂點搜索不是一個有效的方法。文中提出一種新技術，可以在很短的時間內創建出可行的初始航路種群，且保持群體的多樣性，算法從一個可行的種群入手，不再需要花時間來獲得可行的個體。對于航路的編碼，傳統方式是采用固定長度的二進制字符串，這種編碼方式對于含有障礙的搜索空間是非常困難的，進而導致了遺傳進化速度的降低[9]。文中利用可變長度和實數編碼技術，替代限定長度的染色體固化編碼方式，提高了進化算法的靈活性。

1 約束定義和環境模型

反艦導彈向目標飛行過程中，需要避開某些特殊的區域，如島嶼、敵方火力攔截區、已方兵力集結區等，這些區域統稱為飛行規避區，而反艦導彈的航路是要盡量避免與飛行規避區相交的。

飛行規避區半徑是目標類型和速度的函數。例如，小目標有更好的機動性，因此未知的運動范圍比大目標的要大。另外，航路規劃時應該在飛行規避區邊界設置一定的緩沖區，即將規避區邊界適當外擴以修正反艦導彈的中段制導誤差和風的影響。由于導彈飛行誤差隨時間的積累，緩沖區的半徑隨著導彈射距的增加而變大。

反艦導彈飛行規避區如圖1所示，它是由網格組成的數字地圖，網格的分辨率應根據導彈的最大射程或搜索算法所需的精度確定。每個網格的值為1或0，1表明在安全飛行區，0則表明在飛行規避區。文中提出的改進A*搜索算法和改進遺傳搜索算法都是立足于數字規避地圖，從目標到發射平臺反向進行搜索的。反向搜索的原因是反艦導彈雷達開機時的目標距離和攻擊舷角是非常重要的，它們直接決定了對目標的搜捕成功概率，因此必須首先確定。

圖1 反艦導彈飛行規避區數字地圖

2 航路規劃的改進A*算法

2.1 A*算法的基本原理

A*算法采用最佳優先搜索策略，從一個給定的初始節點到目標節點找到代價最低的航路[2]。它使用距離加代價的啟發式函數來確定其搜索樹中節點訪問的順序。距離加代價的啟發式函數是兩個函數之和:

式中:g(n)為實際代價函數，表示從起始節點到當前節點的代價;h(n)為可接受的從當前節點到目標距離的啟發估計代價函數，即其不能高估到目標的距離，對于反艦導彈航路規劃而言，h(n)代表到目標的直線距離。其中:

式中:r(s，c)表示從起點S到當前節點C的直線距離總和;m(s，c)表示從起點S到當前節點C所需的全部機動距離之和;wr和wm分別表示直線距離和機動距離的權重，權重的大小直接影響航路規劃結果，取決于決策者選擇最小的航路長度還是最平滑的航跡。

圖2 搜索扇面示意圖

2.2 改進A*算法

A*搜索方法在構建網絡時主要涉及3個參數。如圖2所示，一個是搜索扇面角(2α)，另一個是角分辨率(β)或扇區角，最后一個參數是步長(L)，即當前節點與父節點之間的距離。搜索扇面角由反艦導彈的最大轉彎角決定，它可以取最大轉彎角的2倍。導彈在不超過最大轉彎角時可以向右轉或向左轉。設置的扇面角越大，搜索的區域越大，意味著計算量越大。另外，角分辨率越小，找到最優解的概率就越大。然而，隨著扇面角的增大或角分辨率的減小，收斂計算所需的內存和時間也成指數增長。步長受限于最小節點間距，即航路在相鄰兩次轉彎之間的導彈飛行的最小直線距離。

綜上所述，每個搜索參數對生成的航路和算法的收斂時間都有很大影響。傳統的A*算法在確定搜索參數時沒有考慮任務場景，使用默認值。當然也有些文獻[10－11]，根據戰術態勢和作戰場景，利用智能方法確定搜索參數，首先針對不同的任務場景估計得到不同的預計值，然后將這些值作為參數用于整個搜索過程，相比在每個場景使用統一的默認值，這樣做的確減少了計算量。然而，對于復雜的作戰場景，整個搜索過程仍過于緩慢，導致在一定的時間內無法獲得最優解或次優解。

文中提出的改進A*算法，在搜索過程中，根據作戰區域的復雜程度，自適應的調整搜索參數。例如，在簡單的地理環境或障礙較少的情況下，可以降低搜索精度(粗搜索)以爭取時間;當在復雜的作戰區域，即搜索有難度或在飛行規避區有較少的可通行區域，則需提高搜索精度(細搜索)，以免錯過理想的可行航路。

如圖3所示復雜場景下的航路規劃，搜索的早期階段(作戰區的上半部分)，由于環境不復雜，所以搜索分辨率設置得較低;但是在作戰區的中間區域，反艦導彈飛行規避區域明顯密集起來，可行通道較為狹窄，因此必須提高搜索分辨率細化搜索。虛線表示搜索參數為默認值時的搜索合成路徑，點劃線表示自適應調整搜索參數時的搜索合成路徑，結果為虛線航路比點劃線航路長得多。

圖3 固定與變化搜索參數時的航路對比

對于參數保持不變的A*搜索算法，要獲得更好的航路，唯一的辦法就是提高搜索分辨率。可是密集搜索就意味著高計算量。如圖4所示，減小步長和扇區角，即提高分辨率，雖然能夠獲得更短的航路，但收斂計算時間成指數增長。而用自適應變搜索參數代替高分辨率，同樣可以得到高質量的航路，但計算時間卻大大減少(超過3倍)。

圖4 分辨率對航路長度和計算時間的影響

改進A*算法的步驟概括如下:

1)以目標為起點，找到所有可能通向目標且相互不交叉的航路段，航路段長度等于反艦導彈對目標的最小可攻擊距離。計算所有航路段的代價，將代價最小的放進CLOSE表中，其他的放進OPEN表中。

2)設置扇面搜索參數，使分辨率參數為最小(L=Lmax且 β = βmax)。

3)在OPEN表中找到最小代價的航路，在該航路末端利用搜索參數(L和β)創建一個搜索扇面，扇面角為反艦導彈最大轉彎角α的2倍。將OPEN表中最小代價的航路放進CLOSE表中。

4)檢查步驟3)中產生的航路避障情況。如果有任何航路與飛行規避區相交，則轉步驟5);否則，轉步驟6)。

5)將分辨率提高n倍(L=L/n且β=β/n)，但必須確保L≥Lmin且β≥βmin;另外，刪除交叉的航路，把剩余航路放到OPEN表中。然后，轉步驟3)。

6)將生成的航路放入OPEN表中。

7)將代價最小的航路放入CLOSE表中，新生成航路的“父節點”航路放入OPEN表中，目的就是可在OPEN表中追蹤到任何一段航路的父節點航路。轉步驟3)。

8)重復上述步驟，(a)直到發射平臺與OPEN表中當前航路之間沒有任何障礙，(b)直到OPEN列表是空的。

9)如果情況是(a)，意味著有解，可通過追蹤OPEN表中當前航路的父節點航路找出一條合成航路。

10)如果情況是(b)，則意味著無解。

最后，為了縮短通過改進A*方法搜到的航路長度，采用航路拉直的方法，并嘗試在合成航路上刪除多余的航路點。

3 航路規劃的改進遺傳算法

將遺傳算法應用于反艦導彈航路規劃問題，關鍵是如何采用合適的編碼方式對代表導彈飛行航路的染色體進行編碼，如何在規定的約束條件下，不但要規避障礙保證導彈飛行安全，而且盡量最小化航路長度和平滑飛行軌跡。下面是文中提出的一種用于遺傳算法的子算法。

3.1 編碼方法和適應度函數

一條染色體表示航路點的一個序列。同時，為了使算法更加靈活，文中提出變長實數編碼方法。這就是說，航路點的數量從一條航路到另一條航路可能是變化的，當然每條航路轉彎點的數量不會超過反艦導彈自身性能所允許的最大航路點個數。

同A*算法中描述的代價函數一樣，適應度函數由各航路點間直線距離總和與導彈機動距離總和加權組成。由于所有的備選航路都是可行的，適應度函數中不含懲罰項。

3.2 初始化種群

傳統的遺傳算法在初始化種群時，一般采用隨機化的生成方式，這樣做的好處在于它提供了解的廣泛的多樣性，但也存在不利之處。因為在作戰區域可能會有許多障礙，初始化種群時隨機選擇的航路也許會穿越障礙，那么這條航路是不可行的。遺傳算法從含有非可行解的初始種群開始搜索，意味著需要花費一些時間通過使用隨機交叉和變異操作來獲得可行的候選航跡。總體來說，可行候選解的搜索需要花費較長時間，降低了遺傳算法的整體收斂性能。遺傳算法采用隨機產生初始種群的文獻案例很多，例如文獻[8]中的移動機器人路徑規劃研究。在該研究中，環境2的復雜程度與文中圖5中的任務環境非常相似，結果顯示在環境2中第一次可行的路徑，是在第23代搜索到的，耗時2.59s。這對于反艦導彈作戰需要實時任務規劃而言是不可接受的，無法應用于工程實踐。

另一方面，文中提出的新技術，可以在合理的較短時間內生成可行的初始航路群，遺傳算法的收斂性能得到較大提高。然而，采用新技術替代隨機生成初始種群也是以損失種群的多樣性為代價的。為此，新技術在生成初始可行候選解時，加入隨機因素來保持搜索空間的多樣性和廣泛性，并采用了基于簡單樹的搜索算法。算法主要步驟如下:

1)設置起始點為當前節點。

2)在當前節點利用分辨率參數(L和β)創建一個搜索扇面，扇面角為反艦導彈最大轉彎角α的2倍，設為一固定值。

3)檢查當前產生的扇面內的每段航路的避障情況，刪除與飛行規避區相交的航路。

4)產生一個隨機整數r，1≤r≤nw+1，這里nw為反艦導彈最大航路轉彎點個數。

5)檢查隨機分配因子是否小于等于扇面邊數。如果r≤ nl，轉步驟6);否則轉步驟7)。

6)隨機選擇扇面中的一條邊，然后轉步驟2)。這意味著航路段應該隨機產生，直到r＞nl，這么做保證了初始可行解的多樣性，并防止了搜索容易陷入局部極小點。

7)計算扇面內各航路末端到目標的直線距離，選擇距離最小的邊以替代隨機選擇，然后轉步驟2)。參數r決定了何時停止隨機式選擇、啟用確定式選擇。隨機式選擇幫助增加了解的多樣性，而確定式選擇引導航路指向目標。例如，如果r較大，獲得的初始航路會較長、較彎曲，但維護了解的多樣性;此外，一旦縮小r值，就會獲得更短、更平滑的航路。這對于改進遺傳算法的收斂效率是有用的。

8)為了獲得一條可行的候選航路，重復步驟2)～7)，直到當前節點與目標節點之間沒有障礙。

如圖5所示，利用提出的初始解產生方法，在0.37s這么短的時間內就生成了20條可行航路，并且初始種群覆蓋了圖5障礙環境中絕大多數的可通行區域，解的多樣性是令人滿意的。還有就是改進遺傳算法搜索效率也是很高的，在第32代便獲得最優解，收斂耗時 1.03s。

3.3 遺傳操作

1)交叉算子。將種群兩兩組對，采用單點交叉法對每組染色體實施交叉操作，兩個父代染色體隨機生成要相互交叉的節點位置，交叉操作后，父代航路用直線在選擇的交叉點處連成兩條新的子代航路(如圖6所示)。如果連線與作戰區域的障礙相交，采用修正算子將其修復成可行航路。

圖5 種群初始化

圖6 遺傳操作示意圖

2)變異算子。隨機選擇航路某一節點，將該節點轉變到另一位置，生成一條新的航路，實現對航路的變異操作(如圖6所示)。變異會不斷重復操作過程，直到獲得可行的子代航路。

3)修正算子。修正算子僅用于支持交叉和變異算子，并不單獨使用。染色體在進行交叉和變異操作后，如果獲得的解為非可行解，它可以通過修正操作將非可行解變得可行。文中在使用遺傳算法進行反艦導彈航路規劃時，沒有采用伸展機制來平滑候選航路，目的是不減少搜索的多樣性，避免搜索過程陷入局部極小點。

4 仿真結果和分析

利用改進A*算法和改進遺傳算法分別對3個不同復雜程度的作戰場景進行仿真實驗，并且對仿真結果進行比較和分析。

如圖7中顯示的3個地理場景，作戰區域網格大小為100m×100m，復雜等級從1到3，衡量標準為障礙數量的多少，改進遺傳算法交叉概率C取0.5，變異概率M取0.2，種群規模PopSize取20。表1給出了仿真結果，包括兩種改進算法在3個想定中的搜索收斂時間和航路距離。根據仿真結果，改進遺傳算法的收斂時間隨環境復雜程度的提高而增長，而改進A*算法并沒有明顯變化，表明改進A*算法在搜索過程中通過自適應調整搜索參數能適應不同的作戰環境。改進A*算法隨環境的變化，收斂時間不僅未受到實質影響，而且由于運算時間短，能夠滿足實時航路規劃要求。雖然改進遺傳算法在收斂時間上落后A*算法10倍以上，但其收斂精度更高，能獲得最優解(如場景2中航路比改進A*算法縮短了15%)

圖7 仿真結果圖

在場景1和場景2中，除了遺傳算法壓縮了A*找到的路徑，使之變短了一些之外，兩種算法發現的路徑十分相似。然而，在場景3中，兩種算法獲得了航路總長差別很小卻截然不同的路徑。A*算法不能獲得遺傳算法所發現的可通行區域的原因可能是自適應搜索參數間隔大小的問題。通過提高角分辨率β或減小搜索步長L，可以獲得更好的路徑。出于該目的，β和L的間隔被縮短到極限，仿真結果表明提高搜索分辨率使A*算法獲得了同遺傳算法所得結果相似的航路。雖然如此，A*算法獲得的航路仍然比遺傳算法發現的航路長4.8km之多，這意味著分辨率還是不夠。然而提高分辨率會讓A*算法的搜索計算時間成指數增長。

表1 仿真結果

5 結束語

航路規劃計算的主要難題在于運算時間長、消耗內存大。為了提高運算速度，文中提出了分別基于A*算法和遺傳算法的兩種不同的規劃技術，用于反艦導彈航路規劃。仿真結果發現，通過提高傳統A*算法的適應性和將種群智能創建技術加入傳統遺傳算法，時間收斂均顯著降低，而且不會惡化解的收斂精度。兩種改進方法彼此各有優缺點，比較表明在計算時間上改進A*算法要優于改進遺傳算法，但在解的最優性上則落后于后者。所以，改進A*算法適合用于時間要求苛刻，尤其是動態環境中需要緊急規劃的任務問題;相反，改進遺傳算法則適合用于發射前并且精度要求高的航路規劃問題。

文中主要研究的是單導彈航路規劃，兩種改進算法可以擴展用于多導彈協同航路規劃問題，可以通過并行運算、相互通信、彼此協調共同完成多重航路規劃研究，這是后續研究的內容。

[1]郝峰，劉明喜，翟英存，等.動態規劃算法在巡飛彈航路離線規劃中的應用[J].彈箭與制導學報，2007，27(1):67－69.

[2]張雅妮，高金源.一種基于改進A*算法的三維航跡規劃方法[J].飛行力學，2008，26(1):48－51.

[3]徐肖豪，李成功，趙嶷飛，等.基于人工勢場算法的改航路徑規劃[J].交通運輸工程學報，2009，9(6):64 －68.

[4]X Zhao，X Fan.A method based on genetic algorithm for anti-ship missile path planning[C]//Proc.of the IEEE Int.Joint Conference on Computational Sciences and Optimization，2009:156－159.

[5]孫濤，謝曉方，喬勇軍.基于二維自由空間蟻群算法的反艦導彈航路規劃仿真[J].系統仿真學報，2008，20(13):3586－3588.

[6]于會，于鑫，李偉華.基于粒子群優化算法的航跡規劃與重規劃[J].計算機工程，2009，35(15):206－208.

[7]D Xin，C Hua-Hua，G Wei-kang.Neural network and genetic algorithm based global path planning in a static environment[J].Journal of Zhejiang University Science，2005，6(6):549－554.

[8]Y Wang，D Mulvaney，I Sillitoe.Genetic-based mobile robot path planning using vertex heuristics[C]//Proc.of the IEEE CIS，2006:1－6.

[9]Y Wang，D Mulvaney，I Sillitoe，et al.Robot navigation by waypoints[J].Journal of Intelligent and Robotic Systems，2008，52(2):175 －207.

[10]R J Szczerba，P Galkowski，I S Glickstein，et al.Robust algorithm for real-time route planning[J].IEEE Transactions on Aerospace and Electronic Systems，2000，36(3):869－878.

[11]K Tulum，U Durak，S K Ider.Situation aware UAV mission route planning[C]//IEEE Aerospace Conference，2009:1－12.