代理模型輔助的復雜網絡能控性魯棒性優化方法

聶君鳳,于卓然,李均利

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

0 引 言

復雜網絡是近幾十年來在網絡科學界中的一個熱門學科,其廣泛應用于互聯網、交通運輸網絡、人際關系等研究領域[1].不同的連接方式會產生不同的網絡結構,常見的網絡模型有隨機網絡(Erd?s-Rényi networks,ER)[2],小世界網絡(Small-Word network,SW)[3],無標度網絡(Scale-Free network,SF)[4],隨機三角形網絡(Random Triangle network,RT)[5],隨 機 四 邊 形 網 絡(Random Rectangular network,RR)[6],Q-回路網絡(Q-Snapback network,QS)[7].

目前大多數網絡都會通過重連的方式來重構網絡結構,使得在優化過程中獲得更廣泛的網絡結構[8].由于網絡暴露在外,會受到各種各樣的攻擊,比如隨機攻擊,蓄意攻擊等.隨機攻擊是隨機移除某一個節點或者某一條連邊,蓄意攻擊是針對度大的節點或者重要的連邊,如介數攻擊、度攻擊[9]等攻擊方式.許多研究者采用各種方法來增強復雜網絡魯棒性,鄧等人[10]針對不同類型的網絡尋找出最佳攻擊序列來保護或者增強復雜網絡的魯棒性.王等人[11]對網絡中的一些割點進行研究,研究割點失效對復雜網絡的能控性魯棒性的影響.網絡中的節點或者連邊被攻擊之后,網絡的整體性能會下降,因此如何找到抗擊能力更好的網絡結構成為了研究熱點.

當復雜網絡受到節點攻擊之后,增強復雜網絡的魯棒性問題可以看成是一個單目標優化問題[12].為了尋找性能更優的網絡結構,大量的研究方法被提出.Liu等人[13]在網絡優化過程中分析采用重連邊策略對網絡魯棒性的影響.Wang等人[14]采用遺傳算法來優化大規模下的復雜網絡在節點受到攻擊后的魯棒性.Zhou等[15]人提出了一個模因算法來解決網絡結構尋優問題,通過選擇、交叉和變異等進化算子,結合利用結構信息的局部搜索過程,該算法可以取得較好的優化結果,同時也被應用于解決隨機、惡意攻擊[16]下出現的情況以及應對級聯破壞的情況.

目前已經有大量的進化算法被用來解決實際中的優化問題.但是,在解決高維數據問題或者是尋找抗擊能力更好的大規模復雜網絡結構過程中的計算成本非常大.在文獻[17]中提到代理模型可以輔助進化算法來優化問題從而降低搜索過程中的計算成本.代理模型可以是插值函數,也可以是非插值函數,其中非插值模型常用的有多項式回歸[18]和支持向量機[19],插值模型常用的有徑向基函數(Radial Basis Function,RBF)網絡、最小二乘法(Least Square,LS)函數、反距離加權插值函數(Inverse Distance Weighting,IDW)[20]和克里金插值函數(Kriging)[21],以及上述代理模型的組合.如何為一個復雜網絡選擇合適的代理模型來評估能控性魯棒性,目前仍沒有明確的判別準則.本文選擇常用的RBF、LS、IDW、Kriging四種模型來評估復雜網絡的能控性魯棒性.為了解決如何選擇代理模型問題,本文使用Dempster-Shafer theory(D-S理論)[22]來選擇代理模型的不同組合方式.該理論是一種數學證據理論,它可以對多種不確定因素進行融合分析,根據幾個特征值來計算權值,將權值大小作為選擇代理模型的判別準則,利用該準則為不同類型的復雜網絡選擇出合適的代理模型.

本文為了找到大規模復雜網絡受到節點攻擊下能力更好的網絡結構,在優化過程中使用代理模型輔助進化算法搜索更優的網絡結構.針對上述問題本文進行了兩組研究,分別是在進化搜索過程中通過D-S理論靜態選擇代理模型組合下的幾種方法之間的能控性魯棒性的比較和自適應選擇代理模型組合下的幾種方法之間的能控性魯棒性的比較.通過在SF、ER、SW、RR、QS和RT這6種合成網絡上進行仿真,驗證了本文所采用方法的有效性.

1 復雜網絡能控性魯棒性優化

對于一個網絡拓撲圖,其中有N個節點和M條邊,并保存網絡的鄰接矩陣(有連邊記為1,反之記為0).本文研究攻擊網絡節點下的網絡能控性魯棒性,復雜網絡能控性描述的是當前網絡的能控性狀態;而能控性魯棒性則是描述網絡在受到攻擊后,復雜網絡能控性的變化情況[23].復雜網絡的能控性是由網絡中驅動節點密度(nD)來量化表示,驅動節點密度計算如公式(1)所示:

(1)

目前常用的能控性計算方式有結構能控性[24]和精準能控性[25],其中結構能控性是根據最大匹配來計算驅動節點個數,適用范圍比較窄,耗時比較多;本文采用精準能控性,它不僅適用于所有稀疏網絡,也適用于有向網絡和無向網絡.所需驅動節點個數可由式(2)計算得到:

ND=max{1,N-rank(A)}

(2)

其中A是網絡的鄰接矩陣,如果矩陣A滿秩,需要nD=1個驅動節點,否則需要N-rank(A)個驅動節點.

能控性魯棒性表示網絡在受到節點攻擊之后,余下網絡的能控性變化情況.這些值是一組能控性值的序列,在節點攻擊下的能控性曲線定義如公式(3):

(3)

其中ND(i)是當i個節點遭受攻擊后,網絡中所需的驅動節點數;N-i為i個節點遭受攻擊后網絡剩余的節點數,網絡規模減少1.

公式(3)是每攻擊一次之后的能控性,而整個網絡的能控性魯棒性可以將上述值求平均得到,如公式(4)所示:

(4)

較小的R表示網絡在受到節點攻擊下的能控性魯棒性更優,這個方式和常用的連通性魯棒性[26]的度量方式類似.

2 代理模型

2.1 徑向基函數(RBF)網絡

該模型的核心是使用徑向基函數,函數中的每個插值點都可以構建一個徑向距離對稱的基函數,并對其進行線性組合.利用徑向基函數可以很好地模擬真實函數的目標值.代理模型如公式(5)所示:

(5)

其中‖.‖表示歐幾里得范數,τ1,τ2,…,τn是權值系數,φ是徑向基函數,以輸入空間的點x與中心點xc之間的歐式距離為該函數的自變量.

2.2 最小二乘法(LS)函數

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

(6)

hθ(xi)就是我們的多組樣本,yi就是我們的假設擬合函數.g(x)也就是在機器學習中常說的損失函數,我們的目的就是得到使損失函數最小化擬合函數的模型.

2.3 反距離加權法(IDW)

反距離加權插值法通過歐氏距離來判斷彼此之間的相似度,距離較近的相似度就較高.因此根據距離預測值來評判權重大小,預測值小反而權重大,預測值大反而權重小.一般形式如公式(7)所示:

(7)

其中,λi為第i個待插入數據點的權重;xi,yi為第i個已知點的值;n為已知數據點個數;λi為已知點對應的權重.權重計算方式如公式(8)所示,權重一般滿足公式(9).

(8)

(9)

其中di是已知點與預測點之間的歐氏距離,權重是距離的倒數的函數.

2.4 克里金插值函數(Kriging)

它用協方差函數來對隨機過程進行空間建模和插值.其實質上是利用變量來構造一個函數,從而對未知數據進行無偏、最優估計.Kriging模型由兩部分構成,第1部分是反映數據的一個簡單模型,第2部分是隨機模型,用于測量簡單模型與真實函數之間的偏差.Kriging代理模型如公式(10)所示:

(10)

3 代理模型輔助的復雜網絡魯棒性優化

本文采用一些計算廉價的代理模型來代替復雜網絡能控性魯棒性的評估,但是代理模型的選擇以及如何組合才能得到更優的能控性魯棒性值得研究.本文在D-S理論下選擇合適的代理模型,以輔助進化算法的復雜網絡魯棒性優化(Surrogate-assisted evolutionary algorithm of robust optimization of complex networks,SAEA_ROnet).本文在SAEA_ROnet算法框架下對選擇的一種代理模型,兩種代理模型、3種代理模型,不使用代理模型與文獻[14]中的GE_SU_EAnet所用的3種代理模型組合得到的能控性魯棒性比較.

3.1 SAEA_ROnet算法流程

3.1.1 SAEA_ROnet算法的偽代碼

SAEA_ROnet算法的偽代碼如算法1所示,分為3個部分,第1部分是初始化網絡產生種群,并且求出這些復雜網絡的能控性魯棒性.第2部分初始化代理模型,使用種群中得到的能控性魯棒性分別訓練代理模型,然后使用D-S理論選擇出代理模型對復雜網絡的預測值與真實值最接近的模型用于輔助進化算法來搜索能控性魯棒性更優的網絡結構.第3部分進化搜索,代理模型輔助進化算法中的交叉、變異和選擇得出能控性魯棒性更優的網絡結構,直到滿足停止條件,即達到最大迭代次數.其中在變異操作中要保證整個網絡的節點度不發生改變,在當前網絡中變異操作是隨機選擇兩條邊eij和ekl,先添加eil和ekj,然后再刪除eij和ekl.重連邊方法如圖1所示.

圖1 網絡的重連邊方法Fig.1 Reconnection method of network

在算法 1 中初始條件給出網絡結構,迭代次數,最后輸出每一代中的最優解.

算法1.SAEA_ROnet偽代碼

輸入:初始化網絡;
迭代次數t=0;
最大迭代次數MaxGen;

輸出:能控性魯棒性及對應的網絡結構;

Step 1.計算初始復雜網絡的能控性魯棒性;

Step 2.訓練代理模型;

whilet

Step 3.在種群中選擇2個能控性魯棒性小的網絡進行交叉操作產生Pt+1;

Step 4.在Pt+1進行重連邊變異操作并使用代理模型預測重連邊后網絡的魯棒性;

Step 5.在Pt+1進行局部搜索;

Step 6.選擇得到的最優解進入下一代的父代中;

Step 7.if random.random()< 0.4:

Step 8.更新代理模型的訓練;

Step 9.t=t+1;

end while

Step 10.輸出能控性魯棒性及對應的網絡結構;

3.1.2 SAEA_ROnet算法流程圖(圖2)

圖2 SAEA_ROnet算法流程圖Fig.2 SAEA_ROnetalgorithm flow chart

3.2 代理模型選擇

3.2.1 單一代理模型選擇

如文獻[27]描述的一樣,一個代理模型不一定適用于評估所有類型的復雜網絡,可能同一個代理模型在一個復雜網絡中能輔助進化算法找到能控性魯棒性更優的網絡結構,但卻在另一個復雜網絡上不能輔助進化算法找到能控性魯棒性更優的網絡結構.如果不知道當前復雜網絡應該選擇哪種代理模型,那么就要針對復雜網絡進行大量的實驗,然后從優化結果分析得出最適合當前復雜網絡的代理模型.本文針對不同類型的復雜網絡選擇合適的代理模型進行研究,代理模型采用RBF,LS,IDW和Kriging.文章中用D-S理論根據這4種代理模型的預測值的權重大小來選擇最合適的代理模型.算法2給出了用D-S理論來計算權值的偽代碼.

算法2.D-S 理論的權值計算偽代碼

輸入:代理模型的個數N;
復雜網絡的規模G;

輸出:每種網絡的權值;

Step 1.隨機初始化復雜網絡,評估代理模型的權值,迭代器t=0;

Step 2.計算這些初始化網絡的能控性魯棒性;

whilet

Step 3.在種群規模下使用已得到的能控性魯棒性來訓練代理模型;

Step 4.用已經訓練完成的代理模型來預測復雜網絡的能控性魯棒性;

Step 6.在上一步中已經計算了幾個特征屬性值進行歸一化,在這幾個特征屬性值下使用DS理論來計算出權值;

Step 7.t=t+1;

end while

根據算法2中的D-S理論權值計算,用復雜網絡魯棒性值與對應真實值求出每個代理模型的權重.為了研究如何為一種復雜網絡選擇合適的代理模型來輔助進化算法搜索能控性魯棒性更優的網絡結構,選用了SF、ER、SW、RT、RR和QS 6種網絡,每種網絡分別訓練4種代理模型,再進行預測.用預測值與真實值之間的相關系數,均方根誤差和最大絕對誤差作為3個性能指標.6種網絡的模型特征如表1所示;6種網絡的權值如表2所示.其中利用性能指標來計算模型特征如公式(11)所示:

表1 6種網絡的模型特征值Table 1 Model eigenvalues of six networks

表2 6種網絡的權值Table 2 Weights of six networks

(11)

其中i是當前代理模型,N是代理模型的總個數,CC,RMSE,MAE分別對應相關系數,均方根誤差,最大絕對誤差3個性能指標.

從上面幾個網絡分別對應的幾個權值得出,使用D-S理論來對不確定性結果進行分析.單一代理模型直接根據權值大小來選擇,為不同的網絡選擇權值大小排名第一的代理模型.結果如表3所示.

表3 6種網絡的單一代理模型選擇Table 3 Single surrogate model selection for six networks

3.2.2 混合代理模型選擇

如果考慮代理模型的混合問題,那么可以根據每個模型的權值排名來進行選擇.使用D-S理論之后,根據4個權值的排名情況,根據需要選擇排名靠前的幾個代理模型.選擇2種代理模型則從表2中根據權值大小選擇靠前的2種.6種網絡的選擇情況如表4所示.

表4 6種網絡的兩種代理模型選擇Table 4 Selection of two surrogate models for six networks

對于3種代理模型選擇的方法和選擇兩種代理模型選擇的方法一樣,在表2中根據權值從大到小選擇3種模型,6種復雜網絡的選擇情況如表5所示.

表5 6種網絡的3種代理模型選擇Table 5 Selection of three surrogate models for six network

3.2.3 自適應代理模型選擇

在上一節中根據D-S理論選擇出來的代理模型,在優化過程中沒有改變模型的本質,只是更新參數設置.例如:在SF網絡中選擇排名靠前的兩個IDW和RBF模型,那么在程序中就一直使用這兩個,其中也有更新的操作,只不過是更新模型的訓練,沒有重新為更新后的復雜網絡種群再次選擇合適的代理模型.因此此部分的操作是在滿足條件之后,用更新后的復雜網絡重新訓練代理模型.如算法3所示:在自適應代理模型的選擇時,重新用種群對應的復雜網絡來訓練本文所用的4種代理模型,接下來用D-S理論重新計算權值,然后選擇排名靠前的兩種或者3種代理模型并重新分配權值.

算法3.自適應更新幾個代理模型所占的權值

輸入:復雜網絡的規模G;
最大迭代次數MaxGen;
代理模型個數N;

輸出:輸出代理模型及其對應的權值;

Step 1.初始復雜網絡,迭代器t=0;

Step 2.計算這些復雜網絡的真實能控性魯棒性;

Step 3.在初始規模下使用能控性魯棒性來訓練代理模型;

Step 4.用已經訓練完成的代理模型來預測該網絡的能控性魯棒性;

Step 5.計算真實值與預測值之間的相關系數 CC,均方誤差 RMSE 和最大絕對誤差 MAE;

Step 6.在幾個特征屬性值下使用D-S理論來計算出權值;

whilet

Step 7.if random.random()<0.4:

Step 8.利用種群中網絡訓練4種代理模型;

Step 9.采用D-S理論計算流程來分配代理模型的權值;

Step 10.根據權值大小選擇排名前N個代理模型;

Step 11.使用種群中的值重新訓練代理模型;

Step 12.t=t+1 ;

end while

4 實驗結果分析

為驗證本文方法的有效性,在平均度為4的SF、ER、SW、RR、RT和QS 6種合成網絡上進行了仿真.其中參數設置交叉率0.6,變異率0.3,局部搜索概率0.5,迭代次數200,種群大小20.統一采用同一個算法框架,即SAEA_ROnet.將使用在D-S理論下選擇出的單一代理模型、混合代理模型、不使用代理模型與文獻[14]中的GE_SU_EAnet幾種方法輔助進化算法搜索到的復雜網絡的能控性魯棒性進行對比,接下來用得到的結果更優的復雜網絡能控性魯棒性與自適應選擇代理模型輔助進化算法得到的能控性魯棒性進行對比.在優化的過程中始終保證每種網絡的度分布不發生改變,這里以SF復雜網絡和ER復雜網絡為例子,圖3給出了兩種復雜網絡優化前和優化后的度分布情況,圖3(a)是初始網絡SF的度分布情況,圖3(b)是優化后的SF網絡的度分布情況,所以SF復雜網絡優化前后的度分布都是冪律分布;圖3(c)是初始網絡ER的度分布情況,圖3(d)是優化后的ER網絡的度分布情況,所以ER復雜網絡優化前后的度分布都是泊松分布,因此在本質上的網絡結構并沒有發生變化.

圖3 SF和ER網絡的優化前后的網絡結構度分布情況Fig.3 Network structure degree distribution of SF and ER networks before and after optimization

4.1 靜態代理模型選擇結果與分析

靜態代理模型包括上文所說的單一代理模型和混合代理來輔助進化算法搜索能控性魯棒性更優的網絡結構,此部分的結果是單一代理模型,混合代理模型,不使用代理模型與文獻[14]中的GE_SU_EANet幾種方法輔助進化算法得到的能控性魯棒性進行對比.圖4給出6種復雜網絡在不同代理模型混合方法下復雜網絡的能控性魯棒性收斂圖.表6給出了6種網絡在不同方法下搜索得到的能控性魯棒性中最優的解,平均解,耗時情況.

表6 給出了6種網絡在不同方法下搜索到的最優值,平均值以及搜索過程中耗時情況Table 6 Shows the optimal value,average value and time-consuming in the search process of the six networks under different methods

圖4 6種網絡在不同代理模型混合方法上的收斂圖Fig.4 Convergence diagram of six networks on different surrogate models mixture methods

為了方便比較,圖4中的5條收斂曲線均采用SAEA_ROnet算法框架,其中,EA0表示不使用代理模型來輔助進化算法優化復雜網絡的能控性魯棒性的優化結果;GE_SU_EAnet是文獻[14]中采用的3種代理模型來輔助進化算法優化復雜網絡的結果;SAEA_ROnet_one是在D-S理論下選擇的最合適的一個代理模型來輔助進化算法優化復雜網絡的優化結果;SAEA_ROnet_two是在D-S理論下選擇最合適的兩個代理模型來輔助進化算法優化復雜網絡的優化結果;SAEA_ROnet_three是在D-S理論下選擇最合適的3個代理模型來輔助進化算法優化復雜網絡的優化結果.

對6種復雜網絡的能控性魯棒性進行分析,在圖4(a)中可以清楚的看到SAEA_ROnet_three方法下的收斂曲線更好,EA0這個的結果不理想,而SAEA_ROnet_two和GE_SU_EAnet兩條曲線幾乎一致,證明在SF網絡中所選用的IDW和Kriging兩個模型得到的優化結果和GE_SU_EAnet中采用的LS,IDW和RBF的優化效果相差較小,SAEA_ROnet_three中所采用的3種代理模型比GE_SU_EAnet中采用的3種代理模型結果更優;在圖4(b)中,在優化的前期階段就可以明顯的區分5條曲線的收斂情況,從一開始SAEA_ROnet_three方法得到的結果就一直領先,GE_SU_EAnet方法都比SAEA_ROnet_one、SAEA_ROnet_two的效果好,因為它采用的3種代理模型包含了其余兩種方法中采用的代理模型,但它的結果不如SAEA_ROnet_three,因為在此方法下有個代理模型采用的是Kriging.在圖4(c)中,在D-S理論下所選出的一種代理模型、兩種代理模型在GE_SU_EAnet方法下都有使用,所以結果都不如GE_SU_EAnet,而且SAEA_ROnet_three中采用的3種代理模型和GE_SU_EAnet中所用模型一致,因此這兩條的曲線幾乎一致.

在圖4(d)中,可以清晰的區分EA0和SAEA_ROnet_one這兩條曲線,其收斂結果都不太理想.而在其余3條曲線中前期結果相差甚小,特別是在110代到150代幾條曲線幾乎重合,150代之后可以明顯的看到SAEA_ROnet_three曲線效果更好,其次是GE_SU_EAnet;在圖4(e)中可以清晰的區分幾條曲線的收斂效果,在120代左右EA0,SAEA_ROnet_one,SAEA_ROnet_two就已經收斂了,沒有搜索到新的最優解,而其余兩條曲線還在搜索全局最優解,最終SAEA_ROnet_three的收斂效果更好;在圖4(f)中,EA0和SAEA_ROnet_one始終在其余幾條曲線的上方,其余3條曲線在110代之后的結果相差很小,SAEA_ROnet_three方法在120代就已經收斂了,而且結果優于其余幾條收斂曲線.

從表6中的幾組值看出在SF、ER、SW、QS和RR中的最優解,平均值最佳的都是SAEA_ROnet_three方法下得到的能控性魯棒性,耗時最少的是SAEA_ROnet_one方法下得到的能控性魯棒性,最優能控性魯棒性及耗時最小的值已加粗顯示;在RR中的最優解,平均值是SAEA_ROnet_three方法下得到的能控性魯棒性,但是耗時最少的是GE_SU_EAnet;在SF、ER、RT幾種網絡中的SAEA_ROnet_three方法中都采用了Kriging這個代理模型,在優化過程中耗時普遍增大,由此可以證明Kriging可以提升大規模復雜網絡的能控性魯棒性,但是耗時較多.

4.2 自適應代理模型選擇結果與分析

本節的實驗結果是將在靜態選擇代理模型下,每種網絡得到的最優能控性魯棒性與在優化過程中根據D-S理論自適應選擇出合適的代理模型組合下得到的能控性魯棒性進行比較,其中需要說明的是SF、ER、SW、RR、RT和QS 6種網絡在自適應選擇代理模型種數的時候設置為3,6種網絡在靜態下的收斂曲線與優化過程中自適應選擇模型下的收斂曲線如圖5所示,表7給出了靜態選擇模型下得到的更佳的能控性魯棒性與自適應選擇代理模型方法得到能控性魯棒性的最優值,平均值及優化所耗時間.在圖5中SAEA_ROnet_three代表的是在靜態選擇下最佳3種代理模型組合下的能控性魯棒性曲線更好,SAEA_ROnet_Adapt代表的是自適應選擇代理模型下的能控性魯棒性曲線.從圖5中可以很清晰的看到自適應收斂曲線始終在靜態下的代理模型最佳組合下得到的收斂曲線的下方,表明在優化過程中,自適應選擇的代理模型組合下的能控性魯棒性曲線更優,但是所花費的時間比靜態情況下所花費的時間多一點.在SF、ER、SW、RR 4個復雜網絡中,兩條曲線前期階段幾乎一致,150代之后兩條收斂曲線才有明顯的區別;其余兩個復雜網絡,兩條收斂曲線一直都能清晰區別,最優解,平均值以及耗時情況數據已放到表7中.

表7 靜態選擇模型下的最優方法與優化過程中自適應選擇模型的最優值,平均值和運行時間Table 7 Optimal method under static selection models and optimal value,average value and running time of adaptive selection models in optimization process

圖5 靜態選擇模型下的最優方法與優化過程中自適應選擇模型的收斂曲線Fig.5 Optimal method under static selection models and convergence curve of adaptive selection models in optimization process

表7中加粗的數據是最優值或者是耗時比較短,從表中可以看出自適應情況下的最優值,平均值都更優,但是靜態情況下的耗時更短,原因是在優化過程中,不斷的使用D-S來計算每種代理模型的權值,然后選擇出最佳代理模型組合,所以耗時更多.

5 結束語

本文主要研究如何得到復雜網絡在受到節點攻擊下的能控性魯棒性更優的網絡結構,算法分別在SF、ER、SW、RR、RT和QS 6種合成網絡上進行了仿真.為了提升進化算法優化過程中的計算效率,本文通過D-S理論選擇的單一代理模型、混合代理模型、不使用代理模型與不采用D-S理論下代理模型輔助進化算法得到的能控性魯棒性進行比較.實驗表明在D-S理論下根據權值大小選擇出的3種代理模型能夠輔助進化算法搜索到能控性魯棒性更優的網絡結構,但如果選擇了Kriging作為代理模型,優化過程中所耗時間會比其他幾個模型多;自適應更新下的優化結果與靜態選擇下得到的優化結果進行對比,由對比結果可知自適應更新下的結果更優,但是比靜態選擇下要花費更多的時間.

在接下來的工作中,還可對復雜網絡的多目標魯棒性優化進行研究.