船舶避碰的粒子群-遺傳（PSO-GA）的混合優(yōu)化算法研究

周鳳杰

（重慶青年職業(yè)技術(shù)學(xué)院，重慶 400712）

0 引 言

隨著世界各國(guó)之間貿(mào)易往來(lái)越來(lái)越頻繁，船舶海上運(yùn)輸已經(jīng)成為一種國(guó)際性的運(yùn)輸產(chǎn)業(yè)，目前全世界大多數(shù)國(guó)家大宗進(jìn)出口貨物都在使用海上運(yùn)輸，海運(yùn)航線極為繁忙。同時(shí)隨著海上科技的發(fā)展，船舶噸位越來(lái)越大，船速也越來(lái)越快，加大了海上碰撞事故發(fā)生的可能性。為避免船舶發(fā)生碰撞，船舶避碰決策研究已成為航海界關(guān)注的重要議題[1-3]。一直以來(lái)，許多專(zhuān)家學(xué)者都在發(fā)表有關(guān)避碰自動(dòng)化、人工智能化的研究成果，目的就是為了避免或減少船舶在海上交通流量大與交通形式復(fù)雜情況下發(fā)生碰撞事故。經(jīng)過(guò)多年的發(fā)展，該領(lǐng)域里的研究已逐步從傳統(tǒng)的基于數(shù)學(xué)理論的分析轉(zhuǎn)變?yōu)榫哂兄悄芑约皩W(xué)科多樣性的路徑規(guī)劃分析，相關(guān)領(lǐng)域的學(xué)術(shù)研究成果也在不斷豐富[4-6]。

以模糊邏輯算法為基礎(chǔ)，針對(duì)船舶碰撞危險(xiǎn)度方面，通過(guò)計(jì)算機(jī)模擬的方法，給出了船舶航行避碰操作的決策模型。也有學(xué)者針對(duì)船舶碰撞危險(xiǎn)度進(jìn)行評(píng)估，利用模糊理論得到學(xué)習(xí)樣本，以每個(gè)目標(biāo)的DCPA（Distance of the Closest Point of Approach）和TCPA（Time to the Closest Point of Approach）作為輸入，船舶碰撞危險(xiǎn)指標(biāo)作為輸出，并應(yīng)用倒傳遞神經(jīng)網(wǎng)絡(luò)進(jìn)行多屬性決策[7-8]。除了進(jìn)行船舶避碰的安全決策外，有學(xué)者還針對(duì)船舶避碰決策中的船舶運(yùn)動(dòng)態(tài)勢(shì)和避碰時(shí)機(jī)，應(yīng)用灰色理論預(yù)測(cè)模型，以最近會(huì)遇距離及時(shí)間為預(yù)測(cè)參數(shù)，實(shí)際預(yù)測(cè)各目標(biāo)與相對(duì)船舶之間在下一刻的運(yùn)動(dòng)方向[9-10]。近年來(lái)，研究學(xué)者開(kāi)始將人工智能技術(shù)引入到避碰領(lǐng)域，利用類(lèi)神經(jīng)網(wǎng)絡(luò)、模糊理論及遺傳算法等來(lái)進(jìn)行避碰問(wèn)題的研究，進(jìn)而開(kāi)啟了有別于純數(shù)學(xué)模式的軟件計(jì)算自動(dòng)避碰研究領(lǐng)域。同時(shí)針對(duì)海上近距離遭遇的船舶，有學(xué)者提出避碰技術(shù)及路徑規(guī)劃發(fā)展分析，以多目標(biāo)優(yōu)化算法搜尋最佳航線的路線規(guī)劃[11-13]。

綜合以上研究可以發(fā)現(xiàn)，目前關(guān)于船舶避碰的研究已經(jīng)從數(shù)學(xué)模式進(jìn)入到系統(tǒng)化模式，從專(zhuān)家系統(tǒng)進(jìn)入到模糊神經(jīng)網(wǎng)絡(luò)及人工智能與決策支持系統(tǒng)，各方面均獲得了較有價(jià)值的數(shù)學(xué)模型。但目前針對(duì)船舶避碰決策的路徑規(guī)劃研究，大部分是基于檢測(cè)算法視角，同時(shí)采用的優(yōu)化算法存在收斂過(guò)早等問(wèn)題。為此，本研究在粒子群算法及遺傳算法的基礎(chǔ)上，建立了船舶避碰路徑規(guī)劃模型，并選用仿真案例進(jìn)行了驗(yàn)證，克服了優(yōu)化算法收斂過(guò)早等問(wèn)題，以期為上述避碰決策提供科學(xué)合理的理論支持。

1 船舶避碰路徑分析

綜合文獻(xiàn)分析可知[14]，避讓船在船舶領(lǐng)域被侵犯前，就已經(jīng)開(kāi)始采取避讓行動(dòng)。船舶領(lǐng)域?yàn)榘踩嚯x的集合，故采取行動(dòng)后與直行船舶間的最小距離為船舶領(lǐng)域。但因航向資料跳動(dòng)頻繁，本研究依據(jù)避讓行為的階段性特征，改以兩船間最近距離點(diǎn)C為中心，并將最近點(diǎn)前后固定時(shí)間區(qū)域分成三段（如圖1 所示）：AB段為發(fā)現(xiàn)危險(xiǎn)區(qū)域段，此時(shí)還維持原航向，定義為初始航向；BD段為船舶施展避讓動(dòng)作區(qū)域段，定義為避讓航向；待他船安全通過(guò)后，即在D點(diǎn)回復(fù)原航向，將DE段定義為回復(fù)航向。當(dāng)BD段與AB段平均航向差值大于10°，且AB段與DE段誤差在3°以內(nèi)時(shí)，即表示有采取避讓動(dòng)作。

從圖1 的船舶避碰路徑圖解中可以看到，與他船最近距離點(diǎn)C前后固定時(shí)間內(nèi)的航向是避碰路徑的新航向。為了確定避讓的航向以及避讓的DCPA 及TCPA，本研究在此取C點(diǎn)前后各2 min 內(nèi)的航向值做平均；取原航向AB段的避碰動(dòng)作時(shí)間點(diǎn)前的航向值做平均；在回復(fù)原航向DE段，因回復(fù)時(shí)間會(huì)較前段采取避讓動(dòng)作時(shí)間短，故其航向平均時(shí)間的選取可比整段避碰時(shí)間區(qū)域短。

圖1 船舶的避碰路徑分析Fig.1 Analysis of ship’s collision avoidance path

2 船舶碰撞的條件判定

本系統(tǒng)以用戶所設(shè)定的DCPA 和TCPA 數(shù)值，作為判斷是否有碰撞危險(xiǎn)以及何時(shí)開(kāi)始執(zhí)行避碰措施的依據(jù)。當(dāng)兩艘船只目前的DCPA 值小于使用者所設(shè)定的DCPA 值，且TCPA 大于零時(shí)，表示兩船繼續(xù)依此航向前進(jìn)，否則會(huì)有碰撞危險(xiǎn)。在有碰撞危機(jī)的情況下，當(dāng)兩艘船目前的TCPA 值開(kāi)始小于使用者所設(shè)定的TCPA 值時(shí)，開(kāi)始執(zhí)行避碰措施。當(dāng)兩艘船目前的TCPA 值開(kāi)始小于零時(shí)，表示已離開(kāi)兩船間的最接近點(diǎn)，無(wú)碰撞危險(xiǎn)。根據(jù)圖1 中的船舶避碰路徑分析示意圖給出船舶碰撞危險(xiǎn)判定條件，如表1所示。

表1 船舶碰撞危險(xiǎn)度判定條件Tab.1 Determination conditions of ship collision risk

3 船舶避碰算法研究

3.1 PSO算法與GA算法概述

粒子群優(yōu)化算法（Particle Swarm Optimization,PSO）其主要概念源自于動(dòng)物群體行為理論，啟發(fā)于對(duì)鳥(niǎo)群及魚(yú)群集體行動(dòng)的觀察，它們集體行動(dòng)時(shí)通過(guò)個(gè)體之間特殊傳遞信息的方式，使整個(gè)團(tuán)體能夠朝同一方向前進(jìn)，由此尋求群體最大利益。其算法首先產(chǎn)生初始粒子群，每個(gè)粒子都為問(wèn)題的一個(gè)解。而在粒子群搜尋空間中，每個(gè)粒子皆有自己的速度，并根據(jù)既往經(jīng)驗(yàn)及群體行為進(jìn)行演化及修正，逐漸趨近最優(yōu)解[15]。遺傳算法（Genetic Algorithm，GA）是基于生物遺傳演化的概念提出的一種優(yōu)化算法，遺傳算法將這樣的概念隨機(jī)選取，接著用隨機(jī)的突變進(jìn)化方式來(lái)優(yōu)化所要的條件，作為對(duì)船舶碰撞的判斷依據(jù)。這種方法能夠更有效地在一個(gè)已知的空間范圍內(nèi)去搜尋新的優(yōu)化問(wèn)題，并能尋求最優(yōu)解。其核心原理就是達(dá)爾文所提出的進(jìn)化論，適者生存，不適者淘汰[16]。

粒子群優(yōu)化（PSO）算法雖然收斂速度快，但PSO 求解優(yōu)化時(shí)，所有粒子在搜尋時(shí)向擁有最佳適應(yīng)值的粒子方向移動(dòng)，導(dǎo)致粒子的多樣性逐漸降低，而使粒子常常無(wú)法跳脫局部最佳解。因此學(xué)者提出了動(dòng)態(tài)粒子群優(yōu)化算法結(jié)合遺傳算法（PSO-GA），在粒子群求解最優(yōu)解的過(guò)程中結(jié)合遺傳算法，在符合了特定條件的情況下，將粒子及其位移速度復(fù)制并投入交配池中，以交配、突變等機(jī)制作為干擾，使粒子能夠脫離局部最佳解，而得到全局的最佳解，此混合算法比起傳統(tǒng)粒子群算法具有更快的收斂速度，并獲得良好的分群質(zhì)量。在考慮上述兩種算法優(yōu)缺點(diǎn)的基礎(chǔ)上整合多目標(biāo)優(yōu)化求解，從而能夠快速搜尋且脫離局部最佳解，構(gòu)建和優(yōu)化船舶路徑，避免船舶碰撞。

3.2 避碰路徑的編碼及初始化

在船舶的避碰路徑上，為了獲得船舶避讓的TCPA 及DCPA 等關(guān)鍵信息，需要實(shí)時(shí)獲得環(huán)境信息，來(lái)更新船舶的位置及避碰路徑的角度。無(wú)論是在船舶實(shí)時(shí)路徑的調(diào)整還是在初始位置的設(shè)定上，都需要憑借環(huán)境信息，來(lái)確定船舶的位置及避讓的角度。因此，在實(shí)時(shí)路徑的調(diào)整跟初始位置關(guān)系上給定如下方程

式中，n為搜尋參數(shù)，pik為目前位置參數(shù)。

在空間中設(shè)定粒子所要產(chǎn)生的數(shù)量，接著再通過(guò)這一初始位置以及速度去修正路徑移動(dòng)的位置及速度：

給每顆粒子限制其最大移動(dòng)速度vmax及最大移動(dòng)范圍pmax，使粒子的速度跟移動(dòng)不會(huì)超出所設(shè)定的范圍，讓控制粒子能在空間范圍中均勻地分布。

式中，ri為權(quán)重系數(shù)，取值為0 ＜ri＜1。

計(jì)算每顆粒子的適應(yīng)性函數(shù)，如下列公式所述

式中，wmax與wmin分別代表w的最大值及最小值。

隨后利用遺傳算法，去調(diào)整粒子群中的權(quán)重值w。首先決定染色體的范圍以及染色體的總量。計(jì)算每條單一染色體的適應(yīng)性，適應(yīng)性取決于復(fù)制過(guò)程或選擇的染色體，進(jìn)而產(chǎn)生最初親代染色體族群（X1，X2，…，Xn），計(jì)算每條染色體的適應(yīng)性（f（x1）,f（x2）,…,f（xn））。在所有親代染色體中，以適應(yīng)性的高低為依據(jù)，抽選出我們?cè)O(shè)定比例數(shù)量的染色體，再?gòu)倪@些染色體中找出一對(duì)適應(yīng)性最高的染色體進(jìn)行交配。通過(guò)染色體間的交叉運(yùn)算以及突變，來(lái)產(chǎn)生一對(duì)子代的染色體。將新的子代染色體加入新的染色體族群。接著重復(fù)步驟，直到染色體總數(shù)跟初始總數(shù)相等為止。以新的子代染色體取代親代染色體，直到滿足終止條件或是目標(biāo)已經(jīng)達(dá)到優(yōu)化。

再次檢查粒子的速度限制

同時(shí)更新每顆粒子的位置值：

在搜尋范圍中，給每顆粒子一個(gè)更新位置值的限制

最后根據(jù)粒子最佳位置（PGbest）與最佳適應(yīng)參數(shù)（FGbest）對(duì)應(yīng)的非線性優(yōu)化目標(biāo)函數(shù)去確定船舶最終避碰路徑的移動(dòng)方式。

3.3 避碰路徑優(yōu)化目標(biāo)函數(shù)

在船舶避碰的決策過(guò)程中，既要滿足安全性又要滿足經(jīng)濟(jì)性目標(biāo)，安全性目標(biāo)主要是通過(guò)DCPA來(lái)確定，通過(guò)設(shè)定最小的DCPA 來(lái)確定，經(jīng)濟(jì)性通過(guò)轉(zhuǎn)向幅度及避讓里程來(lái)確定，具體的優(yōu)化目標(biāo)函數(shù)為

式中，f1為安全性目標(biāo)函數(shù)值，dDCPA表示距離目標(biāo)船的最近距離，f2為經(jīng)濟(jì)性目標(biāo)函數(shù)值，P為避碰路徑里程，θ為轉(zhuǎn)向幅度，α和β分別是權(quán)重系數(shù)，優(yōu)化目標(biāo)函數(shù)以最小值為優(yōu)，這樣得到的避碰路徑安全性及經(jīng)濟(jì)性最好。

3.4 避碰路徑的程序設(shè)計(jì)

根據(jù)以上的PSO-GA 算法模型及優(yōu)化目標(biāo)函數(shù)，給出本研究的船舶避碰路徑的程序設(shè)計(jì)流程，如圖2所示。

圖2 避碰路徑程序算法流程圖Fig.2 Algorithm flow chart of the collision avoidance path program

4 仿真案例研究

4.1 仿真參數(shù)

本研究采用MATLAB 軟件進(jìn)行仿真分析，仿真平臺(tái)采用INTEL 酷睿3.2 GHz 處理器、內(nèi)存為16 GB的計(jì)算機(jī)。風(fēng)向、水密度等環(huán)境參數(shù)設(shè)置為常規(guī)參數(shù)，本船和目標(biāo)船的參數(shù)如表2所示。結(jié)合給定的船舶參數(shù)，本研究結(jié)合會(huì)遇、交叉以及追越三種情況對(duì)船舶避碰進(jìn)行仿真分析，本船為坐標(biāo)原點(diǎn)，三類(lèi)情況的目標(biāo)船信息如表3所示。

表2 仿真船舶的具體參數(shù)Tab.2 Specific parameters of the simulated ship

表3 本船和目標(biāo)船的不同案例信息Tab.3 Different case information of the standard ship and the sample ship

4.2 仿真結(jié)果分析

為了驗(yàn)證本研究避碰算法的可靠性，對(duì)表3給出的三種船舶避碰情況進(jìn)行分析，參照目標(biāo)船的方位角分布及距離，給出避碰狀況的初始參數(shù)值并輸入算法程序，基于初始化函數(shù)視角對(duì)路徑進(jìn)行初期操作。同時(shí)使用混合遺傳算法優(yōu)化船舶避碰路徑。使用遺傳運(yùn)算符選擇初始群體，使用適度函數(shù)確定遺傳過(guò)程的質(zhì)量，獲得全局優(yōu)化位置，進(jìn)而完成對(duì)船舶避碰路徑的搜索并獲得最優(yōu)避碰操作路徑求解。圖3 為會(huì)遇、交叉和追越三種避碰情況下的船舶避碰路徑軌跡分析以及避碰相距距離分析，圖3（a）～（c）中虛線表示本船和目標(biāo)船保持原航速航行時(shí)的軌跡，實(shí)線為本船的實(shí)際避碰路徑。圖中用圓形表示本船，方形表示目標(biāo)船。圖3（d）為三種避碰情況下的相距距離對(duì)比分析。

圖3 船舶避碰路徑分析Fig.3 Path analysis of ship collision avoidance

根據(jù)圖3 的船舶避碰路徑分析可以看到，在會(huì)遇、交叉及追越三種避碰情況下，船舶均能實(shí)現(xiàn)安全有效的避讓?zhuān)冶茏尩穆窂骄鶠槠交?，也即本船與目標(biāo)船之間的距離均勻變化，滿足了避碰中的安全性要求，同時(shí)從圖3（d）的避碰距離可以看到，最小距離均大于5 km，符合了船舶避讓中的寬避讓要求，同時(shí)從路徑軌跡中可以看到，三種避碰情況下的目標(biāo)船最后都接近回到了初始航向軌跡。可見(jiàn)軌跡偏離原航向幅度并不大，滿足了船舶避讓中的經(jīng)濟(jì)性要求。

4.3 算法對(duì)比分析

從圖3的分析可以看出，本研究算法的避碰路徑計(jì)劃能夠滿足船舶避碰的安全性及經(jīng)濟(jì)性要求，路徑的優(yōu)化性較好，為了進(jìn)一步驗(yàn)證本研究混合遺傳算法的有效性，本研究使用粒子群算法、遺傳算法與本研究算法進(jìn)行對(duì)比，對(duì)會(huì)遇、交叉及追越三種情況進(jìn)行仿真模擬，并就仿真模擬的迭代次數(shù)和平均最優(yōu)值進(jìn)行對(duì)比，結(jié)果如表4所示。

表4 算法的對(duì)比分析Tab.4 Comparative analysis of algorithms

根據(jù)表4 的對(duì)比結(jié)果可以看到：在會(huì)遇、交叉及追越三種避碰情況下，本研究算法均能在25 次以內(nèi)完成迭代，其中會(huì)遇情況下的迭代次數(shù)最少為13 次，這比同樣情況下的粒子群算法及遺傳算法都少了20次以上，算法的收斂速度也得到了較大的提升；同時(shí)從平均最優(yōu)值上也能看到，本研究算法在會(huì)遇、交叉及追越三種避碰情況下的平均最優(yōu)值均小于粒子群算法及遺傳算法，本研究算法的收斂性更好，也即避碰路徑的經(jīng)濟(jì)性及安全性最優(yōu)。綜上結(jié)果，進(jìn)一步驗(yàn)證了本研究算法的有效性及高效性。

5 結(jié) 語(yǔ)

隨著海上運(yùn)輸效率的不斷提升，船舶碰撞已經(jīng)成為影響海上運(yùn)輸安全的重要因素之一，對(duì)于船舶避碰路徑的優(yōu)化決策分析成為目前研究的熱點(diǎn)。本研究綜合考慮船舶的安全性及經(jīng)濟(jì)性要求，將粒子群算法與遺傳算法進(jìn)行整合，并應(yīng)用到船舶避碰路徑的優(yōu)化分析中，從而構(gòu)建船舶避碰路徑規(guī)劃的優(yōu)化模型，并結(jié)合具體案例，在船舶會(huì)遇、交叉及追越三種避碰情況下進(jìn)行仿真分析。分析結(jié)果顯示，本研究給出的粒子群遺傳混合優(yōu)化算法的收斂速度較快，船舶避碰路徑較為平滑且路徑距離及轉(zhuǎn)向角度都較小，能夠同時(shí)滿足船舶避碰的經(jīng)濟(jì)性及安全性要求，相較單一算法具有顯著的有效性及高效性。