[發明專利]一種基于多目標優化算法的軟件產品線配置方法

有效

• 申請號: 202011371281.3
• 申請日: 2020-11-30
• 公開（公告）號: CN112488387B
• 公開（公告）日: 2023-08-29
• 發明（設計）人: 周亞博;張力生;桑春艷
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/126;G06F8/30
• 代理公司: 重慶輝騰律師事務所 50215
• 代理人: 王海軍

本發明屬于基于搜索的軟件工程領域，具體為一種基于多目標優化算法的軟件產品線配置方法；所述配置方法包括提取軟件產品的特征和特征間的約束關系；隨機產生指定個數的特征模型配置，形成初始種群；使用隨機局部搜索類型的可滿足性求解器對隨機生成的特征模型配置進行修正；計算修正后的特征模型配置的適應度，選擇適應度較高的特征模型配置進入下一代，將子代特征模型配置集合置于父代特征模型配置集合演化直至得到最終特征模型配置集合；根據軟件產品的非功能性需求，對最終特征模型配置集合進行Pareto排序，得到軟件產品的特征最優解集，并對軟件產品進行配置；本發明大大減少特征規則數量；減少無效配置方案在優化過程所帶來的影響。

技術領域

本發明屬于基于搜索的軟件工程領域，具體為一種基于多目標優化算法的軟件產品線配置方法。

背景技術

軟件產品線工程中開發單個產品的過程稱為產品定制，這其中一個關鍵步驟就是根據產品需求選擇合適的功能模塊。這實際上是特征選擇問題，一般而言，若無自動化支持，特征選擇過程是很難達到最優化的。原因在于，這些功能模塊之間的約束關系一般是通過樹形結構的關系以及跨樹的約束關系表示，限制可組合產品的可能性；且當軟件產品線的規模較大時，其中的特征數量將會十分龐大。這種情況下，在軟件產品線中選擇一個或一組符合需求的軟件產品，其本質上是在一個極大的搜索空間中選擇滿足多個目標的最優產品，并且搜索空間中多數目標之間還存在約束關系，這就為最優化選擇工作帶來了極大的限制。

軟件產品線的多目標最優特征選擇問題，面臨的關鍵問題主要包括：

(1)特征間的依賴和約束關系是判斷配置方案有效性重要依據，任何違反約束的配置方案都是無效的；而隨著特征數量的增大，這些關系變得數量龐大且錯綜復雜，往往會因為選擇一個新特征而導致已選的多個其他特征變得無效，這樣的情況非常普遍，需耗費大量時間。

(2)對非功能性需求的滿足，越來越成為軟件產品成敗的關鍵；非功能性需求實質上是用戶的偏好需求，這對于當前軟件即服務的生產理念而言至關重要，但滿足一個其他質量屬性的同時會導致系統性能在一定程度上下降，因此必須權衡多個非功能性需求的滿足，以達到系統整體質量最優。

(3)一個產品線中明確的功能需求往往成百上千，但用戶明確需要的并不多，所以有效避免用戶對規模龐大的無關特征進行逐個判斷。

目前，相關研究人員提出了許多方法來解決軟件產品線最優產品選擇問題，主要方法有兩類。

單目標最優軟件產品選擇方法，在此類方法中，選擇的目標只有一個，常見的目標就是希望產品的成本最低；采用遺傳算法定義一種代價函數，并將軟件產品線的特征模型建模成最小費用流問題，其中產品配置網絡被表示為流網絡。在相應的產品配置網絡找出最短路徑即可輕松獲得滿足優化目標的最優產品。

多目標最優軟件產品選擇方法，在此類方法中搜索目標考慮更多的特征信息，優化的目標更多，有3個以上甚至10個以上。主要采用演化多目標優化算法(EMO)，并采用在初試種群植入有效產品、提出啟發式技術PUSH和PULL最小化產品違反約束數等方式提高算法得到的產品結果的有效性和多樣性。

可滿足性(SAT)求解器是軟件工程領域通用的約束滿足性求解技術，相比前面所述的在通過改進多目標優化算法機制來提高產品結果的有效性和多樣性，可滿足性(SAT)求解器更具有針對性，有研究結果也證明了將可滿足性(SAT)求解器應用到多目標優化算法的世代種群演化中對個體的修復，產品結果的有效性和多樣性會更優。但在返回大比例有效產品方面依然存在一定困難，有待嘗試和對比更多類型的可滿足性(SAT)求解器應用到多目標優化算法的效果。

這些方法從最優化選擇的角度出發，采用遺傳算法框架為基礎的演化算法求解單目標和多目標最優軟件產品選擇問題，實現了自動化的從軟件產品線中配置符合需求目標的有效產品，但對于高維多目標的最優選擇問題，即優化需求目標在5個以上甚至更多時，這些方法在運行時間和返回大比例有效解方法表現還存在困難。

發明內容