集成偏好的高维多目标最优软件产品选择算法-向毅 , 周育人 , 蔡少伟.pdf

上善若水

231

20页

0次

2022-05-24

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2020,31(2):282−301 [doi: 10.13328/j.cnki.jos.005637] http://www.jos.org.cn

集成偏好的高维多目标最优软件产品选择算法

∗

向

毅

周育人

蔡少伟

(中山大学数据科学与计算机学院,广东广州 510006)

(中国科学院软件研究所,北京 100190)

通讯作者: 周育人, E-mail: zhouyuren@mail.sysu.edu.cn

摘要: 在基于搜索的软件工程研究领域,高维多目标最优软件产品选择问题是当前的一个研究热点.既往工作

主要采用后验方式(即先搜索再选择)处理软件工程师或终端用户的偏好.与此不同,将用户偏好集成于优化过程,提

出了一种新算法以定向搜索用户最感兴趣的软件产品.在算法中,运用权向量表达用户偏好,采用成就标量化函数

(achievement scalarizing function,简称 ASF)集成各个优化目标,并定义一种新关系比较个体之间的优劣.为了增强算

法快速搜索到有效解的能力,分别采用 DPLL/CDCL 类型和随机局部搜索(SLS)类型可满足性(SAT)求解器实现了替

换算子和修复算子.为了验证新算法的有效性,采用 21 个广泛使用的特征模型进行仿真实验,其中最大特征数为 62

482,最大约束数为 343 944.实验结果表明,基于 DPLL/CDCL 类型 SAT 求解器的替换算子有助于算法返回有效软件

产品;基于 SLS 类型 SAT 求解器的修复算子有助于快速搜索到尽可能满足用户偏好的最终产品.在处理带偏好的高

维多目标最优软件产品选择问题时,综合运用两类 SAT 求解器是一种行之有效的方法.

关键词: 基于搜索的软件工程;软件产品线;最优软件产品选择;高维多目标优化;用户偏好;SAT 求解器

中图法分类号: TP311

中文引用格式: 向毅,周育人,蔡少伟.集成偏好的高维多目标最优软件产品选择算法.软件学报,2020,31(2):282−301. http://

www.jos.org.cn/1000-9825/5637.htm

英文引用格式: Xiang Y, Zhou YR, Cai SW. Integrating preference in many-objective optimal software product selection

algorithm. Ruan Jian Xue Bao/Journal of Software, 2020,31(2):282−301 (in Chinese). http://www.jos.org.cn/1000-9825/5637.htm

Integrating Preference in Many-objective Optimal So ftware Product Selection Algorithm

XIANG Yi

, ZHOU Yu-Ren

, CAI Shao-Wei

(School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China)

(Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

Abstra ct : In search-based software engineering, one of the active research topics is the many-objective optimal software selection from

software product lines. Previous works in this area mainly dealt with the preference from software engineers and end users in a posteriori

way (namely selection after search). Different from that, this study integrates users’ preference into the optimization process and proposes

a new algorithm that can conduct a directed search for software products in which users are most interested. In the new algorithm, the

users’ preference is expressed as a weight vector, and an achievement scalarizing function (ASF) is used to aggregate all the optimization

objectives. In addition, a new relation is defined to compare different individuals. To enhance the ability of the algorithm when searching

for valid solutions, a substitution operator and a repair operator are implemented by using DPLL/CDCL-type and SLS-type SAT solvers,

respectively. To verify the effectiveness of the new algorithm, 21 feature models widely used before are adopted to conduct simulation

∗ 基金项目: 国家自然科学基金(61906069, 61773410, 61502464); 广东省基础与应用基础研究基金(2019A1515011411, 2019

A1515011700); 中国博士后科学基金(2019M662912); 中央高校基本科研业务费专项资金(x2rjD2190840/2019MS088)

Foundation item: National Natural Science Foundation of China (61906069, 61773410, 61502464); Guangdong Basic and Applied

Basic Research Foundation (2019A1515011411, 2019A1515011700); Project Funded by China Postdoctoral Science Foundation (2019

M662912); Fundamental Research Funds for the Central Universities (x2rjD2190840/2019MS088)

收稿时间: 2018-05-10; 修改时间: 2018-07-11; 采用时间: 2018-08-29

向毅等:集成偏好的高维多目标最优软件产品选择算法

283

experiments. In these models, the largest number of features and that of constraints are 62 482 and 343 944, respectively. As shown by the

experimental results, the substitution operator, which is based on a DPLL/CDCL-type SAT solver, is beneficial for returning valid

software products, while the repair operator implemented by an SLS-type SAT solver contributes to find products that can satisfy the

preference of users as much as possible. In summary, the simultaneous use of two types of SAT solvers is a feasible and effective way to

handle the many-objective optimal software product selection problem where users’ preference should be considered.

Key words: search-based software engineering; software product line; optimal software product selection; many-objective optimization;

users’ preference; SAT solver

基于搜索的软件工程(search-based software engineering,简称 SBSE)

[1,2]

运用元启发式搜索技术,比如遗传算

法

[3]

、模拟退火算法

[4]

等,从问题的解空间出发解决软件工程的相关问题.它是传统软件工程和智能计算相结合

的新兴研究领域

[5]

.基于搜索的软件工程几乎适用于软件开发的所有阶段,包括需求分析、软件设计与开发、软

件测试与维护等

[6−10]

基于搜索的软件工程同样适用于软件产品线的配置问题.软件产品线(software product line,简称 SPL)

[11]

定

义了一系列可通过模块化软件部件实现自动组装的软件产品.一般而言,这些软件产品具有一些通用功能.但是

在特定的系统功能方面,各软件产品又存在差异.软件产品线定义的系列产品可由特征模型(feature model,简称

FM)简洁地表示

[12]

.在 FM 中,每个特征(feature)代表软件产品线的一个部件或功能,特征模型则清晰地表达了各

特征之间的约束关系

[13]

.配置软件产品线时,除了考虑特征之间的约束关系(满足所有约束关系的配置称为可行

或有效软件产品),一般还需要考虑软件工程师或终端用户的特殊要求,如总费用尽可能少、所选特征尽可能丰

富、已知缺陷数尽可能少等

[14−16]

.事实上,软件产品线的配置是一个离散优化问题,其搜索空间为 {0,1}

,其中,1

表示某个特征被选中,而 0 则表示该特征未被选中,n

表示特征总数.配置软件产品线的任务是在决策空间中搜

索到

“最优”的可行软件产品,故软件产品线配置问题又称为最优软件产品选择问题(或最优特征选择问题).

根据优化目标的个数,一般可分为单目标最优软件产品选择方法和多目标最优软件产品选择方法

[13]

.对于

单目标最优软件产品选择算法

,代表性的工作主要有:Yeh 等人

[17]

提出了基于遗传算法(GA)的软件产品线配置

方法.在该方法中,优化目标为总费用最小化.White 等人

[18]

将最优软件(或特征)选择问题转化成一个多维多选

择的背包问题

(multidimensional multi-choice knapsack problem, 简称 MMKP),并提出了 Filtered Cartesian

Flattening(FCF)

算法以搜索满足全局资源约束(即总预算)的最优软件产品.Müller

[19]

采用模拟退火算法从软件

产品线选择最优软件产品

.他使用了基于价值的投资组合优化方法,唯一的优化目标为最大化利润,定义为收益

和费用之间的固定折衷.此外,Wang 等人

[20]

采用蚁群算法实现了近似最优软件产品的快速搜索.

基于单目标的最优软件产品选择方法仅考虑了特征的少量信息,有时无法很好地满足软件工程师或终端

用户的实际需求

[21]

. 事实上, 最优软件产品选择问题建模为多目标优化问题(multi-objective optimization

problem,

简称 MOP)更符合实际.在 MOP 中,至少存在 2 个优化目标且各目标之间往往相互冲突(即一个目标的

改善通常会导致至少 1 个其他目标的退化).近几年来,演化多目标(evolutionary multi-objective,简称 EMO)研究

领域广泛关注的高维多目标优化问题

(many-objective optimization problem,简称 MaOP)是一类特殊的 MOP,其

中的优化目标个数至少为 4

[22]

.Sayyad 等人

[14]

于 2013 年首次提出了高维多目标最优软件产品选择问题.在选择

最优软件产品时

,他们考虑了 5 个优化目标,并运用两个特征模型比较了 7 种 EMO 算法(包括 NSGA-II

[23]

和

IBEA

[24]

等)的性能表现.实验结果表明,就解的质量、配置正确率和用户偏好满足情况而言,IBEA 优于其他 6 种

EMO 算法.自 Sayyad 等人的开创性工作以后,高维多目标最优软件产品选择问题引起了研究者们的广泛关注.

Henard

等人

[16]

将 IBEA 与可满足性(satisfiability,简称 SAT)求解器相结合,提出了选择最优软件产品的新算法

SATIBEA.在该算法中,SAT 求解器的主要作用是实现新的变异和替换算子.同样地,SATIBEA 也需同时优化 5

个目标.在大规模特征模型上的实验结果表明,SATIBEA 具有较好的拓展性,其性能显著优于 Sayyad 等人

[15]

的

算法

.Hierons 等人

[13]

提出了 ShrInk Prioritise(SIP)策略,用于提升 EMO 算法在配置软件产品线时的性能.SIP 有

机结合了一种新的编码方法(可压缩表示特征模型的染色体)和“1+n”优化策略(即首先优化作为第 1 个目标的

约束违反数

,然后同等优化其他目标).实验结果表明,在成功返回有效软件产品方面,基于 SIP 的 EMO 算法表现

of 20

免费下载

软件学报计算机技术

关注

评论