海上落水目標協同搜尋路徑規劃算法研究*

李 林

（交通運輸部水運科學研究院 北京 100088）

1 引言

以船舶為載體的海運經濟網絡，極大地促進了各國經濟發展，具有不可替代的作用［1~2］。隨著海上運輸船舶數量的增長，船舶遇險事故數量也逐步增長［3］。船載救生裝備往往會安裝示位標［4~5］，示位標基于GNSS 能夠提供準確的待救目標位置，便于搜救艇、直升機等救援設備快速、準確開展海上落水目標的搜救和打撈工作［6~7］。

海上落水目標的搜尋路徑規劃問題可以抽象為多旅行商（mTSP）問題，屬于組合優化問題［8~9］，其求解過程包含了目標分組及組內遍歷次序兩個環節，是典型的NP-Hard問題［10］。對于多旅行商問題的研究主要集中在染色體的編碼方式上［11~12］，不合理的編碼策略將提高遺傳算法的復雜度，產生大量冗余解，制約算法的求解效率。

本文提出一種多無人機協同的海上搜救目標分類與路徑規劃算法。該算法基于K-means 算法和遺傳算法，采用均值-方差模型為作為最優路徑的選擇算子，具有算法簡單、魯棒性強、收斂速度快和全局搜索能力強等特點。

2 模型構建

2.1 變量定義

C={1,2,…,n}表示遍歷目標集合，共有n個目標。其中第一個目標為無人機飛行起點；U={1,2,…,m}表示無人機集合，參與遍歷的無人機數量為m個；(x,y)表示無人機經緯度坐標位置；sij表示無人機從目標i至目標j的路徑長度；Sk表示第k個無人機的路徑總長度；rijk表示第k個無人機從目標i飛行至目標j；wijk表示從第k個無人機從目標i飛行至目標j的權值。

2.2 前置條件

1）遍歷所有目標

2）每個目標僅進過一次

3）其它約束

3 問題分析與算法實現

3.1 海上目標的漂移特征分析

海上目標在風、浪、流等自然因素的影響下［13］，會形成一個速度場，目標漂移運動的速度會隨著這個速度場的變化而變化［14］，逐漸離開原落水地點。受到漂移目標自身性質影響，比如目標的大小、形狀、浸沒比例等也會影響物體的漂移方向。結合風壓的特性，并利用線性回歸的方式對不同狀態的救生筏進行實驗。實驗結果表明，不同狀態的救生筏會向不同方向漂移，最終形成位置差異相對較大的多個群體［15］。海上救生筏漂移方向矢量模型結果如圖1所示。

圖1 海上救生筏漂移方向矢量模型

3.2 海上搜救目標分類子算法

本節采用基于遺傳算法的K-means 聚類方法求解，根據示位標輸出位置實現目標分類。該算法以聚類中心位置作為染色體，并進行編碼。利用K-means準則函數值進行擇優選擇，得到最終的聚類中心。

1）染色體編碼

將集合C聚類成m個簇，聚類中心位置分別為(x1,y1)、(x2,y2)、…、(xm,ym)，則染色體編碼為(x1,y1,x2,y2,…,xm,ym)。采用直接對問題解編碼方式，提高了遺傳算法的運行效率，便于處理復雜的變量約束條件。

2）基于K-means準則函數的適應度函數

利用準則函數構造適應度函數。適應度函數越大說明聚類結果越優，越小說明聚類結果越差，因此適應度函數為

3）遺傳算子

（1）選擇算子：采用最優保存策略和比例選擇法相結合的方法。選擇適應度高的個體，并采用輪盤賭的策略進行個體選擇，最后將最優個體替換種群中最差個體。

（2）交叉算子：選取適合浮點數編碼的算術交叉方式，將兩條配對的染色體進行線性組合，產生兩條新的染色體。

（3）變異算子：采用均勻變異算子，選定染色體的基因變異點，從取值范圍內產生隨機數，并替換原基因值。

3.3 海上目標路徑規劃子算法

本節采用基于均值-方差模型的多染色體遺傳算法進行求解，實現海上目標路徑規劃。該算法突破了單染色體遺傳進化的框架，引入多染色體優化搜索的思路［16］。有針對性的選擇位置相鄰目標，并對其進行基因段插入突變，進而改變了染色體基因數量，有利于獲取全局最優解。下面以3 個無人機、15個目標為例介紹該算法。

1）多染色體編碼

染色體每個基因表示一個目標，其中出發位置編號為0。多染色體編碼方式如圖2所示。

圖2 多染色體編碼方式示例

2）基于均值-方差模型的適應度函數

將搜尋設備行駛距離的均值作為主目標函數，選取設備形式距離的方差作為次目標函數，對方案按主次目標函數進行排序。則多搜尋設備協同的海上目標路徑規劃目標函數為

其中：

式中：μ為主目標函數；σ2為次目標函數，對方案主次目標函數進行排序，即設備行駛距離均值越小越好，行駛距離均值處于同一量級，方差越少越好。

3）遺傳算子

（1）選擇算子：采用最優保存策略和比例選擇法相結合的方法。將適用度高的個體選擇出來，并采用輪盤賭的策略選擇個體，將最優個體替換種群中最差個體。

（2）交叉算子：采用排序交叉方式，隨機選取基因片段進行交叉操作。如后代染色體中出現重復基因，則保留選擇出來的交叉基因片段，其余部分基因按缺失順序進行替換。排序交叉示例如圖3所示。

圖3 排序交叉示例

（3）變異算子：采用基因段插入突變方式。當兩條染色體上目標位置距離較近時，將目標基因段標記為交換區基因。若變異后適應度值小于變異前，則執行變異操作。基因段插入突變方式的變異過程如圖4所示。

圖4 雜交突變算子變異過程

3.4 算法流程

本文提出的算法由目標分類和路徑規劃兩個子算法組成，以主次目標函數方式建立比較準則，算法流程如圖5所示。

圖5 算法流程圖

4 計算結果

采用面向對象的java語言編寫程序，實現本文提出的算法。假設本次搜尋工作提供2 艘搜救船舶和1架搜救直升機，則搜尋設備總數量為3，海上漂移目標數量為30（不包含出發位置），設置算法種群規模為10，最大迭代次數為500，當迭代到100~200時即可獲得最優解，計算結果如圖6所示。

圖6 本文算法計算結果

本文算法輸出結果如表1 所示。從表中可以發現相對初始距離，每個搜尋設備行駛的距離明顯減少，且三個搜尋設備的方差相對較小，避免了因個別搜尋設備遍歷距離長而影響整體方案。同時，對于行駛距離較長的搜救路線，可選取速度相對較快的搜尋設備開展搜救工作。

表1 本文算法計算結果

5 結語

本文提出了一種海上落水目標協同搜尋路徑規劃算法，用于提高海上落水目標的搜尋能力。本文將問題求解拆分為目標分類和路徑規劃兩個子算法。根據實際應用需要，設計了主次兩個目標函數。計算結果分析表明，本文提出的多染色體遺傳算法具有比當前解決同類問題較好的性能和結果，能夠適應實際問題需要。今后研究中需要進一步對染色體編碼方式進行研究，以提高算法精度和性能，并將該算法運用于更廣泛的多旅行商問題求解之中。