基于改進(jìn)型遺傳算法的艦艇航路規(guī)劃研究＊

田 鶴 李啟華 孟一鳴

（海軍兵種指揮學(xué)院 廣州 510430）

1 引言

航線設(shè)計(jì)問題本質(zhì)上是航路任務(wù)規(guī)劃問題。航路規(guī)劃是在特定約束條件下尋找運(yùn)動(dòng)體從初始點(diǎn)到目標(biāo)點(diǎn)并且滿足某種性能指標(biāo)最優(yōu)的運(yùn)動(dòng)軌跡［1］。對(duì)于一個(gè)優(yōu)化問題，如果其目標(biāo)函數(shù)是可微的，并且問題的規(guī)模不是很大，我們可以采用一些傳統(tǒng)的優(yōu)化方法解決，如可視圖法、人工勢(shì)場(chǎng)法等，可是對(duì)于目標(biāo)函數(shù)不可微甚至不連續(xù)，或者雖然目標(biāo)函數(shù)可微但問題的規(guī)模非常大的優(yōu)化問題，很多傳統(tǒng)的優(yōu)化方法往往不再適用［2］。由于遺傳算法不要求目標(biāo)函數(shù)的可微及連續(xù)性，而且可以在容許的時(shí)間范圍內(nèi)找到大規(guī)模優(yōu)化問題的滿意解，因此，近年來，遺傳算法已成為路徑規(guī)劃中使用較多的一種方法。

該方法被廣泛應(yīng)用于艦艇、飛行器和機(jī)器人的航路規(guī)劃中，但是考慮到基本的遺傳算法存在搜索時(shí)間長(zhǎng)，初始種群生成質(zhì)量差等問題，本文對(duì)其進(jìn)行改進(jìn)，即采用蟻群算法的搜索策略生成航線的初始種群，然后用遺傳算子對(duì)其進(jìn)行遺傳操作，進(jìn)而搜索出最優(yōu)航線，仿真結(jié)果表明，改進(jìn)后的遺傳算法在航路的搜索效率、初始種群的生成質(zhì)量、及最優(yōu)航線的選擇上有了明顯的提高。

2 遺傳算法用于航路規(guī)劃

2.1 初始群體的產(chǎn)生方法

初始種群是遺傳算法迭代運(yùn)算的起點(diǎn)，它由一定數(shù)目的個(gè)體所組成，當(dāng)網(wǎng)格數(shù)目較多時(shí)產(chǎn)生初始種群并非易事。由于遺傳算法的初始種群生成沒有統(tǒng)一的模式，因此考慮采用蟻群的搜索策略生成航線初始種群。采用蟻群算法的前行搜索遵循以下三條規(guī)則：

1）前行網(wǎng)格點(diǎn)必須是可行點(diǎn)；

2）搜索時(shí)避開已選擇的網(wǎng)格點(diǎn)；

3）搜索時(shí)如果下一網(wǎng)格點(diǎn)均不滿足上述兩條件，則刪除該點(diǎn)，從上一點(diǎn)開始重新選擇。

經(jīng)過蟻群搜索后生成的兩條初始航線如圖1所示。

圖1 初始航線生成示意圖

圖2 網(wǎng)格編碼示意圖

2.2 種群的編碼方法

由于采用蟻群算法的搜索策略生成航線的初始種群，因此種群的編碼方法既要適用于蟻群算法的單步搜索，又要方便遺傳算子對(duì)其進(jìn)行操作，基于此考慮采用變長(zhǎng)網(wǎng)格序號(hào)的方法進(jìn)行編碼。在采用網(wǎng)格序號(hào)進(jìn)行編碼時(shí)首先要對(duì)任務(wù)海區(qū)進(jìn)行網(wǎng)格離散化。離散具體方法可參考相關(guān)文章［7］，在此不做詳細(xì)介紹。序號(hào)法比直角坐標(biāo)表示網(wǎng)格點(diǎn)簡(jiǎn)潔，同時(shí)在操作過程中可以將網(wǎng)格的序號(hào)和直角坐標(biāo)關(guān)聯(lián)起來，由于直角坐標(biāo)更便于表示網(wǎng)格之間的相對(duì)位置，因此在對(duì)航線進(jìn)行適應(yīng)度評(píng)價(jià)時(shí)可以利用網(wǎng)格對(duì)應(yīng)的直角坐標(biāo)計(jì)算航線的航程及檢驗(yàn)航線的可行性。圖中直角坐標(biāo)和網(wǎng)格的轉(zhuǎn)換關(guān)系為［3］：

式中N表示螞蟻搜索過程中經(jīng)過的網(wǎng)格點(diǎn)的序號(hào)，x，y表示對(duì)應(yīng)的直角坐標(biāo)，其中，mod表示取余操作，int表示取整操作。圖1所示航線如果用序號(hào)編碼表示為：（0，1，7，12，17，18，24），用直角坐標(biāo)表示形式為：（（0，0），（1，0），（2，1），（2，2），（2，3），（3，3），（4，4））。由此可見采用網(wǎng)格序號(hào)編碼較直角坐標(biāo)編碼具有編碼長(zhǎng)度短、簡(jiǎn)明、直觀的優(yōu)點(diǎn)。編碼過程中網(wǎng)格點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為：

struct GridNode／／每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)包括該節(jié)點(diǎn)x，y坐標(biāo)該節(jié)點(diǎn)的編號(hào)o

航線個(gè)體的數(shù)據(jù)結(jié)構(gòu)表示為：struct antindividual｛

double value；／／目標(biāo)值

double fitness；／／適應(yīng)度值

int grid＿n；／／對(duì)應(yīng)的航線網(wǎng)格節(jié)點(diǎn)數(shù)

struct GridNode node［100］；／／網(wǎng)格節(jié)點(diǎn)數(shù)組 ｝

2.3 適應(yīng)度函數(shù)的建立

個(gè)體的適應(yīng)度函數(shù)直接影響到遺傳算法的計(jì)算效率［4］。一般在用遺傳算法解決某一優(yōu)化問題時(shí)，首先針對(duì)該問題進(jìn)行目標(biāo)函數(shù)的構(gòu)建，然后再由目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)。艦艇航路規(guī)劃時(shí)主要考慮三方面因素：即安全性、隱蔽性、及時(shí)性［5～6］。針對(duì)上述三個(gè)因素，在進(jìn)行航路規(guī)劃時(shí)主要從威脅代價(jià)、航程代價(jià)兩個(gè)方面進(jìn)行目標(biāo)函數(shù)的構(gòu)建。

2.3.1 航程代價(jià)函數(shù)模型

艦艇航線的航程為航路上各轉(zhuǎn)向節(jié)點(diǎn)（各網(wǎng)格點(diǎn)）之間的距離之和。以Dcost表示航程代價(jià)，則其表達(dá)式為：

式中N為航路段數(shù)，n為網(wǎng)格節(jié)點(diǎn)數(shù)，li為第i航路段的長(zhǎng)度，x，y分別為航路段中網(wǎng)格節(jié)點(diǎn)所對(duì)應(yīng)的直角坐標(biāo)。

2.3.2 威脅代價(jià)函數(shù)模型

威脅代價(jià)模型包括威脅概率模型和威脅函數(shù)模型［7］。

1）各種威脅概率模型

（1）水深威脅概率模型。水深威脅主要指可能不滿足艦艇吃水的淺水區(qū)域。以淺水區(qū)域中心為圓心，以覆蓋淺水區(qū)域的距離R為半徑畫圓，令艦艇距圓心的距離為d，建立其威脅概率函數(shù)模型

上式中，u為水深安全系數(shù)修正值，為一固定值，且u＞0。

（2）障礙物威脅概率模型。障礙物威脅區(qū)域可以用一圓形區(qū)域近似表示。設(shè)R是影響區(qū)域的最大半徑，d是艦艇到障礙物區(qū)域中心的距離，建立其威脅概率函數(shù)模型為：

上式中γ為障礙物安全系數(shù)修正值，為一固定值，且γ＞0。

（3）軍事威脅概率模型。軍事威脅一般為敵火炮、導(dǎo)彈等火力威脅，其威脅區(qū)域一般為敵武器系統(tǒng)的有效殺傷區(qū)域，基本上是以火力發(fā)射點(diǎn)為圓心，武器射程為半徑的圓。設(shè)武器系統(tǒng)的最大殺傷范圍為R，艦艇到威脅區(qū)域中心的距離為d，建立其威脅概率函數(shù)模型為：

上述三個(gè)模型的威脅概率值在距離最大處為0，在距離最小處為1，且威脅概率模型具有連續(xù)性，滿足距離越小，威脅程度越大的原則，可以較好地描述威脅源隨距離變化的威脅概率分布情況，在進(jìn)行航路規(guī)劃時(shí)，可以針對(duì)不同的任務(wù)情況特點(diǎn)，對(duì)不同的威脅賦予不同的權(quán)重系數(shù)。

2）威脅代價(jià)函數(shù)模型

由于一整條航線是由各個(gè)網(wǎng)格節(jié)點(diǎn)之間的航路線段組成的，因此可以將整條航線的威脅代價(jià)轉(zhuǎn)為對(duì)每個(gè)網(wǎng)格點(diǎn)的威脅代價(jià)的累加。根據(jù)這一思想，建立威脅代價(jià)函數(shù)模型為：

上式中N為網(wǎng)格節(jié)點(diǎn)數(shù)，M為威脅源數(shù)目，pij（dij）為j威脅源對(duì)網(wǎng)格點(diǎn)i的威脅概率，dij表示網(wǎng)格點(diǎn)i到威脅源j的最近距離，kj為威脅源j的權(quán)重系數(shù)。

2.3.3 目標(biāo)函數(shù)模型

建立了航程代價(jià)函數(shù)模型和威脅代價(jià)函數(shù)模型后，可綜合建立航線的目標(biāo)代價(jià)函數(shù)為：

代入各自的計(jì)算公式為：

2.3.4 適應(yīng)度函數(shù)模型

航線代價(jià)函數(shù)與適應(yīng)度函數(shù)的轉(zhuǎn)化結(jié)合遺傳算法對(duì)適應(yīng)度函數(shù)的約束條件，可以采用以下形式來實(shí)現(xiàn)航線目標(biāo)代價(jià)函數(shù)與航線適應(yīng)度函數(shù)之間的轉(zhuǎn)換［8］：

上式中，β為一系數(shù)修正值，Cmin為一正的固定值。經(jīng)過上式的轉(zhuǎn)換，即將代價(jià)函數(shù)的最小值問題轉(zhuǎn)換為求適應(yīng)度函數(shù)的最大值問題，完全符合遺傳算法對(duì)適應(yīng)度值的求解約束條件。

2.4 遺傳算子的設(shè)計(jì)

2.4.1 選擇算子

采用比例選擇算子，使個(gè)體按照與適應(yīng)度成正比的概率向下一代群體繁殖。具體方法為計(jì)算出每一個(gè)個(gè)體的適應(yīng)度值，然后計(jì)算該適應(yīng)度值占所有個(gè)體適應(yīng)度值的比例大小，比例大的被選中的概率高，比例低的被選中的概率小，經(jīng)過N次循環(huán)，就得到N個(gè)適應(yīng)度值相對(duì)比較高的航線個(gè)體。

2.4.2 交叉算子

采用重合點(diǎn)單點(diǎn)交叉的方法。具體方法為隨機(jī)選出兩條航線，從起始節(jié)點(diǎn)開始查找兩條航線的重合點(diǎn)（即網(wǎng)格序號(hào)相同點(diǎn)），然后對(duì)其進(jìn)行標(biāo)記，查找完畢后，任意選擇其中一個(gè)交叉點(diǎn)進(jìn)行交叉，即將該點(diǎn)之后的兩條航線部分互換。采用這種交叉方式優(yōu)點(diǎn)是便于操作，而且可以保證交叉后的兩條航線也是可行的。

2.4.3 變異算子

考慮采用插入和刪除的方法。插入操作的具體方法為：隨機(jī)選擇一條航線個(gè)體的網(wǎng)格節(jié)點(diǎn)，然后將網(wǎng)格節(jié)點(diǎn)周圍最近的一個(gè)可行網(wǎng)格點(diǎn)插入航線個(gè)體，比較新生成航線個(gè)體和未插入節(jié)點(diǎn)之前的航線個(gè)體的適應(yīng)度值大小，若適應(yīng)度值提高，則用新航線個(gè)體替代以前航線個(gè)體，若不提高或降低，則選擇以前航線個(gè)體。刪除操作的具體辦法為：查找航線個(gè)體中有沒有相同序號(hào)的網(wǎng)格節(jié)點(diǎn)，若有則將兩相同序號(hào)之間的冗余序號(hào)，連同兩相同節(jié)點(diǎn)中的一個(gè)一并去掉，得到一條網(wǎng)格節(jié)點(diǎn)變少，適應(yīng)度值提高的新航線個(gè)體。

2.5 終止條件的設(shè)定

遺傳操作在進(jìn)行跌代時(shí)的終止遵循以下規(guī)則：

1）強(qiáng)制終止。即設(shè)定最大進(jìn)化代數(shù)T，當(dāng)超過最大進(jìn)化代數(shù)時(shí)，迭代操作強(qiáng)制終止。

2）條件終止。即如果種群在進(jìn)化過程中每一代的最優(yōu)個(gè)體的適應(yīng)度值趨于一恒定值時(shí)，迭代終止。條件終止的公式為：

ε為一固定值。abs（）為取絕對(duì)值函數(shù)。

圖3 仿真實(shí)現(xiàn)流程圖

圖4 仿真驗(yàn)證示意圖

3 仿真實(shí)現(xiàn)

利用遺傳算法進(jìn)行航路規(guī)劃的編程仿真實(shí)現(xiàn)，編程時(shí)采用流程圖如圖4所示，根據(jù)流程圖所示過程，采用 VC＋＋6.0進(jìn)行編程實(shí)現(xiàn)［9，12］，遺傳參數(shù)分別為｛M，T，Pc，Pm｝＝｛20，100，0.6，0.01｝，仿真實(shí)現(xiàn)后的最優(yōu)航線如圖所示。

4 結(jié)語

通過仿真試驗(yàn)證明，采用簡(jiǎn)化的蟻群方法生成初始航線種群時(shí)，可以保證航線初始種群的可行性，提高了遺傳操作的效率，而且采用網(wǎng)格點(diǎn)序號(hào)的編碼方法，編碼方法簡(jiǎn)單，易于對(duì)其進(jìn)行遺傳操作，經(jīng)過一定代數(shù)的操作之后即可以得到滿足條件的航線。

［1］劉環(huán)宇，董受全.簡(jiǎn)約航路規(guī)劃方法［J］.火力與指揮控制，2008，33（7）：61～63

［2］鞏敦衛(wèi)，孫曉燕.協(xié)同進(jìn)化遺傳算法理論及應(yīng)用［M］.北京：科學(xué)出版社，2009：1～3

［3］王瑩，劉維亭.基于改進(jìn)蟻群算法的艦船航路規(guī)劃研究［J］.現(xiàn)代電子技術(shù)，2010，21（5）：186～196

［4］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，1999：157～159

［5］張高.基于蟻群算法的艦艇航線設(shè)計(jì)問題研究［D］.廣州：海軍兵種指揮學(xué)院，2009：34～36

［6］杜新海，等.航海學(xué)［M］.廣州：海潮出版社，1995：38～39

［7］汲萬峰，姜禮平，朱建沖.基于遺傳算法的航路規(guī)劃模型研究［J］.軍事運(yùn)籌與系統(tǒng)工程，2010，24（2）：52～55

［8］湯先拓.基于遺傳算法的艦艇航線自動(dòng)生成研究［J］.廣州：海軍兵種指揮學(xué)院，2009：41～42

［9］孫鑫，余安萍.VC＋＋深入詳解［M］.北京：電子工業(yè)出版社，2009：49～56

［10］熊瑜，饒躍東.基于改進(jìn)蟻群算法的無人飛行器航跡規(guī)劃［J］.計(jì)算機(jī)與數(shù)字工程，2010，38（7）

［11］宋久元，滕國(guó)庫(kù)，胡麗霞.路徑規(guī)劃算法的改進(jìn)及在車載導(dǎo)航中的應(yīng)用［J］.計(jì)算機(jī)與數(shù)字工程，2010，38（8）

［12］張?jiān)佬?VisualC＋＋程序設(shè)計(jì)［M］.蘇州：蘇州大學(xué)出版社，2002：102～104