一種采用改進(jìn)交叉熵的多目標(biāo)優(yōu)化問題求解方法

趙舵,唐啟超,余志斌

(西南交通大學(xué)電氣工程學(xué)院,610031,成都)

交叉熵(Cross Entropy,CE)優(yōu)化算法是一類新型的啟發(fā)式隨機(jī)優(yōu)化算法,在優(yōu)化過程中無需優(yōu)化問題的梯度信息,僅根據(jù)適應(yīng)度函數(shù)進(jìn)行尋優(yōu),具有計算復(fù)雜度低、魯棒性強(qiáng)并能以較大概率求得全局最優(yōu)解的特點(diǎn)[1-4]。目前,有關(guān)CE優(yōu)化算法的研究已經(jīng)取得了一定進(jìn)展,并解決了許多優(yōu)化問題。在單目標(biāo)優(yōu)化問題的求解方面:文獻(xiàn)[5]介紹了基本CE優(yōu)化算法的原理及改進(jìn),并討論了其在組合優(yōu)化和機(jī)器學(xué)習(xí)方面的應(yīng)用;文獻(xiàn)[6]在CE優(yōu)化算法的開發(fā)和迭代過程中做了改進(jìn),提高了收斂速度,并將其應(yīng)用于連續(xù)變量的逆問題求解;文獻(xiàn)[7]將CE優(yōu)化算法應(yīng)用于比例-積分-微分(PID)控制器的設(shè)計,并與基于遺傳算法的PID控制器設(shè)計方法進(jìn)行比較,結(jié)果表明CE優(yōu)化算法具有較低的計算復(fù)雜度。隨著研究的發(fā)展,CE優(yōu)化算法逐步被拓展到多目標(biāo)優(yōu)化問題的求解中:文獻(xiàn)[8]將廣義分解的方法和CE優(yōu)化算法結(jié)合,提出了MACE-gD算法,并與MOEA/D和RM-MEDA算法進(jìn)行了性能比較;文獻(xiàn)[9]將模糊c均值聚類算法與CE優(yōu)化算法相結(jié)合,提出了改進(jìn)交叉熵優(yōu)化算法,并應(yīng)用于解決多目標(biāo)不等間距陣列綜合問題;文獻(xiàn)[10]結(jié)合了分布估計算法和CE優(yōu)化算法的優(yōu)點(diǎn),提出了一種改進(jìn)的CE優(yōu)化算法,并應(yīng)用于合金微鉆孔加工工藝參數(shù)的多目標(biāo)優(yōu)化問題中,結(jié)果表明加工效率得到了有效提高。

高速和舒適是世界鐵路發(fā)展的主流,因此對于高速鐵道車輛橫向運(yùn)行平穩(wěn)性的要求越來越高,被動懸掛系統(tǒng)逐漸難以滿足使用要求,而主動懸掛和半主動懸掛控制是改善列車橫向運(yùn)行平穩(wěn)性的有效方法[11-12]。結(jié)合我國實(shí)際,采用半主動懸掛控制系統(tǒng)是目前最佳的控制方法[13],半主動懸掛控制系統(tǒng)的參數(shù)優(yōu)化對于列車橫向平穩(wěn)性的改善至關(guān)重要。

本文提出了采用Pareto精英個體保留排序策略以及概率分布漸進(jìn)變化的多目標(biāo)交叉熵優(yōu)化(Multi-Objective Cross Entropy Optimization,MOCEO)算法,并將其與NSGAII[14]、SPEA2[15]、MOEAD[16]以及PAES[17]算法一同應(yīng)用于經(jīng)典多目標(biāo)優(yōu)化問題求解分析,超體積和反轉(zhuǎn)世代距離指標(biāo)表明了本文算法求解多目標(biāo)問題的有效性。最后,將MOCEO應(yīng)用于17自由度列車橫向半主動控制系統(tǒng)的參數(shù)優(yōu)化,結(jié)果表明,MOCEO具有更快的收斂速度,優(yōu)化后的列車系統(tǒng)具有更好的橫向運(yùn)行平穩(wěn)性。

1 交叉熵優(yōu)化算法的基本思想

CE優(yōu)化算法源于對小概率事件的估計,后來被拓展到求解最優(yōu)化問題[18]。

l(γ)=Pu(S(x)≥γ)=

(1)

(2)

(3)

由于g*(x)和未知的l(γ)有關(guān),需在{f(·,u)}函數(shù)族內(nèi)選擇一個合適的g*(x),即選擇一個參數(shù)u使得g*(x)和{f(·,u)}的距離(即CE)最小。兩個概率密度函數(shù)h(x)和h′(x)之間的CE定義為

(4)

使得g*(x)和f(x,u)的CE最小的等價式為

minD(g*(x),f(x,u))=

(5)

將式(3)代入式(5),可以得到

(6)

傳統(tǒng)CE優(yōu)化算法主要包括以下步驟[19]:

Step3 選擇,計算適應(yīng)度函數(shù)S(xi),i=1,2,…,N,對S(xi)進(jìn)行排序得到S(1)≤S(2)≤…≤S(N),選取適應(yīng)度值大的Ne個個體,作為采集的精英樣本集合;

(7)

Step5 平滑處理,平滑系數(shù)α∈[0,1],更新μt和σt為

(8)

Step6 結(jié)果判斷,如果max{σt}<ε(ε為方差限制邊界,令ε=10-6),則程序結(jié)束返回參數(shù)μt,否則,令t←t+1,并轉(zhuǎn)到Step2。

2 多目標(biāo)交叉熵優(yōu)化算法

MOCEO算法以CE優(yōu)化算法為基礎(chǔ),下面詳細(xì)描述MOCEO算法的組成部分。

2.1 初始化

不失一般性,考慮一個包含n個變量、m個目標(biāo)的多目標(biāo)最小化問題[20],具體為

(9)

式中:xi∈[xmin,i,xmax,i],i=1,2,…,n;n為決策變量的維數(shù);m為目標(biāo)函數(shù)的個數(shù)。xmin=[xmin,1,…,xmin,n],xmax=[xmax,1,…,xmax,n]分別是決策變量的上限和下限。

2.2 快速非支配排序及適應(yīng)度值的分配

生成初始種群P0后,算法的主循環(huán)開始。在每次迭代過程中,首先分別計算第tc代種群Ptc中每個個體的適應(yīng)度函數(shù)值,隨后根據(jù)非支配排序算法確定非支配個體,并將其用于后續(xù)算法的參數(shù)更新以及個體選擇。

采用外部存檔機(jī)制,定義外部存檔集合Atc∈RNc×n存放種群中的非支配解(或Pareto近似解),定義集合P′tc∈RM×n存放支配解,其中:種群大小Nc即為集合Atc的最大容量;M是支配解的數(shù)量,它的值在每次迭代中都不同,M≤Nc。

采用文獻(xiàn)[14]中的快速非支配排序方法,將所有非支配解保留在集合Atc中,將所有支配解保存在集合P′tc中,由上文可知Ptc=Atc∪P′tc。當(dāng)|Atc|≤Nc(本文用|·|表示集合中解的數(shù)量)時,采用非支配序作為適應(yīng)度值;當(dāng)|Atc|>N時,將相同非支配序的個體進(jìn)行超體積貢獻(xiàn)度計算,優(yōu)先選取超體積貢獻(xiàn)度更大的個體存入Atc,采用非支配序和超體積貢獻(xiàn)度同時作為適應(yīng)度值。超體積又稱勒貝格測度,是對一系列解集的一種度量,反映了在目標(biāo)空間中,這些解所共同支配的空間的大小[21]。

2.3 參數(shù)更新

2.3.2 方差向量σ2t的更新 對集合Atc-1每一維的變量值分別取均值,得到

(10)

(11)

和傳統(tǒng)的CE優(yōu)化算法相同,MOCEO也使用了平滑操作來提升參數(shù)的穩(wěn)定性。若平滑系數(shù)φ∈[0,1],則新的方差向量σ2tc定義為

(12)

為了保證算法更好的跳出局部收斂,取隨機(jī)數(shù)r∈[0,1],如果r<0.1,則令σ2tc=βσ2tc,β為調(diào)節(jié)系數(shù),β>1,本文取β=100。

2.4 進(jìn)化方向更新

為了提高算法收斂到前沿面的速度,算法定義了方向向量,以采樣個體綜合算法收斂過程信息,引導(dǎo)算法加快尋優(yōu)速度。本文通過比較進(jìn)化過程中10代個體之間的差異,得到個體進(jìn)化的方向信息,用以加速種群的進(jìn)化過程,具體步驟如下:

(13)

Step3 使用dtc指導(dǎo)子代的生成,進(jìn)化10代之后,返回Step1。

2.5 子代的生成

更新了均值向量μtc和方差向量σ2tc以后,按照新的正態(tài)分布模型,結(jié)合方向向量dtc,通過采樣產(chǎn)生下一代種群Qtc。具體步驟如下。

(14)

式中:ne是適應(yīng)度函數(shù)的計算次數(shù);η為比例系數(shù),經(jīng)實(shí)驗,η=0.48時效果最好;Emax為最大計算次數(shù)。

(15)

2.6 個體選擇

在MOCEO迭代初期,有|Atc|≤N1,隨著算法的不斷收斂,落在Pareto前沿面上的個體越來越多,最終導(dǎo)致出現(xiàn)|Atc|>N1的情況,根據(jù)算法的要求需要刪除集合Atc中的一些個體,使得|Atc|=N1。對于不同層間的個體,優(yōu)先選擇非支配序低的個體存入Atc。對于同一層間個體的優(yōu)劣度的比較,采用快速排序[21]的機(jī)制來判斷計算同一層每個個體對于整個種群的超體積貢獻(xiàn)度并排序,選取貢獻(xiàn)度較大的個體存入Atc,直到|Atc|=N1。由于快速超體積排序算法的復(fù)雜度會隨著Nc的增大而呈指數(shù)級增長,為了降低算法的復(fù)雜度,減少運(yùn)算時間,在算法運(yùn)行前期取N1=0.3Nc,同時算法的迭代次數(shù)增加,算法的局部搜索精度提高。

2.7 結(jié)束條件

一般地,當(dāng)達(dá)到算法設(shè)置的Emax時,程序停止運(yùn)行,輸出保存在集合Atc中的個體作為最優(yōu)解集。

3 多目標(biāo)交叉熵優(yōu)化算法的測試與分析

為了驗證算法的有效性和魯棒性,分別針對二維ZDT[21]系列和三維DTLZ[21]系列目標(biāo)測試函數(shù),選用MOCEO、NSGA-II、SPEA2、MOEAD、PAES算法獨(dú)立運(yùn)算30次,計算超體積[22]和反轉(zhuǎn)世代距離[16]性能指標(biāo)并進(jìn)行對比分析。使用Java編程語言在jMetal框架[23]中實(shí)現(xiàn)上述優(yōu)化算法,硬件環(huán)境為Intel i7@2.6 GHz CPU,8 GB內(nèi)存。

在進(jìn)行仿真計算時,各算法的最大計算次數(shù)均設(shè)置為25 000。在MOCEO算法中,當(dāng)適應(yīng)度函數(shù)計算次數(shù)ne≤12 000時,設(shè)置種群大小Nc=100,N1=0.3Nc=30,當(dāng)12 000

3.1 不同優(yōu)化算法性能指標(biāo)的比較

反轉(zhuǎn)世代距離指標(biāo)是表征進(jìn)化計算獲得的近似Pareto面和真實(shí)Pareto面之間的距離指標(biāo),數(shù)值越小表明近似Pareto最優(yōu)解越接近真實(shí)Pareto最優(yōu)解。優(yōu)劣序是不同算法在同種測試函數(shù)下的性能指標(biāo)的均值和方差綜合排序的結(jié)果,數(shù)值越小表明算法越優(yōu)秀。表1和表2分別給出了5種算法分別對ZDT系列以及DTLZ系列測試函數(shù)獨(dú)立運(yùn)算30次所求得的超體積和反轉(zhuǎn)世代距離性能指標(biāo)的比較結(jié)果(深色單元格中的數(shù)據(jù)表示最優(yōu)值,淺色單元格中的數(shù)據(jù)表示次優(yōu)值)。從表1可以看出,在5種算法對7種測試函數(shù)的比較中,MOCEO取得了5個最優(yōu)值和2個次優(yōu)值,NSGA-II、MOEAD以及PAES分別只取得了1個次優(yōu)值,SPEA2取得了2個最優(yōu)值和2個次優(yōu)值。從表2可以看出,MOCEO取得了4個最優(yōu)值和2個次優(yōu)值。綜上可知:MOCEO在超體積和反轉(zhuǎn)世代距離指標(biāo)上明顯優(yōu)于其他4種算法,即MOCEO得到的Pareto面具有更好的貼近度和分散性;MOCEO在30次計算得到的超體積值方差很小,即MOCEO具有更好的魯棒性。

表1 不同算法對ZDT測試函數(shù)以及DTLZ測試函數(shù)優(yōu)化結(jié)果超體積值的比較

3.2 不同優(yōu)化算法收斂速度的比較

圖1是MOCEO、NSGA-II、SPEA2以及MOEAD共4種算法得到的ZDT系列二維測試函數(shù)的超體積隨計算次數(shù)的變化曲線,可以看出:對于ZDT1、ZDT2,MOCEO在2 500次時收斂到最優(yōu),NSGA-II和SPEA2在15 000次左右收斂到最優(yōu),MOEAD在25 000次之前沒有完全收斂;對于ZDT3,MOCEO在7 500次時收斂到最優(yōu),NSGA-II和SPEA2在12 500次左右收斂到最優(yōu),MOEAD沒有完全收斂;對于ZDT6,MOCEO在1 250次時收斂到最優(yōu),NSGA-II和SPEA2在22 500次左右收斂到最優(yōu),MOEAD在17 500次左右收斂到最優(yōu)。由于MOCEO算法在計算次數(shù)為12 000次時種群大小由30轉(zhuǎn)變?yōu)?00,所以超體積在圖中12 000次的位置會有一個跳變。

表2 不同算法對ZDT測試函數(shù)以及DTLZ測試函數(shù)優(yōu)化結(jié)果反轉(zhuǎn)世代距離的比較

(a)ZDT1測試函數(shù)

(c)ZDT3測試函數(shù)

(b)ZDT2測試函數(shù)

(d)ZDT6測試函數(shù)

圖2給出了MOCEO、NSGA-II和SPEA2共3種算法在DTLZ2、DTLZ5和DTLZ6這3種三維測試函數(shù)下超體積隨計算次數(shù)的變化曲線,可以看出:對于DTLZ2和DTLZ5,3種算法的收斂速度基本一致;對于DTLZ6,MOCEO在3 500次時基本收斂到最優(yōu)值,NSGA-II和SPEA2基本沒有收斂。MOCEO由于種群數(shù)量的變化,超體積會在12 000次時發(fā)生跳變。

(a)DTLZ2測試函數(shù)

(b)DTLZ5測試函數(shù)

(c)DTLZ6測試函數(shù)圖2 3種算法在3種DTLZ測試函數(shù)下超體積變化情況

綜上所述,MOCEO在ZDT1、ZDT2、ZDT3、ZDT6及DTLZ6這5種測試函數(shù)下較其他算法明顯收斂速度更快,在DTLZ2和DTLZ5這2種測試函數(shù)下收斂速度與其他算法基本持平。

4 列車懸掛半主動控制系統(tǒng)參數(shù)優(yōu)化

為了使高速列車具有更好的橫向平穩(wěn)性,主要采用半主動和主動懸掛的控制方法,控制器的選取及優(yōu)化尤為重要。

采用文獻(xiàn)[11]中的高速列車17自由度橫向振動模型,以水平不平順、方向不平順及速度v為模型輸入,車體橫向振動合成加速度為模型輸出,設(shè)置車輛運(yùn)行速度v=300 km/h。采用MOCEO算法和NSGA-II算法分別對模型中的廣義預(yù)測控制器[24]進(jìn)行優(yōu)化,選擇預(yù)測時域長度P和控制時域長度P′作為決策變量,選擇列車在直線軌道上輪對橫移量的均方根f1、車體橫向加速度的均方根f2以及列車橫向平穩(wěn)性指標(biāo)[25]f3作為3個優(yōu)化目標(biāo)。設(shè)置種群大小Nd=50,迭代次數(shù)g=100,決策變量P∈(0,300],P′∈(0,300],P和P′均為正整數(shù)。

4.1 控制器參數(shù)優(yōu)化結(jié)果

兩種優(yōu)化算法對控制器進(jìn)行優(yōu)化后,種群個體在空間中的分布如圖3所示可以看出,MOCEO算法得到的個體解可以支配NSGA-II得到的個體解,即MOCEO算法具有更好的優(yōu)化效果。對于MOCEO算法,選取圖中下邊界上的點(diǎn)對應(yīng)參數(shù)作為控制器參數(shù)的優(yōu)化結(jié)果,此時P=13,P′=2,平穩(wěn)性指標(biāo)f3為1.357 8。對于NSGA-II算法,選取圖中下邊界上的點(diǎn)對應(yīng)參數(shù)作為控制器參數(shù)的優(yōu)化結(jié)果,此時P=10,P′=5,平穩(wěn)性指標(biāo)f3為1.416 7。可見,通過MOCEO算法的優(yōu)化,平穩(wěn)性指標(biāo)由1.416 7減小到了1.357 8,平穩(wěn)性提高了4.16%。

圖3 兩種優(yōu)化算法的解的空間分布圖

4.2 兩種算法優(yōu)化后懸掛系統(tǒng)的比較

將MOCEO和NSGA-II得到的控制參數(shù)分別代入仿真模型,得到車體橫向振動加速度的時域、頻譜、功率譜密度,如圖4所示,a表示加速度,t表示時間,f表示頻率,dps表示功率密度。由圖4a看出,車體橫向加速度峰值由0.145 m/s2減小到0.13 m/s2,下降了10.34%。可見采用MOCEO算法優(yōu)化后列車的橫向平穩(wěn)性得到較大改善,旅客乘坐舒適性提高。由圖4b和圖5c可以看出,車體橫向振動加速度主要集中在0.5～5 Hz,而人體對橫向振動最敏感頻率范圍為1～2 Hz,相比于NSGA-II算法,采用MOCEO算法優(yōu)化后,在該頻率范圍內(nèi)車體橫向振動加速度明顯改善。

(a)時譜

(b)頻譜

(c)功率譜密度圖4 車體橫向加速度時域、頻域、功率譜密度

5 結(jié) 論

(1)針對多目標(biāo)優(yōu)化問題,引入進(jìn)化方向,設(shè)置新的子代生成方式,提出一種改進(jìn)的CE優(yōu)化算法MOCEO。ZDT系列和三維DTLZ系列目標(biāo)測試函數(shù)的測試結(jié)果證明,MOCEO是一種快速、有效的多目標(biāo)優(yōu)化算法。

(2)將MOCEO應(yīng)用于某型高速列車橫向穩(wěn)定控制系統(tǒng)的參數(shù)優(yōu)化,仿真結(jié)果表明,車體橫向加速度峰值以及平穩(wěn)性指標(biāo)均得到改善,較NSGA-II算法取得了更優(yōu)的橫向平穩(wěn)性和舒適性。

(3)算法種群大小Nc和平滑操作系數(shù)α是MOCEO的主要參數(shù),對算法性能有著重要影響。采用動態(tài)種群大小策略,即在進(jìn)化不同階段分別設(shè)置不同種群的大小,可以使算法更好地平衡探索和獲得更優(yōu)的開采性能。

(4)今后一方面將研究種群規(guī)模自適應(yīng)調(diào)整變化策略對算法性能的影響,另一方面將研究平滑系數(shù)α的設(shè)置方式及不同的概率模型對算法性能的影響。