結合子樹分解的軟件產品線特征選擇方法

王 銘，王立松，魏 歐

(南京航空航天大學 計算機科學與技術學院，南京 210000)

1 引 言

軟件產品線是一組相關聯的系列產品，也被稱為產品家族[1].各軟件產品擁有共同的核心資產，產品家族中產品成員之間的差異被稱為可變性.目前關于產品線工程的研究大多是自動分析技術[3].另外還有關于最優化自動軟件派生的研究.Sayyed等人將特征模型產品派生問題作為多目標優化問題來解決[4]，并在各種類型的多目標優化算法上進行實驗評估.Henard等人則提出使用SAT求解器作為變異手段的優化算法SATIBEA[6].

然而在Sayyad以及Henard等人的研究中，最終種群的有效產品比率(Valid Product Rate，VR)指標則表現不佳.在Sayyad等人的研究中，VR指標在Web Portal模型上進行50000次評估后為73%，而在E-shop這個相對較大的模型上進行500000次評估后為52%.Henard等人則未對VR指標進行評估.考慮到在軟件工程領域，一個合法(沒有約束違反情況)的產品才是能實際可行的方案.產品有效率將是軟件產品線特征模型選擇問題的一個關鍵評估指標.并且對于特征模型選擇問題而言，在保證解集盡可能最優時，解集還應該提供盡可能多的有效解.然而常規的交叉和變異未考慮特征模型的樹形結構，容易在子代生成更多的約束違反項，影響算法的迭代效率，同時也降低了最終解集的有效率.

針對這些問題，本文擴展了原始SATIBEA算法，提出一種基于特征樹子樹的新交叉算子方法——SATIBEA_ST，利用特征樹之間的結構信息，在交叉操作環節，按照特征樹子樹組成的基因塊進行交叉，使得交叉環節不會引入新的約束違反項，有利于保持合法產品配置的結構信息.同時，本文也對環境選擇算子進行修改，提出算法SATIBEA_ST，使得約束違反項目標被優先考慮.本文設計了實驗實現上述兩種方法，并分析實驗數據說明了兩種算法的有效性.

2 基本概念

2.1 特征模型

特征模型(Feature Models)可以被用來描述整個產品家族[7].表達一個產品線上的所有可能產品，并且能夠準確的表達各個特征之間的約束關系.特征通常對應著產品家族的具體可變特征[19].

特征模型常由樹形結構描述，此時稱為特征樹(Feature Tree).特征樹中的節點對應著特征(Feature).節點和節點之間可以存在跨子樹約束(Cross-Tree Constraint，CTC).典型的跨子樹約束包括蘊含(Requires)和互斥(Excludes).

圖1 簡單手機特征模型樣例Fig.1 A feature model of aamobile phone

2.2 產品配置

2.3 多目標優化

多目標優化通常用來研究在具體領域下多個目標同時最優化的問題.多目標優化問題可以由一組目標函數以及相關的約束條件組成.由于存在多個需要優化的目標函數，一個解可能在目標a上較優，而在目標b上較差.因此，需要一個折中的解集，這樣解集被稱為Pareto最優解集(Pareto-optimal set)，這樣的Pareto最優解集中的每個解在解空間都是不可支配的(non-dominated).

令X為產品線SPL的所有可能配置的空間，v=[F1(x),…，Fk(x)]T為k個目標函數的優化目標向量.假定k個目標函數需要最小化.則產品線的特征選擇問題可以描述為：找到一個配置集x，使得x盡可能地接近Pareto最優解集.

3 本文所提出方法

遺傳算法在迭代過程中，需要進行交叉和變異操作，這兩個步驟賦予原種群更豐富的多樣性.由于特征子樹各個節點之間存在約束關系，常規的單點交叉常常會引入新約束違反項.這啟發我們在交叉環節利用特征樹之間的信息來引導交叉操作.

同時，多目標優化在進行搜索最優解時，解個體在評估適應度時，通常將多個目標同等對待[11].而在產品線特征選擇問題上，一個配置必須要保證的目標是合法性(不存在約束違反情況的配置)，這樣啟發我們可以將約束違反這個目標優先考慮.

3.1 SATIBEA

Henard等人采用遺傳算法IBEA進行產品的最優選擇的同時，引入了約束求解器來處理特征模型間復雜的約束關系.他們定義了一種新的變異算子，在后代種群中通過“修補”和“替換”引入一定量的合法解.他們將該算法稱之為SATIBEA，大致步驟如下：

a)初始化：隨機生成一個種群P，種群大小為α；

b)評估種群：按照給定的指標算子評估種群，在該算法中，采用超體積指標IHD；

c)環境選擇：種群P中個體按適應度的大小排序，并刪除適應度較小的個體直到種群P的大小不大于α；

d)判斷終止：若種群滿P足終止條件則挑選出Pareto前沿的所有合法解作為解集輸出，否則繼續下一步；

e)親代選擇：采用錦標賽選擇法對種群P進行親代選擇，挑選出的親代加入交配池P′；

f)交叉：采用單點交叉對交配的個體進行交叉操作，得到子代種群O；

g)變異：采用結合了SAT求解器的變異算子對子代種群O進行變異操作，得到子代種群O′，并將O′加入到父代種群，轉到步驟c).

如何保證變異算子不引入違反約束項，同時賦予種群更多基因多樣這個問題較為棘手.Henard等人在變異操作中引入SAT求解器，按照一定概率將不合法的個體“修補”或“替換”為合法解.值得注意的是約束求解器求解過程較為耗時，若子代全采用SAT求解器進行變異則算法耗時過大.Henard等人在進行子代變異操作時，是按一定概率進行SAT求解器方法變異，一定概率進行常規單點變異.其中，進行單點變異操作的子代可能會繼承親代的約束違反項，同時被引入單點變異算子造成的新約束違反項.

相對與變異算子，保證交叉環節不引入新約束違反項較為容易.本文的工作之一是基于Henard等人的工作，對SATIBEA的交叉算子進行了擴展，使得交叉算子不再引入新的約束違反項.本文將此交叉算子命名為特征樹子樹交叉算子，具體做法為在SATIBEA框架中步驟f)階段采用特征樹子樹交叉算子，本文將修改后的算法命名為SATIBEA_ST.另外本文還對環境選擇算子進行了修改，使得約束違反項較多的個體更容易被淘汰，具體做法為在SATIBEA框架的步驟c)階段采用3.3節方法進行環境選擇，本文將修改后的算法命名為SATIBEA_CP.

3.2 特征樹子樹交叉

特征模型能夠描述整個產品家族配置信息的工具，其中蘊含大量的結構信息，利用其中的信息能更好的結合遺傳算法進行配置優化.

首先給出特征樹子樹的定義：若節點f的所有后繼節點{f1,f2,…，fn}與除了{f1,f2,…，fn}和f以外的節點都沒有Cross-tree Constrains約束關系，則稱f及其后繼節點{f1,f2,…fn}組成的子樹為特征樹子樹.圖2給定了一個簡單手機樣例的特征樹子樹樣例，圖中橢圓所圍的節點構成所有的特征樹子樹，如在進行交叉時，以特征節點“傳感器”作為父節點的子樹可以作為一顆特征樹子樹，設“傳感器”、“重力感應”和“距離感應”在編碼中分別編碼為f4,f8,f9，則進行交叉操作時，親代的個體的f4,f8,f9三個基因位將同時交換.算法有兩個關鍵環節：1)獲取特征模型所有的特征樹子樹，2)以特征樹子樹作為基因塊進行交叉.

圖2 手機特征模型特征子樹樣例Fig.2 Feature-sub-trees of fig.1

算法1.獲取特征模型所有的特征樹子樹：

輸入：特征模型，跨子樹約束集合c.

輸出：特征樹子樹集合t.

Step1.初始化特征樹子樹根節點集合S為空，特征樹子樹集合t為空，令R為特征模型中所有節點組成的集合.令S=R.

Step2.從跨子樹約束集合C中取出一條約束constrainti，并從C中刪除該條約束.設與約束constrainti相關的節點為nj、nk，求出nj與nk的最小公共祖先節點nr.此時，記路徑nr至nj以及nr至nk上所有的節點組成的集合為D，令S=S/D.

Step3.判斷C是否為空.若C為空，對S中的每個節點s∈S，令t為s的所有后繼節點組成的集合，并將t加入到特征樹子樹集合t中.否則轉到Step 2.

算法2.特征樹子樹交叉算子：

輸入：父代個體fi，fj特征樹子樹集合.

輸出：子代個體Oi,Oj.

Step1.按照公式Pi=mi/m計算每個特征樹子樹被選中的概率，其中mi為第i個特征樹子樹ti的節點數，其中ti∈t.m為t中所有特征樹子樹節點數的總和.

3.3 優先考慮約束違反目標

遺傳算法進行環境選擇時，需要對解個體進行適應度評估，依照所優化的目標來計算個體的適應度.而后按照適應度從種群中淘汰個體.給定種群P一個環境限制大小α，按照適應度的大小對種群P中個體排序后，刪除適應度較小的個體，直到種群大小不大于α.這個操作稱為環境選擇算子.

Sayyed等人提出將約束違反項的數量(最小化)作為算法的一個優化目標，以期最終的種群中存在約束違反項為零的個體，即合法解.Sayyed和Henard等人都將此目標與其他優化目標同等考慮.在軟件產品線工程的領域環境下，合法配置即無約束違反項的解才是實際可用的，約束違反項數量這個優化目標理應比其他目標更加重要.

本文將適應度設計為兩個維度，第一維度衡量個體的約束違反程度，第二維度衡量余下的其他優化目標.當需要種群需要淘汰個體時，那些約束違反項數量少的個體將被優先保留.若兩個個體約束違反項數量相同，則優先保留第二個維度上適應度較高的個體.在原算法基礎上擴展了該環境選擇算子，本文將此算法命名為SATIBEA_CP.

4 實驗與分析

4.1 實驗模型與設置

文章采用開源項目SPLOT提供的特征模型[13]，各個特征模型的參數在表1中有詳細描述.其中有三個真實模型Amazon，E-shopping和Drupal，以及四個大規模隨機模型.

表1 特征模型參數Table 1 Feature models

實驗環境為Windows 7 64bits，平臺為2.4Ghz四核處理器，16G內存.根據變異、交叉及環境選擇算子的不同，我們設計了三組算法進行實驗，具體配置如表2所示.

表2 實驗算法配置Table 2 Configation of each algrithem

在求解最優方案解中，上述算法都將分別執行一遍.每次執行將迭代評估50000次，并且為了排除算法的隨機性每個算法將重復執行30次.

4.2 優化目標及評估指標

本文需要優化的有5個目標，為便于比較我們與Sayyed及Henard等人文章[4，6]中設定了一樣的優化目標：

1)違反約束規則數：產品配置所違反的約束規則數目，取最小值；

2)特征豐富度：產品配置中的配置項個數，通常對應特征模型某個具體產品所選擇的特征，取最大值；

3)特征復用度：產品配置中在曾所使用過的配置項，取最大值；

4)已知缺陷個數：產品配置中各個配置項的缺陷數的和，取最小值；

5)成本：每個配置都有一定成本，產品配置應使得配置最小.

本文采用了三個評估指標對實驗進行評估，解集質量定義在兩個方面，其一為解在各個目標上的優化情況.其二為算法是否能得到合法解，以及解集中合法解的占比情況.

1)HV指標 ：Hypervolume，代表了解集在目標空間所支配的超體積大小，它能很好衡量解集在各個優化目標上的優化程度[17].

2)VN指標：Valid Run Number，在30次運行中最終解集中存在至少一個合法解的運行次數，這個指標能衡量算法得到合法解的概率.

3)VR指標：Valid Product Rate，30次運行所得到最終解集的合并解集中合法解所占比率.這個指標能衡量算法得到解集中有效解比例，即能提供給用戶的合法配置數量.

4.3 結果分析

表4給出了三個算法SATIBEA，SATIBEA_ST，SATIBEA_CP在8個特征模型上實驗的數據.圖3至圖10給出了8個特征模型三個算法的HV指標箱形圖，從左到右分別是SATIBEA，SATIBEA_ST和SATIBEA_CP.

圖3 Amazon關于指標HV的算法箱形圖 圖4 Drupal關于指標HV的算法箱形圖

首先所有算法的VN指標都為30次，說明所有算法的每次運行都能得到合法解.應用約束求解器“修補”或“替換”不合法子代為合法子代后對于種群向著合法這個目標進化有很重要的幫助[6].

SATIBEA_ST與SATIBEA相比，在HV指標方面前者在三個模型上優于后者，另外五個模型上劣于后者，平均而言二者差距較小.在VR指標方面，從表3可以看出，前者在所有模型上都要優于后者，特別是1000個節點以上大規模模型上顯著優于后者.我們能得出這樣的結論：SATIBEA_ST能降低隨機搜索對有效解的破壞程度，顯著提高產品有效率，同時也只犧牲少量的超體積指標.特別是大規模模型上，SATIBEA_ST提升效果明顯.

圖5 E-shop關于指標HV的算法箱形圖 圖6 500節點隨機模型關于指標HV的算法箱形圖

SATIBEA_CP與SATIBEA相比，在HV指標方面前者在所有模型上劣于后者，并有著一定的差距.在VR指標方面，前者在所有模型上都為100%的產品有效率，優于后者.可以看到SATIBEA_CP通過犧牲一定量的超體積，來得到100%的產品有效率.

圖7 1000節點隨機模型關于指標HV的算法箱形圖 圖8 2000節點隨機模型關于指標HV的算法箱形圖

SATIBEA_ST與SATIBEA_CP相比，在HV指標方面前者在所有模型上優于后者.在VR指標方面前者不如后者，但SATIBEA_ST也能達到很好的產品有效率，大部分特征模型的VR指標在70%至100%之間.

圖9 5000節點隨機模型關于指標HV的算法箱形圖 圖10 10000節點隨機模型關于指標HV的算法箱形圖

VR指標代表了最終解集中有效解占所有解得比例，是衡量算法所能得到的有效產品的數量，在特征模型選擇領域是很重要的性能指標.從表3可以看出SATIBEA_ST除了在模型Amazon上表現不佳外(但依然優于原始算法)，在其他7個模型上顯著優于原始算法，并且能保證較高的有效產品比例.可以驗證基于子樹的交叉方法的確能很好的保證特征模型選擇得到的產品的合法性.SATIBEA_CP則在所有的特征模型上都能達到100%的有效產品比例，也驗證了優先考慮約束違反目標的有效性.但SATIBEA_CP的解集超體積指標要明顯差于SATIBEA和SATIBEA_ST.其通過犧牲解集超體積指標來達到更高的解集有效比率，在特征的情況下也是適用的，例如客戶對有效產品數量有嚴格要求的情況.

表3 SATIBEA_ST相對SATIBEA在VR指標上的提升Table 3 SATIBEA_ST vs.SATIBEA on VR

5 相關工作

Olaechea等人是最早嘗試優化多目標配置的人員之一.他們采用規劃的方案進行求解精確解，然而這種方案在規模稍大的模型上則很難進行.Sayyed等人則將采用多目標進化算法來解決特征模型產品派生問題[4]，并在各種類型的多目標優化算法上進行實驗評估.他們還將最小化約束違反個數作為一個優化目標，這樣便將約束條件合理地整合進多目標優化方法中.Sayyad等人在文獻中使用了六種多目標進化算法，包括NSGA-II，SPEA2和IBEA等，最終得出結論IBEA在所有測試模型上都優于其他算法.在他們隨后的研究中，進一步發現算法在大模型上較難得到有效產品[5]，Sayyad等人又提出了兩方面的改進方法，首先通過先確定強制特征(所有有效產品都會選擇的特征)和無效特征(所有有效產品都不會選擇的特征)來縮小變量搜索空間，另外還在初始種群中添加進有效個體作為初始種子.他們改進后的算法顯著的提高了NSGA-II和IBEA算法的表現.Henard等人則提出使用SAT求解器作為變異手段的優化算法SATIBEA[6].并在Linux系統變體分析工具庫(LVAT)中的5個大規模模型上進行實驗評估，實驗表明他們的方法顯著優于Sayyad等人提出的方法.

6 結 論

我們討論了特征選擇問題中的約束條件，并詳細展示了特征樹子樹交叉方法SATIBEA_ST，通過大量實驗驗證了該方法能有效性提高原始算法SATIBEA特征選擇產生的產品有效率.同時修改環境選擇算子提出算法SATIBEA_CP，驗證了優先考慮約束違反目標能很好的保證產品有效率.然而算法也有不足之處，如小規模特征模型下，解集的有效率不高；以及約束項的求解依賴SAT求解器，算法需要耗費大量空間和時間.

表4 實驗數據Table 4 Experiment data

下一步的工作將著重考慮不使用SAT求解器直接進行約束關系推導的特征選擇問題，特別是跨子樹關系約束下自上而下的推導特征選擇.

：

[1] Metzger A，Pohl K.Software product line engineering and variability management：achievements and challenges[C].ICSE Future of Software Engineering Track，2014：70-84.

[2] Long C A.Software product lines：practices and patterns[M].Addison-Wesley Longman Publishing Co.Inc，2001.

[3] Benavides D，Segura S，Ruiz-Cortés A.Automated analysis of feature models 20 years later：a literature review[J].Information Systems，2010，35(6)：615-636.

[4] Sayyad A S，Menzies T，Ammar H.On the value of user preferences in search-based software engineering：A case study in software product lines[C].International Conference on Software Engineering，IEEE，2013：492-501.

[5] Sayyad A S，Ingram J，Menzies T，et al.Scalable product line configuration：a straw to break the camel′s back[C].IEEE/ACM，International Conference on Automated Software Engineering，IEEE，2014：465-474.

[6] Henard C，Papadakis M，Harman M，et al.Combining multi-objective search and constraint solving for configuring large software product lines[C].International Conference on Software Engineering，IEEE Press，2015：517-528.

[7] Kang K C，Cohen S G，Hess J A，et al.Feature-oriented domain analysis (FODA)feasibility study[R].Carnegie-Mellon Univ Pittsburgh Pa Software Engineering Inst，1990.

[8] Thum T，Batory D，Kastner C.Reasoning about edits to feature models[C].Proceedings of the 31st International Conference on Software Engineering，IEEE Computer Society，2009：254-264.

[9] Marler R T，Arora J S.Survey of multi-objective optimization methods for engineering[J].Structural and Multidisciplinary Optimization，2004，26(6)：369-395.

[10] Sayyad A S，Goseva-Popstojanova K，Menzies T，et al.On parameter tuning in search based software engineering：a replicated empirical study[C].Replication in Empirical Software Engineering Research (RESER)，2013 3rd International Workshop on.IEEE，2013：84-90.

[11] Schaffer，David J.Multiple objective optimization with vector evaluated genetic algorithms[C].Proceedings of the 1st International Conference on Genetic Algorithms.L.Erlbaum Associates Inc，1985：93-100.

[12] Zitzler E，Künzli S.Indicator-based selection in multiobjective search[C].International Conference on Parallel Problem Solving from Nature，Springer Berlin Heidelberg，2004：832-842.

[13] Mendonca M，Branco M，Cowan D.SPLOT：software product lines online tools[C].Proceedings of the 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications，ACM，2009：761-762.

[14] Durillo J J，Nebro A J.jMetal：a Java framework for multi-objective optimization[J].Advances in Engineering Software，2011，42(10)：760-771.

[15] Le Berre D，Parrain A.The sat4j library，release 2.2，system description[J].Journal on Satisfiability，Boolean Modeling and Computation，2010，7(1)：59-64.

[16] Olaechea R，Stewart S，Czarnecki K，et al.Modelling and multi-objective optimization of quality attributes in variability-rich software[C].International Workshop on Nonfunctional System Properties in Domain Specific Modeling Languages，2012.

[17] Brockhoff D，Friedrich T，Neumann F.Analyzing hypervolume indicator based algorithms[C].International Conference on Parallel Problem Solving from Nature，Springer Berlin Heidelberg，2008：651-660.

[18] Liu Yu-mei，Huang Ming-yu.Research on configuration method for software poroduct based on feature[J].Computer Technology and Development，2016，26(2)：1-6.

[19] Nie Kun-ming，Zhang Li，Fan Zhi-qiang，Systematic literarture review of software product line variability modeling techniques[J].Journal of Software，2013，24(9)：2001-2019.

附中文參考文獻：

[18] 劉玉梅，黃鳴宇.基于特征的軟件產品線配置方法研究[J].計算機技術與發展，2016，26(2)：1-6.

[19] 聶坤明，張 莉，樊志強.軟件產品線可變性建模技術系統綜述[J].軟件學報，2013，24(9)：2001-2019.