抑制孤立簇的軟件模塊化優(yōu)化算法

牟立峰，王方媛

(上海大學(xué) 悉尼工商學(xué)院，上海 201899)

0 引言

在軟件產(chǎn)品設(shè)計(jì)和開發(fā)過程中，廣泛應(yīng)用模塊化方法來提高軟件產(chǎn)品架構(gòu)的質(zhì)量。但隨著軟件產(chǎn)品的不斷進(jìn)化，軟件產(chǎn)品趨向大型化和復(fù)雜化，僅依靠專家經(jīng)驗(yàn)無法應(yīng)對(duì)復(fù)雜的模塊化方案設(shè)計(jì)問題。因此，如何運(yùn)用智能算法自動(dòng)生成大型復(fù)雜軟件系統(tǒng)的高質(zhì)量模塊劃分備選方案對(duì)軟件產(chǎn)品的設(shè)計(jì)過程中的關(guān)鍵決策有著重要意義，與其相關(guān)的研究工作也成為學(xué)術(shù)界關(guān)注的熱點(diǎn)[1]。

軟件模塊化目的是得到模塊化較好的聚類目標(biāo)，模塊化優(yōu)化問題主要包括設(shè)計(jì)模塊化質(zhì)量的量化指標(biāo)[2-7]和更強(qiáng)尋優(yōu)能力的算法[6-15]。

在量化指標(biāo)方面，研究工作主要從軟件產(chǎn)品的屬性上著手量化軟件架構(gòu)質(zhì)量，其中最重要的兩個(gè)屬性是內(nèi)聚和耦合。內(nèi)聚指的是在同一個(gè)子系統(tǒng)中模塊之間的聯(lián)系，耦合指的是不同的子系統(tǒng)中模塊的聯(lián)系[2]。很多學(xué)者基于內(nèi)聚和耦合的關(guān)系提出了衡量軟件模塊劃分方案優(yōu)劣的指標(biāo)。Stevens等[3]在1974年首先提出用高內(nèi)聚和低耦合指標(biāo)來衡量軟件模塊化的質(zhì)量，并提出了一個(gè)內(nèi)聚和耦合的七分制的衡量方法，為之后軟件質(zhì)量指標(biāo)提供了方法和思路。針對(duì)面向?qū)ο蟮能浖a(chǎn)品，學(xué)術(shù)界也提出了其他指標(biāo)，包括：屬性隱藏因素指標(biāo)(Attribute Hidden Factor, AHF)和方法隱藏因素指標(biāo)(Method Hidden Factor, MHF)，這些指標(biāo)能更好地測(cè)量封裝的程度[4]。之后Tucker等[5]提出了指標(biāo)EVM(EValuation Metric)，該指標(biāo)之前應(yīng)用于時(shí)間序列分析，并且具有優(yōu)秀的魯棒性。隨后研究工作的深入，學(xué)者發(fā)現(xiàn)：一味地追求高內(nèi)聚和低耦合并不可??；高質(zhì)量的軟件架構(gòu)普遍擁有內(nèi)聚和耦合相對(duì)平衡的模塊化特性[2]?；谠撍悸罚琈ancoridis等[6]提出了軟件模塊化質(zhì)量(Modularization Quality, MQ)的評(píng)價(jià)指標(biāo)，并被廣泛采用。然而采用MQ作為進(jìn)化算法的適應(yīng)函數(shù)存在一個(gè)重要缺點(diǎn)：很容易造成孤立簇(Isolated cluster)，即一個(gè)子系統(tǒng)只包含一個(gè)模塊的現(xiàn)象[7]。針對(duì)這個(gè)問題，本文提出了一個(gè)新的改進(jìn)型軟件模塊化衡量指標(biāo)(Improved Modularization Quality, IMQ)，以該指標(biāo)作為進(jìn)化算法的適應(yīng)函數(shù)可以有效抑制孤立簇現(xiàn)象。

在算法方面，軟件模塊化本質(zhì)上是一個(gè)聚類問題，解決該問題的算法可分為兩類：一類需要事先根據(jù)先驗(yàn)知識(shí)確定模塊數(shù)目(通常也稱為聚類數(shù)目)，例如K-means算法[8]和k-mediods算法[9]。這類算法操作簡(jiǎn)單且效率較高，但其缺點(diǎn)是要在優(yōu)化之前就確定模塊數(shù)目，即：模塊數(shù)目不是決策變量。另一類算法將模塊數(shù)目也作為決策變量，比如：Bandyopadhyay等[10]提出的遺傳算法(Genetic Algorithm, GA)以隨機(jī)的方式從染色體中找出有效質(zhì)心來動(dòng)態(tài)決定模塊數(shù)目；Omran等[11]提出的K-means和粒子群相結(jié)合的算法；Maqbool等[12]為軟件架構(gòu)重組設(shè)計(jì)的層次聚類方法。為了使算法具有更好的實(shí)用性，本文重點(diǎn)關(guān)注第二類算法。

傳統(tǒng)聚類問題多以距離為量化的基礎(chǔ)，軟件模塊化問題以特定的軟件工程量化指標(biāo)為模塊化依據(jù)，使得該問題難以求解，因此進(jìn)化算法和啟發(fā)式算法已經(jīng)成為解決軟件模塊化問題的主流方法。第一次運(yùn)用遺傳算法來解決軟件模塊化問題是Mancoridis等[6]。隨后，Harman等[13]將模塊的顆粒度融入適應(yīng)度函數(shù)的測(cè)量中，并基于此設(shè)計(jì)了針對(duì)軟件模塊化問題的啟發(fā)式算法。值得重點(diǎn)說的是由Mitchell等[14]在2008年設(shè)計(jì)的融合模擬退火機(jī)制的多點(diǎn)爬山算法，對(duì)比實(shí)驗(yàn)結(jié)果證明：該多點(diǎn)爬山算法能找到高質(zhì)量的模塊化方案?；谄溲芯抗ぷ鞯闹匾饬x不僅在高效算法的設(shè)計(jì)，而且在于Mancoridis和Mitchell開發(fā)了一個(gè)基于搜索的軟件模塊化工具(Bunch)，該工具集成了多種進(jìn)化算法和啟發(fā)式方法，該領(lǐng)域其他研究工作廣泛采用Bunch工具中的算法作為BenchMark進(jìn)行對(duì)比實(shí)驗(yàn)[6]。同時(shí)，為了兼顧多個(gè)目標(biāo)(如：最大化MQ指標(biāo)的同時(shí)、最小化的孤立簇個(gè)數(shù))，很多研究人員運(yùn)用多目標(biāo)優(yōu)化算法來解決軟件模塊化問題。如：Mkaouer等[15]所采用的NSGA-Ⅲ算法，以及Praditwong等[7]提出的多目標(biāo)方法。雖然多目標(biāo)進(jìn)化算法在搜索Pareto解方面有一定優(yōu)勢(shì)，但是也正是因?yàn)镻areto最優(yōu)，使得多目標(biāo)算法往往要消耗很多的資源和時(shí)間搜索高質(zhì)量的解。隨著問題規(guī)模的增加，搜索空間的迅速膨脹，低效率限制了該類方法的應(yīng)用。本研究不是從多目標(biāo)優(yōu)化算法入手，而是將研究重點(diǎn)放在設(shè)計(jì)本身具備提高M(jìn)Q和抑制孤立簇的指標(biāo)，并設(shè)計(jì)符合問題特點(diǎn)的高效進(jìn)化算法來驗(yàn)證其尋優(yōu)能力和魯棒性。本文工作主要有以下幾點(diǎn)：

1)提出一個(gè)新的軟件模塊化度量指標(biāo)IMQ，該指標(biāo)不僅能夠平衡內(nèi)聚和耦合的關(guān)系，而且能夠有效降低孤立簇個(gè)數(shù)；

2)建立以最大化IMQ為目標(biāo)的軟件模塊化問題的數(shù)學(xué)模型。

3)設(shè)計(jì)符合問題特點(diǎn)的改進(jìn)遺傳算法(Improved Genetic Algorithm, IGA)求解提出的數(shù)學(xué)模型，該算法的重要特點(diǎn)是運(yùn)用了基于邊收縮方法的啟發(fā)式策略生成種子解，提高了算法的尋優(yōu)能力和魯棒性。

4)將IGA與基于GNE(Group Number Encoding)遺傳算法[7]和融合模擬退火機(jī)制的改進(jìn)爬山(Improved Hill Climbing, IHC)算法——多點(diǎn)爬山算法[14]進(jìn)行對(duì)比實(shí)驗(yàn)，用t檢驗(yàn)和Cohen’s d index規(guī)模值[2]的方式來檢驗(yàn)算法對(duì)比的結(jié)果。結(jié)果顯示IGA相對(duì)于該兩種算法具有更好的尋優(yōu)能力和魯棒性。

1 問題描述

一個(gè)軟件系統(tǒng)中軟件構(gòu)件之間的關(guān)系可以使用模塊依賴圖(Module Dependency Graph, MDG)[2,7,14]抽象描述。MDG中的每個(gè)節(jié)點(diǎn)代表了每個(gè)軟件構(gòu)件，邊代表兩構(gòu)件之間的相互關(guān)聯(lián)程度。軟件模塊化是基于軟件構(gòu)件的關(guān)聯(lián)程度對(duì)軟件系統(tǒng)進(jìn)行自動(dòng)劃分并得到模塊化較好的聚類目標(biāo)的過程。不同的模塊化優(yōu)化模型中的目標(biāo)就是以構(gòu)件之間的關(guān)聯(lián)度為依據(jù)構(gòu)造的，比如：內(nèi)聚、耦合或者兩者之間的特定關(guān)系。其中，內(nèi)聚指的是一個(gè)模塊內(nèi)軟件構(gòu)件之間的相互聯(lián)系；耦合衡量的是不同模塊之間軟件構(gòu)件的相互聯(lián)系。本章將提出一個(gè)新的軟件模塊化的量化指標(biāo)和軟件模塊化問題的數(shù)學(xué)規(guī)劃模型。

1.1 IMQ指標(biāo)

早期的研究工作采用高內(nèi)聚和低耦合來判斷軟件設(shè)計(jì)質(zhì)量的標(biāo)準(zhǔn)[2,6-7,14-15]。高內(nèi)聚意味著子系統(tǒng)中模塊之間的聯(lián)系越大越好；低耦合意味著不同子系統(tǒng)之間的聯(lián)系越少越好。然而，一味地追求高內(nèi)聚和低耦合這兩個(gè)目標(biāo)，最后會(huì)得到一個(gè)“完美方案”，即一個(gè)子系統(tǒng)包含了所有模塊。顯然這與實(shí)際要求不符，因此，近年來，學(xué)者們提出在內(nèi)聚和耦合之間作出合理的平衡。Mancoridis等[6]提出的限制過度耦合且不會(huì)完全消除耦合的模塊化質(zhì)量指標(biāo)MQ，能平衡高內(nèi)聚和低耦合這兩個(gè)目標(biāo)；但是MQ指標(biāo)忽略了系統(tǒng)中孤立簇的存在，明顯增加了系統(tǒng)的維護(hù)成本，并不是良好的軟件模塊劃分方案。針對(duì)該問題，Pradiwong等[7]在2011年提出的軟件模塊化的多目標(biāo)算法MCA中，將最小化孤立簇的個(gè)數(shù)作為其中的一個(gè)目標(biāo)。區(qū)別于其研究工作，為了避免多目標(biāo)優(yōu)化尋找Pareto最優(yōu)的低效率，本文提出了一個(gè)新的軟件模塊化指標(biāo)，運(yùn)用該指標(biāo)作為進(jìn)化算法的適應(yīng)函數(shù)，可以在實(shí)現(xiàn)內(nèi)聚和耦合平衡的同時(shí)，有效抑制孤立簇現(xiàn)象的發(fā)生。

一個(gè)模塊依賴圖G可以簡(jiǎn)單記為(V，E)二元組，并用|V|表示頂點(diǎn)的個(gè)數(shù)，用|E|表示邊數(shù)。當(dāng)一個(gè)模塊依賴圖G=(V,E)被劃分成k個(gè)子圖，IMQ的計(jì)算公式如下：

(1)

CFi代表第i(1≤i≤k)個(gè)子圖的聚簇因子，M是孤立簇的個(gè)數(shù)。其中聚簇因子CFi的計(jì)算公式如下：

(2)

1.2 數(shù)學(xué)規(guī)劃模型

以IMQ為基礎(chǔ)，為了建立數(shù)學(xué)規(guī)劃模型，引入數(shù)學(xué)符號(hào)如表1所示。

表1 模型中數(shù)學(xué)符號(hào)的定義Tab. 1 Definition of symbols in the model

基于以上數(shù)學(xué)符號(hào)，軟件模塊化問題的數(shù)學(xué)規(guī)劃模型可表示為：

(3)

(4)

(5)

(6)

xik∈{0,1};i=1,2,…,|V|,k=1,2,…,M

(7)

yk∈{0,1};k=1,2,…,M

(8)

P∈{1,2,…,|V|}

(9)

通過分析模型(3)～ (9)，可知由于如下因素綜合導(dǎo)致無法無法多項(xiàng)式時(shí)間內(nèi)求解該類模型：

1)決策變量xik和yk為二進(jìn)制決策變量；

2)目標(biāo)函數(shù)(3)分子和分母中均包含決策變量，并且含有決策變量的二次項(xiàng)；

3)P作為整數(shù)決策變量出現(xiàn)在模型中導(dǎo)致模型更難求解；

4)該問題可以規(guī)約為圖論中已經(jīng)被證明為NP-hard問題[16]的最小切問題。

因此，本文重點(diǎn)設(shè)計(jì)一種在可接受時(shí)間內(nèi)搜索高質(zhì)量模塊化方案的改進(jìn)遺傳算法。

2 改進(jìn)的遺傳算法

為克服傳統(tǒng)算法局部搜索能力較差、極易陷入局部最優(yōu)的缺點(diǎn)，本文設(shè)計(jì)改進(jìn)遺傳算法IGA來求解軟件模塊化問題。IGA的適應(yīng)度函數(shù)采用IMQ指標(biāo)。IGA的改進(jìn)主要體現(xiàn)在兩個(gè)方面：一個(gè)是用啟發(fā)式策略生成初始種群；另一個(gè)是采用基于相似度的競(jìng)爭(zhēng)和選擇機(jī)制。

2.1 個(gè)體編碼

本文采用分組編碼(Group Number Encoding, GNE)方式，即：染色體中的位置表示軟件構(gòu)件的編號(hào)，每個(gè)位置上的整數(shù)值表示對(duì)應(yīng)的模塊編號(hào)，相同整數(shù)代表對(duì)應(yīng)位置上的軟件構(gòu)件被劃分在同一模塊中。如x=[1,1,1,1,2,2,2,3,3]代表著一個(gè)軟件模塊化方案，該方案將9個(gè)軟件構(gòu)件劃分到3個(gè)模塊中，構(gòu)件1，2，3和4被劃分到模塊1中；構(gòu)件5，6和7被劃分到模塊2中；構(gòu)件8和9被劃分到模塊3中。

2.2 生成初始種群的啟發(fā)式算法

啟發(fā)式算法以IMQ值最大化為目標(biāo)，算法的思想如下：最初，所有頂點(diǎn)都未經(jīng)融合，將所有頂點(diǎn)當(dāng)作一個(gè)獨(dú)立的子圖；然后，每次迭代選擇收縮邊權(quán)最大的邊，并融合該邊兩端的頂點(diǎn)被當(dāng)作一個(gè)新的子圖，此時(shí)所有未經(jīng)融合的頂點(diǎn)同樣被當(dāng)作是一個(gè)子圖，每一步都更新模塊劃分方案，直到最后所有頂點(diǎn)融合在一起。在這個(gè)收縮邊和頂點(diǎn)融合過程中，計(jì)算每一次迭代后IMQ的值，取IMQ最大的狀態(tài)圖作為備選模塊劃分方案。迭代過程中，如果存在多個(gè)權(quán)重最大的邊，以輪盤賭的方式選取其中一個(gè)繼續(xù)迭代過程。此隨機(jī)選擇方式能夠保證初始種群的多樣性。

以圖1直觀解釋啟發(fā)式算法。每個(gè)頂點(diǎn)旁的矩形中的數(shù)字表示該頂點(diǎn)的內(nèi)聚值，最初每個(gè)頂點(diǎn)的內(nèi)聚值均為0。圖標(biāo)題中的P代表每個(gè)過程中的模塊數(shù)，M代表每個(gè)過程中的孤立簇的個(gè)數(shù)。每個(gè)圖中虛線中的兩個(gè)點(diǎn)表示下一步中要融合的點(diǎn)。例如圖1(a)階段，頂點(diǎn)4和頂點(diǎn)5融合在一起形成了一個(gè)新的子圖，該子圖的內(nèi)聚為頂點(diǎn)之間的邊權(quán)與兩個(gè)原頂點(diǎn)的內(nèi)聚之和。將剩下的所有未經(jīng)融合的頂點(diǎn)看作另一個(gè)子圖，所以該狀態(tài)的模塊數(shù)是2，孤立簇個(gè)數(shù)為0。此時(shí)，由于存在兩個(gè)最大權(quán)重的邊，即：頂點(diǎn)1和頂點(diǎn)3之間的邊，頂點(diǎn)7和頂點(diǎn)8之間的邊，邊權(quán)都為8，則以輪盤賭的方式選取一個(gè)，本示例選取了頂點(diǎn)1和頂點(diǎn)3作為下一步融合的兩個(gè)點(diǎn)。

圖1 啟發(fā)式算法示例 Fig. 1 Examples of heuristic algorithm

通過記錄了迭代過程中每個(gè)狀態(tài)的IMQ的值，在圖2中繪出IMQ的變動(dòng)情況。從圖2中可以看出，在合并頂點(diǎn)的過程中IMQ的值是在不斷變動(dòng)的，其中IMQ5的值最大，為2.276 0。IMQ5對(duì)應(yīng)于圖1(f)所示的狀態(tài)，就是啟發(fā)式算法找到的軟件模塊化的方案，即：(1，2，3),(4，5)和(6，7，8)。

圖2 IMQ迭代變動(dòng)情況 Fig. 2 IMQ change with iterations

該啟發(fā)式算法為IGA的初始化種群策略的重要組成部分：即將該啟發(fā)式算法得到的近似最優(yōu)解作為種子植入到初始種群中，再用遺傳算法進(jìn)一步提高解的質(zhì)量。傳統(tǒng)遺傳算法在實(shí)際應(yīng)用過程中經(jīng)常會(huì)陷入局部最優(yōu)解，這些現(xiàn)象的產(chǎn)生主要是因?yàn)檫M(jìn)化過程中個(gè)別較優(yōu)個(gè)體過早地在種群中大量繁殖，種群多樣性大大降低。為避免該現(xiàn)象，IGA的初始種群中一部分的個(gè)體由啟發(fā)式算法生成，另一部分個(gè)體隨機(jī)生成，以保證初始種群的多樣性，具體組成比例由實(shí)驗(yàn)來確定。

2.3 改進(jìn)的競(jìng)爭(zhēng)機(jī)制

本文針對(duì)傳統(tǒng)遺傳算法的早熟和多樣性差的特點(diǎn)[17]，在兩點(diǎn)交叉算子的基礎(chǔ)上提出了一種基于相似度的競(jìng)爭(zhēng)和選擇機(jī)制。在進(jìn)行交叉操作的時(shí)候，兩個(gè)父代之間的相似度越大，越不易于新的基因型的產(chǎn)生[18]；所以該機(jī)制就在進(jìn)行交叉操作之前，先檢驗(yàn)兩個(gè)父代之間的相似度。相似度等于基因串對(duì)應(yīng)位置的基因相同的個(gè)數(shù)除以基因串的長(zhǎng)度。以整數(shù)編碼為例，設(shè)兩個(gè)父代個(gè)體X，Y為:

(10)

其中:xi∈Z,yi∈Z,i=1,2,…,m。

則兩個(gè)個(gè)體之間的相似度p(X,Y)為：

(11)

根據(jù)IGA的算法流程，其主要步驟如下：

1)運(yùn)用啟發(fā)式策略生成一半初始種群(為了提供高質(zhì)量的初始解)，另外一半用隨機(jī)的方法生成(為了保證初始解的多樣性)。

2)計(jì)算種群中每一個(gè)個(gè)體的適應(yīng)值。

3)按照一定的規(guī)則選擇進(jìn)行下一代的個(gè)體，該規(guī)則與個(gè)體的適應(yīng)值相關(guān)。本文運(yùn)用輪盤賭的選擇方法。

4)根據(jù)本文提出的相似度的計(jì)算規(guī)則，計(jì)算父代的相似度p。如果p<0.8，則進(jìn)行交叉操作，否則返回3)。

5)按照一定的變異概率Pm進(jìn)行個(gè)體變異。

6)判斷現(xiàn)在的狀態(tài)是否滿足停止條件，如果滿足就進(jìn)入下一步，否則返回3)。

7)輸出相關(guān)信息，包括最優(yōu)解和運(yùn)行的時(shí)間等信息。

3 實(shí)驗(yàn)數(shù)據(jù)與方法

本文實(shí)驗(yàn)主要解決以下三個(gè)問題：1)IMQ指標(biāo)能否有效減少孤立簇的數(shù)目；2)對(duì)比IHC算法和基于GNE遺傳算法(簡(jiǎn)稱GNE算法)，IGA是否能找到質(zhì)量更高的解；3)對(duì)比IGA、IHC和GNE算法的求解的魯棒性。

3.1 數(shù)據(jù)來源

實(shí)驗(yàn)主要分為兩部分：第一部分是基于真實(shí)數(shù)據(jù)的實(shí)驗(yàn)，第二部分是基于仿真數(shù)據(jù)的實(shí)驗(yàn)。在第一部分中，本文所用實(shí)例來源于Mancoridis和Mitchell開發(fā)的軟件模塊化工具Bunch軟件，且被許多學(xué)者采用，如Kumari等[2]、Praditwong等[7]。MDG的頂點(diǎn)數(shù)從27～148，邊數(shù)從75～1 745。16個(gè)實(shí)例的具體信息如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)來源Tab. 2 Data source used in the experiment

3.2 實(shí)驗(yàn)內(nèi)容

每組實(shí)驗(yàn)中，將IGA分別與GNE算法和IHC算法的解的質(zhì)量作對(duì)比。為了有效跳出局部最優(yōu)解，IHC算法集成了模擬退火機(jī)制。該算法已集成在著名的Bunch軟件中，是同類研究的重要對(duì)比算法[14]。

Bunch中IHC算法設(shè)置了一個(gè)閾值η(0%≤η≤100%) 來計(jì)算在每次爬山算法迭代過程中需要考慮的相鄰節(jié)點(diǎn)的最小值[7]。若相鄰節(jié)點(diǎn)的個(gè)數(shù)少于200，則η取75%；若大于200，則將需要考慮的相鄰節(jié)點(diǎn)的個(gè)數(shù)設(shè)定為200。這樣的設(shè)定無疑會(huì)增加算法的運(yùn)行時(shí)間，但同時(shí)也會(huì)增加找到更好的解的概率。IHC采用模擬退火機(jī)制避免陷入局部最優(yōu)解，即算法以一定的概率P(A)接受質(zhì)量稍差的解，公式如下：

(12)

其中k表示迭代的次數(shù)。由于本文提出了對(duì)軟件模塊化質(zhì)量的改進(jìn)方案，當(dāng)使用IMQ指標(biāo)時(shí)，將IHC的MQ指標(biāo)替換為IMQ指標(biāo)即可。連續(xù)性降低的比率α被設(shè)置為0.9，初始的溫度T(0)=100。此外初始爬山點(diǎn)的個(gè)數(shù)設(shè)置為10個(gè)。以上IHC參數(shù)設(shè)置的合理性，請(qǐng)參考文獻(xiàn)[14]。

首先，為了保證初始種群的多樣性， IGA的初始種群中一部分的個(gè)體由啟發(fā)式算法生成，具體多少比例的初始種群是由實(shí)驗(yàn)來確定的。本文一共設(shè)置了三組實(shí)驗(yàn)。由啟發(fā)式算法和隨機(jī)方式生成初始種群的比例分別為(1/4,3/4)，(1/2,1/2)，(3/4,1/4)?；谡鎸?shí)數(shù)據(jù)，分別記錄下以IMQ為軟件模塊化指標(biāo)的IGA重復(fù)30次實(shí)驗(yàn)的平均值。

對(duì)比實(shí)驗(yàn)中，分別用GNE算法、IGA和IHC對(duì)每個(gè)實(shí)例進(jìn)行模塊化劃分。由于進(jìn)化算法的機(jī)制中存在隨機(jī)因素，每次運(yùn)行算法得到的結(jié)果往往不同，僅一次運(yùn)行結(jié)果并不能說明問題。所以在實(shí)驗(yàn)中，給定一個(gè)實(shí)例，每個(gè)算法運(yùn)行30次，記錄每次搜索到的解。為了公平比較，實(shí)驗(yàn)程序確保三種算法運(yùn)行足夠長(zhǎng)時(shí)間，并且運(yùn)行相同時(shí)間。該時(shí)間由反復(fù)實(shí)驗(yàn)確定，為60 s。為了對(duì)比IMQ指標(biāo)抑制孤立簇的效果，針對(duì)真實(shí)數(shù)據(jù)，本文分別用IMQ指標(biāo)和MQ指標(biāo)進(jìn)行實(shí)驗(yàn)，記錄下三個(gè)算法每次進(jìn)行模塊化劃分后的孤立簇的數(shù)目，并用IMQ指標(biāo)做仿真實(shí)驗(yàn)對(duì)比三個(gè)算法在處理大規(guī)模問題時(shí)的性能。

運(yùn)行實(shí)驗(yàn)的平臺(tái)配置為：3.2 GHz Intel Core i5- 3470 CPU (4×256 KB L2 緩存和6M L3 緩存)，DDR3 8 GB內(nèi)存。遺傳算法的其他參數(shù)的設(shè)定是通過反復(fù)實(shí)驗(yàn)確定的，具體參數(shù)取值：種群規(guī)模=100，交叉概率Pc=0.8， 變異概率Pm=0.2。

3.3 分析方法

為驗(yàn)證新的軟件模塊化指標(biāo)IMQ抑制孤立簇的效果，針對(duì)每個(gè)實(shí)例，分別用MQ指標(biāo)和IMQ指標(biāo)作為三個(gè)算法的優(yōu)化目標(biāo)重復(fù)實(shí)驗(yàn)30次，對(duì)比得到的最優(yōu)解的孤立簇?cái)?shù)目的平均值。

為檢驗(yàn)IGA的尋優(yōu)能力，實(shí)驗(yàn)對(duì)比30次實(shí)驗(yàn)所取最優(yōu)解的平均值和標(biāo)準(zhǔn)差。由于實(shí)驗(yàn)主要檢驗(yàn)IGA的性能，本文分別比較IGA和GNE算法，IGA和IHC的實(shí)驗(yàn)結(jié)果。所有結(jié)果均用獨(dú)立樣本雙尾t檢驗(yàn)進(jìn)行統(tǒng)計(jì)分析，置信水平為95%。檢驗(yàn)是用T分布理論來推論差異發(fā)生的概率，從而比較兩個(gè)平均數(shù)的差異是否顯著[19-20]。由于已知數(shù)據(jù)的均值和標(biāo)準(zhǔn)差，本文用的是統(tǒng)計(jì)分析常用的參數(shù)化t檢驗(yàn)，而不是非參數(shù)t檢驗(yàn)。當(dāng)t檢驗(yàn)的p值小于0.05的時(shí)候，說明兩個(gè)樣本的均值在95%置信水平內(nèi)存在顯著的差異。此外，本文還計(jì)算了效應(yīng)值Cohen’s d index，以便于解釋結(jié)果的顯著性。Cohen’s d index常用在T檢驗(yàn)中表示兩個(gè)均值之間標(biāo)準(zhǔn)化差異的效應(yīng)值[2]。據(jù)經(jīng)驗(yàn)，效應(yīng)值為0.20左右表示顯著性較小; 0.50左右表示顯著性中等，0.80左右表示顯著性較大。

4 結(jié)果及分析

4.1 基于真實(shí)數(shù)據(jù)的實(shí)驗(yàn)

首先，本文通過實(shí)驗(yàn)來確定由啟發(fā)式算法組成初始種群的比例。分別進(jìn)行了三組對(duì)照實(shí)驗(yàn)，由啟發(fā)式算法和隨機(jī)方式生成初始種群的比例分別為(1/4,3/4)，(1/2,1/2)，(3/4,1/4)。最后由IGA運(yùn)行30次得到的IMQ的平均值如表3所示。從結(jié)果可以看出，當(dāng)初始種群組成比例為(1/2,1/2)時(shí)，IGA得到的IMQ值在16個(gè)真實(shí)案例里面有9個(gè)是最高的，優(yōu)勢(shì)明顯。當(dāng)初始種群的組成比例為(1/4,3/4)時(shí)，啟發(fā)式算法組成的初始種群的比例偏低，其優(yōu)勢(shì)顯示不出；當(dāng)初始種群的組成比例為(3/4,1/4)時(shí)，啟發(fā)式算法組成的初始種群的比例偏高，初始種群結(jié)構(gòu)單一，多樣性無法保證，IGA容易陷入局部最優(yōu)解。實(shí)驗(yàn)結(jié)果證明，由啟發(fā)式算法和隨機(jī)方式生成初始種群的比例分別為(1/2,1/2)時(shí)，IGA搜索最優(yōu)解的效果最好。之后的對(duì)比實(shí)驗(yàn)中IGA初始種群都是一半由啟發(fā)式算法生成，而另一半由隨機(jī)方法生成。

表3 初始種群不同組成比例下IGA得到的IMQ值Tab. 3 IMQ value obtained by IGA under different composition of initial population

三個(gè)算法分別用兩個(gè)指標(biāo)得到的最優(yōu)解的孤立簇?cái)?shù)目的平均值如表4所示。由表4可以看出，IMQ指標(biāo)在降低孤立簇?cái)?shù)目上效果顯著：在以IMQ為目標(biāo)函數(shù)的實(shí)驗(yàn)中，GNE算法和IGA針對(duì)每個(gè)實(shí)例的30次實(shí)驗(yàn)所得到的孤立簇?cái)?shù)目的平均值均為零，均小于以MQ為目標(biāo)函數(shù)的結(jié)果值；且在IHC算法得到的結(jié)果中，IMQ指標(biāo)的孤立簇的平均數(shù)目比MQ指標(biāo)的少。由此，本文剩下的實(shí)驗(yàn)部分采用能有效減少孤立簇?cái)?shù)目的IMQ指標(biāo)作為算法的尋優(yōu)目標(biāo)。另外，在以MQ為目標(biāo)函數(shù)的實(shí)驗(yàn)中，IGA降低孤立簇的效果最顯著，孤立簇的平均個(gè)數(shù)最少，GNE最差。三種算法的性能對(duì)比還需通過進(jìn)一步的實(shí)驗(yàn)驗(yàn)證。

表4 兩個(gè)軟件模塊化指標(biāo)的孤立簇?cái)?shù)目對(duì)比Tab. 4 Comparison of the number of isolated clusters by two software modularization qualities

除此之外，實(shí)驗(yàn)得到了三個(gè)算法針對(duì)表2中每個(gè)實(shí)例搜索到的最優(yōu)解IMQ值的平均值及標(biāo)準(zhǔn)差以及T檢驗(yàn)的p值和效應(yīng)值，本文對(duì)三個(gè)算法進(jìn)行兩兩比較，比較結(jié)果如表5所示。

從表5中可得如下結(jié)論：

1)從每個(gè)實(shí)例的均值比較來看，IGA找到的最好解的質(zhì)量均優(yōu)于GNE算法和IHC算法，并且所有實(shí)例里面的p值都遠(yuǎn)遠(yuǎn)小于0.05，說明在95%的置信水平下，IGA在相同的時(shí)間內(nèi)取得解的質(zhì)量要明顯優(yōu)于GNE算法和IHC算法。相比之下，IHC算法重復(fù)運(yùn)行30次得到的IMQ的平均值最低，說明IHC算法在搜索過程中容易落入局部最優(yōu)解，具有短視的缺點(diǎn)。

2)對(duì)于每個(gè)實(shí)例的標(biāo)準(zhǔn)差，IGA在所有實(shí)例中的標(biāo)準(zhǔn)差都比IHC算法的標(biāo)準(zhǔn)差要小。在與GNE算法的比較實(shí)驗(yàn)中，IGA在16個(gè)實(shí)例中有13個(gè)實(shí)例的標(biāo)準(zhǔn)差比GNE算法的小，除了“inn”“bip”“exim”。也正說明了IGA的魯棒性比較高，每次運(yùn)行結(jié)果可行度較高。

3)在所有的16個(gè)實(shí)例的實(shí)驗(yàn)中，效應(yīng)值的絕對(duì)值都大于0.8，說明兩種算法得到結(jié)果的均值差距足夠大，進(jìn)一步說明了IGA的優(yōu)勢(shì)很顯著。

4.2 基于仿真數(shù)據(jù)的實(shí)驗(yàn)

雖然是基于實(shí)際數(shù)據(jù)，但以上對(duì)比實(shí)驗(yàn)中的問題規(guī)模偏小，且不便驗(yàn)證MDG密度的增加對(duì)結(jié)果的影響，為了對(duì)比三個(gè)算法在處理大規(guī)模問題時(shí)的性能，本文設(shè)計(jì)了基于仿真數(shù)據(jù)的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表6所示。通過觀察數(shù)據(jù)，可得到以下結(jié)論：

1)在這30個(gè)算例中，IGA總能夠找到比GNE算法和IHC算法更高的IMQ值，說明IGA能有效跳出局部最優(yōu)解，在求解質(zhì)量方面優(yōu)于GNE算法和IHC算法。所有算例里面的p值都遠(yuǎn)遠(yuǎn)小于0.05，證明了在95%的置信水平下IGA得到的解的質(zhì)量顯著優(yōu)于GNE算法和IHC算法。

2)盡管引入了模擬退火機(jī)制，IHC算法的解的質(zhì)量甚至不如GNE算法，原因是對(duì)于大規(guī)模問題，模擬退火機(jī)制也很難克服爬山算法的短視缺點(diǎn)；特別是在頂點(diǎn)數(shù)增加，圖的密度增加的時(shí)候，IHC算法就可能得到較差的解。例如在|V|=300，|E|=33 637的案例9中，由于IMQ指標(biāo)加入了對(duì)孤立簇的懲罰，IHC算法單次搜索到了負(fù)值，30次重復(fù)實(shí)驗(yàn)所得IMQ值的均值是0.9，說明該算法不穩(wěn)定。

3)大多數(shù)情況下，IGA所得結(jié)果的標(biāo)準(zhǔn)差相對(duì)較小，說明IGA有較強(qiáng)的魯棒性和穩(wěn)定性，即：每次算法運(yùn)行結(jié)果不會(huì)相差很大。

4)在所有的仿真數(shù)據(jù)的實(shí)驗(yàn)中，效應(yīng)值的絕對(duì)值都大于0.8，說明了IGA的優(yōu)勢(shì)顯著。

5)給定頂點(diǎn)數(shù)目，MDG密度的增加對(duì)IGA的魯棒性影響不大，密度越高，IGA得到結(jié)果的標(biāo)準(zhǔn)差越小，但對(duì)IHC算法的魯棒性影響較大。雖然MDG密度的增加對(duì)GNE算法的魯棒性影響也不是很大，但是這是GNE算法過早收斂、陷入局部最優(yōu)的結(jié)果。從IGA和GNE算法的對(duì)比結(jié)果中可以看出，IGA處理稀疏MDG的性能較優(yōu)，得到IMQ的值比GNE算法得到的IMQ值高很多。相比之下，IGA處理稠密MDG的性能較弱，雖然得到的解的質(zhì)量最高，但是與GNE算法得到的IMQ值越來越接近。現(xiàn)實(shí)中的軟件系統(tǒng)大多是稀疏，Mitchell等[14]的研究提出軟件系統(tǒng)的平均密度為17%，由此可見，IGA具有較強(qiáng)的實(shí)用性。

實(shí)驗(yàn)結(jié)果表明：相對(duì)于GNE算法和IHC算法，IGA能找到質(zhì)量更高的解，且有更好的魯棒性。

表5 GNE、IHC和IGA真實(shí)數(shù)據(jù)結(jié)果Tab. 5 Results of GNE, IHC and IGA on real data

表6 GNE, IHC和IGA仿真數(shù)據(jù)結(jié)果Tab. 6 Results of GNE, IHC and IGA on simulated data

5 結(jié)語

本文運(yùn)用基于搜索的方法來解決軟件模塊化問題，與傳統(tǒng)的同類研究不同，本研究設(shè)計(jì)了相應(yīng)機(jī)制抑制解中的孤立簇現(xiàn)象。研究工作提出一個(gè)新的軟件模塊化指標(biāo)IMQ，并為抑制孤立簇的模塊化優(yōu)化問題建立了數(shù)學(xué)模型。最重要的是設(shè)計(jì)了IGA用于尋找得到更高質(zhì)量的解，并通過兩類對(duì)比實(shí)驗(yàn)，證明了IMQ指標(biāo)能夠有效減少孤立簇的數(shù)目，且IGA相比IHC算法和GNE算法具有更強(qiáng)的尋優(yōu)能力和更好的魯棒性。

后續(xù)研究工作計(jì)劃將從如下幾個(gè)方面展開：

1)運(yùn)用改進(jìn)的啟發(fā)式初始種群生成策略、高級(jí)的交叉方式和變異方式改進(jìn)其他進(jìn)化算法，比如：粒子群、文化基因算法等，并與IGA比較，分析各自優(yōu)缺點(diǎn)，進(jìn)一步完善改進(jìn)方案。

2)考慮多目標(biāo)優(yōu)化算法來平衡內(nèi)聚和耦合兩個(gè)指標(biāo)，怎樣將自適應(yīng)算法與多目標(biāo)優(yōu)化算法相結(jié)合解決同類問題。

3)運(yùn)用啟發(fā)式初始種群生成策略和基于相似度的競(jìng)爭(zhēng)和選擇機(jī)制改進(jìn)傳統(tǒng)多目標(biāo)優(yōu)化算法，比如SPEA-Ⅱ算法、NSGA-Ⅲ算法等。

參考文獻(xiàn)(References)

[1] HARMAN M. The current state and future of search based software engineering [C]// FOSE ’07: Proceedings of the 2007 Future of Software Engineering. Washington, DC: IEEE Computer Society, 2007: 342-357.

[2] KUMARI A C, SRINIVAS K. Hyper-heuristic approach for multi-objective software module clustering [J]. Journal of Systems and Software, 2016, 117: 384-401.

[3] STEVENS W P, MYERS G J, CONSTANTINE L L. Structured design [J]. IBM Systems Journal, 1974, 13(2): 115-139.

[4] HARRISON R, COUNSELL S J, NITHI R V, et al. An evaluation of the MOOD set of object-oriented software metrics [J]. IEEE Transactions on Software Engineering, 1998, 24(6): 491-496.

[5] TUCKER A, SWIFT S, LIU X, et al. Variable grouping in multivariate time series via correlation [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2001, 31(2): 235-245.

[6] MANCORIDIS S, MITCHELL B S, CHEN Y, et al. Bunch: a clustering tool for the recovery and maintenance of software system structures [C]// ICSM ’99: Proceedings of the 1999 IEEE International Conference on Software Maintenance. Washington, DC: IEEE Computer Society, 1999: 50-59.

[7] PRADITWONG K, HARMAN M, YAO X, et al. Software module clustering as a multi-objective search problem [J]. IEEE Transactions on Software Engineering, 2011, 37(2): 264-282.

[8] MacQUEEN J. Some methods for classification and analysis of multivariate observations [C]// Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley: University of California Press, 1967: 281-297.

[9] HADI A S. Finding groups in data: an introduction to chster analysis [J]. Technometrics, 1992, 34(1): 111-112.

[10] BANDYOPADHYAY S, MAULIK U. Genetic clustering for automatic evolution of clusters and application to image classification [J]. Pattern Recognition, 2002, 35(6): 1197-1208.

[11] OMRAN M G H, SALMAN A, ENGELBRECHT A P. Dynamic clustering using particle swarm optimization with application in image segmentation [J]. Pattern Analysis & Applications, 2006, 8(4): 332.

[12] MAQBOOL O, BABRI H. Hierarchical clustering for software architecture recovery [J]. IEEE Transactions on Software Engineering, 2007, 33(11): 759-780.

[13] HARMAN M, HIERONS R M, PROCTOR M. A new representation and crossover operator for search-based optimization of software modularization [C]// GECCO ’02: Proceedings of the Genetic and Evolutionary Computation Conference. San Francisco, CA: Morgan Kaufmann Publishers, 2002: 1351-1358.

[14] MITCHELL B S, MANCORIDIS S. On the evaluation of the Bunch search-based software modularization algorithm [J]. Soft Computing, 2008, 12(1): 77-93.

[15] MKAOUER W, KESSENTINI M, SHAOUT A, et al. Many-objective software remodularization using NSGA-Ⅲ [J]. ACM Transactions on Software Engineering & Methodology, 2015, 24(3): Article No. 17.

[16] AKBALIK A, HADJ-ALOUANE A B, SAUER N, et al. NP-hard and polynomial cases for the single-item lot sizing problem with batch ordering under capacity reservation contract [J]. European Journal of Operational Research, 2017, 257(2): 483-493.

[17] 楊劼,高紅,劉濤,等.基于改進(jìn)遺傳算法的泊位岸橋協(xié)調(diào)調(diào)度優(yōu)化[J].計(jì)算機(jī)應(yīng)用,2016,36(11):3136-3140. (YANG J, GAO H, LIU T, et al. Integrated berth and quay-crane scheduling based on improved genetic algorithm [J]. Journal of Computer Applications, 2016, 36(11): 3136-3140.)

[18] 范青武,王普,高學(xué)金.一種基于有向交叉的遺傳算法[J].控制與決策,2009,24(4):542-546. (FAN Q W, WANG P, GAO X J, et al. Improved genetic algorithm based on oriented crossover [J]. Control and Decision, 2009, 24(4): 542-546.)

[19] ARCURI A. A practical guide for using statistical tests to assess randomized algorithms in software engineering [C]// ICSE ’11: Proceedings of the 33rd International Conference on Software Engineering. New York: ACM, 2011: 1-10.

[20] PRADITWONG K. Solving software module clustering problem by evolutionary algorithms [C]// JCSSE 2011: Proceedings of the Eighth International Joint Conference on Computer Science and Software Engineering. Piscataway, NJ: IEEE, 2011: 154-159.

This work is partially supported by the National Natural Science Foundation of China (71302051).

MULifeng, born in 1978, Ph. D., lecturer. His research interests include search-based software engineering, evolutionary algorithm design.

WANGFangyuan, born in 1994, M. S. candidate. Her research interests include search-based software engineering, evolutionary algorithm design.