徐永睿 , 梁 鵬

1(武漢大學(xué) 計(jì)算機(jī)學(xué)院,湖北 武漢 430072)

2(軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué)),湖北 武漢 430072)

軟件體系結(jié)構(gòu)作為控制軟件復(fù)雜性、提高軟件系統(tǒng)質(zhì)量的重要手段,日益受到軟件研究者和實(shí)踐者的關(guān)注,并發(fā)展成為軟件工程的一個(gè)重要的研究領(lǐng)域[1].在軟件體系結(jié)構(gòu)設(shè)計(jì)中,軟件體系結(jié)構(gòu)合成活動(dòng)通過(guò)將軟件體系結(jié)構(gòu)設(shè)計(jì)相關(guān)需求轉(zhuǎn)換成軟件體系結(jié)構(gòu)設(shè)計(jì)方案,連接了問(wèn)題空間和對(duì)應(yīng)的解空間,是軟件體系結(jié)構(gòu)設(shè)計(jì)中的核心活動(dòng)[2].但是在傳統(tǒng)的軟件體系結(jié)構(gòu)合成過(guò)程中,如何合成軟件體系結(jié)構(gòu)解決方案,極大地依賴(lài)于架構(gòu)師的設(shè)計(jì)經(jīng)驗(yàn).為了在軟件體系結(jié)構(gòu)合成中減少對(duì)架構(gòu)師經(jīng)驗(yàn)的依賴(lài),同時(shí)復(fù)用設(shè)計(jì)知識(shí),軟件體系結(jié)構(gòu)模式被廣泛地使用(如MVC、管道過(guò)濾器、分層模式等)[3].因此,面向模式的軟件體系結(jié)構(gòu)合成應(yīng)運(yùn)而生[4].盡管如此,軟件體系結(jié)構(gòu)模式的使用存在著一些困難和挑戰(zhàn):1) 如何將候選模式中的抽象設(shè)計(jì)元素映射到軟件體系結(jié)構(gòu)設(shè)計(jì)的具體實(shí)現(xiàn);2) 架構(gòu)師設(shè)計(jì)經(jīng)驗(yàn)的缺乏會(huì)導(dǎo)致在采用特定模式進(jìn)行軟件體系結(jié)構(gòu)設(shè)計(jì)時(shí),違背該模式的設(shè)計(jì)約束.另一方面,如何將軟件職責(zé)(即面向?qū)ο蠓治龅玫降男袨楹蛯傩?分配到類(lèi),也是軟件體系結(jié)構(gòu)合成中的一個(gè)難點(diǎn)問(wèn)題.目前已有大量研究關(guān)注于解決軟件職責(zé)的分配問(wèn)題[5,6],但這些研究都是獨(dú)立地考慮軟件職責(zé)的分配,而沒(méi)有考慮職責(zé)分配對(duì)軟件體系結(jié)構(gòu)設(shè)計(jì)質(zhì)量的影響(相同的職責(zé)分配在采用不同的模式時(shí),系統(tǒng)質(zhì)量需求的滿足可能完全不同).因此,面向模式的軟件體系結(jié)構(gòu)合成必須同時(shí)考慮軟件職責(zé)的分配以及系統(tǒng)質(zhì)量需求的滿足.

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

假設(shè)對(duì)包含5 個(gè)軟件職責(zé)(R1到R5)的設(shè)計(jì)問(wèn)題進(jìn)行軟件體系結(jié)構(gòu)合成.當(dāng)采用面向模式的軟件體系結(jié)構(gòu)合成時(shí),假設(shè)架構(gòu)師選擇分層模式來(lái)滿足該設(shè)計(jì)問(wèn)題的質(zhì)量需求,那么一個(gè)可能的職責(zé)合成方案rs如圖1(a)所示.在該職責(zé)合成方案中,5 個(gè)軟件職責(zé)被分配到2 個(gè)類(lèi)中.而一個(gè)可能的模式合成方案ps如圖1(b)所示.在該模式合成方案中,5 個(gè)職責(zé)被分配到分層模式的2 個(gè)層中.

當(dāng)架構(gòu)師需要組合職責(zé)合成的設(shè)計(jì)方案rs(如圖1(a)所示)和模式合成的設(shè)計(jì)方案ps(如圖1(b)所示),從而生成軟件體系結(jié)構(gòu)設(shè)計(jì)方案時(shí),必須確保rs和ps方案之間不存在沖突.在職責(zé)合成設(shè)計(jì)方案(如圖1(a)所示)中,R3與R1,R2被分配到同一個(gè)類(lèi)中,但在模式合成設(shè)計(jì)方案(如圖1(b)所示)中,R3與R1,R2卻被分配到分層模式的不同層中.因?yàn)橥粋€(gè)類(lèi)中的軟件職責(zé)應(yīng)該被分配到分層模式的同一層中,所以架構(gòu)師無(wú)法直接利用圖1(a)和圖1(b)的設(shè)計(jì)方案,組合生成最終面向模式的軟件體系結(jié)構(gòu)設(shè)計(jì)方案.如果架構(gòu)師需要利用rs和ps方案來(lái)生成體系結(jié)構(gòu)設(shè)計(jì)方案,則要對(duì)兩者之間的沖突進(jìn)行消解.例如在該例子中,架構(gòu)師可以調(diào)整職責(zé)合成的設(shè)計(jì)方案rs,將R3分配到Class 2 中;或者調(diào)整模式合成的設(shè)計(jì)方案ps,將R3分配到Layer 1 中.

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

為了解決面向模式軟件體系結(jié)構(gòu)合成中的沖突自動(dòng)化消解問(wèn)題,本文提出了基于學(xué)習(xí)的協(xié)作式協(xié)同演化軟件體系結(jié)構(gòu)合成方法(CoEA-L),用于消解職責(zé)合成和模式合成產(chǎn)生的設(shè)計(jì)方案組合時(shí)的潛在沖突.在本文中,我們基于鮑德溫進(jìn)化理論[10],提出了學(xué)習(xí)運(yùn)算子的概念,擴(kuò)展了傳統(tǒng)遺傳算法(genetic algorithm,簡(jiǎn)稱(chēng)GA)中的選擇、突變、交叉運(yùn)算子.通過(guò)在學(xué)習(xí)運(yùn)算子中采用一種關(guān)聯(lián)算法來(lái)發(fā)現(xiàn)職責(zé)合成種群和模式合成種群中個(gè)體間頻繁同時(shí)出現(xiàn)的軟件職責(zé),進(jìn)而利用提取到的知識(shí)消解ps和rs方案組合過(guò)程中產(chǎn)生的沖突.

本文的主要貢獻(xiàn)如下:在面向模式的軟件體系結(jié)構(gòu)合成問(wèn)題中,通過(guò)在搜索過(guò)程中使用關(guān)聯(lián)算法挖掘軟件職責(zé)間的關(guān)系,引入了職責(zé)合成與模式合成間的學(xué)習(xí)效應(yīng)作為解決方案空間的啟發(fā)式搜索方法,進(jìn)而消解職責(zé)合成和模式合成產(chǎn)生的設(shè)計(jì)方案間的沖突.同時(shí),不同于現(xiàn)有基于搜索的軟件工程(SBSE)研究試圖通過(guò)改進(jìn)對(duì)問(wèn)題的表達(dá),定義更好的適應(yīng)度函數(shù),或在搜索過(guò)程中采用更好的啟發(fā)式規(guī)則來(lái)提升候選解決方案的質(zhì)量[11],本文提出的方法利用個(gè)體間的關(guān)系來(lái)改進(jìn)候選方案的設(shè)計(jì)質(zhì)量.個(gè)體通過(guò)學(xué)習(xí)其他種群中個(gè)體的特征,從而提升個(gè)體設(shè)計(jì)解決方案的質(zhì)量.

本文第1 節(jié)介紹本文工作的相關(guān)研究背景.第2 節(jié)提出面向模式的軟件體系結(jié)構(gòu)合成中的沖突消解方法.第3 節(jié)說(shuō)明實(shí)驗(yàn)的設(shè)計(jì).第4 節(jié)給出實(shí)驗(yàn)結(jié)果和分析.第5 節(jié)介紹相關(guān)工作.第6 節(jié)總結(jié)全文及下一步工作.

1 研究背景

針對(duì)面向模式的軟件體系結(jié)構(gòu)候選設(shè)計(jì)方案的自動(dòng)化合成,本節(jié)介紹了我們之前的工作[7]中提出的CoEA方法.

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

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

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

Fig.2 CoEA for automated pattern-oriented architectural synthesis圖2 面向模式軟件體系結(jié)構(gòu)CoEA 自動(dòng)化合成方法

Fig.3 Representations of individuals in RS and PS populations圖3 職責(zé)和模式合成種群個(gè)體的表示實(shí)例

當(dāng)采用整數(shù)向量對(duì)兩個(gè)種群候選解決方案進(jìn)行編碼表示時(shí),需要處理以下問(wèn)題.

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

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

2) 計(jì)算種群適應(yīng)度(如圖2 的步驟2 所示).

在CoEA 方法中,職責(zé)合成種群和模式合成種群分別采用不同的適應(yīng)度函數(shù)計(jì)算種群內(nèi)個(gè)體的適應(yīng)度.針對(duì)職責(zé)合成,目前已有的職責(zé)合成相關(guān)研究文獻(xiàn)[5,6]均采用耦合[13]、內(nèi)聚[14]、復(fù)雜度[6]等指標(biāo)對(duì)候選方案進(jìn)行度量.根據(jù)文獻(xiàn)[15]中提出的系統(tǒng)獨(dú)立性原則,職責(zé)合成的適應(yīng)度函數(shù)如公式(1)所示.

適應(yīng)度RS=內(nèi)聚?耦合?復(fù)雜度 (1)

一個(gè)職責(zé)合成候選方案如果擁有較高的職責(zé)合成適應(yīng)度值,則意味著該方案擁有較高的設(shè)計(jì)質(zhì)量.每一指標(biāo)具體使用的度量見(jiàn)表1.

Table 1 Definitions of the metrics for RS表1 職責(zé)合成相關(guān)度量定義

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

該適應(yīng)度函數(shù)利用模式相關(guān)的度量計(jì)算出一個(gè)模式合成候選方案的模式約束違背代價(jià).一個(gè)模式合成候選方案如果擁有較低的模式合成適應(yīng)度值,則意味著該方案擁有較高的模式實(shí)現(xiàn)質(zhì)量.

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

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

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

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

3) 執(zhí)行選擇運(yùn)算子(如圖2 的步驟3 所示).

在CoEA 方法中,職責(zé)合成種群和模式合成種群選擇運(yùn)算子均使用錦標(biāo)賽選擇方法來(lái)選擇個(gè)體.相對(duì)于其他選擇方法,錦標(biāo)賽選擇更加高效且易于并行實(shí)現(xiàn)[21,22].在錦標(biāo)賽選擇方法中,隨機(jī)選擇種群中的任意兩個(gè)個(gè)體,并保留適應(yīng)度較優(yōu)的個(gè)體作為父代中的個(gè)體.重復(fù)該操作,直到父代中個(gè)體的數(shù)目等于種群數(shù)目.

4) 執(zhí)行交叉運(yùn)算子(如圖2 的步驟4 所示).

在CoEA 方法中,職責(zé)合成種群和模式合成種群交叉運(yùn)算子均使用單點(diǎn)交叉方法[22]從父代個(gè)體生成子代個(gè)體.在單點(diǎn)交叉方法中,父代個(gè)體的整數(shù)向量編碼隨機(jī)產(chǎn)生一個(gè)交叉位置,并根據(jù)該交叉位置交換配對(duì)的父代個(gè)體的整數(shù)向量表示,來(lái)生成子代個(gè)體.

5) 執(zhí)行突變運(yùn)算子(如圖2 的步驟5 所示).

在CoEA 方法中,職責(zé)合成種群和模式合成種群突變運(yùn)算子均使用交換突變方法讓子代個(gè)體產(chǎn)生變異.在交換突變方法中,個(gè)體的整數(shù)向量編碼隨機(jī)產(chǎn)生一個(gè)突變位置,并基于概率確定該位置是否需要突變.當(dāng)突變發(fā)生時(shí),隨機(jī)修改個(gè)體整數(shù)向量該位置的值.對(duì)于職責(zé)合成種群,交換突變意味著將候選方案rs的某一職責(zé)交換到不同的類(lèi)中;對(duì)于模式合成種群,交換突變意味著將候選方案ps的某一職責(zé)交換到不同的模式角色中.當(dāng)突變運(yùn)算子執(zhí)行完成后,職責(zé)合成和模式合成種群產(chǎn)生下一代個(gè)體.

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

在CoEA 方法中,通過(guò)組合職責(zé)合成和模式合成種群個(gè)體,產(chǎn)生面向模式軟件體系結(jié)構(gòu)的候選方案.需要強(qiáng)調(diào)的是,在CoEA 方法中,由于不存在有效的沖突消解機(jī)制,因此只能組合不包含沖突的rs和ps來(lái)產(chǎn)生體系結(jié)構(gòu)設(shè)計(jì)方案.

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

當(dāng)需要繼續(xù)迭代時(shí),針對(duì)職責(zé)合成和模式合成種群,CoEA 用子代種群更新當(dāng)前種群,從而跳轉(zhuǎn)到圖2 的步驟2 開(kāi)始新一輪迭代.

2 協(xié)作式協(xié)同演化軟件體系結(jié)構(gòu)合成中的沖突消解

本節(jié)首先介紹了基于學(xué)習(xí)的協(xié)作式協(xié)同演化軟件體系結(jié)構(gòu)合成方法(見(jiàn)第2.1 節(jié)),然后說(shuō)明了如何使用該方法自動(dòng)化消解面向模式的軟件體系結(jié)構(gòu)合成中產(chǎn)生的沖突(見(jiàn)第2.2 節(jié)).

2.1 基于學(xué)習(xí)的協(xié)作式協(xié)同演化體系結(jié)構(gòu)合成方法

在進(jìn)化生物學(xué)中,生命體的特征會(huì)隨著生命體與環(huán)境的交互而發(fā)生改變.鮑德溫在文獻(xiàn)[10]中研究了生命體具備的學(xué)習(xí)能力,提出了一種特別的生命體進(jìn)化機(jī)制.在該機(jī)制中,后代具備從環(huán)境中獲得新特征的學(xué)習(xí)能力,而不僅僅是直接依賴(lài)于繼承遺傳編碼所獲得的對(duì)應(yīng)特征.

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

Fig.4 Proposed approach for automated pattern-oriented architectural synthesis圖4 本文提出的面向模式軟件體系結(jié)構(gòu)自動(dòng)化合成方法

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

2.2 基于學(xué)習(xí)的協(xié)作式協(xié)同演化體系結(jié)構(gòu)合成方法中學(xué)習(xí)運(yùn)算子的實(shí)現(xiàn)

如圖5 所示,為了消解面向模式的軟件體系結(jié)構(gòu)合成中,職責(zé)種群個(gè)體和模式種群個(gè)體組合生成候選體系結(jié)構(gòu)方案時(shí)的沖突.學(xué)習(xí)運(yùn)算子主要由4 個(gè)步驟組成.

1) 提取種群信息數(shù)據(jù)集;

2) 生成種群頻繁項(xiàng)集;

3) 生成學(xué)習(xí)規(guī)則集;

4) 對(duì)組合的種群個(gè)體應(yīng)用學(xué)習(xí)規(guī)則消解沖突.

這4 個(gè)步驟以順序工作流的形式實(shí)現(xiàn)了圖4 中的學(xué)習(xí)運(yùn)算子(即圖4 中的步驟6),因此在后文中,我們以步驟6.1～步驟6.4 來(lái)標(biāo)示學(xué)習(xí)運(yùn)算子中的每個(gè)具體步驟.本小節(jié)的剩余部分將詳細(xì)介紹如何利用這4 個(gè)步驟來(lái)消解沖突(即第2.2.1 節(jié)～第2.2.4 節(jié)),并給出一個(gè)沖突消解實(shí)例(見(jiàn)第2.2.5 節(jié)).

Fig.5 Implementation of the learning operator圖5 學(xué)習(xí)運(yùn)算子的實(shí)現(xiàn)

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

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

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

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

在步驟6.2 中,我們使用了數(shù)據(jù)挖掘中的Apriori 關(guān)聯(lián)規(guī)則挖掘算法[23]從步驟6.1 提取出的職責(zé)種群信息數(shù)據(jù)集中生成職責(zé)種群的頻繁項(xiàng)集.提取出的職責(zé)種群頻繁項(xiàng)集將在步驟6.3 中生成學(xué)習(xí)規(guī)則集,便于模式種群個(gè)體在組合生成軟件體系結(jié)構(gòu)設(shè)計(jì)方案時(shí)學(xué)習(xí)以消解沖突.需要說(shuō)明的是,Apriori 算法主要的連接和剪枝操作具有較高的性能開(kāi)銷(xiāo),文獻(xiàn)[23]中對(duì)這些操作進(jìn)行了詳細(xì)的性能分析評(píng)估.

2.2.3 生成學(xué)習(xí)規(guī)則集(步驟6.3)

在步驟6.3 中,需要將提取出的職責(zé)種群信息數(shù)據(jù)集中的頻繁項(xiàng)集轉(zhuǎn)化成可以用于沖突消解的學(xué)習(xí)規(guī)則集.在頻繁項(xiàng)集中,我們只知道哪些軟件職責(zé)具有較高的概率被分配到同一個(gè)類(lèi),因此,頻繁項(xiàng)集中軟件職責(zé)之間的關(guān)系是相關(guān)關(guān)系.而在學(xué)習(xí)規(guī)則集中,必須把軟件職責(zé)的相關(guān)關(guān)系轉(zhuǎn)換成軟件職責(zé)間的因果關(guān)系,才能被用于后續(xù)的沖突消解.圖6 給出了本文提出的學(xué)習(xí)規(guī)則集生成算法.

Fig.6 Proposed algorithm for generating the rule set圖6 本文提出的學(xué)習(xí)規(guī)則集生成算法

在該算法中,針對(duì)職責(zé)種群頻繁項(xiàng)集中的每一個(gè)頻繁項(xiàng)fi,生成該頻繁項(xiàng)的所有非空子集構(gòu)成集合S,如算法第2 行所示.在第4 行中,對(duì)S集合中的每一元素s,生成形如“s?(fi?s)”的學(xué)習(xí)規(guī)則.fi?s構(gòu)成一個(gè)軟件職責(zé)集合,包括那些在頻繁集fi中但不在s中的軟件職責(zé).在算法第4 行中,大量的學(xué)習(xí)規(guī)則會(huì)被生成,因此,在算法第5行中,通過(guò)使用cosine度量來(lái)評(píng)估生成的學(xué)習(xí)規(guī)則和其對(duì)應(yīng)的頻繁項(xiàng)fi的相關(guān)性,從而在算法中僅保留那些具有學(xué)習(xí)意義的強(qiáng)關(guān)聯(lián)學(xué)習(xí)規(guī)則.

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

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

當(dāng)有多條規(guī)則可以被學(xué)習(xí)時(shí),優(yōu)先級(jí)最高的規(guī)則將會(huì)被學(xué)習(xí).最后,算法第8 行到第11 行對(duì)重復(fù)的規(guī)則進(jìn)行過(guò)濾.假設(shè)規(guī)則集中有兩條學(xué)習(xí)規(guī)則r1和r2,如果r1是r2的子集并且r1的cosine和置信度度量大于等于r2的cosine和置信度,那么算法將會(huì)從學(xué)習(xí)規(guī)則集中去除重復(fù)規(guī)則r2.步驟6.3 學(xué)習(xí)規(guī)則生成算法的最壞時(shí)間復(fù)雜度為O(n×2n).

2.2.4 應(yīng)用學(xué)習(xí)規(guī)則消解沖突(步驟6.4)

當(dāng)學(xué)習(xí)規(guī)則生成后,學(xué)習(xí)運(yùn)算子可以應(yīng)用生成的學(xué)習(xí)規(guī)則消解職責(zé)種群和模式種群個(gè)體組合生成軟件體系結(jié)構(gòu)候選方案時(shí)產(chǎn)生的沖突.圖7 給出了應(yīng)用學(xué)習(xí)規(guī)則的沖突消解算法.在該算法中,假定當(dāng)職責(zé)種群個(gè)體和模式種群個(gè)體的組合發(fā)生沖突時(shí),模式種群個(gè)體通過(guò)學(xué)習(xí)職責(zé)種群個(gè)體所產(chǎn)生的規(guī)則,從而自適應(yīng)地調(diào)整.換言之,當(dāng)檢測(cè)到?jīng)_突時(shí),由模式種群個(gè)體嘗試進(jìn)行沖突消解(反之,職責(zé)種群個(gè)體也可以通過(guò)學(xué)習(xí)模式種群個(gè)體所產(chǎn)生的規(guī)則來(lái)消解沖突).

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

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

2.2.5 方法示例

在本節(jié)中,我們采用引言部分提出的例子(包含5 個(gè)軟件職責(zé)R1～R5的體系結(jié)構(gòu)合成問(wèn)題),通過(guò)示例的方式進(jìn)一步解釋CoEA-L 中的步驟6.1～步驟6.4.需要說(shuō)明的是,實(shí)際軟件項(xiàng)目中的軟件職責(zé)數(shù)目非常巨大,這里的示例只是為了簡(jiǎn)潔地解釋CoEA-L 中步驟6.1～步驟6.4,因此,示例中假設(shè)只包含5 個(gè)軟件職責(zé).

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

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

Fig.8 Three possible individuals in responsibility population圖8 職責(zé)種群的3 個(gè)可能個(gè)體

在步驟6.2 的職責(zé)種群頻繁項(xiàng)集的生成中,假設(shè)架構(gòu)師定義的頻繁項(xiàng)集的閾值為2,那么圖8 生成的職責(zé)種群信息數(shù)據(jù)集{{R1,R2,R3},{R4,R5},{R1,R4},{R2,R3},{R5},{R1,R2,R3},{R4},{R5}}中,頻繁項(xiàng)集為{{R1,R2},{R1,R3},{R2,R3},{R1,R2,R3}}.因?yàn)樵谒卸?xiàng)集中,{R1,R2},{R1,R3}在職責(zé)種群信息數(shù)據(jù)集中出現(xiàn)次數(shù)等于頻繁項(xiàng)集的閾值(2),分別2 次出現(xiàn)在項(xiàng)集{R1,R2,R3}中,而{R2,R3}在職責(zé)種群信息數(shù)據(jù)集中出現(xiàn)3 次,2 次出現(xiàn)在項(xiàng)集{R1,R2,R3}中,1 次出現(xiàn)在{R2,R3}中.同時(shí),在該例子中不存在除{R1,R2,R3}以外的其他三元及三元以上的項(xiàng)集出現(xiàn)次數(shù)大于等于頻繁項(xiàng)集的閾值.由于頻繁項(xiàng)集的所有非空子集必然也是頻繁的,因此,步驟6.2 最終生成的職責(zé)種群頻繁項(xiàng)集只需要包含{R1,R2,R3}.

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

在步驟6.4 中,如圖9 所示,假設(shè)一個(gè)職責(zé)種群個(gè)體Indr和一個(gè)模式種群個(gè)體Indp嘗試進(jìn)行組合生成軟件體系結(jié)構(gòu)設(shè)計(jì)候選方案.同時(shí),假設(shè)步驟6.3 生成的職責(zé)種群學(xué)習(xí)規(guī)則集包含3 條不同優(yōu)先級(jí)的學(xué)習(xí)規(guī)則.當(dāng)Indr和Indp進(jìn)行組合時(shí),這兩個(gè)個(gè)體之間存在著兩個(gè)沖突:1) 因?yàn)樵诼氊?zé)種群個(gè)體Indr中,軟件職責(zé)R2和R3被分配到同一個(gè)類(lèi),所以與模式種群個(gè)體Indp中R2與R3被分配到分層模式的不同層產(chǎn)生沖突;2) 同理,R4與R5也產(chǎn)生沖突.因此,沖突消解算法需要利用職責(zé)種群學(xué)習(xí)規(guī)則集來(lái)調(diào)整模式種群個(gè)體Indp,從而消解Indp和Indr之間的所有沖突.

Fig.9 An initial state when indp and indr try to resolve inconsistencies圖9 職責(zé)種群個(gè)體indp 和模式種群個(gè)體indr 嘗試沖突消解時(shí)的初始狀態(tài)

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

Fig.10 Procedure of conflict resolution for Indp圖10 模式種群個(gè)體Indp 的沖突消解過(guò)程

3 實(shí)驗(yàn)設(shè)計(jì)

本節(jié)主要描述如何通過(guò)實(shí)驗(yàn)設(shè)計(jì)對(duì)本文所提出的方法進(jìn)行有效性驗(yàn)證,包括研究問(wèn)題的提出(第3.1 節(jié))、設(shè)計(jì)問(wèn)題的選擇(第3.2 節(jié))、競(jìng)爭(zhēng)方法介紹(第3.3 節(jié))、方法運(yùn)行參數(shù)的設(shè)置(第3.4 節(jié))以及對(duì)方法有效性評(píng)估的度量指標(biāo)(3.5 節(jié)).最后介紹了對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析的統(tǒng)計(jì)方法和檢驗(yàn)(第3.6 節(jié))以及效度威脅(第3.7 節(jié)).

3.1 研究問(wèn)題

我們提出3 個(gè)研究問(wèn)題(research question,簡(jiǎn)稱(chēng)RQ),用于驗(yàn)證本文所提出方法的有效性.

· RQ1:職責(zé)種群個(gè)體和模式種群個(gè)體組合生成軟件體系結(jié)構(gòu)候選方案時(shí),沖突發(fā)生的頻率?RQ1 驗(yàn)證本文提出的CoEA-L 方法是否具備研究意義:如果職責(zé)種群個(gè)體和模式種群個(gè)體組合時(shí)很少或基本不發(fā)生沖突,則嘗試進(jìn)行沖突消解的研究意義不大.RQ1 是驗(yàn)證我們所提出的方法意義的基本研究問(wèn)題.

· RQ2:基于學(xué)習(xí)的協(xié)作式協(xié)同演化軟件體系結(jié)構(gòu)合成方法是否可以在不同的問(wèn)題實(shí)例中有效的消解沖突?RQ2 主要研究CoEA-L 方法的有效性,即在多大程度上消解職責(zé)種群個(gè)體和模式種群個(gè)體組合時(shí)所產(chǎn)生的沖突.同時(shí),通過(guò)在不同規(guī)模的問(wèn)題實(shí)例上應(yīng)用本文提出的方法,RQ2 也研究了本文提出的方法是否具備一定的適用性.

· 余下的研究問(wèn)題RQ3 主要關(guān)注于本文所提出的CoEA-L 方法和其他競(jìng)爭(zhēng)方法(見(jiàn)第3.3 節(jié))在解決面向模式的軟件體系結(jié)構(gòu)合成問(wèn)題中的差異.RQ3 包含兩個(gè)子研究問(wèn)題.

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

? RQ3.2:基于學(xué)習(xí)的協(xié)作式協(xié)同演化軟件體系結(jié)構(gòu)合成方法相比于其他競(jìng)爭(zhēng)方法,是否具有顯著的額外系統(tǒng)開(kāi)銷(xiāo)?RQ3.2 主要研究不同方法用于解決面向模式的軟件體系結(jié)構(gòu)合成問(wèn)題時(shí)的系統(tǒng)性能開(kāi)銷(xiāo),在該研究問(wèn)題中,我們主要關(guān)注本文提出方法所引入的學(xué)習(xí)運(yùn)算子是否會(huì)顯著增加系統(tǒng)的性能開(kāi)銷(xiāo).如果額外增加的性能開(kāi)銷(xiāo)過(guò)大,將影響本文提出方法的實(shí)用性.

3.2 實(shí)驗(yàn)設(shè)計(jì)問(wèn)題

在實(shí)驗(yàn)驗(yàn)證中,我們選取了3 個(gè)設(shè)計(jì)問(wèn)題(實(shí)例)進(jìn)行驗(yàn)證,分別是電影院預(yù)訂系統(tǒng)(cinema booking system,簡(jiǎn)稱(chēng)CBS)[26]、畢業(yè)生管理系統(tǒng)(graduate development system,簡(jiǎn)稱(chēng)GDS)[27]和郵輪選擇系統(tǒng)(select cruises system,簡(jiǎn)稱(chēng)SCS)[28].選擇這3 個(gè)設(shè)計(jì)問(wèn)題進(jìn)行實(shí)驗(yàn)驗(yàn)證的理由如下.

1) 這3 個(gè)設(shè)計(jì)問(wèn)題非本文作者設(shè)計(jì),這樣可以減少實(shí)驗(yàn)結(jié)果可能存在的偏向性.

2) 這3 個(gè)系統(tǒng)的人工設(shè)計(jì)方案公開(kāi)[29],便于作為基準(zhǔn)設(shè)計(jì)與各種自動(dòng)化設(shè)計(jì)方法的結(jié)果進(jìn)行統(tǒng)一比較.

3) 軟件體系結(jié)構(gòu)合成領(lǐng)域已有研究工作[30?33]使用這些設(shè)計(jì)問(wèn)題來(lái)評(píng)估所提出的方法.

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

Table 3 Problem instances with their sizes表3 設(shè)計(jì)問(wèn)題(實(shí)例)的規(guī)模

3.3 競(jìng)爭(zhēng)方法介紹

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

3.4 實(shí)驗(yàn)參數(shù)設(shè)置

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

Table 4 Experimental parameter settings of studied approaches表4 方法運(yùn)行的實(shí)驗(yàn)參數(shù)設(shè)置

3.5 實(shí)驗(yàn)度量指標(biāo)

為回答第3.1 節(jié)提出的研究問(wèn)題(RQ),我們需要對(duì)實(shí)驗(yàn)組與對(duì)照組進(jìn)行了如下4 個(gè)方面的比較.

1) 職責(zé)種群個(gè)體和模式種群個(gè)體組合生成候選軟件體系結(jié)構(gòu)方案時(shí)沖突發(fā)生的頻率.

2) 當(dāng)沖突發(fā)生時(shí),不同方法能夠有效地進(jìn)行沖突消解的能力.

3) 不同方法生成的候選軟件體系結(jié)構(gòu)方案的設(shè)計(jì)質(zhì)量.

4) 不同方法運(yùn)行導(dǎo)致的系統(tǒng)性能開(kāi)銷(xiāo).

由于性能開(kāi)銷(xiāo)主要比較方法運(yùn)行時(shí)間,因此這里主要介紹與前3 個(gè)方面相關(guān)的實(shí)驗(yàn)度量指標(biāo).

1) FC(frequency of conflicts)度量

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

FC 度量的取值范圍為0～1,FC 比值越高,則職責(zé)種群個(gè)體和模式種群個(gè)體組合時(shí)發(fā)生沖突的概率越大.

2) ERI(effectiveness of resolving inconsistencies)度量

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

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

3) DQ(design quality of solution)度量

軟件體系結(jié)構(gòu)設(shè)計(jì)方案的設(shè)計(jì)質(zhì)量難以自動(dòng)化度量.通常,設(shè)計(jì)質(zhì)量是根據(jù)架構(gòu)師自身的設(shè)計(jì)經(jīng)驗(yàn)進(jìn)行主觀評(píng)價(jià).文獻(xiàn)[38]證實(shí):對(duì)于軟件設(shè)計(jì)質(zhì)量評(píng)估,目前依舊缺乏有效的自動(dòng)化度量指標(biāo).因此,我們參照軟件體系結(jié)構(gòu)合成領(lǐng)域相關(guān)文獻(xiàn)[6,32],采用將自動(dòng)化設(shè)計(jì)的軟件體系結(jié)構(gòu)候選方案與專(zhuān)家設(shè)計(jì)方案進(jìn)行相似度比較的方法來(lái)度量自動(dòng)化方案的設(shè)計(jì)質(zhì)量.我們認(rèn)為,專(zhuān)家設(shè)計(jì)方案能夠盡可能地滿足軟件設(shè)計(jì)原則,同時(shí),針對(duì)特定設(shè)計(jì)問(wèn)題,專(zhuān)家方案的軟件設(shè)計(jì)質(zhì)量能夠滿足設(shè)計(jì)需求.因此,自動(dòng)化生成的設(shè)計(jì)方案與專(zhuān)家設(shè)計(jì)方案的相似度越高,則可以認(rèn)為設(shè)計(jì)質(zhì)量越高.

本文所采用的實(shí)驗(yàn)設(shè)計(jì)問(wèn)題(見(jiàn)第3.2 節(jié))全部具有作為基準(zhǔn)設(shè)計(jì)的公開(kāi)的專(zhuān)家職責(zé)合成方案[29].根據(jù)專(zhuān)家職責(zé)合成方案類(lèi)及其依賴(lài)關(guān)系,形成以類(lèi)為節(jié)點(diǎn)、類(lèi)間依賴(lài)為邊的有向圖G,進(jìn)而對(duì)G執(zhí)行拓?fù)渑判?從而生成專(zhuān)家模式合成方案.在拓?fù)渑判蛑?最早找到的沒(méi)有前驅(qū)(入度為0)的節(jié)點(diǎn)構(gòu)成節(jié)點(diǎn)集合Vi,Vi中節(jié)點(diǎn)對(duì)應(yīng)的類(lèi)構(gòu)成采用分層模式的專(zhuān)家模式合成方案中的第i層(i>0).在G中刪除節(jié)點(diǎn)集合Vi及所有以Vi中節(jié)點(diǎn)為起點(diǎn)的有向邊后,找到的入度為0 的節(jié)點(diǎn)構(gòu)成節(jié)點(diǎn)集合Vi?1,Vi?1中節(jié)點(diǎn)對(duì)應(yīng)的類(lèi)構(gòu)成采用分層模式的專(zhuān)家模式合成方案中的第i?1 層.重復(fù)該過(guò)程,直到G=?.當(dāng)G中存在環(huán)導(dǎo)致無(wú)法找到入度為0 的節(jié)點(diǎn)時(shí),選擇入度最小出度最大的節(jié)點(diǎn)v連同v的所有前驅(qū)節(jié)點(diǎn)構(gòu)成節(jié)點(diǎn)集合Vi.

對(duì)于職責(zé)種群個(gè)體,我們使用F-Score 來(lái)比較該設(shè)計(jì)方案與專(zhuān)家職責(zé)合成方案的相似度.F-Score 的定義如公式(8)所示.

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

類(lèi)似地,我們?nèi)匀皇褂肍-Score 來(lái)計(jì)算模式種群個(gè)體和專(zhuān)家模式合成方案間的相似度.F-Score 的定義如公式(9)所示.

在公式(9)中,Rol表示專(zhuān)家設(shè)計(jì)方案中存在的所有模式角色,Ro表示模式合成自動(dòng)化生成的一個(gè)候選方案中的所有模式角色,而roli表示專(zhuān)家設(shè)計(jì)方案所用模式的某一特定模式角色,roi表示模式合成自動(dòng)化生成的一個(gè)候選方案所用模式的某一特定模式角色.

F-Score 公式可以對(duì)自動(dòng)化生成的任意軟件體系結(jié)構(gòu)設(shè)計(jì)方案計(jì)算其與專(zhuān)家方案的相似度,從而評(píng)估其設(shè)計(jì)質(zhì)量.通過(guò)評(píng)估種群中所有軟件體系結(jié)構(gòu)設(shè)計(jì)方案與專(zhuān)家方案的相似度,就可以評(píng)價(jià)不同方法生成的候選軟件體系結(jié)構(gòu)方案的設(shè)計(jì)質(zhì)量.

3.6 統(tǒng)計(jì)分析方法

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

3.7 效度威脅

根據(jù)文獻(xiàn)[41]的指南,本節(jié)討論了本文實(shí)驗(yàn)設(shè)計(jì)的局限以及對(duì)實(shí)驗(yàn)結(jié)果效度可能產(chǎn)生的威脅和應(yīng)對(duì)措施.

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

1) 我們使用的評(píng)估候選體系結(jié)構(gòu)設(shè)計(jì)方案質(zhì)量的F-Score 度量是否能夠準(zhǔn)確地度量設(shè)計(jì)方案的設(shè)計(jì)質(zhì)量.為了緩解該效度威脅,在所有的設(shè)計(jì)問(wèn)題(實(shí)例)中,當(dāng)評(píng)價(jià)不同的自動(dòng)化方法時(shí),都使用了相同的適應(yīng)度函數(shù).此外,F-Score 度量的定義是基于信息檢索領(lǐng)域廣泛使用的準(zhǔn)確率和召回率度量[39],從而緩解了F-Score 度量的構(gòu)造效度威脅.

2) 針對(duì)同一設(shè)計(jì)問(wèn)題,不同的架構(gòu)師會(huì)給出不同的專(zhuān)家設(shè)計(jì)方案,因此,當(dāng)專(zhuān)家方案由不同的架構(gòu)師來(lái)設(shè)計(jì)時(shí),自動(dòng)化方法生成的候選體系結(jié)構(gòu)方案的F-Score 會(huì)發(fā)生改變.但由于我們選取的設(shè)計(jì)問(wèn)題(實(shí)例)以及相關(guān)的專(zhuān)家設(shè)計(jì)方案作為基準(zhǔn)設(shè)計(jì)被廣泛采用[30?33],所以該效度威脅在一定程度上得以緩解.

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

· 外部效度是指實(shí)驗(yàn)結(jié)果類(lèi)推到其他環(huán)境的有效性,強(qiáng)調(diào)實(shí)驗(yàn)結(jié)果是否具有普遍適應(yīng)性.在基于搜索的軟件工程研究中,外部效度威脅主要來(lái)自于缺乏對(duì)目標(biāo)設(shè)計(jì)問(wèn)題進(jìn)行清晰的定義、實(shí)驗(yàn)設(shè)計(jì)問(wèn)題的隨意性選擇、實(shí)驗(yàn)選取的設(shè)計(jì)問(wèn)題在規(guī)模等方面沒(méi)有差異[43].在本文的實(shí)驗(yàn)設(shè)計(jì)中,通過(guò)使用3 個(gè)具有不同規(guī)模的設(shè)計(jì)問(wèn)題來(lái)緩解外部效度威脅.選取的3 個(gè)設(shè)計(jì)問(wèn)題在已有的相關(guān)研究中也被廣泛采用作為實(shí)驗(yàn)案例[30?33].

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

4 實(shí)驗(yàn)結(jié)果和分析

本節(jié)基于上一節(jié)描述的實(shí)驗(yàn)設(shè)計(jì)對(duì)3 個(gè)設(shè)計(jì)問(wèn)題(實(shí)例)進(jìn)行了實(shí)驗(yàn).實(shí)驗(yàn)的結(jié)果及分析如下.

4.1 沖突頻率

利用第3.5 節(jié)提出的FC 度量指標(biāo),我們研究了職責(zé)種群個(gè)體和模式種群個(gè)體組合生成軟件體系結(jié)構(gòu)候選方案時(shí)的沖突情況,如圖11 所示.

Fig.11 FC measurement for problem instances圖11 設(shè)計(jì)問(wèn)題的FC 度量

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

4.2 沖突消解效率

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

Fig.12 ERI measurement for problem instances with the proposed approach圖12 本文方法用于不同設(shè)計(jì)問(wèn)題得到的ERI 度量

我們希望進(jìn)一步研究本文提出的沖突消解方法的沖突消解效率是否會(huì)受到設(shè)計(jì)問(wèn)題規(guī)模的影響,我們提出了如下原假設(shè).

· H01:CBS 設(shè)計(jì)問(wèn)題的ERI 度量和GDS 設(shè)計(jì)問(wèn)題的ERI 度量差異沒(méi)有統(tǒng)計(jì)意義上的顯著性.

· H02:CBS 設(shè)計(jì)問(wèn)題的ERI 度量和SCS 設(shè)計(jì)問(wèn)題的ERI 度量差異沒(méi)有統(tǒng)計(jì)意義上的顯著性.

· H03:GDS 設(shè)計(jì)問(wèn)題的ERI 度量和SCS 設(shè)計(jì)問(wèn)題的ERI 度量差異沒(méi)有統(tǒng)計(jì)意義上的顯著性.

針對(duì)每個(gè)設(shè)計(jì)問(wèn)題(實(shí)例),30 次重復(fù)實(shí)驗(yàn)得到的ERI 度量結(jié)果作為每個(gè)設(shè)計(jì)問(wèn)題對(duì)應(yīng)的ERI 度量值樣本,然后計(jì)算p值進(jìn)行比較.每個(gè)原假設(shè)的p值見(jiàn)表5.從表5 可以看到,所有的p值都大于0.05,所以無(wú)法拒絕原假設(shè),沒(méi)有證據(jù)表明,在不同規(guī)模的設(shè)計(jì)問(wèn)題之間,沖突消解的效率存在差異.

Table 5 p-values for the hypotheses of insignificant difference on ERI metric between problem instances表5 不同設(shè)計(jì)問(wèn)題間ERI 度量沒(méi)有統(tǒng)計(jì)差異的原假設(shè)p 值

基于上述實(shí)驗(yàn)和統(tǒng)計(jì)分析結(jié)果,本文提出的CoEA-L 方法針對(duì)不同規(guī)模的設(shè)計(jì)問(wèn)題都有較好的沖突消解效率;同時(shí),設(shè)計(jì)問(wèn)題本身的規(guī)模對(duì)該方法的沖突消解效率的影響較小.因此,本文提出的方法可以有效消解面向模式的軟件體系結(jié)構(gòu)合成中產(chǎn)生的沖突,并且適用于解決實(shí)際應(yīng)用中不同規(guī)模的設(shè)計(jì)問(wèn)題,具有一定的適用性.

需要說(shuō)明的是,由于3 種競(jìng)爭(zhēng)方法在包含沖突的職責(zé)種群個(gè)體和模式種群個(gè)體進(jìn)行組合時(shí),沒(méi)有提供額外的沖突消解策略.因此3 種競(jìng)爭(zhēng)方法的ERI 度量值始終為0.

4.3 軟件體系結(jié)構(gòu)候選方案的設(shè)計(jì)質(zhì)量

針對(duì)3 個(gè)設(shè)計(jì)問(wèn)題,我們比較了CoEA-L 和3 種競(jìng)爭(zhēng)方法所生成的候選軟件體系結(jié)構(gòu)方案的F-Scoreps和F-Scorers的度量結(jié)果.實(shí)驗(yàn)驗(yàn)證過(guò)程針對(duì)每個(gè)設(shè)計(jì)問(wèn)題,將每次實(shí)例運(yùn)行生成的候選軟件體系結(jié)構(gòu)方案與專(zhuān)家設(shè)計(jì)方案的相似度的平均值作為該次運(yùn)行的相似度,從而得到該次實(shí)例運(yùn)行的F-Score 值(相似度).

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

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

針對(duì)規(guī)模相對(duì)較大的設(shè)計(jì)問(wèn)題(如GDS 和SCS 實(shí)例),CoEA-L 和CoEA 也都能生成接近專(zhuān)家方案的候選體系結(jié)構(gòu)設(shè)計(jì)方案.但是CoEA-L 能夠生成更接近專(zhuān)家方案的候選體系結(jié)構(gòu)設(shè)計(jì)方案(F-Scorers和F-Scoreps的平均值和中位數(shù)都更大,并且p值小于0.05).可能的原因是:

1) 針對(duì)某一特定設(shè)計(jì)問(wèn)題,適合該設(shè)計(jì)問(wèn)題的較優(yōu)的候選體系結(jié)構(gòu)方案往往都包含適用于該設(shè)計(jì)問(wèn)題的軟件體系結(jié)構(gòu)知識(shí).個(gè)體從模式種群和職責(zé)種群中學(xué)習(xí),除了學(xué)習(xí)如何消解沖突外,也學(xué)習(xí)到種群中個(gè)體間共有的軟件體系結(jié)構(gòu)知識(shí),從而改善了設(shè)計(jì)質(zhì)量.

2) 相對(duì)于較小規(guī)模的設(shè)計(jì)問(wèn)題,較大規(guī)模的設(shè)計(jì)問(wèn)題擁有更大的解空間,學(xué)習(xí)效應(yīng)的引入,能夠更加有效地對(duì)解空間進(jìn)行探索.

3) 相對(duì)于較小規(guī)模的設(shè)計(jì)問(wèn)題,在較大規(guī)模的設(shè)計(jì)問(wèn)題中,當(dāng)職責(zé)種群個(gè)體和模式種群個(gè)體進(jìn)行組合時(shí),會(huì)發(fā)生更多的沖突.由于CoEA 只組合那些沒(méi)有沖突的個(gè)體,限制了候選體系結(jié)構(gòu)方案的多樣性,從而影響了生成方案的設(shè)計(jì)質(zhì)量.

綜上,當(dāng)問(wèn)題空間更加復(fù)雜時(shí),CoEA-L 方法相對(duì)于CoEA 方法的優(yōu)勢(shì)更明顯.對(duì)于規(guī)模較大的軟件系統(tǒng),CoEA-L 能夠生成比CoEA 設(shè)計(jì)質(zhì)量更高、更接近專(zhuān)家方案的候選體系結(jié)構(gòu)設(shè)計(jì)方案.

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

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

在表8 中,我們給出了在不同的設(shè)計(jì)問(wèn)題中,CoEA-L 和BO 30 次實(shí)例運(yùn)行得到的相似度的平均值、30 次實(shí)例運(yùn)行得到的相似度的中位數(shù)、不同方法統(tǒng)計(jì)差異顯著性的p值以及效應(yīng)量.

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

表8 的結(jié)果表明,針對(duì)軟件規(guī)模較大的設(shè)計(jì)問(wèn)題(如GDS 和SCS 實(shí)例),CoEA-L 明顯優(yōu)于BO(CoEA-L 方法生成的候選體系結(jié)構(gòu)方案的均值和中位數(shù)都大于BO 方法生成的候選體系結(jié)構(gòu)方案的均值和中位數(shù);同時(shí),得到的p值均小于0.000 1).其中,針對(duì)職責(zé)合成,由CoEA-L 生成的候選體系結(jié)構(gòu)方案的F-Score 值所組成的F-Score 樣本優(yōu)勢(shì)更加明顯(效應(yīng)量的值為1).我們認(rèn)為,由于我們的BO 方法實(shí)現(xiàn)將職責(zé)合成作為了外層優(yōu)化問(wèn)題,職責(zé)合成所生成的解決方案必須保證滿足模式合成問(wèn)題生成的最優(yōu)解的約束(因?yàn)樵诿嫦蚰Ｊ降能浖w系結(jié)構(gòu)合成中,為了組合生成最終的解決方案,職責(zé)合成候選方案在與模式合成方案進(jìn)行組合時(shí)不能有沖突,因此,這里的約束意味著外層職責(zé)合成生成的最優(yōu)解不可與內(nèi)層模式合成生成的最優(yōu)解產(chǎn)生沖突),而B(niǎo)O 方法又不具備內(nèi)外層優(yōu)化問(wèn)題沖突消解的機(jī)制,因此這限制了職責(zé)合成候選解決方案的多樣性.另一方面,在CoEA-L 中,雖然職責(zé)合成和模式合成的候選解之間也存在大量沖突(見(jiàn)第4.1 節(jié)),但由于具有較好的沖突消解效率(見(jiàn)第4.2 節(jié)),職責(zé)合成和模式合成候選解決方案的多樣性并不會(huì)受到限制,所以CoEA-L 具有更高的概率生成接近專(zhuān)家方案的候選體系結(jié)構(gòu)設(shè)計(jì)方案.

4.4 運(yùn)行開(kāi)銷(xiāo)

在本小節(jié)中,我們使用3 個(gè)設(shè)計(jì)問(wèn)題中復(fù)雜程度最高的SCS 來(lái)評(píng)估基于學(xué)習(xí)的協(xié)作式協(xié)同演化軟件體系結(jié)構(gòu)合成方法和其他3 個(gè)競(jìng)爭(zhēng)方法的系統(tǒng)運(yùn)行開(kāi)銷(xiāo).我們采用兩種方式來(lái)評(píng)估各種方法的運(yùn)行開(kāi)銷(xiāo).

· 首先,在第4.4.1 節(jié)中,我們根據(jù)第3.4 節(jié)描述的各方法的參數(shù)設(shè)置,通過(guò)固定各種方法適應(yīng)度函數(shù)的總評(píng)估次數(shù),比較各種方法的系統(tǒng)運(yùn)行時(shí)間.在該評(píng)估方法中,由于不同方法間適應(yīng)度函數(shù)的總評(píng)估次數(shù)相同,因此方法間運(yùn)行時(shí)間的差異主要由方法內(nèi)部的實(shí)現(xiàn)差異決定.例如,當(dāng)適應(yīng)度函數(shù)的總評(píng)估次數(shù)相同時(shí),CoEA-L 與CoEA 將運(yùn)行相同的種群代數(shù);同時(shí),由于兩種方法在種群的每一代中使用相同的選擇、交叉、突變運(yùn)算子,則兩種方法運(yùn)行時(shí)間的差異由CoEA-L 新增的學(xué)習(xí)運(yùn)算子實(shí)現(xiàn)所決定.

· 此外,對(duì)于軟件架構(gòu)師而言,自動(dòng)化方法的一個(gè)重要優(yōu)勢(shì)是能夠在盡可能短的時(shí)間向架構(gòu)師提供可行的候選體系結(jié)構(gòu)解決方案.因此在第4.4.2 節(jié)中,我們比較了不同方法生成可行候選體系結(jié)構(gòu)方案的運(yùn)行時(shí)間.

4.4.1 固定適應(yīng)度函數(shù)評(píng)估次數(shù)的運(yùn)行時(shí)間比較

在圖13 中,我們給出了不同方法在SCS 設(shè)計(jì)問(wèn)題中進(jìn)行相同次數(shù)的適應(yīng)度函數(shù)評(píng)估所消耗的運(yùn)行時(shí)間.針對(duì)每種方法,我們同樣運(yùn)行30 次實(shí)例,圖13 中的箱線圖展示了每種方法30 次運(yùn)行所消耗的運(yùn)行時(shí)間的最大值、最小值和四分位.

Fig.13 Running time for CoEA-L and the three rival approaches with the same fitness evaluations圖13 CoEA-L 與3 種競(jìng)爭(zhēng)方法進(jìn)行相同次數(shù)適應(yīng)度函數(shù)評(píng)估所消耗的時(shí)間

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

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

雖然本文提出的CoEA-L 方法在運(yùn)行相同的適應(yīng)度函數(shù)評(píng)估時(shí)性能開(kāi)銷(xiāo)大于已有的方法,但在實(shí)際應(yīng)用中,對(duì)于具有相當(dāng)規(guī)模的設(shè)計(jì)問(wèn)題(比如SCS),額外的性能開(kāi)銷(xiāo)并不影響方法的實(shí)用性(額外6 秒左右的運(yùn)行開(kāi)銷(xiāo)不會(huì)影響方法的實(shí)用性),尤其是本文提出的CoEA-L 方法能夠有效地消解面向模式的軟件體系結(jié)構(gòu)合成問(wèn)題中產(chǎn)生的沖突(見(jiàn)第4.2 節(jié))并能生成更優(yōu)的候選體系結(jié)構(gòu)解決方案(見(jiàn)第4.3 節(jié)).另一方面,在實(shí)際應(yīng)用中,能夠盡快生成可行體系結(jié)構(gòu)候選方案對(duì)架構(gòu)師而言更具有實(shí)用性.在下一小節(jié)中,我們比較了不同方法生成可行候選體系結(jié)構(gòu)方案的運(yùn)行時(shí)間.

4.4.2 生成可行候選體系結(jié)構(gòu)方案的運(yùn)行時(shí)間比較

在圖14 中,我們給出了不同方法在SCS 設(shè)計(jì)問(wèn)題中生成可行候選體系結(jié)構(gòu)方案所消耗的運(yùn)行時(shí)間.針對(duì)每種方法,我們同樣運(yùn)行30 次實(shí)例,圖14 中的箱線圖展示了每種方法30 次運(yùn)行所消耗的運(yùn)行時(shí)間的最大值、最小值和四分位.圖14 的結(jié)果表明,本文提出的CoEA-L 相比3 種競(jìng)爭(zhēng)方法,可以在更短的時(shí)間內(nèi)生成可行的體系結(jié)構(gòu)候選方案.我們認(rèn)為,產(chǎn)生該結(jié)果的原因在于,CoEA-L 具有有效的沖突消解機(jī)制,當(dāng)職責(zé)合成和模式合成候選方案存在沖突時(shí),CoEA-L 可以立即消解沖突并迅速合成候選體系結(jié)構(gòu)方案.

Fig.14 Running time for CoEA-L and the three rival approaches for generating feasible solutions圖14 CoEA-L 與3 種競(jìng)爭(zhēng)方法生成可行體系結(jié)構(gòu)方案所消耗的時(shí)間

綜上,我們認(rèn)為,雖然本文提出的CoEA-L 相對(duì)于已有的3 種競(jìng)爭(zhēng)方法會(huì)產(chǎn)生額外的性能開(kāi)銷(xiāo)(見(jiàn)第4.4.1節(jié)),但并不影響該方法的實(shí)用性.另一方面,由于本文提出的方法具有有效的沖突消解機(jī)制(見(jiàn)第4.2 節(jié)),可以更快地生成可行的候選體系結(jié)構(gòu)方案(見(jiàn)第4.4.2 節(jié),即本小節(jié)),同時(shí),生成的候選體系結(jié)構(gòu)方案具有更優(yōu)的設(shè)計(jì)質(zhì)量(見(jiàn)第4.3 節(jié)).因此,本文提出的CoEA-L 方法與3 種競(jìng)爭(zhēng)方法相比,具有較為明顯的優(yōu)勢(shì).

5 相關(guān)工作

目前有大量的相關(guān)研究關(guān)注于軟件體系結(jié)構(gòu)設(shè)計(jì)中的沖突消解問(wèn)題.在文獻(xiàn)[44]中,作者研究了軟件體系結(jié)構(gòu)模型的不同版本之間合并時(shí)產(chǎn)生的沖突問(wèn)題,并提供了沖突消解方法.文獻(xiàn)[44]中的方法可以自動(dòng)發(fā)現(xiàn)軟件體系結(jié)構(gòu)模型中需要更改的元素,從而消解沖突.該方法基于修復(fù)生成技術(shù),通過(guò)檢測(cè)模型的靜態(tài)、動(dòng)態(tài)結(jié)構(gòu),在準(zhǔn)備合并的模型中建立一系列的修復(fù)操作,并在模型合并時(shí)消解沖突.與文獻(xiàn)[44]中的工作類(lèi)似,本文提出的方法也是用來(lái)消解軟件體系結(jié)構(gòu)的不同模型之間合并時(shí)產(chǎn)生的沖突(職責(zé)合成和模式合成模型).但不同于文獻(xiàn)[44],本文提出的沖突消解方法是用于不同類(lèi)型模型之間的合并,而不是相同模型的不同版本之間的合并.

在發(fā)生沖突時(shí),每個(gè)沖突都有其本質(zhì)根源.而沖突的根源通常揭示了軟件體系結(jié)構(gòu)模型中錯(cuò)誤的來(lái)源.因此,在沖突消解之前了解沖突的根源非常重要.在文獻(xiàn)[45]中,作者分析了軟件體系結(jié)構(gòu)中不一致設(shè)計(jì)規(guī)則的基本結(jié)構(gòu)以及由此產(chǎn)生的相關(guān)行為.作者進(jìn)而提出了一種算法來(lái)識(shí)別沖突產(chǎn)生的根源.與文獻(xiàn)[45]的工作重點(diǎn)不同,本文的工作并不是去嘗試發(fā)現(xiàn)軟件體系結(jié)構(gòu)設(shè)計(jì)模型中的缺陷與錯(cuò)誤,而是消解自動(dòng)化體系結(jié)構(gòu)合成中的沖突,因此無(wú)須分析職責(zé)合成種群個(gè)體與模式合成種群個(gè)體組合時(shí)的沖突根源.

由于沖突消解會(huì)造成軟件系統(tǒng)運(yùn)行時(shí)額外的性能開(kāi)銷(xiāo),因此軟件體系結(jié)構(gòu)設(shè)計(jì)和體系結(jié)構(gòu)建模領(lǐng)域的許多研究重點(diǎn)關(guān)注于沖突檢測(cè)、沖突追蹤,而不是沖突消解.文獻(xiàn)[46]是其中比較有代表性的工作,作者提出了一種可以實(shí)時(shí)檢測(cè)和追蹤沖突的自動(dòng)化方法.在該方法中,用戶只需要利用任意的形式化語(yǔ)言定義一致性規(guī)則,而自動(dòng)化方法則可以偵測(cè)模型的變化是否違反這些自動(dòng)化規(guī)則.與文獻(xiàn)[46]的工作類(lèi)似,本文的工作也可以在職責(zé)種群個(gè)體和模式種群個(gè)體組合時(shí)檢測(cè)到存在的沖突,但是本文的工作不僅僅關(guān)注于沖突檢測(cè),更關(guān)注于在職責(zé)種群個(gè)體和模式種群個(gè)體進(jìn)行組合時(shí),對(duì)檢測(cè)到的沖突進(jìn)行消解.

在軟件體系結(jié)構(gòu)領(lǐng)域,構(gòu)件模型作為一種常見(jiàn)的視圖用于描述軟件體系結(jié)構(gòu).同時(shí),已有的軟件體系結(jié)構(gòu)研究通過(guò)對(duì)軟件體系結(jié)構(gòu)設(shè)計(jì)決策進(jìn)行建模,從而捕捉設(shè)計(jì)原理和軟件體系結(jié)構(gòu)演化過(guò)程中的體系結(jié)構(gòu)知識(shí)[47].當(dāng)需要同時(shí)用構(gòu)件模型和設(shè)計(jì)決策模型描述軟件體系結(jié)構(gòu)設(shè)計(jì)時(shí),可能造成構(gòu)件模型、軟件體系結(jié)構(gòu)設(shè)計(jì)決策模型、軟件體系結(jié)構(gòu)設(shè)計(jì)之間的沖突.在文獻(xiàn)[48]中,作者提出了一種基于約束的方法來(lái)檢測(cè)設(shè)計(jì)決策和相關(guān)構(gòu)件之間是否存在沖突.當(dāng)決策模型發(fā)生改變時(shí),文獻(xiàn)[48]提出的方法可以重新生成構(gòu)件模型的約束,從而使得構(gòu)件模型相應(yīng)更新消解沖突.而文獻(xiàn)[49]則提出了一種軟件體系結(jié)構(gòu)知識(shí)的轉(zhuǎn)換語(yǔ)言消解軟件體系結(jié)構(gòu)設(shè)計(jì)決策模型和對(duì)應(yīng)的軟件體系結(jié)構(gòu)設(shè)計(jì)之間的沖突.不同于文獻(xiàn)[48,49]的工作,本文提出的方法通過(guò)學(xué)習(xí)的方式調(diào)整職責(zé)種群和模式種群個(gè)體,而不需要在職責(zé)種群和模式種群間建立顯式的復(fù)雜約束關(guān)系.

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

針對(duì)軟件體系結(jié)構(gòu)設(shè)計(jì)中產(chǎn)生的沖突,文獻(xiàn)[51]采用體系結(jié)構(gòu)自動(dòng)化重構(gòu)的方法對(duì)沖突進(jìn)行消解.作者通過(guò)結(jié)合使用形式化的沖突檢測(cè)技術(shù)以及搜索算法,自動(dòng)發(fā)現(xiàn)適合消解沖突的重構(gòu)操作集合.但是文獻(xiàn)[51]中候選的重構(gòu)操作僅僅包含了類(lèi)的移動(dòng)重構(gòu)操作,這限制了沖突消解的靈活性.類(lèi)似文獻(xiàn)[51],本文提出的基于學(xué)習(xí)的協(xié)作式協(xié)同演化體系結(jié)構(gòu)合成方法中也采用了自動(dòng)化的搜索算法,但不同的是,本文通過(guò)在搜索算法中引入學(xué)習(xí)機(jī)制來(lái)消解沖突,種群個(gè)體間的學(xué)習(xí)并不限定于通過(guò)形式化方法定義的學(xué)習(xí)規(guī)則集合.

針對(duì)運(yùn)行時(shí)的軟件體系結(jié)構(gòu),文獻(xiàn)[52]利用本體[53]、UML 建模語(yǔ)言[54]、著色Petri 網(wǎng)[55]建模技術(shù),提出了一個(gè)描述系統(tǒng)結(jié)構(gòu)及行為的一致性框架.該框架通過(guò)使用不同的建模技術(shù),采用映射的方式在體系結(jié)構(gòu)的不同構(gòu)件和體系結(jié)構(gòu)的不同視圖間建立關(guān)聯(lián),從而確保軟件體系結(jié)構(gòu)不同構(gòu)件及視圖之間不存在沖突.類(lèi)似于文獻(xiàn)[48],文獻(xiàn)[52]通過(guò)利用多種建模技術(shù),采用形式化語(yǔ)言定義模型元素間的約束,來(lái)確保體系結(jié)構(gòu)構(gòu)件和視圖間的一致性.對(duì)于規(guī)模較為復(fù)雜的軟件體系結(jié)構(gòu)模型,人工定義模型元素之間的約束極易出錯(cuò).本文所提出的CoEA-L 方法并不需要通過(guò)建模語(yǔ)言來(lái)定義不同模型間的約束關(guān)系進(jìn)行沖突消解.

當(dāng)前,許多大型軟件系統(tǒng)采用了面向服務(wù)的軟件體系結(jié)構(gòu)技術(shù)(service-oriented architecture,簡(jiǎn)稱(chēng)SOA)[56]進(jìn)行構(gòu)建.為了促進(jìn)SOA 的標(biāo)準(zhǔn)化及可復(fù)用性,針對(duì)不同的業(yè)務(wù)領(lǐng)域,軟件工程研究社區(qū)提出了SOA 的參考軟件體系結(jié)構(gòu)[57].如何消解采用SOA 技術(shù)構(gòu)建的軟件體系結(jié)構(gòu)和相關(guān)參考軟件體系結(jié)構(gòu)之間的沖突,是SOA 領(lǐng)域的重要研究問(wèn)題.文獻(xiàn)[58]是其中比較有代表性的工作,文獻(xiàn)[58]通過(guò)利用自動(dòng)化的映射技術(shù),將軟件體系結(jié)構(gòu)設(shè)計(jì)元素映射到SOA 參考軟件體系結(jié)構(gòu)的不同角色上,通過(guò)參考軟件體系結(jié)構(gòu)元素間的規(guī)則和約束,自動(dòng)化修改軟件體系結(jié)構(gòu)設(shè)計(jì)元素,從而消解軟件體系結(jié)構(gòu)設(shè)計(jì)與相關(guān)參考軟件體系結(jié)構(gòu)之間的沖突.與文獻(xiàn)[58]不同的是,本文提出的沖突消解方法不需要依賴(lài)業(yè)務(wù)領(lǐng)域的參考軟件體系結(jié)構(gòu).本文工作與相關(guān)工作的比較見(jiàn)表9.

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

6 結(jié)束語(yǔ)

軟件體系結(jié)構(gòu)合成活動(dòng)連接了問(wèn)題空間和解決方案空間,是軟件體系結(jié)構(gòu)設(shè)計(jì)中的關(guān)鍵性活動(dòng).為了在軟件體系結(jié)構(gòu)合成中復(fù)用已有的體系結(jié)構(gòu)知識(shí),架構(gòu)師通常使用軟件體系結(jié)構(gòu)模式進(jìn)行面向模式的軟件體系結(jié)構(gòu)合成.職責(zé)合成和模式合成是面向模式的軟件體系結(jié)構(gòu)合成中的兩大主要活動(dòng).由于軟件系統(tǒng)規(guī)模不斷增大,軟件職責(zé)不斷增加,使得自動(dòng)化進(jìn)行職責(zé)合成和模式合成并組合生成候選軟件體系結(jié)構(gòu)方案變得非常重要.但難點(diǎn)問(wèn)題是:當(dāng)組合職責(zé)合成和模式合成的設(shè)計(jì)方案時(shí),如何消解設(shè)計(jì)方案之間的沖突.針對(duì)該問(wèn)題,本文提出了基于學(xué)習(xí)的協(xié)作式協(xié)同演化軟件體系結(jié)構(gòu)合成方法.該方法利用鮑德溫進(jìn)化作為理論基礎(chǔ),提出了學(xué)習(xí)運(yùn)算子概念,擴(kuò)展了協(xié)作式協(xié)同演化軟件體系結(jié)構(gòu)合成方法[7].在本文中,我們通過(guò)在學(xué)習(xí)運(yùn)算子中采用數(shù)據(jù)挖掘的關(guān)聯(lián)算法,自動(dòng)化發(fā)現(xiàn)哪些軟件職責(zé)具有較高的概率在職責(zé)合成中被分配到相同的類(lèi)或者哪些軟件職責(zé)具有較高的概率在模式合成中被分配到相同的模式角色.提取到的這些信息進(jìn)而用于沖突消解.

為了驗(yàn)證本文提出方法的有效性,我們使用了3 個(gè)不同規(guī)模的設(shè)計(jì)問(wèn)題作為研究案例.實(shí)驗(yàn)結(jié)果表明,與3種競(jìng)爭(zhēng)方法相比,本文提出的方法能夠有效地消解沖突,并且能夠生成更加接近專(zhuān)家方案的候選軟件體系結(jié)構(gòu)設(shè)計(jì)方案.

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

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