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

趙舵,唐啟超,余志斌

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

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

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

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

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

2.1 初始化

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

(9)

式中:xi∈[xmin,i,xmax,i],i=1,2,…,n;n為決策變量的維數(shù);m為目標函數(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ù)更新以及個體選擇。

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

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

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

2.4 進化方向更新

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

(13)

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

2.5 子代的生成

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

(14)

式中:ne是適應(yīng)度函數(shù)的計算次數(shù);η為比例系數(shù),經(jīng)實驗,η=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]的機制來判斷計算同一層每個個體對于整個種群的超體積貢獻度并排序,選取貢獻度較大的個體存入Atc,直到|Atc|=N1。由于快速超體積排序算法的復(fù)雜度會隨著Nc的增大而呈指數(shù)級增長,為了降低算法的復(fù)雜度,減少運算時間,在算法運行前期取N1=0.3Nc,同時算法的迭代次數(shù)增加,算法的局部搜索精度提高。

2.7 結(jié)束條件

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

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

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

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

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

反轉(zhuǎn)世代距離指標是表征進化計算獲得的近似Pareto面和真實Pareto面之間的距離指標,數(shù)值越小表明近似Pareto最優(yōu)解越接近真實Pareto最優(yōu)解。優(yōu)劣序是不同算法在同種測試函數(shù)下的性能指標的均值和方差綜合排序的結(jié)果,數(shù)值越小表明算法越優(yōu)秀。表1和表2分別給出了5種算法分別對ZDT系列以及DTLZ系列測試函數(shù)獨立運算30次所求得的超體積和反轉(zhuǎn)世代距離性能指標的比較結(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)世代距離指標上明顯優(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)化尤為重要。

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

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

兩種優(yōu)化算法對控制器進行優(yōu)化后,種群個體在空間中的分布如圖3所示可以看出,MOCEO算法得到的個體解可以支配NSGA-II得到的個體解,即MOCEO算法具有更好的優(yōu)化效果。對于MOCEO算法,選取圖中下邊界上的點對應(yīng)參數(shù)作為控制器參數(shù)的優(yōu)化結(jié)果,此時P=13,P′=2,平穩(wěn)性指標f3為1.357 8。對于NSGA-II算法,選取圖中下邊界上的點對應(yīng)參數(shù)作為控制器參數(shù)的優(yōu)化結(jié)果,此時P=10,P′=5,平穩(wěn)性指標f3為1.416 7?？梢?通過MOCEO算法的優(yōu)化,平穩(wěn)性指標由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)針對多目標優(yōu)化問題,引入進化方向,設(shè)置新的子代生成方式,提出一種改進的CE優(yōu)化算法MOCEO。ZDT系列和三維DTLZ系列目標測試函數(shù)的測試結(jié)果證明,MOCEO是一種快速、有效的多目標優(yōu)化算法。

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

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

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