基于子空間對齊和反向學習的進化多任務優(yōu)化算法

徐 奇,葛方振

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

進化算法是一種通過模擬生物基因遺傳和種群進化而產(chǎn)生的群體導向隨機搜索的方法,由于其具有高度并行、自適應等特征,可以有效解決現(xiàn)實生活中存在的許多優(yōu)化問題,如路徑規(guī)劃[1]、車間調度[2]等。隨著優(yōu)化問題的日益復雜,研究人員發(fā)現(xiàn)很多問題并不是獨立存在的[3-4],它們之間可能存在著或多或少的聯(lián)系。受人類同時處理多個不同任務的能力的啟發(fā),研究人員提出了進化多任務優(yōu)化(Evolutionary Multitasking Optimization,EMT)[5-6]的概念。

與傳統(tǒng)的單任務進化算法相比,進化多任務算法在對不同任務進行進化搜索時,能夠利用任務間的相似性,在任務間共享可重復使用的知識,使其在解決優(yōu)化問題時具有更好的性能[7]。然而,隨著任務變得越來越復雜,不同任務有可能來自不同領域,或擁有完全不同的特征,負向任務間交互就會導致信息的負遷移[8],使算法的性能受到負面影響。因此,在EMT 算法中,遷移什么信息、如何遷移信息一直以來都受到了研究者們的廣泛關注。

在進化算法中,種群個體是任務的信息載體,遷移什么信息就是要選擇哪些個體進行遷移。Gupta等[9]提出了多因素進化算法(MFEA),該算法以遺傳算法為框架,將多個任務的決策空間映射到統(tǒng)一空間中,在個體選擇交配階段,將另一任務種群中隨機選取的個體與當前任務的個體作為父代,以一定概率進行交叉變異產(chǎn)生新的子代,實現(xiàn)不同任務知識的遷移。然而,這種方法在解決不相似問題時會產(chǎn)生大量無效的解,造成信息的負遷移。Fend等[10]在EMEA 中利用單個目標對個體進行排序,將排名靠前的個體作為遷移個體。這種方法在任務最優(yōu)解相鄰時可以取得好的效果,但任務之間相似度低時,不能取得較好效果。Lin等[11]提出了一種基于歷史支配關系的策略選擇遷移個體。該方法根據(jù)遷移到目標任務的表現(xiàn)來選擇下一個進化過程中要遷移的個體。實驗結果表明,該方法優(yōu)于前兩種遷移個體選擇方法。

然而,直接對源任務選擇出的優(yōu)秀個體進行遷移不能保證遷移信息適配于目標任務。因此,需要選擇一種合適的信息遷移方式,避免將源任務中無關信息遷移至目標任務中造成負遷移。隨著多任務優(yōu)化的深入研究,研究人員意識到遷移學習[12]方法在探索任務之間存在的關系的重要性。為深入理解任務之間的潛在關系,減少知識負遷移的產(chǎn)生,Bali等[13]提出了一種線性化域自適應(LDA)策略,該策略將簡單任務的搜索空間轉化為具有高度相關性的復雜搜索空間,以實現(xiàn)任務之間的信息交換。Liang等[14]提出了一種基于子空間對齊和自適應差分進化(DE)的MOMFEA-SADE 算法。其通過學習映射矩陣將種群的搜索空間映射到一個子空間,實現(xiàn)任務之間的高效知識轉移。Chen等[15]提出了EMT-LTR 算法,在該方法中,每個任務的決策空間被看作一個流形,任務關系被表示為多個映射函數(shù)組成的聯(lián)合映射矩陣M,通過M將任務間轉移的個體映射到潛在空間,在不同決策空間之間進行信息傳遞。Hu等[16]提出了一種TCADE算法,將TCA 方法用于構建降維子空間,利用任務之間的相關性來尋找遷移個體,同時使用DE算子提高種群多樣性,通過實驗表明,TCADE 能夠有效利用任務之間的潛在關系,減少知識遷移時負遷移的產(chǎn)生。

為了在多任務優(yōu)化過程中遷移更多樣、更有用的特征信息,避免源任務無關信息遷移至目標任務中造成的負遷移,本文提出了一種基于子空間對齊和反向學習的EMT 算法(EMT-SOL)。該算法基于歷史支配關系選取遷移個體,通過利用遷移學習中子空間對齊策略,建立任務之間的映射關系,減小源任務與目標任務之間的個體差異;同時遷移個體利用目標任務種群進行反向學習,提高目標任務種群的多樣性,加快種群收斂。本文選取技術報告[17]中的9個標準測試集作為測試對象,將EMT-SOL 算法與MFEA[9]、EMEA[10]、EMT-ET[11]、MOMFEA-SADE[14]、SPEA2[18]和NSGA-Ⅱ[19]進行對比研究,研究結果表明,EMT-SOL算法遷移個體存活率更高,目標任務可以從遷移個體獲取更多的有益信息,并且算法收斂性能更好。

1 相關知識

1.1 問題描述

EMT 包括單目標多任務優(yōu)化(STO)和多目標多任務優(yōu)化(MTO)[20]。本文研究的是求解MTO 問題的算法性能。MTO 由多個多目標優(yōu)化問題組成,不失一般性,MTO 問題定義為:

其中,Fk表示第k個多目標優(yōu)化問題表示第k個任務的決策空間;nk表示第k個任務的決策空間維數(shù)由mk個實數(shù)連續(xù)目標函數(shù)f1k,…,fmkk組成;Rmk表示第k個任務的目標空間。

1.2 子空間對齊

多維數(shù)據(jù)通常具有一個或多個有效的低維結構模型,這些低維結構代表了數(shù)據(jù)的本質維度和特征。子空間對齊[21]是一種域自適應算法,可以有效挖掘數(shù)據(jù)低維結構。對于兩個樣本數(shù)據(jù),通過特征向量表示源域和目標域的子空間,學習映射函數(shù)來尋找域不變特征空間,該映射函數(shù)將源子空間與目標子空間對齊,實現(xiàn)最小化源數(shù)據(jù)和目標數(shù)據(jù)之間的差異。

對給定的源域數(shù)據(jù)樣本S和目標域數(shù)據(jù)樣本T(其中S,T?Rm×d,m為數(shù)據(jù)集大小,d為數(shù)據(jù)維度),首先,使用主成分分析(PCA)獲得源數(shù)據(jù)和目標數(shù)據(jù)的特征向量,保留其對應的特征值95%信息,通過特征向量生成源域和目標域的子空間ZS?Rd×h和ZT?Rd×h(h為子空間維度);然后通過最小化Bregman散度L(M)=‖ZS·M-ZT‖2F≈0(其中F表示Frobenius范數(shù),M表示最小化ZS和ZT之間的差異的轉換矩陣)實現(xiàn)ZS與ZT坐標對齊,Z′S=ZT·M(Z′P表示對齊后的源域子空間)。由于ZS與ZT均為正交矩陣,且F具有正交不變性,因此Bregman散度為:

式中,ZTS為ZS的轉置矩陣。

通過式(2)實現(xiàn)ZS與ZT的最優(yōu)對齊,從而消除源域與目標域之間的數(shù)據(jù)分布差異:

1.3 反向學習

反向學習策略[22]是由Tizhoosh提出的一種能夠提高算法搜索的智能計算方法,目前已廣泛應用于進化算法、粒子群算法等智能優(yōu)化算法中。點x,x?[a,b]在一維空間中反向學習搜索空間躍變示意圖如圖1所示。

圖1 搜索空間反向學習示意圖

假設x?[a,b],則x的對立點定義為=a+b-x。將定義拓展到n維空間,設在n維空間中存在點p=(x1,x2,…,xn),其中xi?[ai,bi],i=1,2,…,n,則其對立點=(1,2,…,n),其中i=ai+bix i。

汪慎文等[23]在反向學習的基礎上提出了精英反向學習策略,該策略首先找到當前種群中的若干精英個體,計算出當前種群個體的精英反向解,從而生成一個精英反向種群;然后將產(chǎn)生的精英反向種群與當前種群一起競爭,選出優(yōu)秀個體作為下一代種群。實驗結果表明[23],精英反向學習策略可以促進群體進化過程的躍變,從而使算法具有較快的收斂速度。

2 本文算法

2.1 統(tǒng)一搜索空間

為了構建任務之間的信息交流環(huán)境,在M TO 問題的研究中通常將所有任務的搜索空間歸一化到統(tǒng)一的搜索空間Y?[0,1]DY中。假設在一個MTO問題中有K個優(yōu)化任務{T1,T2,…,TK},任務Ti對應的決策空間和維數(shù)分別為Xi和Di。為了在信息遷移時能夠給目標任務提供完整的信息,將所有任務中維度最大值作為統(tǒng)一搜索空間維數(shù),即DY=Max{D1,D2,…,DK},假設任務Ti的第j個決策變量Xji?歸一化公式為

2.2 遷移個體選擇

在多任務進化算法中,基于歷史支配關系選取策略是一種具有代表性的遷移個體選擇方法。當被遷移的個體在目標任務中是非支配的,那么該個體實現(xiàn)了正遷移;同時,在正遷移個體的源任務的搜索空間中,與該個體最接近的解(基于歐式距離)最有可能實現(xiàn)正遷移。從t-1(t>1)代種群中選取遷移個體的示意圖如圖2所示。

圖2 遷移個體選取示意圖

給定任務T1的種群P={p1,p2,…,pn}和任務T2的種群Q={q1,q2,…,qn}(其中P,Q?Rm×d,m表示種群中的個體數(shù),d表示決策變量維數(shù))。假設T1為源任務,T2為目標任務,在源任務種群P進化至t代時,對將要遷移的個體X={x1,x2,…,xk}的選擇方式具體如下:

①當t=1時,從P中隨機挑選k個個體進行遷移;

②當t>1時,根據(jù)第t-1代正遷移個體選擇新的遷移個體;如果t-1代源任務的遷移個體在目標任務上均未實現(xiàn)正遷移,則從種群P的第t代選取k個非支配解作為遷移個體。

2.3 個體遷移策略

對于選擇后的遷移個體,需要合適的遷移策略來減少將源任務中無關信息遷移至目標任務中去。為此,基于1.2中子空間對齊方法對給定的源任務種群P和目標任務種群Q使用PCA方法獲取對應的子空間ZP和ZQ,利用最小化Bregman散度獲取子空間之間的映射關系M*,通過M*實現(xiàn)P與Q之間的數(shù)據(jù)分布差異最小化,達到有效地利用任務之間的潛在關系;同時借鑒精英反向學習思想,將遷移個體集X*作為一個種群,利用目標任務種群計算出反向遷移解,從而生成一個反向遷移種群*與目標種群個體競爭。第t代個體遷移策略流程圖如圖3所示。

圖3 個體遷移策略流程圖

(1)子空間對齊。對于從源任務種群P中選取的遷移個體集X={x1,x2,…,xk}中的個體xi,i=1,…,k,首先通過xi·ZP映射到子空間ZP中;根據(jù)子空間映射關系M*將xi轉換到子空間ZQ;最后,通過xi·Z*P·ZTQ將xi轉換到Q空間作為選擇的遷移個體,即

式中,x*i為源任務中個體xi轉換到目標任務后的個體;ZTQ為ZQ的轉置矩陣。

(2)反向學習。為了提高目標任務種群的勘探能力,EM T-SOL算法借鑒精英反向學習思想,對轉換后的遷移個體集X*執(zhí)行反向學習策略,使*充分吸收目標種群中個體的有益搜索信息,加快目標任務種群的收斂速度;同時將*與目標種群Q合并,選出優(yōu)秀個體進入下一代群體中以增強種群的多樣性,幫助算法跳出局部最優(yōu)陷阱。

對于遷移個體集X*={x1*,x2*,…,xk*,}和目標任務種群Q={q1,q2,…,qn};設第t代qi,j和xi*,j(t)分別為qi(t)和x*i(t)在第j維上的值,遷移個體反向解*i,j(t)通過式(5)進行計算:

式中,λ?(0,1)為隨機數(shù);aj=min(q1,j(t),…,qm,j(t));bj=max(q1,j(k),…,qm,j(k));若*i,j(t)>bj(t),則取

2.4 EMT-SOL算法

EMT-SOL以EMT-ET 算法為框架,對其個體遷移策略進行了改進。EMT-SOL 算法的偽代碼如表1所示。

表1 EMT-SOL偽代碼

3 實驗與結果分析

為驗證本文所提出算法的性能,選取技術報告[17]中的9個標準測試集作為測試對象。在標準測試集上,每一個多任務優(yōu)化問題都包含兩個多目標優(yōu)化問題,每個問題的性質如表2所示。

表2 多目標多任務優(yōu)化問題性質

3.1 實驗設置

對于每個測試問題,本文所提出算法EMT-SOL 都將與算法EMT-ET、MOMFEA-SADE、EMEA、MFEA、SPEA2和NSGA-Ⅱ進行對比。

(1)種群大小:在測試問題中,兩目標優(yōu)化問題種群大小設置為100,三目標優(yōu)化問題設置為120。

(2)最大迭代次數(shù):Gmax=500。

(3)獨立運行次數(shù):nr=30。

(5)MFEA 算法中的隨機交叉概率(rmp)根據(jù)文獻[9]設置為Pr=0.3。

3.2 算法評價指標

在本文中,采用IGD(In verted Generational Distance)[24]評估算法的收斂性和種群的多樣性,算法性能越好,IGD 值越小。公式如下:

式中,|P|為真實PF中的種群個體個數(shù);di為真實Pareto前沿上的每個個體到算法選出的種群個體的最短距離。

3.3 實驗結果與分析

各個算法在測試集上分別運行30次的IGD 平均值如表3所示。根據(jù)表3中數(shù)據(jù)可以看出,本文所提出算法EMT-SOL 與其他算法相比,在大多數(shù)的測試問題中都顯示出較好的性能。結合測試函數(shù)性質,我們對EMT-SOL算法能夠表現(xiàn)出良好的性能進行了以下分析:從表中CIHS-CILS的測試結果可以看出,EMT-SOL算法在大多數(shù)問題上都優(yōu)于其他比較算法。這是因為在CIHS-CILS測試集上,每個問題都是由兩個具有相同Pareto前沿的任務組成,當源任務種群收斂到Pareto前沿上時,目標任務就能夠得到解決,但源任務種群的非支配個體并不能直接幫助目標種群。EMT-SOL 算法根據(jù)歷史支配關系能夠選取更合適的遷移個體,并通過構建任務之間的映射關系,最小化任務之間的差異,從而對源任務選取的遷移個體進行轉換,使源任務個體能夠更好地幫助目標任務種群加快收斂速度。

表3 7種算法在測試函數(shù)上的IGD 平均值

在PIHS-PILS測試集上,本文所提出算法的性能明顯優(yōu)于其他算法,這是因為在此測試集上每個問題包含的兩個任務在Pareto前沿上有部分交集,但兩個任務的Pareto前沿并不相同。EMT-SOL算法在選取合適的遷移個體后,遷移個體利用目標任務種群進行反向學習,能夠增強目標任務種群的多樣性,幫助目標任務跳出局部最優(yōu)陷阱。

在NIHS-NILS測試集上,本文所提出算法在部分問題中仍然優(yōu)于其他比較算法。對于此測試集中的每個問題,其兩個優(yōu)化任務在Pareto集合中并沒有任何交集,因此,直接遷移源任務個體可能無法有效的提高目標任務的求解效果。EMT-SOL算法基于子空間對齊的方法,減小遷移個體與目標種群個體的數(shù)據(jù)差異,避免源任務中無關信息遷入目標任務中;同時通過反向學習使遷移個體吸收了目標任務種群中的個體有益搜索信息,從而提高目標種群的多樣性和算法搜索能力,加快算法的收斂速度。

同時,為驗證遷移個體在目標任務種群中的存活率,將本文所提出算法與EMT-ET、MOMFEASADE、MFEA 在進化過程中分別獲得的正遷移比例(正遷移的比例為正遷移解決方案的數(shù)量除以遷移解決方案的總數(shù))進行比較,以比較它們選擇有價值的知識遷移個體的能力。在本實驗中,每50代計算一次正遷移的比例,獨立運行30次。

4種算法在9個測試問題的進化過程中得到的正遷移的平均比例如圖4所示。從圖4中可以看出,本文所提出算法在正遷移比例方面比其他4種算法更適合大多數(shù)測試問題。特別是針對CIHS、CIMS、CILS、PILS-Task1等問題,EMT-SOL 算法平均正遷移率接近0.46,而EMT-ET、MOMFEA-SADE 和MFEA 的平均正遷移率分別為0.38、0.31和0.24。在其他測試問題上,雖然EMT-SOL算法獲得的正遷移比例存在一定的波動,但仍然比EMT-ET、MOMFEA-SADE 與MFEA 具有更好的性能和更好的穩(wěn)定性。因此,本文所提出算法從源任務中選擇的遷移個體能夠實現(xiàn)更多的正遷移,目標任務可以從遷移個體獲取更多的有益信息,幫助目標任務種群加速收斂。

圖4 各算法在進化過程中的正遷移的平均比例

4 結論

本文基于子空間對齊和反向學習提出了一種新的EMT 算法(EMT-SOL)。為了在多任務優(yōu)化過程中遷移更有用的特征信息,通過基于歷史支配關系選擇出更為有效的遷移個體,然后利用子空間對齊的方法,構建源任務種群和目標任務種群的映射關系,通過映射關系減小遷移個體與目標種群個體的數(shù)據(jù)差異,提高遷移個體在目標任務中的存活率,避免產(chǎn)生信息的負遷移;同時,為了提高目標任務種群的多樣性,利用目標任務中的個體對遷移個體進行反向學習,使遷移個體吸收目標任務種群中的個體有益搜索信息,以探索目標種群的搜索空間。實驗結果驗證了所提算法的有效性,與其他多目標多任務算法相比較,本文所提出算法在測試集上運行的效果更好,并且遷移個體在目標任務種群中實現(xiàn)正遷移的比例更高。