杜 欣，吳曉斌+，倪友聰,2，葉 鵬，李 松

1.福建師范大學 軟件學院，福州 350117

2.倫敦大學學院 計算機科學學院，英國 倫敦 WC1E 6BT

3.武漢紡織大學 數(shù)學與計算機學院，武漢 430200

代理模型幫助的SA層性能差分演化優(yōu)化算法*

杜 欣1，吳曉斌1+，倪友聰1,2，葉 鵬3，李 松1

1.福建師范大學 軟件學院，福州 350117

2.倫敦大學學院 計算機科學學院，英國 倫敦 WC1E 6BT

3.武漢紡織大學 數(shù)學與計算機學院，武漢 430200

為了在龐大空間中搜索軟件體系結構（software architecture，SA）層最優(yōu)性能改進方案，當前已涌現(xiàn)出一些以NSGA-II為代表的性能優(yōu)化算法。然而這些算法大多未充分考慮性能改進空間的離散特性和性能評估的高計算代價特點，導致了解質(zhì)量不高和優(yōu)化時間過長的問題。針對這一問題，提出一種代理模型幫助的SA層性能差分演化優(yōu)化算法SMDE4PO（surrogate model assisted differential evolution algorithm for performance optimization）。該算法采用多種交叉和變異策略以增大搜索空間和提高收斂速度，并運用隨機森林作為代理模型以大幅減少實際性能評估的次數(shù)。在4個不同規(guī)模案例上的實驗結果表明：（1）在貢獻度、世代距離和超體積3個指標上SMDE4PO顯著優(yōu)于NSGA-II算法；（2）通過使用隨機森林代理模型，在最好情況下SMDE4PO較NSGA-II算法的運行時間可降低48%。

軟件體系結構；性能優(yōu)化；差分演化；代理模型

1 引言

軟件體系結構（software architecture，SA）在較高抽象層次上描述了構成軟件系統(tǒng)的元素以及元素之間的交互關系[1]?；赟A進行性能分析評估[2]，可以盡早地發(fā)現(xiàn)資源使用率過高，響應時間過長和吞吐量過小等性能問題，并通過相應的設計改進來緩解或消除這些問題，進而可在軟件生命周期的早期達到性能優(yōu)化的目的。然而隨著軟件系統(tǒng)的規(guī)模越來越大，復雜性越來越高，影響性能的因素也隨之增多，使得基于SA的性能改進空間也在不斷增大。

文獻[3]描述了業(yè)務報告系統(tǒng)（business report system，BRS），其初始SA如圖1所示。BRS的初始SA包括server1至server4共4臺硬件服務器和9個組件。每臺服務器的處理器速率（processing rate，PR）都為10.0 GHz。BRS的SA中有處理器速率、組件部署和組件選擇3類不同的可變元素（又稱自由度）。具體的，4臺服務器的PR值可在[5.0,20.0]GHz上變化；而9個組件中的每一個均可部署在4臺服務器中的任意1臺；此外WebServer組件有可替代組件Web-Server2供選擇。因而，BRS的SA共有14個可變元素，且這些元素不同取值都對性能產(chǎn)生復雜的非線性影響。即使每個服務器的PR只考慮取20個可選值，BRS例子中可能的改進方案也將超過839億。如何在龐大的性能改進空間中獲得最優(yōu)SA已成為學術界和工業(yè)界高度關注的研究主題[4]。近年來已涌現(xiàn)出基于規(guī)則和基于元啟發(fā)兩類SA層性能的自動優(yōu)化方法[5]。

基于規(guī)則的方法[6-7]將SA層性能改進知識運用機器可處理的規(guī)則形式予以描述。規(guī)則的條件部分用于診斷性能問題，而動作部分則按一定幅度對可變元素的值進行改進。基于規(guī)則的方法還按照一定的策略組合使用預定義的規(guī)則以搜索最優(yōu)性能改進方案。受制于規(guī)則預定義的改進幅度和所采用的搜索策略，基于規(guī)則的方法往往只能搜索受限的改進空間，常常只能獲取局部最優(yōu)的性能改進方案。而基于元啟發(fā)的方法則直接對SA中可變元素進行編碼以表示出性能改進方案，并進一步設計元啟發(fā)算法搜索最優(yōu)性能改進方案。與規(guī)則方法相比，元啟發(fā)方法可以搜索更大的空間，能夠獲取更優(yōu)的性能改進方案。最近一些元啟發(fā)方法還將性能、硬件成本或其他質(zhì)量屬性作為多個目標，并運用NSGA-II算法進行演化優(yōu)化。然而已有的元啟發(fā)方法大多未充分考慮以下兩個問題：

Fig.1 Schematic diagram of initial software architecture of business reporting system圖1 業(yè)務報告系統(tǒng)的初始軟件體系結構

（1）SA中可變元素不僅有不同的取值類型，如數(shù)值和類屬（category）等，而且還需要滿足一定的取值約束和限制。這將導致性能改進空間呈現(xiàn)高度的非連續(xù)形態(tài)。例如：BRS案例中4臺服務器的PR取實數(shù)類型的值；而每個組件的部署只能取類屬類型的值，即取集合{server1,server2,server3,server4}中的1個元素作為值；對于WebServer組件的取值也是類屬類型。此外，BRS例中PR取值在[5.0,20.0]內(nèi)連續(xù)變化；若將組件部署和組件選擇的類屬類型取值映射到從1開始的整數(shù)集，則它們的取值約束分別為[1,4]和[1,2]。因此，性能改進方案的編碼將呈現(xiàn)實數(shù)和整數(shù)混合編碼的形式。這給優(yōu)化算法搜索全局最優(yōu)解帶來一定的困難。

（2）在演化過程中，通過SA性能評估而獲取性能指標值（如系統(tǒng)響應時間）是一個高代價和耗時長的計算步驟。在2.66 GHz處理器、2 GB內(nèi)存及Win8.1操作系統(tǒng)環(huán)境下，根據(jù)文獻[3]迭代200次共評估性能6 000次的參數(shù)設定，圖2給出了NSGA-II算法的運行時間以及性能評估耗時的對照情況。從圖2中可以看出，將近一半的運行時間要用于SA的性能評估。

Fig.2 Running time of NSGA-II algorithm and consuming time of performance evaluation in BRS case圖2 BRS案例中NSGA-II算法運行時間與性能評估耗時

針對已有的元啟發(fā)方法因未充分考慮性能改進空間的離散特性和性能評估的高計算代價特點，而導致解質(zhì)量不高和優(yōu)化時間過長的問題，本文提出了一種代理模型幫助的SA層性能差分演化優(yōu)化算法。主要貢獻如下：

（1）通過4個不同規(guī)模的案例對多項式回歸（polynomial regression，PRS）、Kriging、徑向基函數(shù)網(wǎng)絡（radial basis function network，RBFN）、支持向量機（support vector machine，SVM）與隨機森林（random forest，RF）等5種常用的預測模型進行實驗對比，實證了RF更加適合用作SA層性能演化優(yōu)化過程中的代理模型。

（2）設計了一種代理模型幫助的SA層性能差分演化優(yōu)化算法SMDE4PO（surrogate model assisted differential evolution algorithm for performance optimization）。該算法采用多種交叉和變異策略，并運用RF作為代理模型預估系統(tǒng)響應時間值，以提高解質(zhì)量，并降低演化時間。

（3）在4個不同規(guī)模的案例上與NSGA-II算法進行實驗對比，結果表明本文SMDE4PO算法在貢獻度、世代距離和超體積3個質(zhì)量指標上顯著優(yōu)于NSGA-II算法。與此同時，在最好情況下SMDE4PO較NSGA-II算法的運行時間可降低48%。

本文組織結構如下：第2章闡述相關工作；第3章描述SA層性能優(yōu)化問題；第4章給出差分演化算法SMDE4PO的具體步驟和總體流程；第5章給出案例研究及實驗結果；第6章總結全文，并給出未來工作。

2 相關工作

下面簡要介紹基于SA層性能評估、基于元啟發(fā)的SA層性能優(yōu)化方法及用于演化算法的代理模型等相關工作。

2.1 SA層性能評估

為了能夠在設計階段基于SA進行軟件性能評估，人們已提出了排隊網(wǎng)（queueing net，QN）[8]、分層排隊網(wǎng)（layered queueing net，LQN）[9]、隨機Petri網(wǎng)[10]、隨機進程代數(shù)[11]和馬爾可夫鏈[12]等性能模型及其分析工具，并在此基礎上，提出了一些SA層性能評估方法[2]。圖3示意了SA層性能評估過程。待建系統(tǒng)的SA經(jīng)過變換器的變換可生成某種性能模型的一個實例，再通過解析分析器對該性能模型進行處理并輸出相應的性能評估報告，最后借助讀取器可從評估報告中獲取待建系統(tǒng)的各項性能指標（如響應時間、吞吐量和資源使用率等），本文僅討論系統(tǒng)響應時間。值得注意的是：在SA層性能優(yōu)化過程中，性能評估是一個計算代價相對較高和耗時相對較長的步驟。

Fig.3 Process of performance evaluation at SAlevel圖3 SA層性能評估過程

2.2 基于元啟發(fā)的SA層性能優(yōu)化方法

針對不同的SA建模語言，并通過設計不同的元啟發(fā)算法，人們已提出了一些基于元啟發(fā)的SA層性能優(yōu)化方法。

（1）基于PCM（Palladio component model）建模語言，Martens[13]和Saed[14]分別運用爬山算法和粒子群算法優(yōu)化系統(tǒng)響應時間。Koziolek等人[15]使用NSGA-II算法優(yōu)化系統(tǒng)的響應時間和硬件成本。Martens等人[16-17]利用NSGA-II算法優(yōu)化系統(tǒng)的性能、可靠性和硬件成本。

（2）基于 East-AADL（architecture analysis and design language）建模語言，Li等人[18]使用NSGA-II算法優(yōu)化系統(tǒng)的數(shù)據(jù)流延遲、處理器使用率和代價。Etemaadi等人[19-22]應用NSGA-II算法優(yōu)化系統(tǒng)的性能、安全性和硬件成本。Walker等人[23]使用NSGA-II算法優(yōu)化系統(tǒng)的性能、可信性和硬件代價。

（3）基于AADL建模語言，Meedeniya[24]和Rahmoun等人[25]運用NSGA-II算法優(yōu)化系統(tǒng)的性能和可靠性。

已有的元啟發(fā)優(yōu)化方法可以對單個性能指標進行優(yōu)化也可以對多個性能指標進行優(yōu)化，甚至還將性能、硬件成本及其他質(zhì)量屬性作為多個目標進行優(yōu)化。在多目標性能的元啟發(fā)優(yōu)化方法中，NSGA-II往往是它們首選的演化優(yōu)化算法。

2.3 用于演化算法的代理模型

演化算法在求解復雜的非線性優(yōu)化問題時，往往需要用很高的代價計算目標函數(shù)的值，常常導致求解效率低和演化時間長的問題。通過構建代理模型預估個體的目標函數(shù)值，減少演化算法調(diào)用目標函數(shù)的次數(shù)，為解決這一問題提供了一種較好的手段。文獻[26-27]指出多項式回歸[28]、Kriging[29]、徑向基函數(shù)網(wǎng)絡[30]、支持向量機[31]和隨機森林[32]等常被用作演化算法[33-36]的代理模型。

演化算法在運行過程中有3種訓練代理模型的控制策略[27]：一是無演化控制策略，僅在初始種群產(chǎn)生之前訓練生成代理模型，并在整個演化過程中一直運用代理模型預估目標函數(shù)值，而不再訓練生成新的代理模型。二是固定的演化控制策略，當預估目標值的個體數(shù)或演化代數(shù)達到預定義的數(shù)目時，重新訓練并生成新的代理模型，并用新模型預估個體的目標函數(shù)值。三是自適應的演化控制策略，當代理模型的性能下降到預設的下界時，重新訓練并生成新的代理模型，并用新模型預估個體的目標函數(shù)值。第一種策略[37]更多適用于低維問題，第二種策略[38-39]因能獲取良好的性能而得到廣泛應用，第三種策略[40]常由于控制過程的復雜性而較少在實際中使用。

3 SA層性能優(yōu)化問題的描述

下面以系統(tǒng)響應時間和硬件成本為目標，給出SA層性能優(yōu)化問題的描述。

定義1定義rest(SA)和cost(SA)分別表示根據(jù)軟件體系結構SA進行性能和成本評估，而獲取的系統(tǒng)響應時間和硬件成本的值。

rest(SA)的計算需要對SA進行性能模型的變換、解析和分析，因而計算代價相對較高，計算時間相對較長。本文采用文獻[3,15]的方法計算cost(SA)，只需要根據(jù)SA中各硬件服務器的處理速率PR值進行計算。

定義2若SA中有D個可變元素，且每個元素可以取一定范圍內(nèi)變化的實數(shù)或整數(shù)值，則SA層性能優(yōu)化問題的解X可表示為滿足式（1）的D維向量(x1,x2,…,xD)。式（1）中分別表示第j維變量取值的上下界。

可變元素處理器PR值往往取指定范圍內(nèi)的實數(shù)。若將組件部署、組件選擇等類屬類型取值映射到從1開始的整數(shù)集，則它們可以取特定范圍內(nèi)的整數(shù)。

定義3定義函數(shù)genSA(X)表示根據(jù)解X定義的各可變元素的值，修改初始軟件體系結構SA0而生成的結果軟件體系結構。

定義4SA層性能優(yōu)化可以抽象為式（2）定義的兩目標優(yōu)化問題。式（2）中目標函數(shù)f1(X)和f2(X)分別表示根據(jù)解X生成的結果軟件體系結構，獲取系統(tǒng)響應時間和改進代價的值。式（3）和式（4）給出式（2）問題對應的Pareto最優(yōu)解集Opt。在式（3）和式（4）中，?和Ω分別表示支配關系和代表解空間。

4 代理模型幫助的SA層性能差分演化優(yōu)化算法SMDE4PO

為了求解式（2）定義的問題，本文基于DEMO（differential evolution for multiobjective optimization）算法[41]提出一種SA層性能差分優(yōu)化算法SMDE4PO。下面先闡述SMDE4PO算法的主要遺傳操作，再給出其總體流程。

4.1 初始化種群

SMDE4PO算法初始化種群中第i個體的編碼可按式（5）和式（6）定義的方法進行隨機生成。式（5）和式（6）中，xj,i(0)表示第0代初始種群中第i個體的第j維編碼。rand(0,1)表示在[0,1]區(qū)間產(chǎn)生均勻分布的隨機數(shù)，而ceil表示上取整函數(shù)。實數(shù)編碼和整數(shù)編碼的維度可分別按式（5）和式（6）隨機生成。

4.2 適應度評估

SMDE4PO算法的適應度評估主要是依據(jù)個體編碼x獲取硬件成本和系統(tǒng)響應時間兩個目標值，其過程如圖4所示。硬件成本的計算分成兩個步驟：首先計算genSA(x)獲取結果軟件體系結構SA*；然后計算cost(SA*)并輸出硬件成本的值。由于計算系統(tǒng)響應時間的代價高，耗時長，SMDE4PO算法引入隨機森林代理模型預估系統(tǒng)響應時間。具體的系統(tǒng)響應時間目標值的求解過程由解析階段、預測階段，以及這兩個階段之間的轉化構成，如圖4中3個虛線框所示。

在解析階段，首先根據(jù)結果軟件體系結構SA*求解rest(SA*)獲取實際的系統(tǒng)響應時間rst*；然后將(x,rst*)作為樣本進行收集和存儲。當收集的樣本超過預定義的數(shù)目時，則由解析階段向預測階段進行轉化。在轉化過程中，首先隨機森林學習算法被啟動，并運用解析階段采集的樣本構建代理模型，然后進入預測階段。

在預測階段，個體編碼x被輸入到隨機森林代理模型預測其對應的系統(tǒng)響應時間。當預測次數(shù)超過預定義的大小時，預測階段向解析階段進行轉化。系統(tǒng)響應時間目標值的求解將進入下一個解析階段并重新收集新的訓練樣本。

4.3 變異操作

SMDE4PO算法的變異操作分為兩個步驟：第一步從預定義的差分策略池中隨機選取一種策略對個體編碼xi（又稱目標向量）進行變異，并生成變異向量vi；第二步對vi的每個分量j進行越界檢查，若實數(shù)編碼部分違反，則依據(jù)式（7）進行修復，若整數(shù)編碼部分違反，則按式（8）修復。

Fig.4 Process for fitness evaluation of SMDE4PO algorithm圖4SMDE4PO算法的適應度評估過程

為了防止種群陷入局部搜索，并考慮加快收斂速度，從文獻[42]定義的差分策略中選取4種構建SMDE4PO算法的策略池，如表1所示。表1“DE/x/y”中的x和y分別表示目標向量、差分向量的個數(shù)。x可以是當前種群中的隨機（rand）個體xri、最優(yōu)（best）個體xb或當前（current）個體xc。xri(g)表示第g代種群中第ri個體，F(xiàn)為縮放因子。

Table 1 Mutation strategies used by SMDE4PO algorithm表1 SMDE4PO算法選用的變異策略

4.4 交叉操作

SMDE4PO算法從預定義的交叉策略池中隨機選取一種交叉策略，并對目標向量xi和變異向量vi進行交叉，以生成試驗向量ui。交叉策略池是由二項分布和指數(shù)分布兩種交叉策略所構成的。

式（9）給出了二項分布交叉操作。其中，NP為種群大小，jrand為[1,NP]上的隨機整數(shù)，CR稱為交叉概率，取值范圍為[0,1]。而指數(shù)分布交叉操作是先在[1,D]上隨機產(chǎn)生uj,i(g)的開始交叉位置k，并按圖5生成連續(xù)交叉的位數(shù)l，再依據(jù)式（10）和式（11）確定交叉范圍[low,high]。ui(g)中在交叉范圍內(nèi)的每個分量置為vj,i(g)，而其他分量則置為xj,i(g)。

Fig.5 Pseudo code for generating cross over bits圖5 生成交叉位數(shù)的偽代碼

4.5 選擇操作

SMDE4PO算法采用式（12）表示貪婪策略選擇下一代種群的個體。式（12）中，P?(g)表示第g代的臨時種群，在第g代種群演化前置空。?表示支配關系，它的含義由式（3）定義。

4.6 算法流程

SMDE4PO算法流程如下所示。第12行對臨時種群P?(g)的截斷方法與文獻[41]相同，都是按非支配等級和擁擠距離進行排序后，從中選取NP（種群大?。﹤€個體。

5 案例研究

為了驗證本文SMDE4PO算法的有效性，下面首先給出驗證的問題及度量指標；然后簡介案例并闡述所使用的統(tǒng)計方法；最后說明實驗的安裝，并展示實驗結果。

5.1 驗證研究的問題及度量指標

問題1（RQ1）多項式回歸（PRS）、Kriging模型、徑向基函數(shù)網(wǎng)絡（RBFN）、支持向量機（SVM）和隨機森林（RF）等5種常用的預測模型哪一種更適合作為SA層性能演化優(yōu)化算法的代理模型？SMDE4PO算法使用代理模型預估個體的系統(tǒng)響應時間，并作為選擇個體的依據(jù)。因而代理模型的優(yōu)劣直接影響到SMDE4PO算法的性能。文獻[24-25]綜述了用于演化算法的各種代理模型，并指出PRS、Kriging、RBFN、SVM和RF是最常使用的5種代理模型。故SMDE4PO算法重點考慮這5種模型。

為了公平評判各種代理模型，本文考慮SA層性能優(yōu)化問題的特點和文獻[26]評估代理模型的方法，選用訓練+預測執(zhí)行時間（time of execution for training+prediction，TTP）和等級保持（ranking preservation，RP）作為回答RQ1的兩個指標。TTP定義為在訓練樣本數(shù)和測試樣本數(shù)都為100的情況下，代理模型的訓練和預測所需的時間總和。RP較TTP復雜，下面先闡述保序性的概念，再具體給出計算方法。

稱代理模型對個體x和y的目標值預估具有保序性，當且僅當式（13）定義的h(x,y)為真。在式（13）中，分別是目標函數(shù)和預測函數(shù)。當預測從1開始順序編號的N個個體的目標值時，RP值的計算如式（14）和式（15）所示。其中，函數(shù)u表示按編號獲取對應的個體。從式（14）和式（15）可以看出：RP度量了代理模型在預測的N個個體中有多少對個體具有保序性，并將這個數(shù)字規(guī)一化到[0,1]區(qū)間內(nèi)。RP值越大說明代理模型越優(yōu)。

問題2（RQ2）SMDE4PO算法的解質(zhì)量是否優(yōu)于NSGA-II算法？NSGA-II算法是目前SA層性能優(yōu)化采用最多的，同時也是獲取較優(yōu)結果的一種算法。因而通過回答這一問題，以驗證SMDE4PO算法的有效性和有用性。

為了定量回答RQ2，本文使用貢獻度（contribution）、世代距離（generational distance）和超體積（hyper volume）3個指標，并依次將它們簡記為IC、IHV和IGD。在說明IC、IHV和IGD之前，先假設 SMDE4PO和NSGA-II算法求出的Pareto解集分別為S1和S2，且這兩個解集對應的參考Pareto解集為RS（對S1和S2的并集求取非支配解集）。

IC指標[43]用于度量S1和S2對RS的貢獻度。IC指標值在[0,1]之間變化，其值越大說明對RS貢獻越多。IHV指標[44]用于度量S1和S2在目標空間中所覆蓋的超體積。IHV值在[0,1]之間變化，其值越大說明在目標空間中支配其他解的數(shù)目也越多。IGD指標[45]用于度量S1和S2與RS在目標空間中的接近程度。為了使IGD與IC、IHV具有相同的取值范圍和優(yōu)劣變化的方向，將文獻[45]的指標值進行反向并歸一化到[0,1]。本文定義的IGD指標如式（16）所示。其中d(x,y)表示解x和y在目標空間中的歐氏距離，而|RS|表示RS中解的個數(shù)。IGD越大說明解集Si與RS在目標空間中越接近。IC、IHV和IGD的值越大，表明解質(zhì)量越優(yōu)。

問題3（RQ3）在獲取更高質(zhì)量解的前提下，SMDE4PO算法較NSGA-II算法是否顯著降低了運行時間？通過這一問題進一步驗證代理模型引入的合理性和有效性。

5.2 案例簡介

商業(yè)報告系統(tǒng)BRS[3]、多媒體文件存取系統(tǒng)MS[46]、過程控制系統(tǒng)PCS[47]和簡單設計策略例子STE（https://svnserver.informatik.kit.edu/i43/svn/code/Palladio/Examples/SimpleHeuristicsExample）被用作回答RQ1、RQ2和RQ3的案例。表2給出了這4個案例的規(guī)模。從表2中可以看出，規(guī)模從大到小依次是PCS、BRS、MS和STE，這與各案例可變元素的數(shù)目一致。此外，經(jīng)對比可變元素的取值范圍，發(fā)現(xiàn)各案例性能改進空間的大小與它們的規(guī)模大小也是一致的。

5.3 使用的統(tǒng)計方法

Table 2 Scale of BRS,MS,PCS and STE cases表2 BRS、MS、PCS和STE案例的規(guī)模

本文采用Wilcoxon秩和檢驗對實驗數(shù)據(jù)進行統(tǒng)計分析，并將置信水平α的值設為0.05。Wilcoxon秩和檢驗能夠給出對比數(shù)據(jù)在統(tǒng)計學上顯著的差異性。為了進一步觀測差異程度的大?。╡ffect size），本文采用Vargha-Delaney[48]的作為 effect size的直觀度量。的值域為[0,1]，其值越大說明差異程度越大。

5.4 實驗安裝

（1）代理模型訓練參數(shù)的設定

為了避免因模型參數(shù)設定不當而導致評價有失公平，在表3設定的參數(shù)范圍內(nèi)訓練各個模型并取測試中平均平方誤差（mean squared error，MSE）最小的模型作為參與比較的模型。

（2）算法參數(shù)的設定

Table 3 Value or range of parameters used to train surrogate model in SMDE4PO algorithm表3 SMDE4PO算法代理模型訓練參數(shù)及范圍設定

表4給出NSGA-II和SMDE4PO兩種算法的參數(shù)設定，為了公平起見，這兩種算法每次運行過程中個體評估次數(shù)都為6 000次。對每個案例，NSGA-II和SMDE4PO算法都獨立運行30次。

（3）實驗過程

Table 4 Parameters setting in NSGA-II and SMDE4PO algorithms表4 NSGA-II和SMDE4PO算法參數(shù)設定

實驗過程可按下面的4個步驟進行。

步驟1對每個案例按照拉丁超立方體抽樣的思想生成200個解，并通過性能評估獲取這些解對應的系統(tǒng)響應時間。將每個解及其對應的系統(tǒng)響應時間作為一個樣本，則每個案例可生成包含200個樣本的數(shù)據(jù)集。BRS、PCS、MS和STE案例共生成4個數(shù)據(jù)集。

步驟2根據(jù)步驟1生成的每個數(shù)據(jù)集，與文獻[24]一樣，先隨機均勻抽取100個樣本作為訓練樣本并將剩下樣本作為測試樣本；再按照表4設定的參數(shù)范圍對PRS、Kriging、RBFN、SVM和RF模型分別進行訓練，記錄最優(yōu)模型下RP值和TTP值，并進行統(tǒng)計分析，回答RQ1。

步驟3 針對各個案例（BRS、PCS、MS和STE），按表5的參數(shù)設置獨立運行NSGA-II和SMDE4PO算法各30次，記錄每次運行所獲取的Pareto最優(yōu)解集和所消耗的時間。

步驟4根據(jù)步驟3記錄的結果，先計算NSGA-II和SMDE4PO算法的解質(zhì)量指標IC、IHV和IGD；再對IC、IHV、IGD和運行時間分別進行統(tǒng)計分析后回答RQ2和RQ3。

5.5 實驗結果

在Intel?CoreTM2 2.66 GHz處理器、2 GB內(nèi)存及Win8.1操作系統(tǒng)實驗環(huán)境下，按上一節(jié)闡述的方法安裝和運行實驗，并完成實驗數(shù)據(jù)的收集和相關圖表的繪制。下面具體給出3個問題RQ1、RQ2和RQ3的實驗結果。

（1）RQ1的結果

表5顯示了BRS、MS、PCS和STE案例下5種模型PRS、Kriging、RBFN、SVM和RF在最優(yōu)訓練參數(shù)下獲取的等級保持RP、訓練和預測運行時間TTP兩個指標的值。從表5中可以看出，對所有的4個案例，RF的RP和TTP值優(yōu)于其他4個模型。

Table 5 Measure of TTP and RP applied to PRS,Kriging,RBFN,SVM and RF models in BRS,MS,PCS,and STE cases表5 PRS、Kriging、RBFN、SVM和RF模型在BRS、MS、PCS和STE案例下的RP和TTP值

為了便于比較，除了對表5中RF行對應的最優(yōu)RP和TTP值進行了加粗標記外，還加粗標出了各案例中第二優(yōu)的RP和TTP值。具體地，在BRS、MS、PCS和STE案例中，RF的RP值較第二優(yōu)的RP值分別提高了8.3%、0.2%、0.1%和0.8%；而RF的TPP值較第二優(yōu)的TPP值分別降低了35.2%、29.8%、4.0%和57.1%。這一實驗結果表明，RF較PRS、Kriging、RBFN和SVM模型更適合作為SA層性能演化優(yōu)化算法的代理模型。

（2）RQ2的結果

表6顯示了BRS、MS、PCS和STE案例下NSGAII和SMDE4PO算法的IC、IGD和IHV指標的秩和實驗結果。從表6中p-value值可以看出，SMDE4PO算法的IC、IGD和IHV指標顯著優(yōu)于NSGA-II算法。這一結論與統(tǒng)計盒圖6觀測的結果是一致的。表7顯示了IC、IGD和IHV指標對應的effect size的大小。從表7中可以得出兩個結論：一是在所有案例上，IC指標的effect size都為1，這說明SMDE4PO算法總能獲取一些兩個目標值均優(yōu)于NSGA-II的解；另一是BRS和PCS對應的IGD和IHV指標的effect size優(yōu)于MS和STE，這說明在案例規(guī)模和性能改進空間較大時，SMDE4PO算法獲取的解集較NSGA-II算法不僅更加接近于參考Pareto解集，并且能夠覆蓋更多解空間。

Table 6 p-value obtained in Wilcoxon experiments applying NSGA-II and SMDE4PO algorithms to BRS,MS,PCS and STE cases表6 BRS、MS、PCS和STE案例下NSGA-II和SMDE4PO算法的Wilcoxon實驗對應的p-value值

（3）RQ3的結果

表8和圖7顯示了BRS、MS、PCS和STE案例下NSGA-II和SMDE4PO算法運行30次的平均耗時情況。從表8和圖7中可以看出，BRS和PCS的耗時較MS和STE長，說明案例的規(guī)模和性能改進空間越大，NSGA-II和SMDE4PO算法的耗時也越長。另外，從表8中可以看出SMDE4PO算法較NSGA-II算法耗時降低的比例，從PCS案例的43%到BRS案例的48%。這一實驗結果表明：運用代理模型可以有效地減少性能評估的次數(shù)，進而能夠大幅地降低運行時間。

6 結論和未來工作

Table 7 Effect size obtained in Wilcoxon experiments applying NSGA-II and SMDE4PO algorithms to BRS,MS,PCS and STE cases表7 BRS、PCS、MS和STE案例下NSGA-II和SMDE4PO算法的Wilcoxon實驗對應的effect size值

Fig.6 Boxplots of IC,IGD,and IHVapplying NSGA-II and SMDE4PO algorithms in BRS,PCS,MS and STE cases圖6 BRS、PCS、MS和STE案例下NSGA-II和SMDE4PO算法的IC、IGD和IHV盒圖

Table 8 Average consuming time between NSGA-II and SMDE4PO algorithms by 30 runs in BRS,PCS,MS,and STE cases表8 BRS、MS、PCS和STE案例下NSGA-II和SMDE4PO算法運行30次的平均耗時

Fig.7 Time-consuming comparison between NSGA-II and SMDE4PO algorithms in BRS,MS,PCS and STE cases圖7 BRS、MS、PCS和STE案例下NSGA-II和SMDE4PO算法耗時對比

本文提出了一種SA層性能差分演化優(yōu)化算法SMDE4PO。SMDE4PO算法采用多種交叉和變異策略增大搜索空間和提高收斂速度，以期在離散解空間中獲取高質(zhì)量的解。SMDE4PO算法還引入隨機森林作為代理模型預估性能指標，以解決因SA層性能評估的計算代價大而導致優(yōu)化時間長的問題。與NSGA-II算法在4個不同規(guī)模案例上的實驗結果表明，SMDE4PO算法在顯著降低運行時間的同時，能夠有效地提高解的質(zhì)量。未來將擴展本文算法同時優(yōu)化性能、硬件成本、可用性和可靠性等多個質(zhì)量屬性，以提出一種代理模型幫助的軟件體系結構演化優(yōu)化方法。

[1]Taylor R N,Medvidovic N,Dashofy E M.Software architecture:foundations,theory,and practice[M].New York:Wiley Publishing,2009:471-472.

[2]Brosig F,Meier P,Becker S,et al.Quantitative evaluation of model-driven performance analysis and simulation of component-based architectures[J].IEEE Transactions on Software Engineering,2015,41(2):157-175.

[3]Koziolek A,Ardagna D,Mirandola R.Hybrid multi-attribute QoS optimization in component based software systems[J].Journal of Systems&Software,2013,86(10):2542-2558.

[4]Aleti A,Buhnova B,Grunske L,et al.Software architecture optimization methods:a systematic literature review[J].IEEE Transactions on Software Engineering,2013,39(5):658-683.

[5]Koziolek A.Automated improvement of software architecture models for performance and other quality attributes[M].Karlsruhe:KIT Scientific Publishing,2014.

[6]Du Xin,Ni Youcong,Ye Peng,et al.An evolutionary algorithm for performance optimization at software architecture level[C]//Proceedings of the 2015 IEEE Congress on Evolutionary Computation,Sendai,Japan,May 25-28,2015.Piscataway,USA:IEEE,2015:2129-2136.

[7]Du Xin,Ni Youcong,Ye Peng.A multi-objective evolutionary algorithm for rule-based performance optimization at software architecture level[C]//Proceedings of the 2015 Genetic and Evolutionary Computation Conference,Madrid,Spain,Jul 11-15,2015.New York:ACM,2015:1385-1386.

[8]Kounev S.Performance modeling and evaluation of distributed component-based systems using queueing Petri nets[J].IEEE Transactions on Software Engineering,2006,32(7):486-502.

[9]Tribastone M.A fluid model for layered queueing networks[J].IEEE Transactions on Software Engineering,2013,39(6):744-756.

[10]Distefano S,Scarpa M,Puliafito A.From UML to Petri nets:the PCM-based methodology[J].IEEE Transactions on Software Engineering,2010,37(1):65-79.

[11]Tribastone M,Gilmore S,Hillston J.Scalable differential analysis of process algebra models[J].IEEE Transactions on Software Engineering,2010,38(1):205-219.

[12]Koziolek A,Ardagna D,Mirandola R.Hybrid multi-attribute QoS optimization in component based software systems[J].Journal of Systems&Software,2013,86(10):2542-2558.

[13]Martens A,Koziolek H.Automatic,model-based software performance improvement for component-based software designs[J].Electronic Notes in Theoretical Computer Science,2009,253(1):77-93.

[14]Saed A A,Kadir W M N W.Applying particle swarm optimization to software performance prediction an introduction to the approach[C]//Proceedings of the 5th Malaysian Conference in Software Engineering,Johor Bahru,Malaysia,Dec 13-14,2011.Piscataway,USA:IEEE,2011:207-212.

[15]Koziolek A,Koziolek H,Reussner R H.Peropteryx:automated application of tactics in multi-objective software architecture optimization[C]//Proceedings of the 7th International Conference on the Quality of Software Architectures and 2nd International Symposium on Architecting Critical Systems,Boulder,USA,Jun 20-24,2011.New York:ACM,2011:33-42.

[16]Martens A,Koziolek H,Becker S,et al.Automatically improve software architecture models for performance,reliability,and cost using evolutionary algorithms[C]//Proceedings of the 1st Joint WOSP/SIPEW International Conference on Performance Engineering,San Jose,USA,Jan 28-30,2010.New York:ACM,2010:105-116.

[17]Reussner R.Domain-specific heuristics for automated improvement of PCM-based architectures[D].Karlsruhe:University of Karlsruhe,2010.

[18]Li Rui,Etemaadi R,Emmerich M T M,et al.An evolutionary multiobjective optimization approach to componentbased software architecture design[C]//Proceedings of the 2011 IEEE Congress on Evolutionary Computation,New Orleans,USA,Jun 5-8,2011.Piscataway,USA:IEEE,2011:432-439.

[19]Etemaadi R,Chaudron M R.Varying topology of componentbased system architectures using metaheuristic optimization[C]//Proceedings of the 38th Euromicro Conference on Software Engineering and Advanced Applications,Izmir,Turkey,Sep 5-8,2012.Washington:IEEE Computer Society,2012:63-70.

[20]Etemaadi R,Lind K,Heldal R,et al.Quality-driven optimization of system architecture:industrial case study on an automotive sub-system[J].Journal of Systems&Software,2013,86(10):2559-2573.

[21]Etemaadi R.Quality-driven multi-objective optimization of software architecture design:method,tool,and application[D].Leiden:Leiden University,2014.

[22]Etemaadi R,Chaudron M R.New degrees of freedom in metaheuristic optimization of component-based systems architecture:architecture topology and load balancing[J].Science of Computer Programming,2015,97:366-380.

[23]Walker M,Reiser M O,Tucci-Piergiovanni S,et al.Automatic optimisation of system architectures using EAST-ADL[J].Journal of Systems&Software,2013,86(10):2467-2487.

[24]Meedeniya I,Aleti A,Avazpour I,et al.Robust archeopterix:architecture optimization of embedded systems under uncertainty[C]//Proceedings of the 2nd International Workshop on Software Engineering for Embedded Systems,Zurich,Switzerland,Jun 9,2012.Piscataway,USA:IEEE,2012:23-29.

[25]Rahmoun S,BordeE,Pautet L.Automatic selection and composition of model transformations alternatives using evolutionary algorithms[C]//Proceedings of the 2015 European Conference on Software Architecture Workshops,Dubrovnik/Cavtat,Croatia,Sep 7-11,2015.New York:ACM,2015:25.

[26]Díaz-ManríquezA,Toscano-Pulido G,Gómez-Flores W.On the selection of surrogate models in evolutionary optimization algorithms[C]//Proceedings of the 2011 IEEE Congress on Evolutionary Computation,New Orleans,USA,Jun 5-8,2011.Piscataway,USA:IEEE,2011:2155-2162.

[27]Díaz-Manríquez A,Toscano-Pulido G,Barron-Zambrano J H,et al.A review of surrogate assisted multi-objective evolutionary algorithms[J].Computational Intelligence&Neuroscience,2016,4:1-14.

[28]Box G E P,Wilson K B.On the experimental attainment of optimum conditions[M]//Breakthroughs in Statistics.New York:Springer-Verlag,Inc,1992:270-310.

[29]Matheron G.Principles of geostatistics[J].Economic Geology,1963,58(8):1246-1266.

[30]Babu G S,Suresh S.Sequential projection-based metacognitive learning in a radial basis function network for classification problems[J].IEEE Transactions on Neural Networks&Learning Systems,2013,24(2):194-206.

[31]Cortes C,Vapnik V.Support-vector networks[J].Machine Learning,1995,20(3):273-297.

[32]Breiman L.Random forests[J].Machine Learning,2001,45(1):5-32.

[33]Mallipeddi R,Lee M.An evolving surrogate model-based differential evolution algorithm[J].Applied Soft Computing,2015,34(C):770-787.

[34]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[35]Ciccazzo A,Pillo G D,Latorre V.A SVM surrogate modelbased method for parametric yield optimization[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2016,35(7):1224-1228.

[36]Akhtar T,Shoemaker C A.Multi objective optimization of computationally expensive multi-modal functions with RBF surrogates and multi-rule selection[J].Journal of Global Optimization,2016,64(1):17-32.

[37]Husain A,Kim K Y.Enhanced multi-objective optimization of a microchannel heat sink through evolutionary algorithm coupled with multiple surrogate models[J].Applied Thermal Engineering,2010,30(13):1683-1691.

[38]Isaacs A,Ray T,Smith W.An evolutionary algorithm with spatially distributed surrogates for multiobjective optimization[C]//LNCS 4828:Proceedings of the 3rd Australian conference on Progress in Artificial Life,Gold Coast,Australia,Dec 4-6,2007.Berlin,Heidelberg:Springer,2007:257-268.

[39]Jin Yaochu.A comprehensive survey of fitness approximation in evolutionary computation[J].Soft Computing,2005,9(1):3-12.

[40]Gaspar-Cunha A,Vieira A.A multiobjective evolutionary algorithm using neural network to approximate fitness evaluations[J].International Journal of Computers,Systems&Signals,2005,6:18-36.

[41]Robi? T,Filipi? B.DEMO:differential evolution for multiobjective optimization[C]//LNCS 3410:Proceedings of the 2005 International Conference on Evolutionary Multi-Criterion Optimization,Guanajuato,Mexico,Mar 9-11,2005.Berlin,Heidelberg:Springer,2005:520-533.

[42]Mendes R,Mohais A S.DynDE:a differential evolution for dynamic optimization problems[C]//Proceedings of the 2015 IEEE Congress on Evolutionary Computation,Edinburgh,UK,Sep 2-4,2005.Piscataway,USA:IEEE,2005:2808-2815.

[43]Meunier H,Talbi E G,Reininger P.A multiobjective genetic algorithm for radio network optimization[C]//Proceedings of the 2000 Congress on Evolutionary Computation,La Jolla,USA,Jul 16-19,2000.Piscataway,USA:IEEE,2000:317-324.

[44]Zitzler E,Thiele L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.

[45]Van Veldhuizen D A,Lamont G B.Multiobjective evolutionary algorithm research:a history and analysis[J].Evolutionary Computation,1999,8(2):125-147.

[46]Brosch F,Buhnova B,Koziolek H,et al.Reliability prediction for fault-tolerant software architectures[C]//Proceedings of the Joint ACM SIGSOFT Conference-ISARCS on Quality of Software Architectures-QoSA and Architecting Critical Systems,Boulder,USA,Jun 20-24,2011.New York:ACM,2011:75-84.

[47]Koziolek H,Schlich B,Bilich C,et al.An industrial case study on quality impact prediction for evolving service-oriented software[C]//Proceedings of the 33rd International Conference on Software Engineering,Honolulu,USA,May 21-28,2011.New York:ACM,2011:776-785.

[48]Goulden K J.Effect sizes for research:a broad practical approach[J].Journal of Developmental&Behavioral Pediatrics,2006,27(5):419-420.

2016-09,Accepted 2016-11.

Surrogate Model Assisted Differential Evolutionary for Performance Optimization at SALevel*

DU Xin1,WU Xiaobin1+,NI Youcong1,2,YE Peng3,LI Song1
1.Faculty of Software,Fujian Normal University,Fuzhou 350117,China
2.Department of Computer Science,University College London,London,WC1E 6BT,UK
3.College of Mathematics and Computer,Wuhan Textile University,Wuhan 430200,China
+Corresponding author:E-mail:a1072466135@163.com

A few of evolutionary algorithms for performance optimization at software architecture(SA)level have been proposed to obtain the near optimal performance improvement solutions in large search space,and the NSGAII is the typical representative of these algorithms.However,most of these algorithms do not fully consider two factors:the performance improvement space with discrete feature and the performance evaluation with the high computational effort.As a result,the solutions obtained by these algorithms are not good and the corresponding processes of performance optimization are also considerably time-consuming.Aiming at this problem,this paper proposes a surrogate model assisted differential evolution algorithm for performance optimization at SA level,which is named by SMDE4PO.In the SMDE4PO,many strategies of crossover and mutation are adopted to enlarge the search space and accelerate the convergence.Furthermore,the random forest is regarded as surrogate model to substantially reduce the number of performance evaluation.The experimental results from four different size of cases show that(1)The SMDE4PO is significantly better than the NSGA-II in three indicators of contribution,generation distance and hyper volume;(2)By means of the random forest to predict performance indices,the run time of the SMDE4PO is reduced by 48%than the NSGA-II in the best results in the experiments.

software architecture;performance optimization;differential evolution;surrogate model

10.3778/j.issn.1673-9418.1609032

*The National Natural Science Foundation of China under Grant Nos.61305079,61370078(國家自然科學基金);the Natural Science Foundation of Fujian Province under Grant No.2015J01235(福建省自然科學基金);the JK Project of the Education Department of Fujian Province under Grant No.JK2015006(福建省教育廳JK類項目);the Open Fund of State Key Laboratory of Software Engineering of Wuhan University under Grant No.SKLSE 2014-10-02(武漢大學軟件工程國家重點實驗室開放基金).

CNKI網(wǎng)絡優(yōu)先出版:2016-11-11,http://www.cnki.net/kcms/detail/11.5602.TP.20161111.1627.006.html

DU Xin,WU Xiaobin,NI Youcong,et al.Surrogate model assisted differential evolutionary for performance optimization at SAlevel.Journal of Frontiers of Computer Science and Technology,2017,11(11)：1733-1746.

A

TP311

DU Xin was born in 1979.She received the Ph.D.degree from Wuhan University in 2010.Now she is an associate professor and M.S.supervisor at Fujian Normal University.Her research interests include search-based software engineering and evolutionary computing,etc.

杜欣（1979—），女，新疆石河子人，2010年于武漢大學獲得博士學位，現(xiàn)為福建師范大學軟件學院副教授、碩士生導師，主要研究領域為基于搜索的軟件工程，演化計算等。

WU Xiaobin was born in 1991.He is an M.S.candidate at Fujian Normal University.His research interest is searchbased software design.

吳曉斌（1991—），男，安徽安慶人，福建師范大學碩士研究生，主要研究領域為基于搜索的軟件設計。

NI Youcong was born in 1976.He received the Ph.D.degree from Wuhan University in 2010.Now he is an associate professor and M.S.supervisor at Fujian Normal University.His research interests include search-based software design and software architecture,etc.

倪友聰（1976—），男，安徽肥西人，2010年于武漢大學獲得博士學位，現(xiàn)為福建師范大學軟件學院副教授、碩士生導師，主要研究領域為基于搜索的軟件設計，軟件體系結構等。

YE Peng was born in 1976.He is a lecture at Wuhan Textile University.His research interests include search-based software design and software architecture,etc.

葉鵬（1976—），男，湖北武漢人，武漢紡織大學數(shù)學與計算機學院講師，主要研究領域為基于搜索的軟件設計，軟件體系結構等。

LI Song was born in 1993.He is an M.S.candidate at Fujian Normal University.His research interest is searchbased software design.

李松（1993—），男，湖北廣水人，福建師范大學碩士研究生，主要研究領域為基于搜索的軟件設計。