基于遷移學習的拐點預測策略求解動態多目標優化問題

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

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

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

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

1 動態多目標優化問題

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

其中:x 為決策變量,f 是與時間變量t有關的M 維目標函數,g 和h 的函數分別表示不等式和等式約束集,t表示問題的時間或動態性質,M 表示目標函數的個數。

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

定義2(Pareto最優解集,PS)設x 為決策變量,Ω 為決策空間,F 為目標函數,則PS 定義為

定義3(Pareto最優前沿,PF)設x 為決策變量,F 為目標函數,則PF 定義為

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

2 基于遷移學習的拐點預測策略

2.1 PF拐點

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

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

設有2個目標函數,A～N 是14個非支配點,其中M 和N 是非支配集的邊界點,M、N 構成直線L。將PF 分成三個區域,在每個區域內找出距離直線L 最遠的非支配點作為拐點,因此B、G 和K是該PF 的拐點。當目標函數的個數是3時,用非支配集的邊界點構成一個平面,然后在每個區域內找到距離平面最遠的非支配點作為拐點。

具體步驟如算法1所示。

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

輸入:PF,拐點數目Knum。

輸出:拐點集Knee。

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

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

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

2.2 遷移成分分析

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

2.3 記憶策略

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

算法3記憶策略:Ememory

輸入:內存池Memory,內存池容量Msize,當前時刻的種群Popt,Esize。

輸出:Memory。

1)使用非支配排序從當前種群Popt中找到Esize個優秀個體;

2)判斷Memory是否已滿,如果內存池滿了就轉到步驟2;否則將Esize個優秀個體存入Memory;

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

2.4 TKPS算法

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

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

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

算法4TKPS算法偽代碼

輸入:動態多目標優化問題F(x,t)。

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

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

2)檢測環境是否發生變化,如果環境發生變化,轉步驟5;否則轉步驟3;

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

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

5)環境發生變化:使用TCA 算法得到映射關系矩陣W;

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

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

8)設置t＝t＋1;

9)for k∈PLSkdo;

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

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

12)end;

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

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

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

3 實驗分析

3.1 測試函數

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

表1 測試函數Table 1 Test functions

續表1

3.2 評價指標

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

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

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

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

3.3 參數設置

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

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

3.4 實驗結果與分析

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

表2 4種算法所獲得解集的性能指標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

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

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

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

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

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

3)針對第三類問題(FDA3、FDA5 和DMOP2),這三個測試函數部分時刻的解集分布圖分別如圖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測試函數,DNSGA-Ⅱ的收斂性和分布性最差,PPS也無法完全收斂到真實PF 上,Tr-RM-MEDA 表現較好,能收斂到真實的PF上,而TKPS表現最好,完全收斂到最優前沿,種群的分布性也非常好。對于FDA5和DMOP2 測試函數,這4 種算法的效果與FDA3測試函數效果表現一樣,Tr-RM-MEDA的收斂性和分布性較好,TKPS的收斂性和分布性最好。

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

4 結 語

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