李智翔,李赟,賀亮,沈超

(1.盲信號處理重點實驗室,610041,成都; 2.西安交通大學(xué)智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點實驗室,710049,西安)

在許多實際的工程問題,如規(guī)劃調(diào)度、數(shù)據(jù)挖掘、資源分配、電路設(shè)計、控制系統(tǒng)等等問題中,由于問題的復(fù)雜性,優(yōu)化目標(biāo)往往不止一個,多個優(yōu)化目標(biāo)之間相互沖突并且取值隨時間變化,這樣的優(yōu)化問題被稱作動態(tài)多目標(biāo)優(yōu)化問題(dynamic multiobjective optimization problems,DMOPs)[1]。與求解靜態(tài)多目標(biāo)優(yōu)化問題不同,在處理動態(tài)多目標(biāo)優(yōu)化問題時,需要在每次環(huán)境發(fā)生變化之前找到近似最優(yōu)解集,這就要求算法能夠跟蹤隨時間變化的環(huán)境[2]。特別地,當(dāng)環(huán)境變化的速度較快時,動態(tài)多目標(biāo)優(yōu)化問題的求解難度進(jìn)一步提升。

近些年來,在動態(tài)多目標(biāo)優(yōu)化問題的相關(guān)研究領(lǐng)域,學(xué)者做了很多工作,其中一部分研究工作針對如何在動態(tài)多目標(biāo)優(yōu)化算法的迭代過程中檢測環(huán)境變化。文獻(xiàn)[3]提出了一種最常見的基于解再計算方式檢測環(huán)境變化的方法,文獻(xiàn)[4]提出了一種基于反轉(zhuǎn)模型的兩階段檢測的方法,文獻(xiàn)[5]則通過解的分布性來判斷環(huán)境的變化情況。動態(tài)多目標(biāo)優(yōu)化算法為了在變化發(fā)生時加快收斂速度,通常需要在變化時增加解集的多樣性。文獻(xiàn)[6]通過優(yōu)化變異算子來增加解集的多樣性,文獻(xiàn)[7]通過對部分解進(jìn)行重定位來增加解集的多樣性,文獻(xiàn)[8]通過引入多種群協(xié)同進(jìn)化機(jī)制,使得不同種群采用不同的進(jìn)化策略,從而增加了解集的多樣性。為了跟隨和預(yù)測環(huán)境的變化,一些學(xué)者對基于歷史記錄的方法進(jìn)行了深入研究:文獻(xiàn)[9]采用記憶串的方式對歷史信息進(jìn)行記錄,保持解的多樣性并快速響應(yīng)新的環(huán)境變化;文獻(xiàn)[10]提出了通過維護(hù)一個外部存儲空間來保留歷史信息,利用歷史信息實現(xiàn)對變化后的最優(yōu)解集進(jìn)行快速逼近;文獻(xiàn)[11]通過對動態(tài)變化的環(huán)境進(jìn)行學(xué)習(xí),自適應(yīng)地調(diào)整算法參數(shù),從而提升了算法效率。除了對歷史信息的記錄,學(xué)者們還提出采用預(yù)測的方法對變化后的環(huán)境進(jìn)行主動判斷和逼近,已有的研究成果包括對最優(yōu)解的變化進(jìn)行預(yù)測[12]、對區(qū)域的變動進(jìn)行預(yù)測[13]、對變化發(fā)生的時間進(jìn)行預(yù)測[14]等。與其他思路相比,采用預(yù)測思想的算法取得了較好的效果,但該類算法應(yīng)用于實際問題求解時仍存在對快速變化的最優(yōu)解集的跟蹤能力不強(qiáng),算法運行效率較差等問題,有待進(jìn)一步解決。

本文采用預(yù)測解集變化的思路,提出了一種基于卡爾曼濾波的動態(tài)多目標(biāo)優(yōu)化算法(dynamic multiobjective optimization evolutionary algorithm based on decomposition with Kalman filter,DDKF)?？柭鼮V波是一種利用包含噪聲的觀測數(shù)據(jù)對未來數(shù)據(jù)進(jìn)行預(yù)測的方法,其思想在動態(tài)優(yōu)化算法中得到了廣泛的使用[15-16]?？柭鼮V波能夠快速、準(zhǔn)確地跟蹤線性系統(tǒng)的變化,具有計算復(fù)雜度低、抗噪聲干擾能力強(qiáng)等特點,適合動態(tài)多目標(biāo)優(yōu)化算法用來在環(huán)境變化時快速逼近最優(yōu)解。與已有算法為每個解維護(hù)一個卡爾曼濾波模型不同,DDKF算法提出了一種全新的預(yù)測模型,一方面通過記錄每次環(huán)境變化前解集的中心并使用卡爾曼濾波對該中心進(jìn)行預(yù)測,利用中心變化的方向和幅度對一部分新解進(jìn)行放置和搜索,并且為每個新解增加垂直于變化方向的隨機(jī)擾動以豐富新解的多樣性;另一方面,保持一部分解不變,避免因變化方向無規(guī)律時導(dǎo)致預(yù)測偏差較大影響解的收斂速度。與其他3種算法在標(biāo)準(zhǔn)測試集上的對比實驗表明,本文DDKF算法在大多數(shù)測試函數(shù)上得到的結(jié)果優(yōu)于其他3種算法,并且算法運行時間較已有的基于卡爾曼濾波模型進(jìn)行預(yù)測的MOEA/D-KF算法[15]更短,從而說明了DDKF算法的有效性。

1 背景知識

1.1 動態(tài)多目標(biāo)優(yōu)化問題

一個動態(tài)多目標(biāo)優(yōu)化問題的優(yōu)化模型如下

(1)

1.2 基于分解的多目標(biāo)優(yōu)化算法

基于分解的多目標(biāo)進(jìn)化算法的核心思想是通過降維的方式將一個高維的多目標(biāo)優(yōu)化問題轉(zhuǎn)換成若干子問題,子問題通常是單目標(biāo)優(yōu)化問題。每個子問題對應(yīng)原多目標(biāo)優(yōu)化問題的一個解,由于不同子問題的參數(shù)不同,因此通過合理地選擇參數(shù),所有子問題的解組合起來就構(gòu)成了原多目標(biāo)優(yōu)化問題的最優(yōu)解集。在求解的過程中,子問題既可以獨立求解,也可以通過對比采納參數(shù)相近的鄰居子問題得到的解加速自身的收斂速度。與其他多目標(biāo)優(yōu)化算法相比,基于分解的多目標(biāo)優(yōu)化算法通常具有較好的收斂速度并且能夠得到分布多樣性更優(yōu)的解集[18]。

1.3 卡爾曼濾波預(yù)測模型

參考文獻(xiàn)[19],考慮一個線性系統(tǒng)的狀態(tài)差分方程如下

xt=Axt-1+But-1+wt-1

(2)

式中:xt∈Rn為t時刻的系統(tǒng)狀態(tài)變量;A為n×n的轉(zhuǎn)換矩陣;ut-1為t-1時刻的系統(tǒng)輸入,長度為l;B為將輸入轉(zhuǎn)換為狀態(tài)的矩陣,大小為n×l;wt-1為t-1時刻的系統(tǒng)噪聲。t時刻的測量值zt∈Rm可表示為

zt=Hxt+vt

(3)

式中:H是狀態(tài)變量到測量的轉(zhuǎn)換矩陣,其大小為m×n;vt為t時刻的測量噪聲。假設(shè)任意時刻的系統(tǒng)噪聲w和測量噪聲v是相互獨立的白噪聲,且具有如下多元高斯分布

(4)

式中Q、R分別為系統(tǒng)噪聲和測量噪聲的協(xié)方差矩陣?？柭鼮V波的預(yù)測模型采用迭代的形式,模型估計某一時刻的狀態(tài),之后收到帶有噪聲的測量值反饋后對模型進(jìn)行修正,如此往復(fù)?？柭鼮V波預(yù)測模型的公式分為時間更新和測量更新兩個部分,時間更新和測量更新的公式如下

(5)

(6)

2 動態(tài)多目標(biāo)優(yōu)化算法DDKF

2.1 卡爾曼濾波模型設(shè)計

(7)

(8)

式中:x為決策空間的變量;v表示x的一階導(dǎo)數(shù),即觀測對象的速度;a為x的二階導(dǎo)數(shù),即觀測對象的加速度。采用這樣的定義,有利于將更多的歷史數(shù)據(jù)用來進(jìn)行預(yù)測。系統(tǒng)只能通過x進(jìn)行觀測,有

(9)

(10)

式中:矩陣A的值表示這里的卡爾曼濾波模型為二階線性模型;矩陣H的值表示在該問題中只能測量到系統(tǒng)狀態(tài)變量的第一維,即觀測對象的位置。結(jié)合式(5)可以看出,對觀測對象下一時刻的位置的預(yù)測,與上一時刻的位置、速度的預(yù)測值和上一時刻的位置測量值有關(guān)。

2.2 新解集的生成

當(dāng)根據(jù)卡爾曼濾波預(yù)測模型得到t+1時刻的預(yù)測值xt+1時,可以計算出相應(yīng)的位移為

(11)

V(dt)={v∈Rn:‖v‖=1,dtv=0}

(12)

對t+1時刻變化之前得到的解集中的任意一個解x,所對應(yīng)的新解xnew的計算方式如下

(13)

式(13)表明:一部分新解按照概率pn保持不變,避免預(yù)測產(chǎn)生錯誤;其他新解則在原始解的基礎(chǔ)上疊加預(yù)測的位移分量和垂直的超平面擾動分量。這樣處理能夠進(jìn)一步增加新解的多樣性,避免因變化方向預(yù)測的錯誤帶來對收斂速度的影響。

圖1 本文算法在環(huán)境變化時的預(yù)測模型

2.3 算法流程

步驟1初始化種群、權(quán)重向量、鄰居大小等參數(shù);

步驟4判斷環(huán)境是否發(fā)生變化:若未變化,則跳轉(zhuǎn)至步驟9;若環(huán)境發(fā)生變化,繼續(xù)執(zhí)行步驟5;

步驟5應(yīng)用式(7)生成當(dāng)前時刻的中心點,即測量值zt;

步驟6應(yīng)用式(6)進(jìn)行卡爾曼濾波測量更新;

步驟7利用式(5)進(jìn)行卡爾曼濾波時間更新,得到對下一時刻的預(yù)測值xt+1;

步驟8根據(jù)式(11)～式(13)計算生成新一代解;

步驟9進(jìn)行下一代進(jìn)化。若算法達(dá)到終止條件,則返回結(jié)果,算法結(jié)束;否則返回步驟2。

3 實驗分析

3.1 實驗設(shè)置

為了驗證本文DDKF算法的有效性,選擇3種優(yōu)秀的動態(tài)多目標(biāo)優(yōu)化算法進(jìn)行對比測試。這3種算法分別是DNSGAII算法[20]、MOEA/D-KF算法[15]及PPS算法[21]。其中DNSGAII是在經(jīng)典的多目標(biāo)優(yōu)化算法NSGAII的基礎(chǔ)上針對動態(tài)多目標(biāo)優(yōu)化問題重新設(shè)計的算法;MOEA/D-KF是一種為每個解構(gòu)造一個卡爾曼濾波預(yù)測模型的基于分解的動態(tài)多目標(biāo)優(yōu)化算法;PPS算法對分布進(jìn)行了估計,并采用了一種時間序列回歸分析的技術(shù)進(jìn)行預(yù)測。

本文選擇使用10個動態(tài)多目標(biāo)測試函數(shù)對上述算法進(jìn)行對比測試,這些測試函數(shù)選自文獻(xiàn)[21-23]。測試函數(shù)的特征如表1所示。

表1 測試函數(shù)屬性

DNSGAII算法、MOEA/D-KF算法以及PPS算法的參數(shù)參照相應(yīng)文獻(xiàn)進(jìn)行設(shè)置,其他參數(shù)設(shè)置如下:種群大小為100;算法執(zhí)行代數(shù)為4 000代,變化程度nt=10,式(13)中pn=0.3。此外,為了對4種算法在動態(tài)多目標(biāo)優(yōu)化問題發(fā)生變化前充分收斂和未充分收斂的情況進(jìn)行分析,令環(huán)境變化頻度τt的值分別取40和5,其他參數(shù)不變。4種算法在10個測試函數(shù)上分別運行20次。

(14)

3.2 實驗結(jié)果和分析

4種算法在10個測試函數(shù)上的平均反向距離指標(biāo)均值測試結(jié)果如表2所示?？梢钥闯?針對環(huán)境變化頻度τt取40的情形,本文提出的DDKF算法在10個測試函數(shù)中的8個測試函數(shù)上的平均反向距離指標(biāo)測試結(jié)果優(yōu)于其他3種算法,而MOEA/D-KF算法和PPS算法分別在dMOP2和F7測試函數(shù)上最優(yōu);針對環(huán)境變化頻度τt取5的情形,本文提出的DDKF算法在10個測試函數(shù)中的7個測試函數(shù)上的平均反向距離指標(biāo)結(jié)果優(yōu)于其他3種算法,而MOEA/D-KF算法在FDA1測試函數(shù)上最優(yōu),PPS算法在dMOP1和F7兩個測試函數(shù)上最優(yōu)。測試結(jié)果說明,本文提出的DDKF算法在大多數(shù)測試函數(shù)上優(yōu)于其他3種算法,當(dāng)環(huán)境變化頻度τt由40變成5時,MOEA/D-KF算法、PPS算法和本文提出的DDKF算法得到的平均反向距離指標(biāo)結(jié)果平均有3～5倍的增大,而DNSGAII算法得到的結(jié)果平均有1個數(shù)量級左右的增大,其增幅大于其他3種算法。這是因為當(dāng)環(huán)境變化頻度τt由40變成5時,每次變化之間的迭代次數(shù)減少,由于算法均不能充分收斂,相應(yīng)的平均反向距離指標(biāo)結(jié)果均較原先的值變差,但此時本文提出的DDKF算法在大部分測試函數(shù)上仍優(yōu)于其他3種算法。此外,與DNSGAII算法采用隨機(jī)初始化策略對種群進(jìn)行處理相比,其他3種算法均采用了各自不同的預(yù)測策略,其效果優(yōu)于DNSGAII的隨機(jī)初始化策略,尤其是當(dāng)環(huán)境變化頻度τt的值取5時,算法在兩次變化之間的迭代次數(shù)較少,無法充分收斂,此時具有預(yù)測策略的3種算法的優(yōu)勢更加明顯。

為了進(jìn)一步說明本文提出的DDKF算法的有效性,選取F6測試函數(shù)對上述4種算法在環(huán)境變化頻度τt的值取40時的測試結(jié)果進(jìn)行深入分析。首先對4種算法在F6上不同時刻的反向距離指標(biāo)的值進(jìn)行對比,結(jié)果如圖2和圖3所示?？梢钥闯?本文提出的DDKF算法在迭代次數(shù)為5之后基本趨于穩(wěn)定,反向距離隨環(huán)境變化的波動很小,且平均值小于其他3種算法;MOEA/D-KF算法及PPS算法的結(jié)果相當(dāng),但PPS波動性較小;從算法的穩(wěn)定性來講,本文算法優(yōu)于MOEA/D-KF算法;DNSGAII算法的結(jié)果差于其他3種算法,且波動性較強(qiáng)。

表2 4種算法的平均反向距離比較

注:黑體數(shù)據(jù)表示最優(yōu)值

圖2 4種算法在F6測試函數(shù)上不同迭代次數(shù)的 反向距離對比

圖3 4種算法在F6測試函數(shù)上的反向距離的箱線圖對比

為了觀察不同時刻4種算法得到的解的分布情況,這里選取了t為65、67、69、71、73 s這5個時刻4種算法得到的解在目標(biāo)空間的值,其結(jié)果如圖4至圖7所示。圖中實線為不同時刻的最優(yōu)面,點為不同時刻求得的解集?？梢钥闯?本文提出的DDKF算法在這5個時刻的解均優(yōu)于其他3種算法的對應(yīng)解,收斂性好且分布較為均勻,基本覆蓋了整個最優(yōu)面;PPS算法和MOEA/D-KF算法的結(jié)果次之,收斂性較好但分布不夠均勻,最優(yōu)面的一些片段附近并沒有相應(yīng)的解;而DNSGAII算法的收斂性差于上述3種算法,分布均勻程度與MOEA/D-KF算法和PPS算法相當(dāng)。

為了對比分析不同算法的時間效率,將4種算法在上述10個測試函數(shù)上分別運行10次,記錄并對比總的運行時間。令本文提出算法DDKF的總運行時間為1,其他3種算法的總運行時間與本文算法運行時間的比值如表3所示。

表3 4種算法的運行時間對比

由表3可以看出,DNSGAII算法的運行時間最短,本文DDKF算法次之,而MOEA/D-KF算法和PPS算法運行時間較長。這是因為:與其他3種算法相比,DNSGAII采用的隨機(jī)初始化策略較為簡單,時間復(fù)雜度較低;與PPS使用的回歸模型相比,本文DDKF算法使用的單個狀態(tài)向量的卡爾曼濾波模型時間復(fù)雜度更低,而MOEA/D-KF盡管也采用了卡爾曼濾波模型,但該算法對每一個解分別構(gòu)造一個卡爾曼濾波模型,而本文僅構(gòu)造了一個卡爾曼濾波模型,因此本文提出的DDKF算法運行時間優(yōu)于MOEA/D-KF算法和PPS算法。

圖4 在測試函數(shù)F6上DNSGAII算法的結(jié)果分布

圖5 在測試函數(shù)F6上MOEA/D-KF算法的結(jié)果分布

圖6 在測試函數(shù)F6上PPS算法的結(jié)果分布

圖7 在測試函數(shù)F6上DDKF算法的結(jié)果分布

4 結(jié) 論

當(dāng)環(huán)境發(fā)生變化時,如何快速均勻地收斂到新的最優(yōu)面是動態(tài)多目標(biāo)優(yōu)化算法需要解決的一個核心問題。本文設(shè)計了一種新的預(yù)測方法,一方面使用卡爾曼濾波模型對不同時刻的解集中心點進(jìn)行跟蹤,預(yù)測其變化;另一方面為新解集在預(yù)測的變化方向的垂直超平面上增加一個擾動量,使得新解集保持充分的多樣性。與其他優(yōu)秀算法在公開測試集上的對比實驗結(jié)果證明了本文提出算法的有效性。如何優(yōu)化選取參考點以及如何在環(huán)境不變時加速算法收斂是今后研究的重點。