基于改進(jìn)的隨機(jī)路徑圖及和聲算法的艦船航線規(guī)劃

呂進(jìn)鋒 馬建偉李曉靜

(1.河南科技大學(xué)信息工程學(xué)院，河南洛陽(yáng) 471000;2.中國(guó)空空導(dǎo)彈研究院，河南洛陽(yáng) 471009)

1 引言

海上航行通常具有航程較遠(yuǎn)、難以避免海上災(zāi)害性天氣等特點(diǎn).艦船在航行中與障礙物相撞引起的事故危害通常較大.海上障礙物主要包括靜態(tài)障礙物(如海岸、海島、暗礁、禁行海域)及動(dòng)態(tài)障礙物(如臺(tái)風(fēng)、氣旋、其他艦船).艦船航線規(guī)劃是指根據(jù)水文、氣象等信息，為艦船設(shè)計(jì)從指定位置到達(dá)目的地的可行路線的過(guò)程[1-2].

本文旨在利用現(xiàn)有的電子海圖系統(tǒng)，考慮艦船行駛期間障礙物躲避問(wèn)題，為艦船規(guī)劃航程最短的安全航線.類似于機(jī)器人路徑規(guī)劃，航線設(shè)計(jì)問(wèn)題本質(zhì)上為優(yōu)化問(wèn)題[3-6].常見(jiàn)的路徑規(guī)劃方法包括A*(A-star)算法、D*(Dijkstra)算法、人工勢(shì)場(chǎng)法及相應(yīng)的改進(jìn)算法;和聲算法、遺傳算法、蟻群算法、粒子群算法等群智能優(yōu)化算法.

利用A*，D*算法及其改進(jìn)算法進(jìn)行航線規(guī)劃的局限性在于:算法計(jì)算量隨著地圖柵格數(shù)的增多呈指數(shù)級(jí)增長(zhǎng)[7-8];其生成的路線轉(zhuǎn)向較頻繁且轉(zhuǎn)向角較大，不利于艦船安全行駛.人工勢(shì)場(chǎng)法的常見(jiàn)不足為當(dāng)艦船距障礙物較近而距終點(diǎn)較遠(yuǎn)時(shí)，可能由于斥力過(guò)大而遠(yuǎn)離終點(diǎn);或當(dāng)障礙物距終點(diǎn)較近時(shí)，艦船由于斥力大于引力而無(wú)法到達(dá)終點(diǎn)[9-11].利用蟻群[12-14]、粒子群[15-16]、人工蜂群[17-19]等群智能優(yōu)化算法進(jìn)行路徑規(guī)劃時(shí)，優(yōu)點(diǎn)在于算法結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)，不足為當(dāng)問(wèn)題復(fù)雜度較高、解空間為高維且呈現(xiàn)多峰形態(tài)時(shí)，種群易因快速收斂而陷入局部最優(yōu)解，所得路徑質(zhì)量無(wú)法保證.

和聲算法為模仿音樂(lè)家創(chuàng)作新樂(lè)曲提出的優(yōu)化算法[20-21].該算法利用隨機(jī)生成、選擇部分和聲、微調(diào)等策略對(duì)記憶庫(kù)中存儲(chǔ)的解進(jìn)行優(yōu)化.其所得解的質(zhì)量很大程度上依賴于記憶庫(kù)中初始解質(zhì)量.若初始解多樣性較好且質(zhì)量較高，則較容易獲得全局最優(yōu)解.遺傳算法為模擬自然界進(jìn)化過(guò)程而提出的一種優(yōu)化算法，其利用遺傳因子交叉、變異等操作搜索最優(yōu)解.交叉算子決定算法的全局搜索能力，變異算子決定局部搜索能力.

隨機(jī)路徑圖通過(guò)在地圖上設(shè)置節(jié)點(diǎn)并連接生成全局路徑，其所得路徑質(zhì)量很大程度上依賴于節(jié)點(diǎn)的數(shù)量及位置.該算法主要包含節(jié)點(diǎn)設(shè)置與查詢兩階段，其查詢階段通常具有一定的隨機(jī)性.多次重復(fù)該算法可得到多個(gè)不同的全局路徑.

對(duì)艦船航線規(guī)劃問(wèn)題，由于障礙物的運(yùn)動(dòng)特性，相應(yīng)的解空間為復(fù)雜的多峰形態(tài).利用常見(jiàn)優(yōu)化算法的局限性在于，由于參數(shù)輕微變動(dòng)導(dǎo)致備選解適應(yīng)度值變化較大，種群通常會(huì)越過(guò)全局最優(yōu)解.基于以上分析，針對(duì)艦船航行中障礙物躲避問(wèn)題，本文擬提出一種改進(jìn)的隨機(jī)路徑圖及和聲算法.該算法首先利用改進(jìn)的隨機(jī)路徑圖生成全局航線，通過(guò)多次重復(fù)得到多個(gè)質(zhì)量較高的初始航線;其次將其作為改進(jìn)和聲算法的輸入量，利用改進(jìn)的優(yōu)化策略對(duì)初始航線進(jìn)行交叉、消除節(jié)點(diǎn)、微調(diào)等操作;最終生成高質(zhì)量的全局航線.

2 問(wèn)題描述

海上航線在幾何上分為恒向線航線、大圓航線等.大圓航線為沿著經(jīng)過(guò)起始點(diǎn)與終點(diǎn)的地球大圓弧航行的航線，為地面兩點(diǎn)距離最短的航線.恒向線航線為沿著兩點(diǎn)間恒向線方向航行的航線，通常為非最短航線.大圓航線要求時(shí)刻改變艦船航向，在海上航行中難以實(shí)現(xiàn);因此常用多段恒向線航線代替大圓航線.如圖1(a)所示，PQ為大圓航線，可用多段恒向線航線PS，ST，TQ代替PQ，如圖1(b)所示.

圖1 大圓航線及恒向線航線Fig.1 A great circle route and its corresponding rhumb line route

對(duì)于多段恒向線組成的航線R，可用R=(P1，P2，···，Pn)表示，其中Pi為航線中的轉(zhuǎn)向點(diǎn)，即節(jié)點(diǎn).整個(gè)航線的航程為多段子航線航程之和.對(duì)一段恒向線航線(P1，P2)，起點(diǎn)與終點(diǎn)經(jīng)緯度分別為P1:(φ1，λ1)，P2:(φ2，λ2).該恒向線航線航程S、航向C可通過(guò)中分緯法求出:

其中:Dφ，Dλ分別為經(jīng)差與緯差，φm=對(duì)于航線R，其航程f(R)為

本文規(guī)定，在不與障礙物相遇的前提下，航程是衡量航線優(yōu)劣的唯一指標(biāo).本文擬利用群智能優(yōu)化算法，為艦船進(jìn)行航線規(guī)劃，生成可行的由多段恒向線航線組成的全局航線，確定航線節(jié)點(diǎn)位置、航程及航向.

3 改進(jìn)的隨機(jī)路徑圖及和聲算法

3.1 基于改進(jìn)隨機(jī)路徑圖的初始航線生成

隨機(jī)路徑圖(probabilistic roadmap，PRM)通過(guò)在地圖上設(shè)置節(jié)點(diǎn)并連接最終生成全局路徑，從而構(gòu)建路徑網(wǎng)絡(luò)圖R=(N，E);N為隨機(jī)點(diǎn)集，E為任意兩點(diǎn)之間的可行路徑集.其在學(xué)習(xí)階段隨機(jī)生成多個(gè)節(jié)點(diǎn)并連接，在查詢階段則從路徑網(wǎng)絡(luò)中選擇多個(gè)子路徑，最終獲得連接起點(diǎn)與終點(diǎn)的全局路徑.考慮到若PRM在學(xué)習(xí)階段生成的節(jié)點(diǎn)數(shù)較少，則在查詢階段有可能無(wú)法獲得全局路徑;若構(gòu)造的路徑網(wǎng)絡(luò)圖較復(fù)雜，在查詢階段得到的全局路徑質(zhì)量難以保證，見(jiàn)圖2.

圖2 PRM生成的路徑網(wǎng)絡(luò)圖及全局路徑Fig.2 The path network map and global route generated by PRM

本文采用改進(jìn)的隨機(jī)路徑圖(improved probabilistic roadmap，IPRM)為艦船規(guī)劃初始全局航線.對(duì)航線規(guī)劃問(wèn)題，若連接起點(diǎn)與終點(diǎn)，以該直線為中心線向周圍區(qū)域膨脹;則對(duì)任一全局航線，其子航線距離該中心線越近，可認(rèn)為該航線具有較短航程的可能性越大.考慮到障礙物躲避問(wèn)題，IPRM將起點(diǎn)與終點(diǎn)連線、與該連線距離較近的障礙物的邊緣區(qū)域作為關(guān)鍵區(qū)域，進(jìn)行節(jié)點(diǎn)擴(kuò)充;基于此可利用較少節(jié)點(diǎn)生成完備的網(wǎng)絡(luò)路徑圖.考慮障礙物及艦船的運(yùn)動(dòng)特性，IPRM分階段查詢節(jié)點(diǎn)，可有效減少需查詢節(jié)點(diǎn)數(shù)量、減少計(jì)算量、獲得可行的全局航線.

航線規(guī)劃任務(wù)中若存在動(dòng)態(tài)障礙物躲避問(wèn)題，同一航線在不同時(shí)間的可行性通常有較大差異.圖3中，海圖每12 h進(jìn)行一次更新.

圖3 不同時(shí)段海圖示例Fig.3 Nautical charts of different periods

根據(jù)艦船航速，本文首先計(jì)算艦船在一定階段相應(yīng)海圖上的行駛范圍，其次在該范圍內(nèi)設(shè)置節(jié)點(diǎn).考慮到節(jié)點(diǎn)數(shù)量及位置在很大程度上決定了全局航線的質(zhì)量;因此在學(xué)習(xí)階段，除隨機(jī)生成節(jié)點(diǎn)外，本文在關(guān)鍵區(qū)域進(jìn)行節(jié)點(diǎn)擴(kuò)充，即最佳路線可能經(jīng)過(guò)的區(qū)域.具體策略為:連接起點(diǎn)與終點(diǎn)，在該直線上等間隔取點(diǎn)作為擴(kuò)充節(jié)點(diǎn);以該直線上的點(diǎn)為圓心，以D1為直徑作圓，對(duì)與該圓相交的障礙物，圍繞其邊緣取點(diǎn)進(jìn)行節(jié)點(diǎn)擴(kuò)充.在連接節(jié)點(diǎn)生成路徑網(wǎng)絡(luò)圖時(shí)，對(duì)每個(gè)節(jié)點(diǎn)，選擇與其最近鄰的若干個(gè)節(jié)點(diǎn)進(jìn)行連接，生成局部路徑.相較隨機(jī)生成的節(jié)點(diǎn)，對(duì)關(guān)鍵區(qū)域選擇較多節(jié)點(diǎn)與其連接，增大其在查詢階段被選擇的概率;基于此生成路徑網(wǎng)絡(luò)圖.重復(fù)此過(guò)程，獲得每一階段相應(yīng)的路徑網(wǎng)絡(luò)圖.如對(duì)上海-馬尼拉的航線規(guī)劃任務(wù)，大型集裝箱船只行駛速度為36～52 km/h，取中間值為估計(jì)航速，則其在不同時(shí)段可選擇節(jié)點(diǎn)如圖4所示.在獲得路徑網(wǎng)絡(luò)圖的基礎(chǔ)上，從第1階段開(kāi)始，依次查詢路徑網(wǎng)絡(luò)圖，選擇節(jié)點(diǎn)及相應(yīng)的路徑進(jìn)行連接，直至生成全局航線，對(duì)航線可行性進(jìn)行進(jìn)一步檢驗(yàn).分階段設(shè)置與選擇節(jié)點(diǎn)可有效減少計(jì)算量.

圖4 改進(jìn)的隨機(jī)路徑圖節(jié)點(diǎn)選擇范圍Fig.4 The regional scope of nodes in different periods

3.2 基于改進(jìn)和聲搜索的航線優(yōu)化

和聲搜索算法(harmony search，HS)首先隨機(jī)生成初始解保存在記憶庫(kù)中，其次利用隨機(jī)生成、組合、微調(diào)等策略對(duì)初始解進(jìn)行優(yōu)化.其初始解對(duì)最終所得解質(zhì)量影響較大.航線規(guī)劃問(wèn)題相應(yīng)解空間為復(fù)雜的多峰形態(tài)，直接利用HS優(yōu)化策略任意改變航線節(jié)點(diǎn)可能導(dǎo)致新航線不可行.較隨機(jī)生成的航線，利用IPRM生成的航線質(zhì)量較高.為有效提高初始航線質(zhì)量，本文利用改進(jìn)的和聲搜索算法(improved harmony search，IHS)對(duì)其進(jìn)行優(yōu)化.IHS的初始解為IPRM生成的全局航線.IHS引入遺傳算法中交叉策略，結(jié)合節(jié)點(diǎn)消除與微調(diào)策略對(duì)航線進(jìn)行優(yōu)化.為保證新生成航線的可行性，IHS首先檢測(cè)其是否滿足相應(yīng)的更新條件.在此基礎(chǔ)上選擇相應(yīng)的優(yōu)化策略生成新航線.IHS具體優(yōu)化策略如下.

對(duì)解空間為n 維的優(yōu)化問(wèn)題，任一備選解可用X={x1，x2，···，xn}表示.由多個(gè)備選航線構(gòu)成的記憶庫(kù)HM可表示為

其中:Xi為由IPRM生成的全局航線，1 ≤i ≤HMS，HMS表示記憶庫(kù)中航線數(shù)量;f為評(píng)價(jià)航線質(zhì)量的適應(yīng)度函數(shù)，如式(3)所示.

IHS針對(duì)記憶庫(kù)中的備選航線，通過(guò)交叉航線、消除節(jié)點(diǎn)、微調(diào)節(jié)點(diǎn)位置對(duì)其進(jìn)行優(yōu)化.IHS首先從記憶庫(kù)中選擇兩條初始航線，若其滿足交叉要求，則通過(guò)交叉生成兩條新航線，即:若兩條航線存在交點(diǎn)，或者在海圖區(qū)域中存在直徑小于D2、不包含障礙物的圓，且兩條航線同時(shí)穿過(guò)該圓，此時(shí)可對(duì)兩條航線進(jìn)行交叉操作.若有路徑X1=其交點(diǎn)為pc，交叉操作后兩條新航線分別為若兩條航線不存在交點(diǎn)，但在X1上存在點(diǎn)p1:(φ1，λ1)，在X2上存在點(diǎn)p2:(φ2，λ2)，p1和p2同時(shí)位于直徑小于D2、不包含障礙物的圓內(nèi)，則X1和X2在點(diǎn)pm:(φm，λm)處進(jìn)行交叉，生成新路徑φ2)/2，λm=(λ1+λ2)/2.

對(duì)新生成的兩條航線，若其可行，則將其與原航線進(jìn)行比較，選擇質(zhì)量較高的兩條航線保存在記憶庫(kù)中，并按以下策略進(jìn)行節(jié)點(diǎn)消除及微調(diào)操作:生成隨機(jī)數(shù)r，r在0和1之間均勻分布;若r ＜PAR，則嘗試消除航線中的節(jié)點(diǎn)，PAR 為消除節(jié)點(diǎn)的概率.對(duì)航線若其節(jié)點(diǎn)之間存在不與障礙物相交的子路徑，則消除原航線中之間的節(jié)點(diǎn);否則對(duì)節(jié)點(diǎn)位置按式(5)-(6)進(jìn)行微調(diào)，得到新的航線:

其中:BW為節(jié)點(diǎn)位置微調(diào)幅度;r1，r2為絕對(duì)值小于BW的隨機(jī)數(shù);xi1，xi2為節(jié)點(diǎn)xi的經(jīng)、緯度.考慮到能消除節(jié)點(diǎn)可有效減小航程，但其為不可逆操作，相對(duì)地微調(diào)策略對(duì)航線的改動(dòng)較小;因此，本文中PAR 取值較小.

對(duì)新生成的航線Xnew，若其可行，將其與記憶庫(kù)中最差航線Xworst進(jìn)行比較:若f(Xnew)＜f(Xworst)，則將Xnew代替Xworst;否則，不改變記憶庫(kù).對(duì)優(yōu)化過(guò)程中生成的不可行航線，直接舍棄，記憶庫(kù)保留原航線.

3.3 改進(jìn)的隨機(jī)路徑圖及和聲算法步驟

綜上所述，利用改進(jìn)的隨機(jī)路徑圖及和聲算法進(jìn)行航線規(guī)劃的步驟為

步驟1根據(jù)海圖更新頻率及艦船航速，確定不同階段海圖上節(jié)點(diǎn)范圍;

步驟2按階段在海圖上相應(yīng)區(qū)域隨機(jī)生成節(jié)點(diǎn)，并在關(guān)鍵區(qū)域進(jìn)行節(jié)點(diǎn)擴(kuò)充;

步驟3有側(cè)重地選擇節(jié)點(diǎn)并連接，生成各個(gè)階段對(duì)應(yīng)的路徑網(wǎng)絡(luò)圖;

步驟4按階段查詢路徑網(wǎng)絡(luò)圖進(jìn)行路徑連接，生成初始全局航線;

步驟5重復(fù)步驟2-4生成多條全局航線保存在記憶庫(kù)中，并計(jì)算其適應(yīng)度值;

步驟6隨機(jī)選擇兩條航線，若滿足相應(yīng)要求，則進(jìn)行交叉操作，比較新航線與原航線的適應(yīng)度值，選擇質(zhì)量較高的兩條航線保存在記憶庫(kù)中;若新航線不可行，則舍棄，記憶庫(kù)中保留原航線;

步驟7生成隨機(jī)數(shù)，嘗試消除航線中的節(jié)點(diǎn)、調(diào)整航線節(jié)點(diǎn)位置，將生成的新航線與記憶庫(kù)中最差航線進(jìn)行比較，選擇質(zhì)量較高的航線保存在記憶庫(kù)中;若新航線不可行，則舍棄，記憶庫(kù)保留原航線;

步驟8重復(fù)步驟6-7直至算法結(jié)束.

本文算法在可行的初始航線的基礎(chǔ)上進(jìn)行優(yōu)化，改進(jìn)的和聲搜索策略能有效保證新生成航線的可行性，對(duì)解空間進(jìn)行有效搜索.

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證所提算法的有效性，本文利用多個(gè)艦船航線規(guī)劃任務(wù)進(jìn)行實(shí)驗(yàn)驗(yàn)證.任務(wù)1中艦船起點(diǎn)為上海，終點(diǎn)為馬尼拉.艦船行駛過(guò)程中無(wú)臺(tái)風(fēng)、氣旋等運(yùn)動(dòng)障礙物出現(xiàn).任務(wù)2，3均存在臺(tái)風(fēng)、氣旋等障礙，海圖每12小時(shí)進(jìn)行更新.任務(wù)2中艦船起點(diǎn)為上海，終點(diǎn)為馬尼拉，包含8個(gè)不同時(shí)段海圖信息.任務(wù)3起點(diǎn)為上海，終點(diǎn)為胡志明市，包含12個(gè)不同時(shí)段海圖信息.

本文將所提算法(IPRM-IHS)與和聲搜索算法(HS)、粒子群優(yōu)化算法(particle swarm optimization，PSO)、蟻群算法(ant colony algorithm，ACA)、人工蜂群算法(artificial bee colony algorithm，ABC)等進(jìn)行比較.實(shí)驗(yàn)環(huán)境為Windows 10 64 bit，CPU 為Intel Core 2.80 GHz，內(nèi)存為4.0 GB，MATLAB 2014b.實(shí)驗(yàn)輸入為艦船航速、起點(diǎn)與終點(diǎn)、海圖信息等;輸出為相應(yīng)航線信息.實(shí)驗(yàn)中，種群規(guī)模均為30，迭代次數(shù)上限為1000.對(duì)IPRM-IHS，PAR決定了節(jié)點(diǎn)被消除的概率;相對(duì)于微調(diào)節(jié)點(diǎn)位置，消除節(jié)點(diǎn)對(duì)航線的改動(dòng)較大.考慮到迭代次數(shù)上限較大及節(jié)點(diǎn)消除操作不可逆，PAR取值不應(yīng)過(guò)大.本文中PAR=0.2，即在每次迭代過(guò)程中，對(duì)任意航線，消除其節(jié)點(diǎn)的概率不大于20%.BW決定節(jié)點(diǎn)經(jīng)緯度變化范圍，考慮節(jié)點(diǎn)位置的較大改變可能導(dǎo)致航線不可行;因此BW應(yīng)取較小值.本文中BW=0.005，即節(jié)點(diǎn)位置微調(diào)上限約為0.6 km.HS 中，HMCR=0.9，PAR=0.5，BW=0.005;PSO中，慣性常數(shù)ω=0.7，c1=c2=2;ACA中，啟發(fā)式因子重要程度β=7，信息素重要程度α=0.0001，信息素?fù)]發(fā)系數(shù)c=0.5;ABC中，φ為[-1，1]之間的隨機(jī)數(shù).若連續(xù)迭代200次仍未有更優(yōu)航線出現(xiàn)，則算法結(jié)束.

對(duì)每個(gè)航線規(guī)劃任務(wù)，每個(gè)算法重復(fù)運(yùn)行30次，相應(yīng)航線航程的均值及歸一化方差如表1所示.圖5-7分別為IPRM-IHS針對(duì)任務(wù)1-3生成的路徑網(wǎng)絡(luò)圖及全局路徑.

表1 實(shí)驗(yàn)結(jié)果:IPRM-IHS與啟發(fā)式優(yōu)化算法對(duì)比Table 1 Experimental results:the comparison between IPRM-IHS and other heuristic algorithms

從表1中可知，對(duì)3個(gè)航線規(guī)劃任務(wù)，IPRM-IHS生成的航線航程均值及歸一化方差均為最小;驗(yàn)證了相較其余幾種算法，IPRM-IHS在航線規(guī)劃問(wèn)題上的適用性.在其余幾種優(yōu)化算法中，ACA表現(xiàn)略優(yōu)于ABC，HS和PSO所得航線質(zhì)量較差.在實(shí)驗(yàn)中發(fā)現(xiàn)，對(duì)初始航線進(jìn)行更新優(yōu)化時(shí)，HS通過(guò)隨機(jī)生成航線中節(jié)點(diǎn)位置，PSO利用向更優(yōu)航線靠近的策略更改航線中節(jié)點(diǎn)位置，都可能導(dǎo)致新生成的航線與障礙物相遇而不可行，即搜索無(wú)效;這是降低算法有效性的重要原因.相應(yīng)的，ACA，ABC圍繞可行航線進(jìn)行優(yōu)化，也會(huì)產(chǎn)生新生成的航線與障礙物相遇的情況，但比例相對(duì)較小.

圖5 任務(wù)1路徑網(wǎng)絡(luò)圖及全局路徑Fig.5 The route map and global route for Task 1

圖6 任務(wù)2路徑網(wǎng)絡(luò)圖及全局路徑Fig.6 The route map and global route for Task 2

統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，IPRM-IHS在優(yōu)化過(guò)程中生成不可行航線26次，HS為403次，PSO為352次，ABC為189次，即本文采用的改進(jìn)和聲算法在航線優(yōu)化問(wèn)題上效率遠(yuǎn)高于其余幾種對(duì)比算法.本文提出的優(yōu)化策略較好保證新生成航線的可行性.

IPRM-IHS穩(wěn)定較好，即相應(yīng)的航線航程方差較小.PSO，HS無(wú)法保證新生成航線的可行性，算法穩(wěn)定性相對(duì)較差，相應(yīng)的方差較大.從表1中可知，隨問(wèn)題復(fù)雜度上升，算法穩(wěn)定性均有所下降，IPRM-IHS所得歸一化方差變化相對(duì)較小;驗(yàn)證在存在動(dòng)態(tài)障礙物的復(fù)雜海況下，IPRM-IHS更具優(yōu)越性.

為分析所提算法效率，表2給出每個(gè)算法平均運(yùn)行時(shí)間.對(duì)任務(wù)2、任務(wù)3，圖8給出隨機(jī)抽取的一組算法收斂曲線.

圖7 任務(wù)3路徑網(wǎng)絡(luò)圖及全局路徑Fig.7 The route map and global route for Task 3

表2 IPRM-IHS與啟發(fā)式優(yōu)化算法運(yùn)行時(shí)間Table 2 The running time of IPRM-IHS and other heuristic algorithms

從表2可知，HS的運(yùn)行時(shí)間最短，PSO的運(yùn)行時(shí)間最長(zhǎng).IPRM-IHS的效率與HS相當(dāng).從圖8中同時(shí)可知，IPRM-IHS的初始航線具有較好的質(zhì)量，同時(shí)其收斂速度最快.IPRM-IHS在利用種群進(jìn)行優(yōu)化前首先利用改進(jìn)的PRM生成可行航線，該過(guò)程耗費(fèi)一定時(shí)間.

圖8 任務(wù)2與任務(wù)3的收斂曲線Fig.8 The convergence curves for Task 2 and Task 3

所有算法的運(yùn)行時(shí)間隨著問(wèn)題復(fù)雜度的上升而增長(zhǎng).對(duì)涉及動(dòng)態(tài)障礙物躲避的航線規(guī)劃問(wèn)題，需處理的海圖信息較多，導(dǎo)致算法運(yùn)行時(shí)間增長(zhǎng).

為進(jìn)一步驗(yàn)證IPRM-IHS的有效性，本文將其與改進(jìn)的PRM 算法(LPRM，GSPRM，VPRM)進(jìn)行對(duì)比[22-24]，所得實(shí)驗(yàn)結(jié)果如表3所示.

表3 IPRM-IHS與LPRM，GSPRM，VPRM對(duì)比Table 3 Comparison between IPRM-HIS，LPRM，GSPRM and VPRM

分析表3 可知，IPRM-IHS 相較LPRM，GSPRM，VPRM在航線規(guī)劃問(wèn)題上具有更好的適用性.LPRM利用貪婪搜索的策略，在已有路徑網(wǎng)絡(luò)圖的基礎(chǔ)上可查找出連接起點(diǎn)與終點(diǎn)的最短路徑.其所得航線質(zhì)量嚴(yán)重依賴于節(jié)點(diǎn)的分布.GSPRM引入高斯濾波函數(shù)，增大靠近障礙物的節(jié)點(diǎn)被存儲(chǔ)在路徑網(wǎng)絡(luò)圖中的概率.該策略可有效增大生成可行路線的概率;但在障礙物較為分散且距終點(diǎn)相對(duì)較遠(yuǎn)時(shí)，有可能降低全局航線質(zhì)量.VPRM通過(guò)設(shè)置節(jié)點(diǎn)，完成對(duì)整個(gè)地圖的可視性覆蓋;但對(duì)于動(dòng)態(tài)障礙物躲避問(wèn)題，其原先有效可視范圍會(huì)發(fā)生相應(yīng)變化，在一定程度增大獲得高質(zhì)量全局航線的難度.

為分別驗(yàn)證PRM改進(jìn)策略與和聲改進(jìn)策略的有效性，本文將IPRM 與PRM，IHS 與HS 進(jìn)行比較，其中:IP RM與PRM利用相同數(shù)量的節(jié)點(diǎn)構(gòu)造路徑網(wǎng)絡(luò)圖;IHS與HS的記憶庫(kù)初始解均為IPRM生成的多個(gè)備選航線，實(shí)驗(yàn)結(jié)果如表4所示.

表4 實(shí)驗(yàn)結(jié)果:IPRM與PRM，IHS與HS對(duì)比Table 4 Experimental results:the comparison between IPRM and PRM，the comparison between IHS and HS

分析表4可知，IPRM與PRM相比，獲得的航線質(zhì)量更高.IPRM的主要優(yōu)勢(shì)體現(xiàn)在:其按階段查詢節(jié)點(diǎn)并連接;在構(gòu)造全局路徑時(shí)選擇的節(jié)點(diǎn)數(shù)量較少，且其節(jié)點(diǎn)大部分為圍繞障礙物分布或位于連接起點(diǎn)與終點(diǎn)的連線區(qū)域附近;相較PRM，其構(gòu)造的路徑網(wǎng)絡(luò)圖更加完備，更有可能生成高質(zhì)量的全局航線.分析實(shí)驗(yàn)結(jié)果同時(shí)可知，將IPRM生成的全局航線作為IHS及HS的初始解，IHS能更加有效地對(duì)初始解進(jìn)行優(yōu)化.HS利用隨機(jī)生成、從記憶庫(kù)中隨機(jī)選擇備選解進(jìn)行改進(jìn)的策略易造成新生成航線不可行，造成搜索資源的浪費(fèi).考慮初始解已有較好的質(zhì)量及多樣性，IHS僅對(duì)滿足限制條件的航線進(jìn)行優(yōu)化，該策略有效避免種群在解空間中無(wú)效搜索.

為驗(yàn)證IPRM與IHS結(jié)合策略的有效性，本文將IP RM與ACA，PSO分別進(jìn)行組合，將其作為對(duì)比算法，實(shí)驗(yàn)結(jié)果如表5所示.

表5 實(shí)驗(yàn)結(jié)果:IPRM-IHS與IPRM-ACA，IPRM-PSO對(duì)比Table 5 Experimental results:the comparison between IPRM-IHS，IPRM-ACA and IPRM-PSO

分析表5 可知，IPRM-ACA，IPRM-PSO 較ACA，PSO所得航線質(zhì)量略有提高.IPRM算法生成的航線相較隨機(jī)生成的航線具有更高的質(zhì)量.ACA，PSO均圍繞解空間中較高質(zhì)量的解展開(kāi)搜索.由于航線規(guī)劃問(wèn)題中障礙物為運(yùn)動(dòng)狀態(tài)，相應(yīng)的解空間為復(fù)雜的多峰形態(tài)，僅改變ACA，PSO的初始解而采用同樣的優(yōu)化策略，對(duì)航線進(jìn)行有效優(yōu)化的難度較大.

綜上可知，本文利用IPRM-IHS為艦船進(jìn)行航線規(guī)劃，相較其余幾種對(duì)比算法具有明顯的優(yōu)越性.IPRM-IHS的節(jié)點(diǎn)設(shè)置與查詢策略，可有效減少計(jì)算量，增大生成高質(zhì)量全局航線的概率.本文利用隨機(jī)路徑圖查詢階段的隨機(jī)性，多次重復(fù)隨機(jī)路徑圖生成多條初始全局航線，并將其作為IHS的輸入量，設(shè)定優(yōu)化條件使種群對(duì)解空間進(jìn)行有效搜索.實(shí)驗(yàn)結(jié)果驗(yàn)證該策略的可靠性與穩(wěn)定性.

5 結(jié)論

針對(duì)艦船航線規(guī)劃問(wèn)題，本文提出一種改進(jìn)的隨機(jī)路徑圖及和聲算法.該算法首先利用改進(jìn)的隨機(jī)路徑圖生成多條可行的初始航線，隨后利用改進(jìn)的和聲搜索算法，通過(guò)交叉、節(jié)點(diǎn)消除、微調(diào)策略對(duì)航線進(jìn)行優(yōu)化，最終獲得全局航線.實(shí)驗(yàn)結(jié)果表明，相較對(duì)比算法，本文所提算法生成的航線質(zhì)量更高，算法的穩(wěn)定性更好.進(jìn)一步提高算法效率是本文下一步工作的重點(diǎn).