江儲文,葛方振,劉懷愚,高向軍,沈龍鳳

(淮北師范大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,安徽 淮北 235000)

動態(tài)多目標(biāo)優(yōu)化問題(dynamic multi-objective optimization problems,DMOPs)廣泛地存在現(xiàn)實生活中,如動態(tài)調(diào)度[1-3]、路徑規(guī)劃[4-5]、貨位優(yōu)化[6-7]。動態(tài)多目標(biāo)優(yōu)化問題具有時變的目標(biāo)函數(shù)和約束條件的特征,因此求解動態(tài)多目標(biāo)優(yōu)化問題不僅要得到最優(yōu)解或最優(yōu)前沿,而且要在下一次變化之前持續(xù)快速地得到最優(yōu)解或最優(yōu)前沿。處理動態(tài)多目標(biāo)優(yōu)化問題的技術(shù)有很多,如遺傳算法[8-9]、人工免疫系統(tǒng)[10]、粒子群優(yōu)化[11-12]等,其中進化算法是最受研究者關(guān)注的方法之一[13]。求解DMOPs的傳統(tǒng)方法通常是當(dāng)環(huán)境變化時在傳統(tǒng)的靜態(tài)多目標(biāo)優(yōu)化算法中增加種群多樣性[9-14],如DNSGA-Ⅱ[14],在每次環(huán)境變化時通過移民策略增加種群多樣性,DNSGA-Ⅱ-A 通過替換ζ%新種群增加多樣性,DNSGA-Ⅱ-B通過替換ζ%具有突變解的新種群確保多樣性。這些方法僅增加種群多樣性,尋找最優(yōu)解的能力仍然依靠種群的自主進化,其主要缺點是種群的收斂性差和收斂速度慢。為此,研究人員提出基于記憶的策略和基于預(yù)測的策略來引導(dǎo)種群進化方向。記憶策略根據(jù)以前獲得的最優(yōu)解或其他最優(yōu)信息來快速應(yīng)對環(huán)境變化,這對周期性的環(huán)境變化能夠取得較好的效果,但是對于非周期性的環(huán)境變化難以獲得較好的收斂性。GOH 和TAN 將存檔中的過時個體添加到臨時內(nèi)存中[8],并根據(jù)外部種群更新存檔,這樣任何關(guān)于當(dāng)前種群的有用信息都可以被使用。預(yù)測策略利用歷史環(huán)境信息預(yù)測新環(huán)境最優(yōu)解的位置,引導(dǎo)種群進化加快算法的收斂速度,但是歷史環(huán)境信息眾多,如何選取有的信息十分重要,利用PF 面上的信息進行預(yù)測是一種有效的方法。HATZAKIS 和WALLACE 提出了一種向前預(yù)測策略(FPS)[15],FPS通過PF 面上的邊界點和自回歸模型預(yù)測新的最優(yōu)解位置,從而加速種群收斂。LI等[16]提出一種基于特殊點的預(yù)測策略(SPPS),SPPS通過中心點和特殊點跟蹤PF 來快速響應(yīng)環(huán)境變化。然而,PF上有很多信息(中心點,邊界點等),所以想要跟蹤PF就需要選擇一些有代表性的點。DEB[17]證明了在HV[18]度量標(biāo)準(zhǔn)下拐點優(yōu)于PF上的其他點。ZOU 等[18]提出一種基于中心點和拐點的預(yù)測策略(CKPS),將拐點集加入預(yù)測種群中,引導(dǎo)種群收斂,同時指出PF上的拐點是邊際收益率最大的點。此外,研究人員開始將機器學(xué)習(xí)知識加入到進化計算中。2017 年,JIANG等[19]提出了基于遷移學(xué)習(xí)的動態(tài)多目標(biāo)優(yōu)化算法(Tr-DMOEA)。現(xiàn)有的大多數(shù)動態(tài)多目標(biāo)優(yōu)化算法通常假設(shè)不同環(huán)境下的決策空間分布是獨立同分布(IID),JIANG 等認為這樣的假設(shè)可能會導(dǎo)致算法失敗。因此,他們提出了一種新的假設(shè):DMOPs在不同的環(huán)境下解空間相互獨立,并且解空間分布不同,但是它們具有相關(guān)性。JIANG 等將Tr-DMOEA 加入3種著名的多目標(biāo)優(yōu)化算法:NSGA-Ⅱ[20]、MOPSO[21]和RM-MEDA[22],并且做了一系列的對比實驗,實驗結(jié)果表明將遷移學(xué)習(xí)技術(shù)引入動態(tài)優(yōu)化算法中,可以大大提高解的質(zhì)量和算法的魯棒性。

通過對遷移學(xué)習(xí)和拐點的分析,本研究提出一種基于遷移學(xué)習(xí)的拐點預(yù)測策略(TKPS)求解動態(tài)多目標(biāo)優(yōu)化問題。實驗選取DMOP1,DMOP2,DMOP3[23],FDA1,FDA2,FDA3、FDA4 和FDA5[23]8個經(jīng)典動態(tài)測試函數(shù),將TKPS 算法與DNSGA-Ⅱ[11],PPS[24],Tr-RM-MEDA[19]算法進行對比研究,實驗結(jié)果表明TKPS算法能更好地響應(yīng)環(huán)境變化。

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

在不失一般性的前提下,DMOP可以定義為[13]

其中:x 為決策變量,f 是與時間變量t有關(guān)的M 維目標(biāo)函數(shù),g 和h 的函數(shù)分別表示不等式和等式約束集,t表示問題的時間或動態(tài)性質(zhì),M 表示目標(biāo)函數(shù)的個數(shù)。

定義1(Pareto支配)設(shè)p 和q 是種群中任意兩個個體,p 支配q 表示為f(p)?f(q),當(dāng)且僅當(dāng)fi(p)≤fi(q),?i＝{1,2,…,m}且?j＝{1,2,…,m}滿足fj(p)＜fj(q)。

定義2(Pareto最優(yōu)解集,PS)設(shè)x 為決策變量,Ω 為決策空間,F 為目標(biāo)函數(shù),則PS 定義為

定義3(Pareto最優(yōu)前沿,PF)設(shè)x 為決策變量,F 為目標(biāo)函數(shù),則PF 定義為

PF＝{y＝F(x)|x∈PS}。

2 基于遷移學(xué)習(xí)的拐點預(yù)測策略

2.1 PF拐點

拐點是距離PF 邊界點連線最遠的點[18],圖1給出拐點的尋找過程。

圖1 尋找拐點的示意圖Fig.1 Sketch map of finding knee points

設(shè)有2個目標(biāo)函數(shù),A～N 是14個非支配點,其中M 和N 是非支配集的邊界點,M、N 構(gòu)成直線L。將PF 分成三個區(qū)域,在每個區(qū)域內(nèi)找出距離直線L 最遠的非支配點作為拐點,因此B、G 和K是該PF 的拐點。當(dāng)目標(biāo)函數(shù)的個數(shù)是3時,用非支配集的邊界點構(gòu)成一個平面,然后在每個區(qū)域內(nèi)找到距離平面最遠的非支配點作為拐點。

具體步驟如算法1所示。

算法1尋找拐點的偽代碼:Seek Knee

輸入:PF,拐點數(shù)目Knum。

輸出:拐點集Knee。

1)尋找邊界點,用邊界點構(gòu)成直線或平面;

2)將PF 平均分成Knum 個區(qū)域;

3)分別計算Knum 個區(qū)域上的點到直線或平面的距離,找出每個區(qū)域上距離直線或平面最遠的點作為拐點,并將它們存入拐點集Knee中。

2.2 遷移成分分析

遷移成分分析[25](transfer component analysis,TCA)是本工作使用的遷移學(xué)習(xí)方法,TCA 算法用來處理領(lǐng)域適應(yīng)問題,當(dāng)源域和目標(biāo)域處于不同的數(shù)據(jù)分布時,將兩個域的數(shù)據(jù)一起映射到一個高維希爾伯特空間中,并且在此空間中最小化源域數(shù)據(jù)與目標(biāo)域數(shù)據(jù)的距離。在處理DMOPs時,將得到的t時刻的帕累托最優(yōu)前沿(PF)作為源域,以t＋1時刻的可行解為目標(biāo)域,使用TCA 算法得到映射矩陣W。

2.3 記憶策略

基于記憶的方法在解決循環(huán)變化的DMOPs時是有效的。使用非支配排序的方法從種群中選取優(yōu)秀個體保存在內(nèi)存池中,如果內(nèi)存池滿了,就把當(dāng)前時刻的優(yōu)秀個體取代最先進入內(nèi)存池的個體。記憶策略的具體步驟如算法3所示。

算法3記憶策略:Ememory

輸入:內(nèi)存池Memory,內(nèi)存池容量Msize,當(dāng)前時刻的種群Popt,Esize。

輸出:Memory。

1)使用非支配排序從當(dāng)前種群Popt中找到Esize個優(yōu)秀個體;

2)判斷Memory是否已滿,如果內(nèi)存池滿了就轉(zhuǎn)到步驟2;否則將Esize個優(yōu)秀個體存入Memory;

3)Ememory使用“先進先出”原則更新Memory。

2.4 TKPS算法

本工作使用RM-MEDA 算法[22]對種群進行優(yōu)化,并從種群中選取優(yōu)秀個體存入Memory中。如果環(huán)境發(fā)生變化,從Memory中選取個體組成2個種群,分別作為t 時刻和t＋1 時刻的種群(如果Memory中的個體不足以組成2個種群,那么不足的個體隨機生成),然后計算得到它們的目標(biāo)值Yt和Yt＋1,將Yt作為源域,Yt＋1作為目標(biāo)域,通過TCA 算法得到映射關(guān)系矩陣W。通過映射關(guān)系矩陣W 將t時刻PF的拐點集Kneet映射到高維希爾伯特空間得到一組映射解PLSk,然后在高維希爾伯特空間內(nèi)找到下一時刻PFt＋1的拐點集對應(yīng)的個體集KneePt＋1。

為了增加種群的多樣性,在t＋1 時刻Knum個拐點對應(yīng)的個體Pj周圍,半徑為r 的區(qū)域內(nèi)隨機產(chǎn)生4×Knum 個伴隨個體(如果伴隨個體超出決策空間范圍,就將其刪除),伴隨個體表示如下:

將KneePt＋1和4×Knum 個伴隨個體放在一起進行非支配排序,選出2×Knum 個相對最優(yōu)的個體添加到下一時刻的初始種群Popt＋1中。TKPS算法的具體步驟如算法4所示。

算法4TKPS算法偽代碼

輸入:動態(tài)多目標(biāo)優(yōu)化問題F(x,t)。

輸出:F(x,t)的最優(yōu)解集PS。

1)初始化:t＝0,隨機初始化種群Pop0,Esize,,Msize,Knum;

2)檢測環(huán)境是否發(fā)生變化,如果環(huán)境發(fā)生變化,轉(zhuǎn)步驟5;否則轉(zhuǎn)步驟3;

3)使用RM-MEDA 算法求出當(dāng)前時刻的PS、PF 和種群Popt;

4)Memory ＝Ememory (Memory,Esize,Msize,Popt);

5)環(huán)境發(fā)生變化:使用TCA 算法得到映射關(guān)系矩陣W;

6)Kneet＝Seek Knee(PF,Knum);

7)通過W 將拐點集Kneet映射到高維希爾伯特空間中,得到PLSk;

8)設(shè)置t＝t＋1;

9)for k∈PLSkdo;

10)在當(dāng)前解空間中找到個體q,使得它的目標(biāo)值在高維希爾伯特空間中的映射離k 最近,那么q就作為下一時刻PFt＋1的拐點對應(yīng)的個體;

11)將個體q 存入KneePt＋1;

12)end;

13)通過(1)式獲得伴隨個體;

14)使用快速非支配排序得到一個種群大小為Pop Size 的新種群Popt＋1,并將其作為下一時刻的初始種群;

15)判斷是否滿足停止條件,若滿足就停止;否則,跳轉(zhuǎn)步驟2。

3 實驗分析

3.1 測試函數(shù)

選取3個DMOP[23]和5 個FDA 系列[23]系列問題作為測試函數(shù),其中FDA1、FDA4和DMOP3屬于第一類問題[26]:PS隨時間變化,PF 不隨時間變化;FDA2、DMOP1 屬于第二類問題:PS 不隨時間變化,PF 隨時間變化;FDA3、FDA5 和DMOP2屬于第三類問題:PS和PF都隨時間變化。函數(shù)的具體定義與特征如表1所示。

表1 測試函數(shù)Table 1 Test functions

續(xù)表1

3.2 評價指標(biāo)

本研究采用反向世代距離(inverted generational distance,IGD)[23]和Schott 的間隔度量(Schott′s spacing metric,SP)[23]2個評價指標(biāo)來評價算法的性能,具體信息如下:

1)反向世代距離(IGD)的值可以反應(yīng)算法的收斂性和種群的多樣性的優(yōu)劣,IGD 的值越小,說明算法的收斂性和種群的多樣性越好。計算IGD 的公式如下:其中,di表示真實PF 中的個體到算法求出的種群個體的最小歐幾里得距離,|P|是算法求出的種群數(shù)量。

2)Schott的間隔度量(SP)反映算法獲得的PS 在目標(biāo)空間中分布的均勻性,SP 的值越小,PS的分布越好。計算SP 的公式如下:

其中:Di表示真實PF中的個體到算法求出的種群個體的最小歐幾里得距離,為所有Di的均值,|P*|是算法求出的種群數(shù)量。

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

1)本研究算法以基于規(guī)則模型的多目標(biāo)分布估計算法(RM-MEDA)[22]為框架進行設(shè)計,RM-MEDA 算法和TCA 算法的相關(guān)參數(shù)按文獻[19]進行設(shè)置。種群大小Pop Size 設(shè)置為100[26],Memory的容量大小Msize 設(shè)置為200,拐點的個數(shù)Knum設(shè)置為10[18],優(yōu)秀個體Esize 設(shè)置為20,鄰域半徑r 設(shè)置為0.05。

參照文獻[19]對時間t 的相關(guān)參數(shù)進行設(shè)置,其中nt表示變化的嚴(yán)重程度,設(shè)為10,τT表示最大迭代次數(shù),設(shè)為200,τt表示變化的頻率,設(shè)為10,即每個測試函數(shù)有20個環(huán)境變化,每個環(huán)境變化迭代10次。

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

4種算法所獲解集性能指標(biāo)見表2。繪制了4個算法部分時刻的解集分布圖,如圖2～9所示。

表2 4種算法所獲得解集的性能指標(biāo)Table 2 Performance indexes of the solution sets obtained by the four algorithms

圖2 4種算法在FDA1上的解集分布圖Fig.2 Solution sets distribution of the four algorithms on FDA1

實驗環(huán)境為:Intel Core i5-8300H CPU ＠2.30 GHz,內(nèi)存8 GB 2 667 MHz,硬盤為512 GB的固態(tài)硬盤,操作系統(tǒng)為Windows 10家庭版;所有實驗都在Matlab2014b上完成。

每個測試函數(shù)將在TKPS、DNSGA-Ⅱ、PPS和Tr-RM-MEDA 算法上運行。每個算法獨立運行20次,記錄每次得到的IGD 和SP的值,計算它們的均值,如表2所示,表中加粗數(shù)據(jù)為較好數(shù)據(jù)。

1)針對第一類問題(FDA1,FDA4 和DMOP3),這3個測試函數(shù)部分時刻的解集分布圖分別如圖2、圖3和圖4所示。

圖3 4種算法在FDA4上的解集分布圖Fig.3 Solution sets distribution of the four algorithms on FDA4

圖4 4種算法在DMOP3上的解集分布圖Fig.4 Solution sets distribution of the four algorithms on DMOP3

從圖2 中可以看出,對于FDA1 測試函數(shù),DNSGA-Ⅱ算法在第1次和第15次環(huán)境變化時,并不能收斂到真實的PF上,表2的數(shù)據(jù)也顯示DNSGA-Ⅱ的收斂性最差,這是因為DNSGA-Ⅱ算法在環(huán)境變化時僅僅增加種群多樣性,無法加速種群收斂。PPS在第10次環(huán)境變化時沒有收斂到真實PF上,而Tr-RM-MEDA 在第15次環(huán)境變化時沒能完全收斂到真實PF 上,但從表2的數(shù)據(jù)中看出這兩個算法的收斂性比DNSGA-Ⅱ算法好,這說明預(yù)測的方法可以加快種群收斂。對于FDA4測試函數(shù),只有DNSGA-Ⅱ算法的收斂性和分布性較差,其它3個算法的收斂性和分布性較好。對于DMOP3測試函數(shù),DNSGA-Ⅱ算法和PPS 算法的收斂性較差,DNSGA-Ⅱ算法的分布性最差,Tr-RM-MEDA算法和TKPS算法的收斂性和分布性都比較好。

2)針對第二類問題(FDA2 和DMOP1),這兩個測試函數(shù)部分時刻的解集分布圖分別如圖5和圖6所示。

圖5 4種算法在FDA2上的解集分布圖Fig.5 Solution sets distribution of the four algorithms on FDA2

圖6 4種算法在DMOP1上的解集分布圖Fig.6 Solution sets distribution of the four algorithms on DMOP1

由圖5～6可以看出,對于FDA2測試函數(shù),4種算法的收斂性都較差,都沒能完全收斂到真實的PF上,但是它們的分布性都很好。對于DMOP1測試函數(shù),4種算法中DNSGA-Ⅱ算法的收斂性和分布性最差,其余3種算法的收斂性和分布性都較好,能夠快速收斂到真實PF上。

總之,TKPS算法在處理第二類問題時具有較好的效果,能夠快速響應(yīng)環(huán)境變化,及時收斂且保持較好的分布性。

3)針對第三類問題(FDA3、FDA5 和DMOP2),這三個測試函數(shù)部分時刻的解集分布圖分別如圖7、圖8和圖9所示。

圖7 4種算法在FDA3上的解集分布圖Fig.7 Solution sets distribution of the four algorithms on FDA3

圖8 4種算法在FDA5上的解集分布圖Fig.8 Solution sets distribution of the four algorithms on FDA5

圖9 4種算法在DMOP2上的解集分布圖Fig.9 Solution sets distribution of the four algorithms on DMOP2

由圖7～9可知,對于FDA3測試函數(shù),DNSGA-Ⅱ的收斂性和分布性最差,PPS也無法完全收斂到真實PF 上,Tr-RM-MEDA 表現(xiàn)較好,能收斂到真實的PF上,而TKPS表現(xiàn)最好,完全收斂到最優(yōu)前沿,種群的分布性也非常好。對于FDA5和DMOP2 測試函數(shù),這4 種算法的效果與FDA3測試函數(shù)效果表現(xiàn)一樣,Tr-RM-MEDA的收斂性和分布性較好,TKPS的收斂性和分布性最好。

綜上所述,TKPS算法的收斂性和分布性是最好的,說明TKPS算法得到的最優(yōu)解更接近Pareto真實解,在目標(biāo)空間中分布更均勻。這是因為TKPS算法通過記憶策略提高遷移學(xué)習(xí)的準(zhǔn)確性,加強了算法的預(yù)測效果,在環(huán)境變化的初始時刻就能獲得具有較好收斂性的解集,通過伴隨個體增加種群多樣性,避免種群陷入局部最優(yōu),提高了種群的分布性。

4 結(jié) 語

針對動態(tài)多目標(biāo)優(yōu)化問題,本研究提出了一種基于拐點和遷移學(xué)習(xí)的預(yù)測策略(TKPS),該策略將拐點和遷移學(xué)習(xí)相結(jié)合,使用記憶策略保存種群中優(yōu)秀個體,通過遷移學(xué)習(xí)算法預(yù)測下一時刻的拐點,并將這些拐點對應(yīng)的個體加入下一時刻的初始種群,引導(dǎo)種群進化方向,加快算法響應(yīng)環(huán)境變化的速度。TKPS與基于規(guī)則模型的多目標(biāo)分布估計算法(RM-MEDA)相結(jié)合,并在FDA 和DMOP 8個測試函數(shù)上與其它3種算法進行比較,實驗結(jié)果表明TKPS算法有較好的收斂性和分布性。同時該算法結(jié)構(gòu)較為簡單,能夠融入其它的多目標(biāo)優(yōu)化算法中求解動態(tài)多目標(biāo)優(yōu)化問題。