王 軍，蔣金陽，牛 壯

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院, 遼寧 大連 116026)

0 引 言

隨著海洋運(yùn)輸在國際商品交換中所占比重越來越大，船舶航線優(yōu)化被提到了重要的地位。該領(lǐng)域研究的問題是在考慮風(fēng)浪環(huán)境條件的情況下，尋找給定航行的最優(yōu)路徑和航速，目標(biāo)通?？紤]最小航行時間、燃油消耗或通行風(fēng)險[1]。

近年來，多目標(biāo)航線優(yōu)化得到了較多關(guān)注，它可以同時針對多個目標(biāo)進(jìn)行優(yōu)化，進(jìn)而產(chǎn)生大量的權(quán)衡解，決策者可根據(jù)當(dāng)前的需要確定最終的航行方案。目前，進(jìn)化算法在解決該問題上取得了廣泛應(yīng)用[2-3]，主要包括經(jīng)典算法SPEA2[4]、NSGA-Ⅱ[5]以及一些改進(jìn)的算法NMOEA[6]、SPEA2+[7]。然而，由于規(guī)劃過程中存在龐大的樣本量和優(yōu)化空間，收斂效率慢成為普遍現(xiàn)象。特別是隨著迭代步長的增加，搜索樣本量的限制還可能導(dǎo)致算法陷入局部最優(yōu)。

本文針對SPEA2 在解決多目標(biāo)航線優(yōu)化問題中存在的收斂速度慢和易陷入局部最優(yōu)的現(xiàn)象進(jìn)行改進(jìn)。通過Dijkstra 算法搜索的可行解加入到初始種群中作為引導(dǎo)以加快算法尋優(yōu)的效率；采用更精細(xì)化的選擇過程保證精英個體可繼續(xù)參與進(jìn)化；提出新的交叉和變異策略，有效提升了種群質(zhì)量。

1 SPEA2 算法改進(jìn)

1.1 SPEA2 的基本思想

Zitzler[4]提出的強(qiáng)度Pareto 進(jìn)化算法（SPEA2）是一種多目標(biāo)進(jìn)化算法，具有良好的搜索性能，它包含一些重要的操作，例如在適應(yīng)度分配策略中，同時考慮了種群中的顯性個體和隱性個體，提高了全局搜索能力；計算最近相鄰個體的密度提高搜索精度；采用新的存檔截斷方法，保證邊界解得以保留。

1.2 改進(jìn)工作的動機(jī)

大多數(shù)優(yōu)化算法無法找到更高質(zhì)量的解，主要因為它們工作效率較低。例如，當(dāng)種群中的大多數(shù)解處于非支配階段時，粗糙的選擇方法將剝奪優(yōu)勢精英繼續(xù)參與進(jìn)化的機(jī)會，導(dǎo)致優(yōu)化結(jié)果停滯或更差。同時，交叉機(jī)制作為進(jìn)化算法中生成新個體和擴(kuò)展解空間的一種有效方法，還尚未被有效探索。尤其當(dāng)種群中個體間差異較小時，算法易進(jìn)入停滯狀態(tài)，這時應(yīng)增大變異概率，通過改變種群內(nèi)個體的部分基因形成新的個體，以跳出局部最優(yōu)。

1.3 SPEA2 方法的改進(jìn)

在種群更新階段，改進(jìn)后的算法只允許非支配個體加入到外部歸檔集A，位于Pareto 前沿端點上的2 個解被強(qiáng)制保留，防止算法陷入局部最優(yōu)。并且從第T(T≥2) 代開始，將種群P中所有非支配個體與AT-1中的個體進(jìn)行比較，支配AT-1中任何一方的個體將被遷移到AT中。

在交叉和變異階段，事先給出比較值K，并與選中個體的相似度r進(jìn)行比較，K的計算公式為：

式中：IDi為組成個體i的基因序列；N為序列的長度；t表示基因值的位置，函數(shù)U表示n個個體的基因序列在t位置的非重復(fù)值的數(shù)量。因此，當(dāng)種群內(nèi)個體的基因序列都相同時，K=1；基因序列都不同時，K=1/n。相似度r的計算公式為：

若2 個個體的基因值在t位置相等，則ID1(t)-ID2(t)=0 ，否則為1。 當(dāng)r≥K，個體間差異較大，利用交叉操作來進(jìn)行個體間有用信息的交換，來產(chǎn)生更多較好的個體。相反，當(dāng)r＜K時，個體相似度較高，互相值得學(xué)習(xí)的信息較少，需要對二者進(jìn)行變異操作以跳出局部最優(yōu)，增大搜索空間。

2 基于改進(jìn)SPEA2 的船舶航線優(yōu)化

2.1 航線優(yōu)化相關(guān)模型的構(gòu)建

2.1.1 航行環(huán)境建模

本文采用大圓航線作為網(wǎng)格系統(tǒng)的參考路徑來擴(kuò)展航路點，從出發(fā)點開始，在大圓航線上每隔距離 ε記錄一次參考點，其中 ε代表天氣預(yù)報的空間分辨率。以每個參考點為垂足，生成垂直于當(dāng)前大圓路線方向的其他路徑點，航路點應(yīng)只覆蓋在船舶可能行駛的區(qū)域內(nèi)。為避免船舶大幅度轉(zhuǎn)彎和前往無效的航路點而造成不必要的成本消耗，需在系統(tǒng)中構(gòu)建連接關(guān)系來保證船舶只能在相鄰2 個階段中指定的航路點間移動。本文規(guī)定船舶的航行方向分為直行、左轉(zhuǎn)和右轉(zhuǎn)，因此系統(tǒng)中從任意一個路徑點出發(fā)有可能到達(dá)下一階段的3 個不同航路點。

2.1.2 目標(biāo)函數(shù)設(shè)計

目標(biāo)函數(shù)是反映航線質(zhì)量的性能指標(biāo)，是優(yōu)化的最終目的。本文以船舶航行時間T和燃油消耗F為優(yōu)化目標(biāo)，建立多目標(biāo)優(yōu)化函數(shù)：

式中：n-1為 航段總數(shù)；Si、Vi、 (Te)i分別為船舶在第i階段的航行距離、實際航行速度和主機(jī)有效推力。在動力不變的情況下，由于風(fēng)浪的干擾，船舶實際航行速度較靜止?fàn)顟B(tài)下的速度有所下降，本文采用文獻(xiàn)[8]中的經(jīng)驗公式，計算在特定的氣象環(huán)境和設(shè)定的服務(wù)航速下船舶的失速損失。

2.2 創(chuàng)建初始種群

初始種群P0在求解的質(zhì)量和效率上起著很大作用，如果P0包含盡可能多的有利個體，它們可以在迭代過程中不斷引導(dǎo)結(jié)果靠近帕累托邊界，同時迭代次數(shù)會在大程度上減少。為保證解的多樣性和優(yōu)良性，采用以下3 種方式來生成P0：一是采用隨機(jī)遍歷的方法，在航行區(qū)域內(nèi)隨機(jī)生成一條滿足網(wǎng)格系統(tǒng)連接關(guān)系的航線，并隨機(jī)賦予一個船舶主機(jī)功率。二是采用大圓航線作為一部分初始種群，并同樣賦予不同的船舶主機(jī)功率。三是采用Dijkstra 算法尋找單目標(biāo)優(yōu)化下的最佳航線。

2.3 種群更新

種群中個體質(zhì)量的好壞通過適應(yīng)度函數(shù)評定。SPEA2 采用細(xì)粒度的適應(yīng)度分配策略，在計算種群P中個體的適應(yīng)度R(i) 時，種群和外部歸檔集A的個體都考慮在內(nèi)。而且R值越小，說明支配該個體的個體越少，R(i)=0 表示個體i為非支配解，適應(yīng)度計算方法為：

當(dāng)外部歸檔集 |AT|＜Q(預(yù)設(shè)值) 時，通過k臨近算法估算個體密度值，并將特征空間最鄰近的個體逐個剔除，直至 |AT|=Q；相反，若外部歸檔集 |AT|＜Q，則根據(jù)適應(yīng)度排序選擇前Q-|AT|個支配解，直至|AT|=Q。

2.4 交叉、變異操作

交叉通過隨機(jī)選擇2 個個體共同經(jīng)過的航路點a（起終點除外），將父代1 從第1 個至第a個航路點的位置信息都復(fù)制到子代，第a+1至最后1 個航路點的位置信息從父代2 上復(fù)制。在變異個體上隨機(jī)選擇一個變異點，使該變異點處的船舶路徑隨機(jī)發(fā)生改變。操作后的子代和父代共同組成新的種群繼續(xù)參與進(jìn)化。

2.5 檢查終止條件

隨著迭代步數(shù)的增加，與最大迭代次數(shù)進(jìn)行比較。如果超過最大迭代次數(shù)，則終止算法，否則返回種群更新繼續(xù)完成種群進(jìn)化。

3 仿真實驗與分析

仿真實驗設(shè)定的航線起點為橫濱附近（35.25N，141.75E），終點為舊金山附近（37N，122W），分別在3 個月份下進(jìn)行多目標(biāo)航線優(yōu)化實驗，航行環(huán)境比較結(jié)果如表1 所示。

表1 不同月份下航行環(huán)境的比較Tab.1 Comparison of sailing conditions in different months

船舶出發(fā)時間設(shè)定為每月6 號上午11：00，選擇3500 TEU 的集裝箱船進(jìn)行仿真，其標(biāo)準(zhǔn)排水量為47202.48 t。為驗證算法的性能，將本文算法與Dijkstra、NMOEA 和SPEA2 進(jìn)行比較，其中針對3 種進(jìn)化算法，設(shè)定初始種群容量為34，外部種群容量6，交叉概率0.8，變異概率0.2，最大迭代次數(shù)100，求解出的Pareto 前沿面如圖1～圖3 所示。

圖1 2018 年7 月的Pareto 前沿面Fig.1 Pareto frontier in July 2018

圖2 2018 年4 月的Pareto 前沿面Fig.2 Pareto frontier in April 2018

圖3 2018 年1 月的Pareto 前沿面Fig.3 Pareto frontier in January 2018

實驗結(jié)果顯示，進(jìn)化算法求得的解在時間和油耗上均優(yōu)于Dijkstra 算法得到的結(jié)果。另一方面，本文提出的算法在收斂性上優(yōu)于NMOEA 和SPEA2，且隨著氣象的變差，優(yōu)勢表現(xiàn)越明顯。從多目標(biāo)進(jìn)化算法性能評價指標(biāo)-超體積（HV）[9]的角度對結(jié)果進(jìn)行數(shù)學(xué)分析。表2 比較了3 種進(jìn)化算法求得解的HV值，HV 值越高，群體中個體的綜合表現(xiàn)越好。將（1120，260）做為參考點進(jìn)行HV 的計算，結(jié)果顯示本文提出的算法綜合性能最高，其次SPEA2，最差的是NMOEA。圖4～圖6 分別展示了3 個月份下的Pareto 航線集，對于海況較好的7 月和4 月，該月份下的航線集主要是以Dijkstra 求得的航線為基礎(chǔ)并對其優(yōu)化。優(yōu)化部分主要集中在航線的后半段，但在海況較差的1 月份，它的Pareto 航線集不僅包含Dijkstra 的結(jié)果，還包括隨機(jī)路線，這些路線光滑度較低，但在省油和省時方面仍優(yōu)于Dijkstra 結(jié)果。

圖4 2018 年7 月的Pareto 航線集Fig.4 Pareto route set in July 2018

圖5 2018 年4 月的Pareto 航線集Fig.5 Pareto route set in April 2018

圖6 2018 年1 月的Pareto 航線集Fig.6 Pareto route set in January 2018

表2 進(jìn)化算法的HV 結(jié)果比較Tab.2 Comparison of HV results of evolutionary algorithms

4 結(jié) 語

針對多目標(biāo)航線優(yōu)化問題，本文構(gòu)建了燃油成本和航行時間最小的雙目標(biāo)優(yōu)化模型，并設(shè)計了基于SPEA2 的引導(dǎo)性多目標(biāo)進(jìn)化算法。通過在初始種群中加入Dijkstra 算法得到的單目標(biāo)優(yōu)化結(jié)果，以此作為引導(dǎo)，并在種群更新階段進(jìn)行改進(jìn)，保證了具有代表性的精英個體繼續(xù)參與進(jìn)化。為避免種群優(yōu)良基因的破壞以及陷入局部最優(yōu)，對交叉和變異機(jī)制進(jìn)行改進(jìn)。最后以太平洋航線為例，在不同海況條件下進(jìn)行仿真實驗，驗證了算法的高效性。與NMOEA 和SPEA2 多目標(biāo)進(jìn)化算法的求解結(jié)果進(jìn)行對比，證明本文算法具有較好的收斂性和全局尋優(yōu)能力。