基于MPC編碼方式的軟件產品線配置優(yōu)化算法研究

鄭煒, 曹立鑫, 李隆俊, 李寧

(1.西北工業(yè)大學 軟件與微電子學院, 陜西 西安　710072；2.西北工業(yè)大學 計算機學院, 陜西 西安　710072)

?

基于MPC編碼方式的軟件產品線配置優(yōu)化算法研究

鄭煒1, 曹立鑫1, 李隆俊1, 李寧2

(1.西北工業(yè)大學 軟件與微電子學院, 陜西 西安710072；2.西北工業(yè)大學 計算機學院, 陜西 西安710072)

摘要：軟件產品線配置問題是一個多目標選擇難題，借助于遺傳算法的全局搜索能力可以得到成本低、耗時少、功能健全的最優(yōu)方案解。合理的軟件產品線特征模型映射編碼可以提高求解效率，增加有效解的個數。傳統(tǒng)的直接編碼是對所有特征進行編碼，這使得大型軟件產品線配置問題求解效率低下，并且往往得到無效解?，F行的強制編碼通過隱藏強制節(jié)點來縮小特征編碼范圍，從而達到提高求解效率的目的。然而，很多大型軟件產品線配置問題依然未得到有效解決。針對這一問題，提出一種新型編碼方式——MPC編碼，在強制編碼的基礎上，通過節(jié)點子父關系進一步縮小編碼范圍，更加有效提高求解效率，從而獲取最優(yōu)方案解。最后通過傳統(tǒng)模型與隨機模型進行編碼方式驗證，將MPC編碼與直接編碼以及強制編碼進行對比，證明MPC編碼在求解軟件產品線配置問題中的有效性。

關鍵詞：軟件產品線;軟件配置;多目標優(yōu)化;遺傳算法;特征模型;編碼方式

軟件產品線是一組具有共同體系構架和可復用組件的軟件系統(tǒng)，它們共同構建支持特定領域內產品開發(fā)的軟件平臺。軟件產品線集中體現一種大規(guī)模、大粒度軟件復用實踐，是軟件工程領域中軟件體系結構和軟件重用技術發(fā)展的結果[1]。軟件產品線特征建模是呈現組件模塊之間依賴、互斥等關系的重要手段，自Kang等[2]在1990年介紹面向特征域的分析方法提出后，特征建模就被廣泛運用于軟件產品線中。合理的配置特征模型直接影響和決定了整個產品線的質量和成敗，然而產品線配置解決方案域并不唯一，因此如何獲取最優(yōu)配置方案解變得尤為重要。

遺傳算法是一種求解問題的高度并行性全局搜索算法，它能在搜索過程中自動獲取和積累有關搜索空間的知識，并自適應地控制搜索過程以求得最優(yōu)解，因此它在多目標優(yōu)化問題的優(yōu)化求解中有很大的作用和優(yōu)勢[3]。現階段研究表明，將軟件產品線特征模型映射編碼后，通過遺傳算法可以有效得到最優(yōu)配置方案解[4]。本文將對現有的編碼方式予以改進，通過合并相互依賴性高的模塊，進一步合理縮小軟件產品線特征模型，從而提高獲取最優(yōu)方案解的效率與個數。經過大量實驗證明，這種編碼方式是有效的。

1軟件產品線介紹

1.1特征模型

軟件產品線工程是一個系統(tǒng)的發(fā)展軟件系列產品的方法[5]，其中軟件產品被定義為一個特征集合，一個特征就代表著產品的一項功能。特征模型通常被用來表示一個軟件產品線中的全部產品[2]，特征模型可以表示為可見的樹狀結構，樹的節(jié)點表示特征，樹狀結構將特征節(jié)點相關聯。只要遵循特征模型的依賴、互斥等關系進行配置，就可以得到一個有效的軟件產品配置。例如，圖1為GPS(全球定位系統(tǒng))的特征模型，其根節(jié)點特征為GPS產品線本身。根據父節(jié)點與子節(jié)點之間的關系，其他節(jié)點可分為以下幾種類型：

1)強制型定義該節(jié)點為其父節(jié)點必要節(jié)點，標示為●。如圖1中，尋路系統(tǒng)及人機交互是GPS產品線必須實現的功能，屏幕是人機交互必須具備的配置。

2)可選型定義該節(jié)點為其父節(jié)點的可選節(jié)點，標示為○。如圖1中，提供路況信息是GPS產品線的可選功能。

3)組間或類型定義為其父節(jié)點有且僅有一個子節(jié)點，標示為g[1,1]。如圖1中，屏幕必須在觸摸屏與液晶顯示器中二選一。

4)組間異或類型定義為其父節(jié)點至少有一個子節(jié)點，標示為g[1,*]。如圖1中，尋路系統(tǒng)在3D地圖與自動尋路中至少實現一個功能。

此外，特征之間還存在2種約束關系：

1)等價關系選擇特征A則并需選擇特征B，表示為單箭頭虛線。如圖1中，路況信息與自動尋路為等價關系。

2)互斥關系特征A與特征B不能同時存在，表示為雙箭頭虛線。如圖1中，鍵盤與觸摸屏為互斥關系。

圖1　GPS特征模型

與此同時，特征模型通過特征屬性來擴展特征的額外信息。特征屬性的組成通常為：屬性名稱、閾值與數值。如圖1中人機交互的一個屬性，可知其開銷為8。特征屬性不僅用來統(tǒng)計整個產品的細節(jié)信息，更是合理配置產品功能的重要依據。

1.2多目標優(yōu)化

軟件產品線最優(yōu)化問題主要包含2類目標函數：①盡可能少的成本開銷；②盡完備的實現功能。此問題也被稱為多目標優(yōu)化問題，多目標優(yōu)化旨在找出一組同時滿足所有優(yōu)化目標的解集，再由相關決策做出最終選擇。傳統(tǒng)的多目標優(yōu)化問題解決方案主要有2個：①將多目標轉換為單目標，即把各目標加權，然后選擇權值最高的解作為最優(yōu)解；②僅針對多目標中的某一目標求解，其他目標只需達到一定范圍即可。

然而，傳統(tǒng)的多目標優(yōu)化具有很大的主觀性、不一致性，并不能有效的得到最優(yōu)方案解。通過遺傳算法可以很好解決這些問題，遺傳算法可以并行的處理一組可行的解集，能在一次運算過程中找到滿足多個目標的Pareto最優(yōu)解集。

2新型的編碼方式

軟件產品線編碼方式是將其特征模型依照特征進行編碼，使它的排列形式符合遺傳算法的基因序列，隨后根據特征屬性進行選擇運算，最終獲得軟件產品配置最優(yōu)方案解集。優(yōu)秀的編碼策略能極大的提高獲取最優(yōu)方案解集的效率和個數，文章將介紹三種編碼方式：直接編碼方式，強制編碼，以及一種新型的編碼方式——MPC編碼。

2.1直接編碼

直接編碼即為直接按照層次遍歷順序對特征樹進行編碼。令特征集為S，編碼特征集為S′，則S′=S。例如，圖2為任意特征模型樹，此特征模型的直接編碼如圖3所示。

圖2　特征模型樹

圖3　直接編碼

2.2強制編碼

強制編碼是將強制型節(jié)點和其父節(jié)點結合為1個特征節(jié)點的編碼方式。令特征集為S，編碼特征集為S′，強制型節(jié)點集為M，則S′=S-M。例如，在圖2中，f1存在時f2必定存在，f2存在時f5必定存在，因此f1、f2與f5是共存的，于是可將3個特征結合為1個特征再依照層次遍歷進行編碼，如圖4所示，從而達到減小模型編碼序列的目的，提高求解配置最優(yōu)解的效率。

圖4　強制編碼

圖5　MPC編碼

2.3MPC編碼

MPC編碼又稱強制子父節(jié)點編碼，是基于強制編碼改進的編碼方式，通過隱藏子父關系節(jié)點達到進一步縮小編碼范圍的目的。令特征集為S，編碼特征集為S′，強制型節(jié)點集為M，根節(jié)點為r，組間型節(jié)點g的父節(jié)點為gf，該父節(jié)點gf的非組間型節(jié)點為fc，則：

例如，在圖2中，f3有且僅有一組異或子節(jié)點f7、f8，因此將f3分別與f7、f8相結合，然后將其祖父節(jié)點變?yōu)楦腹?jié)點，如圖5所示。MPC編碼進一步減小模型編碼序列，大量實驗證明，該編碼有效提高了求解最優(yōu)配置解的效率與個數。

3核心算法

文章將采用遺傳算法來求解軟件產品線最優(yōu)配置問題，在算法實現上，首先將特征按照順序排列為一個0、1序列，其中序列第n位對應特征編碼號n-1，當序列第n位值為1時，表示第n-1個特征被選中，當序列第n位值為0時，表示第n-1個特征未被選中。其次，若要得到一個合理、可行的產品配置，需要滿足以下5個規(guī)則：

1)根節(jié)點是必要的，即產品線本身必定存在；

2)任意子節(jié)點存在時，其父節(jié)點必定存在；

3)若某節(jié)點存在強制型子節(jié)點，則當該節(jié)點存在時，其強制型子節(jié)點必定存在；

4)若某節(jié)點存在組間子節(jié)點時，則必須符合組間節(jié)點定義；

5)必須符合等價關系與互斥關系。

因此，我們可根據以上5個規(guī)則生成1個規(guī)則函數，通過算法1來檢驗特征序列是否滿足配置要求。

算法1 規(guī)則函數

輸入：特征序列

算法步驟：

Step1若根節(jié)點為0，違反規(guī)則數+1；

Step2若子節(jié)點為0，父節(jié)點為1，違反規(guī)則數+1；

Step3若父節(jié)點為1，其強制子節(jié)點為0，違反規(guī)則數+1；

Step4若父節(jié)點為1，其組間異或子節(jié)點都為0，違反規(guī)則數+1；

Step5若父節(jié)點為1，其組間或子節(jié)點全部為0或有2個以上為1，違反規(guī)則數+1；

Step6若某節(jié)點為1，其等價節(jié)點為0，違反規(guī)則數+1；

Step7若某節(jié)點為1，其互斥節(jié)點為1，違反規(guī)則數+1。

輸出：違反規(guī)則數。

最終，當得到的違反規(guī)則數等于0時，表示當前特征序列滿足要求，是一個有效的配置方案解。

4實驗配置

4.1遺傳算法

文章將選用2種遺傳算法來對特征編碼方式予以驗證：NSGA-II[6](精英保留的非劣排序遺傳算法)和IBEA[7](基于指標的遺傳算法)。其中，NSGA-II是NSGA[8](非劣排序遺傳算法)的改進算法，有效地將NSGA的計算復雜度從O(mN3)降至O(mN2)，從而進一步提高算法的計算效率和魯棒性。IBEA是一種通用多目標遺傳算法，該算法首次將評價指標函數作為適應度評價方法嵌入到遺傳算法中，使其可以與任意服從Pareto優(yōu)勝規(guī)則的指標相結合，常用的指標有二元additive epsilon指標和二元hypervolume指標。

4.2SPL特征模型

文章選用2個傳統(tǒng)模型E-Shopping[9]和WebPortal[10]，以及2個大數據隨機模型來驗證3種編碼方式，并使用Hypervolume指標(簡稱HV)來評估運算結果。E-Shopping是一個商務網站模型，WebPortal是一個門戶網站模型，2個大數據隨機模型分別采用5 000特征節(jié)點和10 000特征節(jié)點。其中，每個特征模型的基本數據如表1所示。

在實驗中，模擬了5個目標來定義特征模型，并賦予初值：

1)違反規(guī)則數：通過特征模型樹所生成的符合5個規(guī)則的規(guī)則函數，計算遺傳算法個體解違反規(guī)則的數量，取最小值；

2)特征個數：個體解中包含特征的個數，取最大值；

3)特征被用性：個體解中的特征是否曾經被使用過，未曾使用過的特征存在未知缺陷，因此取最大值；

4)已知缺陷個數：曾經被使用過的特征都存在已知的缺陷個數，其值取最小值；

5)開銷：每個特征都存在開銷，其值取最小值。

5實驗結果及結論分析

在實驗中，首先對4個特征模型進行編碼，編碼后的節(jié)點個數如表2所示。其中，EN表示編碼節(jié)點個數，OP表示優(yōu)化概率。優(yōu)化概率的公式為：令特征個數為f，編碼個數為e，則OP=(f-e)/f×100%。通過編碼結果不難看出，MPC編碼進一步縮小了模型大小，在10 000節(jié)點隨機模型中可優(yōu)化比高達40%，使得求解效率得到進一步提高。

表1　特征模型的基本數據

表2　3種編碼節(jié)點統(tǒng)計

表3　E-Shopping數據測評結果

表4　Web-Portal數據測評結果

表5　數據5 000節(jié)點數據測評結果

表6　大數據10 000節(jié)點數據測評結果

在求解最優(yōu)方案解中，2個遺傳算法分別執(zhí)行2遍，1遍為5個等價目標的執(zhí)行，1遍為限定違反規(guī)定數為0的執(zhí)行。每次執(zhí)行評估50 000次并循環(huán)30次，即得到30組解集。表3～表6為4個特征模型的測評結果，其中，VN表示30組解集中含有違反規(guī)則數為0解的解集個數，VR表示30組解集中所有違反規(guī)則數為0解所占全部解百分比。

比較實驗結果可知，在3個編碼方式中，MPC編碼的HV評估值普遍最優(yōu)，直接編碼的HV評估值通常最低，并且，MPC編碼的含有違反規(guī)則數為0解的解集個數以及違反規(guī)則數為0解所占比也大部分高于其他2個算法。同樣地，直接編碼普遍偏低。尤其在大型隨機模型LargeData實驗中，直接編碼和強制編碼并不能得到有效解，然而MPC編碼卻得到了有效的結果。由此可證實，MPC編碼的確在求解軟件配置最優(yōu)解中更加有效率。

6結論

通過大量實驗數據結果可驗證MPC編碼方式較優(yōu)于其他編碼方式，然而此方法還有很多不足之處。眾所周知，軟件產品線特征模型是各式各樣的，本方法不一定能囊括所有特征模型，在某些特定模型下并不能絕對提高獲取最優(yōu)方案解的效率。如何使MPC編碼可以優(yōu)化更多特征模型是我們進一步研究的問題。

參考文獻：

[1]李蘭濤, 王忠民. 基于UML的軟件產品線建模方法研究[J]. 微計算機信息, 2006, 22(30): 204-206

Li Lantao, Wang Zhongmin. Software Product Lines Modeling Approach with UML[J]. Control & Automation, 2006, 22(30): 204-206 (in Chinese)

[2]Kang K, Cohen S, Hess J, et al. Feature-Oriented Domain Analysis (FODA) Feasibility Study[R]. Technical Report CMU/SEI-90-TR-21, SEI, 1990

[3]Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning[M]. Boston, Addison-Wesley Professional,

1989

[4]Abdel Salam Sayyad, Tim Menzies, Hany Ammar. On the Value of User Preferences in Search-Based Software Engineering: A Case Study in Software Product Lines[C]∥35th International Conference on Software Engineering, 2013: 492-501

[5]Clements P, Northrop L. Software Product Lines: Practices and Patterns[M]. Boston, Addison-Wesley Professional, 2001

[6]Kalyanmoy Deb, AmritPratap, Sameer Agarwal, et al. A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197

[7]Zitzler E, Künzli S. Indicator-Based Selection in Multi-Objective Search[C]∥Proc of the 8th hat′1 Conf Oil Parallel Problem Solving from Nature, 2004

[8]Srinivas N, Kalyanmoy Deb. Multi-Objective Optimization Using Ondominated Sorting in Genetic Algorithms[J]. Evolutionary Computation, 1994, 2(3): 221-248

[9]Sean Quan Lau. Domain Analysis of E-Commerce Systems Using Feature-Based Model Templates[D]. University of Waterloo,

2006

[10] Marcilio Mendonca, Thiago Tonelli Bartolomei, Donald Cowan. Decision-Making Coordination in Collaborative Product Configuration[C]∥Proceedings of the 23rd Annual ACM Symposium on Applied Computing, 2008: 108-113

A New Solution of Configuration Based Genetic Algorithm for Software Product Line

Zheng Wei1, Cao Lixin1, Li Longjun1, Li Ning2

(1．Department of Software Engineering，Northwestern Polytechnical University，Xi'an 710072，China 2．Department of Computer Science and Engineering，Northwestern Polytechnical University，Xi'an 710072，China)

Abstract:A problem, the configuration of software product line, is a puzzle of multi-objective optimization. Optimum solution can be accessed effectively by the capability of searching the optimal solution within defined space form genetic algorithm. Reasonable code of software product line feature model can promote efficiency of global searching and increase the number of efficient solutions. This paper improves current code and obtains a new one - Mandatory Parent Child Encoding. A great number of experimental data indicate that this method is feasible.

Keywords:computational efficiency, cost reduction, genetic algorithms, global positioning system, multi-objective optimization, stochastic models; encoding mode, feature model, MPC(Mandatory Parent Child) encoding, software configuration, software product line

中圖分類號：TP311.5

文獻標志碼：A

文章編號:1000-2758(2016)01-0176-07

作者簡介：鄭煒(1975—)，西北工業(yè)大學副教授，主要從事軟件工程及軟件測試的研究。

基金項目：國家自然科學基金(61402370)與中央高?；究蒲袠I(yè)務費專項資金資助

收稿日期：2015-09-12