邱鴻輝，劉海林，陳 磊

（廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院，廣州 510520）

0 概述

進(jìn)化算法是一類基于種群個(gè)體隨機(jī)搜索的算法［1-2］，由于其強(qiáng)大的搜索能力及簡(jiǎn)單易用的特性，在路徑規(guī)劃［3］、軟件工程［4］等現(xiàn)實(shí)問(wèn)題中被廣泛的應(yīng)用，并取得了良好的效果。

近年來(lái)，研究人員受到人類大腦能同時(shí)處理多個(gè)任務(wù)的啟發(fā)，提出多任務(wù)進(jìn)化（Evolutionary Multi-Tasking，EMT）［5-6］的研究方向，傳統(tǒng)的進(jìn)化搜索方法一次只能解決一個(gè)任務(wù)，然而EMT 方法一次運(yùn)行能夠同時(shí)解決多個(gè)任務(wù)。研究表明，與傳統(tǒng)的單任務(wù)進(jìn)化算法相比，由于EMT 方法利用了任務(wù)間潛在的協(xié)同作用，使其在解決優(yōu)化問(wèn)題時(shí)具有更好的性能［7］。EMT 包括單目標(biāo)多任務(wù)優(yōu)化（Single-Objective Multi-Tasking Optimization，STO）［8］和多目標(biāo)多任務(wù)優(yōu)化（Multi-Objective Multi-Tasking Optimization，MTO）。本文研究的是求解MTO 問(wèn)題［9］的算法性能。

當(dāng)前，求解MTO 問(wèn)題的算法大致可以分為基于單個(gè)種群進(jìn)化的算法和基于多個(gè)種群進(jìn)化的算法。前者的典型代表是文獻(xiàn)［9］提出的解決MTO 問(wèn)題的MO-MFEA 算法，該算法通過(guò)采用單個(gè)種群來(lái)同時(shí)優(yōu)化多個(gè)相關(guān)的任務(wù)，并以預(yù)先設(shè)定的概率決定是否要實(shí)施任務(wù)間的知識(shí)遷移。文獻(xiàn)［10］在MO-MFEA 算法的基礎(chǔ)上引入粒子群優(yōu)化［11-12］和差分進(jìn)化策略［13-14］，提出解決MTO 問(wèn)題的新算法。實(shí)驗(yàn)結(jié)果表明，上述多任務(wù)優(yōu)化算法比其對(duì)應(yīng)的單任務(wù)優(yōu)化算法的性能更好。后者的典型代表是文獻(xiàn)［15］提出的全新多種群多任務(wù)框架，使用多個(gè)子種群同時(shí)解決多個(gè)任務(wù)，每個(gè)子種群對(duì)應(yīng)于解決單個(gè)任務(wù)。文獻(xiàn)［16］在多個(gè)種群的條件下，采用一種高效的知識(shí)遷移策略來(lái)促進(jìn)多個(gè)任務(wù)的同時(shí)優(yōu)化。大量實(shí)驗(yàn)表明，多種群MTO 框架由于能在多個(gè)種群之間互相獨(dú)立，可以靈活解決多個(gè)任務(wù)的優(yōu)化問(wèn)題，因此比單種群MTO 框架更具有優(yōu)勢(shì)。盡管當(dāng)前解決MTO 問(wèn)題的算法較多，但這些算法涉及到衡量任務(wù)間相似度的研究很少，有些算法雖然包含衡量任務(wù)間相似度的策略，但步驟較繁瑣，計(jì)算量較大，難以推廣應(yīng)用。

本文提出一種多目標(biāo)多任務(wù)優(yōu)化算法，基于自適應(yīng)協(xié)方差矩陣的進(jìn)化策略，從某個(gè)正態(tài)分布中采樣產(chǎn)生種群個(gè)體，使種群分布特征具有規(guī)律性，并采用任務(wù)間種群的分布特征差異和分布距離衡量任務(wù)間的相似程度。設(shè)計(jì)一種從相似任務(wù)中尋找有價(jià)值的解，進(jìn)而實(shí)施知識(shí)遷移的方法，并基于遷移學(xué)習(xí)的思想，對(duì)相似任務(wù)中的解實(shí)施K 最近鄰（K-Nearest Neighbor，KNN）分類，以篩選出對(duì)目標(biāo)任務(wù)更有價(jià)值的解。

1 相關(guān)工作

1.1 多目標(biāo)多任務(wù)優(yōu)化算法

多目標(biāo)多任務(wù)優(yōu)化是進(jìn)化計(jì)算領(lǐng)域的一個(gè)重要研究方向。但目前大部分的多目標(biāo)多任務(wù)優(yōu)化算法主要解決2 個(gè)待優(yōu)化任務(wù)的問(wèn)題，較少涉及到研究超多任務(wù)優(yōu)化問(wèn)題。文獻(xiàn)［17］闡明了使用進(jìn)化算法解決現(xiàn)實(shí)生活中超多任務(wù)優(yōu)化問(wèn)題的可行性，當(dāng)待優(yōu)化的任務(wù)數(shù)量超過(guò)2 個(gè)時(shí)，為避免過(guò)高的時(shí)間開(kāi)銷，對(duì)于某個(gè)給定的目標(biāo)任務(wù)，從其余任務(wù)中選擇一個(gè)與目標(biāo)任務(wù)最相似的輔助任務(wù)，進(jìn)而實(shí)施任務(wù)間的知識(shí)遷移，因此衡量任務(wù)間的相似性是解決超多任務(wù)優(yōu)化問(wèn)題的核心。文獻(xiàn)［18］從最優(yōu)解之間的距離、適應(yīng)度等級(jí)的相關(guān)性和適應(yīng)值函數(shù)范圍分析3 個(gè)方面衡量任務(wù)間的相似性。文獻(xiàn)［19］提出一個(gè)協(xié)同性度量指標(biāo)量化不同任務(wù)間的聯(lián)系，這一度量指標(biāo)可以從側(cè)面證明任務(wù)間的知識(shí)遷移能夠同時(shí)促進(jìn)多個(gè)待優(yōu)化任務(wù)的收斂性能。

基于任務(wù)間的相似性，為求解超多任務(wù)優(yōu)化問(wèn)題，文獻(xiàn)［20］采用輪盤賭的方法為目標(biāo)任務(wù)選擇一個(gè)合適的輔助任務(wù)，某個(gè)與目標(biāo)任務(wù)最相似的任務(wù)有較大的概率被選為輔助任務(wù)，從而通過(guò)遷移有用的知識(shí)來(lái)減少負(fù)遷移的產(chǎn)生。文獻(xiàn)［21］通過(guò)同時(shí)考慮任務(wù)間的相似性和進(jìn)化過(guò)程中知識(shí)遷移的累積獎(jiǎng)勵(lì)值，提出一種自適應(yīng)輔助任務(wù)選擇機(jī)制，采用KL散度衡量任務(wù)間的相似性，并基于強(qiáng)化學(xué)習(xí)的思想，構(gòu)建關(guān)于種群進(jìn)化過(guò)程中任務(wù)間知識(shí)遷移的累積獎(jiǎng)勵(lì)系統(tǒng)，選擇出合適的輔助任務(wù)，并通過(guò)交叉的方式實(shí)現(xiàn)知識(shí)遷移。文獻(xiàn)［22］基于任務(wù)間種群概率分布的差異自適應(yīng)地學(xué)習(xí)任務(wù)間的聯(lián)系，并根據(jù)進(jìn)化過(guò)程中求得的不同任務(wù)種群間的聯(lián)系，自適應(yīng)調(diào)整知識(shí)遷移的強(qiáng)度。文獻(xiàn)［21］和文獻(xiàn)［22］中的算法均采用高斯分布來(lái)近似模擬種群的真實(shí)概率分布，但實(shí)際上，種群的真實(shí)分布通常是隨機(jī)且不可預(yù)測(cè)的，且算法花費(fèi)大量的計(jì)算資源在衡量任務(wù)間的相似度上，導(dǎo)致最終運(yùn)行的效率較低。

1.2 自適應(yīng)協(xié)方差矩陣進(jìn)化算法CMA-ES

CMA-ES 算法［23-24］是目前性能較好、應(yīng)用較多的進(jìn)化策略之一，在中等規(guī)模的復(fù)雜優(yōu)化問(wèn)題處理上具有良好的效果。CMA-ES 算法的核心思想是：每一代種群的所有個(gè)體均從某個(gè)正態(tài)分布群體中采樣產(chǎn)生，并通過(guò)調(diào)整協(xié)方差矩陣Ct和步長(zhǎng)參數(shù)σt，使產(chǎn)生的種群個(gè)體盡可能往產(chǎn)生好解的搜索方向搜索，從而增強(qiáng)算法的收斂速率。CMA-ES 算法的具體步驟如下：

1）采樣產(chǎn)生新的種群個(gè)體。在CMA-ES 算法中，進(jìn)化過(guò)程中的每一代種群均從產(chǎn)生進(jìn)化的種群個(gè)體，個(gè)體xi更新的表達(dá)式如式（1）所示：

其中：yi通過(guò)協(xié)方差矩陣Ct的特征分解Ct=BD2BT得到，即：

其中：B為正交矩陣；D為對(duì)角矩陣且其對(duì)角元素值為矩陣Ct特征值的平方根；I為單位矩陣。

2）進(jìn)化路徑的更新。在CMA-ES 算法中，每一代種群的進(jìn)化路徑均通過(guò)如下的方式構(gòu)造［24］：

其中：pt表示在第t代的進(jìn)化路徑；c表示進(jìn)化路徑更新的累積學(xué)習(xí)率；μw表示均值的有效選擇質(zhì)量。

式（3）描述了種群分布均值的移動(dòng)方向，將每一代種群進(jìn)化過(guò)程中的移動(dòng)方向做加權(quán)平均，使得種群中每個(gè)個(gè)體相反的進(jìn)化方向分量相互抵消，相同的進(jìn)化方向分量相互疊加，從而保證種群沿著最優(yōu)的方向搜索。

3）協(xié)方差矩陣的更新。通過(guò)增大沿歷史成功搜索最優(yōu)方向的方差，即增大沿這些最優(yōu)搜索方向的采樣概率，避免算法把搜索資源浪費(fèi)在無(wú)效的區(qū)域上。協(xié)方差矩陣的更新原理如式（4）所示［24］：

其中：yi表示當(dāng)前種群中較優(yōu)個(gè)體的搜索方向；c1和cμ表示協(xié)方差矩陣更新的學(xué)習(xí)率。

本文采用下述方法衡量任務(wù)間的相似度：基于CMA-ES 算法的思想，每一代種群在進(jìn)化過(guò)程中，均從正態(tài)分布群體采樣產(chǎn)生種群個(gè)體，即種群的均值和協(xié)方差矩陣可以反映當(dāng)前種群的特征，因此通過(guò)種群的均值和協(xié)方差矩陣來(lái)表示任務(wù)之間的聯(lián)系，從而為目標(biāo)任務(wù)選擇出一個(gè)最合適的輔助任務(wù)來(lái)實(shí)施知識(shí)遷移，加速目標(biāo)任務(wù)的收斂進(jìn)程。

2 本文算法

2.1 種群編碼和解碼

為便于在任務(wù)間高效地實(shí)施知識(shí)遷移，目前許多多任務(wù)優(yōu)化算法采用統(tǒng)一空間表示法對(duì)不同任務(wù)的種群實(shí)施編碼［9］。具體為，首先把所有任務(wù)的解集均編碼到一個(gè)統(tǒng)一的搜索空間中。例如，給定K個(gè)待優(yōu)化的任務(wù){(diào)T1,T2,…,TK}，將第i個(gè)任務(wù)決策空間的維度記為Di(i=1,2,…,K)，定義所有任務(wù)統(tǒng)一的搜索空間維度為Dmax，且Dmax=maxi{Di}，在種群進(jìn)化的初始階段，給所有任務(wù)種群中的每個(gè)個(gè)體都分配一個(gè)Dmax維的隨機(jī)向量，該向量每個(gè)維度的變量范圍為［0，1］，通常把這個(gè)向量稱為包含該個(gè)體所有遺傳物質(zhì)的染色體，該編碼策略把所有任務(wù)中的種群都統(tǒng)一到共同的搜索空間中，以便于在不同的任務(wù)之間實(shí)施知識(shí)遷移。本文提出的衡量任務(wù)間相似度策略以及任務(wù)間知識(shí)遷移的方式均基于該編碼策略，且均在統(tǒng)一的搜索空間中進(jìn)行。

當(dāng)要對(duì)某個(gè)特定的任務(wù)Ti中的個(gè)體實(shí)施評(píng)估時(shí)，必須把該個(gè)體的染色體解碼為任務(wù)Ti對(duì)應(yīng)問(wèn)題的解。同時(shí)，對(duì)于任務(wù)Ti中的個(gè)體，只使用其對(duì)應(yīng)染色體的前Di維變量。本文僅考慮連續(xù)優(yōu)化的情形，例如對(duì)于任務(wù)Ti中某個(gè)解的第i維變量yi，其取值范圍是［Li，Ui］，若其染色體前Di維中對(duì)應(yīng)的變量值為xi，則二者通過(guò)如式（5）所示的方式實(shí)現(xiàn)轉(zhuǎn)換：

該解碼策略把實(shí)際問(wèn)題中的解與統(tǒng)一搜索空間中的染色體一一對(duì)應(yīng)，通過(guò)在統(tǒng)一搜索空間中進(jìn)行染色體間的雜交變異，從而在實(shí)際問(wèn)題中增加每個(gè)任務(wù)最優(yōu)解的多樣性。

2.2 任務(wù)間相似度衡量

若有K個(gè)待優(yōu)化的任務(wù){(diào)T1,T2,…,TK}，對(duì)于某個(gè)目標(biāo)任務(wù)Tt，使用一個(gè)任務(wù)間的自適應(yīng)相似度衡量策略來(lái)決定是否需要為目標(biāo)任務(wù)Tt分配一個(gè)輔助任務(wù)，以實(shí)施知識(shí)遷移，促進(jìn)目標(biāo)任務(wù)的優(yōu)化進(jìn)程。該策略包含2 個(gè)部分：任務(wù)間種群分布特征差異的衡量及任務(wù)間種群分布距離的衡量。根據(jù)CMA-ES 算法的原理，每個(gè)任務(wù)的種群個(gè)體經(jīng)過(guò)正態(tài)分布采樣后，用種群的協(xié)方差矩陣表示種群的分布特征，用任務(wù)間種群均值之間的距離表示任務(wù)間的分布距離，從而衡量出任務(wù)間的相似性。

2.2.1 任務(wù)間種群分布特征差異

給定任務(wù)T1的種群P={P1,P2,…,Pn}以及任務(wù)T2的種群Q={Q1,Q2,…,Qn}，他們分別從正態(tài)分布中采樣而來(lái)。每個(gè)任務(wù)中種群的協(xié)方差矩陣可以近似看作種群沿著最優(yōu)解搜索方向的集合，因此衡量任務(wù)間種群的協(xié)方差矩陣之間的差異可以度量任務(wù)間種群分布特征的差異（種群中的所有個(gè)體均沿著最優(yōu)解方向搜索）。基于主成分分析（Principal Component Analysis，PCA）的思想衡量任務(wù)T1和任務(wù)T2中種群協(xié)方差矩陣之間的差異。

首先，對(duì)任務(wù)T1和任務(wù)T2中種群的協(xié)方差矩陣分別實(shí)施特征分解：

接著，分別從E1和E2中選出k個(gè)特征向量，這些特征向量對(duì)應(yīng)C1和C2中最大的k個(gè)特征值，根據(jù)PCA 中的可解釋方差比例指標(biāo)，若保留的這k個(gè)主成分的累積方差貢獻(xiàn)率大于等于95%，即選出的主成分至少能分別保留C1和C2中95%的信息，使用從E1和E2中選出的k個(gè)特征向量來(lái)構(gòu)建種群P和Q的子空間Ps和Pt，即：

最后，由于Ps和Pt中的列向量均為單位向量，故對(duì)Ps和Pt中的列向量之間做內(nèi)積，表示Ps和Pt中的列向量之間角度的余弦值。若Ps中的一個(gè)列向量為e1，從Pt中找到一個(gè)列向量f1，使e1和f1之間的余弦值最大（夾角最?。⒂沞1和f1之間的夾角為θ1。照此步驟執(zhí)行k次，對(duì)應(yīng)的夾角分別記為θ1，θ2，…，θk，采用這些夾角正弦值的平均值來(lái)表示任務(wù)間種群協(xié)方差矩陣之間的差異，即：

其中：Covd(T1,T2)的值越小，表明任務(wù)T1和任務(wù)T2中種群的分布特征越相似，即任務(wù)T1和任務(wù)T2中種群搜索最優(yōu)解的方向越相似。

2.2.2 任務(wù)間種群分布距離

若任務(wù)T1的種群P和任務(wù)T2的種群Q分別從正態(tài)分布中采樣產(chǎn)生，則任務(wù)T1和任務(wù)T2種群的均值可以分別看作任務(wù)T1和任務(wù)T2中種群的中心，因此任務(wù)間種群均值間的距離可以近似看作任務(wù)間種群的分布距離。

任務(wù)T1和任務(wù)T2之間的種群分布距離的表達(dá)式如式（11）所示：

其中：任務(wù)T1和任務(wù)T2的種群均值間的距離（種群中心之間的距離）表示任務(wù)T1和任務(wù)T2的種群分布間的交叉程度。若任務(wù)T1和任務(wù)T2之間的種群分布距離較近，則在任務(wù)T1和任務(wù)T2之間實(shí)施知識(shí)遷移能夠促進(jìn)每個(gè)任務(wù)的優(yōu)化進(jìn)程。

2.2.3 任務(wù)間種群相似度衡量

基于CMA-ES 算法的思想，每個(gè)任務(wù)中的種群均通過(guò)正態(tài)分布采樣產(chǎn)生，在種群進(jìn)化的前期階段，每個(gè)任務(wù)中的種群均朝著各自的最優(yōu)解方向搜索，種群的協(xié)方差矩陣可以反映種群沿著最優(yōu)解方向搜索時(shí)的分布特征，因此在種群進(jìn)化的前期，任務(wù)間種群的相似度主要由任務(wù)間種群分布特征的差異決定。在種群進(jìn)化的后期階段，大部分任務(wù)中的種群已經(jīng)收斂到了最優(yōu)解，此時(shí)任務(wù)間種群的相似度主要由任務(wù)間種群分布的距離決定。采用式（12）來(lái)表達(dá)種群進(jìn)化全過(guò)程中，任務(wù)T1和任務(wù)T2之間種群的相似度：

其中：λ表示任務(wù)間種群的分布特征差異和分布距離之間的權(quán)重值，令g表示當(dāng)前的進(jìn)化代數(shù)，m表示進(jìn)化的最大代數(shù)。式（12）表示在種群進(jìn)化的前期階段，任務(wù)間種群的相似度主要由任務(wù)間種群分布特征的差異決定，在種群進(jìn)化的后期階段，任務(wù)間種群的相似度主要由任務(wù)間種群分布的距離決定。若Sim(T1,T2)的值較小，則表明任務(wù)T1和任務(wù)T2的Pareto 最優(yōu)解的方向和位置較接近，在任務(wù)T1和任務(wù)T2之間實(shí)施知識(shí)遷移能夠有效促進(jìn)每個(gè)待優(yōu)化任務(wù)的收斂進(jìn)程。

2.3 任務(wù)間知識(shí)遷移策略

圖1 所示為本文算法任務(wù)間知識(shí)遷移策略的具體流程圖?？梢钥吹?，在種群進(jìn)化的第g代，對(duì)于某個(gè)待優(yōu)化的目標(biāo)任務(wù)Tt，根據(jù)本文策略可以找到與目標(biāo)任務(wù)Tt最相似的任務(wù)是Ta。依據(jù)遷移學(xué)習(xí)的思想，把目標(biāo)任務(wù)Tt種群中的解分成兩類，一類是非支配解，標(biāo)記為“1”，另一類是支配解，標(biāo)記為0，把這些解作為給任務(wù)Ta中解分類的源標(biāo)簽，本文采用K最近鄰（KNN）分類，具體的分類方式為，對(duì)于任務(wù)Ta中的某個(gè)解P，找出目標(biāo)任務(wù)Tt中距離解P最近的2 個(gè)解Q1和Q2，并記錄他們的標(biāo)簽為L(zhǎng)a、Lb，若La+Lb=2，則把解P標(biāo)記為“1”，否則記為“0”。接著，對(duì)于任務(wù)Ta中標(biāo)記為“1”的解（近似目標(biāo)任務(wù)中的非支配解），將他們遷移到目標(biāo)任務(wù)Tt的種群中，從而促進(jìn)目標(biāo)任務(wù)的優(yōu)化進(jìn)程。若根據(jù)式（12）計(jì)算得到目標(biāo)任務(wù)Tt與任務(wù)Ta的相似度在逐代降低，表明此時(shí)所有任務(wù)均與目標(biāo)任務(wù)Tt不相似，為避免無(wú)效的遷移，應(yīng)停止知識(shí)遷移，讓目標(biāo)任務(wù)Tt中的種群個(gè)體之間獨(dú)立進(jìn)化產(chǎn)生后代。

圖1 任務(wù)間知識(shí)遷移策略流程Fig.1 Procedure of knowledge transfer strategy between tasks

2.4 算法整體框架

綜合以上過(guò)程，本節(jié)給出解決多目標(biāo)多任務(wù)優(yōu)化問(wèn)題的EMTSD 算法。若給定一個(gè)有K個(gè)任務(wù)的多目標(biāo)多任務(wù)優(yōu)化問(wèn)題，EMTSD 算法通過(guò)進(jìn)化K個(gè)獨(dú)立的種群來(lái)同時(shí)優(yōu)化這些任務(wù)。首先，EMTSD 算法初始化K個(gè)種群P1，P2，…，PK，并按照2.1 節(jié)中的策略將這K個(gè)種群中的所有個(gè)體均編碼到一個(gè)統(tǒng)一的空間中，便于各個(gè)任務(wù)之間的知識(shí)實(shí)施互相遷移。然后，對(duì)于某個(gè)特定的目標(biāo)任務(wù)Tt，按照2.2 節(jié)的過(guò)程，根據(jù)式（12）從其余K-1 個(gè)任務(wù)中找出當(dāng)前與目標(biāo)任務(wù)Tt最相似的任務(wù)Ta，并按照2.3 節(jié)的策略在目標(biāo)任務(wù)Tt與任務(wù)Ta之間實(shí)施知識(shí)遷移，從而促進(jìn)目標(biāo)任務(wù)Tt的收斂進(jìn)程。若在進(jìn)化過(guò)程中發(fā)現(xiàn)目標(biāo)任務(wù)Tt與其余任務(wù)的相似度降低，則停止知識(shí)遷移，讓目標(biāo)任務(wù)Tt種群內(nèi)部中的個(gè)體獨(dú)立產(chǎn)生后代。EMTSD 算法的具體框架如圖2 所示。

圖2 EMTSD 算法的整體框架Fig.2 Overall framework of the EMTSD algorithm

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

為驗(yàn)證本文算法EMTSD的性能，本文使用文獻(xiàn)［25］提出的多目標(biāo)多任務(wù)測(cè)試集，包括CIHS、CIMS、PIHS、PIMS 等，每個(gè)測(cè)試集由2個(gè)多目標(biāo)優(yōu)化問(wèn)題（2個(gè)任務(wù)）構(gòu)成。通過(guò)對(duì)這些測(cè)試集的Pareto Sets 進(jìn)行旋轉(zhuǎn)和平移，得到4 組新的多目標(biāo)多任務(wù)測(cè)試集，分別記為MATP1～MATP4，這4 組測(cè)試集是基于任務(wù)間聯(lián)系的先驗(yàn)知識(shí)創(chuàng)建的，任務(wù)間的聯(lián)系通過(guò)多目標(biāo)優(yōu)化問(wèn)題的Pareto Sets 重合程度來(lái)衡量。每個(gè)測(cè)試集包含5 個(gè)任務(wù)，這些測(cè)試問(wèn)題的詳細(xì)信息如表1 所示。

表1 多目標(biāo)多任務(wù)測(cè)試問(wèn)題信息Table 1 Information about multi-objective multi-tasking test problems

在上述4 組測(cè)試函數(shù)集的基礎(chǔ)上，將本文算法EMTSD 與MO-MFEA-II［22］、MaTEA［21］、MO-MFEA［9］等多目標(biāo)多任務(wù)算法進(jìn)行比較。其中：MO-MFEA-II算法采用最小化任務(wù)間KL 散度的方式找出任務(wù)間的聯(lián)系；MaTEA 算法采用KL 散度和自適應(yīng)獎(jiǎng)勵(lì)策略的方式為目標(biāo)任務(wù)選擇一個(gè)最合適的輔助任務(wù)；MO-MFEA算法采用隨機(jī)遷移的方式實(shí)施任務(wù)間的知識(shí)遷移。

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

將實(shí)驗(yàn)中每個(gè)任務(wù)的種群規(guī)模設(shè)置為100，算法的最大進(jìn)化代數(shù)為500代，算法的獨(dú)立運(yùn)行次數(shù)為20次。對(duì)于多目標(biāo)多任務(wù)優(yōu)化算法，多目標(biāo)優(yōu)化算法是NSGA-II。在DE算法中，令F=0.5、CCR=0.4。根據(jù)文獻(xiàn)［24］，CMA-ES算法中的步長(zhǎng)參數(shù)σt=0.3，步長(zhǎng)更新的阻尼參數(shù)dσ=1。根據(jù)文獻(xiàn)［9］，將MO-MFEA 算法中的隨機(jī)交配概率值設(shè)置為0.3。根據(jù)文獻(xiàn)［21］，將MaTEA 算法中的知識(shí)遷移率設(shè)置為α=0.1，令精英集更新率UUR=0.2，精英集最大規(guī)模AAcS=300。MO-MFEA-II 算法中使用的概率模型為多元正態(tài)分布。

3.2 算法性能表征

本文采用反轉(zhuǎn)世代距離（Inverted Generational Distance，IGD）來(lái)表征算法的性能。IGD 的原理是計(jì)算Pareto 最優(yōu)解集中的點(diǎn)到算法最終得到的解之間的平均距離。IGD 的值越小，表明算法最終得到的解接近問(wèn)題的Pareto 前沿界面且具有良好的分布性。IGD 值通過(guò)式（13）計(jì)算：

其中：dist（x，A）表示Pareto 前沿界面上的參考點(diǎn)x到算法最終求解得到的解之間的最小距離；P*表示Pareto 前沿界面上預(yù)設(shè)的參考點(diǎn)集合。

3.3 結(jié)果分析

表2 所示為EMTSD 算 法、MaTEA 算 法、MO-MFEA-II算法與MO-MFEA 算法在4 組多任務(wù)測(cè)試集下運(yùn)行20 次得到的平均IGD 值，表中加粗?jǐn)?shù)字表示該組數(shù)據(jù)最大值。

表2 不同算法在測(cè)試集下運(yùn)行的平均IGD 值對(duì)比Table 2 Comparison of average IGD value of different algorithms running on the test suites

從表2 中可以看到，與其他算法相比，EMTSD 算法在大多數(shù)測(cè)試問(wèn)題中均顯示出卓越的性能，這是因?yàn)樵诿恳淮N群進(jìn)化過(guò)程中，EMTSD 算法均從正態(tài)分布群體中采樣產(chǎn)生新的種群個(gè)體，通過(guò)任務(wù)間種群的分布特征差異和分布距離找到任務(wù)間相似度，進(jìn)而實(shí)施任務(wù)間的知識(shí)遷移，促進(jìn)種群中解的多樣性并加速目標(biāo)任務(wù)的收斂。MaTEA 算法和MO-MFEA-II 算法均采用多元高斯分布來(lái)近似模擬種群的真實(shí)分布，然而這些算法中的種群個(gè)體通過(guò)雜交變異產(chǎn)生，并不像EMTSD 算法通過(guò)在多元高斯分布中采樣產(chǎn)生種群個(gè)體，這樣會(huì)導(dǎo)致真實(shí)的種群分布是隨機(jī)且不可預(yù)測(cè)的，因此多元高斯分布通常很難準(zhǔn)確近似為真實(shí)的種群分布。對(duì)于MO-MFEA 算法，由于缺乏衡量任務(wù)間相似度的步驟，因此在任務(wù)間隨機(jī)進(jìn)行知識(shí)遷移時(shí)，難以保證知識(shí)遷移會(huì)對(duì)目標(biāo)任務(wù)起作用。然而，EMTSD算法在MATP2-T1、MATP2-T3、MATP2-T4、MATP2-T5、MATP3-T3、MATP3-T4、MATP4-T2這7 個(gè)任務(wù)中的性能比其他算法差。在實(shí)驗(yàn)中發(fā)現(xiàn)，測(cè)試問(wèn)題集MATP2 和MATP3 中各個(gè)測(cè)試問(wèn)題的Pareto Sets 之間較相似，因此在其他算法中，針對(duì)某個(gè)目標(biāo)任務(wù)，從最相似的任務(wù)中隨機(jī)選擇解來(lái)實(shí)施知識(shí)遷移的策略，能夠幫助目標(biāo)任務(wù)跳出局部最優(yōu)，找到更多分布性良好的最優(yōu)解。

表3 所示為EMTSD 算 法、MaTEA 算 法、MO-MFEA-II 算法與MO-MFEA 算法在4 組多任務(wù)測(cè)試集下運(yùn)行20 次的平均運(yùn)行時(shí)間對(duì)比。由于EMTSD 算 法、MaTEA 算法和MO-MFEA-II 算法衡量任務(wù)間相似度的方式不同，因此每個(gè)算法在衡量任務(wù)間相似度方面花費(fèi)的計(jì)算資差異直接影響了各個(gè)算法最終運(yùn)行時(shí)間的差異。

表3 不同算法在測(cè)試集運(yùn)行時(shí)的平均運(yùn)行時(shí)間對(duì)比Table 3 Comparsion of average running time of different algorithms s

由表3可知，EMTSD 算法的運(yùn)行時(shí)間比MaTaE 算法和MO-MFEA-II算法都要短，MO-MFEA-II算法運(yùn)行的時(shí)間最長(zhǎng)。這主要是因?yàn)镸O-MFEA-II 算法需要構(gòu)建概率模型來(lái)近似種群的真實(shí)分布，而求解該概率模型需要花費(fèi)大量的計(jì)算資源。此外，EMTSD算法在4組多任務(wù)測(cè)試集下的平均運(yùn)行時(shí)間比MaTEA 算法縮短約66.62%。盡管MO-MFEA 算法只需要很短的運(yùn)行時(shí)間，但它缺乏衡量任務(wù)間相似度這一步驟，隨機(jī)實(shí)施知識(shí)遷移的做法會(huì)導(dǎo)致算法的性能較差。

為驗(yàn)證EMTSD 算法在衡量任務(wù)間相似度方面的有效性，表4 和表5 分別列出了EMTSD 算法在MATP1和MATP2測(cè)試集中計(jì)算得到的任務(wù)間相似度，其中“—”表示忽略該欄的值。由表4 和表5 可知，在MATP1 測(cè)試集中，任務(wù)T1與任務(wù)T2較相似，任務(wù)T3與任務(wù)T4較相似，任務(wù)T5與其他任務(wù)之間的相似度較低。在MATP2 測(cè)試集中，任務(wù)T1與任務(wù)T2之間、任務(wù)T3與任務(wù)T4之間的相似程度均較高，任務(wù)T5與其他任務(wù)之間的相似度較低。實(shí)驗(yàn)得出的結(jié)果與事先已知的任務(wù)間相似度高度吻合，因此可以說(shuō)明EMTSD 算法衡量任務(wù)間相似度的方法是有效的。

表4 EMTSD 算法在MATP1 測(cè)試集中得到的任務(wù)間相似度Table 4 Similarity between tasks in the MATP1 test set obtained by EMTSD algorithm

表5 EMTSD 算法在MATP2 測(cè)試集中得到的任務(wù)間相似度Table 5 Similarity between tasks in the MATP2 test set obtained by EMTSD algorithm

4 結(jié)束語(yǔ)

本文提出一種基于自適應(yīng)協(xié)方差矩陣調(diào)整的多目標(biāo)多任務(wù)優(yōu)化算法，令所有任務(wù)中的種群個(gè)體均通過(guò)正態(tài)分布采樣產(chǎn)生，并采用不同任務(wù)種群間的分布特征差異和分布距離得到任務(wù)間的相似度，從而找到與目標(biāo)任務(wù)最相似的任務(wù)并實(shí)施知識(shí)遷移。采用種群的協(xié)方差矩陣反映種群的分布特征，使用不同種群均值之間的距離反映任務(wù)間種群的分布距離。實(shí)驗(yàn)結(jié)果表明，與EMTSD、MaTEA、MO-MFEA-II等多目標(biāo)多任務(wù)優(yōu)化算法相比，本文算法具有較好的收斂性能，平均運(yùn)行效率提高了約66.62%。下一步將結(jié)合遷移學(xué)習(xí)中特征遷移的相關(guān)理論，使本文算法能應(yīng)用于復(fù)雜的多目標(biāo)多任務(wù)優(yōu)化問(wèn)題。