基于差分進化鄰域自適應的大規模多目標算法

閆世瑛, 顏克斐, 方 偉, 陸恒楊

(江南大學人工智能與計算機學院, 江蘇 無錫 214122)

0 引 言

大規模多目標優化問題(large-scale multi-objective optimization problems,LSMOPs)是指有兩個或三個目標的帶有多于100個決策變量的問題。對于多目標問題的求解已經有很多研究成果,例如帶精英選擇策略的非支配排序多目標遺傳算法、基于參考點的非支配排序的進化多目標優化算法、基于分解的多目標優化算法(multi-objective evolutionary algorithm based on decomposition，MOEA/D)等。對于單目標大規模優化問題,以協同進化(coo-perative coevolution)為框架將問題采用分治策略來處理是可行手段之一。但對LSMOPs使用傳統的多目標優化算法或者大規模優化算法往往都得不到好的效果。原因是隨著維數增加,其搜索空間會呈指數式增長,導致算法無法收斂或者陷入局部最優,不但計算成本很高,而且復雜性也會成倍增加。差分進化算法相比遺傳算法在高維上收斂速度更快且不容易陷入局部最優,易與其他算法相結合構造混合算法,被廣泛應用于LSMOPs的求解中,改進的差分進化算法主要提升算法的收斂速度,克服早熟收斂和搜索停滯的問題,LSMOPs與之結合能顯著提升算法性能。目前，針對LSMOPs的求解方法大致可以分為3種類型。

第一類是基于決策變量分解的思想,采用分治思想將決策變量分為若干小組并單獨優化,從而解決LSMOPs搜索空間過大的問題,但在分組決策變量時需耗費較多計算資源。Iorio等提出基于非支配排序的合作協同進化算法,首先將各決策變量分派到不同的子種群中,再通過帶精英選擇策略的非支配排序算法優化各個子種群。Ma等提出基于決策變量分析的大規模多目標優化算法(large-scale multi-objective evolutionary algorithm based on decision variable analysis, MOEA/DVA),利用決策變量分析策略將所有變量分為距離變量、位置變量和混合變量三類,然后根據各個距離變量間的相互作用關系劃分出多個子多目標優化問題,在種群進化階段先優化距離變量從而提升種群的收斂性,然后優化所有變量從而獲得種群多樣性性能的提升。MOEA/DVA將決策變量分析應用到LSMOPs的求解中,但是對混合變量的處理不夠有針對性,僅考慮其對多樣性進化的影響,將混合變量與位置變量合并,共同優化種群的多樣性。此外,種群的進化過程分為前期收斂性進化階段和后期多樣性進化階段,但是區分進化前期的結束時間與后期的開始時間在實際問題上較為困難。Zhang等提出基于變量聚類的大規模多目標進化算法(evolutionary algorithm for large-scale multi-objective optimization,LMEA),首先用均值聚類法將決策變量劃分分為收斂性變量和多樣性變量兩類,然后進行交替迭代,使用不同方法來優化不同類型的變量。

第二類是基于決策空間縮減的思想,利用問題轉化思想將LSMOPs轉化為小規模優化問題,并使用傳統進化算法進行優化求解,從而減小決策空間,降低搜索最優解集的難度,但問題轉化策略在不連續的搜索空間易陷入局部最優。Zille等提出基于問題轉化的求解LSMOPs的框架,用一組權重來改變決策向量,然后將權重作為要優化的變量來建立小規模的多目標優化問題。He等提出問題重構加速大規模多目標優化的通用框架,在搜索空間上定義多個參考方向,在進化過程中通過擾動參考方向的解來探索更優解。Liu等提出基于聚類和降維的多目標進化算法,首先通過聚類方法將決策變量劃分為收斂變量和多樣性變量,然后通過主成分分析減少收斂性相關變量,并用差分分組進一步劃分收斂性相關變量。

最后一類通過提出新的搜索策略直接解決LSMOPs,主要包括新的復制算子和概率模型,無需借助決策變量分組或決策空間縮減,但其對問題的求解效率隨決策變量數的增長而降低。Zhang等提出基于信息反饋模型的大規模多目標優化算法,設計6個信息反饋模型并集成到MOEA/D中,通過根據歷史信息更新產生子代。Cheng等提出基于概率模型的多目標優化算法,構建基于高斯過程的逆模型,將解從目標空間映射到決策空間,并使用逆模型對目標空間進行采樣來生成后代。

針對基于決策變量分解思想的求解方法,由于LSMOPs包含多個互相沖突的目標,在這些目標上決策變量之間的相互作用可能不同,優化每組變量時應同時考慮種群的收斂性和多樣性。因此，在LSMOPs上分組決策變量需要更精細的算法。基于問題轉化的方法通過優化當前解的最佳權重來減少決策空間,雖然可以快速找到一些局部最優解,但是轉化后的問題可能會丟失全局最優解。此外,雖然機器學習中已經有大量降維技術,但是由于其縮短的向量不可恢復,所以大多數都不能用來解決LSMOPs。為了解決上述問題,本文提出了一種基于差分進化鄰域自適應策略的大規模多目標優化算法(large-scale multi-objective optimization based on differential evolution with neighborhood adaptive strategy, NAS-MOEA)。首先,對決策變量進行分析,擾動決策變量生成一系列被擾動解,根據被擾動解間的支配關系將決策變量分為兩類,即多樣性變量和收斂性變量,使變量分類更加準確,提升了進化過程的效率。其中,對收斂性變量進行主成分分析降噪,在保留原始數據主要信息的前提下使主成分間沒有關聯,從而減少計算成本并獲得更好的結果。然后對種群交替進化,采用優化策略交替處理收斂性變量和多樣性變量,平衡了進化種群收斂性變量與多樣性變量之間的關系,避免算法陷入局部最優。在使用差分進化算法優化收斂性變量時,設計了鄰域自適應更新操作,進而加快了種群在進化過程中的收斂速度。

1 問題描述

一個具有維決策變量,個目標函數的LSMOPs可以描述為

(1)

式中:=(,,…,)∈為決策變量;()為目標向量，由個目標函數()共同組成；()(=1,2,…,)表示目標函數需滿足個不等式約束；()(=1,2,…,)表示目標函數需滿足個等式約束。在此基礎上,給出以下幾個重要定義。

帕累托占優:假設可行解集中存在兩個可行解、,當且僅當

(2)

則稱與相比是帕累托占優的,記作p,稱為支配。

(3)

帕累托最優前沿:PS中的所有帕累托最優解對應的目標矢量組成的曲面稱為帕累托最優前沿(Pareto front,PF):

PF?{()|∈PS}

(4)

帕累托真正的前沿記為PF。

2 NAS-MOEA

2.1 決策變量分析

在LSMOPs中,既要保證解集的收斂性,也要保證解集的多樣性,相對應的,一部分決策變量主要控制著解集生成的收斂性,而另一部分則主要控制著解集生成的多樣性。因此,優化算法可以根據變量的不同控制類型來對其進行分類。Ma等提出的決策變量分類策略基于擾動解的支配關系將決策變量分為位置變量、距離變量和混合變量。當擾動解間均為支配關系時為距離變量,控制種群的收斂性,當擾動解間都處于同一PF時稱為位置變量,控制種群的多樣性,其余稱為混合變量。由于混合變量與位置變量都對種群的分布有影響,因此將這兩類變量都用作控制種群的多樣性。但是有些混合變量生成的擾動解間大多數為支配關系,只有少數不是,那么這種變量在實際進化中更趨向于控制種群的收斂性,若用這種更適合進化種群收斂性的混合變量來進化種群的多樣性不但會造成資源浪費,而且也沒有達到種群多樣性進化的目的。

因此,本文改進了決策變量的分類方式,對于距離變量和位置變量依舊根據其對種群收斂性和多樣性的影響劃分為收斂性變量和多樣性變量。對混合變量則根據其對收斂性和多樣性的偏好進行分類,若該混合變量趨向于控制解的收斂性,則將其劃分為收斂性變量,反之則劃分為多樣性變量。這樣提升了分類的準確性,能夠在后續優化過程中對不同種類的變量進行更精確的處理,進而提升算法的整體性能。

圖1舉例說明了混合變量分析的過程,在圖1中使用的多目標優化問題是

(5)

圖1 混合變量分析示意圖Fig.1 Schematic diagram of mixed variable analysis

圖1中，()和()為兩個目標函數,圓點和方點分別表示保持其他變量等于05而只改變和各8次產生的擾動解。需要注意的是,評價擾動解間的支配關系需要耗費的目標函數評價次數與擾動解的個數相同。由圖1可以看出,大部分方點都處于同一個PF上,只有一個點與其他點間存在支配關系;對圓點而言,只有兩個點在同一PF上,其他點間互為支配關系。因此,雖然這兩個點均為混合變量,但是對于進化種群收斂性和多樣性的影響是不同的,圓點對于進化種群收斂性更佳,方點則更適合進化種群多樣性,這說明了分離混合變量,針對不同種類的混合變量進行針對性處理的必要性。算法1給出了決策變量分析的算法。

算法1 決策變量分析算法輸入 決策變量數n,采樣個數NCA。輸出 多樣性變量的索引向量DiverIndexes,收斂性變量的索引向量ConverIndexes。步驟 1 在可行域內生成隨機向量X=(x1,x2,…,xi,…,xn),設置樣本解集DiverIndexes=ConverIndexes=S=?。步驟 2 按照x'i←xLi+j-1+randNCA·(xUi-xLi))對xi進行NCA次擾動,得到F(x1,x2,…,xi-1,x'i,xi+1,…,xn),將其加入到樣本解集S中。其中,rand是分布在[0,1)上的均勻隨機數。步驟 3 使用非支配排序方法對樣本解集S進行排序,得到非支配解的數量。步驟 4 如果非支配解的數量小于NCA/2,那么xi被判定為收斂性變量,將i加入到收斂性索引向量ConverIndexes中;否則,xi被判定為多樣性變量,將i加入到多樣性索引向量DiverIndexes中。

2.2 主成分分析降噪策略

決策變量分為收斂性變量和多樣性變量之后,本文對收斂性變量使用了主成分分析降噪策略,用于獲得收斂性變量的降噪表示,它代表了數據集中的關鍵信息。算法2給出了主成分分析降噪的算法。

算法2 主成分分析降噪算法輸入 種群pop,收斂性變量的索引向量ConverIndexes。輸出 降噪后的種群pop。步驟 1 計算收斂性變量的協方差矩陣V。步驟 2 對協方差矩陣V進行特征分解,求得該矩陣所對應的特征值λi和特征向量wi,并對特征值λi進行降序排列。步驟 3 根據貢獻率的大小,取前d個特征值Λ=diag[λ1,λ2,…,λd]和相應的特征向量Wd=[w1,w2,…,wd]作為子空間的基。步驟 4 由所提取的主成分重建原數據,得到降噪后的種群pop。

使用主成分分析進行降噪而非降維的原因是,降維操作會導致決策變量維數改變,隨著參考坐標系的改變,計算適應度值時的映射關系也就發生了改變,這種改變是黑盒的,無法用公式來進行描述。先降維,將降維后的數據重建成原來的維度,一些對收斂性進化影響不大的值會被去除,在原始數據主要信息保留的前提下使主成分間沒有關聯,會使決策變量的特征更清晰,從而減少計算成本并獲得更好的結果。

2.3 交替進化策略

在開始進化前,NAS-MOEA利用鏈接學習的思想將一個龐大的多目標優化問題分解為許多個比較簡易的子多目標優化問題。其中,這些子多目標優化問題的多樣性變量是均勻分布的,通過固定原始多目標優化問題的多樣性變量生成,每一個子多目標優化問題的多樣性變量都是不變的,只有全體收斂性變量需要被優化。

圖2為種群結構示意圖,共有個子多目標優化問題,每個問題有8個決策變量,,…,。其中,,是多樣性變量，而,,…,是收斂性變量。

圖2 NAS-MOEA的種群結構示意圖Fig.2 Schematic diagram of population structure of NAS-MOEA

在進化階段,NAS-MOEA采用不同的策略交替地優化收斂性變量與多樣性變量直至算法結束。在種群收斂性進化階段,固定種群多樣性變量的值而只進化收斂性變量,在種群多樣性進化階段,固定種群收斂性變量的值而只進化多樣性變量。圖3為種群交替進化流程圖。

圖3 種群交替進化流程圖Fig.3 Flow chart of population alternate evolution

在種群的收斂性進化階段,NAS-MOEA使用差分進化算子。變異策略為DE/rand/1,其定義為

,=1,+·(2,-3,)

(6)

在當前代中,對于個體,,首先找到該子多目標問題的鄰域,從鄰域中隨機選取兩個個體2,和3,作為偏差向量,生成一個新個體,。其中,需關注變異算子,變異算子決定偏差向量的放大比例,過小造成算法早熟,過大導致算法的收斂性變差。因此,在NAS-MOEA中的變異算子使用0～1之間的隨機值,在進化收斂性變量時,避免算法早熟以及收斂性變差。

在種群的多樣性進化階段,首先NAS-MOEA對每個子多目標優化問題都會隨機產生一個新的子代解,需要注意的是,這些子代解只有全部多樣性變量與父代解不同。然后,NAS-MOEA將父代種群和所有新生成的子代解相結合,并對其進行非支配排序,最終得到許多個非支配前沿。在此過程中,NAS-MOEA會選出位于前個非支配前沿位置的解,其中是滿足|PF∪PF∪…∪PF|≤||的最大值。若=0,NAS-MOEA則尋找至少在一個目標方向上具有最大目標值的解,將其放入選擇之后的新種群中。之后,NAS-MOEA每次從第+1個非支配前沿中選出一個解直到所有選出解的數量與種群的大小相同,其中,NAS-MOEA在第+1個非支配前沿中每次選擇的單個解必須保證與所有已經被選中的解有最遠的距離。

2.4 差分進化的鄰域自適應更新策略

自適應更新鄰域策略指每個子多目標優化問題優化完成后,自適應地更新該子多目標優化問題的鄰域,這樣每次使用鄰域時都能保證此鄰域是該子多目標優化問題當前的鄰域,使算法更容易找到PF,從而提升算法的收斂速度。

鄰域的自適應更新策略在收斂性變量的進化過程中執行,在使用差分進化算子進化收斂性變量時,首先要找到每個子多目標問題的鄰域。通過比較當前子多目標優化問題與其他子多目標優化問題間多樣性變量的歐幾里得距離獲取當前子多目標優化問題的鄰域。

但是隨著迭代次數的增加,該子多目標優化問題與其他子多目標優化問題間的歐式距離可能會發生改變,可能靠近也可能遠離。這時,以最初找到的鄰域作為固定鄰域則不夠準確,不利于進化種群的收斂性。

圖4為一次鄰域更新過程示意圖,初始鄰域中有,,,4個子多目標問題,鄰域中有,,3個子多目標問題,隨著一次收斂性變量的進化,的位置由變為′,自適應更新鄰域劃分,將′從鄰域更新到鄰域中,再進行下一次收斂性變量的進化。

圖4 鄰域更新過程示意圖Fig.4 Schematic diagram of neighborhood update process

算法3給出了收斂性變量優化及差分進化的鄰域自適應更新過程。

算法3 收斂性變量優化流程輸入 進化種群當前解pop及其目標值Obj,收斂性變量的索引向量indices,子多目標優化問題的個數N。輸出 優化后的進化種群pop及其目標值Obj。步驟 1 令i=1。步驟 2 從第i個子多目標優化問題的鄰域中隨機選擇兩個子多目標優化問題pop(k,indices)和pop(1,indices)。使用差分進化算子生成一個新個體y'←pop(i,indices)+F·(pop(k,indices)-pop(1,indices))。其中,差分進化算子的縮放因子F為0～1之間的隨機值。步驟 3 對新個體y'實行多項式變異操作。步驟 4 若f1(y)+f2(y)+…+fm(y)

2.5 NAS-MOEA算法流程

NAS-MOEA算法的具體流程如算法4所示。

算法4 NAS-MOEA算法流程輸入 LSMOPs,目標數M,決策變量數n,種群大小N,采樣個數NCA,變量鏈接判定的最大試驗次數NIA,變異系數f,鄰域大小S。輸出 經過優化后的種群pop,目標值Obj。步驟 1 使用算法1進行決策變量分析。步驟 2 使用隨機采樣方法初始化種群的收斂性變量,得到pop(:,CV),使用均勻分布采樣點技術初始化種群的多樣性變量,得到pop(:,DV)。步驟 3 使用算法2和鏈接分析技術將收斂性變量分組。步驟 4 計算多樣性變量之間的歐氏距離,按照距離從小到大排列,取最小的S個變量作為該變量的鄰域。步驟 5 進化種群。步驟 5.1 令f的初始值為0.5。步驟 5.2 按照算法3優化收斂性變量。步驟 5.3 優化多樣性變量:使用遺傳算法對種群中的每個解產生一個子代解,將所有子代解與種群結合,并對合并后的種群進行非支配排序;接著,采用擁擠度距離為次環境選擇策略來選出大小為N的種群作為子種群。步驟 5.4 停止準則。如果終止條件滿足,則輸出種群N;否則,返回步驟5.2。

2.6 算法復雜度分析

本文主要的運算量是變量鏈接分析、非支配排序和擁擠度距離計算。變量鏈接分析的復雜度為(),其中是決策變量數。非支配排序的復雜度為(()),其中是種群數量,是目標數。擁擠度距離計算的復雜度為(log())。因此,本算法整體時間復雜度為max((),(()))。LMEA和MOEA/DVA作為本文的對比算法,其時間復雜度分別是(())和max((),())。由此可見,本文提出的算法在復雜度方面與對比算法相似。

3 算法性能測試及分析

3.1 測試函數

本文針對兩目標和三目標的LSMOPs進行測試,分別采用測試函數集為UF和LSMOP系列測試函數。

UF是由IEEE Congress on Evolutionary Computation所提出的針對LSMOPs的測試集,UF測試集有共包括10個連續且不帶約束的多目標優化問題。UF測試集求解難度較高,主要是決策變量間的關聯度很高,這給決策變量分類算法帶來了很大的挑戰。因此,UF測試集中一些求解難度較高的多目標優化問題仍然需要探索更有效的算法去求解。

LSMOP是針對LSMOPs提出的第一個大規模多目標優化測試集,含有9個測試函數。LSMOP測試集不但具有復雜的決策變量關聯性,還有決策變量分組的不均勻性以及適應度函數地形的復雜性,這些都增加了其求解難度。

3.2 性能指標

為了評估算法的性能,在實驗中使用反向世代距離(inverted generational distance,IGD)指標和超體積(hypervolume,HV)指標,二者都能標量化地反映算法的性能。針對某一個測試問題,IGD指標越小,表明該算法獲得的PF越能夠代表該問題的PF,而HV指標反之。IGD的計算公式如下:

(7)

式中：是在PF上均勻分布的一系列解；是PF的近似解；(,)是中的個體到中所有個體的最小歐氏距離。

HV定義為種群中的點與參考點集中的點所圍成的區域的超體積,但HV中的參考點集R是遠離PF的一個或多個參考點,而不是處于PF上的一個或多個隨機采樣點，計算公式如下:

HV(,)=((,))

(8)

式中：表示勒貝格測度,即

(9)

3.3 參數設置

實驗的參數設置如下:種群大小設置為100,最大目標函數評價次數在決策維數為100、300、1 000時分別設為1 000 000、3 000 000、30 000 000,經過20次獨立運行比較算法的IGD結果。本文對比的算法有LMEA和MOEA/DVA,對于NAS-MOEA,在進化收斂性種群階段,設置差分進化時的變異算子的初始值為05,交叉算子為1。鄰域的大小設置為01,每個解被子代解替換的概率為001,從鄰域中選擇父代解的概率設置為09。為了方便比較,決策變量分析的相關參數設置與LMEA一致。在NAS-MOEA和MOEA/DVA中的決策變量相關性分析次數設為6,決策變量分析中解的選擇數量設為20,LMEA中的決策變量聚類中解的選擇數量設為2,每個解的擾動次數NCA設為4,決策變量相關性分析次數設為6。

3.4 實驗結果與分析

表1給出了NAS-MOEA和MOEA/DVA,LMEA在UF和LSMOP上20次運行后得到的IGD和平均運行時間統計結果。表2給出了NAS-MOEA、MOEA/DVA和LMEA在UF和LSMOP上20次運行后得到的HV統計結果。在LSMOP測試集的9個測試函數上的實驗結果由兩行數據構成,分別代表目標數為3時,維數為300,1 000維下的優化結果。在UF測試集上,其中UF1-7測試函數的目標數均設置為2,在UF8-10上設置為3,3行數據分別表示維數為100,300,1 000維下的優化結果。

表1 3種算法在UF和LSMOP上的IGD和平均運行時間結果

續表1

表2 3種算法在UF和LSMOP上的HV結果

續表2

實驗記錄IGD和HV指標的平均值,其中,加粗項為同一測試函數中獲得的最優值。還采用了顯著性水平為0.05的Wilcoxon秩和檢驗對結果進行分析,符號“+”“-”和“≈”分別表示對比算法的性能顯著優于、顯著差于或統計意義上相似于所提出的算法。

3.4.1 參數敏感性分析

NAS-MOEA算法主要用到了3個參數,鄰域的大小、每個解被子代解替換的概率,和從鄰域中選擇父代解的概率。為了分析上述3個參數對算法性能的敏感性,本文對每個參數使用多個實驗數據,的3個實驗值分別是5,10和15,的兩個實驗值為1和09,的4個實驗值分別是08,09,095和099。以3目標300個決策變量的LSMOP1～LSMOP9作為測試問題,每個問題兩個參數的配置都獨立運行3 000 000次。

表3給出了NAS-MOEA在不同參數的3目標300個決策變量的LSMOP上20次運行的IGD結果。從表3中可以看出,NAS-MOEA提出的基于差分進化鄰域自適應的算法對參數,和的不同組合具有很強的魯棒性,在=10,=1,=09下得到的結果最優,在9個測試函數中有3個結果最優,有3個次優。故將=10,=1,=0.作為NAS-MOEA的首選參數設置。

表3 NAS-MOEA在不同參數的3目標300個決策變量的LSMOP上的IGD結果

3.4.2 100維問題上的實驗結果

在這一部分,將NAS-MOEA算法用于具有100維決策變量的測試函數上,使用UF1～UF10問題。實驗結果表明,NAS-MOEA在UF3～UF7、UF10等問題上取得了較好的效果,而MOEA/DVA在UF1、UF2、UF8問題上優化效果最好,對于UF9來說,LMEA的優化效果優于NAS-MOEA算法。從算法總體運行時間上看,NAS-MOEA要稍高于LMEA和MOEA/DVA。

圖5～圖14展示了NAS-MOEA、LMEA和MOEA/DVA在100個變量的UF1～UF10上運行20次獲得的平均最終種群,其最大迭代次數為1 000 000。其中，黑色曲線/點代表理想的PF,灰色圓圈代表各算法運行得到的真實個體,形成了PF。可以看到，NAS-MOEA在UF2～UF3,UF6,UF8～UF10問題上獲得的解集在多樣性和收斂性上要比對比方法更好。在UF1,UF4,UF5,UF7上MOEA/DVA找到的解集與NAS-MOEA相似,均比LMEA在多樣性和收斂性上更好。實驗結果表明,NAS-MOEA在保證收斂的情況下對于解集分布更加均勻,之所以NAS-MOEA在被選問題上成功,主要原因是將決策變量根據其本身性質劃分為收斂性變量和多樣性變量,對每種變量進行針對性處理,并利用其特性進行收斂性和多樣性的交替進化操作,這說明NAS-MOEA在大規模決策變量測試問題上的優越性。

圖5 100個變量的UF1上的解集Fig.5 Solution set on UF1 with 100 variables

圖6 100個變量的UF2上的解集Fig.6 Solution set on UF2 with 100 variables

圖7 100個變量的UF3上的解集Fig.7 Solution set on UF3 with 100 variables

圖8 100個變量的UF4上的解集Fig.8 Solution set on UF4 with 100 variables

圖9 100個變量的UF5上的解集Fig.9 Solution set on UF5 with 100 variables

圖10 100個變量的UF6上的解集Fig.10 Solution set on UF6 with 100 variables

圖11 100個變量的UF7上的解集Fig.11 Solution set on UF7 with 100 variables

圖12 100個變量的UF8上的解集Fig.12 Solution set on UF8 with 100 variables

圖13 100個變量的UF9上的解集Fig.13 Solution set on UF9 with 100 variables

圖14 100個變量的UF10上的解集Fig.14 Solution set on UF10 with 100 variables

3.4.3 300維問題上的實驗結果

統計結果表明,NAS-MOEA在LSMOP1～LSMOP9、UF3～UF7、UF9和UF10等絕大多數問題上的性能都優于MOEA/DVA和LMEA,MOEA/DVA在UF1和UF2上依舊以微弱的差距優于NAS-MOEA,在UF8上LMEA優于MOEA/DVA和NAS-MOEA。總體來看,NAS-MOEA對于三目標問題的求解優勢更為顯著,在給出的所有三目標測試函數上的IGD和HV結果均優于對比算法。原因是NAS-MOEA采用了分治策略,將一個復雜的LSMOPs轉化為了多個簡單的子多目標優化問題,減小了問題的規模,加快了算法的執行速度,并對其進行交替優化,通過交替進化收斂性變量和多樣性變量,平衡了算法的收斂性和多樣性。

圖15～圖20選取了對比算法在300變量的部分LSMOP和UF測試函數上運行20次得到的平均最終種群,最大迭代次數為3 000 000。其中，黑色曲線和三維網狀圖代表PF,灰色圓圈代表各算法運行得到的真實個體,形成了PF。

圖15 300個變量的UF3上的解集Fig.15 Solution set on UF3 with 300 variables

圖16 300個變量的UF6上的解集Fig.16 Solution set on UF6 with 300 variables

圖17 300個變量的UF8上的解集Fig.17 Solution set on UF8 with 300 variables

圖18 300個變量的LSMOP4上的解集Fig.18 Solution set on LSMOP4 with 300 variables

圖19 300個變量的LSMOP8上的解集Fig.19 Solution set on LSMOP8 with 300 variables

圖20 300個變量的LSMOP9上的解集Fig.20 Solution set on LSMOP9 with 300 variables

NAS-MOEA獲得的PF優于其他算法的結果,對UF3和LSMOP4而言,MOEA/DVA得到的解集較為均勻,這是因為其能正確地將決策變量分組,故在此問題上性能較好。NAS-MOEA也可以正確地將這些問題中的決策變量分組,故也能在這些問題上得到最好或與MOEA/DVA相當的結果。NAS-MOEA在UF8上的性能與LMEA相當,但是在解集的分布性上優于LMEA,這是因為NAS-MOEA采用交替進化策略,平衡了進化種群的收斂性和多樣性的沖突。NAS-MOEA在UF6、LSMOP8、LSMOP9上性能要優于LMEA和MOEA/DVA,原因是NAS-MOEA采用主成分分析降噪和差分進化的鄰域自適應更新策略,兩種策略相結合使NAS-MOEA在進化過程中更高效的進化種群,這對種群收斂性有積極作用。因此本實驗可以驗證NAS-MOEA在大規模決策變量問題上的有效性,其收斂能力和多樣性能力更優。

3.4.4 1 000維問題上的實驗結果

在1 000維的測試函數上,在LSMOP系列和UF系列共19個測試函數上進行實驗,IGD結果表明,NAS-MOEA在其中的17個測試函數上的性能都優于MOEA/DVA和LMEA,在UF8上NAS-MOEA表現雖不如LMEA,但與MOEA/DVA相比仍有優勢,MOEA/DVA在UF9上表現更優。HV結果表明,NAS-MOEA在其中的14個測試函數上的性能都優于對比算法,NAS-MOEA和MOEA/DVA在UF1～UF3上表現相似,MOEA/DVA略優于NAS-MOEA,兩算法均優于LMEA。從算法總體運行時間上看,NAS-MOEA在LSMOP7上運行時間小于MOEA/DVA,在全部測試函數上總體運行時間均小于LMEA。

可以看出,隨著決策變量的增加,NAS-MOEA的優勢逐漸顯現出來,這主要是因為差分進化的鄰域自適應更新策略隨著決策變量的增加顯示出了其優越性。收斂性變量的鄰域自適應更新是收斂性變量的優化是進化過程中最重要的環節之一,在收斂性變量差分進化的過程中,從合適的鄰域中選取父代有助于更快地找到非支配前沿,在進化過程中不斷更新鄰域,會加快種群收斂性進化的速度,從而更快更好地找到PF。

3.4.5 算子有效性的實驗驗證

為了進一步探究NAS-MOEA中各個算子的貢獻度和魯棒性,本節針對每一個算子設計了消融實驗,通過與算法中的一部分進行對比,在保證其余部分一直可控的情況下,單獨探究每個算子的有效性。為此,設計了4種NAS-MOEA變體,分別命名為去除決策變量分析的NAS-MOEA(NAS-MOEA without decision variable analysis，NAS-DVA)、去除決策變量分析的NAS-MOEA(NAS-MOEA without principal component analysis，NAS-PCA)、去除交替進化策略的NAS-MOEA(NAS-MOEA without alternate evolution strategy，NAS-EVO)、去除鄰域自適應策略的NAS-MOEA(NAS-MOEA without neighborhood adaptive strategy，NAS-NAS)。

在NAS-DVA中,去除了決策變量分析算子,對于混合變量沒有進一步劃分,將混合變量默認為多樣性變量。NAS-PCA去除了收斂性變量的降噪算子,直接對收斂性變量進行鏈接分析。在NAS-EVO中,放棄了種群的交替進化策略,取而代之的是將整個進化過程分為兩階段,第一階段進化種群的收斂性,第二階段進化種群的多樣性。NAS-NAS去除了收斂性進化過程中的鄰域自適應更新算子,只在開始進化前計算鄰域組成,在進化收斂性過程中不改變鄰域。NAS-MOEA和其4個變體在LSMOP和UF測試集上的IGD結果表4所示。表5給出了NAS-PCA和NAS-MOEA在2目標3 000個決策變量的5個UF問題上20次運行的平均運行時間統計結果。

表4 5種算法在UF和LSMOP上算子有效性驗證的IGD結果

續表4

表5 NAS-MOEA和NAS-PCA在3目標3 000個決策變量的LSMOP上的運行時間結果

從表4可以看出,在1 000維以下的NAS-MOEA在LSMOP6～LSMOP10、UF3～UF8的性能均優于NAS-PCA,這表明主成分分析降噪策略對算法性能提升有效果。在與NAS-PCA算子的比較中,從表5可以看出在UF1,UF2和UF5測試函數上,缺少降噪算子會導致算法的總體運行時間變長,這說明在高維情況下降噪算子在保留原始數據主要信息的前提下能有效減少計算成本,效果會隨著維數的增加而更加明顯。

在與NAS-DVA算子的比較中可以驗證決策變量分析算子的有效性,通過對混合變量的準確劃分,使算法在后續進化過程中對不同種類變量采用不同進化方式的策略得以實現。在與NAS-EVO的比較中,交替進化策略的去除導致算法的尋優效率減慢,導致NAS-EVO在大多數測試函數上表現都比較差。因此可以看出,交替進化策略對進化種群收斂能力和多樣性尋優能力有影響。在與NAS-NAS的對比可以看出,差分進化的鄰域的自適應更新策略避免了鄰域變化對種群的收斂性進化的不利影響,加快了收斂性進化的速度。

4 結 論

本文針對LSMOPs提出了NAS-MOEA。在NAS-MOEA中,設計了一種新的決策變量分類方法,根據決策變量分別對收斂性和多樣性的貢獻,將決策變量分為兩組,即收斂性變量和多樣性變量。使用主成分分析策略對收斂性變量進行降噪處理,根據分組結果,分別對兩組變量進行交替優化,在優化收斂性變量的過程中又加入差分進化的鄰域自適應更新策略。多種機制相結合,有助于提升算法的收斂能力。在具有多達1 000個決策變量的19個復雜測試函數上開展實驗,并將實驗結果與經典大規模多目標優化算法以及最新的大規模優化算法進行對比。實驗結果表明,本文提出的算法能在一定的計算時間內具有更快的收斂速度和更高的尋優精度,表現出良好的性能。下一步將探索新的決策變量分類方法,減少變量分組階段的計算資源消耗,以進一步提高算法性能,加快問題求解。