航線動態優化算法在海上搜救中的應用

聶皓冰，王勝正，胡志武，施朝健

(上海海事大學商船學院，上海 201306)

0 引言

近年來，我國海上運輸船舶數量持續增長，各類涉海、用海活動越來越多，規模越來越大，使得我國海上搜救任務日益繁重.這是一項復雜而艱巨的任務，海員們通常需要面對許多復雜的氣象和海況.海上搜救的成功與否取決于整個搜救計劃的科學決策:快速確定和尋找失事船舶和救生艇筏，確定搜尋范圍是整個搜救計劃的基礎;快速抵達搜救區域是救助的關鍵.在過去幾年里，國內外已經提出許多輔助搜救的決策系統，BREIVIK等［1]提出搜救目標隨機漂移軌跡模型，利用蒙特卡洛方法對漂移模型中的一些不確定因素進行估計，以獲得魯棒的漂浮物軌跡預測模型，并成功應用于北海區域.HONG等［2]提出基于馬爾科夫鏈的目標搜尋方法，以提高目標搜索的準確率.另外，國內對搜尋區域確定方法和海上漂浮物的漂流軌跡預測也有較深入的研究.［3-6]

綜上所述，現有的搜救輔助決策系統主要集中在對預測搜尋區域的研究，很少考慮搜救船舶的操縱與航行.但是在實際搜救過程中，由于時間非常緊迫，不僅需要搜救決策系統在搜救開始階段用最短的時間制訂出安全、準確、快速的搜救航線，而且隨著搜救目標的漂移，希望系統能實時動態地規劃最新航線，只有這樣才能保證搜救人員快速抵達搜救區域，從而大大減少船員定位、制訂航線計劃的工作負擔.

國內外已經對自動航線設計方法進行初步研究和探討，如基于改進的Dijkstra最短路徑算法的最佳航線設計［7]，基于動態網格模型的航線自動生成［8]，基于蟻群算法的航線自動生成［9]，以及基于航路二叉樹的航線自動生成［10].但是，這些方法主要集中在最短路徑的搜索，既沒有考慮氣象環境的變化，也沒有考慮目的地的變化，因而只能適用于固定航線的船舶，無法適用于搜救船舶.因此，為了在各種復雜氣象環境下實時自動設計最優化的搜救航線，本文提出基于電子海圖空間數據快速檢索與最優路徑規劃算法的搜救航線實時動態優化方法.即首先用電子海圖數據的空間和特征屬性建立改進的空間索引樹，實現海圖數據信息的快速檢索;然后利用礙航物生成空間連通矩陣，并提出改進的蟻群算法計算最優航線，試驗結果表明，該方法計算效率高、能夠滿足實時性要求，算法穩定性好、能夠適應各種海洋環境;最后，將其成功應用于某海域的搜救輔助決策系統中.

1 搜救航線動態優化算法

1.1 電子海圖空間數據結構

為了實現對海圖信息的快速查詢和檢索，利用標準電子海圖數據(S57格式)中的每個特征元(具有空間屬性和特征屬性)建立基于R-樹的空間索引樹.圖1為基于R-樹的空間索引樹的結構圖，圖中的矩形框表示每個海圖信息特征元的最小包圍框.

圖1 基于R-樹的海圖空間數據索引結構圖

1.2 航線設計規則和航區連通矩陣生成算法

航線設計的基本原則是充分排除礙航物，在遵守海上通航要求的前提下，獲取路徑最短、能耗最少和效率最高的航線.影響海上通航的基本要素通常有島嶼、初露水面的礁石群、海上油田、燈標、樁標船等.其他礙航區還包括軍事演習區、低于船舶凈空高度的空中電纜和橋梁、垃圾傾倒區、拋泥區、彈藥傾倒區、雷區等.除此之外還必須遵守船舶定線制要求，將礙航區處理成符合船舶定線規則的區域.

利用R-樹空間數據索引結構檢索海圖信息特征屬性，獲取航區礙航物信息，并確定礙航物邊界，以邊界轉角點為頂點組成連通矩陣G.礙航物邊界的選取原則是盡量減少頂點數量并將障礙物或礙航區完全包圍，形成獨立的凸多邊形，這主要考慮到計算連通圖復雜性問題和實際運用問題.

i=1，2，…，n，j=i，i+1，…，n，n 為邊界頂點數

式中:

頂點A，B可見，定義為:除連接A，B兩點的線段以外再無任何由其他頂點連接成的線段與A，B之間的線段相交.

因此，可以根據頂點互見定義，利用下述算法I和算法II計算航區連通矩陣.

算法I:頂點互見算法

(1)設由頂點Vi和Vj決定的直線段方程被定義為 Eij(x，y)=0，x∈(xi，xj)，由不包含頂點 Vi和Vj的任意兩個頂點Vk，Vm確定的直線段方程被定義為 Ekm(x，y)=0，x∈(xk，xm).計算如下方程組:

k=1，2，…，n;m=k，k+1，…，n

(2)如果上述方程組有解，則表示頂點Vi和Vj不互見，即gij=0，否則gij=1.

算法II:連通矩陣算法

輸入為礙航物凸多邊形集合

輸出為連通矩陣G

提取所有凸多邊形頂點組成初始連通矩陣(零矩陣)

For each Vi∈初始連通矩陣

For another Vj≠Vi＆ Vj∈初始連通矩陣

If Vi，Vj∈相同凸多邊形

/*凸多邊形邊界不能作為備選航線，且不相鄰頂點必不可見*/

Then continue

Else

判斷頂點互見(算法I);

End if

End for

End for

1.3 基本蟻群算法

蟻群算法的基本思想是借助螞蟻在尋找食物過程中的所經路徑上留下的一種信息素(pheromone)，其濃度的高低影響后來者的尋找過程.螞蟻總是朝著信息素濃度較高的位置移動，逐漸形成信息素的正反饋.螞蟻通過信息素這種物質進行相互的信息傳遞，體現出螞蟻之間的組織協調性.圖2為蟻群算法遍歷的大致過程.

圖2 蟻群算法搜索過程模擬圖(圖片引自Wikipedia)

由于螞蟻之間互相合作的這種群體智能效應，蟻群算法被廣泛應用于各類搜索最優解算法［11-14]中，基本蟻群算法中螞蟻以概率Pij由頂點i向頂點j前進，計算公式如下:

式(1)和(2)中:τij是頂點i與頂點j路徑上信息素濃度，隨著算法的運行動態調整;Ni={Vj|g(i，j)=1;j=1，2，…，n}表示由 i頂點出發時可見頂點集合;α是信息素啟發因子，表示信息素濃度對下一頂點取舍的重要程度;ηij為啟發函數值，體現從頂點i向頂點 j移動的期望值，一般取 ηij=1/Wij，Wij是＜i，j＞路徑的權重;β與α有類似之處，差別在于β表示的是啟發函數的重要性.

蟻群每完成一次搜索，需要進行信息素更新，更新規則如下:

ρ是信息素揮發因數，(1-ρ)表示信息素殘留因數，0＜ρ＜1;Δτ是信息素增量.

另外，螞蟻具有記憶性，算法為每只螞蟻建立禁忌表TabuList(k)，記錄螞蟻k走過的路徑，防止其“繞圈子”.

螞蟻借助信息素作為媒體，根據不同的需求，相互協作、共同完成復雜的搜索任務，獲得所求問題的最優解.

以上為蟻群算法的基本思想.

1.4 改進的蟻群算法

基本蟻群算法在尋優過程中存在搜索時間過長、容易停滯、易收斂于局部最優等缺點，而且人工螞蟻進行路徑搜索具有經驗型和直覺性［15]，為了解決快速搜索全局最優路徑問題，針對蟻群算法信息素更新規則進行改進.其基本思想是:對每一輪迭代中所得到的路徑長度進行排序，找出當前最優路徑，并且加強此路徑上的信息素，以吸引更多螞蟻.具體實施步驟:

(1)將當前所有搜索到的路徑按長度L排序得到L1(t)≤L2(t)≤…≤Lr(t)≤…≤Lw(t);

(2)用與長度值成反比的權值加強相應路徑上的信息素濃度增量.

算法加速之后有可能導致收斂至局部最優解，是因為局部路徑中信息素濃度上升快且未控制其增長.因此，為了使螞蟻在全局范圍內搜索到最短路徑，應該對信息素的更新加以控制，使其在一定區間內變化.綜上所述，蟻群算法信息素更新規則為

1.5 搜救航線動態優化算法

綜合連通矩陣G生成算法和改進后的蟻群算法，結合公式(1)，(2)，(4)～(6)，得出如下搜救航線動態優化算法流程.

步驟1輸入礙航區信息，計算連通矩陣G.

步驟2初始化搜索算法.

步驟3派出m只螞蟻外出搜索，記錄每只螞蟻的搜索路徑及路徑長度:

步驟3-1根據連通矩陣G收集螞蟻k當前可見頂點集 Ni={Vj|g(i，j)=1;j=1，2，…，n};

步驟3-2螞蟻k(k＜m)以概率Pij向前搜索，見式(1)和(2)，更新禁忌表TabuList(k);

步驟3-3若找到終點，記錄螞蟻k所經路徑及路徑長度，w+=1;否則轉步驟3-1.

步驟4將w條路徑按長度排序，更新各路徑信息素分布，見式(4)～(6).

步驟5如果當前最短路徑長度小于全局最短路徑長度，用當前解替代全局解.

步驟6若達到最大迭代次數，停止計算;否則，轉步驟3.

2 試驗結果及算法評估

為驗證算法的有效性和可靠性，設計以標準電子海圖為平臺的自動航線設計系統，對3種航行環境進行試驗，并對計算效率和穩定性進行評估.

系統測試環境:普通計算機，其配置為Intel i5 2.27GHz雙核 CPU，3G內存，Win 7 32位操作系統，Visual Studio 2008 C++編程環境.

蟻群算法參數配置見表1.

表1 蟻群算法參數配置

表2為測試數據及結果.

表2 測試數據與結果

如圖3(a)～(c)分別為表2所示的3種不同航行環境條件下的最優航線設計結果.在電子海圖平臺上，可以看到航線避開島嶼等障礙物，遵守船舶定線制，每條航線都是安全、合理的最優航線.通過一些資深船長的定性分析可知，該算法無論從效率上、還是可靠性上都是一種較優的航線設計方法，可以獲得比較滿意的結果.

針對以下幾個方面對算法的可靠性和有效性進行分析.

(1)蟻群算法參數選擇:參數α是信息素權重因數，該因數大表示螞蟻搜索時著重于將信息素濃度作為啟發因子，其取值在［3，5]之間能取得較優解［16];β是啟發信息權重因數，如啟發函數是與距離相關的一個函數，當β取值較大時，螞蟻搜索時著重將距離作為啟發因子，也就是朝離終點最近的方向前進.α與β兩者取值的搭配不同，有可能會對計算時間產生影響，如果α太大，由于初始狀態下沒有任何信息素可以作為啟發因子，導致大量的無效路徑，減緩穩定時間;而β太大，容易在復雜的航區中丟失全局最優解，也偏離蟻群搜索算法的本質.ρ是信息素揮發因數，決定每一輪搜索后各頂點信息素的殘留量.各頂點上螞蟻釋放的信息素含量會隨時間的推移逐漸消散，如果不限制其無限降低，該頂點在計算中將產生丟失現象，這是蟻群算法正反饋機制的不良體現，即某個頂點的信息素一旦積累到一定程度，會吸引越來越多的螞蟻，使得該頂點信息素濃度迅速上升.考慮到算法會收斂到局部最優解，需要適當的削弱正反饋.可以采用信息素控制方法來減緩正反饋的力度，當某頂點信息素濃度超過預設值時，立刻自動消散一部分信息素以保證螞蟻保留一些“主觀能動性”，該措施可防止頂點丟失現象的產生.

圖3 不同條件下的最優化航線設計結果

蟻群算法是一種啟發式算法，利用仿生原理處理問題，雖然存在對算法收斂性的證明，但是仍舊沒有具有普遍意義的嚴格數學證明表示算法確實最終收斂到全局最優解，因為一般的證明只單純從迭代次數趨向于無窮時的情況作出解釋，而蟻群算法中各參數的配置對算法收斂將產生重要影響，但是從十多年的應用以及各種理論成果［17-18]中可以發現，蟻群算法在實際運用過程中能夠接近最優解，獲得比較理想的結果.啟發式算法的結構簡單，程序實現較為容易，受到許多研究人員的青睞.

(2)算法性能分析:圖4為算法迭代100次的收斂曲線，顯示改進后的蟻群算法在搜索過程中能夠在保證全局最優的情況下，不斷搜索新的路徑.從圖中可以看到，最小值都出現在前15次迭代以內，充分表明算法能夠快速搜索到全局最優路徑，而且能夠搜索其他路徑，體現出蟻群一直具有活力，希望不斷搜索到更佳的路線，但是由于最優路徑信息素濃度的加強，后續迭代中螞蟻再找到更優路徑的概率很小.圖5表明這一點.

圖4 收斂曲線

圖5 迭代搜索過程

圖5 為前30次迭代蟻群搜索路徑長度變化情況，測試數據1的始末點距離較另外兩組數據始末點距離遠，搜索經過3個遞減過程，但仍然確保在少于15次時就能找到最優解(如圖4中的數據1).3組實驗結果的路線長度迭代過程表明:航程越長、航區范圍越大、航線越復雜，導致穩定速度越慢.例如，第1組數據的航程為294.26 n mile，第3組數據的航程為183.43 n mile，兩組數據的穩定迭代次數分別為 13和 3次，計算時間分別為1.281 188和0.605 013 s.由于每一輪迭代后都更新信息素，使最短路線上的信息素積累更多，為下一輪迭代的螞蟻提供啟發信息，把更多的螞蟻吸引到最優解的周圍，最終得到全局最短路線，如圖5中路徑長度(縱軸)在迭代過程中逐漸逼近全局最優值.

3 算法在海上搜救船舶上的應用

搜救航線動態優化算法在實際投入運行中的效果可以通過一次模擬實驗得到結果.假設某海域搜救中心收到船舶的求救信號后需作出部署，根據遇險船舶的位置和遇險性質制訂救援計劃，前往救助.實驗條件如下:

(1)遇險船舶不能主動控制船舶，屬于失控船，而且在風浪影響下產生漂移;將根據航區風流情況和初始遇險地點，預測另外2個漂移點;

(2)搜救船舶按照預定航線航行，同時遇險船舶發生漂移;

(3)根據4月氣象數據擬定航區天氣情況，流場流向為東北，風向為東北，風速10.3 ～18.4 kn.疊加氣象信息后搜索區域海圖見圖6.

圖6 疊加氣象信息后的海圖

設定海上救助中心的搜救船事發時正在21°25.683′N，73°31.763′W處巡邏，遇險船舶即時船位為19°9.393′N，73°23.663′W，搜救船舶前往救援.全程取樣3次，每次完成航線1/3時取樣進行動態調整.結果見圖7.

圖7 動態優化航線實驗結果

圖7 中矩形框就是擬定的船舶遇險位置，A，B，C 3條航線分別代表初始航線、第1次動態調整航線和第2次動態調整航線，搜救船舶實際營救航線已加粗顯示在電子海圖上.

根據漂移的軌跡，本算法快速計算出航線，第2次動態調整時，搜救船與遇險船之間已經沒有其他礙航物，航線為直線.

算法運行平均計算時間為0.85 s，實際航程174.56 n mile.在沒有假設物標漂移的情況下，直接從起始點到最終目標的距離為172.29 n mile，計算值已經非常接近這一距離，說明本算法確實能夠完成制訂安全、準確、有效、快速搜救計劃路線的任務.

4 結束語

提出基于標準電子海圖空間數據快速檢索與最優路徑規劃算法的搜救航線實時動態優化方法，并成功應用于海上搜救船舶的動態航線設計，不僅能減輕船員的工作負擔，同時可提高海上救助效率，加強海上搜救能力.

首先引入基于R-樹的電子海圖數據空間索引結構，優化海圖信息的查詢和管理;其次提出空間連通矩陣方法實現航線設計規則，為實現最優航線提供基礎;最后提出改進的蟻群算法自動設計最佳航線.改進后的蟻群算法能快速、高效地完成搜索計算，充分考慮各種礙航物、航行規則以及外部環境因素，因此該算法更加適合在復雜航區中進行最優航線設計.另外，最顯著的特征是航行過程中能夠根據當前的氣象環境，自動估算搜救目標漂移來動態優化航線，避免船員反復進行航線設計工作，對海上搜救尤為重要.

但是，本文僅考慮船舶航行安全性而設計的自動航線與實際航行條件存在一定的差距，因為實際航行過程中通常涉及航行環境、水文氣象以及效能等要素，因此在今后的研究工作中將進一步引入水文氣象等要素.

［1]BREIVIK O，ALLEN A A.An operational search and rescue model for the Norwegian Sea and the North Sea［J].J Mar Systems，2008，69(1/2):99-113.

［2]HONG S P，CHO S J，PARK M J，et al.Optimal search-relocation trade-off in Markovian-target searching［J].Computers ＆ Operations Res，2009，36(6):2097-2104.

［3]于衛紅，賈傳熒.海上搜救中搜尋區域確定方法研究［J].中國航海，2006(2):34-37.

［4]胡志武，畢署光，耿鶴軍.海上搜尋區域確定的計算機輔助方法［J].上海海事大學學報，2008，29(2):11-16.

［5]張有為.海上搜救模擬人及其漂移模型研究［D].大連:大連海事大學，2010.

［6]歐陽.海上失控船舶漂移模型研究［D].大連:大連海事大學，2008.

［7]馬欣.海上最優航線算法研究［J].科技風，2010(18):281-283.

［8]李源惠，潘明陽，吳嫻.基于動態網格模型的航線自動生成算法［J].交通運輸工程學報，2007，7(3):34-39.

［9]楊慧，王直.基于蟻群退火算法的最優航線設計［J].現代電子技術，2009，32(11):188-194.

［10]汪柱，李樹軍，張立華，等.基于航路二叉樹的航線自動生成方法［J].武漢大學學報:信息科學版，2010，35(4):407-410.

［11]陳艷.基于蟻群算法的最優路徑選擇研究［D].北京:北京交通大學，2007.

［12]付宇.蟻群優化算法的改進及應用［D].上海:上海海事大學，2006.

［13]KUMAR S，RAO C S P.Application of ant colony，genetic algorithm and data mining-based techniques for scheduling［J].Robotics and Comput-Integrated Manufacturing，2009，25(6):901-908.

［14]LI Y，CHAN HILTON A B.Optimal groundwater monitoring design using an ant colony optimization paradigm［J].Environ Modeling＆ Software.2007，22(1):110-116.

［15]段海濱，王道波，于秀芬.基本蟻群算法的A.S.收斂性研究［J].應用基礎與工程科學學報，2006，14(2):297-301.

［16]SIMPSON A R，MAIER H R，FOONG W K，et al.Selection of parameters for ant colony optimization applied to the optimal design of water distribution systems［C]//Int Congress on Modelling and Simulation，Australia:Modeling and Simulation Society of Australia and New Zealand，2001:1931-1936.

［17]高尚，楊靜宇.最短路的蟻群算法收斂性分析［J].科學技術與工程，2006，6(3):273-277.

［18]劉立東，蔡淮，趙旭.一類自適應蟻群算法的收斂性分析［J].計算機應用，2007，27(6):73-75.