基于隱馬爾可夫鏈的自適應(yīng)MODE及應(yīng)用

崔彩霞，畢超超，范勤勤，3

1.上海海事大學(xué) 物流科學(xué)與工程研究院，上海201306

2.上海海事大學(xué) 物流研究中心，上海201306

3.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海200240

差分進(jìn)化算法[1]是由Storn和Price于1997年提出的一種高效元啟發(fā)式搜索算法。由于該算法易于實現(xiàn)、尋優(yōu)性能強、魯棒性好，從而吸引了國內(nèi)外學(xué)者的關(guān)注與研究，并被用于求解各領(lǐng)域的優(yōu)化問題。

除求解單目標(biāo)優(yōu)化問題外，差分進(jìn)化算法也被用來求解各類多目標(biāo)優(yōu)化問題。為提高其性能，各種多目標(biāo)差分進(jìn)化算法（Multi-Objective Differential Evolution Algorithm，MODE）被不斷提出。比如Kukkonen 等人[2]于2005 年提出的GDE3（The Third Evolution Step of Generalized Differential Evolution）算法是其中一種較為典型的多目標(biāo)差分進(jìn)化算法，并被用于解決有約束的多目標(biāo)優(yōu)化問題。該算法對變異策略進(jìn)行改進(jìn)，并且增加新的選擇規(guī)則。張春美等人[3]提出一種參數(shù)自適應(yīng)的分布式差分進(jìn)化算法（Distributed Differential Evolution Algorithm with Adaptive Parameters，APDDE）。該算法根據(jù)馮·諾依曼拓?fù)浣Y(jié)構(gòu)將初始種群分為多個子種群，用子種群的優(yōu)秀個體代替其鄰域子種群中的較差個體，并根據(jù)個體適應(yīng)值的變化情況對種群內(nèi)各個體分配不同的F和CR，從而實現(xiàn)參數(shù)自適應(yīng)。結(jié)果表明該算法在收斂速度和求解質(zhì)量上都有所提高。李牧東等人[4]于2016年提出一種基于最優(yōu)高斯隨機游走和個體篩選策略的差分進(jìn)化算法（Differential Evolution Based on Optimal Gaussian Random Walk and Individual Selection Strategies）。在該算法中，首先利用最優(yōu)高斯隨機游走策略產(chǎn)生新的種群；然后僅對種群中性能較差的個體進(jìn)行交叉和變異操作，并使用改進(jìn)的個體篩選策略來產(chǎn)生新個體；最后，得到一個新種群。實驗結(jié)果表明該算法具有較快的收斂速度和較好的魯棒性。Fan 等人[5]提出一種基于性能指標(biāo)的多目標(biāo)差分進(jìn)化算法（Multi-Objective Differential Evolution with Performance-Metricbased Self-adaptive Mutation Operator，MODE-PMSMO）。該算法采用一種多目標(biāo)性能評價指標(biāo)來指導(dǎo)變異策略的動態(tài)調(diào)整。所得結(jié)果表明MODE-PMSMO 能夠根據(jù)進(jìn)化進(jìn)程自適應(yīng)得到合適的變異策略來求解相應(yīng)類型的多目標(biāo)優(yōu)化問題。候瑩等人[6]提出了一種基于參數(shù)動態(tài)調(diào)整的多目標(biāo)差分進(jìn)化算法（Adaptive Multi-Objective Differential Evolution Algorithm Based on the Dynamic Parameters Adjustment，AMODE）。該算法通過實現(xiàn)控制參數(shù)自適應(yīng)的方式來提高其求解多目標(biāo)優(yōu)化問題的能力。實驗結(jié)果表明該算法能夠有效提高所得帕累托前沿的收斂性和多樣性。Lin等人[7]于2018年提出一種具有多種差分進(jìn)化策略的自適應(yīng)免疫啟發(fā)多目標(biāo)算法（An Adaptive Immune-inspired Multi-Objective Algorithm with Multiple Differential Evolution Strategies）。該算法將差分變異算子融入到多目標(biāo)免疫算法中，結(jié)果表明所提算法有效提高了解集的多樣性。艾兵等人[8]提出一種基于多策略和排序變異的多目標(biāo)差分進(jìn)化算法（Multi-Objective Differential Evolution Algorithm with Multi-strategy and Ranking-based Mutation，MODEMERM）。該算法利用基于多策略和排序變異的DE 算子進(jìn)行變異操作。所得結(jié)果表明MODE-MERM采用多種變異策略能夠平衡解集的收斂性與多樣性。童旅楊等人[9]于2019 年提出一種基于分解和多策略變異的多目標(biāo)差分進(jìn)化算法（Multi-Objective Differential Evolution Algorithm Based on Decomposition and Multi-Strategy Mutation，MODE/DMSM）。該算法利用改進(jìn)的切比雪夫分解方法將多目標(biāo)優(yōu)化問題分解成多個單目標(biāo)子問題；并采用多策略變異的方法來求解各個子問題。實驗結(jié)果表明MODE/DMSM使用多個差分變異算子能夠得到多樣性和收斂性較好的解集。

雖然眾多學(xué)者對多目標(biāo)差分進(jìn)化算法已進(jìn)行大量研究，但是在其控制參數(shù)和策略自適應(yīng)方面仍存在一些問題。比如，現(xiàn)有多目標(biāo)差分進(jìn)化算法的自適應(yīng)方法一般不具有預(yù)測功能，因此這會大大降低其所得控制參數(shù)和策略的適應(yīng)性。為解決該問題，本研究提出一種基于隱馬爾可夫鏈的自適應(yīng)多目標(biāo)差分進(jìn)化算法（Selfadaptive Multi-Objective Differential Evolution Algorithm Based on Hidden Markov Chain，SMODE-HMC）。在SMODE-HMC 算法中，隱馬爾可夫鏈方法被分別用來預(yù)測控制參數(shù)和變異策略的演化趨勢，從而實現(xiàn)自適應(yīng)調(diào)整。通過16 個基準(zhǔn)多目標(biāo)優(yōu)化問題的測試，結(jié)果表明所提算法的整體性能要好于其他9 種比較算法。另外，本研究還將SMODE-HMC 算法用于求解海鐵聯(lián)運多目標(biāo)優(yōu)化問題，得到令人滿意的結(jié)果。

1 預(yù)備知識

1.1 多目標(biāo)優(yōu)化問題

在現(xiàn)實世界中，多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problems，MOPs）廣泛存在于各個領(lǐng)域，如多目標(biāo)柔性車間作業(yè)調(diào)度[10]、電動車充電站規(guī)劃[11]等問題。通常情況下，多目標(biāo)優(yōu)化問題中的各個子目標(biāo)相互矛盾且不可調(diào)和。不失一般性，多目標(biāo)優(yōu)化問題的數(shù)學(xué)形式表示如下：

其中，x為決策向量；Ω∈RD為D維決策空間；m表示優(yōu)化目標(biāo)數(shù)量。其他一些相關(guān)概念如下：

定理1（支配關(guān)系）向量p支配另一個向量q（記作p?q）的條件是：如果對?w∈{1,2,…,k},pw≤qw，并且p≠q。

定理2（Pareto 最優(yōu)解集）一個向量x*∈Ω，如果不存在其他向量x∈Ω，使得F(x)?F(x*)，那么就稱x*為Pareto解，x*的集合（記作X*）被稱為Pareto最優(yōu)解集。

定理3（Pareto 前沿）多目標(biāo)優(yōu)化問題中，Pareto 最優(yōu)解集中的解對應(yīng)的目標(biāo)向量被稱為Pareto前沿（Pareto Front，PF）。

1.2 多目標(biāo)性能評價指標(biāo)

多目標(biāo)性能評價指標(biāo)能夠?qū)λ媒饧|(zhì)量做出評判，通常使用的方法有世代距離（Generational Distance，GD）、空間分布評價方法（Spacing，SP）與反向世代距離（Inverted Generational Distance，IGD）[12-14]。其中GD是收斂性指標(biāo)，評價的是所得解集與真實Pareto前沿的逼近程度；SP 是多樣性指標(biāo)，評價的是所得解集在真實Pareto前沿上分布的均勻性；IGD是綜合性指標(biāo)，評價的是所得解集的收斂性和多樣性。具體計算公式如下：

（1）GD

式中，PF*表示一組沿著真實PF均勻分布的解集；C表示算法得到的PF逼近；d(z,PF*)表示z與PF*最近點的歐幾里德距離；|C|表示C中解的數(shù)量。GD 值越小，說明所得解集的收斂性越好，與PF越逼近。

（2）SP

式中，k表示非支配解的個數(shù)；di表示第i個解與其他解的最小歐幾里德距離；dˉ表示所有di的平均值。SP值越小，說明所得解集的均勻性越好。值得注意的是該性能指標(biāo)并未對所得解集的延展性進(jìn)行評價。

（3）IGD

式中，d(z*,C)表示z*與C最近點的歐幾里德距離；|PF*|表示PF*中解的數(shù)量。IGD值越小，說明所得目標(biāo)解集的收斂性和多樣性就越好。

1.3 標(biāo)準(zhǔn)差分進(jìn)化算法

差分進(jìn)化算法是一種高效的元啟發(fā)式搜索算法，標(biāo)準(zhǔn)差分進(jìn)化算法主要有以下幾個步驟：

（1）初始化

設(shè)置參數(shù)，例如初始化縮放因子F、交叉概率CR、種群規(guī)模PS和最大迭代次數(shù)等。同時，在定義域(Ω)內(nèi)，生成初始化種群。

（2）變異

種群中的個體通過變異策略生成變異個體，差分進(jìn)化算法常用的變異策略如下所示：

式中，D為多目標(biāo)優(yōu)化問題的維度，Rj為[0，1]之間均勻隨機數(shù)，jrand為[1,D] 范圍內(nèi)的一個隨機整數(shù)。

（4）選擇

選擇試驗個體與種群個體中較優(yōu)個體進(jìn)入下一代，選擇方式如下：

1.4 隱馬爾可夫模型

隱馬爾可夫模型（Hidden Markov Model，HMM）是馬爾可夫鏈（Markov Chains，MC）的其中一種方法。在隱馬爾可夫模型中，最難確定的是隱含狀態(tài)參數(shù)。雖然HMM的隱藏狀態(tài)不能被直接觀測到，但是隱藏狀態(tài)會通過一定的概率分布在外部狀態(tài)中被觀測到。因此，隱馬爾可夫模型是一個隱藏和非隱藏的雙重隨機過程，第一重是一個隱藏狀態(tài)轉(zhuǎn)移到另一個隱藏狀態(tài)的隨機過程，這是不可被觀測的；第二重是一個隱藏狀態(tài)到外部展現(xiàn)的隨機過程，這是可以被觀測的。隱馬爾可夫模型的一些相關(guān)概念如下[15]。

隱馬爾可夫模型的圖結(jié)構(gòu)如圖1 所示。其中{s1,s2,…,sN}是HMM 的狀態(tài)序列，即隱藏的馬爾可夫鏈。其中st∈S表示t時刻模型的狀態(tài)。S={g1,g2,…}表示有K1個可能取值的狀態(tài)空間；{o1,o2,…,oN}是HMM 的觀測序列，其中ot∈O表示t時刻模型的觀測值。{h1,h2,…} 表示O的取值范圍。

圖1 隱馬爾可夫模型

在HMM中，各個隱藏狀態(tài)間的轉(zhuǎn)換概率稱為狀態(tài)轉(zhuǎn)移概率，通常記為矩陣，其中：

模型在初始狀時刻各狀態(tài)出現(xiàn)的概率即為初始狀態(tài)概率，記為π={π1,π2,…}，且=1。

綜上，HMM可用其參數(shù)λ={A,B,π} 來指代。

2 基于隱馬爾可夫鏈的自適應(yīng)多目標(biāo)差分進(jìn)化算法

研究表明隱馬爾可夫模型具有良好的預(yù)測能力[16]。因此，為提高多目標(biāo)差分進(jìn)化算法的性能，提出一種基于隱馬爾可夫鏈的自適應(yīng)多目標(biāo)差分進(jìn)化算法。在該算法中，將父代種群、變異種群和交叉種群轉(zhuǎn)換為概率作為隱馬爾可夫模型中的參數(shù)，并通過計算最大似然估計值實現(xiàn)對控制參數(shù)的自適應(yīng)更新；另外，通過改進(jìn)的IGD指標(biāo)不斷更新隱馬爾可夫模型中的參數(shù)，從而不斷更新通過隱馬爾可夫模型生成的策略鏈，實現(xiàn)變異策略選擇的自適應(yīng)；而且為保證算法前期偏向于全局搜索和后期偏向于局部搜索，本文采取多項式交叉和模擬二進(jìn)制交叉的混合交叉策略。隱馬爾可夫模型所需參數(shù)的初始值均設(shè)置為等概率。控制參數(shù)自適應(yīng)與變異策略自適應(yīng)的具體實現(xiàn)方式見以下部分。

2.1 控制參數(shù)自適應(yīng)

進(jìn)化過程中，種群隨迭代次數(shù)的變化情況與隱馬爾可夫模型內(nèi)部過程類似[16]。在該部分，將個體的狀態(tài)變化情況分為三種：優(yōu)、中、差。優(yōu)表示當(dāng)前個體支配比較個體，中表示當(dāng)前個體與比較個體互不支配，差表示比較個體支配當(dāng)前個體。

在每一次迭代過程中，種群中每個個體都有與其相對應(yīng)的變異縮放因子與交叉概率。對比個體的實際狀態(tài)序列與最優(yōu)隱藏序列得到相應(yīng)行向量，然后計算行向量的最大似然估計值來得到個體對應(yīng)的F與CR。控制參數(shù)自適應(yīng)方法的具體步驟如下：

步驟1 初始化狀態(tài)轉(zhuǎn)移矩陣A。設(shè)置三種狀態(tài)之間的轉(zhuǎn)移是等概率的，即A=[1/3,1/3,1/3;1/3,1/3,1/3;1/3,1/3,1/3]。

步驟2 得到混淆概率矩陣B。將父代種群、變異種群和交叉種群轉(zhuǎn)換為概率，作為隱馬爾可夫模型中的混淆概率，轉(zhuǎn)換方法詳見算法1（參考文獻(xiàn)[16]）。對種群中每個個體而言，其對應(yīng)的混淆概率矩陣B的大小為3×D。

步驟3 得到實際狀態(tài)序列。個體狀態(tài)可以利用隱馬爾可夫模型中的概率矩陣來評估[16]。在本文中，設(shè)置0～1/3 代表“差”狀態(tài)，1/3～2/3 代表“中”狀態(tài)，2/3～1 代表“優(yōu)”狀態(tài)。從而可得到每個個體變異之后的實際狀態(tài)序列realMutseq、交叉之后的實際狀態(tài)序列realCanseq，序列大小都為1×D。

步驟4 得到最優(yōu)隱藏序列。父代種群觀察到的父代觀測序列記為EMseq，變異種群觀察到的變異觀測序列記為Mutseq，交叉種群觀察到的交叉觀測序列記為Canseq。每個個體對應(yīng)觀測序列大小都為1×D。利用隱馬爾可夫模型中的Viterbi 算法[17]分別求出父代個體觀測序列與變異個體觀測序列條件下的最優(yōu)隱藏序列，記為bestMutseq和bestCanseq。

步驟5 變異縮放因子F與交叉概率CR的計算方式如下：

對種群中的每個個體，對比其實際狀態(tài)序列real-Mutseq與最優(yōu)隱藏序列bestMutseq中每一列的值，若相等，將1 存入行向量lm中對應(yīng)列位置，否則存入0。同理對比realCanseq與bestCanseq，得到行向量lc。

式中，MLE(?)表示最大似然估計值。

種群信息轉(zhuǎn)換為概率的偽代碼如算法1所示。

算法1 種群信息轉(zhuǎn)換為概率

輸入：種群大小為PS×D的種群pop。

（1）建立一個大小為PS×D的新矩陣popr；

（2）建立兩個長度為D的向量δ和ε；

（3）計算種群pop中每一列的平均值與方差，分別計入δ和ε；

（4）計算種群pop中每一行i和每一列j即pop(i,j)的概率分布，計入popr(i,j)。

輸出：popr。

2.2 變異策略自適應(yīng)

為實現(xiàn)多目標(biāo)差分進(jìn)化算法變異策略自適應(yīng)，本研究采用改進(jìn)的反向世代距離對變異策略進(jìn)行評價，再使用隱馬爾可夫鏈模型對變異策略進(jìn)行預(yù)測生成。本研究使用“DE/rand/1”“DE/best/1”和“DE/current-to-best/1”三種變異策略。即，隱馬爾可夫模型中的三種隱藏狀態(tài)可以表示如下：策略1、策略2、策略3，其中策略1 表示“DE/rand/1”，策略2 表示“DE/best/1”，策略3 表示“DE/current-to-best/1”。前者有很好的全局開發(fā)能力，后兩者有較好的局部探索能力，能夠保持全局搜索與局部搜索的平衡。

設(shè)置隱馬爾可夫模型中有三種觀測狀態(tài)：優(yōu)、中、差。優(yōu)表示當(dāng)前變異個體支配對應(yīng)父代個體；中表示當(dāng)前變異個體與對應(yīng)父代個體互不支配；差表示對應(yīng)父代個體支配當(dāng)前變異個體。

初始化階段，設(shè)置三種狀態(tài)之間的轉(zhuǎn)移是等概率的以及在某一狀態(tài)下觀測到各策略的概率是相等的。即變異差分策略的狀態(tài)轉(zhuǎn)移概率矩陣A與混淆概率矩陣B均為[1/3，1/3，1/3；1/3，1/3，1/3；1/3，1/3，1/3]，通過隱馬爾可夫模型生成一個選擇變異策略的初始策略鏈，記為chain，大小為1×PS。變異策略自適應(yīng)方法的具體步驟如下：

步驟1 根據(jù)個體選擇變異策略的不同，將種群劃分為三個子種群，分別記為Prand、Pbest、Pcurrent，對應(yīng)的目標(biāo)空間解集記為Crand、Cbest、Ccurrent，它們對應(yīng)的改進(jìn)反向世代距離分別記為mIGDrand、mIGDbest、mIGDcurrent。改進(jìn)反向世代距離計算公式如下：

步驟2 各個策略所得改進(jìn)反向世代距離值越小，說明選擇該策略的變異效果越好。因此，狀態(tài)轉(zhuǎn)移矩陣設(shè)置為：

步驟3 同理，各個策略的改進(jìn)反向世代距離值越小，說明在該策略狀態(tài)下，觀測到“優(yōu)”的概率較大。因此，混淆矩陣表示如下：

步驟4 利用矩陣A和B作為隱馬爾可夫模型參數(shù)生成一個新的策略鏈chain。

2.3 混合交叉策略

為保證算法前期有較好的全局搜索能力和后期有較好的局部搜索能力，本研究采取一種多項式交叉和模擬二進(jìn)制交叉混合使用的交叉策略。其中，模擬二進(jìn)制交叉（Simulated Binary Crossover，SBX）具有很強的局部搜索能力[18]；而多項式交叉則有較好的全局搜索能力。因此，本文設(shè)置一個隨迭代次數(shù)不斷變小的μ來達(dá)到此目的[19]。

從公式（26）可以看出，μ在種群進(jìn)化前期具有較大值，故選擇多項式交叉的概率較大，此時算法偏向于全局搜索；算法后期，μ值減小，選擇SBX 交叉策略的概率較大，算法偏向于局部搜索。

2.4 SMODE-HMC算法的基本流程

步驟1 設(shè)置參數(shù)PS、F、CR、最大迭代次數(shù)等，并利用隱馬爾可夫模型生成初始策略鏈chain。

步驟2 如果G<0.2×Gmax[5]，所提算法只使用“DE/rand/1”變異策略，否則使用2.2 節(jié)來自動選擇合適的變異策略。確定策略后，依據(jù)2.1 節(jié)計算F的數(shù)值，然后進(jìn)行變異操作。

步驟3 依據(jù)2.1 節(jié)計算CR的數(shù)值。若rand<μ，選擇多項式交叉策略，否則使用模擬二進(jìn)制交叉策略。

步驟4 對試驗個體進(jìn)行邊界值判定[5]；如果一個隨機數(shù)rand>Bset[20]那么

式中，Lj和Uj表示變量第j維的下界與上界。否則在定義域(Ω)范圍內(nèi)重新生成新的試驗個體。

步驟5 環(huán)境選擇。若是三目標(biāo)問題，采用文獻(xiàn)[21]中的tDEA方法；若是雙目標(biāo)問題，則采用快速非支配選擇方式[22]。

步驟6G=G+1。

步驟7 循環(huán)步驟2到步驟6，直到滿足最大迭代次數(shù)。

3 實驗結(jié)果與分析

為驗證SMODE-HMC算法的性能，將其與另外9種多目標(biāo)進(jìn)化算法在9個三目標(biāo)（WFG1～WFG9）和7個雙目標(biāo)（UF1～UF7）測試函數(shù)上進(jìn)行性能對比。其他9 種多目標(biāo)進(jìn)化算法分別為MOEAD[23]、NSGAIII[24]、GDE3[2]、ARMOEA[25]、LMEA[26]、MOEADDE[27]、tDEA[21]、MMOPSO[28]、MODE-SS[19]，其中前8 種算法的結(jié)果由文獻(xiàn)[29]提供的軟件求得。為保證實驗結(jié)果分析的可靠性，采用Wilcoxon 和Friedman 非參數(shù)檢驗方法對實驗結(jié)果進(jìn)行統(tǒng)計分析，顯著性水平設(shè)置為5%。其中“+”“－”分別表示所提算法優(yōu)于、劣于相比較算法；“≈”表示所提算法與相比較的算法性能相近。

3.1 參數(shù)設(shè)置

在本研究中，所有測試函數(shù)的種群數(shù)量均設(shè)置為120，三目標(biāo)的最大迭代次數(shù)設(shè)置為300，雙目標(biāo)的最大迭代次數(shù)設(shè)置為200，每一種算法求解每一個測試函數(shù)均獨立運行20次。比較算法的參數(shù)設(shè)定均與原始文獻(xiàn)一致。

3.2 算法比較

SMODE-HMC 與其他9 種比較算法得到的GD 平均值與方差以及Wilcoxon 統(tǒng)計結(jié)果見表1。從表1 可以看出，SMODE-HMC 分別優(yōu)于MOEAD、NSGAIII、GDE3、ARMOEA、LMEA、MOEADDE、tDEA、MMOPSO、MODE-SS 算法12、10、14、10、11、11、9、13、14 個測試函數(shù)，分別劣于以上算法3、3、1、2、3、2、2、1、1 個測試函數(shù)，另外分別有1、3、1、4、2、3、5、2、1個測試函數(shù)與以上相比較的算法性能相近。同時，10 種算法得到GD 的Friedman 統(tǒng)計分析結(jié)果見表2，實驗結(jié)果顯示SMODEHMC 排名第一，說明本文所提算法得到的Pareto 前沿與真實PF最為接近，收斂性是所有算法中最好的。其主要原因是SMODE-HMC算法使用了自適應(yīng)變異策略和混合交叉策略，它能夠根據(jù)不同類型的多目標(biāo)優(yōu)化問題來選擇合適的生成策略。同時，控制參數(shù)自適應(yīng)策略為算法提供合適的參數(shù)使其適應(yīng)不同的進(jìn)化階段或問題。

表1 所有比較多目標(biāo)進(jìn)化算法得到的GD平均值與方差

表2 所有比較算法在GD平均值上的性能排序

SMODE-HMC與其他9種比較算法得到的SP平均值與方差以及Wilcoxon統(tǒng)計結(jié)果見表3。從表3可以看出，MOEAD、NSGAIII、GDE3、ARMOEA、MODESS 等算法在3個測試函數(shù)上優(yōu)于所提算法；tDEA和MMOPSO算法在2個測試函數(shù)上優(yōu)于所提算法；而MOEADDE只在1 個測試函數(shù)上比所提算法性能好。除了LMEA，SMODE-HMC 的整體性能優(yōu)于其他8 種比較算法。LMEA在大部分三目標(biāo)測試函數(shù)上的SP值要小于所提算法，這是因為LMEA算法利用聚類方法將決策變量分為兩組，其中一組特意考慮了多樣性指標(biāo)。但是，從整體性能來看（見表4），所提算法在性能指標(biāo)SP上的表現(xiàn)要比LMEA略好。其主要原因是SMODE-HMC算法利用隱馬爾可夫模型分別來預(yù)測控制參數(shù)和變異策略，使其在進(jìn)化過程中自適應(yīng)調(diào)整。

表3 所有比較多目標(biāo)進(jìn)化算法得到的SP平均值與方差

表4 所有比較算法在SP平均值上的性能排序

SMODE-HMC 與其他9 種比較算法得到的IGD 平均值與方差以及Wilcoxon統(tǒng)計結(jié)果見表5。從表5可以看出，SMODE-HMC分別優(yōu)于MOEAD、NSGAIII、GDE3、ARMOEA、LMEA、MOEADDE、tDEA、MMOPSO、MODESS 算法15、7、12、8、11、11、7、9、10 個測試函數(shù)，分別劣于以上相比較算法1、4、3、4、4、4、3、6、1個測試函數(shù)，另外分別有0、5、1、4、1、1、6、1、5 個測試函數(shù)與以上相比較的算法性能相近。同時，10種算法得到IGD的Friedman統(tǒng)計結(jié)果見表6，實驗結(jié)果顯示本文所提算法SMODEHMC排名第一，說明SMODE-HMC算法得到的解集整體分布性最好。其主要原因是SMODE-HMC算法在進(jìn)化過程中能夠自動選擇合適的變異策略，并生成合適的控制參數(shù)來提高其求解不同類型多目標(biāo)優(yōu)化問題的能力。

表5 所有比較多目標(biāo)進(jìn)化算法的IGD平均值與方差

表6 所有比較算法在IGD平均值上的性能排序

綜上，SMODE-HMC 算法所得解集的收斂性和多樣性是所有比較算法中最好的。

3.3 算法分析

由以上實驗結(jié)果可知，SMODE-HMC 在16 個多目標(biāo)測試函數(shù)上的整體表現(xiàn)優(yōu)于其他9 種多目標(biāo)進(jìn)化算法。其主要原因是控制參數(shù)和策略自適應(yīng)方法能夠為多目標(biāo)差分進(jìn)化算法提供實時有效的控制參數(shù)和策略。本節(jié)將對所提算法控制參數(shù)和變異策略在進(jìn)化過程中的自適應(yīng)性進(jìn)行分析。

3.3.1 控制參數(shù)自適應(yīng)分析

本實驗給出SMODE-HMC在兩個測試函數(shù)（WFG5、UF3）上控制參數(shù)F與CR平均值的進(jìn)化曲線（見圖2）。

從圖2（a）中可以看出，控制參數(shù)F與CR的整體變化趨勢類似，前期逐漸減小，后期又隨著迭代次數(shù)的增加而緩慢增大。圖2（b）中，F(xiàn)與CR的整體變化趨勢也類似，先增加后減小。

圖2 SMODE-HMC控制參數(shù)F 和CR 的進(jìn)化曲線

由上可知，SMODE-HMC 算法的控制參數(shù)根據(jù)不同類型的多目標(biāo)優(yōu)化問題而實現(xiàn)自適應(yīng)實時調(diào)整。

為進(jìn)一步驗證所提方法的有效性，在實驗中使用固定控制參數(shù)的SMODE-HMC（命名為SMODE-HMC-1）；并用WFG5 和UF3 兩個測試函數(shù)來進(jìn)行測試。所得到的GD、SP與IGD值見表7。

從表7可以看出，SMODE-HMC-1在兩個測試函數(shù)上的表現(xiàn)均劣于SMODE-HMC。這表明，相比于固定的參數(shù)設(shè)定策略，控制參數(shù)自適應(yīng)策略能夠提高多目標(biāo)進(jìn)化算法的求解性能。

表7 SMODE-HMC和沒有參數(shù)自適應(yīng)SMODE-HMC所得結(jié)果

綜上，本研究使用隱馬爾可夫模型來實現(xiàn)多目標(biāo)進(jìn)化算法的控制參數(shù)自適應(yīng)是有效和可行的。

3.3.2 變異策略自適應(yīng)分析

本部分將使用兩個測試函數(shù)WFG5和UF3對SMODEHMC 算法變異策略的自適應(yīng)進(jìn)行分析。需要注意的是，當(dāng)G≥0.2×Gmax時，SMODE-HMC才使用變異策略自適應(yīng)策略；在此之前，算法只使用DE/rand/1 變異策略。這主要是讓所提算法在進(jìn)化前期有足夠的全局探索能力。各個變異策略在整個進(jìn)化過程中的數(shù)量和占比分別見圖3和圖4。

從圖3（a）中可以看出，SMODE-HMC 在前期主要使用DE/rand/1 和DE/best/1 兩個變異策略；中期使用DE/curret-to-best/1 較多；進(jìn)化后期策略DE/curret-tobest/1 和DE/best/1 作用類似。圖3（b）顯示，變異策略DE/rand/1 在整個進(jìn)化過程中幾乎都占據(jù)主導(dǎo)位置，而變異策略DE/curret-to-best/1 和DE/best/1 在整個進(jìn)化過程中的作用似乎差不多。從上可得，SMODE-HMC 可以根據(jù)不同類型的多目標(biāo)優(yōu)化問題實時選擇合適的變異策略，因此，該自適應(yīng)變異策略可以大大提高搜索性能。另外，三種變異策略在整個種群進(jìn)化過程中的占比見圖4。從圖4可知，變異策略DE/rand/1被使用的次數(shù)最多。其主要原因是，對于復(fù)雜問題，算法只有擁有良好的全局搜索能力，才能找到高質(zhì)量的解。同時，變異策略DE/curret-to-best/1 和DE/best/1 在這兩個測試函數(shù)上被使用的頻率幾乎相同。但根據(jù)圖3所得，它們在不同的進(jìn)化階段發(fā)揮不同的作用。

圖3 SMODE-HMC變異策略的進(jìn)化曲線

圖4 SMODE-HMC求解測試函數(shù)時三種變異策略數(shù)量占比

為進(jìn)一步驗證策略自適應(yīng)的有效性，本實驗使用固定變異策略的SMODE-HMC 來求解WFG5 和UF3。由圖4 可知，DE/rand/1 在三種變異策略中使用次數(shù)最多，故SMODE-HMC只使用它來對個體進(jìn)行變異操作，算法命名為SMODE-HMC-2。所得GD、SP與IGD值見表8。

表8 SMODE-HMC和沒有策略自適應(yīng)SMODE-HMC所得結(jié)果

從表8可以看出，SMODE-HMC-2在兩個測試函數(shù)上的性能評價指標(biāo)值均劣于SMODE-HMC，說明變異策略自適應(yīng)能夠使多目標(biāo)差分進(jìn)化算法的性能更好。

綜上，隱馬爾可夫鏈可以輔助SMODE-HMC 算法實現(xiàn)變異策略的自適應(yīng)選擇，從而提高其求解多目標(biāo)優(yōu)化問題的能力。

3.3.3 參數(shù)分析

在本實驗中，對混合交叉策略中的參數(shù)μ進(jìn)行分析。利用上述16 個測試函數(shù)對不同的μ進(jìn)行測試。圖5 表示由Friedman統(tǒng)計分析得到的不同μ值下GD、SP、IGD性能排序平均值。由圖5可知，當(dāng)μ=1-G/Gmax時，算法整體性能最好。故在所提算法SMODE-HMC 中，μ值取μ=1-G/Gmax。

圖5 不同μ 值的性能排序

4 SMODE-HMC 在海鐵聯(lián)運能耗優(yōu)化問題中的應(yīng)用

在該部分，將SMODE-HMC與上述相比較的9種算法用于求解海鐵聯(lián)運能耗優(yōu)化問題，以驗證SMODEHMC 求解實際優(yōu)化問題的有效性。種群規(guī)模設(shè)定為120，最大迭代次數(shù)設(shè)置為200。能量損耗E與運輸時間T的雙目標(biāo)優(yōu)化建立如下：

式中，f1(v)=E,f2(v)=T,v表示火車或船的速度。海鐵聯(lián)運模擬運輸路線、速度與能耗關(guān)系詳見參考文獻(xiàn)[19]。參數(shù)PF是將10種算法所得解集進(jìn)行合并，并挑選其中的非支配解所得到。

10種算法求解海鐵聯(lián)運模型得到的GD、SP與IGD值見表9。從表9 可以看出，本文所提算法SMODEHMC 在GD、SP 和IGD 值上均優(yōu)于9 種比較算法，說明SMODE-HMC 具有較好的收斂性和多樣性，整體性能最好。另外，10種算法求解海鐵聯(lián)運能耗優(yōu)化問題所得PF見圖6。從圖6 中也可以看出，SMODE-HMC 所得PF的整體分布要優(yōu)于所比較的9種算法。

表9 各個算法得到的GD、SP與IGD值

從SMODE-HMC的求解結(jié)果中分別選取耗能最大的點Q1 和耗時最長的點Q2，Q1 與Q2 點見圖6（a）中綠色實心圓。Q1 與Q2 點火車與船舶在各路段的行駛速度見表10。從表10可以看出速度對耗能與時間皆有影響，顯然速度與耗能成正比，與時間成反比。即耗能最大時，各路段行駛速度相對較大；當(dāng)時間最大時，各路段行駛速度相對較小。特別是在鐵路運輸上，二者速度的變化率最大。

圖6 SMODE-HMC與其他9種算法所得PF 逼近

表10 Q1 與Q2 在各路段的速度

5 結(jié)語

差分進(jìn)化算法的控制參數(shù)和生成策略選擇對其性能有著顯著影響。為提高多目標(biāo)差分進(jìn)化算法求解多目標(biāo)優(yōu)化問題的能力，本文提出了一種基于隱馬爾可夫鏈的自適應(yīng)多目標(biāo)差分進(jìn)化算法（Self-adaptive Multi-Objective Differential Evolution Algorithm Based on Hidden Markov Chain，SMODE-HMC）。在該算法中，利用隱馬爾可夫模型對多目標(biāo)差分進(jìn)化算法的控制參數(shù)和變異策略進(jìn)行自適應(yīng)動態(tài)調(diào)整；并使用兩種不同搜索性能的交叉變異策略來實現(xiàn)算法在進(jìn)化前期進(jìn)行全局搜索和進(jìn)化中后期進(jìn)行局部搜索。通過與其他9 種多目標(biāo)進(jìn)化算法測試對比，實驗結(jié)果顯示SMODEHMC 的整體性能要優(yōu)于所比較的其他算法。最后，將SMODE-HMC 用于求解海鐵聯(lián)運能耗優(yōu)化問題，依據(jù)所得實驗結(jié)果分析得出能耗E和時間T與行駛速度的關(guān)系，從而為決策者提供重要的決策參考。實驗表明SMODE-HMC算法可以為實際多目標(biāo)優(yōu)化問題的求解提供有效幫助。