李紅亮，宋貴寶，劉 鐵

(海軍航空工程學(xué)院，山東煙臺(tái) 264001)

0 引言

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

航路規(guī)劃算法通常在所有可通行區(qū)域?qū)ふ胰肿顑?yōu)路徑，如果搜索空間不能涵蓋全部可通行地區(qū)，該算法在搜索結(jié)束時(shí)可能會(huì)得不到全局最優(yōu)軌跡[7]。文中提出的基于自適應(yīng)的改進(jìn)A*算法，解決了網(wǎng)絡(luò)在搜索時(shí)間內(nèi)無(wú)法覆蓋所有可通行區(qū)域的難題，算法通過(guò)啟發(fā)式的搜索更大跨度的區(qū)間，降低了錯(cuò)過(guò)最優(yōu)解的可能性和縮短了收斂時(shí)間。經(jīng)過(guò)改進(jìn)的A*算法在搜索過(guò)程中根據(jù)當(dāng)前作戰(zhàn)區(qū)域的復(fù)雜性而自適應(yīng)的改變搜索參數(shù)，克服了運(yùn)算時(shí)間和搜索空間巨大的難題。此外，為了防止算法搜索不必要的戰(zhàn)場(chǎng)區(qū)域，搜索空間是在搜索時(shí)智能產(chǎn)生的。搜索空間樹(shù)從發(fā)射平臺(tái)開(kāi)始構(gòu)造一直延伸到目標(biāo)，延伸過(guò)程中考慮戰(zhàn)場(chǎng)地理環(huán)境、導(dǎo)彈機(jī)動(dòng)性能和動(dòng)力航程約束。

近年來(lái)，遺傳算法同A*算法一樣，被廣泛應(yīng)用于解決復(fù)雜的優(yōu)化問(wèn)題。在路徑規(guī)劃問(wèn)題，特別是在機(jī)器人應(yīng)用技術(shù)中，頂點(diǎn)啟發(fā)式方法被主要用于染色體創(chuàng)建，原因是最短路徑必須通過(guò)起始點(diǎn)和目標(biāo)點(diǎn)之間的所有障礙頂點(diǎn)。這個(gè)假設(shè)縮短了遺傳算法的收斂時(shí)間，因?yàn)樗恍杷阉黜旤c(diǎn)，而不用搜索整個(gè)環(huán)境[8]。然而，對(duì)于反艦導(dǎo)彈航路規(guī)劃問(wèn)題，作戰(zhàn)區(qū)域中的圓形威脅區(qū)沒(méi)有任何頂點(diǎn)，并且地理海岸線(xiàn)非常復(fù)雜，只能由眾多給定頂點(diǎn)代表。因此，頂點(diǎn)搜索不是一個(gè)有效的方法。文中提出一種新技術(shù)，可以在很短的時(shí)間內(nèi)創(chuàng)建出可行的初始航路種群，且保持群體的多樣性，算法從一個(gè)可行的種群入手，不再需要花時(shí)間來(lái)獲得可行的個(gè)體。對(duì)于航路的編碼，傳統(tǒng)方式是采用固定長(zhǎng)度的二進(jìn)制字符串，這種編碼方式對(duì)于含有障礙的搜索空間是非常困難的，進(jìn)而導(dǎo)致了遺傳進(jìn)化速度的降低[9]。文中利用可變長(zhǎng)度和實(shí)數(shù)編碼技術(shù)，替代限定長(zhǎng)度的染色體固化編碼方式，提高了進(jìn)化算法的靈活性。

1 約束定義和環(huán)境模型

反艦導(dǎo)彈向目標(biāo)飛行過(guò)程中，需要避開(kāi)某些特殊的區(qū)域，如島嶼、敵方火力攔截區(qū)、已方兵力集結(jié)區(qū)等，這些區(qū)域統(tǒng)稱(chēng)為飛行規(guī)避區(qū)，而反艦導(dǎo)彈的航路是要盡量避免與飛行規(guī)避區(qū)相交的。

飛行規(guī)避區(qū)半徑是目標(biāo)類(lèi)型和速度的函數(shù)。例如，小目標(biāo)有更好的機(jī)動(dòng)性，因此未知的運(yùn)動(dòng)范圍比大目標(biāo)的要大。另外，航路規(guī)劃時(shí)應(yīng)該在飛行規(guī)避區(qū)邊界設(shè)置一定的緩沖區(qū)，即將規(guī)避區(qū)邊界適當(dāng)外擴(kuò)以修正反艦導(dǎo)彈的中段制導(dǎo)誤差和風(fēng)的影響。由于導(dǎo)彈飛行誤差隨時(shí)間的積累，緩沖區(qū)的半徑隨著導(dǎo)彈射距的增加而變大。

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

圖1 反艦導(dǎo)彈飛行規(guī)避區(qū)數(shù)字地圖

2 航路規(guī)劃的改進(jìn)A*算法

2.1 A*算法的基本原理

A*算法采用最佳優(yōu)先搜索策略，從一個(gè)給定的初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)找到代價(jià)最低的航路[2]。它使用距離加代價(jià)的啟發(fā)式函數(shù)來(lái)確定其搜索樹(shù)中節(jié)點(diǎn)訪問(wèn)的順序。距離加代價(jià)的啟發(fā)式函數(shù)是兩個(gè)函數(shù)之和:

式中:g(n)為實(shí)際代價(jià)函數(shù)，表示從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià);h(n)為可接受的從當(dāng)前節(jié)點(diǎn)到目標(biāo)距離的啟發(fā)估計(jì)代價(jià)函數(shù)，即其不能高估到目標(biāo)的距離，對(duì)于反艦導(dǎo)彈航路規(guī)劃而言，h(n)代表到目標(biāo)的直線(xiàn)距離。其中:

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

圖2 搜索扇面示意圖

2.2 改進(jìn)A*算法

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

綜上所述，每個(gè)搜索參數(shù)對(duì)生成的航路和算法的收斂時(shí)間都有很大影響。傳統(tǒng)的A*算法在確定搜索參數(shù)時(shí)沒(méi)有考慮任務(wù)場(chǎng)景，使用默認(rèn)值。當(dāng)然也有些文獻(xiàn)[10－11]，根據(jù)戰(zhàn)術(shù)態(tài)勢(shì)和作戰(zhàn)場(chǎng)景，利用智能方法確定搜索參數(shù)，首先針對(duì)不同的任務(wù)場(chǎng)景估計(jì)得到不同的預(yù)計(jì)值，然后將這些值作為參數(shù)用于整個(gè)搜索過(guò)程，相比在每個(gè)場(chǎng)景使用統(tǒng)一的默認(rèn)值，這樣做的確減少了計(jì)算量。然而，對(duì)于復(fù)雜的作戰(zhàn)場(chǎng)景，整個(gè)搜索過(guò)程仍過(guò)于緩慢，導(dǎo)致在一定的時(shí)間內(nèi)無(wú)法獲得最優(yōu)解或次優(yōu)解。

文中提出的改進(jìn)A*算法，在搜索過(guò)程中，根據(jù)作戰(zhàn)區(qū)域的復(fù)雜程度，自適應(yīng)的調(diào)整搜索參數(shù)。例如，在簡(jiǎn)單的地理環(huán)境或障礙較少的情況下，可以降低搜索精度(粗搜索)以爭(zhēng)取時(shí)間;當(dāng)在復(fù)雜的作戰(zhàn)區(qū)域，即搜索有難度或在飛行規(guī)避區(qū)有較少的可通行區(qū)域，則需提高搜索精度(細(xì)搜索)，以免錯(cuò)過(guò)理想的可行航路。

如圖3所示復(fù)雜場(chǎng)景下的航路規(guī)劃，搜索的早期階段(作戰(zhàn)區(qū)的上半部分)，由于環(huán)境不復(fù)雜，所以搜索分辨率設(shè)置得較低;但是在作戰(zhàn)區(qū)的中間區(qū)域，反艦導(dǎo)彈飛行規(guī)避區(qū)域明顯密集起來(lái)，可行通道較為狹窄，因此必須提高搜索分辨率細(xì)化搜索。虛線(xiàn)表示搜索參數(shù)為默認(rèn)值時(shí)的搜索合成路徑，點(diǎn)劃線(xiàn)表示自適應(yīng)調(diào)整搜索參數(shù)時(shí)的搜索合成路徑，結(jié)果為虛線(xiàn)航路比點(diǎn)劃線(xiàn)航路長(zhǎng)得多。

圖3 固定與變化搜索參數(shù)時(shí)的航路對(duì)比

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

圖4 分辨率對(duì)航路長(zhǎng)度和計(jì)算時(shí)間的影響

改進(jìn)A*算法的步驟概括如下:

1)以目標(biāo)為起點(diǎn)，找到所有可能通向目標(biāo)且相互不交叉的航路段，航路段長(zhǎng)度等于反艦導(dǎo)彈對(duì)目標(biāo)的最小可攻擊距離。計(jì)算所有航路段的代價(jià)，將代價(jià)最小的放進(jìn)CLOSE表中，其他的放進(jìn)OPEN表中。

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

3)在OPEN表中找到最小代價(jià)的航路，在該航路末端利用搜索參數(shù)(L和β)創(chuàng)建一個(gè)搜索扇面，扇面角為反艦導(dǎo)彈最大轉(zhuǎn)彎角α的2倍。將OPEN表中最小代價(jià)的航路放進(jìn)CLOSE表中。

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

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

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

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

8)重復(fù)上述步驟，(a)直到發(fā)射平臺(tái)與OPEN表中當(dāng)前航路之間沒(méi)有任何障礙，(b)直到OPEN列表是空的。

9)如果情況是(a)，意味著有解，可通過(guò)追蹤OPEN表中當(dāng)前航路的父節(jié)點(diǎn)航路找出一條合成航路。

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

最后，為了縮短通過(guò)改進(jìn)A*方法搜到的航路長(zhǎng)度，采用航路拉直的方法，并嘗試在合成航路上刪除多余的航路點(diǎn)。

3 航路規(guī)劃的改進(jìn)遺傳算法

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

3.1 編碼方法和適應(yīng)度函數(shù)

一條染色體表示航路點(diǎn)的一個(gè)序列。同時(shí)，為了使算法更加靈活，文中提出變長(zhǎng)實(shí)數(shù)編碼方法。這就是說(shuō)，航路點(diǎn)的數(shù)量從一條航路到另一條航路可能是變化的，當(dāng)然每條航路轉(zhuǎn)彎點(diǎn)的數(shù)量不會(huì)超過(guò)反艦導(dǎo)彈自身性能所允許的最大航路點(diǎn)個(gè)數(shù)。

同A*算法中描述的代價(jià)函數(shù)一樣，適應(yīng)度函數(shù)由各航路點(diǎn)間直線(xiàn)距離總和與導(dǎo)彈機(jī)動(dòng)距離總和加權(quán)組成。由于所有的備選航路都是可行的，適應(yīng)度函數(shù)中不含懲罰項(xiàng)。

3.2 初始化種群

傳統(tǒng)的遺傳算法在初始化種群時(shí)，一般采用隨機(jī)化的生成方式，這樣做的好處在于它提供了解的廣泛的多樣性，但也存在不利之處。因?yàn)樵谧鲬?zhàn)區(qū)域可能會(huì)有許多障礙，初始化種群時(shí)隨機(jī)選擇的航路也許會(huì)穿越障礙，那么這條航路是不可行的。遺傳算法從含有非可行解的初始種群開(kāi)始搜索，意味著需要花費(fèi)一些時(shí)間通過(guò)使用隨機(jī)交叉和變異操作來(lái)獲得可行的候選航跡?？傮w來(lái)說(shuō)，可行候選解的搜索需要花費(fèi)較長(zhǎng)時(shí)間，降低了遺傳算法的整體收斂性能。遺傳算法采用隨機(jī)產(chǎn)生初始種群的文獻(xiàn)案例很多，例如文獻(xiàn)[8]中的移動(dòng)機(jī)器人路徑規(guī)劃研究。在該研究中，環(huán)境2的復(fù)雜程度與文中圖5中的任務(wù)環(huán)境非常相似，結(jié)果顯示在環(huán)境2中第一次可行的路徑，是在第23代搜索到的，耗時(shí)2.59s。這對(duì)于反艦導(dǎo)彈作戰(zhàn)需要實(shí)時(shí)任務(wù)規(guī)劃而言是不可接受的，無(wú)法應(yīng)用于工程實(shí)踐。

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

1)設(shè)置起始點(diǎn)為當(dāng)前節(jié)點(diǎn)。

2)在當(dāng)前節(jié)點(diǎn)利用分辨率參數(shù)(L和β)創(chuàng)建一個(gè)搜索扇面，扇面角為反艦導(dǎo)彈最大轉(zhuǎn)彎角α的2倍，設(shè)為一固定值。

3)檢查當(dāng)前產(chǎn)生的扇面內(nèi)的每段航路的避障情況，刪除與飛行規(guī)避區(qū)相交的航路。

4)產(chǎn)生一個(gè)隨機(jī)整數(shù)r，1≤r≤nw+1，這里nw為反艦導(dǎo)彈最大航路轉(zhuǎn)彎點(diǎn)個(gè)數(shù)。

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

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

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

8)為了獲得一條可行的候選航路，重復(fù)步驟2)～7)，直到當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間沒(méi)有障礙。

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

3.3 遺傳操作

1)交叉算子。將種群兩兩組對(duì)，采用單點(diǎn)交叉法對(duì)每組染色體實(shí)施交叉操作，兩個(gè)父代染色體隨機(jī)生成要相互交叉的節(jié)點(diǎn)位置，交叉操作后，父代航路用直線(xiàn)在選擇的交叉點(diǎn)處連成兩條新的子代航路(如圖6所示)。如果連線(xiàn)與作戰(zhàn)區(qū)域的障礙相交，采用修正算子將其修復(fù)成可行航路。

圖5 種群初始化

圖6 遺傳操作示意圖

2)變異算子。隨機(jī)選擇航路某一節(jié)點(diǎn)，將該節(jié)點(diǎn)轉(zhuǎn)變到另一位置，生成一條新的航路，實(shí)現(xiàn)對(duì)航路的變異操作(如圖6所示)。變異會(huì)不斷重復(fù)操作過(guò)程，直到獲得可行的子代航路。

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

4 仿真結(jié)果和分析

利用改進(jìn)A*算法和改進(jìn)遺傳算法分別對(duì)3個(gè)不同復(fù)雜程度的作戰(zhàn)場(chǎng)景進(jìn)行仿真實(shí)驗(yàn)，并且對(duì)仿真結(jié)果進(jìn)行比較和分析。

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

圖7 仿真結(jié)果圖

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

表1 仿真結(jié)果

5 結(jié)束語(yǔ)

航路規(guī)劃計(jì)算的主要難題在于運(yùn)算時(shí)間長(zhǎng)、消耗內(nèi)存大。為了提高運(yùn)算速度，文中提出了分別基于A*算法和遺傳算法的兩種不同的規(guī)劃技術(shù)，用于反艦導(dǎo)彈航路規(guī)劃。仿真結(jié)果發(fā)現(xiàn)，通過(guò)提高傳統(tǒng)A*算法的適應(yīng)性和將種群智能創(chuàng)建技術(shù)加入傳統(tǒng)遺傳算法，時(shí)間收斂均顯著降低，而且不會(huì)惡化解的收斂精度。兩種改進(jìn)方法彼此各有優(yōu)缺點(diǎn)，比較表明在計(jì)算時(shí)間上改進(jìn)A*算法要優(yōu)于改進(jìn)遺傳算法，但在解的最優(yōu)性上則落后于后者。所以，改進(jìn)A*算法適合用于時(shí)間要求苛刻，尤其是動(dòng)態(tài)環(huán)境中需要緊急規(guī)劃的任務(wù)問(wèn)題;相反，改進(jìn)遺傳算法則適合用于發(fā)射前并且精度要求高的航路規(guī)劃問(wèn)題。

文中主要研究的是單導(dǎo)彈航路規(guī)劃，兩種改進(jìn)算法可以擴(kuò)展用于多導(dǎo)彈協(xié)同航路規(guī)劃問(wèn)題，可以通過(guò)并行運(yùn)算、相互通信、彼此協(xié)調(diào)共同完成多重航路規(guī)劃研究，這是后續(xù)研究的內(nèi)容。

[1]郝峰，劉明喜，翟英存，等.動(dòng)態(tài)規(guī)劃算法在巡飛彈航路離線(xiàn)規(guī)劃中的應(yīng)用[J].彈箭與制導(dǎo)學(xué)報(bào)，2007，27(1):67－69.

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

[3]徐肖豪，李成功，趙嶷飛，等.基于人工勢(shì)場(chǎng)算法的改航路徑規(guī)劃[J].交通運(yùn)輸工程學(xué)報(bào)，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]孫濤，謝曉方，喬勇軍.基于二維自由空間蟻群算法的反艦導(dǎo)彈航路規(guī)劃仿真[J].系統(tǒng)仿真學(xué)報(bào)，2008，20(13):3586－3588.

[6]于會(huì)，于鑫，李偉華.基于粒子群優(yōu)化算法的航跡規(guī)劃與重規(guī)劃[J].計(jì)算機(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.