基于子空間對齊和反向?qū)W習(xí)的進(jìn)化多任務(wù)優(yōu)化算法

徐 奇,葛方振

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

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

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

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

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

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

1 相關(guān)知識

1.1 問題描述

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

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

1.2 子空間對齊

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

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

式中,ZTS為ZS的轉(zhuǎn)置矩陣。

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

1.3 反向?qū)W習(xí)

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

圖1 搜索空間反向?qū)W習(xí)示意圖

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

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

2 本文算法

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

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

2.2 遷移個(gè)體選擇

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

圖2 遷移個(gè)體選取示意圖

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

①當(dāng)t=1時(shí),從P中隨機(jī)挑選k個(gè)個(gè)體進(jìn)行遷移;

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

2.3 個(gè)體遷移策略

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

圖3 個(gè)體遷移策略流程圖

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

式中,x*i為源任務(wù)中個(gè)體xi轉(zhuǎn)換到目標(biāo)任務(wù)后的個(gè)體;ZTQ為ZQ的轉(zhuǎn)置矩陣。

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

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

式中,λ?(0,1)為隨機(jī)數(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 算法為框架,對其個(gè)體遷移策略進(jìn)行了改進(jìn)。EMT-SOL 算法的偽代碼如表1所示。

表1 EMT-SOL偽代碼

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

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

表2 多目標(biāo)多任務(wù)優(yōu)化問題性質(zhì)

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

在PIHS-PILS測試集上,本文所提出算法的性能明顯優(yōu)于其他算法,這是因?yàn)樵诖藴y試集上每個(gè)問題包含的兩個(gè)任務(wù)在Pareto前沿上有部分交集,但兩個(gè)任務(wù)的Pareto前沿并不相同。EMT-SOL算法在選取合適的遷移個(gè)體后,遷移個(gè)體利用目標(biāo)任務(wù)種群進(jìn)行反向?qū)W習(xí),能夠增強(qiáng)目標(biāo)任務(wù)種群的多樣性,幫助目標(biāo)任務(wù)跳出局部最優(yōu)陷阱。

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

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

4種算法在9個(gè)測試問題的進(jìn)化過程中得到的正遷移的平均比例如圖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)定性。因此,本文所提出算法從源任務(wù)中選擇的遷移個(gè)體能夠?qū)崿F(xiàn)更多的正遷移,目標(biāo)任務(wù)可以從遷移個(gè)體獲取更多的有益信息,幫助目標(biāo)任務(wù)種群加速收斂。

圖4 各算法在進(jìn)化過程中的正遷移的平均比例

4 結(jié)論

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