趙 敏，高建華

(上海師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，上海 200234)

1 引 言

代碼異味是由于設(shè)計(jì)缺陷或不良編碼習(xí)慣導(dǎo)致深層次質(zhì)量問題的代碼癥狀，不一定直接地導(dǎo)致軟件的錯(cuò)誤，但會(huì)引起后續(xù)的一些可讀性差、效率低等系統(tǒng)問題，加大軟件維護(hù)的難度[1].相關(guān)研究報(bào)告顯示，大型系統(tǒng)的改進(jìn)、更新以及重組等一系列維護(hù)活動(dòng)占用了軟件項(xiàng)目總成本的90%，提前檢測(cè)并清理這些代碼異味，可以幫助程序員很好地理解源代碼的同時(shí)也節(jié)約了項(xiàng)目的成本.

Marinescu、Moha以及Khomh[2-4]等人使用度量、結(jié)構(gòu)和詞匯信息的組合來表示代碼異味的特征，定義規(guī)則來識(shí)別代碼異味的關(guān)鍵特征.但是在檢測(cè)特征不明顯的代碼異味時(shí)，精確度不高.在大型的應(yīng)用場(chǎng)景中，也需要花很多時(shí)間對(duì)規(guī)則做大量的校準(zhǔn)工作.

Fokaefs[5]提出了移動(dòng)重構(gòu)的方法，這是一種基于度量的代碼異味檢測(cè)方法.該方法用Eclipse插件將問題量化，先通過插件對(duì)系統(tǒng)質(zhì)量進(jìn)行評(píng)估，再重構(gòu).此方法僅適用于單一的代碼異味.

Fontana[6]等人提出了基于關(guān)聯(lián)的代碼異味檢測(cè)方法，通過代碼異味之間的直接關(guān)系和傳遞關(guān)系來檢測(cè)代碼異味，但這一方法只能檢測(cè)一些可量化的代碼異味.

Emerson[7]等人提出來一種基于可視化的代碼異味檢測(cè)方法.這一方法將可交互的檢測(cè)工具和手工識(shí)別代碼異味相結(jié)合，快速地認(rèn)識(shí)和理解代碼異味.但此方法涉及到手動(dòng)標(biāo)識(shí)代碼異味的特征，在效率和精確性上沒有很大的保證.

對(duì)此，本文提出了一種基于協(xié)同并行算法優(yōu)化的代碼異味檢測(cè)方法，即將遺傳規(guī)劃和遺傳算法相結(jié)合，把代碼異味的檢測(cè)問題看作一個(gè)分布式搜索最優(yōu)解問題.本文又通過Jaccard系數(shù)對(duì)算法進(jìn)行優(yōu)化，降低了檢測(cè)器的成本，提高了搜索效率.

2 相關(guān)術(shù)語

2.1 代碼異味

代碼異味也稱設(shè)計(jì)異?；蛟O(shè)計(jì)缺陷，是指對(duì)軟件維護(hù)產(chǎn)生不利影響的設(shè)計(jì)情況，它常常標(biāo)志著代碼應(yīng)該被重構(gòu)[8].本文關(guān)注以下8種代碼異味，如表1所示.

表1 代碼異味及其描述Table 1 Code smells and its descriptions

2.2 遺傳規(guī)劃

遺傳規(guī)劃的基本思想是演化候選的程序種群來解決一個(gè)特定的問題[9].隨機(jī)生成候選種群，通過適應(yīng)度函數(shù)對(duì)這些種群的質(zhì)量進(jìn)行評(píng)，如果符合標(biāo)準(zhǔn)則為最優(yōu)解，反之，則對(duì)這些種群進(jìn)行一系列的交叉、變異等基因操作生成新的種群，迭代至符合標(biāo)準(zhǔn)輸出.

2.2.1 檢測(cè)規(guī)則的生成

在評(píng)估大量與代碼異味檢測(cè)相關(guān)的參數(shù)后，確定了檢測(cè)規(guī)則的終端集和函數(shù)集，終端集包含不同的質(zhì)量度量以及閾值，函數(shù)集包含不同的邏輯運(yùn)算符.檢測(cè)規(guī)則是基于抽象語法樹從范例中生成的，多用二叉樹的形式來表示[10].

1)終端節(jié)點(diǎn)A是度量及其閾值的集合.度量包括一些代碼的行數(shù)、方法的數(shù)量、屬性的數(shù)量、加權(quán)方法的數(shù)量以及接口數(shù)量等.

2)內(nèi)部節(jié)點(diǎn)B是一個(gè)邏輯運(yùn)算符的集合C{AND，OR}.

如圖1所示，規(guī)則由一個(gè)AND-OR樹組成.其中，一條候選檢測(cè)規(guī)則對(duì)應(yīng)一條特定的代碼異味.

圖1 檢測(cè)規(guī)則的表示Fig.1 Representation of detection rules

規(guī)則1(R1).如果Locclass≥1500且(AND)Locmethod≥129或(OR)Nmd≥100，代碼異味為L(zhǎng)ager Class(LC)；

規(guī)則2(R2).如果Locmethod≥151，代碼異味為L(zhǎng)ong Method(LM)；

規(guī)則3(R3).如果Locmethod≥7且(AND)Nmd=16，代碼異味為Data Clumps(DC).

2.2.2 最優(yōu)檢測(cè)規(guī)則的生成

遺傳規(guī)劃通過其進(jìn)化算子(選擇、交叉和變異)迭代得到最優(yōu)檢測(cè)規(guī)則.

1)選擇：以保留良好解決方案的基因和提供更好的解決方案為兩大原則進(jìn)行選擇.通過適應(yīng)度函數(shù)對(duì)檢測(cè)規(guī)則池P進(jìn)行評(píng)估，根據(jù)適應(yīng)度值的高低排序，在池P中挑選出1/2適應(yīng)度高的檢測(cè)規(guī)則，形成新的檢測(cè)規(guī)則池S(大小為|S|，|S|=1/2|P|)；再將池S經(jīng)過隨機(jī)的交叉、變異形成新的子代檢測(cè)規(guī)則池E，從子代池E中選出大小跟池P一樣的檢測(cè)規(guī)則池O(大小為|O|，|O|=|P|)，新的檢測(cè)規(guī)則池U由池P和池O組成，大小為|U|=|P|+|O|=2|P|.

2)交叉：在兩個(gè)父節(jié)點(diǎn)上隨機(jī)選取他們的子節(jié)點(diǎn)及其子樹進(jìn)行交叉，生成的新樹結(jié)合雙方的信息，但僅限于同種代碼異味的檢測(cè)規(guī)則.

3)變異：變異通常分為三種情況：當(dāng)變異算子應(yīng)用在終端節(jié)點(diǎn)時(shí)，則將它替換為新的終端節(jié)點(diǎn)(質(zhì)量度量以及閾值)；當(dāng)變異算子應(yīng)用在功能節(jié)點(diǎn)時(shí)，則用新的函數(shù)來替換；如果是樹的變異，則將節(jié)點(diǎn)及其子樹一并替換為新生成的子樹.

2.3 遺傳算法

選擇、交叉以及變異是遺傳算法的三個(gè)基本操作.選擇，根據(jù)定義的適應(yīng)度函數(shù)對(duì)種群中個(gè)體進(jìn)行評(píng)估，適應(yīng)度高的種群個(gè)體被選擇；交叉，根據(jù)自然遺傳學(xué)對(duì)被選擇的種群個(gè)體進(jìn)行交叉，形成新的個(gè)體；變異，在個(gè)體基因的基礎(chǔ)上按照一定的規(guī)則進(jìn)行變異繼而形成新的最優(yōu)種群個(gè)體[11].

2.3.1 檢測(cè)器的生成

所謂的檢測(cè)器是指與良好范例代碼(幾乎沒有代碼異味的范例代碼)的偏差[12].由于本文只對(duì)代碼的結(jié)構(gòu)感興趣，所以可將檢測(cè)器表示為一組謂詞序列，謂詞序列的每個(gè)維度都是一個(gè)代碼元素，對(duì)應(yīng)面向?qū)ο笙到y(tǒng)中的類(C)、屬性(A)、方法(M)、參數(shù)(P)、泛型(G)和類之間的方法調(diào)用關(guān)系(R).

為了方便謂詞序列之間的比較，降低相似性計(jì)算的復(fù)雜度，謂詞序列的順序必須嚴(yán)格按照類、屬性、方法、參數(shù)、泛型、類之間調(diào)用關(guān)系的順序排列.例如，謂詞序列CGAAMPPM表示一個(gè)具有泛型的類，謂詞序列中包含兩個(gè)屬性、兩種方法，第一種方法有兩個(gè)參數(shù)，如圖2所示.

圖2 檢測(cè)器A的表示Fig.2 Representation of detection A

謂詞序列還包含一些相關(guān)結(jié)構(gòu)的詳細(xì)信息，如類型、可見性等.在檢測(cè)器A中，謂詞C是一個(gè)類，類名為C12，可見性為public.

2.3.2 最優(yōu)檢測(cè)器的生成

遺傳算法通過其三個(gè)基本操作選擇、交叉以及變異，不斷迭代搜索得到最優(yōu)的檢測(cè)器.

1)選擇：檢測(cè)器的選擇算子與檢測(cè)規(guī)則的選擇算子相同.

2)交叉：兩個(gè)父代謂詞序列L1、L2，兩個(gè)子代謂詞序列S1、S2.隨機(jī)選擇一個(gè)位置p；L1的前p個(gè)元素放入S1的前p個(gè)元素，L2進(jìn)行同樣的操作；L1剩下的元素放入S2，L2進(jìn)行同樣的操作.例如謂詞序列L1：CGAAMPPM和謂詞序列L2：CGAMPPR在1/5處進(jìn)行交叉，得到的新謂詞序列S1：CGAAMPR和S2：CGAMPPPM.

3)變異：變異應(yīng)用在隨機(jī)改變檢測(cè)器中元素的參數(shù).例如，圖2中檢測(cè)器A的第一個(gè)類的可見性為public，將其可見性變異成private.

2.4 遺傳算法與遺傳規(guī)則的區(qū)別

遺傳規(guī)劃是遺傳算法的一個(gè)分支.由于遺傳算法是按照一定字長(zhǎng)的字符串形式來描述問題，而遺傳規(guī)劃是以非定長(zhǎng)層次結(jié)構(gòu)反映特定的問題.檢測(cè)器是以謂詞序列(字符串)形式呈現(xiàn)，檢測(cè)規(guī)則是用二叉樹表示，所以本文將遺傳規(guī)則和遺傳算法分別應(yīng)用在搜索最優(yōu)檢測(cè)規(guī)則和最優(yōu)檢測(cè)器的問題中.

3 檢測(cè)規(guī)則和檢測(cè)器的評(píng)估

3.1 代碼異味范例的覆蓋率

設(shè)定一個(gè)目標(biāo)函數(shù)C，計(jì)算實(shí)際檢測(cè)到的代碼異味與范例中的代碼異味的重疊，覆蓋率如公式(1)所示.

(1)

其中：e是范例代碼中代碼異味的數(shù)量，r是執(zhí)行檢測(cè)規(guī)則后檢測(cè)到的實(shí)際代碼異味數(shù)量，對(duì)于ai(C)，如果第i次檢測(cè)到有code smell存在，ai(C)為1，否則為0，如表2、表3所示.

表2 范例代碼中的代碼異味Table 2 Code-smells in the base of examples

表3 實(shí)際檢測(cè)的代碼異味Table 3 Detected code smells

將表3中檢測(cè)到的代碼異味與表2中代碼異味相比，類Senior、Primary以及Junior不是代碼異味.類Bachelor是代碼異味但代碼異味的類型不對(duì).只有類Doctor是真正的代碼異味.所以，代碼異味范例的覆蓋率為(1/3+1/5)/2=0.26.

3.2 檢測(cè)器的成本

設(shè)定一個(gè)成本函數(shù)Cost來評(píng)估檢測(cè)器的質(zhì)量.其中，S為檢測(cè)器組，檢測(cè)器Si的成本是其通用性和重疊的缺失的加權(quán)平均數(shù)，如公式(2)所示.

(2)

通用性的缺失是通過計(jì)算檢測(cè)器Si的謂詞序列與良好范例代碼中類Cj的謂詞序列相似性而來，如公式(3)所示.

(3)

重疊的缺失是通過計(jì)算檢測(cè)器Si的謂詞序列與檢測(cè)器組S中所有其他檢測(cè)器Sj的謂詞序列的相似性而來，如公式(4)和式(5)所示.

(4)

其中，sim()如公式(5)所示.

(5)

a，b為謂詞序列A和B的長(zhǎng)度，Sa，b為A和B的公共最長(zhǎng)子序列.

為了計(jì)算兩個(gè)謂詞序列之間的相似性，本文將Needleman-Wunsch算法應(yīng)用到全文，并使用Jaccard系數(shù)對(duì)其進(jìn)行優(yōu)化.

Needleman-Wunsch算法是一種動(dòng)態(tài)編程方法，它是在允許加入空隙的情況下，找到兩個(gè)序列之間的最優(yōu)全局對(duì)齊[13].對(duì)齊序列(a1，…，an)和序列(b1，…，bn)時(shí)，根據(jù)下面的式(6)計(jì)算出Needleman-Wunsch算法矩陣LCS，并通過回溯寫出匹配字符串.其中，LCS矩陣第一行和第一列都為0；

ai=bj；

LCS(i，j)=LCS(i-1，j-1)+Sim(A，B)

ai≠bj；

(6)

Jaccard系數(shù)是計(jì)算兩個(gè)樣本集合之間的相似性[15，16]，如公式(7)所示.

(7)

如圖3所示，檢測(cè)器A的第一個(gè)方法Method(C12，m154，void，Y，public)與范例代碼34中的第一個(gè)方法Method(Options，isFractionalMetrics，boolean，Y，public)相比，N、Y都為變量名，public是可見性，所以用Jaccard系數(shù)計(jì)算為2/(5+5-2)=0.2.

本文設(shè)定了一個(gè)風(fēng)險(xiǎn)評(píng)估適應(yīng)度函數(shù)，將風(fēng)險(xiǎn)評(píng)分超過0.75的片段認(rèn)為是代碼異味，如式(8)所示.

(8)

其中，ei是待評(píng)估的代碼片段.

3.3 檢測(cè)規(guī)則和檢測(cè)器的交叉函數(shù)

如果一個(gè)類被檢測(cè)規(guī)則和檢測(cè)器同時(shí)檢測(cè)到，那么該類是代碼異味的幾率就會(huì)很大.因此，本文將檢測(cè)規(guī)則和檢測(cè)器組合來檢測(cè)代碼異味.

圖3 Jaccard系數(shù)計(jì)算圖Fig.3 Calculation figure of the Jaccard index

在每一次的迭代中，從最優(yōu)檢測(cè)規(guī)則和最優(yōu)檢測(cè)器中選出一組檢測(cè)規(guī)則和檢測(cè)器，應(yīng)用在新的系統(tǒng)N中.本文構(gòu)造了一個(gè)最優(yōu)解決方案矩陣M，行是最優(yōu)檢測(cè)規(guī)則MPi，列是最優(yōu)檢測(cè)器MAj，最優(yōu)檢測(cè)規(guī)則和最優(yōu)檢測(cè)器的交叉點(diǎn)得分，如公式(9)所示.

(9)

對(duì)于新系統(tǒng)N中，由最優(yōu)檢測(cè)規(guī)則檢測(cè)出含有代碼異味類的集合為Cr={c1，c2，…，ci}；由最優(yōu)檢測(cè)器檢測(cè)出含有代碼異味類的集合為Cd={c1，c2，…，cj}；實(shí)際檢測(cè)出含有代碼異味類的個(gè)數(shù)為T.

圖4 交叉點(diǎn)得分的說明Fig.4 Illustration of the intersection score

如圖4所示，待評(píng)估系統(tǒng)有5個(gè)類，其中有2個(gè)類存在代碼異味.將4個(gè)最優(yōu)檢測(cè)規(guī)則和4個(gè)最優(yōu)檢測(cè)器在待評(píng)估系統(tǒng)上運(yùn)行，并得到一個(gè)4×4的矩陣，檢測(cè)規(guī)則R18檢測(cè)出2個(gè)類存在代碼異味，檢測(cè)器檢S11測(cè)出3個(gè)類的risk值都高于0.75，所以3個(gè)類都存在代碼異味.計(jì)算兩種解決方案的交叉點(diǎn)得分依據(jù)式(9)為：(2/3+2/2)/2=0.83.

檢測(cè)器S11與4種檢測(cè)規(guī)則的交叉得分點(diǎn)分別為：0.43、0.83、0.59以及0.64.分析交叉得分點(diǎn)可知S11與R18的交叉得分點(diǎn)最高，在檢測(cè)代碼異味時(shí)，將其視作一組可能的最優(yōu)解決方案.

其中，每一種解決方案的交叉適應(yīng)度函數(shù)如公式(10)所示.

finter(MPi)=Min{finter(MPi，MA?j)}
finter(MPj)=Min{finter(MP?i，MAj)}

(10)

3.4 檢測(cè)規(guī)則質(zhì)量的評(píng)估

檢測(cè)規(guī)則的適應(yīng)度函數(shù)基于：

1)最大概率地覆蓋代碼異味的范例；

2)使用與檢測(cè)器并行執(zhí)行的交叉函數(shù)，使得一致性達(dá)到最大.

基于以上兩點(diǎn)，檢測(cè)規(guī)則質(zhì)量的適應(yīng)度函數(shù)如公式(11)所示.

(11)

3.5 檢測(cè)器質(zhì)量的評(píng)估

檢測(cè)器的適應(yīng)度函數(shù)基于：

1)減小范例代碼與檢測(cè)器之間的相似性，從而提高檢測(cè)器的通用性；

2)減小檢測(cè)器之間的重疊，即兩個(gè)檢測(cè)器的相似性.

基于以上兩點(diǎn)，檢測(cè)器質(zhì)量的適應(yīng)度函數(shù)如公式(12)所示.

(12)

4 基于協(xié)同并行算法優(yōu)化的代碼異味檢測(cè)方法

4.1 改進(jìn)的Needleman-Wunsch算法

在文獻(xiàn)[16]中提出了一種改進(jìn)的Needleman-Wunsch算法，普通的Needleman-Wunsch算法只比較謂詞的相似度，改進(jìn)的Needleman-Wunsch算法通過式(13)進(jìn)一步計(jì)算謂詞的參數(shù)的相似性，精確了最長(zhǎng)公共子序列的長(zhǎng)度，如公式(13)所示.

(13)

其中，ai、bj是兩個(gè)謂詞的參數(shù)集，p、q是兩個(gè)謂詞的參數(shù).

以檢測(cè)器A中謂詞Method參數(shù)集(C12，m154，void，Y，public)和范例代碼34的謂詞Method參數(shù)集(Options，isFractionalMetrics，boolean，Y，public)為例，式(13)計(jì)算得出兩種方法的相似性為：2/5=0.4.改進(jìn)后的LCS矩陣如公式(6)所示，其中Sim(A，B)=PMij.

4.2 基于Jaccard系數(shù)的Needleman-Wunsch算法

為了更進(jìn)一步地提高檢測(cè)器的通用性和降低檢測(cè)器之間的重疊，本文在改進(jìn)的Needleman-Wunsch算法基礎(chǔ)上，提出基于Jaccard系數(shù)的Needleman-Wunsch算法，用于對(duì)比計(jì)算兩個(gè)謂詞的參數(shù)集.

以檢測(cè)器A中謂詞Method參數(shù)集(C12，m154，void，Y，public)和范例代碼34中的謂詞Method參數(shù)集(Options，isFractionalMetrics，boolean，Y，public)為例，由Jaccard系數(shù)計(jì)算出來兩個(gè)謂詞參數(shù)集的相似度0.2.改進(jìn)后得到計(jì)算LCS矩陣如公式(6)所示，其中Sim(A，B)=J(A，B).兩種方法的對(duì)比如圖5所示.

圖5 兩種方法的對(duì)比圖Fig.5 Comparisonfigureof two methods

根據(jù)以上兩個(gè)公式計(jì)算出來的最長(zhǎng)公共子序列分別為2.4和2.2，將結(jié)果帶入式(5)，可得到檢測(cè)器A和代碼范例34的相似度Sim()分別為0.4和0.2.由式(3)可得，檢測(cè)器和范例代碼之間相似度的精確可以提高檢測(cè)器的通用性；由式(4)可見，檢測(cè)器間相似度的精確可以降低檢測(cè)器之間的重疊；由式(2)可得，隨著檢測(cè)器通用性的提高和檢測(cè)器間重疊的降低，檢測(cè)器的成本也隨之減少.后續(xù)本文對(duì)這兩種方法在同一數(shù)據(jù)集上進(jìn)行驗(yàn)證，以說明基于Jaccard系數(shù)的Needleman-Wunsch算法要優(yōu)于改進(jìn)的的Needleman-Wunsch算法.

4.3 協(xié)同并行算法優(yōu)化

為了減少搜索時(shí)間、精確檢測(cè)結(jié)果，本文提出將最優(yōu)檢測(cè)規(guī)則和最優(yōu)檢測(cè)器并行應(yīng)用在檢測(cè)過程中，該并行算法的具體實(shí)現(xiàn)過程如算法1和算法2所示.

算法1.基于遺傳規(guī)劃的最優(yōu)檢測(cè)規(guī)則獲取算法

輸入：代碼質(zhì)量度量集合M

手工評(píng)估的系統(tǒng)集合S(異味示例)

新系統(tǒng)A

輸出：最優(yōu)檢測(cè)規(guī)則

1.Max_size=100;

2.gen=0;%Counter

3.NBS=100;%number of best Soulution

4.MaxGen=500;%maximum no.fo generation

5.R1=rules(M,Smell_type);

6.P1=set_of(R1);

7.Initial_population_GP(P1,Max_size);

8.While gen

9. for each R1∈P1 do

10. detected_smells_GP(S)=excute_rules(R1,S);

11. fitness(R1)=compare(detected_smells,smells_examples);

12. end for

13. best_sol_P1=select(P1,NBS);

14. send(best_sol_P1);

15. best_sol_P2=receive(best_sol_P2);

16. for each R1∈best_sol_P1 do

17. detected_smells_GP(A)=excute_rules(R1,A);

18. fitness_intersection(R1)=Max_intersection(detected_smells_GP(A,R1)∩detected_smells_GA(A,best_sol_P2)

19. fitness(R1):=update fitness(R1,fitness_intersection);

20. end for

21. gen=gen+1;

22.end

23.retum best solution rules;

算法2.基于遺傳算法的最優(yōu)檢測(cè)器獲取算法

輸入：良好示例代碼的集合GES

新系統(tǒng)A

輸出：最優(yōu)檢測(cè)器

1.Max_size=100;

2.gen=0;%Counter

3.NBS=100;%number of best Soulution

4.MaxGen=500;%maximum no.fo generation

5.R2=detectors(GES);

6.P2=set_of(R2);

7.Initial_population_GP(P2,Max_size);

8.While gen

9. for each R2∈P2 do

10. fitness(R2)=cost(R2);

12. end for

13. best_sol_P2=select(P2,NBS);

14. send(best_sol_P2);

15. best_sol_P1=receive(best_sol_P1);

16. for each R2∈best_sol_P2 do

17. detected_smells_GA(A)=excute_rules(R2,A);

18. fitness_intersection(R2)=Max_intersection(detected_smells_GA(A,R2)∩detected_smells_GP(A,best_sol_P1)

19. fitness(R2):=update fitness(R2,fitness_intersection);

20. end for

21. gen=gen+1;

22.end

23.retum best solution rules;

算法1和算法2并行執(zhí)行，并在每一代中使用適應(yīng)度函數(shù)進(jìn)行交互.第1-3行構(gòu)造一個(gè)初始檢測(cè)規(guī)則種群和檢測(cè)器種群；第4-15行是搜索最優(yōu)檢測(cè)規(guī)則和檢測(cè)器的循環(huán)過程；第16-20行是兩種算法的交互.

在每次迭代中，本文使用適應(yīng)度函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行質(zhì)量評(píng)估.在評(píng)估檢測(cè)器時(shí)(算法2的第10行)，對(duì)原先的適應(yīng)度函數(shù)進(jìn)行了改進(jìn).本文使用Jaccard系數(shù)對(duì)Needleman-Wunsch算法進(jìn)行改進(jìn)，從而增加了檢測(cè)器的通用性和檢測(cè)器之間的重疊，減小了檢測(cè)器的成本.5.2中的實(shí)驗(yàn)結(jié)果表明，這種改進(jìn)不僅增加了代碼異味的精度和召回率，還減少了搜索時(shí)間.

圖6 方法的概圖Fig.6 Overviewof the proposed approach

如圖6所示，協(xié)同并行算法優(yōu)化可以理解為以下4個(gè)步驟：

1)通過遺傳規(guī)則和遺傳算法并行搜索最優(yōu)檢測(cè)規(guī)則和最優(yōu)檢測(cè)器；

2)將搜索得到的最優(yōu)檢測(cè)規(guī)則和最優(yōu)檢測(cè)器應(yīng)用在新系統(tǒng)上；

3)根據(jù)交叉點(diǎn)得分更改最優(yōu)檢測(cè)規(guī)則和最優(yōu)檢測(cè)器的適應(yīng)度函數(shù)，生成最優(yōu)解決方案.

4)達(dá)到先前設(shè)定的固定迭代次數(shù)后，停止.

5 實(shí) 驗(yàn)

5.1 實(shí)驗(yàn)環(huán)境

為了評(píng)估基于協(xié)同并行算法優(yōu)化的代碼異味檢測(cè)的方法，本實(shí)驗(yàn)從大型開源系統(tǒng)中提取8個(gè)開源項(xiàng)目對(duì)8種代碼異味進(jìn)行實(shí)驗(yàn)，并與基于單一種群的算法以及文獻(xiàn)[16]中的協(xié)同并行算法進(jìn)行比較.

本實(shí)驗(yàn)從現(xiàn)有的數(shù)據(jù)集[17]中挑選出類大小不的開源項(xiàng)目，其包含了近800種手動(dòng)識(shí)別的代碼異味，如表4所示.

在過去的十多年中，這些項(xiàng)目一直保持著活躍的狀態(tài)，并包含了大量的代碼異味.此外，這些項(xiàng)目被諸多研究引用，分布于不同的應(yīng)用領(lǐng)域，其包含的代碼異味已被大量相關(guān)研究明確檢測(cè)和分析[16].

表4 實(shí)驗(yàn)項(xiàng)目Table 4 Systems for experiment

5.2 實(shí)驗(yàn)配置

本實(shí)驗(yàn)將剩余的項(xiàng)目作為代碼異味范例來生成檢測(cè)規(guī)則，例如檢測(cè)GanttProject3，則選擇剩余的項(xiàng)目作為代碼異味范例來生成規(guī)則.從范例中可以生成特定項(xiàng)目的特定的規(guī)則，所以在同一軟件項(xiàng)目?jī)?nèi)，規(guī)則是適用的[10].

對(duì)于檢測(cè)規(guī)則的充分性，范例庫中包含了研究的所有代碼異味類型，所以范例具有充分性.規(guī)則是從范例中生成，范例的充分性從一定程度上也保證了規(guī)則的充分性[10].

對(duì)于檢測(cè)規(guī)則的一般性，Decor[3]是公認(rèn)的可用于生產(chǎn)環(huán)境的經(jīng)典代碼異味檢測(cè)工具.在參考文獻(xiàn)[10]中，將從范例中生成規(guī)則的方法與Decor行對(duì)比，實(shí)驗(yàn)表明前者的精度與召回都要優(yōu)于后者.

本實(shí)驗(yàn)選擇JHotdraw[18]作為良好的代碼異味范例，并通過與JHotdraw之間的偏差來生成檢測(cè)器，因?yàn)镴Hotdraw包含很少的已知代碼異味.

本文根據(jù)文獻(xiàn)[19]提出的種群數(shù)和迭代數(shù)，將遺傳規(guī)則和遺傳算法的種群數(shù)固定在100，迭代數(shù)固定在1000.協(xié)同并行算法優(yōu)化的種群數(shù)固定在100，迭代數(shù)固定在500.并將基于遺傳規(guī)劃、遺傳算法、協(xié)同并行算法以及協(xié)同并行算法優(yōu)化的方法執(zhí)行500次進(jìn)行比較.

為了強(qiáng)調(diào)種群的多樣性，本實(shí)驗(yàn)將進(jìn)化算子中交叉概率設(shè)為0.9，變異概率設(shè)為0.5.

為了評(píng)估本文方法的準(zhǔn)確性，本實(shí)驗(yàn)計(jì)算了兩種度量：精度(PMV)和召回(RMV).在實(shí)驗(yàn)中，精度表示所有檢測(cè)到的代碼異味中檢測(cè)到正確的代碼異味的概率，召回表示所有手動(dòng)識(shí)別的代碼異味中正確檢測(cè)到的代碼異味的概率.

實(shí)驗(yàn)主要尋求以下幾個(gè)問題的解答：

Q1：基于協(xié)同并行算法優(yōu)化，什么類型的代碼異味可以被正確的檢測(cè)？

Q2：協(xié)同并行算法優(yōu)化在多大程度上優(yōu)于基于單一種群的方法以及原來的協(xié)同并行算法？

5.3 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)記錄了不同項(xiàng)目中基于協(xié)同并行優(yōu)化方法下8種代碼異味的精度值和召回率，如表5所示.在不同的項(xiàng)目中，8種代碼氣味的精度值和召回率都超過了85%.表5結(jié)果表明協(xié)同并行算法優(yōu)化的方法沒有偏向于檢測(cè)特定的代碼異味.在所有項(xiàng)目中，每個(gè)代碼異味類型的分布幾乎相等.這種不偏向于識(shí)別某種特定代碼異味的能力是本文方法的一個(gè)關(guān)鍵優(yōu)勢(shì).大多數(shù)現(xiàn)有的工具和技術(shù)在很大程度上依賴于度量的方法，對(duì)于FE、SS這些代碼異味，度量的方法并不奏效[20，21].從這一方面來看，協(xié)同并行算法優(yōu)化結(jié)合了多種不同的檢測(cè)方法，在代碼異味的檢測(cè)上具有一定的準(zhǔn)確性.(Q1)

表5 不同項(xiàng)目下代碼異味的精度值和召回率Table 5 Precision median values and recall median values of different projects

實(shí)驗(yàn)將4種方法分別應(yīng)用在不同的項(xiàng)目上，每種方法運(yùn)行51次，并計(jì)算精度值和召回率.

表6 不同方法下的精度值和召回率Table 6 Precision median values and recall median values of different methods

如表6所示，基于遺傳規(guī)劃方法下得到的精度值大約在82%、召回率大約在80%；基于遺傳算法方法下得到的精度值大約在82%、召率大約在81%；基于協(xié)同并行算法方法下得到的精度值大約在89%、召回率大約在87%；基于協(xié)同并行算法優(yōu)化方法下得到的精度值大約在91%、召回率大約在88%；從縱向來看，隨著項(xiàng)目大小的改變，精度值和召回率并沒有很大的浮動(dòng)，可以表明精度值以及召回率與項(xiàng)目大小無關(guān).從整體來看，基于單一種群的算法的精度和召回率低于基于協(xié)同并行算法，基于協(xié)同并行算法優(yōu)化方法的精度值和召回率最高，可以表明基于協(xié)同并行算法優(yōu)化的方法優(yōu)于其余兩種基于單一種群以及基于協(xié)調(diào)并行算法的方法.(Q1)

將基于協(xié)同并行算法優(yōu)化的代碼異味檢測(cè)方法和兩個(gè)基于單一種群以及基于協(xié)同并行算法的代碼異味檢測(cè)方法，分別應(yīng)用在不同的項(xiàng)目上.

圖7 不同項(xiàng)目上的平均執(zhí)行時(shí)間比較Fig.7 Average execution time comparison on the different project

如圖7所示，從CUP時(shí)間來看，基于協(xié)同并行算法優(yōu)化的執(zhí)行時(shí)間是基于單一種群的一半.因此，在代碼異味檢測(cè)的問題上，并行執(zhí)行比單一執(zhí)行耗時(shí)更少，基于協(xié)同算法優(yōu)化的執(zhí)行時(shí)間也少于基于協(xié)同并行算法.這是因?yàn)樵趦?yōu)化研究領(lǐng)域中，評(píng)估階段通常是最耗時(shí)的，在本實(shí)驗(yàn)中，用Jaccard算法優(yōu)化了用于評(píng)估檢測(cè)器的Needleman-Wuncsh算法，增大了檢測(cè)器的通用性并減小了檢測(cè)器之間的重疊，減少搜索時(shí)間的同時(shí)也減少了評(píng)估階段的耗時(shí).(Q2)

6 期 望

本文提出了基于并行協(xié)同算法優(yōu)化的方法來檢測(cè)代碼異味，降低了檢測(cè)器的成本，加快了搜索速度.由遺傳規(guī)劃搜索得到最優(yōu)檢測(cè)規(guī)則，由遺傳算法搜索得到最優(yōu)檢測(cè)器，再將兩種方法在同一項(xiàng)目上運(yùn)行，找到兩種解決方案的交集，其結(jié)果是令人信服的.不足之處在于，本文只關(guān)注8種代碼異味，相對(duì)局限，未來將擴(kuò)大實(shí)驗(yàn)規(guī)模，以檢測(cè)更多的代碼異味，提高方法的一般適用性.此外，還準(zhǔn)備增加并行的算法個(gè)數(shù)，求證3個(gè)及3個(gè)以上的算法檢測(cè)出來的結(jié)果會(huì)不會(huì)更加精確.