在软件工程领域，软件产品线（Software Product Line, SPL）是一种有效的大型软件开发方法，通过组装模块化软件构件来实现产品定制。SPL因其可复用性强、开发成本低、上市周期短等优势而受到了工业界的广泛青睐，同时也是学术界的重要研究对象。其中，有关软件产品线采样方法的研究一直是学者们关注的焦点[1]。

图1 软件产品线示意图

软件产品线采样是指从SPL提供的可能有效的软件产品中挑选出少量代表（样本）。真实的软件产品线所产生的可能有效的软件产品通常数量巨大。因此，以枚举的方式进行采样在实际中几乎不可行。事实上，学术界已提出了若干采样方法，包括随机采样、均匀采样、基于求解器的采样等。这些方法各有优缺点，且适用于特定的情形。我们的工作关注的是一类特殊的采样情形，即多样化采样。实践表明，实现多样化采样是提高SPL性能预测模型准确率的关键步骤[2]，也是提升软件配置效果的内在需求[3-5]。然而，现有的软件产品线采样方法陷入了两难境地——要么无法实现多样化采样，要么实现了多样化采样却难以扩展到大规模软件产品线。针对以上困境，智能算法研究中心的研究人员联合中山大学、伯明翰大学和微软亚洲研究院的专家学者，提出了一种面向软件产品线的可拓展多样化采样方法（Novelty-Search-based Sampling, NSbS）[6]。相关论文已被软件工程领域的旗舰会议IEEE/ACM International Conference on Software Engineering（ICSE 2022）录用。

NSbS的核心思想是利用现成的可满足性（SATisfiablity, SAT）求解器快速生成一个初始样本集，即有效软件产品，然后运用搜索算法（Search Algorithms）不断提升样本集的多样性。在构建NSbS的过程中，多样性的度量和搜索算法的选择是两个关键问题。

针对多样性度量的问题，我们提出以下距离公式：

其中，

以上距离公式包含两项的加权和。其中，第一项加权和度量个体xi和xj在行为空间的距离，其中函数T(xi)将返回产品xi的模块数，而行为空间是指由软件产品中已选模块数组成的空间。第二项加权和度量原始决策空间中软件产品个体之间的距离，的作用是避免生成聚集在特定区域的样本。同时考虑样本在行为空间和决策空间的距离有利于提高样本集的代表性。

针对搜索算法的选择问题，我们选择掘新搜索（Novelty Search, NS）[7]作为搜索算法。实践表明，掘新搜索算法在SPL测试问题上表现优异[8]。最近的理论研究证明，NS的搜索能够覆盖整个特征空间[9]。由于上述理论性质与多样化采样的目标需求高度契合，因此我们选择NS算法作为NSbS的搜索算法。

 图2 NSbS算法

NSbS算法的流程如图2所示。该算法的基本框架与普通的进化算法高度相似，最主要的区别在于NSbS并未明确地优化某个目标函数，而是显式地提升样本的多样性。图3给出了更新档案（样本集）的伪代码。如算法2所示，只有当新个体能够提升样本集的多样性时，才将其加入档案。

 图3 NSbS中更新档案的伪代码

用户可根据自己的需求灵活设置NSbS算法的终止条件，例如在算法的运行时间超过最大值max_t时强制终止算法，或在算法达到相对稳定的状态时自动终止算法。由于目前多数采样算法的运行时间是人为不可控的，因此灵活的终止条件是NSbS算法相较于其他采样算法的一大优势。

我们选择了39个真实的软件产品线作为实验对象以检验NSbS方法的效果。表1给出了包括NSbS在内的五个采样算法的平均运行时间，其中Timeout = 1小时。由表1可知，NSbS和基于SAT求解器的采样算法能处理所有软件产品线，可拓展性好。然而，除NSbS以外的其他算法均出现超时现象。比方说，最新的多样化采样算法DDbS（Diversified Distance-Based Sampling） [2] 仅能处理前11个小规模的SPL，在对剩下的SPL进行处理时均出现超时现象，这说明DDbS的可拓展性很差。

表1 单个样本的采样时间（单位：毫秒）

表2则显示了NSbS与各采样算法的多样性指标比较结果。Wilcoxon假设检验结果表明，NSbS的多样性与DDbS相当，但显著优于其他算法。在所有参与对比的算法中，仅有NSbS算法实现了可扩展的多样化采样。

表2 NSbS与各采样算法多样性比较的Wilcoxon假设检验结果

长期以来，华南理工大学智能算法研究中心致力于将人工智能算法应用于解决软件工程领域的典型问题，目前已取得初步成效。本文提出的NSbS算法可作为一种通用工具用于支持研究人员和工程实践者自主定义距离测度，进而完成特定情形下的多样化采样。另外，我们正在研究如何利用NSbS生成的样本提高性能预测模型的准确率[2]。未来，我们将继续在这个领域进行探索，以期为软件工程的学科建设和发展作出积极贡献。

参考文献

[1] T. Pett, S. Krieter, T. Thüm, et al, “AutoSMP: an evaluation platform for sampling algorithms,” in Proceedings of the 25th ACM International Systems and Software Product Line Conference, New York, 2021, pp. 41–44.

[2] C. Kaltenecker, A. Grebhahn, N. Siegmund, et al, “Distance-based sampling of software configuration spaces,” in Proceedings of the 41st International Conference on Software Engineering(ICSE), 2019, pp. 1084-1094.

[3] C. Henard, M. Papadakis, M. Harman, et al, “Combining multi-objective search and constraint solving for configuring large software product lines,” in Proceedings of the37th International Conference on Software Engineering, 2015, pp. 517-528.

[4] R. M. Hierons, M. Li, X. Liu, et al, “SIP: Optimal product selection from feature models using many-objective evolutionary optimization,” ACM Transactions on Software Engineering and Methodology (TOSEM), vol. 25, no. 2, pp. 1-39, 2016.

[5] Y. Xiang, Y. Zhou, Z. Zheng, et al, “Configuring software product lines by combining many-objective optimization and SAT solvers,” ACM Transactions on Software Engineering and Methodology, vol. 26, no. 4, pp. 1-46, 2018.

[6] Y. Xiang, H. Huang, Y. Zhou, et al, “Search-based diverse sampling from real-world software product lines,” in Proceedings of the 44th IEEE/ACM International Conference on Software Engineering(ICSE), 2022.

[7] J. Lehman, O. S. Kenneth, “Abandoning Objectives: Evolution Through the Search for Novelty Alone,” Evolutionary Computation, vol. 19, no. 2, pp. 189-223, 2011.

[8] Y. Xiang, H. Huang, M. Li, et al, “Looking for novelty in search-based software product line testing,” IEEE Transactions on Software Engineering, 2021, DOI: 10.1109/TSE.2021.3057853.

[9] S. Doncieux, A. Laflaquière, A. Coninx, et al, “Novelty search: A theoretical perspective,” in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), New York, 2019, pp. 99-106.

总编：黄翰

责任编辑：袁中锦

文字：向毅、邓淇

图片：向毅、袁中锦

校稿：何莉怡

时间：2022年4月2日