面向模式軟件體系結構合成中的沖突消解方法?

徐永睿 , 梁 鵬

1(武漢大學 計算機學院,湖北 武漢 430072)

2(軟件工程國家重點實驗室(武漢大學),湖北 武漢 430072)

軟件體系結構作為控制軟件復雜性、提高軟件系統質量的重要手段,日益受到軟件研究者和實踐者的關注,并發展成為軟件工程的一個重要的研究領域[1].在軟件體系結構設計中,軟件體系結構合成活動通過將軟件體系結構設計相關需求轉換成軟件體系結構設計方案,連接了問題空間和對應的解空間,是軟件體系結構設計中的核心活動[2].但是在傳統的軟件體系結構合成過程中,如何合成軟件體系結構解決方案,極大地依賴于架構師的設計經驗.為了在軟件體系結構合成中減少對架構師經驗的依賴,同時復用設計知識,軟件體系結構模式被廣泛地使用(如MVC、管道過濾器、分層模式等)[3].因此,面向模式的軟件體系結構合成應運而生[4].盡管如此,軟件體系結構模式的使用存在著一些困難和挑戰:1) 如何將候選模式中的抽象設計元素映射到軟件體系結構設計的具體實現;2) 架構師設計經驗的缺乏會導致在采用特定模式進行軟件體系結構設計時,違背該模式的設計約束.另一方面,如何將軟件職責(即面向對象分析得到的行為和屬性)分配到類,也是軟件體系結構合成中的一個難點問題.目前已有大量研究關注于解決軟件職責的分配問題[5,6],但這些研究都是獨立地考慮軟件職責的分配,而沒有考慮職責分配對軟件體系結構設計質量的影響(相同的職責分配在采用不同的模式時,系統質量需求的滿足可能完全不同).因此,面向模式的軟件體系結構合成必須同時考慮軟件職責的分配以及系統質量需求的滿足.

在我們之前的工作中[7],提出了基于協作式協同演化的方法(CoEA)來自動化合成面向模式的軟件體系結構候選設計方案.在我們提出的方法中,主要包含兩個自動化活動:職責合成(responsibility synthesis,簡稱RS)和模式合成(pattern synthesis,簡稱PS).職責合成負責處理軟件職責到類的分配,而模式合成關注于軟件體系結構層面的模式實現.我們提出的自動化合成方法能夠生成接近專家設計方案的體系結構設計方案[7],但是文獻[7]中提出的方法存在一定局限:在模式合成生成的方案ps和職責合成生成的方案rs進行組合,生成候選軟件體系結構方案時,ps和rs可能存在沖突.這里,我們通過一個簡單的例子來說明該沖突問題及其影響.

假設對包含5 個軟件職責(R1到R5)的設計問題進行軟件體系結構合成.當采用面向模式的軟件體系結構合成時,假設架構師選擇分層模式來滿足該設計問題的質量需求,那么一個可能的職責合成方案rs如圖1(a)所示.在該職責合成方案中,5 個軟件職責被分配到2 個類中.而一個可能的模式合成方案ps如圖1(b)所示.在該模式合成方案中,5 個職責被分配到分層模式的2 個層中.

當架構師需要組合職責合成的設計方案rs(如圖1(a)所示)和模式合成的設計方案ps(如圖1(b)所示),從而生成軟件體系結構設計方案時,必須確保rs和ps方案之間不存在沖突.在職責合成設計方案(如圖1(a)所示)中,R3與R1,R2被分配到同一個類中,但在模式合成設計方案(如圖1(b)所示)中,R3與R1,R2卻被分配到分層模式的不同層中.因為同一個類中的軟件職責應該被分配到分層模式的同一層中,所以架構師無法直接利用圖1(a)和圖1(b)的設計方案,組合生成最終面向模式的軟件體系結構設計方案.如果架構師需要利用rs和ps方案來生成體系結構設計方案,則要對兩者之間的沖突進行消解.例如在該例子中,架構師可以調整職責合成的設計方案rs,將R3分配到Class 2 中;或者調整模式合成的設計方案ps,將R3分配到Layer 1 中.

通過上述包含5 個軟件職責的簡單例子,我們直觀地介紹了面向模式的體系結構合成中的沖突問題.在實際設計問題中,職責合成需要將大量軟件職責分配到許多類中,而模式合成則需要將大量軟件職責分配到某一模式的不同角色中(例如分層模式的不同層).這導致了rs和ps方案在進行組合生成最終的面向模式的軟件體系結構設計方案時可能包含大量沖突.因此,對于面向模式的軟件體系結構合成,自動化方法不僅需要自動生成rs和ps方案,同時必須具備自動消解rs和ps方案間沖突的能力.在我們之前的工作中[7],采用協作式協同演化的方法較好地解決了rs和ps方案的生成問題.但當組合rs和ps方案生成最終的體系結構設計方案時,文獻[7]中提出的方法不能對沖突進行自動化消解,而只能組合那些沒有沖突的rs和ps方案來生成軟件體系結構設計方案.該策略雖然能避免設計沖突的產生,但缺陷是限制了軟件體系結構設計方案的多樣性,而這也是采用協作式協同演化方法所面臨的一個常見困難與挑戰[8,9].因此,本文的工作嘗試解決面向模式的軟件體系結構合成中的沖突自動化消解問題.

為了解決面向模式軟件體系結構合成中的沖突自動化消解問題,本文提出了基于學習的協作式協同演化軟件體系結構合成方法(CoEA-L),用于消解職責合成和模式合成產生的設計方案組合時的潛在沖突.在本文中,我們基于鮑德溫進化理論[10],提出了學習運算子的概念,擴展了傳統遺傳算法(genetic algorithm,簡稱GA)中的選擇、突變、交叉運算子.通過在學習運算子中采用一種關聯算法來發現職責合成種群和模式合成種群中個體間頻繁同時出現的軟件職責,進而利用提取到的知識消解ps和rs方案組合過程中產生的沖突.

本文的主要貢獻如下:在面向模式的軟件體系結構合成問題中,通過在搜索過程中使用關聯算法挖掘軟件職責間的關系,引入了職責合成與模式合成間的學習效應作為解決方案空間的啟發式搜索方法,進而消解職責合成和模式合成產生的設計方案間的沖突.同時,不同于現有基于搜索的軟件工程(SBSE)研究試圖通過改進對問題的表達,定義更好的適應度函數,或在搜索過程中采用更好的啟發式規則來提升候選解決方案的質量[11],本文提出的方法利用個體間的關系來改進候選方案的設計質量.個體通過學習其他種群中個體的特征,從而提升個體設計解決方案的質量.

本文第1 節介紹本文工作的相關研究背景.第2 節提出面向模式的軟件體系結構合成中的沖突消解方法.第3 節說明實驗的設計.第4 節給出實驗結果和分析.第5 節介紹相關工作.第6 節總結全文及下一步工作.

1 研究背景

針對面向模式的軟件體系結構候選設計方案的自動化合成,本節介紹了我們之前的工作[7]中提出的CoEA方法.

在我們之前的工作[7]中,CoEA 被用于面向模式軟件體系結構候選方案的合成.如圖2 所示,CoEA 主要包含7 個步驟.

1) 初始化種群(如圖2 的步驟1 所示).

在CoEA 方法中,我們使用兩個獨立的種群(職責合成種群和模式合成種群)分別對應面向模式軟件體系結構合成活動中的RS 和PS.因此,圖2 中m取值為2.職責合成種群中的每個個體即為一個候選的rs方案;同理,模式合成種群中的每個個體即為一個候選的ps方案.對于任意的rs(RS 種群表現型),我們使用整數向量(RS 種群基因型)對其進行編碼.整數向量的長度取決于軟件系統中軟件職責的數目,而向量中的每一位表示某個具體的單一職責,該位的取值即為該職責所被分配到的類.如果向量中不同的位具有相同的取值,則說明這些位所對應的軟件職責被分配到了同一個類中.類似地,對于任意的ps(PS 種群表現型),我們也使用整數向量(PS 種群基因型)對其進行編碼.該整數向量的長度仍然取決于軟件系統中軟件職責的數目,但不同的是,向量中每一位的取值表示的是在所選取的模式中,該職責所對應的模式角色[4].模式角色獨立于具體的軟件體系結構候選方案合成問題,而只與選取的模式相關.在我們之前的工作[12]中,研究了包括分層模式在內的常見軟件體系結構模式的模式角色及模式角色之間的關系.在圖3(a)中,我們給出了圖1(a)中的職責合成候選方案rs的表示實例.在該例子中,由于系統包含5 個軟件職責,所以候選方案所對應的向量長度為5,而每一位的取值,則表示了對應的軟件職責所被分配到的具體類的編號.同理,由于分層模式中基本的模式角色為層[12],圖1(b)中的模式合成候選方案ps的表示如圖3(b)所示.

Fig.2 CoEA for automated pattern-oriented architectural synthesis圖2 面向模式軟件體系結構CoEA 自動化合成方法

Fig.3 Representations of individuals in RS and PS populations圖3 職責和模式合成種群個體的表示實例

當采用整數向量對兩個種群候選解決方案進行編碼表示時,需要處理以下問題.

(1) 整數向量每一位的取值范圍.在職責合成中,向量每一位的取值范圍為[1,R],其中,R表示軟件職責的個數.在模式合成中,向量每一位的取值范圍為[1,P],其中,P表示所選取的模式中包含的不同模式角色的數目.在分層模式中,系統可能存在的最大層數等同于軟件職責的個數(在該極端情況下,每個軟件職責被分配到單獨一層),因此P=R.

(2) 相同候選方案可能具有不同的整數向量表示,即相同種群表現型對應不同的種群基因型.這里以圖3(a)中的職責合成候選方案rs為例.rs作為一個候選的RS 種群表現型,其可能的一種基因型如圖3(a)所示為[11122],而不同的基因型[11133][22211][33355][55533]也可以表示rs.針對該問題,我們將每一個基因型進行額外的轉換.在轉換中,通過逐個掃描原始基因型的每一位,令第1 個掃描到的整數值為i,將所有取值為i的向量位的值替換為1;同理,令第2 個掃描到的整數值為j,將所有取值為j的向量位的值替換為 2.以此類推.通過該方法的轉換,基因型[11133][22211][33355][55533]都將被轉換為[11122],從而保證兩個種群中表現型與基因型之間的一一對應關系.

2) 計算種群適應度(如圖2 的步驟2 所示).

在CoEA 方法中,職責合成種群和模式合成種群分別采用不同的適應度函數計算種群內個體的適應度.針對職責合成,目前已有的職責合成相關研究文獻[5,6]均采用耦合[13]、內聚[14]、復雜度[6]等指標對候選方案進行度量.根據文獻[15]中提出的系統獨立性原則,職責合成的適應度函數如公式(1)所示.

適應度RS=內聚?耦合?復雜度 (1)

一個職責合成候選方案如果擁有較高的職責合成適應度值,則意味著該方案擁有較高的設計質量.每一指標具體使用的度量見表1.

Table 1 Definitions of the metrics for RS表1 職責合成相關度量定義

另一方面,目前僅有較少文獻關注于軟件模式合成的自動化度量[18].文獻[18]也僅研究了分層模式的自動化度量.針對模式合成的自動化度量,在我們之前的工作[12]中,通過研究包括分層模式在內的常見軟件體系結構模式的模式角色、模式約束以及模式角色之間的關系,提出了一個通用的模式度量的定義過程.利用該模式度量定義過程,針對某個特定的模式,我們可以定義與該模式相關的度量,并利用模式的約束設置每個度量的權值w.因此,模式合成的適應度函數如公式(2)所示.

該適應度函數利用模式相關的度量計算出一個模式合成候選方案的模式約束違背代價.一個模式合成候選方案如果擁有較低的模式合成適應度值,則意味著該方案擁有較高的模式實現質量.

由于軟件體系結構可以被視為一系列設計規則空間的集合[19],而每個空間中的設計元素(例如模塊、包、類等)以層次化的關系進行交互[19],因此,分層模式作為使用頻率最高的軟件體系結構模式,適用于絕大多數系統的軟件體系結構設計.表2 列出了利用文獻[12]中模式度量定義過程定義的分層模式相關的度量.

Table 2 Definitions of the metrics of the layer pattern for PS表2 分層模式合成相關度量的定義

在使用分層模式進行模式合成時,根據分層模式的模式約束,需要盡可能地減少候選方案中存在的跨層依賴和反向依賴.因此,在定義關于分層模式的適應度函數時,需要對跨層依賴和反向依賴度量設置較高的權值(即跨層依賴和反向依賴會對模式的實現方案的質量產生較大的影響),同時對同層依賴和相鄰層依賴度量設置較低的權值.我們通過使用在決策分析領域常用于權重設置的層次分析法[20],設置分層模式中的上述度量的權值分別為0.145,0.277,0.508,0.07.因此,分層模式的適應度函數定義如公式(3)所示.

其中,i,j為分層模式中的任一層(i≠j),n為候選方案中包含的總層數.同理,我們可以根據公式(2)及文獻[12]中的模式度量定義過程,定義出其他軟件體系結構模式的適應度函數.

3) 執行選擇運算子(如圖2 的步驟3 所示).

在CoEA 方法中,職責合成種群和模式合成種群選擇運算子均使用錦標賽選擇方法來選擇個體.相對于其他選擇方法,錦標賽選擇更加高效且易于并行實現[21,22].在錦標賽選擇方法中,隨機選擇種群中的任意兩個個體,并保留適應度較優的個體作為父代中的個體.重復該操作,直到父代中個體的數目等于種群數目.

4) 執行交叉運算子(如圖2 的步驟4 所示).

在CoEA 方法中,職責合成種群和模式合成種群交叉運算子均使用單點交叉方法[22]從父代個體生成子代個體.在單點交叉方法中,父代個體的整數向量編碼隨機產生一個交叉位置,并根據該交叉位置交換配對的父代個體的整數向量表示,來生成子代個體.

5) 執行突變運算子(如圖2 的步驟5 所示).

在CoEA 方法中,職責合成種群和模式合成種群突變運算子均使用交換突變方法讓子代個體產生變異.在交換突變方法中,個體的整數向量編碼隨機產生一個突變位置,并基于概率確定該位置是否需要突變.當突變發生時,隨機修改個體整數向量該位置的值.對于職責合成種群,交換突變意味著將候選方案rs的某一職責交換到不同的類中;對于模式合成種群,交換突變意味著將候選方案ps的某一職責交換到不同的模式角色中.當突變運算子執行完成后,職責合成和模式合成種群產生下一代個體.

6) 組合各種群個體(如圖2 的步驟6 所示).

在CoEA 方法中,通過組合職責合成和模式合成種群個體,產生面向模式軟件體系結構的候選方案.需要強調的是,在CoEA 方法中,由于不存在有效的沖突消解機制,因此只能組合不包含沖突的rs和ps來產生體系結構設計方案.

7) 更新種群(如圖2 的步驟7 所示).

當需要繼續迭代時,針對職責合成和模式合成種群,CoEA 用子代種群更新當前種群,從而跳轉到圖2 的步驟2 開始新一輪迭代.

2 協作式協同演化軟件體系結構合成中的沖突消解

本節首先介紹了基于學習的協作式協同演化軟件體系結構合成方法(見第2.1 節),然后說明了如何使用該方法自動化消解面向模式的軟件體系結構合成中產生的沖突(見第2.2 節).

2.1 基于學習的協作式協同演化體系結構合成方法

在進化生物學中,生命體的特征會隨著生命體與環境的交互而發生改變.鮑德溫在文獻[10]中研究了生命體具備的學習能力,提出了一種特別的生命體進化機制.在該機制中,后代具備從環境中獲得新特征的學習能力,而不僅僅是直接依賴于繼承遺傳編碼所獲得的對應特征.

相對于單種群進化,鮑德溫效應對于協同演化計算模型的意義更加突出:在協同演化計算中,其他種群扮演了某一特定種群的外部環境,每個種群內部的個體能夠從外部環境中學習從而改變自身特征.在我們之前提出的方法中[7],職責和模式種群采用的遺傳算法[22]基于達爾文進化理論,個體特征依賴于從父代繼承的遺傳編碼,而無法從另一種群中學習.種群間交互的缺失,導致了協同演化軟件體系結構合成中的沖突問題.因此,基于鮑德溫效應,針對面向模式的軟件體系結構自動化合成問題,我們提出了CoEA-L 方法,從而擴展了CoEA 方法.CoEA-L 方法的主要步驟如圖4 所示.

Fig.4 Proposed approach for automated pattern-oriented architectural synthesis圖4 本文提出的面向模式軟件體系結構自動化合成方法

相對于CoEA,在CoEA-L 中,我們根據鮑德溫效應提出了新的學習運算子(如圖4 的步驟6 所示),從而擴展了遺傳算法的選擇、交叉和突變運算子.作為CoEA 和CoEA-L 方法的唯一區別,學習運算子的提出,為職責合成和模式合成種群個體引入了學習機制.當突變操作完成后,生成的子代可以從外部環境(其他種群)中學習,自適應地對種群個體的特征進行調整.當職責合成種群和模式合成種群中的個體進行組合,生成面向模式的候選軟件體系結構設計方案時,如果檢測到沖突,個體可以利用從其他種群中的個體學習到的知識對自身進行自適應調整,從而完成沖突消解.需要注意的是,當進行沖突消解時,只需要任意1 個或多個種群(即種群集合P的子集K)在學習運算子中進行消解即可.在本文中,由于CoEA-L 方法只需要使用兩個種群,我們假設由模式種群來進行沖突消解.

2.2 基于學習的協作式協同演化體系結構合成方法中學習運算子的實現

如圖5 所示,為了消解面向模式的軟件體系結構合成中,職責種群個體和模式種群個體組合生成候選體系結構方案時的沖突.學習運算子主要由4 個步驟組成.

1) 提取種群信息數據集;

2) 生成種群頻繁項集;

3) 生成學習規則集;

4) 對組合的種群個體應用學習規則消解沖突.

這4 個步驟以順序工作流的形式實現了圖4 中的學習運算子(即圖4 中的步驟6),因此在后文中,我們以步驟6.1～步驟6.4 來標示學習運算子中的每個具體步驟.本小節的剩余部分將詳細介紹如何利用這4 個步驟來消解沖突(即第2.2.1 節～第2.2.4 節),并給出一個沖突消解實例(見第2.2.5 節).

Fig.5 Implementation of the learning operator圖5 學習運算子的實現

2.2.1 提取種群信息數據集(步驟6.1)

對于職責種群個體,首先需要從模式種群個體中提取出模式種群的數據信息.通過后續步驟將提取出的信息進一步處理,提供了職責種群個體在與軟件體系結構模式種群個體進行組合時消解沖突的必要信息.同理,對于模式種群個體,我們也需要類似地從職責種群個體中提取出職責種群的數據信息.由于我們假設由模式種群進行沖突消解,步驟6.1 需要從職責種群個體中提取出職責種群的數據信息,再將提取到的信息傳遞給模式種群用于后續的沖突消解.職責種群提取出的數據信息包含職責種群所有個體中職責到類的分配信息.當職責種群的種群信息數據集被提取后,可以在步驟6.2 中進一步生成職責種群的頻繁項集.種群信息數據集提取操作的時間復雜度為O(n).

2.2.2 生成種群頻繁項集(步驟6.2)

在關聯數據挖掘中,頻繁項集表示那些在數據集中出現次數大于等于用戶定義的閾值的項集[23].頻繁項集意味著項集里包含的元素有較高的概率在不同的記錄中同時出現.在一個包含n個軟件職責的面向模式軟件體系結構合成中,項集表示軟件職責的任意組合,因此所有可能的不同項集數為2n?1,而頻繁項集除了需要滿足關聯數據挖掘中的定義外,還需要保證該項集中包含的元素數目大于1(即由單一軟件職責構成的項集不能算作頻繁項集).在我們提出的方法中,職責種群信息數據集中的頻繁項集意味著該項集所包含的軟件職責在職責種群的不同個體中,擁有較高的概率被分配到相同的類.類似地,模式種群信息數據集中的頻繁項集意味著該項集所包含的軟件職責在模式種群的不同個體中,有較高的概率被分配到相同的模式角色.

在步驟6.2 中,我們使用了數據挖掘中的Apriori 關聯規則挖掘算法[23]從步驟6.1 提取出的職責種群信息數據集中生成職責種群的頻繁項集.提取出的職責種群頻繁項集將在步驟6.3 中生成學習規則集,便于模式種群個體在組合生成軟件體系結構設計方案時學習以消解沖突.需要說明的是,Apriori 算法主要的連接和剪枝操作具有較高的性能開銷,文獻[23]中對這些操作進行了詳細的性能分析評估.

2.2.3 生成學習規則集(步驟6.3)

在步驟6.3 中,需要將提取出的職責種群信息數據集中的頻繁項集轉化成可以用于沖突消解的學習規則集.在頻繁項集中,我們只知道哪些軟件職責具有較高的概率被分配到同一個類,因此,頻繁項集中軟件職責之間的關系是相關關系.而在學習規則集中,必須把軟件職責的相關關系轉換成軟件職責間的因果關系,才能被用于后續的沖突消解.圖6 給出了本文提出的學習規則集生成算法.

Fig.6 Proposed algorithm for generating the rule set圖6 本文提出的學習規則集生成算法

在該算法中,針對職責種群頻繁項集中的每一個頻繁項fi,生成該頻繁項的所有非空子集構成集合S,如算法第2 行所示.在第4 行中,對S集合中的每一元素s,生成形如“s?(fi?s)”的學習規則.fi?s構成一個軟件職責集合,包括那些在頻繁集fi中但不在s中的軟件職責.在算法第4 行中,大量的學習規則會被生成,因此,在算法第5行中,通過使用cosine度量來評估生成的學習規則和其對應的頻繁項fi的相關性,從而在算法中僅保留那些具有學習意義的強關聯學習規則.

針對任意生成的學習規則“s?(fi?s)”,該學習規則cosine度量的定義如公式(4)所示.

其中,P(i)表示集合i中的所有軟件職責在步驟6.1 生成的種群信息數據集中同時出現的概率.根據Merceron 和Yacef 的經驗準則[24],算法僅保留cosine度量大于臨界值0.65 的學習規則.在后續的研究中,我們將進一步研究cosine度量的臨界值,從而找到沖突消解效率最高的cosine臨界值取值.此外,由于不同的學習規則具有不同的優先級,在第6 行中,算法利用置信度[25]定義學習規則的優先級.置信度計算公式如公式(5)所示.

當有多條規則可以被學習時,優先級最高的規則將會被學習.最后,算法第8 行到第11 行對重復的規則進行過濾.假設規則集中有兩條學習規則r1和r2,如果r1是r2的子集并且r1的cosine和置信度度量大于等于r2的cosine和置信度,那么算法將會從學習規則集中去除重復規則r2.步驟6.3 學習規則生成算法的最壞時間復雜度為O(n×2n).

2.2.4 應用學習規則消解沖突(步驟6.4)

當學習規則生成后,學習運算子可以應用生成的學習規則消解職責種群和模式種群個體組合生成軟件體系結構候選方案時產生的沖突.圖7 給出了應用學習規則的沖突消解算法.在該算法中,假定當職責種群個體和模式種群個體的組合發生沖突時,模式種群個體通過學習職責種群個體所產生的規則,從而自適應地調整.換言之,當檢測到沖突時,由模式種群個體嘗試進行沖突消解(反之,職責種群個體也可以通過學習模式種群個體所產生的規則來消解沖突).

Fig.7 Algorithm for conflict resolution圖7 沖突消解算法

首先,在算法的第1 行～第3 行,算法檢測待組合的職責種群個體和模式種群個體是否存在沖突:如果不存在沖突,則可以直接進行組合生成軟件體系結構候選方案;否則,需要在職責種群個體和模式種群個體組合前進行沖突消解.在算法的第4 行,按照規則的優先級對職責種群的學習規則集進行排序,確保高優先級的規則被優先學習.算法的第5 行使用了列表來記錄最近被學習的學習規則.為了防止單一的規則在短時期內多次被學習從而影響到生成個體的多樣性,該列表確保最近被學習的學習規則在短時間之內不可再次被個體學習.如第6 行所示,算法的主體部分使用深度優先搜索對職責種群學習規則集進行了遍歷,從而盡最大可能根據職責種群學習規則集自適應調整模式種群個體.在算法的第10 行和第11 行,通過找到優先級相對最高且最近沒有被學習過的學習規則對模式種群個體進行學習.需要說明的是,每條學習規則有其前置條件,如果模式種群個體嘗試學習該規則,則個體必須滿足該學習規則的前置條件.假設學習規則為{Ri,Rj}?{Rk},那么規則的左部{Ri,Rj}即為該規則的前置條件.如果一個模式種群個體嘗試學習該條規則,意味著Ri和Rj必須屬于相同的模式角色.通常情況下,模式種群個體需要通過多次學習規則集中的規則才能消解與職責種群個體間的沖突.在最壞的情況下,Indp始終無法學習到合適的規則來消解沖突,我們將在第4.2 節對此進行討論.如圖7 所示的沖突消解算法的最壞時間復雜度為O(nn).

2.2.5 方法示例

在本節中,我們采用引言部分提出的例子(包含5 個軟件職責R1～R5的體系結構合成問題),通過示例的方式進一步解釋CoEA-L 中的步驟6.1～步驟6.4.需要說明的是,實際軟件項目中的軟件職責數目非常巨大,這里的示例只是為了簡潔地解釋CoEA-L 中步驟6.1～步驟6.4,因此,示例中假設只包含5 個軟件職責.

由于本文提出的方法假設由模式種群進行沖突消解,在步驟6.1 中,需要從職責種群中提取出職責種群所有個體中職責到類的分配信息,生成職責種群信息數據集.這里,我們假設職責合成種群的個體總數為3(在演化計算中,種群個體數一般較大,這里為了以例子形式直觀進行描述,假設職責種群的個體總數只有3 個).職責合成種群及其包含的3 個可能個體如圖8 所示.

在步驟6.1 中,針對職責種群的每一個個體的每一個類,使用一個記錄來記錄該類所包含的軟件職責.因此,個體的記錄數目等于該個體所對應的職責候選方案中的類的數目.例如,圖8(a)中職責種群個體1 包含2 條記錄,分別是{R1,R2,R3},{R4,R5};而圖8(b)中職責種群個體2 因為有3 個類,所以包含3 條記錄,分別是{R1,R4},{R2,R3},{R5}.同理,圖8(c)中職責種群個體3 的記錄為{R1,R2,R3},{R4},{R5}.只需要將職責種群的所有個體的所有記錄組合,就生成了職責種群信息數據集.在圖8 中,提取到的職責種群信息數據集為{{R1,R2,R3},{R4,R5},{R1,R4},{R2,R3},{R5},{R1,R2,R3},{R4},{R5}}.

Fig.8 Three possible individuals in responsibility population圖8 職責種群的3 個可能個體

在步驟6.2 的職責種群頻繁項集的生成中,假設架構師定義的頻繁項集的閾值為2,那么圖8 生成的職責種群信息數據集{{R1,R2,R3},{R4,R5},{R1,R4},{R2,R3},{R5},{R1,R2,R3},{R4},{R5}}中,頻繁項集為{{R1,R2},{R1,R3},{R2,R3},{R1,R2,R3}}.因為在所有二元項集中,{R1,R2},{R1,R3}在職責種群信息數據集中出現次數等于頻繁項集的閾值(2),分別2 次出現在項集{R1,R2,R3}中,而{R2,R3}在職責種群信息數據集中出現3 次,2 次出現在項集{R1,R2,R3}中,1 次出現在{R2,R3}中.同時,在該例子中不存在除{R1,R2,R3}以外的其他三元及三元以上的項集出現次數大于等于頻繁項集的閾值.由于頻繁項集的所有非空子集必然也是頻繁的,因此,步驟6.2 最終生成的職責種群頻繁項集只需要包含{R1,R2,R3}.

由于步驟6.2 生成的頻繁項集中只包含頻繁項{R1,R2,R3}(圖6 算法第1 行中的fi),該頻繁項fi對應7 個非空子集,則步驟6.3 中圖6 算法第2 行中的S集合包含7 個元素s,分別為{R1},{R2},{R3},{R1,R2},{R1,R3},{R2,R3},{R1,R2,R3}.這里以其中的一個元素s({R1,R2})為例,因為在圖6 算法第4 行中,只有職責R3在fi中,同時又不在s中,則該元素s對應生成的學習規則為{R1,R2}?{R3}.同理,假設元素s為{R1,R3},則對應的學習規則為{R1,R3}?{R2}.通過進一步應用圖6 算法第5 行中對學習規則cosine度量的計算、圖6 算法第6 行中對學習規則confidence度量的計算以及圖6 算法第8 行到第11 行中對冗余學習規則的消除,步驟6.3 可以生成用于后續沖突消解的學習規則集,并將這些學習規則按照confidence度量進行優先級排序.

在步驟6.4 中,如圖9 所示,假設一個職責種群個體Indr和一個模式種群個體Indp嘗試進行組合生成軟件體系結構設計候選方案.同時,假設步驟6.3 生成的職責種群學習規則集包含3 條不同優先級的學習規則.當Indr和Indp進行組合時,這兩個個體之間存在著兩個沖突:1) 因為在職責種群個體Indr中,軟件職責R2和R3被分配到同一個類,所以與模式種群個體Indp中R2與R3被分配到分層模式的不同層產生沖突;2) 同理,R4與R5也產生沖突.因此,沖突消解算法需要利用職責種群學習規則集來調整模式種群個體Indp,從而消解Indp和Indr之間的所有沖突.

Fig.9 An initial state when indp and indr try to resolve inconsistencies圖9 職責種群個體indp 和模式種群個體indr 嘗試沖突消解時的初始狀態

圖 9 中的模式種群個體沖突消解實例如圖 10 所示.在圖 10 中,Indp嘗試學習優先級最高的規則{R1,R2}?{R3},由于該規則的前置條件是軟件職責R1和R2必須屬于同種模式角色(分層模式的同一層),因此Indp只能繼續嘗試學習第二優先級的規則{R1}?{R2,R3}.于是,Indp通過學習,將自身調整為圖10(a)所示狀態.在該狀態下,由于R2,R3已被分配到分層模式的同一層里,上文提到的第1 個沖突被成功消解.但R4與R5的沖突依舊存在,Indp繼續利用職責種群學習規則集進行第2 輪學習.在第2 輪學習中,優先級最高的規則{R1,R2}?{R3}由于無法改變Indp產生新的狀態(圖7 第13 行),所以依然無法被Indp學習,而第二優先級的規則{R1}?{R2,R3}因為在上一輪已被學習,因此在這一輪的學習中,Indp只能利用優先級最低的{R4}?{R3,R5}進行學習,產生新的狀態如圖10(b)所示.在該狀態下,由于R4與R5已被分配到分層模式的同一層里,上文提到的第2 個沖突被成功消解.但R2與R3的沖突又重新產生,Indp需要繼續進行第3 輪學習.在第3 輪學習中,Indp利用優先級最高的規則{R1,R2}?{R3}產生新的狀態,如圖10(c)所示.在該狀態下,Indr和Indp之間的兩個沖突全部被消解.因此對于該例子中的Indr和Indp,本文提出的方法可以無沖突地使用它們進行軟件體系結構候選方案的合成.但是在Indp的某一(中間)狀態下,可能所有的規則都無法被學習.當學習無法繼續時,Indp的當前狀態需要回溯到上一狀態,重新利用不同的規則進行學習(即優先級相對較低的候選規則).

Fig.10 Procedure of conflict resolution for Indp圖10 模式種群個體Indp 的沖突消解過程

3 實驗設計

本節主要描述如何通過實驗設計對本文所提出的方法進行有效性驗證,包括研究問題的提出(第3.1 節)、設計問題的選擇(第3.2 節)、競爭方法介紹(第3.3 節)、方法運行參數的設置(第3.4 節)以及對方法有效性評估的度量指標(3.5 節).最后介紹了對實驗結果進行分析的統計方法和檢驗(第3.6 節)以及效度威脅(第3.7 節).

3.1 研究問題

我們提出3 個研究問題(research question,簡稱RQ),用于驗證本文所提出方法的有效性.

· RQ1:職責種群個體和模式種群個體組合生成軟件體系結構候選方案時,沖突發生的頻率?RQ1 驗證本文提出的CoEA-L 方法是否具備研究意義:如果職責種群個體和模式種群個體組合時很少或基本不發生沖突,則嘗試進行沖突消解的研究意義不大.RQ1 是驗證我們所提出的方法意義的基本研究問題.

· RQ2:基于學習的協作式協同演化軟件體系結構合成方法是否可以在不同的問題實例中有效的消解沖突?RQ2 主要研究CoEA-L 方法的有效性,即在多大程度上消解職責種群個體和模式種群個體組合時所產生的沖突.同時,通過在不同規模的問題實例上應用本文提出的方法,RQ2 也研究了本文提出的方法是否具備一定的適用性.

· 余下的研究問題RQ3 主要關注于本文所提出的CoEA-L 方法和其他競爭方法(見第3.3 節)在解決面向模式的軟件體系結構合成問題中的差異.RQ3 包含兩個子研究問題.

? RQ3.1:基于學習的協作式協同演化軟件體系結構合成方法最終生成的面向模式的軟件體系結構方案相比于其他競爭方法生成的設計方案,是否具有更好的設計質量?如果CoEA-L 方法最終生成的軟件體系結構的設計質量低于其他方法生成方案的設計質量,那么即使本文提出的方法能夠較好地進行沖突消解,方法的實用性依然存在問題.

? RQ3.2:基于學習的協作式協同演化軟件體系結構合成方法相比于其他競爭方法,是否具有顯著的額外系統開銷?RQ3.2 主要研究不同方法用于解決面向模式的軟件體系結構合成問題時的系統性能開銷,在該研究問題中,我們主要關注本文提出方法所引入的學習運算子是否會顯著增加系統的性能開銷.如果額外增加的性能開銷過大,將影響本文提出方法的實用性.

3.2 實驗設計問題

在實驗驗證中,我們選取了3 個設計問題(實例)進行驗證,分別是電影院預訂系統(cinema booking system,簡稱CBS)[26]、畢業生管理系統(graduate development system,簡稱GDS)[27]和郵輪選擇系統(select cruises system,簡稱SCS)[28].選擇這3 個設計問題進行實驗驗證的理由如下.

1) 這3 個設計問題非本文作者設計,這樣可以減少實驗結果可能存在的偏向性.

2) 這3 個系統的人工設計方案公開[29],便于作為基準設計與各種自動化設計方法的結果進行統一比較.

3) 軟件體系結構合成領域已有研究工作[30?33]使用這些設計問題來評估所提出的方法.

選取的這3 個設計問題具有不同的問題規模,表3 給出了每個設計問題的方法、屬性、軟件職責以及職責間的依賴數目.在文獻[31]中,Simons 等人分析了職責合成的問題復雜度以及不同問題實例所對應的解空間的大小[31].Simons 等人通過一個包含16 個軟件職責的具體例子,指出職責合成問題的解空間大小將隨著軟件職責數目的增加而呈指數級增長.例如,將這16 個職責分配到5 個類中,該實例所對應的解空間大小也超過了132 300 000[31].而在實際職責合成中,由于類的數目并不固定,因此即便是對16 個軟件職責進行職責合成,問題也具有非常高的復雜度.類似地,軟件職責的模式合成問題也具有非常高的問題復雜度.綜上,本文所選取的這3個不同規模的設計問題都足以驗證本文提出方法的有效性,從而保證實驗結果具有實用意義.

Table 3 Problem instances with their sizes表3 設計問題(實例)的規模

3.3 競爭方法介紹

本文選擇的競爭方法包括RS,CoEA 和BO.Arcuri 等人指出,在進行實驗驗證時,任何基于搜索的算法都需要和RS 算法進行比較,從而確保改進算法獲得的理想實驗結果并不是由于選取的目標實驗研究問題過于簡單導致的[34,35].而CoEA 和本文提出的CoEA-L 的唯一差異就是是否引入學習運算子(圖4 中的步驟6).通過比較CoEA 和CoEA-L 的性能差異,我們可以驗證學習運算子的有效性.BO 作為一種廣泛使用的分層優化方法[36,37],適合解決面向模式軟件體系結構設計方案的合成問題.因此在實驗驗證中,我們選擇了RS,CoEA 和BO 作為CoEA-L 的競爭方法.

3.4 實驗參數設置

實驗運行在配置酷睿2.3G 雙核處理器,10GB 物理內存的計算機上.在實驗中,包含3 個不同的對照組,分別采用了第3.3 節介紹的3 種競爭方法,而實驗組采用了本文提出的CoEA-L.實驗參數設置見表4(其中,斜體字表示僅適用于本文所提出的方法(即CoEA-L)的參數及其設置).

Table 4 Experimental parameter settings of studied approaches表4 方法運行的實驗參數設置

3.5 實驗度量指標

為回答第3.1 節提出的研究問題(RQ),我們需要對實驗組與對照組進行了如下4 個方面的比較.

1) 職責種群個體和模式種群個體組合生成候選軟件體系結構方案時沖突發生的頻率.

2) 當沖突發生時,不同方法能夠有效地進行沖突消解的能力.

3) 不同方法生成的候選軟件體系結構方案的設計質量.

4) 不同方法運行導致的系統性能開銷.

由于性能開銷主要比較方法運行時間,因此這里主要介紹與前3 個方面相關的實驗度量指標.

1) FC(frequency of conflicts)度量

在FC 度量中,我們使用兩個計數器Cconflict和Ccombine:當一個職責種群個體r和一個模式種群個體p嘗試組合生成候選軟件體系結構方案時,Ccombine計數器始終遞增;如果r和p發生沖突,則同時遞增Cconflict計數器.因此,FC度量的定義如公式(6)所示.

FC 度量的取值范圍為0～1,FC 比值越高,則職責種群個體和模式種群個體組合時發生沖突的概率越大.

2) ERI(effectiveness of resolving inconsistencies)度量

在ERI 度量中,我們使用兩個計數器Cconflict和Cresolved:當一個職責種群個體r和一個模式種群個體p嘗試組合生成候選軟件體系結構方案發生沖突時,Cconflict遞增;如果r和p的沖突可以成功消解,則Cresolved遞增.因此,ERI 度量定義如公式(7)所示.

ERI 度量的取值范圍為0～1,ERI 比值越高,則職責種群個體和模式種群個體組合發生沖突時,沖突被消解概率越大.

3) DQ(design quality of solution)度量

軟件體系結構設計方案的設計質量難以自動化度量.通常,設計質量是根據架構師自身的設計經驗進行主觀評價.文獻[38]證實:對于軟件設計質量評估,目前依舊缺乏有效的自動化度量指標.因此,我們參照軟件體系結構合成領域相關文獻[6,32],采用將自動化設計的軟件體系結構候選方案與專家設計方案進行相似度比較的方法來度量自動化方案的設計質量.我們認為,專家設計方案能夠盡可能地滿足軟件設計原則,同時,針對特定設計問題,專家方案的軟件設計質量能夠滿足設計需求.因此,自動化生成的設計方案與專家設計方案的相似度越高,則可以認為設計質量越高.

本文所采用的實驗設計問題(見第3.2 節)全部具有作為基準設計的公開的專家職責合成方案[29].根據專家職責合成方案類及其依賴關系,形成以類為節點、類間依賴為邊的有向圖G,進而對G執行拓撲排序,從而生成專家模式合成方案.在拓撲排序中,最早找到的沒有前驅(入度為0)的節點構成節點集合Vi,Vi中節點對應的類構成采用分層模式的專家模式合成方案中的第i層(i>0).在G中刪除節點集合Vi及所有以Vi中節點為起點的有向邊后,找到的入度為0 的節點構成節點集合Vi?1,Vi?1中節點對應的類構成采用分層模式的專家模式合成方案中的第i?1 層.重復該過程,直到G=?.當G中存在環導致無法找到入度為0 的節點時,選擇入度最小出度最大的節點v連同v的所有前驅節點構成節點集合Vi.

對于職責種群個體,我們使用F-Score 來比較該設計方案與專家職責合成方案的相似度.F-Score 的定義如公式(8)所示.

在公式(8)中,R表示軟件職責;Cls表示專家設計方案;clsi表示專家設計方案中的任意一類(class),而該類所擁有的軟件職責數目為|clsi|.類似地,C表示職責合成自動化生成的一個候選方案,cj表示其中的一個類,nij記錄了專家設計方案Cls中的類clsi和自動化生成的一個候選方案C中的類cj共同擁有的軟件職責數目.F-Score的計算依賴于F值,而F值的計算依賴于信息檢索領域的精確率和召回率的計算[39].在我們的公式中,通過重新定義精確率和召回率的計算方法來計算F值.

類似地,我們仍然使用F-Score 來計算模式種群個體和專家模式合成方案間的相似度.F-Score 的定義如公式(9)所示.

在公式(9)中,Rol表示專家設計方案中存在的所有模式角色,Ro表示模式合成自動化生成的一個候選方案中的所有模式角色,而roli表示專家設計方案所用模式的某一特定模式角色,roi表示模式合成自動化生成的一個候選方案所用模式的某一特定模式角色.

F-Score 公式可以對自動化生成的任意軟件體系結構設計方案計算其與專家方案的相似度,從而評估其設計質量.通過評估種群中所有軟件體系結構設計方案與專家方案的相似度,就可以評價不同方法生成的候選軟件體系結構方案的設計質量.

3.6 統計分析方法

對于具有隨機性特征的搜索算法,為了可靠地回答第3.1 節提出的研究問題(RQ),針對每一個設計問題(實例)的每次實驗驗證,我們采用多次運行并使用統計分析的方法給出對應的實驗結果[40].根據Arcuri 等人提出的隨機性算法實驗評估建議[35],所有實驗驗證次數設置為30 次.比較兩組樣本時,最常使用的統計檢驗是t-test 和Mann-WhitneyU-test.其中,t-test 是有參檢驗,而U-test 是無參檢驗.U-test 在統計推斷過程中不涉及有關總體分布的參數,因而對樣本數據的分布假設較少.根據文獻[40]中的建議,我們使用p值為0.05 的雙尾t-test 和U-Test進行兩組樣本間差異的顯著性檢驗.根據文獻[40,41]的建議,我們同時報告了效應量[42].度量可以定量分析兩組樣本之間差異的顯著性,其取值為0～1.假設得到的度量值為0.8,則意味著在不同的實驗驗證中,80%的運行第1 組樣本能取得更優的結果.因此,取值越大,表明樣本間差異越顯著.根據文獻[42]中的建議,當取值小于0.56,0.64,0.71 時,我們分別認為第1 組樣本和第2 組樣本之間差異較小、差異一般,或具有較大差異.

3.7 效度威脅

根據文獻[41]的指南,本節討論了本文實驗設計的局限以及對實驗結果效度可能產生的威脅和應對措施.

· 構造效度是指實驗與理論間的一致性.在基于搜索的軟件工程研究中,構造效度威脅主要來自于使用了不可靠的有效性度量[43].在本文的實驗中,主要包含兩個該類威脅.

1) 我們使用的評估候選體系結構設計方案質量的F-Score 度量是否能夠準確地度量設計方案的設計質量.為了緩解該效度威脅,在所有的設計問題(實例)中,當評價不同的自動化方法時,都使用了相同的適應度函數.此外,F-Score 度量的定義是基于信息檢索領域廣泛使用的準確率和召回率度量[39],從而緩解了F-Score 度量的構造效度威脅.

2) 針對同一設計問題,不同的架構師會給出不同的專家設計方案,因此,當專家方案由不同的架構師來設計時,自動化方法生成的候選體系結構方案的F-Score 會發生改變.但由于我們選取的設計問題(實例)以及相關的專家設計方案作為基準設計被廣泛采用[30?33],所以該效度威脅在一定程度上得以緩解.

· 內部效度指實驗的自變量和因變量之間存在明確因果關系或相關關系的程度,它表明因變量的變化在多大程度上來自自變量的影響.在本文的實驗中,我們并未研究沖突消解效率和設計質量提升是由什么因素造成,因此不需要考慮內部效度威脅.另一方面,通過比較CoEA-L和CoEA算法的運行時間差異,我們研究了性能開銷與學習運算子實現之間的因果關系.我們通過固定實驗相關的其他自變量,并采用30 次(多次)運行的方式,盡量消除其他可能變量產生的干擾.

· 外部效度是指實驗結果類推到其他環境的有效性,強調實驗結果是否具有普遍適應性.在基于搜索的軟件工程研究中,外部效度威脅主要來自于缺乏對目標設計問題進行清晰的定義、實驗設計問題的隨意性選擇、實驗選取的設計問題在規模等方面沒有差異[43].在本文的實驗設計中,通過使用3 個具有不同規模的設計問題來緩解外部效度威脅.選取的3 個設計問題在已有的相關研究中也被廣泛采用作為實驗案例[30?33].

· 結論效度是關于研究結果的數據分析與方法的有效性.在基于搜索的軟件工程研究中,結論效度威脅主要來自于使用了較少的設計問題進行實驗驗證、設計問題在規模或復雜度方面缺乏代表性、實驗中沒有考慮到生成數據的隨機性、缺乏有效的統計顯著性檢驗等[43].因此,采用更多不同規模、不同復雜度的設計問題(實例)進行實驗驗證,對于緩解結論效度威脅非常重要.在本文的實驗設計中,主要采取3 項措施來緩解結論效度威脅:1) 對每次實驗驗證采用多次重復實驗,從而盡可能消除實驗生成數據的隨機性;2) 通過文獻[41]中定義的標準實驗流程和統計顯著性檢驗方法,減少實驗過程中不規范的數據分析;3) 使用具有不同規模的設計問題進行實驗.同時,選取的設計問題的專家設計方案都是公開的,以便于重復驗證[26?29].

4 實驗結果和分析

本節基于上一節描述的實驗設計對3 個設計問題(實例)進行了實驗.實驗的結果及分析如下.

4.1 沖突頻率

利用第3.5 節提出的FC 度量指標,我們研究了職責種群個體和模式種群個體組合生成軟件體系結構候選方案時的沖突情況,如圖11 所示.

Fig.11 FC measurement for problem instances圖11 設計問題的FC 度量

從圖11 中可以看到,當職責種群個體和模式種群個體組合生成軟件體系結構候選方案時,對于3 個設計問題(實例)都存在大量的沖突.在所有的3 個設計問題中,FC度量的最小值都超過了40%,這意味著在職責種群個體和模式種群個體進行組合時,至少40%的組合會發生沖突.此外,從圖11 中我們還可以發現,相對于軟件規模較小的設計問題(CBS),較大的設計問題(GDS 和SCS)在合成過程中存在更多的沖突.這表明采用協作式協同演化方法進行面向模式的軟件體系結構候選方案合成時,有效的沖突消解至關重要,特別是對于規模較大的軟件系統.這個結果佐證了本文研究工作的研究價值和實用意義.

4.2 沖突消解效率

在圖12 中,針對3 個設計問題,我們給出了CoEA-L 在職責種群個體和模式種群個體產生沖突時的沖突消解效率.在所有的3 個設計問題中,ERI 度量的最小值均超過了70%,意味著70%以上的沖突都可以被CoEA-L方法有效地消解.而ERI 度量在3 個設計問題中的平均值接近90%,表明了在所有的30 次不同實例運行中產生的絕大多數沖突都可以被有效地消解.此外,在所有的3 個設計問題中,ERI 度量的最大值均能達到100%,表明針對這3 個設計問題的某些運行中,所有沖突都被成功消解.

Fig.12 ERI measurement for problem instances with the proposed approach圖12 本文方法用于不同設計問題得到的ERI 度量

我們希望進一步研究本文提出的沖突消解方法的沖突消解效率是否會受到設計問題規模的影響,我們提出了如下原假設.

· H01:CBS 設計問題的ERI 度量和GDS 設計問題的ERI 度量差異沒有統計意義上的顯著性.

· H02:CBS 設計問題的ERI 度量和SCS 設計問題的ERI 度量差異沒有統計意義上的顯著性.

· H03:GDS 設計問題的ERI 度量和SCS 設計問題的ERI 度量差異沒有統計意義上的顯著性.

針對每個設計問題(實例),30 次重復實驗得到的ERI 度量結果作為每個設計問題對應的ERI 度量值樣本,然后計算p值進行比較.每個原假設的p值見表5.從表5 可以看到,所有的p值都大于0.05,所以無法拒絕原假設,沒有證據表明,在不同規模的設計問題之間,沖突消解的效率存在差異.

Table 5 p-values for the hypotheses of insignificant difference on ERI metric between problem instances表5 不同設計問題間ERI 度量沒有統計差異的原假設p 值

基于上述實驗和統計分析結果,本文提出的CoEA-L 方法針對不同規模的設計問題都有較好的沖突消解效率;同時,設計問題本身的規模對該方法的沖突消解效率的影響較小.因此,本文提出的方法可以有效消解面向模式的軟件體系結構合成中產生的沖突,并且適用于解決實際應用中不同規模的設計問題,具有一定的適用性.

需要說明的是,由于3 種競爭方法在包含沖突的職責種群個體和模式種群個體進行組合時,沒有提供額外的沖突消解策略.因此3 種競爭方法的ERI 度量值始終為0.

4.3 軟件體系結構候選方案的設計質量

針對3 個設計問題,我們比較了CoEA-L 和3 種競爭方法所生成的候選軟件體系結構方案的F-Scoreps和F-Scorers的度量結果.實驗驗證過程針對每個設計問題,將每次實例運行生成的候選軟件體系結構方案與專家設計方案的相似度的平均值作為該次運行的相似度,從而得到該次實例運行的F-Score 值(相似度).

在表6 中,我們給出了在不同的設計問題中,CoEA-L 和CoEA 30 次實例運行得到的相似度的平均值、30次實例運行得到的相似度的中位數、不同方法統計差異顯著性的p值以及效應量.表6 的結果表明,針對軟件規模較小的設計問題(如CBS 實例),CoEA-L 和CoEA 都能生成接近專家方案的候選體系結構設計方案(F-Scorers和F-Scoreps的平均值和中位數都大于0.8),并且設計質量不存在明顯的差異(t-test 和U-test 得到的p值大于0.05).可能的原因是:(1) 規模較小的設計問題其解空間也較小,使得自動化生成的候選解決方案的設計質量差異較小;(2) 在較小規模的設計問題中,模式種群個體和職責種群個體進行組合時發生沖突的概率相對較少,因此減弱了引入學習效應對軟件體系結構候選方案設計質量的影響.

Table 6 CoEA-L vs.CoEA—Comparison in terms of the design quality metrics:F-Score for responsibility and pattern synthesis表6 職責合成和模式合成的設計質量度量F-Score 在CoEA-L 和CoEA 方法上的比較

針對規模相對較大的設計問題(如GDS 和SCS 實例),CoEA-L 和CoEA 也都能生成接近專家方案的候選體系結構設計方案.但是CoEA-L 能夠生成更接近專家方案的候選體系結構設計方案(F-Scorers和F-Scoreps的平均值和中位數都更大,并且p值小于0.05).可能的原因是:

1) 針對某一特定設計問題,適合該設計問題的較優的候選體系結構方案往往都包含適用于該設計問題的軟件體系結構知識.個體從模式種群和職責種群中學習,除了學習如何消解沖突外,也學習到種群中個體間共有的軟件體系結構知識,從而改善了設計質量.

2) 相對于較小規模的設計問題,較大規模的設計問題擁有更大的解空間,學習效應的引入,能夠更加有效地對解空間進行探索.

3) 相對于較小規模的設計問題,在較大規模的設計問題中,當職責種群個體和模式種群個體進行組合時,會發生更多的沖突.由于CoEA 只組合那些沒有沖突的個體,限制了候選體系結構方案的多樣性,從而影響了生成方案的設計質量.

綜上,當問題空間更加復雜時,CoEA-L 方法相對于CoEA 方法的優勢更明顯.對于規模較大的軟件系統,CoEA-L 能夠生成比CoEA 設計質量更高、更接近專家方案的候選體系結構設計方案.

在表7 中,我們給出了在不同的設計問題中,CoEA-L 和RS 30 次實例運行得到的相似度的平均值、30 次實例運行得到的相似度的中位數、不同方法統計差異顯著性的p值以及效應量.表7 的結果表明,針對3 個規模不同的設計問題,相對于RS,CoEA-L 都能生成更接近專家方案的候選體系結構設計方案(CoEA-L 方法生成的候選體系結構方案的均值和中位數都大于RS 方法生成的候選體系結構方案的均值和中位數;同時,t-test 和U-test 得到的p值遠小于0.000 1).值得注意的是,由CoEA-L 生成的候選體系結構方案的F-Score 值所組成的F-Score 樣本與由RS 生成的候選體系結構方案的F-Score 值所組成的F-Score 樣本之間的效應量的值始終為1.這意味著針對3 個規模不同的設計問題的任意一次實例運行中,CoEA-L 都優于RS.這說明:(1) 面向模式的軟件體系結構合成問題具有一定的復雜性,簡單的應用隨機搜索方法并不能獲得理想的結果;(2) 針對第3.1節提出的研究問題(RQ),實驗所選取的3 個設計實例都具備足夠的復雜性.

Table 7 CoEA-L vs.RS—Comparison in terms of the design quality metrics:F-Score for responsibility and pattern synthesis表7 職責合成和模式合成的設計質量度量F-Score 在CoEA-L 和RS 方法上的比較

在表8 中,我們給出了在不同的設計問題中,CoEA-L 和BO 30 次實例運行得到的相似度的平均值、30 次實例運行得到的相似度的中位數、不同方法統計差異顯著性的p值以及效應量.

Table 8 CoEA-L vs.BO—Comparison in terms of the design quality metrics:F-Score for responsibility and pattern synthesis表8 職責合成和模式合成的設計質量度量F-Score 在CoEA-L 和BO 方法上的比較

表8 的結果表明,針對軟件規模較大的設計問題(如GDS 和SCS 實例),CoEA-L 明顯優于BO(CoEA-L 方法生成的候選體系結構方案的均值和中位數都大于BO 方法生成的候選體系結構方案的均值和中位數;同時,得到的p值均小于0.000 1).其中,針對職責合成,由CoEA-L 生成的候選體系結構方案的F-Score 值所組成的F-Score 樣本優勢更加明顯(效應量的值為1).我們認為,由于我們的BO 方法實現將職責合成作為了外層優化問題,職責合成所生成的解決方案必須保證滿足模式合成問題生成的最優解的約束(因為在面向模式的軟件體系結構合成中,為了組合生成最終的解決方案,職責合成候選方案在與模式合成方案進行組合時不能有沖突,因此,這里的約束意味著外層職責合成生成的最優解不可與內層模式合成生成的最優解產生沖突),而BO 方法又不具備內外層優化問題沖突消解的機制,因此這限制了職責合成候選解決方案的多樣性.另一方面,在CoEA-L 中,雖然職責合成和模式合成的候選解之間也存在大量沖突(見第4.1 節),但由于具有較好的沖突消解效率(見第4.2 節),職責合成和模式合成候選解決方案的多樣性并不會受到限制,所以CoEA-L 具有更高的概率生成接近專家方案的候選體系結構設計方案.

4.4 運行開銷

在本小節中,我們使用3 個設計問題中復雜程度最高的SCS 來評估基于學習的協作式協同演化軟件體系結構合成方法和其他3 個競爭方法的系統運行開銷.我們采用兩種方式來評估各種方法的運行開銷.

· 首先,在第4.4.1 節中,我們根據第3.4 節描述的各方法的參數設置,通過固定各種方法適應度函數的總評估次數,比較各種方法的系統運行時間.在該評估方法中,由于不同方法間適應度函數的總評估次數相同,因此方法間運行時間的差異主要由方法內部的實現差異決定.例如,當適應度函數的總評估次數相同時,CoEA-L 與CoEA 將運行相同的種群代數;同時,由于兩種方法在種群的每一代中使用相同的選擇、交叉、突變運算子,則兩種方法運行時間的差異由CoEA-L 新增的學習運算子實現所決定.

· 此外,對于軟件架構師而言,自動化方法的一個重要優勢是能夠在盡可能短的時間向架構師提供可行的候選體系結構解決方案.因此在第4.4.2 節中,我們比較了不同方法生成可行候選體系結構方案的運行時間.

4.4.1 固定適應度函數評估次數的運行時間比較

在圖13 中,我們給出了不同方法在SCS 設計問題中進行相同次數的適應度函數評估所消耗的運行時間.針對每種方法,我們同樣運行30 次實例,圖13 中的箱線圖展示了每種方法30 次運行所消耗的運行時間的最大值、最小值和四分位.

Fig.13 Running time for CoEA-L and the three rival approaches with the same fitness evaluations圖13 CoEA-L 與3 種競爭方法進行相同次數適應度函數評估所消耗的時間

圖13 的結果表明,(1) 3 種競爭方法進行相同次數的適應度函數評估所消耗的運行時間差異不大;(2) 每種競爭方法內部30 次運行所消耗的運行時間幾乎沒有差異(最大值、最小值及四分位基本相等);(3) 本文提出的CoEA-L 與3 種競爭方法相比,完成相同次數的適應度函數評估需要消耗更多的運行時間;(4) CoEA-L 內部30次運行所消耗的運行時間存在一定的差異.我們認為,以上結果的原因是:由于適應度函數的評估次數固定,意味著對于CoEA,BO 和RS 而言,它們采用的算法每次運行的搜索次數是恒定的.同時,這3 種算法基本的搜索運算操作獨立于生成解,導致在不同的運行中,雖然可以生成不同的候選方案,但運行時間幾乎沒有差異.這里以CoEA 方法中的算法為例,在每一子代的生成中,該算法包含的選擇、交叉、突變運算子在任意的生成解上運行都不會有顯著的運行時間差異,而生成子代的數目確定,使得該算法不同運行所消耗的運行時間差異很小.另一方面,本文提出的CoEA-L 不同運行間存在較大的運行時間差異.我們認為,主要原因在于,CoEA-L 中,學習運算子進行學習消解沖突時,職責合成和模式合成生成的候選方案對沖突的消解效率具有較大的影響.每一次的實例運行由于生成了不同的職責合成和模式合成候選方案,導致了不同運行所消耗的運行時間有較大差異.

在圖13 中,通過比較CoEA-L 和CoEA 方法的算法運行時間差異,我們可以評估學習運算子的實際執行代價.通過比較兩種算法的運行時間可以發現,相比于選擇、交叉和突變運算子,學習運算子的執行代價較高.學習運算子的引入導致CoEA-L 相比于CoEA 方法的平均運行時間增長了2 倍以上.通過進一步分析,我們認為,CoEA-L 和CoEA 方法所采用算法的公共部分,即選擇、交叉和突變運算子的實現非常簡單,任一操作的平均時間復雜度不會超過O(n),而CoEA-L 方法中的學習運算子則由圖5 所示的4 個步驟組成,這些步驟的時間復雜度討論見第2.2.1 節～第2.2.4 節.

雖然本文提出的CoEA-L 方法在運行相同的適應度函數評估時性能開銷大于已有的方法,但在實際應用中,對于具有相當規模的設計問題(比如SCS),額外的性能開銷并不影響方法的實用性(額外6 秒左右的運行開銷不會影響方法的實用性),尤其是本文提出的CoEA-L 方法能夠有效地消解面向模式的軟件體系結構合成問題中產生的沖突(見第4.2 節)并能生成更優的候選體系結構解決方案(見第4.3 節).另一方面,在實際應用中,能夠盡快生成可行體系結構候選方案對架構師而言更具有實用性.在下一小節中,我們比較了不同方法生成可行候選體系結構方案的運行時間.

4.4.2 生成可行候選體系結構方案的運行時間比較

在圖14 中,我們給出了不同方法在SCS 設計問題中生成可行候選體系結構方案所消耗的運行時間.針對每種方法,我們同樣運行30 次實例,圖14 中的箱線圖展示了每種方法30 次運行所消耗的運行時間的最大值、最小值和四分位.圖14 的結果表明,本文提出的CoEA-L 相比3 種競爭方法,可以在更短的時間內生成可行的體系結構候選方案.我們認為,產生該結果的原因在于,CoEA-L 具有有效的沖突消解機制,當職責合成和模式合成候選方案存在沖突時,CoEA-L 可以立即消解沖突并迅速合成候選體系結構方案.

Fig.14 Running time for CoEA-L and the three rival approaches for generating feasible solutions圖14 CoEA-L 與3 種競爭方法生成可行體系結構方案所消耗的時間

綜上,我們認為,雖然本文提出的CoEA-L 相對于已有的3 種競爭方法會產生額外的性能開銷(見第4.4.1節),但并不影響該方法的實用性.另一方面,由于本文提出的方法具有有效的沖突消解機制(見第4.2 節),可以更快地生成可行的候選體系結構方案(見第4.4.2 節,即本小節),同時,生成的候選體系結構方案具有更優的設計質量(見第4.3 節).因此,本文提出的CoEA-L 方法與3 種競爭方法相比,具有較為明顯的優勢.

5 相關工作

目前有大量的相關研究關注于軟件體系結構設計中的沖突消解問題.在文獻[44]中,作者研究了軟件體系結構模型的不同版本之間合并時產生的沖突問題,并提供了沖突消解方法.文獻[44]中的方法可以自動發現軟件體系結構模型中需要更改的元素,從而消解沖突.該方法基于修復生成技術,通過檢測模型的靜態、動態結構,在準備合并的模型中建立一系列的修復操作,并在模型合并時消解沖突.與文獻[44]中的工作類似,本文提出的方法也是用來消解軟件體系結構的不同模型之間合并時產生的沖突(職責合成和模式合成模型).但不同于文獻[44],本文提出的沖突消解方法是用于不同類型模型之間的合并,而不是相同模型的不同版本之間的合并.

在發生沖突時,每個沖突都有其本質根源.而沖突的根源通常揭示了軟件體系結構模型中錯誤的來源.因此,在沖突消解之前了解沖突的根源非常重要.在文獻[45]中,作者分析了軟件體系結構中不一致設計規則的基本結構以及由此產生的相關行為.作者進而提出了一種算法來識別沖突產生的根源.與文獻[45]的工作重點不同,本文的工作并不是去嘗試發現軟件體系結構設計模型中的缺陷與錯誤,而是消解自動化體系結構合成中的沖突,因此無須分析職責合成種群個體與模式合成種群個體組合時的沖突根源.

由于沖突消解會造成軟件系統運行時額外的性能開銷,因此軟件體系結構設計和體系結構建模領域的許多研究重點關注于沖突檢測、沖突追蹤,而不是沖突消解.文獻[46]是其中比較有代表性的工作,作者提出了一種可以實時檢測和追蹤沖突的自動化方法.在該方法中,用戶只需要利用任意的形式化語言定義一致性規則,而自動化方法則可以偵測模型的變化是否違反這些自動化規則.與文獻[46]的工作類似,本文的工作也可以在職責種群個體和模式種群個體組合時檢測到存在的沖突,但是本文的工作不僅僅關注于沖突檢測,更關注于在職責種群個體和模式種群個體進行組合時,對檢測到的沖突進行消解.

在軟件體系結構領域,構件模型作為一種常見的視圖用于描述軟件體系結構.同時,已有的軟件體系結構研究通過對軟件體系結構設計決策進行建模,從而捕捉設計原理和軟件體系結構演化過程中的體系結構知識[47].當需要同時用構件模型和設計決策模型描述軟件體系結構設計時,可能造成構件模型、軟件體系結構設計決策模型、軟件體系結構設計之間的沖突.在文獻[48]中,作者提出了一種基于約束的方法來檢測設計決策和相關構件之間是否存在沖突.當決策模型發生改變時,文獻[48]提出的方法可以重新生成構件模型的約束,從而使得構件模型相應更新消解沖突.而文獻[49]則提出了一種軟件體系結構知識的轉換語言消解軟件體系結構設計決策模型和對應的軟件體系結構設計之間的沖突.不同于文獻[48,49]的工作,本文提出的方法通過學習的方式調整職責種群和模式種群個體,而不需要在職責種群和模式種群間建立顯式的復雜約束關系.

除了軟件構件模型和設計決策模型以外,在軟件體系結構領域,還有多種不同的視圖對軟件體系結構進行描述[3].消解不同類型視圖之間的沖突,對于軟件體系結構的理解具有重要的意義.在文獻[50]中,作者通過利用軟件體系結構中的層次結構信息,將不同的軟件體系結構視圖轉換成樹形結構.然后,作者利用提出的算法修正了樹形結構之間的不一致,實現了軟件體系結構視圖之間的沖突消解和視圖間差異化的顯示.與本文工作不同的是,本文主要關注軟件體系結構合成中候選解決方案的沖突消解.

針對軟件體系結構設計中產生的沖突,文獻[51]采用體系結構自動化重構的方法對沖突進行消解.作者通過結合使用形式化的沖突檢測技術以及搜索算法,自動發現適合消解沖突的重構操作集合.但是文獻[51]中候選的重構操作僅僅包含了類的移動重構操作,這限制了沖突消解的靈活性.類似文獻[51],本文提出的基于學習的協作式協同演化體系結構合成方法中也采用了自動化的搜索算法,但不同的是,本文通過在搜索算法中引入學習機制來消解沖突,種群個體間的學習并不限定于通過形式化方法定義的學習規則集合.

針對運行時的軟件體系結構,文獻[52]利用本體[53]、UML 建模語言[54]、著色Petri 網[55]建模技術,提出了一個描述系統結構及行為的一致性框架.該框架通過使用不同的建模技術,采用映射的方式在體系結構的不同構件和體系結構的不同視圖間建立關聯,從而確保軟件體系結構不同構件及視圖之間不存在沖突.類似于文獻[48],文獻[52]通過利用多種建模技術,采用形式化語言定義模型元素間的約束,來確保體系結構構件和視圖間的一致性.對于規模較為復雜的軟件體系結構模型,人工定義模型元素之間的約束極易出錯.本文所提出的CoEA-L 方法并不需要通過建模語言來定義不同模型間的約束關系進行沖突消解.

當前,許多大型軟件系統采用了面向服務的軟件體系結構技術(service-oriented architecture,簡稱SOA)[56]進行構建.為了促進SOA 的標準化及可復用性,針對不同的業務領域,軟件工程研究社區提出了SOA 的參考軟件體系結構[57].如何消解采用SOA 技術構建的軟件體系結構和相關參考軟件體系結構之間的沖突,是SOA 領域的重要研究問題.文獻[58]是其中比較有代表性的工作,文獻[58]通過利用自動化的映射技術,將軟件體系結構設計元素映射到SOA 參考軟件體系結構的不同角色上,通過參考軟件體系結構元素間的規則和約束,自動化修改軟件體系結構設計元素,從而消解軟件體系結構設計與相關參考軟件體系結構之間的沖突.與文獻[58]不同的是,本文提出的沖突消解方法不需要依賴業務領域的參考軟件體系結構.本文工作與相關工作的比較見表9.

Table 9 Comparison of our work with existing work.表9 本文工作與相關工作的比較

6 結束語

軟件體系結構合成活動連接了問題空間和解決方案空間,是軟件體系結構設計中的關鍵性活動.為了在軟件體系結構合成中復用已有的體系結構知識,架構師通常使用軟件體系結構模式進行面向模式的軟件體系結構合成.職責合成和模式合成是面向模式的軟件體系結構合成中的兩大主要活動.由于軟件系統規模不斷增大,軟件職責不斷增加,使得自動化進行職責合成和模式合成并組合生成候選軟件體系結構方案變得非常重要.但難點問題是:當組合職責合成和模式合成的設計方案時,如何消解設計方案之間的沖突.針對該問題,本文提出了基于學習的協作式協同演化軟件體系結構合成方法.該方法利用鮑德溫進化作為理論基礎,提出了學習運算子概念,擴展了協作式協同演化軟件體系結構合成方法[7].在本文中,我們通過在學習運算子中采用數據挖掘的關聯算法,自動化發現哪些軟件職責具有較高的概率在職責合成中被分配到相同的類或者哪些軟件職責具有較高的概率在模式合成中被分配到相同的模式角色.提取到的這些信息進而用于沖突消解.

為了驗證本文提出方法的有效性,我們使用了3 個不同規模的設計問題作為研究案例.實驗結果表明,與3種競爭方法相比,本文提出的方法能夠有效地消解沖突,并且能夠生成更加接近專家方案的候選軟件體系結構設計方案.

在下一步工作中,我們將針對3 個方面展開研究.1) 提升沖突消解的性能.一方面,在本文中,我們使用了數據關聯挖掘中的Apriori 算法,在下一步,我們嘗試對Apriori 算法及其參數進行進一步分析,并考慮使用其他數據關聯挖掘算法來提升沖突消解的性能;另一方面,基于搜索的軟件工程的最終目標之一是實現知識表示與處理的自動化[59],在下一步,我們將考慮如何在搜索過程中高效地表示和處理搜索過程中自動化產生的沖突消解相關知識,從而提升沖突消解性能.2) 使用更多不同規模、領域和復雜度的設計問題(實例)來評價本文提出的方法,考慮采用工業項目或開源項目.3) 基于本文提出的方法,實現面向模式的軟件體系結構合成的支撐工具,并將該工具集成到已有的設計工具或集成開發環境中.

作者注 本文是我們于2016 年2 月26 日投到《軟件學報》的論文.該文是武漢大學梁鵬老師(本文第二作者)指導的2018 屆(2018 年6 月)畢業的研究生徐永睿(本文第一作者)的博士論文《基于模式的軟件體系結構自動化合成》工作成果的一部分,特此說明.