田 鶴 李啟華 孟一鳴

（海軍兵種指揮學院 廣州 510430）

1 引言

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

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

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

2.1 初始群體的產生方法

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

1）前行網格點必須是可行點；

2）搜索時避開已選擇的網格點；

3）搜索時如果下一網格點均不滿足上述兩條件，則刪除該點，從上一點開始重新選擇。

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

圖1 初始航線生成示意圖

圖2 網格編碼示意圖

2.2 種群的編碼方法

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

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

struct GridNode／／每個節(jié)點的數(shù)據結構包括該節(jié)點x，y坐標該節(jié)點的編號o

航線個體的數(shù)據結構表示為：struct antindividual｛

double value；／／目標值

double fitness；／／適應度值

int grid＿n；／／對應的航線網格節(jié)點數(shù)

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

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

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

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

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

式中N為航路段數(shù)，n為網格節(jié)點數(shù)，li為第i航路段的長度，x，y分別為航路段中網格節(jié)點所對應的直角坐標。

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

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

1）各種威脅概率模型

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

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

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

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

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

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

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

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

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

2.3.3 目標函數(shù)模型

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

代入各自的計算公式為：

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

航線代價函數(shù)與適應度函數(shù)的轉化結合遺傳算法對適應度函數(shù)的約束條件，可以采用以下形式來實現(xiàn)航線目標代價函數(shù)與航線適應度函數(shù)之間的轉換［8］：

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

2.4 遺傳算子的設計

2.4.1 選擇算子

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

2.4.2 交叉算子

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

2.4.3 變異算子

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

2.5 終止條件的設定

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

1）強制終止。即設定最大進化代數(shù)T，當超過最大進化代數(shù)時，迭代操作強制終止。

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

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

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

圖4 仿真驗證示意圖

3 仿真實現(xiàn)

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

4 結語

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

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

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

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

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

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

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

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

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

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

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

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

［12］張岳新.VisualC＋＋程序設計［M］.蘇州：蘇州大學出版社，2002：102～104