一句话：提出基于距离度量与新颖性搜索的可扩展多样性采样策略，能从大规模真实软件产品线中生成多样有效配置样本。
真实软件产品线（SPL）通常包含数量巨大、无法枚举的有效配置。为理解这些有效配置构成的空间，需要选取规模小且有效的样本集。现有采样策略要么在所选特征数量维度上多样性不足，要么虽能多样性采样但可扩展性有限（仅能处理约 10^13 的配置空间）。本文提出一种可扩展的多样性采样策略，将专门设计的距离度量与新颖性搜索（novelty search）结合，以增量方式生成多样样本。该距离度量用于衡量配置间相似性以及样本集多样性，新颖性搜索则通过持续寻找新颖配置来提升样本集多样性。作者在 39 个真实 SPL 上评估，所提方法能为所有 SPL 生成所需数量样本，包括 sharpSAT 状态数计数器无法计数的实例；在样本集多样性上优于或至少不劣于当前最佳采样器。实验表明，在所有测试采样器中，只有本文采样器实现了可扩展的多样性采样。
Real-world software product lines (SPLs) often encompass enormous valid configurations that are impossible to enumerate. To understand properties of the space formed by all valid configurations, a feasible way is to select a small and valid sample set. Even though a number of sampling strategies have been proposed, they either fail to produce diverse samples with respect to the number of selected features (an important property to characterize behaviors of configurations), or achieve diverse sampling but with limited scalability (the handleable configuration space size is limited to 1013). To resolve this dilemma, we propose a scalable diverse sampling strategy, which uses a distance metric in combination with the novelty search algorithm to produce diverse samples in an incremental way. The distance metric is carefully designed to measure similarities between configurations, and further diversity of a sample set. The novelty search incrementally improves diversity of samples through the search for novel configurations. We evaluate our sampling algorithm on 39 real-world SPLs. It is able to generate the required number of samples for all the SPLs, including those which cannot be counted by sharpSAT, a state-of-the-art model counting solver. Moreover, it performs better than or at least competitively to state-of-the-art samplers regarding diversity of the sample set. Experimental results suggest that only the proposed sampler (among all the tested ones) achieves scalable diverse sampling.
@inproceedings{Xiang0ZLLLLY22,
title = {Search-based diverse sampling from real-world software product lines},
author = {Yi Xiang and Han Huang and Yuren Zhou and Sizhe Li and Chuan Luo and Qingwei Lin and Miqing Li and Xiaowei Yang},
booktitle = {ICSE},
year = {2022},
doi = {10.1145/3510003.3510053}
}