加權(quán)模型的復(fù)雜網(wǎng)絡(luò)的多目標魯棒性優(yōu)化

聶君鳳, 于卓然, 李均利

(四川師范大學(xué) 計算機科學(xué)學(xué)院, 四川 成都 610101)

復(fù)雜網(wǎng)絡(luò)是近幾十年來在網(wǎng)絡(luò)科學(xué)界中的一個熱門學(xué)科,比如互聯(lián)網(wǎng)、交通運輸網(wǎng)絡(luò)和人際關(guān)系等研究領(lǐng)域[1].常見的網(wǎng)絡(luò)模型有隨機網(wǎng)絡(luò)(erdos-renyi networks,ER)[2]、小世界網(wǎng)絡(luò)(small-world networks,SW)[3]、無標度網(wǎng)絡(luò)(scale-free networks,SF)[4]和隨機三角形網(wǎng)絡(luò)(random-triangle networks,RT)[5].文獻[6]中提到,網(wǎng)絡(luò)的魯棒性可以看成是一個優(yōu)化問題.由于網(wǎng)絡(luò)暴露在外,會受到各種各樣的攻擊,比如隨機攻擊、蓄意攻擊.隨機攻擊是隨機移除某一個節(jié)點或者某一條連邊;蓄意攻擊會針對重要的節(jié)點或者連邊進行攻擊,如介數(shù)攻擊、度攻擊[7]等.目前已有成熟的單目標進化算法來優(yōu)化網(wǎng)絡(luò)受到節(jié)點或者連邊攻擊下的魯棒性,但是在現(xiàn)實社會中,網(wǎng)絡(luò)往往會同時受到節(jié)點和連邊的攻擊.

由于復(fù)雜網(wǎng)絡(luò)暴露在外,可能會受到自然災(zāi)害、故意攻擊、機械故障和級聯(lián)故障等,如2008年1月25日,中國一條高壓輸電線路因下雪斷裂,落在另一條線路上而造成大面積停電[8];網(wǎng)絡(luò)中一個節(jié)點出故障可能會引發(fā)大面積故障,甚至整個網(wǎng)絡(luò)崩潰,如2003年發(fā)生的美國歷史上最大的停電事故[9],擁塞導(dǎo)致的互聯(lián)網(wǎng)崩潰[10].這些故障都迫使研究人員找到抗擊能力更好的網(wǎng)絡(luò).

在文獻[11]中以魯棒性作為優(yōu)化目標,使用多目標進化算法增強網(wǎng)絡(luò)的魯棒性,以抵御2種攻擊.拓撲重連是增強網(wǎng)絡(luò)魯棒性常用的策略,文獻[12]對幾種拓撲重連方式進行了比較和分析,證明了在實驗過程中對網(wǎng)絡(luò)進行重連邊之后能得到更有效的魯棒性.在優(yōu)化復(fù)雜網(wǎng)絡(luò)魯棒性過程中,對網(wǎng)絡(luò)結(jié)構(gòu)進行重連邊之后能得到更多廣泛的網(wǎng)絡(luò)結(jié)構(gòu),但在重連邊的過程中沒有改變節(jié)點間的度分布情況;增強網(wǎng)絡(luò)的魯棒性還應(yīng)該考慮運行的環(huán)境及受到的干擾.復(fù)雜網(wǎng)絡(luò)對不確定性、干擾和攻擊都具有魯棒性,也就是說,復(fù)雜網(wǎng)絡(luò)在受到攻擊的情況下,網(wǎng)絡(luò)都能夠正常運行,不受外界的干擾,即魯棒性越好,對應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)抗干擾力也就越強.

文獻[13]中提到網(wǎng)絡(luò)系統(tǒng)可能會受到各種破壞性的攻擊,因此針對復(fù)雜網(wǎng)絡(luò)的單目標魯棒性優(yōu)化算法不能很好地解決實際應(yīng)用中的問題.研究人員同時考慮多種攻擊下的魯棒性,但是不同魯棒性之間可能會存在沖突[14].后來,大量的研究人員針對多種攻擊下得到的魯棒性進行研究,他們越來越關(guān)注同時優(yōu)化多個魯棒性來構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu),具有良好抗擊能力的網(wǎng)絡(luò)有利于實際網(wǎng)絡(luò)系統(tǒng)的設(shè)計和優(yōu)化.文獻[15]中設(shè)計了一個多目標進化算法,同時增強SF網(wǎng)絡(luò)對基于節(jié)點和連邊攻擊下的魯棒性.與單目標算法相比,多目標算法具有更顯著的特點,每個非支配解都可以看作是2個目標之間加權(quán)后的結(jié)果.

在文獻[8]中提到用多目標進化算法來優(yōu)化網(wǎng)絡(luò)魯棒性的過程中計算成本太大.為了解決計算成本問題,已有研究在優(yōu)化過程中使用卷積神經(jīng)網(wǎng)絡(luò)來評估網(wǎng)絡(luò)魯棒性[16-18],但需要大量的數(shù)據(jù)集;也有大量的研究在優(yōu)化過程中采用代理模型來評估復(fù)雜網(wǎng)絡(luò)魯棒性.代理模型可以是插值函數(shù),也可以是非插值函數(shù),非插值模型常用的有多項式回歸[19]和支持向量機[20],插值模型常用的有徑向基函數(shù)(radial basis function,RBF)網(wǎng)絡(luò)、最小二乘法(least square,LS)函數(shù)、反距離加權(quán)(inverse distance weighting,IDW)插值函數(shù)[11]和克里金插值的函數(shù)[21].如何為一個復(fù)雜網(wǎng)絡(luò)選擇合適的代理模型來評估復(fù)雜網(wǎng)絡(luò)的魯棒性,目前仍沒有明確的判別準則.現(xiàn)在大部分研究是同時選擇幾種代理模型,然后使用每種代理模型對網(wǎng)絡(luò)進行評估,再對幾個評估值求平均,將其作為該網(wǎng)絡(luò)的評估值.

在傳統(tǒng)的代理模型組合基礎(chǔ)上,本文提出了一種基于加權(quán)模型的復(fù)雜網(wǎng)絡(luò)多目標魯棒性優(yōu)化(three surrogate models weight average,TSWA)方法,使用dempster-shafer theory(D-S)[22]分別給幾個代理模型分配權(quán)值,并通過不同代理模型評估方法對合成網(wǎng)絡(luò)多目標魯棒性的優(yōu)化結(jié)果驗證了該方法的有效性.

1 多目標魯棒性優(yōu)化

對于一個網(wǎng)絡(luò)拓撲圖,記錄N個節(jié)點與M條邊,并保存網(wǎng)絡(luò)間的鄰接矩陣(有連邊記為1,反之記為0).圖1中給出了網(wǎng)絡(luò)結(jié)構(gòu)圖表示與鄰接矩陣之間的關(guān)系.本文研究攻擊網(wǎng)絡(luò)中節(jié)點和連邊情況下網(wǎng)絡(luò)連通魯棒性值,也就是網(wǎng)絡(luò)在減少節(jié)點或者連邊之后,該網(wǎng)絡(luò)能維持正常運行的能力.通過攻擊節(jié)點后的變化來評估網(wǎng)絡(luò)的連通魯棒性,記為

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)及其對應(yīng)的鄰接矩陣

(1)

其中,s(j)是攻擊j個節(jié)點后,網(wǎng)絡(luò)剩余的最大連通分量的節(jié)點數(shù)所占剩余節(jié)點數(shù)的比例.在這里對節(jié)點采用的攻擊方式是度攻擊,即每次攻擊度數(shù)最大的節(jié)點.1/N用作標準化因子,使不同規(guī)模的網(wǎng)絡(luò)具有可比性.在網(wǎng)絡(luò)的連通魯棒性中,R值越大表明網(wǎng)絡(luò)的魯棒性越好[23].

另一種評估方式是基于連邊的攻擊,在這種攻擊下采用的方式是介數(shù)攻擊,該攻擊方式是集中于攻擊全局中的最短路徑,網(wǎng)絡(luò)受到攻擊后的魯棒性記為

(2)

其中,s(k)是攻擊k條邊后,網(wǎng)絡(luò)剩余的最大連通分量的連邊數(shù)所占剩余連邊數(shù)的比例,1/M是標準化因子,與R類似,RL給出了網(wǎng)絡(luò)對基于連邊攻擊下的魯棒性.

本文將這2種情況下得到的魯棒性問題構(gòu)建成一個多目標優(yōu)化問題.文獻[24]設(shè)計了一種基于啟發(fā)式的算法,以成功地增強由R引導(dǎo)的網(wǎng)絡(luò)魯棒性.同時,文獻[25]提到,單獨增強R不能保證RL也隨著增強,這2種目標存在沖突.由于很難同時優(yōu)化R和RL,所以出現(xiàn)了大量的多目標進化算法來優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu).

2 代理模型及評估方法

代理模型輔助的進化算法(surrogate-assisted evolutionary algorithm,SAEA)[26]不管是在單目標還是多目標問題上都廣泛應(yīng)用.代理模型的選擇、參數(shù)的確定都是SAEA中的關(guān)鍵問題.

代理模型以較低的計算成本來估計網(wǎng)絡(luò)的魯棒性,并使用評估得到的連通魯棒性來引導(dǎo)優(yōu)化過程.文獻[27]為了解決數(shù)據(jù)維度高和數(shù)據(jù)稀疏的問題,采用了DeepWalk算法來把網(wǎng)絡(luò)節(jié)點映射到低維空間中.為了使高維空間的結(jié)構(gòu)數(shù)據(jù),降維到低緯度空間,采用圖嵌入SDNE[28]方法來提升低維空間節(jié)點相似性,降低嵌入損失,使得數(shù)據(jù)易于處理.此外,由于異構(gòu)輸入有助于提高模型訓(xùn)練的多樣性[20],在原始數(shù)據(jù)下采用了多種特征提取技術(shù)作為代理模型輸入的特征.首先采用的是主成分分析(PCA),它可以以較低的計算成本來提取主要信息,把數(shù)據(jù)降維到一維;還采用了K-means聚類[29],此方法就是計算樣本間的距離,把相近的樣本放到一個集合中.文獻[6]把原始數(shù)據(jù)、PCA降維后的數(shù)據(jù)和聚類后的數(shù)據(jù)用來訓(xùn)練代理模型.在不同特征屬性下分別采用RBF、LS和IDW等3種代理模型,然后取3種模型下預(yù)測結(jié)果的平均值.3種代理模型的輸入數(shù)據(jù)和訓(xùn)練過程如圖2所示.

圖2 代理模型結(jié)構(gòu)

圖2中S是選擇的代理模型,1是選擇RBF模型來進行訓(xùn)練,2是選擇LS模型來進行訓(xùn)練,3是選擇IDW模型來進行訓(xùn)練,X表示降維后的一個二維向量,n是輸入層單元數(shù),cji是網(wǎng)絡(luò)中心參數(shù)的初始值,Cj是隱含層第j個神經(jīng)元的中心向量,dj表示寬度向量,影響著輸入信息的作用范圍,g是高斯函數(shù),Y表示輸出向量的預(yù)測值,λ是反距離加權(quán)方法中的權(quán)值,Z(X)是預(yù)測的未知點.

從給定網(wǎng)絡(luò)數(shù)據(jù),首先計算網(wǎng)絡(luò)的魯棒性度量(R,RL),然后利用SDNE對網(wǎng)絡(luò)進行降維,得到網(wǎng)絡(luò)的二維數(shù)據(jù).隨后,將原始數(shù)據(jù)和2種特征提取技術(shù)作為代理模型訓(xùn)練的異構(gòu)輸入.下面介紹本文所使用的徑向基(RBF)網(wǎng)絡(luò)、最小二乘法(LS)函數(shù)和反距離加權(quán)(IDW)插值函數(shù)3種代理模型.

2.1 徑向基函數(shù)(RBF)網(wǎng)絡(luò)該網(wǎng)絡(luò)中的重要部分是隱藏層中采用徑向基函數(shù),該函數(shù)中的每個插值點都可以構(gòu)建一個徑向距離對稱的基函數(shù),并對其進行線性組合.利用徑向基函數(shù)可以很好地模擬真實函數(shù)的目標值.代理模型定義如下:

(3)

2.2 最小二乘法(LS)函數(shù)依據(jù)最小二乘法原則,利用微分學(xué)中的極值原理,建立標準方程,求解回歸方程的參數(shù).它是為了找到一個與給定點(xi,yi)的距離平方和最小的曲線g(x),模型如下:

(4)

其中,hθ(xi)是數(shù)據(jù)中的多組樣本,yi是假設(shè)擬合函數(shù),g(x)也就是在機器學(xué)習(xí)中常說的損失函數(shù).本文的目的就是得到使損失函數(shù)最小化擬合函數(shù)的模型.

2.3 反距離加權(quán)法(IDW)插值函數(shù)通過歐氏距離來判斷彼此之間的相似度,距離較近的相似度就較高.因此,根據(jù)距離預(yù)測值來評判權(quán)重大小,預(yù)測值小反而權(quán)重大,預(yù)測值大反而權(quán)重小.一般形式如下:

(5)

其中,λi為第i個待插入數(shù)據(jù)點的權(quán)重,xi、yi為第i個已知點的值,n為已知數(shù)據(jù)點個數(shù),λi為已知點對應(yīng)的權(quán)重.權(quán)重計算方式如(6)式所示,權(quán)重一般滿足(7)式.

λ

(6)

(7)

其中,di是已知點與預(yù)測點之間的歐氏距離,權(quán)重是距離的倒數(shù)的函數(shù).

2.4 度量指標目前有大量的度量指標來衡量在進化算法中方法是否有效,本文采用超體積(hyper volume,簡稱HV)來計算不同代理模型下的非支配解與原點之間的體積,根據(jù)HV的大小來判斷方法是否有效,HV越大,方法越好.HV的計算如下:

(8)

其中,?是Lebesgue測度,用來測量體積,S表示非支配解的數(shù)目,Ti表示參考點與解集中第i個非支配解構(gòu)成的超體積.

3 TSWA方法

3.1 代理模型評估方法采用代理模型進行評估的方法一般單獨使用一個代理模型[29],或者同時使用多個代理模型[6,20],然后對其結(jié)果進行求平均.代理模型組合結(jié)構(gòu)如圖3所示,先用SDNE的方法對復(fù)雜網(wǎng)絡(luò)降維,接下來使用PCA、K-means和原始數(shù)據(jù)作為輸入數(shù)據(jù)來訓(xùn)練代理模型,采用多種輸入數(shù)據(jù)是為了獲得更廣泛的數(shù)據(jù),使訓(xùn)練模型更加準確.其中,N是網(wǎng)絡(luò)的個數(shù),G是網(wǎng)絡(luò)結(jié)構(gòu),V是網(wǎng)絡(luò)節(jié)點數(shù).

圖3 代理模型組合結(jié)構(gòu)

3.2 TSWA評估方法在采用代理模型進行評估時,如果使用單一的代理模型會因為代理模型的缺陷或者不足影響復(fù)雜網(wǎng)絡(luò)的連通魯棒性;通過選取多個代理模型的評估結(jié)果的平均值,可能會降低對復(fù)雜網(wǎng)絡(luò)魯棒性評估的準確性.因此,本文采用加權(quán)的方法給幾個代理模型分配不同的權(quán)值,該方法彌補了直接對多個代理模型的評估值求平均而導(dǎo)致準確率降低的缺陷.本文使用D-S理論來分配權(quán)值,它是一種不確定性推理的一般框架,由Dempster[30]在統(tǒng)計推斷的背景下被引入,具有處理不確定性信息的能力,在先驗概率已知的情況下,利用概率論中貝葉斯條件概率來實驗.然而,D-S理論不需要知道先驗概率,就能被用于解決不確定的問題.文中通過給不同的代理模型分配不同的權(quán)值來評估魯棒性進行研究,代理模型在D-S理論下的權(quán)值計算流程如圖4所示.其中,RBF、LS、DW是本文所使用的3種代理模型,CC(correlation coefficients)、RMSE(root mean squared errors)和MAE(maximal absolute errors)分別是評估值與真實值的相關(guān)系數(shù)、均方根誤差和最大絕對值誤差,mass是權(quán)值.每種復(fù)雜網(wǎng)絡(luò)分別訓(xùn)練3種代理模型,然后通過計算評估值與真實值之間的性能得到3個權(quán)值mass.

圖4 D-S下的權(quán)值計算流程

根據(jù)表1中的D-S權(quán)值計算流程,用評估得到的復(fù)雜網(wǎng)絡(luò)魯棒性值與真實值之間的特征屬性來求出每個代理模型的權(quán)重.本文為了研究3種加權(quán)平均的方法與單個使用、3種組合求平均的效果,選用了SF、ER、SW和RT網(wǎng)絡(luò),每種網(wǎng)絡(luò)分別訓(xùn)練3種代理模型,再對復(fù)雜網(wǎng)絡(luò)進行評估.用評估值與真實值之間的相關(guān)系數(shù)、均方根誤差和最大絕對值誤差作為3個性能指標,然后使用D-S理論的計算方式來計算每個代理模型的權(quán)值.

表 1 D-S理論的權(quán)值計算流程

通過使用上面提及的D-S理論來分別對RBF、LS和IDW等3種代理模型賦予不同的權(quán)值,權(quán)值的計算過程如圖3所示,最后復(fù)雜網(wǎng)絡(luò)的評估值是對這3個代理模型加權(quán)求平均后的結(jié)果.3種網(wǎng)絡(luò)在不同代理模型的權(quán)值分配如表2所示,每種網(wǎng)絡(luò)的3個權(quán)值和為1.圖5給出了加權(quán)評估復(fù)雜網(wǎng)絡(luò)魯棒性的結(jié)構(gòu)圖,圖5與圖3的區(qū)別在于是否使用了D-S理論為每個代理模型進行加權(quán)操作,這也是本文所提出的評估分析方法.

表 2 4種網(wǎng)絡(luò)在3種代理模型上的權(quán)值分配

圖5 TSWA結(jié)構(gòu)

先用SDNE的方法對復(fù)雜網(wǎng)絡(luò)降維,然后使用PCA、K-means和原始數(shù)據(jù)作為輸入數(shù)據(jù)來訓(xùn)練代理模型,此操作是為了獲得更廣泛的數(shù)據(jù),使得訓(xùn)練的模型更加準確.對代理模型訓(xùn)練完成之后,用網(wǎng)絡(luò)結(jié)構(gòu)作為數(shù)據(jù)集進行評估,然后用D-S理論計算3種代理模型下得到的評估值與真實值之間的相關(guān)系數(shù)、均方根誤差和最大絕對值誤差作為特征屬性值,然后用D-S理論計算權(quán)值.在使用多目標進化算法過程中將圖5中的w1、w2、w3分別對應(yīng)RBF、LS、IDW進行加權(quán)操作.在本文所使用的TSWA中通過D-S理論得到權(quán)值,然后在評估時給代理模型分配權(quán)值進行評估,評估的公式如下:

(9)

其中,R、D、L分別代表RBF、IDW、LS等3個代理模型,w1、w2、w3是使用D-S理論后的權(quán)值.

4 實驗結(jié)果分析

4.1 實驗設(shè)置本文在4種合成網(wǎng)絡(luò)上進行實驗,分別為隨機網(wǎng)絡(luò)(ER)、無標度網(wǎng)絡(luò)(SF)、小世界網(wǎng)絡(luò)(SW)和隨機三角形網(wǎng)絡(luò)(RT).網(wǎng)絡(luò)節(jié)點數(shù)為300,平均度為4,也就是連邊數(shù)為1 200.此外,在多目標進化算法中交叉率為0.6,變異率為0.5,代理模型更新率為0.4,種群大小為20,迭代次數(shù)為100.

4.2 實驗結(jié)果分析在使用同一種多目標進化算法框架下,單獨采用代理模型RBF、LS和IDW進行實驗.文獻[6]中使用同時訓(xùn)練3種代理模型求平均(SP-RV-MOEANet);本文構(gòu)造一種同時訓(xùn)練3種代理模型加權(quán)求平均TSWA的方法與上述2種方法得到的復(fù)雜網(wǎng)絡(luò)非支配解以及HV值進行比較.

從圖6(a)中可以看出,在單獨使用代理模型的情況下,在優(yōu)化過程中單獨采用IDW代理模型能得到更優(yōu)的復(fù)雜網(wǎng)絡(luò)的非支配解,而SP-RV-MOEANet的非支配解不如單獨使用IDW代理模型下得到的非支配解,但是這些非支配解與TSWA的非支配解相比,后者得到的非支配解更理想.

從圖6(b)中可以看出,在單獨采用3種代理模型下得到的非支配解中,優(yōu)化過程中采用RBF代理模型得到的非支配解更優(yōu).但是RBF下得到的非支配解與SP-RV-MOEANet下得到的非支配解及TSWA方法下得到的非支配解相比,RBF下的復(fù)雜網(wǎng)絡(luò)非支配解的效果不理想,也可以看到RBF的非支配解與SP-RV-MOEANet的非支配解差距不明顯,但是可以明顯地看出TSWA方法下的這條線的非支配解更優(yōu).

在圖6(c)中,SP-RV-MOEANet方法下得到的非支配解和單獨使用LS、IDW的非支配解相吻合.還可以看出,前期SP-RV-MOEANet的非支配解與LS的非支配解更接近,后期與IDW代理模型得到的非支配解更接近,由此說明SP-RV-MOEANet的方法能得到更廣泛準確的非支配解,但是在搜索過程中引入加權(quán)評估后能明顯地看出非支配解結(jié)果更優(yōu).

從圖6(d)中看出,單獨使用代理模型IDW的效果相當不理想.而LS、RBF和SP-RV-MOEANet下的非支配解很接近,有段區(qū)間內(nèi)幾乎不能區(qū)分這幾種結(jié)果,但是可以很明顯地看出使用TSWA方法的非支配解始終比其他幾種非支配解更優(yōu),說明此方法有效.

從4種不同網(wǎng)絡(luò)結(jié)構(gòu)上得到的非支配解可以看出,在優(yōu)化過程中使用代理模型加權(quán)評估能輔助進化算法搜索到連通魯棒性更優(yōu)的復(fù)雜網(wǎng)絡(luò).

從復(fù)雜網(wǎng)絡(luò)的非支配解中也不能完全憑借肉眼看出結(jié)果,下面給出了用HV來評估該方法的性能,該方法是計算所獲得的非支配解集與參考點圍成的目標空間中區(qū)域的體積,HV值越大表明方法性能越好.圖7給出了不同復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)下5種情況的HV值在各代理模型中的變化,分別是單獨使用LS、RBF、IDW代理模型下得到的HV值,3種代理模型結(jié)合求平均得到的HV值(SP-RV-MOEANet)和3種代理模型結(jié)合加權(quán)求平均得到的HV值(TSWA).

從圖7(a)中可以看到,幾個方法下的HV值都在不停上升,證明這些方法對優(yōu)化復(fù)雜網(wǎng)絡(luò)連通魯棒性都有效果.雖然加權(quán)的曲線TSWA的效果一開始增長得不是那么明顯,但是在后期搜索過程中,優(yōu)化效果明顯提升.

從圖7(b)中可以看出,單獨使用代理模型時,RBF得到的HV曲線更突出;但是TSWA曲線和SP-RV-MOEANet曲線相比可以看出后者的曲線效果并不好,反而TSWA得到的HV曲線效果更加突出.

從圖7(c)中可以看出,使用TSWA后的HV曲線前期搜索效果更快,很快就能找到最優(yōu)解,在后期階段,增長趨勢很平緩,不像其他幾個模型的波動情況大,證明在使用加權(quán)后能更快地搜索復(fù)雜網(wǎng)絡(luò)連通魯棒性.

從圖7(d)中可以看出,使用IDW后的結(jié)果相比其他幾條曲線來說,效果不理想,雖然HV值在增加,但增加得不明顯.剩下4條曲線從圖中看出很是接近,可以看出使用TSWA方法下的HV值在LS、RBF和SP-RV-MOEANet曲線的上邊,其優(yōu)化效果更佳.

從4個復(fù)雜網(wǎng)絡(luò)的不同方法下得到的HV值都能表明在多目標優(yōu)化算法中,使用代理模型加權(quán)評估方法得到的HV值效果更好.

表3給出了4種復(fù)雜網(wǎng)絡(luò)在單獨采用代理模型下的優(yōu)化時間,以及SP-RV-MOEANet和TSWA的優(yōu)化時間,同時也給出了在不同情況下的平均HV值,其中最優(yōu)的HV值和耗時最少的加粗表示.

在SF網(wǎng)絡(luò)中,用時最短的是LS代理模型,SP-RV-MOEANet方法的耗時多一點;TSWA的耗時與SP-RV-MOEANet相差甚小.表3中的平均HV值能反映出模型的大致變化情況,并不起決定性作用,因為有些模型在前期表現(xiàn)得并不是很理想,但是后期的搜索結(jié)果會超過其他幾個方法,這樣也會影響平均HV值,但是在優(yōu)化SF網(wǎng)絡(luò)結(jié)構(gòu)中,使用加權(quán)下的平均HV值比其他幾個結(jié)果好.

在ER網(wǎng)絡(luò)中,用時最少的是RBF模型的優(yōu)化時間,用時最多的是加權(quán)后運行的時間,從表3中可以清楚地看出單獨使用一個代理模型的時間確實更短,加權(quán)操作的過程中要花費一定的時間計算D-S理論下的權(quán)值分配,但是使用加權(quán)的方法并沒比3個結(jié)合求平均的方法耗時太多,反而得到的連通魯棒性是所有方法中最好的.

表 3 4種網(wǎng)絡(luò)在不同方法上的運行時間和平均HV值

在SW網(wǎng)絡(luò)中,運行時間較短的是在優(yōu)化過程中采用IDW代理模型,其次是采用RBF,然后是采用LS;同樣SP-RV-MOEANet的優(yōu)化時間和TSWA的時間普遍耗費更多,因為連續(xù)訓(xùn)練3種代理模型耗時較多.在SW網(wǎng)絡(luò)中平均HV值更大的依舊是TSWA的方法.

在RT網(wǎng)絡(luò)中,其實從這個復(fù)雜網(wǎng)絡(luò)優(yōu)化后的非支配解和HV值都可以看出,除了使用IDW方法的效果不是特別理想之外,剩下幾個方法的HV值差距特別小.從運行時間看,IDW的運行時間是其他幾種方法的2倍左右.但是從一系列的實驗依舊可以得出在RT網(wǎng)絡(luò)下,TSWA方法同樣有效.

從表3中可以看出,不同復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)所耗時不同,不同的方法耗時也不相同,而且所消耗的運行時間在可接受的范圍內(nèi),TSWA與SP-RV-MOEANet所耗時間差不多,但TSWA方法下的效果更佳.前面所有的實驗分析都可以證明加權(quán)下的代理模型得到的優(yōu)化結(jié)果更好,也說明本文所采用的方法是可行的,其中加粗數(shù)據(jù)代表是較優(yōu)的.

通過TSWA的方法與采用單一代理模型和SP-RV-MOEANet方法的對比實驗結(jié)果可以表明,在多目標進化算法評估過程中,對多個代理模型進行加權(quán)操作后的結(jié)果更加理想,從圖6中可以看出所有的非支配解中都是R值在變大,RL值在變小,原因就是在多目標優(yōu)化問題中,目標之間存在沖突關(guān)系.在圖8中把在TSWA下的每種網(wǎng)絡(luò)結(jié)構(gòu)的非支配解分離出來單獨展示,可以明確地看出R、RL之間的變化情況.

5 結(jié)束語

本文為了得到能同時抵抗節(jié)點度攻擊和連邊介數(shù)攻擊下連通魯棒性更佳的網(wǎng)絡(luò)結(jié)構(gòu).由于復(fù)雜網(wǎng)絡(luò)多目標魯棒性優(yōu)化計算成本非常大,因此,本文在優(yōu)化過程中采用代理模型來降低優(yōu)化時間.通過用加權(quán)代理模型的方法評估復(fù)雜網(wǎng)絡(luò)連通魯棒性與3種單一代理模型評估方法,以及使用3種代理模型組合平均的評估方法進行比較.從每種方法下得到優(yōu)化后的非支配解與HV的大小都可以表明本文采用的TSWA方法更優(yōu),且所耗時間近似于采用3種代理模型組合平均評估方法的時間.通過本文的實驗表明,在優(yōu)化過程中使用D-S理論為不同的復(fù)雜網(wǎng)絡(luò)選擇合適的代理模型評估方法可以得到連通魯棒性更佳的網(wǎng)絡(luò)結(jié)構(gòu).