基于改進(jìn)SPEA2 算法的多目標(biāo)航線優(yōu)化

王 軍，蔣金陽，牛 壯

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

0 引 言

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

近年來，多目標(biāo)航線優(yōu)化得到了較多關(guān)注，它可以同時(shí)針對(duì)多個(gè)目標(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)象。特別是隨著迭代步長(zhǎng)的增加，搜索樣本量的限制還可能導(dǎo)致算法陷入局部最優(yōu)。

本文針對(duì)SPEA2 在解決多目標(biāo)航線優(yōu)化問題中存在的收斂速度慢和易陷入局部最優(yōu)的現(xiàn)象進(jìn)行改進(jìn)。通過Dijkstra 算法搜索的可行解加入到初始種群中作為引導(dǎo)以加快算法尋優(yōu)的效率；采用更精細(xì)化的選擇過程保證精英個(gè)體可繼續(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)度分配策略中，同時(shí)考慮了種群中的顯性個(gè)體和隱性個(gè)體，提高了全局搜索能力；計(jì)算最近相鄰個(gè)體的密度提高搜索精度；采用新的存檔截?cái)喾椒?，保證邊界解得以保留。

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

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

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

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

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

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

若2 個(gè)個(gè)體的基因值在t位置相等，則ID1(t)-ID2(t)=0 ，否則為1。 當(dāng)r≥K，個(gè)體間差異較大，利用交叉操作來進(jìn)行個(gè)體間有用信息的交換，來產(chǎn)生更多較好的個(gè)體。相反，當(dāng)r＜K時(shí)，個(gè)體相似度較高，互相值得學(xué)習(xí)的信息較少，需要對(duì)二者進(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ò)展航路點(diǎn)，從出發(fā)點(diǎn)開始，在大圓航線上每隔距離 ε記錄一次參考點(diǎn)，其中 ε代表天氣預(yù)報(bào)的空間分辨率。以每個(gè)參考點(diǎn)為垂足，生成垂直于當(dāng)前大圓路線方向的其他路徑點(diǎn)，航路點(diǎn)應(yīng)只覆蓋在船舶可能行駛的區(qū)域內(nèi)。為避免船舶大幅度轉(zhuǎn)彎和前往無效的航路點(diǎn)而造成不必要的成本消耗，需在系統(tǒng)中構(gòu)建連接關(guān)系來保證船舶只能在相鄰2 個(gè)階段中指定的航路點(diǎn)間移動(dòng)。本文規(guī)定船舶的航行方向分為直行、左轉(zhuǎn)和右轉(zhuǎn)，因此系統(tǒng)中從任意一個(gè)路徑點(diǎn)出發(fā)有可能到達(dá)下一階段的3 個(gè)不同航路點(diǎn)。

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

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

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

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

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

2.3 種群更新

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

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

2.4 交叉、變異操作

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

2.5 檢查終止條件

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

3 仿真實(shí)驗(yàn)與分析

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

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

船舶出發(fā)時(shí)間設(shè)定為每月6 號(hào)上午11：00，選擇3500 TEU 的集裝箱船進(jìn)行仿真，其標(biāo)準(zhǔn)排水量為47202.48 t。為驗(yàn)證算法的性能，將本文算法與Dijkstra、NMOEA 和SPEA2 進(jìn)行比較，其中針對(duì)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

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

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