一種基于K-means改進蟻群算法的船舶航線設計方法

馬 俊，董良雄，李 軍

(浙江海洋大學，浙江 舟山 316022)

船舶航行時必須綜合考慮船舶安全性及經濟性等因素，根據航行環境(如水深、障礙物等)結合船舶參數，選擇恰當的方法設計航線。船舶傳統航線是根據個人經驗，徒手海圖作業方式完成的，但隨著船舶日益趨于智能化、自動化、數字化[1]，這種方法不僅計算復雜，而且人為因素影響大。因此，許多學者提出各種算法來設計船舶航線，例如Khatib提出人工勢場法，易于實時避障和控制，規劃的路徑較為平滑和安全，但缺乏對全局信息的掌握，易于過早陷入局部最優解，致使出現“死鎖”現象。Holland基于進化機制理論構造出的一種隱含并行性隨機搜索算法，能夠直接通過確定適應度(按照自然進化過程中適者生存和優勝劣汰的原理)作為搜索條件，不受其他輔助信息的限制，但存在運算速度慢、占用儲存空間大、出現早熟收斂的缺點。針對上述算法的局限性，M.Dorigo提出一種基于螞蟻種群覓食的過程來解決復雜路徑問題的新型優化算法，即蟻群算法。該方法能提高搜索效率，且具有較強的穩健性和適應性，但蟻群算法受初始參數的影響，容易陷入局部最優解[2]。

因此，本文針對單一蟻群算法在執行過程中存在陷入局部最優解、效率低等問題進行了研究，提出一種基于K-means改進蟻群算法的航線設計方法。即先利用K-means對已標識的柵格海圖進行聚類分析，將整個TSP問題分解成許多獨立的TSP子問題；然后多次利用蟻群算法對每個子問題求解，并將得到的所有解合并成待求問題的解，該方法能為船舶航跡規劃尋找一種更加有效的工具。

1 K-means在海域柵格建模中的應用

K-means是一個對在某些方面相似的數據進行分類組織的過程。航跡規劃時，一般要把航行區域柵格化為若干個方格(柵格)，然后在航行環境中，對可航區域與不可航區域加以區分，進而設計合理航線。顯然，柵格粒度(大小)越細，障礙物劃分就越詳細，環境模型就越貼近真實環境[3]，但往往因為柵格大小劃分不同，致使所需時間增加，占用空間大；而且在密集環境下，障礙物往往并不規則，存在與可航區域劃分界限不是特別清楚等現象。因此，為了對柵格地圖進行更加合理有效分區，可采用K-means方法對柵格進行分區，把代表相似障礙物的柵格聚集到一起，即加快柵格處理時離散化，對柵格進行先分離后集中處理。

本文選取了一個20×20的柵格并采用Python軟件進行分簇。先確定簇的個數K，隨機生成K個聚類中心點，將數據對象進行分類，即將x個數據對象分成K個簇，使簇間內相似度高，簇與簇之間相似度較低；然后依據簇間數據對象到簇內聚類中心點的距離計算其相似度，根據數據對象到各簇中心點的距離不同，將數據對象劃分給不同簇。其Python程序中，當聚類不再變化時，找到最近的聚類中心后更改聚類中心位置，使結果具有可比性、合理性。分簇后得到的結果如圖1所示。圖1中“箭頭”所指的是分簇后該簇的中心點，“數字屬性密集程度”代表各對象之間的相似度，其中?屬性柵格為可航區域，①屬性柵格為陸地、島嶼，②屬性柵格為淺水區(?屬性柵格之間能聯通，②屬性柵格可到?屬性柵格)。可以看出，海域柵格已被分成了4個集合(簇)，每一個集合中都有若干個相似對象，在此基礎上為船舶設計路徑時，需要考慮的因素大大減少，進而使航跡規劃的模型簡單化，有助于航跡規劃算法精確性的提高。

圖1 分簇結果圖

同時，海上環境存在著陸地、島嶼和淺水區等不同的通航環境，船舶航行必須避開陸地和島嶼，這是船舶航行設計時的一般原則。此外，船長往往還會根據實際經驗設置額外的航線要求，比如安全距離要求，位處淺水區可到可航海域，但可航海域應避免或不能到達淺水區等要求。因此，本文將陸地、島嶼和淺水海域等需要規避的障礙物與可航海域進行了相應區分與標記，并將障礙物進行了一定的膨脹處理，從而滿足船舶與障礙物之間的安全距離要求。圖2為針對某海圖進行柵格化的模型，通過對柵格進行離散化和膨脹化，并對不同柵格屬性進行標識，可構建圖2中所示的連通關系。

圖2 柵格示意連通模型

2 基于K-means改進蟻群算法的設計

2.1 傳統蟻群算法的搜索模型

海域柵格建好之后，就可以利用蟻群算法進行最優路徑的搜索。蟻群算法作為一種新生仿生啟發式算法[4]，求解問題速度快，具有并行運算能力及穩健性強等特點，其搜索路徑過程如下。

1)分析搜索范圍。在如圖3所示的柵格圖中，某時刻螞蟻位于圖3(a)中黑色圓圈部分，根據所在位置周圍其他螞蟻留下的信息素變化，得到向相鄰柵格移動的范圍，即向圖3(b)的深灰部分移動；最終到達圖3(c)的位置。

2)蟻群移動法則。螞蟻由初始位置向周圍柵格i移動，其移動到下一個柵格位置概率為：

(1)

式中，P0→i為螞蟻由初始柵格0移動到柵格i的概率值;c0→i為螞蟻由初始柵格0移動到柵格i所經歷距離的倒數；b0→i為終點柵格i的信息素濃度；M為螞蟻移動時可到達的柵格數；B、H為強度系數。

3)實時更新蟻群信息素濃度。螞蟻在柵格中移動時，根據路徑中的信息素濃度進行路徑搜索。同時對柵格路徑中的信息素濃度進行更新，方法一般采用混合更新策略，計算公式為：

τi=(1-σ)(τi+Δτ) ，

(2)

式中：σ為信息至少揮發系數，σ∈(0,1)；τi為原始信息素濃度；Δτ為信息素濃度的變化值。

圖3 柵格搜索過程

2.2 基于K-means改進蟻群算法的搜索模型

蟻群算法搜索船舶最優航線時，可運用避讓規則、移動法則和信息素實時更新等規則[5]。避讓規則簡單直觀，只需避開障礙物；移動法則為在螞蟻所處位置的一定范圍內選擇移動的區域；信息素實時更新規則為根據前一只螞蟻在所經過路徑遺留的信息素選擇，信息素越多，代表所經過的螞蟻數量就越多。

根據基于K-means的航跡規劃方案，采用避讓規則是比較適合的。因此本文綜合考慮障礙物及淺水海域等不可航行因素，并結合航線應用到實際海況中的可行性，在建立的海域柵格圖的基礎上，利用避讓規則進行船舶最優航線設計搜索，搜索過程如圖4所示。因傳統蟻群算法周圍柵格為當前的陰影柵格，見圖3(b)，使得利用蟻群算法進行船舶最優航線設計搜索后期出現停滯，所以為了加快搜索的速度，采用K-means先對柵格進行聚類并加以區分特性標識，既能保證搜索的精度，又能減少搜索的次數。為了更加明顯地看出優勢，將數字屬性轉化為特性柵格，最終得到3種搜索方案并采用方案2進行航行。圖4中，黑色柵格(①)屬性代表陸地，灰色柵格(①)屬性代表島嶼，柵格(②)屬性代表淺水區，白色柵格(?)代表可航區域，1、2、3代表搜索方案。

圖4 K-means改進蟻群算法的搜索路徑圖

2.3 K-means改進蟻群算法最優航線導航流程

為了對比傳統蟻群算法與K-means改進的蟻群算法，本文針對2.1節與2.2節所述的搜索模型進行了航跡規劃算法步驟設計與對比。

2.3.1 傳統蟻群算法

傳統的蟻群算法設計航線時[6]，首先對海圖進行柵格化，建立柵格模型，在柵格模型中應用轉移概率公式(3)和信息素更新公式(4)進行規劃航線，重復應用公式(3)和公式(4)直至規劃出航線。

(3)

(4)

2.3.2 基于K-means的船舶航線規劃方法

基于K-means改進蟻群算法的船舶航線規劃方法具體步驟如下。

1)按照前文所述，利用Python算法程序語句先對20×20柵格進行聚類分簇，得到分類后標識其中元素。

2)在類內和類間分別應用2.1搜索模型，對得到的路徑進行連接。其中尋找各類的邊界柵格路徑算法實現如下：①將類內當成一個獨立的TSP問題，這樣各類內組合就又構成了一個新的TSP。利用傳統蟻群算法對其TSP進行求解，得到的最優解就是各類內的最優連接順序。②求類內與類內間的連接，即類間的連接口。在其中，利用傳統蟻群算法求各類間連接口之間的最短路徑。③求解新的TSP問題的最短路徑，即求得各類間連接口之間的最短路徑后，對所有的類，通過①中運算得到的連接順序把類間連接口連接起來，進而構成了新的TSP問題的最優路徑。

3)輸出新的TSP問題的最優解。

3 仿真試驗結果與分析

仿真平臺仍采用前文使用的Python軟件，按照海域柵格設計模型方法，對20×20已分類的柵格進行不同標識，并且按要求設置各種海洋環境[7]、安全距離(深度)等參數。為了使仿真結果具有可比性和說服性，參數設置如表1所示。

表1 模型參數設置

利用表1的模型參數進行編程，基于K-means改進的蟻群算法(本文算法)與傳統蟻群算法分別設計的船舶最優航線對比如圖5所示。從圖5可看出，雖然2種算法均有效地避開海上不可航行區域，但基于K-means改進的蟻群算法搜索得到的航線里程更短。該算法設計時要求合理利用淺水區航行，因此航線中不僅保證了船舶的吃水深度，避免重量級船舶行駛至淺水區的擱淺概率，保證所設計的航線航行安全性。

圖5 本文算法與傳統蟻群算法設計船舶最優航線對比

針對該算法設計生成航線的效率方面，本文共進行5次實驗，統計每次實驗所耗費的時間，生成航線耗時對比表見表2。不管從單次實驗所耗時間，還是從平均所耗時間來看，每次試驗所耗時間相比于傳統蟻群算法都更少。

4 結束語

本文利用K-means改進蟻群算法設計的船舶航跡規劃方法，有效地解決了傳統蟻群算法易陷入

表2 生成航線耗時對比表 s

局部最優解、收斂速度慢等缺陷。通過實驗仿真的結果看，本文所提出的基于K-means改進蟻群算法是可行的，該方法能夠科學合理地設計出一條里程最短且安全避障，并滿足設計時對淺水區的實際需求的航線，算法所耗時間比傳統蟻群算法所耗時間更少。