基于碳循環優化算法的船舶航路規劃方法

宋冬宇 陳順懷 羅 亮 鄭 龍 楊 達

(武漢理工大學船海與動力工程學院1) 武漢 430063) (高性能船舶技術教育部重點實驗室2) 武漢 430063)

0 引 言

船舶智能航路規劃是船舶實現智能化航行的關鍵技術之一[1].船舶智能航路規劃的主要任務是根據船舶航行時所經過的水域環境情況,按照一定的策略自動尋找一條或多條從起點到終點的可航行路線.目前,國內外學者基于不同的環境建模方法采用各異的智能優化算法對船舶智能航線規劃問題進行相關探索.文獻[2]基于海圖柵格模型將船舶路徑規劃轉化為多目標優化問題應用改進NSGA-III算法求解得到多條可航路線.文獻[3]將勢場合力與距離信息結合改進了傳統蟻群算法的啟發函數,并通過仿真實驗證明了改進蟻群算法能夠提高船舶航行路徑的全局搜索能力.文獻[4]將遺傳算法與非線性規劃方法相結合提出混合遺傳算法針對不同會遇態勢下船舶路徑規劃問題進行了有效的求解.文獻[5]結合人工勢場思想改進通航環境模型,提出A*改進搜索步長及搜索方向限制解決風電場區風機維護船舶路徑規劃問題.綜上所述,智能優化算法用于解決路徑規劃問題是船舶智能航行路徑規劃的研究方向,由于傳統優化算法有過早收斂,容易陷入局部最優,難以兼顧多個優化目標的缺點,因此需要對傳統算法進行改進或探索新的優化算法.

碳循環智能優化算法(carbon cycle optimization algorithm,CCA)是一種模擬碳元素在生物圈與大氣圈中交換循環的智能優化算法,該算法具有全局搜索能力強、收斂速度快的優點,在解決小范圍多目標優化問題時有一定的優勢.文中通過幾何圖法進行環境建模采用一維編碼方式,考慮航行安全性、路線平滑程度和航行總距離,結合碳循環優化算法解決船舶智能航行路徑規劃問題,并通過仿真實驗驗證了本文方法的可行性.

1 問題描述及模型建立

1.1 船舶路徑規劃問題描述

船舶全局航行路徑規劃問題是在環境信息已知的條件下尋找到可航行的路線.在進行規劃時一般僅考慮靜態障礙物,包括大陸、島嶼、巖石等位置固定不動的障礙物.靜態障礙物信息可在進行航行規劃前讀取海圖數據獲取.

在船舶路徑規劃過程中需要對路徑搜索問題設定優化目標.路徑平滑程度與船舶操縱性相關,船舶在航行時進行大角度轉彎時會造成船體傾斜影響船體穩定性同時轉路徑不平滑也會造成航行時間增加.航行總距離關系燃料消耗和碳排放對船舶航行成本和綠色性有重要影響.因此,將航行安全性,路線平滑程度和航行總距離作為優化目標對船舶路徑搜索問題進行求解.

1.2 通航環境模型建立

環境建模采用最多的方法為柵格法及幾何圖法,柵格圖法建模時障礙物的表達依賴于柵格的大小,柵格過大不能準確表達障礙物信息,柵格過小會增加搜索時間不利于大范圍水域的路徑規劃.因此,環境建模時采用幾何圖法將障礙物抽象表示為幾何圖形,采用幾何圖法建模時會導致航線緊挨障礙物邊界,然而船舶在緊挨障礙物行駛時往往吃水不能達到航行要求并且船舶本身具有一定的體積在緊挨障礙物行駛時容易發生碰撞,因此需要對障礙物進行膨脹化處理.障礙物表達示意圖見圖1.

圖1 障礙物表達

圖2 路徑編碼方式

路徑點集編碼時需要將障礙物邊界點坐標以及起點終點坐標進行轉換,轉換公式為

(1)

式中:(x,y),(x′,y′)分為任意Pi在原始坐標系O-xy和新坐標系O-x′y′下的坐標;θ為坐標軸x與直線SG之間的夾角,由x軸轉向直線SG,逆時針方向為正;(xs,ys)為起點S在原始坐標系O-xy下的坐標.在新坐標系下優化得到路徑途徑點集后需通過式(2)反變化到初始坐標系下的坐標.

(2)

1.3 路徑搜索模型建立

考慮航行安全性、路線平滑程度和航行總距離三個優化目標.優化目標函數設定為

minf(R)=w1×Safety(R)+w2×

Smoothness(R)+w3×Length(R)

(3)

式中:w1,w2,w3為權值;Safety(R)為規劃路徑的安全程度;Smoothness(R)為規劃路徑的平滑程度;Length(R)為規劃路徑的長度,分別定義為

(4)

式中:Penal為懲罰值;Collision(PiPi+1)為航段PiPi+1與障礙物的碰撞次數

(5)

φ(Pi)=π-

(6)

式中:φ(Pi)為船舶在該途徑點處的轉向角度;d(PiPi+1)為路徑點PiPi+1間的歐式距離.

(7)

2 碳循環優化算法及其性能分析

2.1 碳循環優化算法

碳循環是碳元素在地球的巖石圈、巖石圈、水圈和大氣圈中交換的現象,并隨著地球的運動不斷循環.在碳循環算法中,模擬了生物圈和大氣圈之間碳元素的循環,示意圖見圖3.

圖3 碳循環過程

根據碳循環過程將優化算法主要分為五個階段:動植物呼吸、動物捕食、動植物死亡、微生物分解以及植物光合作用.

2.1.1動植物呼吸

在碳循環過程開始時,碳元素以含碳有機物的形式存在于動植物體內,其中部分含碳有機物被用于動植物呼吸作用.動植物通過呼吸作用中的逐步反應將這部分含碳有機物分解為體積更小,結構更簡單的含碳無機物(主要為二氧化碳)釋放到大氣中,大氣中的碳元素位置分布具有隨機性.該過程的數學模型為

(8)

(9)

2.1.2動物捕食

在碳循環算法中,將動物捕食階段根據碳元素的轉移過程進行簡化,在該階段只考慮動植物之間的捕食過程不考慮動物間的捕食過程.在呼吸階段植物中部分碳元素由于呼吸作用由含碳有機物轉化為二氧化碳回到大氣圈中,在動物捕食階段,剩余以含碳機物形式存在于植物中碳元素將通過動物捕食行為部分轉移到動物體內以含碳有機物的形式繼續存在.該過程的數學模型為

(10)

2.1.3動植物死亡

在碳循環過程中,動植物死亡的過程可視為將體內含碳有機物向分解者轉移的過程.同時,動植物死亡與時間直接相關,因此隨著算法循環迭代碳元素的轉移會發生改變.

(11)

(12)

(13)

式中:maxt為最大迭代次數;tnow為當前迭代次數;f為控制系數,一般設為1.5,隨著迭代次數的增加γ從f線性下降到0.

2.1.4微生物分解

在動植物死亡后,體內留存的含碳有機物通過微生物的分解作用被分解為二氧化碳并將其釋放到大氣圈中,該過程使得生物圈中的碳元素重新回到大氣圈中.分解過程數學模型為

(14)

2.1.5植物光合作用

大氣中的碳元素主要通過植物進行光合過程進入生物圈,在現實生活中通常希望植物吸收更多的二氧化碳優化環境質量.植物通常貼近地表,在吸收大氣中二氧化碳時通常選擇靠近自身位置的二氧化碳分子,因此通過評價函數找出適應度更好即更靠近自身位置的碳元素進行光合作用.該過程使得大氣圈中碳元素進入到生物圈中.其數學模型為

(15)

在碳循環算法中,植物光合作用時對大氣中的二氧化碳分子應用適應度函數進行評估,選擇適應度最好即位置最靠近自身的二氧化碳分子作為植物光合作用合成含碳有機物的原料.

2.2 算法測試實驗

2.2.1測試實驗一

在實驗一中使用的測試函數在表1中提供,相對應的函數圖像見圖4,所有函數的維度均為30.將碳循環算法的結果與四種典型的優化算法進行了比較,這四種算法分別是PSO算法,GA算法,GWO算法和ALO算法,PSO和GA的結果通過Matlab 2019a中的PSO和GA工具箱進行計算.本實驗中使用的ALO和GWO算法的源代碼下載于http://www.alimirjalili.com/ALO.html 和http://www.alimir-jalili.com/GWO.html.對于PSO、GA、ALO和GWO,種群規模為30,最大運算次數為1 000;對于CCA,碳元素規模大小等于30,最大迭代次數為1 000.所有考慮的算法在每個基準函數上獨立運行30次.統計結果(ave和std)見表2.

圖4 單峰測試函數對應的函數圖像

表1 單峰基礎測試函數

表2 單峰基準函數優化結果比較(30維)

圖5中展示了收斂曲線,由圖5可知:碳循環優化算法在單峰基準函數上比其他算法具有更高的收斂速度.在迭代的初始階段,碳循環優化算法能夠更快速地向最優值區域進行收斂.該算法在計算上是可用于解決優化問題的.

圖5 對一些單峰基準測試函數CCA和其他算法的收斂性分析

2.2.2測試實驗二

在實驗2中,考慮了六個維度為30的多峰測試函數,并與實驗1中使用的四種算法(PSO、GSA、GWO和ALO)進行了比較.這些函數的函數圖像對應于圖6,具體的函數表達式對應表3.總體種群規模和最大迭代次數與實驗1中的相同.表4為30次獨立運行的平均實驗結果,圖7為基準函數F9、F10和F11的收斂曲線.

圖7 對一些多峰基準測試函數CCA和其他算法的收斂性分析

表3 多峰基礎測試函數

由圖6可知:多峰函數有許多局部最優解,這些局部最優解的數量隨著函數維數的增加呈指數增長.由表4可知:除了F8函數外,CCA算法的性能優于所有算法.該算法可以避免局部最優,并在多模態基準函數上提供許多有競爭力的結果.

圖6 多峰測試函數對應的函數圖像

由上可知:CCA算法的效果比較顯著.從收斂曲線的角度來看,CCA總是在測試函數中快速向最優解移動.這可以與算法進行比較.

3 船舶航行路徑規劃流程

碳循環優化算法的船舶航行路徑規劃流程圖見圖8.

圖8 技術路線圖

4 仿真驗證及分析

選取舟山附近水域島嶼較多的復雜水域環境構建環境模型,所選水域見圖9.

圖9 舟山水域地圖

通過提取海圖數據得到障礙物邊界信息,將多邊形邊界根據船長進行膨脹處理.經過簡化及膨脹處理后該水域的環境模型見圖10.

圖10 幾何圖法生成障礙物模型

基于構建好的環境模型,分別選取遺傳算法(GA),基于膜系統的擴散算法(DAPS),鯨群優化算法(WOA)與文中的碳循環優化算法(CCA)在相同的仿真環境下進行結果對比,DAPS為武漢理工大學高性能船舶技術教育部重點實驗室汪皓開發的一種群智能優化算法[6-7].四種算法種群數量設為50,最大迭代次數設為200.規劃得到的路徑見圖11.該結果為在不同算法中運行30次的平均結果.表5 為應用四種算法所生成的規劃航行路徑在安全性,航行距離及適航性的數據.

圖11 四種算法生成的規劃路徑

表5 算法結果對比

在環境建模時,對障礙物進行了膨脹,因此四種算法生成的航行路徑均與障礙物有一定的安全距離都能滿足安全航行的需求[8-9].根據地圖測距,起點至終點的直線距離為47 km,碳循環優化算法生成的航行路徑總距離為47.5 km,相比其它算法優化效果提高2.1%以上,同時所生成的路徑無較大轉角船舶沿規劃航線航行時更容易操縱.通過上述分析表明,本文基于碳循環優化算法可以正確的、滿足多種要求的自動生成船舶航行路徑且求解得到的路徑更優.

5 結 束 語

本文提出一種基于碳循環優化算法的船舶智能航行路徑規劃方法,說明了方法的基本思想、設計內容以及實現過程,并且通過仿真實驗證明該方法可以滿足多個準則下自動生成滿足約束的船舶航行路徑,而且得到的規劃方案效果較傳統規劃方法.另外,本文研究尚有不足,如沒有考慮更多航行影響因素(如風、浪、流、能見度等)達到更符合真實航行環境的航行路徑規劃效果,后續有待進一步研究.