文 王代楠，陳 瓊

（1.漳州海事局，福建 漳州 363122；2.東海航海保障中心福州通信中心，福建 福州 350000）

一、引言

隨著交通強國戰(zhàn)略持續(xù)推進，水上水下活動日益活躍形成的船舶密集區(qū)給VTS遠程監(jiān)管服務(wù)帶來嚴峻挑戰(zhàn)。VTS為船舶密集區(qū)域內(nèi)的船舶通過提供遠程交通組織和信息服務(wù)，可防止水上交通擁堵局面進一步加劇，改善通航水平，保障海上人命財產(chǎn)安全。

運用信息化手段對船舶密集區(qū)域進行識別和監(jiān)視，可有效提升VTS監(jiān)管服務(wù)效能，減輕轄區(qū)通航壓力，并能及時為VTS值班人員提供決策信息，彌補值班過程中的決策疏忽，輔助值班人員做出科學(xué)決策。而當(dāng)前使用的VTS系統(tǒng)缺乏對船舶密集區(qū)域的快速識別功能，識別主要依靠值班員的業(yè)務(wù)能力和經(jīng)驗，對船舶密集區(qū)域高效的識別需求與VTS落后的識別水平之間的矛盾凸顯。

本文探討了結(jié)合差分進化算法的改進K-means聚類算法，該算法具有較高的全局搜索能力和收斂速度，能快速實現(xiàn)VTS覆蓋區(qū)船舶的劃分聚類，形成VTS船舶密集區(qū)域快速識別模型，并以該識別模型為原型設(shè)計“VTS船舶密集區(qū)預(yù)警系統(tǒng)”，通過人機對比試驗，證明該模型是有效且可行的。

二、結(jié)合差分進化算法改進的K-means聚類算法

（一）傳統(tǒng)K-means聚類算法

傳統(tǒng)K-means聚類算法是一種經(jīng)典的無監(jiān)督學(xué)習(xí)算法，通過迭代將數(shù)據(jù)劃分到各個簇，使得數(shù)據(jù)點到各區(qū)域中心的距離之和最小[1]。VTS中船舶方位分布是二維的，兩個樣本點之間歐式距離計算簡單快速，因此K-means算法適用于船舶聚類。算法步驟簡要如下：

（3）收斂結(jié)束。重復(fù)步驟（2），直到所有樣本數(shù)據(jù)都劃分到距離最小的簇中，最終得到k個目標(biāo)聚類。

（二）改進K-means聚類算法

經(jīng)分析可知，傳統(tǒng)K-means算法對k值敏感，k值難以快速選擇確定，初始值對最終聚類結(jié)果影響較大，聚類結(jié)果可能只是局部最優(yōu)而不是全局最優(yōu)[2]。傳統(tǒng)算法穩(wěn)定性差、結(jié)果波動較大、收斂速度慢等缺點和船舶密集區(qū)快速精準(zhǔn)識別的應(yīng)用需求不符，因此，本文通過引進差分進化算法來改進K-means聚類算法，以彌補算法缺陷，提升聚集分析中的收斂速度和穩(wěn)定性。

1. 差分進化算法

差分進化算法（Differential Evolution Algorithm，DE）是一種模擬生物進化的自適應(yīng)全局優(yōu)化算法。該算法通過變異、交叉、選擇的反復(fù)迭代，優(yōu)勝劣汰獲取最優(yōu)個體。算法具有收斂快、參數(shù)設(shè)置簡單、優(yōu)化結(jié)果穩(wěn)健等優(yōu)點[3]。算法步驟簡要如下：

（2）變異。初始化后，執(zhí)行變異策略獲取變異向量Vi,G。本文選定的變異策略為：

其中，縮放因子F的值過小會降低收斂速度，過大會造成不收斂。

（5）判斷。達到最大進化代數(shù)則輸出結(jié)果，反之執(zhí)行變異步驟[4]。

2. 結(jié)合差分進化算法的改進K-means聚類算法

算法分析可知，DE算法通過對群體中個體多次優(yōu)化以達到逼近最優(yōu)解，具有實現(xiàn)簡單、收斂快速、魯棒性強等優(yōu)點，與K-means算法相結(jié)合能較好解決k值敏感缺陷，從而提高整體聚類的收斂速度和穩(wěn)定性。改進算法步驟簡要如下：

結(jié)合差分進化算法的改進K-means聚類算法流程圖，見圖1：

圖1 改進K-means聚類算法流程圖

三、改進K-means聚類算法在“VTS船舶密集區(qū)預(yù)警系統(tǒng)”中應(yīng)用

對船舶數(shù)超過一定數(shù)目的聚類作為預(yù)警信息進行提示，顯示船舶聚類信息，可輔助VTS值班人員對船舶和通航狀況進行研判并做出決策[5]，適時開展VTS交通組織和遠程預(yù)警提醒，能有效避免船舶密集導(dǎo)致險情事故的發(fā)生。

本文以上述改進K-means聚類算法為算法原型，以某個時間點的VTS覆蓋區(qū)內(nèi)所有船舶為樣本數(shù)據(jù)輸入（單船數(shù)據(jù)模型見表1），以船舶密集區(qū)中心方位和半徑（簇中心至簇內(nèi)樣本的最遠距離）作為輸出，建立VTS船舶密集區(qū)識別模型。

表1 單船數(shù)據(jù)模型

以改進K-means聚類算法為基礎(chǔ)，參考現(xiàn)有VTS架構(gòu)[6]，本文設(shè)計“VTS船舶密集區(qū)預(yù)警系統(tǒng)”，系統(tǒng)泳道圖見圖2，系統(tǒng)主要包含VTS、MIS、K-means&DE、NTP等4個模塊，各模塊主要功能為：

圖2 VTS船舶密集區(qū)預(yù)警系統(tǒng)泳道圖

VTS模塊：提供算法所需基礎(chǔ)AIS樣本數(shù)據(jù)，并將接收的聚類信息和預(yù)警信息展示在VTS界面上。同時，VTS也提供中斷操作，避免系統(tǒng)影響VTS主要功能，妨礙業(yè)務(wù)正常開展。MIS模塊：用于設(shè)置算法和程序初始化操作。算法初始化包括：聚類中心點k初始值，進化代數(shù)G，縮放因子F，交叉概率CR，最小聚類大小等。程序初始化包括：算法運行頻率、樣本（船舶）類型、中斷類型設(shè)置等。同時，MIS還提供日志和歷史數(shù)據(jù)存儲等功能。K-means&DE模塊：核心算法模塊，根據(jù)輸入的參數(shù)和樣本數(shù)據(jù)獲取聚類中心信息。該模塊同時具有樣本過濾、中斷監(jiān)聽、日志攔截存儲等功能。NTP模塊：時間服務(wù)模塊，提供時間一致性和定時服務(wù)。

本文以漳州VTS為示例。首先，獲取某個時間片報告線內(nèi)所有船舶的AIS數(shù)據(jù)，剔除岸上物標(biāo)、港內(nèi)錨地內(nèi)船舶、助航設(shè)施等非目標(biāo)對象，結(jié)合時間、簇等屬性封裝成便于計算的樣本對象集合。其次，將樣本集合作為輸入代入算法進行計算，通過多次變異、交叉、選擇的迭代運算，獲取船舶聚類集合，最后，將符合實際應(yīng)用的聚類信息在用戶界面進行輸出展示，達成遠程預(yù)警目的。實驗示例見圖3：將某一時刻船舶數(shù)超過10的聚類區(qū)域在VTS界面上進行高亮顯示。

圖3 模擬實驗截圖

選取6組樣本數(shù)據(jù)進行機器和人工的對比試驗，獲取預(yù)警系統(tǒng)運行日志和人工盯屏預(yù)警的數(shù)據(jù)，見表2，并對人工數(shù)據(jù)結(jié)果進行一定的偏差校正。造成偏差的原因：一是預(yù)警方式偏差。與預(yù)警系統(tǒng)的全記錄方式相比，值班人員主要是以TCPA和CPA為依據(jù)向船舶提供信息服務(wù)，對于船舶密集區(qū)，值班人員并不完全依此提供預(yù)警服務(wù)；二是試驗人員偏差。不同樣本對應(yīng)的值班人員不同，其業(yè)務(wù)能力、經(jīng)驗各不相同，即人工預(yù)警數(shù)因人而異；三是客觀因素偏差。如凌晨時段值班人員交通組織和信息服務(wù)數(shù)量有所下降。因此，為盡可能的體現(xiàn)實驗數(shù)據(jù)真實性和可靠性，需對人工預(yù)警數(shù)采取一定修正以減少偏差，經(jīng)評估修正系數(shù)設(shè)定為1.4。

表2 系統(tǒng)報警和人工報警對比

可以看出，即使是修正后，預(yù)警系統(tǒng)報警數(shù)和檢出率都遠超人工預(yù)警數(shù)和檢出率，表明預(yù)警系統(tǒng)和VTS船舶密集區(qū)識別模型是有效的，即改進K-means聚類算法應(yīng)用于船舶密集區(qū)的識別是可行的。

四、結(jié)語

本文引進差分進化算法對K-means聚類算法進行一定混合研究，改進后的K-means算法具有全局優(yōu)化能力、收斂速度快等特點?；谠撍惴ㄔO(shè)計的船舶密集區(qū)域識別模型，在“VTS船舶密集區(qū)預(yù)警系統(tǒng)”中的實踐應(yīng)用取得良好的應(yīng)用成果。

本文存在下列不足之處：一是改進K-means算法仍限制于參數(shù)設(shè)定，不同的參數(shù)設(shè)置、不同數(shù)量級的樣本對算法執(zhí)行有效性、復(fù)雜度和資源占用率的影響有顯著區(qū)別；二是本文構(gòu)建的模型忽略了船舶大小問題，而在實際中受操縱問題影響，大型船對船舶聚類有顯著影響，VTS對大型船舶動態(tài)應(yīng)當(dāng)優(yōu)先識別和監(jiān)視；三是受編程能力限制，模擬系統(tǒng)的功能性、集成性需進一步改進。