崔彩霞,畢超超,范勤勤,3
1.上海海事大學 物流科學與工程研究院,上海201306
2.上海海事大學 物流研究中心,上海201306
3.上海交通大學 電子信息與電氣工程學院,上海200240
差分進化算法[1]是由Storn和Price于1997年提出的一種高效元啟發(fā)式搜索算法。由于該算法易于實現、尋優(yōu)性能強、魯棒性好,從而吸引了國內外學者的關注與研究,并被用于求解各領域的優(yōu)化問題。
除求解單目標優(yōu)化問題外,差分進化算法也被用來求解各類多目標優(yōu)化問題。為提高其性能,各種多目標差分進化算法(Multi-Objective Differential Evolution Algorithm,MODE)被不斷提出。比如Kukkonen 等人[2]于2005 年提出的GDE3(The Third Evolution Step of Generalized Differential Evolution)算法是其中一種較為典型的多目標差分進化算法,并被用于解決有約束的多目標優(yōu)化問題。該算法對變異策略進行改進,并且增加新的選擇規(guī)則。張春美等人[3]提出一種參數自適應的分布式差分進化算法(Distributed Differential Evolution Algorithm with Adaptive Parameters,APDDE)。該算法根據馮·諾依曼拓撲結構將初始種群分為多個子種群,用子種群的優(yōu)秀個體代替其鄰域子種群中的較差個體,并根據個體適應值的變化情況對種群內各個體分配不同的F和CR,從而實現參數自適應。結果表明該算法在收斂速度和求解質量上都有所提高。李牧東等人[4]于2016年提出一種基于最優(yōu)高斯隨機游走和個體篩選策略的差分進化算法(Differential Evolution Based on Optimal Gaussian Random Walk and Individual Selection Strategies)。在該算法中,首先利用最優(yōu)高斯隨機游走策略產生新的種群;然后僅對種群中性能較差的個體進行交叉和變異操作,并使用改進的個體篩選策略來產生新個體;最后,得到一個新種群。實驗結果表明該算法具有較快的收斂速度和較好的魯棒性。Fan 等人[5]提出一種基于性能指標的多目標差分進化算法(Multi-Objective Differential Evolution with Performance-Metricbased Self-adaptive Mutation Operator,MODE-PMSMO)。該算法采用一種多目標性能評價指標來指導變異策略的動態(tài)調整。所得結果表明MODE-PMSMO 能夠根據進化進程自適應得到合適的變異策略來求解相應類型的多目標優(yōu)化問題。候瑩等人[6]提出了一種基于參數動態(tài)調整的多目標差分進化算法(Adaptive Multi-Objective Differential Evolution Algorithm Based on the Dynamic Parameters Adjustment,AMODE)。該算法通過實現控制參數自適應的方式來提高其求解多目標優(yōu)化問題的能力。實驗結果表明該算法能夠有效提高所得帕累托前沿的收斂性和多樣性。Lin等人[7]于2018年提出一種具有多種差分進化策略的自適應免疫啟發(fā)多目標算法(An Adaptive Immune-inspired Multi-Objective Algorithm with Multiple Differential Evolution Strategies)。該算法將差分變異算子融入到多目標免疫算法中,結果表明所提算法有效提高了解集的多樣性。艾兵等人[8]提出一種基于多策略和排序變異的多目標差分進化算法(Multi-Objective Differential Evolution Algorithm with Multi-strategy and Ranking-based Mutation,MODEMERM)。該算法利用基于多策略和排序變異的DE 算子進行變異操作。所得結果表明MODE-MERM采用多種變異策略能夠平衡解集的收斂性與多樣性。童旅楊等人[9]于2019 年提出一種基于分解和多策略變異的多目標差分進化算法(Multi-Objective Differential Evolution Algorithm Based on Decomposition and Multi-Strategy Mutation,MODE/DMSM)。該算法利用改進的切比雪夫分解方法將多目標優(yōu)化問題分解成多個單目標子問題;并采用多策略變異的方法來求解各個子問題。實驗結果表明MODE/DMSM使用多個差分變異算子能夠得到多樣性和收斂性較好的解集。
雖然眾多學者對多目標差分進化算法已進行大量研究,但是在其控制參數和策略自適應方面仍存在一些問題。比如,現有多目標差分進化算法的自適應方法一般不具有預測功能,因此這會大大降低其所得控制參數和策略的適應性。為解決該問題,本研究提出一種基于隱馬爾可夫鏈的自適應多目標差分進化算法(Selfadaptive Multi-Objective Differential Evolution Algorithm Based on Hidden Markov Chain,SMODE-HMC)。在SMODE-HMC 算法中,隱馬爾可夫鏈方法被分別用來預測控制參數和變異策略的演化趨勢,從而實現自適應調整。通過16 個基準多目標優(yōu)化問題的測試,結果表明所提算法的整體性能要好于其他9 種比較算法。另外,本研究還將SMODE-HMC 算法用于求解海鐵聯運多目標優(yōu)化問題,得到令人滿意的結果。
在現實世界中,多目標優(yōu)化問題(Multi-objective Optimization Problems,MOPs)廣泛存在于各個領域,如多目標柔性車間作業(yè)調度[10]、電動車充電站規(guī)劃[11]等問題。通常情況下,多目標優(yōu)化問題中的各個子目標相互矛盾且不可調和。不失一般性,多目標優(yōu)化問題的數學形式表示如下:
其中,x為決策向量;Ω∈RD為D維決策空間;m表示優(yōu)化目標數量。其他一些相關概念如下:
定理1(支配關系)向量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 前沿)多目標優(yōu)化問題中,Pareto 最優(yōu)解集中的解對應的目標向量被稱為Pareto前沿(Pareto Front,PF)。
多目標性能評價指標能夠對所得解集質量做出評判,通常使用的方法有世代距離(Generational Distance,GD)、空間分布評價方法(Spacing,SP)與反向世代距離(Inverted Generational Distance,IGD)[12-14]。其中GD是收斂性指標,評價的是所得解集與真實Pareto前沿的逼近程度;SP 是多樣性指標,評價的是所得解集在真實Pareto前沿上分布的均勻性;IGD是綜合性指標,評價的是所得解集的收斂性和多樣性。具體計算公式如下:
(1)GD
式中,PF*表示一組沿著真實PF均勻分布的解集;C表示算法得到的PF逼近;d(z,PF*)表示z與PF*最近點的歐幾里德距離;|C|表示C中解的數量。GD 值越小,說明所得解集的收斂性越好,與PF越逼近。
(2)SP
式中,k表示非支配解的個數;di表示第i個解與其他解的最小歐幾里德距離;dˉ表示所有di的平均值。SP值越小,說明所得解集的均勻性越好。值得注意的是該性能指標并未對所得解集的延展性進行評價。
(3)IGD
式中,d(z*,C)表示z*與C最近點的歐幾里德距離;|PF*|表示PF*中解的數量。IGD值越小,說明所得目標解集的收斂性和多樣性就越好。
差分進化算法是一種高效的元啟發(fā)式搜索算法,標準差分進化算法主要有以下幾個步驟:
(1)初始化
設置參數,例如初始化縮放因子F、交叉概率CR、種群規(guī)模PS和最大迭代次數等。同時,在定義域(Ω)內,生成初始化種群。
(2)變異
種群中的個體通過變異策略生成變異個體,差分進化算法常用的變異策略如下所示:
式中,D為多目標優(yōu)化問題的維度,Rj為[0,1]之間均勻隨機數,jrand為[1,D] 范圍內的一個隨機整數。
(4)選擇
選擇試驗個體與種群個體中較優(yōu)個體進入下一代,選擇方式如下:
隱馬爾可夫模型(Hidden Markov Model,HMM)是馬爾可夫鏈(Markov Chains,MC)的其中一種方法。在隱馬爾可夫模型中,最難確定的是隱含狀態(tài)參數。雖然HMM的隱藏狀態(tài)不能被直接觀測到,但是隱藏狀態(tài)會通過一定的概率分布在外部狀態(tài)中被觀測到。因此,隱馬爾可夫模型是一個隱藏和非隱藏的雙重隨機過程,第一重是一個隱藏狀態(tài)轉移到另一個隱藏狀態(tài)的隨機過程,這是不可被觀測的;第二重是一個隱藏狀態(tài)到外部展現的隨機過程,這是可以被觀測的。隱馬爾可夫模型的一些相關概念如下[15]。
隱馬爾可夫模型的圖結構如圖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)間的轉換概率稱為狀態(tài)轉移概率,通常記為矩陣,其中:
模型在初始狀時刻各狀態(tài)出現的概率即為初始狀態(tài)概率,記為π={π1,π2,…},且=1。
綜上,HMM可用其參數λ={A,B,π} 來指代。
研究表明隱馬爾可夫模型具有良好的預測能力[16]。因此,為提高多目標差分進化算法的性能,提出一種基于隱馬爾可夫鏈的自適應多目標差分進化算法。在該算法中,將父代種群、變異種群和交叉種群轉換為概率作為隱馬爾可夫模型中的參數,并通過計算最大似然估計值實現對控制參數的自適應更新;另外,通過改進的IGD指標不斷更新隱馬爾可夫模型中的參數,從而不斷更新通過隱馬爾可夫模型生成的策略鏈,實現變異策略選擇的自適應;而且為保證算法前期偏向于全局搜索和后期偏向于局部搜索,本文采取多項式交叉和模擬二進制交叉的混合交叉策略。隱馬爾可夫模型所需參數的初始值均設置為等概率。控制參數自適應與變異策略自適應的具體實現方式見以下部分。
進化過程中,種群隨迭代次數的變化情況與隱馬爾可夫模型內部過程類似[16]。在該部分,將個體的狀態(tài)變化情況分為三種:優(yōu)、中、差。優(yōu)表示當前個體支配比較個體,中表示當前個體與比較個體互不支配,差表示比較個體支配當前個體。
在每一次迭代過程中,種群中每個個體都有與其相對應的變異縮放因子與交叉概率。對比個體的實際狀態(tài)序列與最優(yōu)隱藏序列得到相應行向量,然后計算行向量的最大似然估計值來得到個體對應的F與CR??刂茀底赃m應方法的具體步驟如下:
步驟1 初始化狀態(tài)轉移矩陣A。設置三種狀態(tài)之間的轉移是等概率的,即A=[1/3,1/3,1/3;1/3,1/3,1/3;1/3,1/3,1/3]。
步驟2 得到混淆概率矩陣B。將父代種群、變異種群和交叉種群轉換為概率,作為隱馬爾可夫模型中的混淆概率,轉換方法詳見算法1(參考文獻[16])。對種群中每個個體而言,其對應的混淆概率矩陣B的大小為3×D。
步驟3 得到實際狀態(tài)序列。個體狀態(tài)可以利用隱馬爾可夫模型中的概率矩陣來評估[16]。在本文中,設置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。每個個體對應觀測序列大小都為1×D。利用隱馬爾可夫模型中的Viterbi 算法[17]分別求出父代個體觀測序列與變異個體觀測序列條件下的最優(yōu)隱藏序列,記為bestMutseq和bestCanseq。
步驟5 變異縮放因子F與交叉概率CR的計算方式如下:
對種群中的每個個體,對比其實際狀態(tài)序列real-Mutseq與最優(yōu)隱藏序列bestMutseq中每一列的值,若相等,將1 存入行向量lm中對應列位置,否則存入0。同理對比realCanseq與bestCanseq,得到行向量lc。
式中,MLE(?)表示最大似然估計值。
種群信息轉換為概率的偽代碼如算法1所示。
算法1 種群信息轉換為概率
輸入:種群大小為PS×D的種群pop。
(1)建立一個大小為PS×D的新矩陣popr;
(2)建立兩個長度為D的向量δ和ε;
(3)計算種群pop中每一列的平均值與方差,分別計入δ和ε;
(4)計算種群pop中每一行i和每一列j即pop(i,j)的概率分布,計入popr(i,j)。
輸出:popr。
為實現多目標差分進化算法變異策略自適應,本研究采用改進的反向世代距離對變異策略進行評價,再使用隱馬爾可夫鏈模型對變異策略進行預測生成。本研究使用“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ā)能力,后兩者有較好的局部探索能力,能夠保持全局搜索與局部搜索的平衡。
設置隱馬爾可夫模型中有三種觀測狀態(tài):優(yōu)、中、差。優(yōu)表示當前變異個體支配對應父代個體;中表示當前變異個體與對應父代個體互不支配;差表示對應父代個體支配當前變異個體。
初始化階段,設置三種狀態(tài)之間的轉移是等概率的以及在某一狀態(tài)下觀測到各策略的概率是相等的。即變異差分策略的狀態(tài)轉移概率矩陣A與混淆概率矩陣B均為[1/3,1/3,1/3;1/3,1/3,1/3;1/3,1/3,1/3],通過隱馬爾可夫模型生成一個選擇變異策略的初始策略鏈,記為chain,大小為1×PS。變異策略自適應方法的具體步驟如下:
步驟1 根據個體選擇變異策略的不同,將種群劃分為三個子種群,分別記為Prand、Pbest、Pcurrent,對應的目標空間解集記為Crand、Cbest、Ccurrent,它們對應的改進反向世代距離分別記為mIGDrand、mIGDbest、mIGDcurrent。改進反向世代距離計算公式如下:
步驟2 各個策略所得改進反向世代距離值越小,說明選擇該策略的變異效果越好。因此,狀態(tài)轉移矩陣設置為:
步驟3 同理,各個策略的改進反向世代距離值越小,說明在該策略狀態(tài)下,觀測到“優(yōu)”的概率較大。因此,混淆矩陣表示如下:
步驟4 利用矩陣A和B作為隱馬爾可夫模型參數生成一個新的策略鏈chain。
為保證算法前期有較好的全局搜索能力和后期有較好的局部搜索能力,本研究采取一種多項式交叉和模擬二進制交叉混合使用的交叉策略。其中,模擬二進制交叉(Simulated Binary Crossover,SBX)具有很強的局部搜索能力[18];而多項式交叉則有較好的全局搜索能力。因此,本文設置一個隨迭代次數不斷變小的μ來達到此目的[19]。
從公式(26)可以看出,μ在種群進化前期具有較大值,故選擇多項式交叉的概率較大,此時算法偏向于全局搜索;算法后期,μ值減小,選擇SBX 交叉策略的概率較大,算法偏向于局部搜索。
步驟1 設置參數PS、F、CR、最大迭代次數等,并利用隱馬爾可夫模型生成初始策略鏈chain。
步驟2 如果G<0.2×Gmax[5],所提算法只使用“DE/rand/1”變異策略,否則使用2.2 節(jié)來自動選擇合適的變異策略。確定策略后,依據2.1 節(jié)計算F的數值,然后進行變異操作。
步驟3 依據2.1 節(jié)計算CR的數值。若rand<μ,選擇多項式交叉策略,否則使用模擬二進制交叉策略。
步驟4 對試驗個體進行邊界值判定[5];如果一個隨機數rand>Bset[20]那么
式中,Lj和Uj表示變量第j維的下界與上界。否則在定義域(Ω)范圍內重新生成新的試驗個體。
步驟5 環(huán)境選擇。若是三目標問題,采用文獻[21]中的tDEA方法;若是雙目標問題,則采用快速非支配選擇方式[22]。
步驟6G=G+1。
步驟7 循環(huán)步驟2到步驟6,直到滿足最大迭代次數。
為驗證SMODE-HMC算法的性能,將其與另外9種多目標進化算法在9個三目標(WFG1~WFG9)和7個雙目標(UF1~UF7)測試函數上進行性能對比。其他9 種多目標進化算法分別為MOEAD[23]、NSGAIII[24]、GDE3[2]、ARMOEA[25]、LMEA[26]、MOEADDE[27]、tDEA[21]、MMOPSO[28]、MODE-SS[19],其中前8 種算法的結果由文獻[29]提供的軟件求得。為保證實驗結果分析的可靠性,采用Wilcoxon 和Friedman 非參數檢驗方法對實驗結果進行統(tǒng)計分析,顯著性水平設置為5%。其中“+”“-”分別表示所提算法優(yōu)于、劣于相比較算法;“≈”表示所提算法與相比較的算法性能相近。
在本研究中,所有測試函數的種群數量均設置為120,三目標的最大迭代次數設置為300,雙目標的最大迭代次數設置為200,每一種算法求解每一個測試函數均獨立運行20次。比較算法的參數設定均與原始文獻一致。
SMODE-HMC 與其他9 種比較算法得到的GD 平均值與方差以及Wilcoxon 統(tǒng)計結果見表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 個測試函數,分別劣于以上算法3、3、1、2、3、2、2、1、1 個測試函數,另外分別有1、3、1、4、2、3、5、2、1個測試函數與以上相比較的算法性能相近。同時,10 種算法得到GD 的Friedman 統(tǒng)計分析結果見表2,實驗結果顯示SMODEHMC 排名第一,說明本文所提算法得到的Pareto 前沿與真實PF最為接近,收斂性是所有算法中最好的。其主要原因是SMODE-HMC算法使用了自適應變異策略和混合交叉策略,它能夠根據不同類型的多目標優(yōu)化問題來選擇合適的生成策略。同時,控制參數自適應策略為算法提供合適的參數使其適應不同的進化階段或問題。
表1 所有比較多目標進化算法得到的GD平均值與方差
表2 所有比較算法在GD平均值上的性能排序
SMODE-HMC與其他9種比較算法得到的SP平均值與方差以及Wilcoxon統(tǒng)計結果見表3。從表3可以看出,MOEAD、NSGAIII、GDE3、ARMOEA、MODESS 等算法在3個測試函數上優(yōu)于所提算法;tDEA和MMOPSO算法在2個測試函數上優(yōu)于所提算法;而MOEADDE只在1 個測試函數上比所提算法性能好。除了LMEA,SMODE-HMC 的整體性能優(yōu)于其他8 種比較算法。LMEA在大部分三目標測試函數上的SP值要小于所提算法,這是因為LMEA算法利用聚類方法將決策變量分為兩組,其中一組特意考慮了多樣性指標。但是,從整體性能來看(見表4),所提算法在性能指標SP上的表現要比LMEA略好。其主要原因是SMODE-HMC算法利用隱馬爾可夫模型分別來預測控制參數和變異策略,使其在進化過程中自適應調整。
表3 所有比較多目標進化算法得到的SP平均值與方差
表4 所有比較算法在SP平均值上的性能排序
SMODE-HMC 與其他9 種比較算法得到的IGD 平均值與方差以及Wilcoxon統(tǒng)計結果見表5。從表5可以看出,SMODE-HMC分別優(yōu)于MOEAD、NSGAIII、GDE3、ARMOEA、LMEA、MOEADDE、tDEA、MMOPSO、MODESS 算法15、7、12、8、11、11、7、9、10 個測試函數,分別劣于以上相比較算法1、4、3、4、4、4、3、6、1個測試函數,另外分別有0、5、1、4、1、1、6、1、5 個測試函數與以上相比較的算法性能相近。同時,10種算法得到IGD的Friedman統(tǒng)計結果見表6,實驗結果顯示本文所提算法SMODEHMC排名第一,說明SMODE-HMC算法得到的解集整體分布性最好。其主要原因是SMODE-HMC算法在進化過程中能夠自動選擇合適的變異策略,并生成合適的控制參數來提高其求解不同類型多目標優(yōu)化問題的能力。
表5 所有比較多目標進化算法的IGD平均值與方差
表6 所有比較算法在IGD平均值上的性能排序
綜上,SMODE-HMC 算法所得解集的收斂性和多樣性是所有比較算法中最好的。
由以上實驗結果可知,SMODE-HMC 在16 個多目標測試函數上的整體表現優(yōu)于其他9 種多目標進化算法。其主要原因是控制參數和策略自適應方法能夠為多目標差分進化算法提供實時有效的控制參數和策略。本節(jié)將對所提算法控制參數和變異策略在進化過程中的自適應性進行分析。
3.3.1 控制參數自適應分析
本實驗給出SMODE-HMC在兩個測試函數(WFG5、UF3)上控制參數F與CR平均值的進化曲線(見圖2)。
從圖2(a)中可以看出,控制參數F與CR的整體變化趨勢類似,前期逐漸減小,后期又隨著迭代次數的增加而緩慢增大。圖2(b)中,F與CR的整體變化趨勢也類似,先增加后減小。
圖2 SMODE-HMC控制參數F 和CR 的進化曲線
由上可知,SMODE-HMC 算法的控制參數根據不同類型的多目標優(yōu)化問題而實現自適應實時調整。
為進一步驗證所提方法的有效性,在實驗中使用固定控制參數的SMODE-HMC(命名為SMODE-HMC-1);并用WFG5 和UF3 兩個測試函數來進行測試。所得到的GD、SP與IGD值見表7。
從表7可以看出,SMODE-HMC-1在兩個測試函數上的表現均劣于SMODE-HMC。這表明,相比于固定的參數設定策略,控制參數自適應策略能夠提高多目標進化算法的求解性能。
表7 SMODE-HMC和沒有參數自適應SMODE-HMC所得結果
綜上,本研究使用隱馬爾可夫模型來實現多目標進化算法的控制參數自適應是有效和可行的。
3.3.2 變異策略自適應分析
本部分將使用兩個測試函數WFG5和UF3對SMODEHMC 算法變異策略的自適應進行分析。需要注意的是,當G≥0.2×Gmax時,SMODE-HMC才使用變異策略自適應策略;在此之前,算法只使用DE/rand/1 變異策略。這主要是讓所提算法在進化前期有足夠的全局探索能力。各個變異策略在整個進化過程中的數量和占比分別見圖3和圖4。
從圖3(a)中可以看出,SMODE-HMC 在前期主要使用DE/rand/1 和DE/best/1 兩個變異策略;中期使用DE/curret-to-best/1 較多;進化后期策略DE/curret-tobest/1 和DE/best/1 作用類似。圖3(b)顯示,變異策略DE/rand/1 在整個進化過程中幾乎都占據主導位置,而變異策略DE/curret-to-best/1 和DE/best/1 在整個進化過程中的作用似乎差不多。從上可得,SMODE-HMC 可以根據不同類型的多目標優(yōu)化問題實時選擇合適的變異策略,因此,該自適應變異策略可以大大提高搜索性能。另外,三種變異策略在整個種群進化過程中的占比見圖4。從圖4可知,變異策略DE/rand/1被使用的次數最多。其主要原因是,對于復雜問題,算法只有擁有良好的全局搜索能力,才能找到高質量的解。同時,變異策略DE/curret-to-best/1 和DE/best/1 在這兩個測試函數上被使用的頻率幾乎相同。但根據圖3所得,它們在不同的進化階段發(fā)揮不同的作用。
圖3 SMODE-HMC變異策略的進化曲線
圖4 SMODE-HMC求解測試函數時三種變異策略數量占比
為進一步驗證策略自適應的有效性,本實驗使用固定變異策略的SMODE-HMC 來求解WFG5 和UF3。由圖4 可知,DE/rand/1 在三種變異策略中使用次數最多,故SMODE-HMC只使用它來對個體進行變異操作,算法命名為SMODE-HMC-2。所得GD、SP與IGD值見表8。
表8 SMODE-HMC和沒有策略自適應SMODE-HMC所得結果
從表8可以看出,SMODE-HMC-2在兩個測試函數上的性能評價指標值均劣于SMODE-HMC,說明變異策略自適應能夠使多目標差分進化算法的性能更好。
綜上,隱馬爾可夫鏈可以輔助SMODE-HMC 算法實現變異策略的自適應選擇,從而提高其求解多目標優(yōu)化問題的能力。
3.3.3 參數分析
在本實驗中,對混合交叉策略中的參數μ進行分析。利用上述16 個測試函數對不同的μ進行測試。圖5 表示由Friedman統(tǒng)計分析得到的不同μ值下GD、SP、IGD性能排序平均值。由圖5可知,當μ=1-G/Gmax時,算法整體性能最好。故在所提算法SMODE-HMC 中,μ值取μ=1-G/Gmax。
圖5 不同μ 值的性能排序
在該部分,將SMODE-HMC與上述相比較的9種算法用于求解海鐵聯運能耗優(yōu)化問題,以驗證SMODEHMC 求解實際優(yōu)化問題的有效性。種群規(guī)模設定為120,最大迭代次數設置為200。能量損耗E與運輸時間T的雙目標優(yōu)化建立如下:
式中,f1(v)=E,f2(v)=T,v表示火車或船的速度。海鐵聯運模擬運輸路線、速度與能耗關系詳見參考文獻[19]。參數PF是將10種算法所得解集進行合并,并挑選其中的非支配解所得到。
10種算法求解海鐵聯運模型得到的GD、SP與IGD值見表9。從表9 可以看出,本文所提算法SMODEHMC 在GD、SP 和IGD 值上均優(yōu)于9 種比較算法,說明SMODE-HMC 具有較好的收斂性和多樣性,整體性能最好。另外,10種算法求解海鐵聯運能耗優(yōu)化問題所得PF見圖6。從圖6 中也可以看出,SMODE-HMC 所得PF的整體分布要優(yōu)于所比較的9種算法。
表9 各個算法得到的GD、SP與IGD值
從SMODE-HMC的求解結果中分別選取耗能最大的點Q1 和耗時最長的點Q2,Q1 與Q2 點見圖6(a)中綠色實心圓。Q1 與Q2 點火車與船舶在各路段的行駛速度見表10。從表10可以看出速度對耗能與時間皆有影響,顯然速度與耗能成正比,與時間成反比。即耗能最大時,各路段行駛速度相對較大;當時間最大時,各路段行駛速度相對較小。特別是在鐵路運輸上,二者速度的變化率最大。
圖6 SMODE-HMC與其他9種算法所得PF 逼近
表10 Q1 與Q2 在各路段的速度
差分進化算法的控制參數和生成策略選擇對其性能有著顯著影響。為提高多目標差分進化算法求解多目標優(yōu)化問題的能力,本文提出了一種基于隱馬爾可夫鏈的自適應多目標差分進化算法(Self-adaptive Multi-Objective Differential Evolution Algorithm Based on Hidden Markov Chain,SMODE-HMC)。在該算法中,利用隱馬爾可夫模型對多目標差分進化算法的控制參數和變異策略進行自適應動態(tài)調整;并使用兩種不同搜索性能的交叉變異策略來實現算法在進化前期進行全局搜索和進化中后期進行局部搜索。通過與其他9 種多目標進化算法測試對比,實驗結果顯示SMODEHMC 的整體性能要優(yōu)于所比較的其他算法。最后,將SMODE-HMC 用于求解海鐵聯運能耗優(yōu)化問題,依據所得實驗結果分析得出能耗E和時間T與行駛速度的關系,從而為決策者提供重要的決策參考。實驗表明SMODE-HMC算法可以為實際多目標優(yōu)化問題的求解提供有效幫助。