牟立峰，王方媛

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

0 引言

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

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

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

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

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

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

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

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

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

1 問題描述

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

1.1 IMQ指標

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

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

(1)

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

(2)

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

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

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

基于以上數(shù)學符號，軟件模塊化問題的數(shù)學規(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)，可知由于如下因素綜合導致無法無法多項式時間內(nèi)求解該類模型：

1)決策變量xik和yk為二進制決策變量；

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

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

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

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

2 改進的遺傳算法

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

2.1 個體編碼

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

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

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

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

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

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

圖2 IMQ迭代變動情況 Fig. 2 IMQ change with iterations

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

2.3 改進的競爭機制

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

(10)

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

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

(11)

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

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

2)計算種群中每一個個體的適應值。

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

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

5)按照一定的變異概率Pm進行個體變異。

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

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

3 實驗數(shù)據(jù)與方法

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

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

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

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

3.2 實驗內(nèi)容

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

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

(12)

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

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

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

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

3.3 分析方法

為驗證新的軟件模塊化指標IMQ抑制孤立簇的效果，針對每個實例，分別用MQ指標和IMQ指標作為三個算法的優(yōu)化目標重復實驗30次，對比得到的最優(yōu)解的孤立簇數(shù)目的平均值。

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

4 結果及分析

4.1 基于真實數(shù)據(jù)的實驗

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

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

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

表4 兩個軟件模塊化指標的孤立簇數(shù)目對比Tab. 4 Comparison of the number of isolated clusters by two software modularization qualities

除此之外，實驗得到了三個算法針對表2中每個實例搜索到的最優(yōu)解IMQ值的平均值及標準差以及T檢驗的p值和效應值，本文對三個算法進行兩兩比較，比較結果如表5所示。

從表5中可得如下結論：

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

2)對于每個實例的標準差，IGA在所有實例中的標準差都比IHC算法的標準差要小。在與GNE算法的比較實驗中，IGA在16個實例中有13個實例的標準差比GNE算法的小，除了“inn”“bip”“exim”。也正說明了IGA的魯棒性比較高，每次運行結果可行度較高。

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

4.2 基于仿真數(shù)據(jù)的實驗

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

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

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

3)大多數(shù)情況下，IGA所得結果的標準差相對較小，說明IGA有較強的魯棒性和穩(wěn)定性，即：每次算法運行結果不會相差很大。

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

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

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

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

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

5 結語

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

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

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

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

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

參考文獻(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] 楊劼,高紅,劉濤,等.基于改進遺傳算法的泊位岸橋協(xié)調(diào)調(diào)度優(yōu)化[J].計算機應用,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] 范青武,王普,高學金.一種基于有向交叉的遺傳算法[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.