基于差分進(jìn)化鄰域自適應(yīng)的大規(guī)模多目標(biāo)算法

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

(江南大學(xué)人工智能與計(jì)算機(jī)學(xué)院, 江蘇 無(wú)錫 214122)

0 引 言

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

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

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

最后一類(lèi)通過(guò)提出新的搜索策略直接解決LSMOPs,主要包括新的復(fù)制算子和概率模型,無(wú)需借助決策變量分組或決策空間縮減,但其對(duì)問(wèn)題的求解效率隨決策變量數(shù)的增長(zhǎng)而降低。Zhang等提出基于信息反饋模型的大規(guī)模多目標(biāo)優(yōu)化算法,設(shè)計(jì)6個(gè)信息反饋模型并集成到MOEA/D中,通過(guò)根據(jù)歷史信息更新產(chǎn)生子代。Cheng等提出基于概率模型的多目標(biāo)優(yōu)化算法,構(gòu)建基于高斯過(guò)程的逆模型,將解從目標(biāo)空間映射到?jīng)Q策空間,并使用逆模型對(duì)目標(biāo)空間進(jìn)行采樣來(lái)生成后代。

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

1 問(wèn)題描述

一個(gè)具有維決策變量,個(gè)目標(biāo)函數(shù)的LSMOPs可以描述為

(1)

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

帕累托占優(yōu):假設(shè)可行解集中存在兩個(gè)可行解、,當(dāng)且僅當(dāng)

(2)

則稱(chēng)與相比是帕累托占優(yōu)的,記作p,稱(chēng)為支配。

(3)

帕累托最優(yōu)前沿:PS中的所有帕累托最優(yōu)解對(duì)應(yīng)的目標(biāo)矢量組成的曲面稱(chēng)為帕累托最優(yōu)前沿(Pareto front,PF):

PF?{()|∈PS}

(4)

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

2 NAS-MOEA

2.1 決策變量分析

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

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

圖1舉例說(shuō)明了混合變量分析的過(guò)程,在圖1中使用的多目標(biāo)優(yōu)化問(wèn)題是

(5)

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

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

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

2.2 主成分分析降噪策略

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

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

使用主成分分析進(jìn)行降噪而非降維的原因是,降維操作會(huì)導(dǎo)致決策變量維數(shù)改變,隨著參考坐標(biāo)系的改變,計(jì)算適應(yīng)度值時(shí)的映射關(guān)系也就發(fā)生了改變,這種改變是黑盒的,無(wú)法用公式來(lái)進(jìn)行描述。先降維,將降維后的數(shù)據(jù)重建成原來(lái)的維度,一些對(duì)收斂性進(jìn)化影響不大的值會(huì)被去除,在原始數(shù)據(jù)主要信息保留的前提下使主成分間沒(méi)有關(guān)聯(lián),會(huì)使決策變量的特征更清晰,從而減少計(jì)算成本并獲得更好的結(jié)果。

2.3 交替進(jìn)化策略

在開(kāi)始進(jìn)化前,NAS-MOEA利用鏈接學(xué)習(xí)的思想將一個(gè)龐大的多目標(biāo)優(yōu)化問(wèn)題分解為許多個(gè)比較簡(jiǎn)易的子多目標(biāo)優(yōu)化問(wèn)題。其中,這些子多目標(biāo)優(yōu)化問(wèn)題的多樣性變量是均勻分布的,通過(guò)固定原始多目標(biāo)優(yōu)化問(wèn)題的多樣性變量生成,每一個(gè)子多目標(biāo)優(yōu)化問(wèn)題的多樣性變量都是不變的,只有全體收斂性變量需要被優(yōu)化。

圖2為種群結(jié)構(gòu)示意圖,共有個(gè)子多目標(biāo)優(yōu)化問(wèn)題,每個(gè)問(wèn)題有8個(gè)決策變量,,…,。其中,,是多樣性變量，而,,…,是收斂性變量。

圖2 NAS-MOEA的種群結(jié)構(gòu)示意圖Fig.2 Schematic diagram of population structure of NAS-MOEA

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

圖3 種群交替進(jìn)化流程圖Fig.3 Flow chart of population alternate evolution

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

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

(6)

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

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

2.4 差分進(jìn)化的鄰域自適應(yīng)更新策略

自適應(yīng)更新鄰域策略指每個(gè)子多目標(biāo)優(yōu)化問(wèn)題優(yōu)化完成后,自適應(yīng)地更新該子多目標(biāo)優(yōu)化問(wèn)題的鄰域,這樣每次使用鄰域時(shí)都能保證此鄰域是該子多目標(biāo)優(yōu)化問(wèn)題當(dāng)前的鄰域,使算法更容易找到PF,從而提升算法的收斂速度。

鄰域的自適應(yīng)更新策略在收斂性變量的進(jìn)化過(guò)程中執(zhí)行,在使用差分進(jìn)化算子進(jìn)化收斂性變量時(shí),首先要找到每個(gè)子多目標(biāo)問(wèn)題的鄰域。通過(guò)比較當(dāng)前子多目標(biāo)優(yōu)化問(wèn)題與其他子多目標(biāo)優(yōu)化問(wèn)題間多樣性變量的歐幾里得距離獲取當(dāng)前子多目標(biāo)優(yōu)化問(wèn)題的鄰域。

但是隨著迭代次數(shù)的增加,該子多目標(biāo)優(yōu)化問(wèn)題與其他子多目標(biāo)優(yōu)化問(wèn)題間的歐式距離可能會(huì)發(fā)生改變,可能靠近也可能遠(yuǎn)離。這時(shí),以最初找到的鄰域作為固定鄰域則不夠準(zhǔn)確,不利于進(jìn)化種群的收斂性。

圖4為一次鄰域更新過(guò)程示意圖,初始鄰域中有,,,4個(gè)子多目標(biāo)問(wèn)題,鄰域中有,,3個(gè)子多目標(biāo)問(wèn)題,隨著一次收斂性變量的進(jìn)化,的位置由變?yōu)椤?自適應(yīng)更新鄰域劃分,將′從鄰域更新到鄰域中,再進(jìn)行下一次收斂性變量的進(jìn)化。

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

算法3給出了收斂性變量?jī)?yōu)化及差分進(jìn)化的鄰域自適應(yīng)更新過(guò)程。

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

2.5 NAS-MOEA算法流程

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

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

2.6 算法復(fù)雜度分析

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

3 算法性能測(cè)試及分析

3.1 測(cè)試函數(shù)

本文針對(duì)兩目標(biāo)和三目標(biāo)的LSMOPs進(jìn)行測(cè)試,分別采用測(cè)試函數(shù)集為UF和LSMOP系列測(cè)試函數(shù)。

UF是由IEEE Congress on Evolutionary Computation所提出的針對(duì)LSMOPs的測(cè)試集,UF測(cè)試集有共包括10個(gè)連續(xù)且不帶約束的多目標(biāo)優(yōu)化問(wèn)題。UF測(cè)試集求解難度較高,主要是決策變量間的關(guān)聯(lián)度很高,這給決策變量分類(lèi)算法帶來(lái)了很大的挑戰(zhàn)。因此,UF測(cè)試集中一些求解難度較高的多目標(biāo)優(yōu)化問(wèn)題仍然需要探索更有效的算法去求解。

LSMOP是針對(duì)LSMOPs提出的第一個(gè)大規(guī)模多目標(biāo)優(yōu)化測(cè)試集,含有9個(gè)測(cè)試函數(shù)。LSMOP測(cè)試集不但具有復(fù)雜的決策變量關(guān)聯(lián)性,還有決策變量分組的不均勻性以及適應(yīng)度函數(shù)地形的復(fù)雜性,這些都增加了其求解難度。

3.2 性能指標(biāo)

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

(7)

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

HV定義為種群中的點(diǎn)與參考點(diǎn)集中的點(diǎn)所圍成的區(qū)域的超體積,但HV中的參考點(diǎn)集R是遠(yuǎn)離PF的一個(gè)或多個(gè)參考點(diǎn),而不是處于PF上的一個(gè)或多個(gè)隨機(jī)采樣點(diǎn)，計(jì)算公式如下:

HV(,)=((,))

(8)

式中：表示勒貝格測(cè)度,即

(9)

3.3 參數(shù)設(shè)置

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

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

表1給出了NAS-MOEA和MOEA/DVA,LMEA在UF和LSMOP上20次運(yùn)行后得到的IGD和平均運(yùn)行時(shí)間統(tǒng)計(jì)結(jié)果。表2給出了NAS-MOEA、MOEA/DVA和LMEA在UF和LSMOP上20次運(yùn)行后得到的HV統(tǒng)計(jì)結(jié)果。在LSMOP測(cè)試集的9個(gè)測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果由兩行數(shù)據(jù)構(gòu)成,分別代表目標(biāo)數(shù)為3時(shí),維數(shù)為300,1 000維下的優(yōu)化結(jié)果。在UF測(cè)試集上,其中UF1-7測(cè)試函數(shù)的目標(biāo)數(shù)均設(shè)置為2,在UF8-10上設(shè)置為3,3行數(shù)據(jù)分別表示維數(shù)為100,300,1 000維下的優(yōu)化結(jié)果。

表1 3種算法在UF和LSMOP上的IGD和平均運(yùn)行時(shí)間結(jié)果

續(xù)表1

表2 3種算法在UF和LSMOP上的HV結(jié)果

續(xù)表2

實(shí)驗(yàn)記錄IGD和HV指標(biāo)的平均值,其中,加粗項(xiàng)為同一測(cè)試函數(shù)中獲得的最優(yōu)值。還采用了顯著性水平為0.05的Wilcoxon秩和檢驗(yàn)對(duì)結(jié)果進(jìn)行分析,符號(hào)“+”“-”和“≈”分別表示對(duì)比算法的性能顯著優(yōu)于、顯著差于或統(tǒng)計(jì)意義上相似于所提出的算法。

3.4.1 參數(shù)敏感性分析

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

表3給出了NAS-MOEA在不同參數(shù)的3目標(biāo)300個(gè)決策變量的LSMOP上20次運(yùn)行的IGD結(jié)果。從表3中可以看出,NAS-MOEA提出的基于差分進(jìn)化鄰域自適應(yīng)的算法對(duì)參數(shù),和的不同組合具有很強(qiáng)的魯棒性,在=10,=1,=09下得到的結(jié)果最優(yōu),在9個(gè)測(cè)試函數(shù)中有3個(gè)結(jié)果最優(yōu),有3個(gè)次優(yōu)。故將=10,=1,=0.作為NAS-MOEA的首選參數(shù)設(shè)置。

表3 NAS-MOEA在不同參數(shù)的3目標(biāo)300個(gè)決策變量的LSMOP上的IGD結(jié)果

3.4.2 100維問(wèn)題上的實(shí)驗(yàn)結(jié)果

在這一部分,將NAS-MOEA算法用于具有100維決策變量的測(cè)試函數(shù)上,使用UF1～UF10問(wèn)題。實(shí)驗(yàn)結(jié)果表明,NAS-MOEA在UF3～UF7、UF10等問(wèn)題上取得了較好的效果,而MOEA/DVA在UF1、UF2、UF8問(wèn)題上優(yōu)化效果最好,對(duì)于UF9來(lái)說(shuō),LMEA的優(yōu)化效果優(yōu)于NAS-MOEA算法。從算法總體運(yùn)行時(shí)間上看,NAS-MOEA要稍高于LMEA和MOEA/DVA。

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

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

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

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

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

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

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

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

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

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

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

3.4.3 300維問(wèn)題上的實(shí)驗(yàn)結(jié)果

統(tǒng)計(jì)結(jié)果表明,NAS-MOEA在LSMOP1～LSMOP9、UF3～UF7、UF9和UF10等絕大多數(shù)問(wèn)題上的性能都優(yōu)于MOEA/DVA和LMEA,MOEA/DVA在UF1和UF2上依舊以微弱的差距優(yōu)于NAS-MOEA,在UF8上LMEA優(yōu)于MOEA/DVA和NAS-MOEA。總體來(lái)看,NAS-MOEA對(duì)于三目標(biāo)問(wèn)題的求解優(yōu)勢(shì)更為顯著,在給出的所有三目標(biāo)測(cè)試函數(shù)上的IGD和HV結(jié)果均優(yōu)于對(duì)比算法。原因是NAS-MOEA采用了分治策略,將一個(gè)復(fù)雜的LSMOPs轉(zhuǎn)化為了多個(gè)簡(jiǎn)單的子多目標(biāo)優(yōu)化問(wèn)題,減小了問(wèn)題的規(guī)模,加快了算法的執(zhí)行速度,并對(duì)其進(jìn)行交替優(yōu)化,通過(guò)交替進(jìn)化收斂性變量和多樣性變量,平衡了算法的收斂性和多樣性。

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

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

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

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

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

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

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

NAS-MOEA獲得的PF優(yōu)于其他算法的結(jié)果,對(duì)UF3和LSMOP4而言,MOEA/DVA得到的解集較為均勻,這是因?yàn)槠淠苷_地將決策變量分組,故在此問(wèn)題上性能較好。NAS-MOEA也可以正確地將這些問(wèn)題中的決策變量分組,故也能在這些問(wèn)題上得到最好或與MOEA/DVA相當(dāng)?shù)慕Y(jié)果。NAS-MOEA在UF8上的性能與LMEA相當(dāng),但是在解集的分布性上優(yōu)于LMEA,這是因?yàn)镹AS-MOEA采用交替進(jìn)化策略,平衡了進(jìn)化種群的收斂性和多樣性的沖突。NAS-MOEA在UF6、LSMOP8、LSMOP9上性能要優(yōu)于LMEA和MOEA/DVA,原因是NAS-MOEA采用主成分分析降噪和差分進(jìn)化的鄰域自適應(yīng)更新策略,兩種策略相結(jié)合使NAS-MOEA在進(jìn)化過(guò)程中更高效的進(jìn)化種群,這對(duì)種群收斂性有積極作用。因此本實(shí)驗(yàn)可以驗(yàn)證NAS-MOEA在大規(guī)模決策變量問(wèn)題上的有效性,其收斂能力和多樣性能力更優(yōu)。

3.4.4 1 000維問(wèn)題上的實(shí)驗(yàn)結(jié)果

在1 000維的測(cè)試函數(shù)上,在LSMOP系列和UF系列共19個(gè)測(cè)試函數(shù)上進(jìn)行實(shí)驗(yàn),IGD結(jié)果表明,NAS-MOEA在其中的17個(gè)測(cè)試函數(shù)上的性能都優(yōu)于MOEA/DVA和LMEA,在UF8上NAS-MOEA表現(xiàn)雖不如LMEA,但與MOEA/DVA相比仍有優(yōu)勢(shì),MOEA/DVA在UF9上表現(xiàn)更優(yōu)。HV結(jié)果表明,NAS-MOEA在其中的14個(gè)測(cè)試函數(shù)上的性能都優(yōu)于對(duì)比算法,NAS-MOEA和MOEA/DVA在UF1～UF3上表現(xiàn)相似,MOEA/DVA略?xún)?yōu)于NAS-MOEA,兩算法均優(yōu)于LMEA。從算法總體運(yùn)行時(shí)間上看,NAS-MOEA在LSMOP7上運(yùn)行時(shí)間小于MOEA/DVA,在全部測(cè)試函數(shù)上總體運(yùn)行時(shí)間均小于LMEA。

可以看出,隨著決策變量的增加,NAS-MOEA的優(yōu)勢(shì)逐漸顯現(xiàn)出來(lái),這主要是因?yàn)椴罘诌M(jìn)化的鄰域自適應(yīng)更新策略隨著決策變量的增加顯示出了其優(yōu)越性。收斂性變量的鄰域自適應(yīng)更新是收斂性變量的優(yōu)化是進(jìn)化過(guò)程中最重要的環(huán)節(jié)之一,在收斂性變量差分進(jìn)化的過(guò)程中,從合適的鄰域中選取父代有助于更快地找到非支配前沿,在進(jìn)化過(guò)程中不斷更新鄰域,會(huì)加快種群收斂性進(jìn)化的速度,從而更快更好地找到PF。

3.4.5 算子有效性的實(shí)驗(yàn)驗(yàn)證

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

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

表4 5種算法在UF和LSMOP上算子有效性驗(yàn)證的IGD結(jié)果

續(xù)表4

表5 NAS-MOEA和NAS-PCA在3目標(biāo)3 000個(gè)決策變量的LSMOP上的運(yùn)行時(shí)間結(jié)果

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

在與NAS-DVA算子的比較中可以驗(yàn)證決策變量分析算子的有效性,通過(guò)對(duì)混合變量的準(zhǔn)確劃分,使算法在后續(xù)進(jìn)化過(guò)程中對(duì)不同種類(lèi)變量采用不同進(jìn)化方式的策略得以實(shí)現(xiàn)。在與NAS-EVO的比較中,交替進(jìn)化策略的去除導(dǎo)致算法的尋優(yōu)效率減慢,導(dǎo)致NAS-EVO在大多數(shù)測(cè)試函數(shù)上表現(xiàn)都比較差。因此可以看出,交替進(jìn)化策略對(duì)進(jìn)化種群收斂能力和多樣性尋優(yōu)能力有影響。在與NAS-NAS的對(duì)比可以看出,差分進(jìn)化的鄰域的自適應(yīng)更新策略避免了鄰域變化對(duì)種群的收斂性進(jìn)化的不利影響,加快了收斂性進(jìn)化的速度。

4 結(jié) 論

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