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

馬 俊，董良雄，李 軍

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

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

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

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

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

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

圖1 分簇結(jié)果圖

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

圖2 柵格示意連通模型

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

2.1 傳統(tǒng)蟻群算法的搜索模型

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

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

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

(1)

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

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

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

(2)

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

圖3 柵格搜索過程

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

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

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

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

2.3 K-means改進蟻群算法最優(yōu)航線導航流程

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

2.3.1 傳統(tǒng)蟻群算法

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

(3)

(4)

2.3.2 基于K-means的船舶航線規(guī)劃方法

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

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

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

3)輸出新的TSP問題的最優(yōu)解。

3 仿真試驗結(jié)果與分析

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

表1 模型參數(shù)設置

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

圖5 本文算法與傳統(tǒng)蟻群算法設計船舶最優(yōu)航線對比

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

4 結(jié)束語

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

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

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