海上落水目標(biāo)協(xié)同搜尋路徑規(guī)劃算法研究*

李 林

（交通運(yùn)輸部水運(yùn)科學(xué)研究院 北京 100088）

1 引言

以船舶為載體的海運(yùn)經(jīng)濟(jì)網(wǎng)絡(luò)，極大地促進(jìn)了各國(guó)經(jīng)濟(jì)發(fā)展，具有不可替代的作用［1~2］。隨著海上運(yùn)輸船舶數(shù)量的增長(zhǎng)，船舶遇險(xiǎn)事故數(shù)量也逐步增長(zhǎng)［3］。船載救生裝備往往會(huì)安裝示位標(biāo)［4~5］，示位標(biāo)基于GNSS 能夠提供準(zhǔn)確的待救目標(biāo)位置，便于搜救艇、直升機(jī)等救援設(shè)備快速、準(zhǔn)確開(kāi)展海上落水目標(biāo)的搜救和打撈工作［6~7］。

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

本文提出一種多無(wú)人機(jī)協(xié)同的海上搜救目標(biāo)分類(lèi)與路徑規(guī)劃算法。該算法基于K-means 算法和遺傳算法，采用均值-方差模型為作為最優(yōu)路徑的選擇算子，具有算法簡(jiǎn)單、魯棒性強(qiáng)、收斂速度快和全局搜索能力強(qiáng)等特點(diǎn)。

2 模型構(gòu)建

2.1 變量定義

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

2.2 前置條件

1）遍歷所有目標(biāo)

2）每個(gè)目標(biāo)僅進(jìn)過(guò)一次

3）其它約束

3 問(wèn)題分析與算法實(shí)現(xiàn)

3.1 海上目標(biāo)的漂移特征分析

海上目標(biāo)在風(fēng)、浪、流等自然因素的影響下［13］，會(huì)形成一個(gè)速度場(chǎng)，目標(biāo)漂移運(yùn)動(dòng)的速度會(huì)隨著這個(gè)速度場(chǎng)的變化而變化［14］，逐漸離開(kāi)原落水地點(diǎn)。受到漂移目標(biāo)自身性質(zhì)影響，比如目標(biāo)的大小、形狀、浸沒(méi)比例等也會(huì)影響物體的漂移方向。結(jié)合風(fēng)壓的特性，并利用線(xiàn)性回歸的方式對(duì)不同狀態(tài)的救生筏進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，不同狀態(tài)的救生筏會(huì)向不同方向漂移，最終形成位置差異相對(duì)較大的多個(gè)群體［15］。海上救生筏漂移方向矢量模型結(jié)果如圖1所示。

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

3.2 海上搜救目標(biāo)分類(lèi)子算法

本節(jié)采用基于遺傳算法的K-means 聚類(lèi)方法求解，根據(jù)示位標(biāo)輸出位置實(shí)現(xiàn)目標(biāo)分類(lèi)。該算法以聚類(lèi)中心位置作為染色體，并進(jìn)行編碼。利用K-means準(zhǔn)則函數(shù)值進(jìn)行擇優(yōu)選擇，得到最終的聚類(lèi)中心。

1）染色體編碼

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

2）基于K-means準(zhǔn)則函數(shù)的適應(yīng)度函數(shù)

利用準(zhǔn)則函數(shù)構(gòu)造適應(yīng)度函數(shù)。適應(yīng)度函數(shù)越大說(shuō)明聚類(lèi)結(jié)果越優(yōu)，越小說(shuō)明聚類(lèi)結(jié)果越差，因此適應(yīng)度函數(shù)為

3）遺傳算子

（1）選擇算子：采用最優(yōu)保存策略和比例選擇法相結(jié)合的方法。選擇適應(yīng)度高的個(gè)體，并采用輪盤(pán)賭的策略進(jìn)行個(gè)體選擇，最后將最優(yōu)個(gè)體替換種群中最差個(gè)體。

（2）交叉算子：選取適合浮點(diǎn)數(shù)編碼的算術(shù)交叉方式，將兩條配對(duì)的染色體進(jìn)行線(xiàn)性組合，產(chǎn)生兩條新的染色體。

（3）變異算子：采用均勻變異算子，選定染色體的基因變異點(diǎn)，從取值范圍內(nèi)產(chǎn)生隨機(jī)數(shù)，并替換原基因值。

3.3 海上目標(biāo)路徑規(guī)劃子算法

本節(jié)采用基于均值-方差模型的多染色體遺傳算法進(jìn)行求解，實(shí)現(xiàn)海上目標(biāo)路徑規(guī)劃。該算法突破了單染色體遺傳進(jìn)化的框架，引入多染色體優(yōu)化搜索的思路［16］。有針對(duì)性的選擇位置相鄰目標(biāo)，并對(duì)其進(jìn)行基因段插入突變，進(jìn)而改變了染色體基因數(shù)量，有利于獲取全局最優(yōu)解。下面以3 個(gè)無(wú)人機(jī)、15個(gè)目標(biāo)為例介紹該算法。

1）多染色體編碼

染色體每個(gè)基因表示一個(gè)目標(biāo)，其中出發(fā)位置編號(hào)為0。多染色體編碼方式如圖2所示。

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

2）基于均值-方差模型的適應(yīng)度函數(shù)

將搜尋設(shè)備行駛距離的均值作為主目標(biāo)函數(shù)，選取設(shè)備形式距離的方差作為次目標(biāo)函數(shù)，對(duì)方案按主次目標(biāo)函數(shù)進(jìn)行排序。則多搜尋設(shè)備協(xié)同的海上目標(biāo)路徑規(guī)劃目標(biāo)函數(shù)為

其中：

式中：μ為主目標(biāo)函數(shù)；σ2為次目標(biāo)函數(shù)，對(duì)方案主次目標(biāo)函數(shù)進(jìn)行排序，即設(shè)備行駛距離均值越小越好，行駛距離均值處于同一量級(jí)，方差越少越好。

3）遺傳算子

（1）選擇算子：采用最優(yōu)保存策略和比例選擇法相結(jié)合的方法。將適用度高的個(gè)體選擇出來(lái)，并采用輪盤(pán)賭的策略選擇個(gè)體，將最優(yōu)個(gè)體替換種群中最差個(gè)體。

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

圖3 排序交叉示例

（3）變異算子：采用基因段插入突變方式。當(dāng)兩條染色體上目標(biāo)位置距離較近時(shí)，將目標(biāo)基因段標(biāo)記為交換區(qū)基因。若變異后適應(yīng)度值小于變異前，則執(zhí)行變異操作?；蚨尾迦胪蛔兎绞降淖儺愡^(guò)程如圖4所示。

圖4 雜交突變算子變異過(guò)程

3.4 算法流程

本文提出的算法由目標(biāo)分類(lèi)和路徑規(guī)劃兩個(gè)子算法組成，以主次目標(biāo)函數(shù)方式建立比較準(zhǔn)則，算法流程如圖5所示。

圖5 算法流程圖

4 計(jì)算結(jié)果

采用面向?qū)ο蟮膉ava語(yǔ)言編寫(xiě)程序，實(shí)現(xiàn)本文提出的算法。假設(shè)本次搜尋工作提供2 艘搜救船舶和1架搜救直升機(jī)，則搜尋設(shè)備總數(shù)量為3，海上漂移目標(biāo)數(shù)量為30（不包含出發(fā)位置），設(shè)置算法種群規(guī)模為10，最大迭代次數(shù)為500，當(dāng)?shù)?00~200時(shí)即可獲得最優(yōu)解，計(jì)算結(jié)果如圖6所示。

圖6 本文算法計(jì)算結(jié)果

本文算法輸出結(jié)果如表1 所示。從表中可以發(fā)現(xiàn)相對(duì)初始距離，每個(gè)搜尋設(shè)備行駛的距離明顯減少，且三個(gè)搜尋設(shè)備的方差相對(duì)較小，避免了因個(gè)別搜尋設(shè)備遍歷距離長(zhǎng)而影響整體方案。同時(shí)，對(duì)于行駛距離較長(zhǎng)的搜救路線(xiàn)，可選取速度相對(duì)較快的搜尋設(shè)備開(kāi)展搜救工作。

表1 本文算法計(jì)算結(jié)果

5 結(jié)語(yǔ)

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