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

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

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

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

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

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

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

定義1(Pareto支配)設(shè)p 和q 是種群中任意兩個(gè)個(gè)體,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í)的拐點(diǎn)預(yù)測策略

2.1 PF拐點(diǎn)

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

圖1 尋找拐點(diǎn)的示意圖Fig.1 Sketch map of finding knee points

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

具體步驟如算法1所示。

算法1尋找拐點(diǎn)的偽代碼:Seek Knee

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

輸出:拐點(diǎn)集Knee。

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

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

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

2.2 遷移成分分析

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

2.3 記憶策略

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

算法3記憶策略:Ememory

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

輸出:Memory。

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

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

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

2.4 TKPS算法

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

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

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

算法4TKPS算法偽代碼

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

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

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

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

3)使用RM-MEDA 算法求出當(dāng)前時(shí)刻的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 將拐點(diǎn)集Kneet映射到高維希爾伯特空間中,得到PLSk;

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

9)for k∈PLSkdo;

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

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

12)end;

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

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

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

3 實(shí)驗(yàn)分析

3.1 測試函數(shù)

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

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

續(xù)表1

3.2 評價(jià)指標(biāo)

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

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

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

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

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

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

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

3.4 實(shí)驗(yàn)結(jié)果與分析

4種算法所獲解集性能指標(biāo)見表2。繪制了4個(gè)算法部分時(shí)刻的解集分布圖,如圖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

實(shí)驗(yàn)環(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家庭版;所有實(shí)驗(yàn)都在Matlab2014b上完成。

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

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

2)針對第二類問題(FDA2 和DMOP1),這兩個(gè)測試函數(shù)部分時(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種算法的收斂性都較差,都沒能完全收斂到真實(shí)的PF上,但是它們的分布性都很好。對于DMOP1測試函數(shù),4種算法中DNSGA-Ⅱ算法的收斂性和分布性最差,其余3種算法的收斂性和分布性都較好,能夠快速收斂到真實(shí)PF上。

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

3)針對第三類問題(FDA3、FDA5 和DMOP2),這三個(gè)測試函數(shù)部分時(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也無法完全收斂到真實(shí)PF 上,Tr-RM-MEDA 表現(xiàn)較好,能收斂到真實(shí)的PF上,而TKPS表現(xiàn)最好,完全收斂到最優(yōu)前沿,種群的分布性也非常好。對于FDA5和DMOP2 測試函數(shù),這4 種算法的效果與FDA3測試函數(shù)效果表現(xiàn)一樣,Tr-RM-MEDA的收斂性和分布性較好,TKPS的收斂性和分布性最好。

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

4 結(jié) 語

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