基于自适应进化算法的软件产品线抽样方法

Sampling method of software product line based on adaptive evolutionary algorithm

摘要

为了进一步提高样本集的多样性，提出了DDHNSbS算法，其中多样化变异策略（DMS）不仅能保留初始种群的多样性，还能优化传统遗传算子的效果。同时，为弥补新颖性搜索的局限性，提出了多样性检测（DD）以一定概率对特征的赋值进行检验并翻转。此外，利用Halton数列实现概率感知多样化（Halton-PaD），提高初始配置的均匀性。实验在39个公共软件产品线（SPL）上进行，结果表明，与当前性能最优的多样化抽样方法PaD-NSbS算法相比，DDHNSbS在42.1%的小型SPL上求解性能显著更优，在其他SPL上性能相当。

Abstract

In order to further improve the diversity of the sample set， the DDHNSbS algorithm was proposed， in which the Diversity Mutation Strategy（DMS）not only preserves the diversity of the initial population， but also optimizes the effect of traditional genetic operators. Meanwhile， to make up for the limitations of novelty search， diversity detection（DD）was proposed to check and flip the assigned values of features with a certain probability. So as to further diversify the number of features selected in the sample set， probability-aware diversification via the Halton sequence（Halton-PaD）was achieved， and the generated initial configurations' uniformity was developed thanks to Halton-PaD. Experiments were carried out on 39 public SPLs， and the experimental results show that when DDHNSbS algorithm is compared with PaD-NSbS algorithm， DDHNSbS performs significantly better in 42.1% of the small SPLs， and has the same performance on other SPLs.

Graphical abstract

关键词

软件产品线 / 多样化抽样 / 新颖性搜索 / 概率感知多样化 / 进化算法

Key words

software product lines / diverse sampling / novelty search / probability-aware diversification / evolutionary algorithm

0 引 言

软件产品线（Software product line，SPL）^［1］能降低软件成本，提高可重用性^［2］，它根据所选特征及所选特征数量生成多种配置，满足特征间所有约束的配置被称为有效配置。大型真实世界的SPL特征数量庞大，面对软件工程任务（例如例如结合多目标进化算法思想^［3，4］，根据用户所需获得最优配置^［2］、测试SPL^［5，6］等）时，考虑到生成配置的不确定性和有限的资源，枚举有效配置非常困难^［7］，因此需要高效的抽样方法选取样本反映总体。

目前，抽样方法大致分为5种：基于求解器的抽样短时间内通过求解器生成大量样本，但不能保证样本有效性^［8-10］；随机抽样随机选择特征生成样本集^［11-13］；面向覆盖的抽样通过特定的覆盖标准选取样本^［14-16］；均匀抽样在搜索空间中统一采样^{［17，18］}；多样性抽样^［19-26］在SPL抽样中占有优势，它不仅保证导出性能预测模型时尽可能保留不同行为的配置^［19］，还可以替代覆盖抽样^［20］。目前，已有多种多样性抽样方法被提出并被投入实际应用。DDbS（Diversified distance-based sampling）算法^［19］根据所选特征数量选取样本，它表明该数量越多样化，样本集就越有代表性。多目标SPL配置问题^［21-24］也将所选特征数量作为优化目标之一，因此提高样本有关该数量的多样性至关重要。NSbS（Novelty search-based sampling）算法^［25］在此基础上提出行为空间的概念，结合新颖性搜索在行为空间和配置空间进行探索，生成具有多样性的样本集，同时提出分散值作为实验指标衡量算法性能。PaD-NSbS（Probability‑aware diversification-NSbS）算法^［26］是目前最新的方法，它根据PaD的特点改进了SAT（Satisfiability）求解器，在生成初始种群的过程中尽可能减少取消赋值的变量数量，从而在行为空间达到更好的覆盖。

然而，最新的PaD-NSbS算法仍有不足，为了保留该算法中初始种群的多样性并进行有效搜索，提高样本集的多样性，本文提出DDHNSbS算法，主要贡献如下：

（1）多样化变异策略（Diversity mutation strategy，DMS）保留新颖性分数高的个体并以随机生成的新配置替换分数低的个体，弥补了原算法过早收敛的不足；

（2）多样性检测（Diversity detection，DD）以一定概率进行并防止父代与子代同时选择或取消选择同一特征，避免原算法局部搜索不足，出现个体早熟的情况；

（3）以Halton序列^［27］为基础的概率感知多样性（Halton-PaD），其生成的初始种群均匀性得到进一步提高；

（4）本文选择了不同的遗传算子进行实验，判断出最高效的组合。

1 预备知识

本节将介绍从配置空间采样所需的基础知识，包括从配置空间采样的方法以及行为空间的基本概念。在多样性抽样中，通过配置选择特征的数量描述配置的行为，该数量越多样化，性能预测的准确性就越高^［25］。为了清晰表述各配置的行为并计算抽样方法的性能指标，文献［25］提出了行为空间的概念，并说明如何将配置空间映射到行为空间。

1.1　从配置空间采样

与其他问题相同，SPL在特征之间存在约束，为直观表述约束和特征的关系，需要对SPL进行建模^［28］。特征模型（Feature model，FM）^［29］可以清晰地表示出SPL中的特征及其约束等信息，该模型采用树状结构，其具体定义如下。

定义1 FM用二元组〈F,C〉表示^［25］，其中F=\left\{f_{\mathrm{1}},f_{\mathrm{2}},...,f_n\right\}为n个特征的集合，f_i为SPL的第i个特征，C为各特征间约束关系的集合。

定义2 配置c由集合\left\{\pm f_{\mathrm{1}},\pm f_{\mathrm{2}},...,\pm f_n\right\}表示，其中+f_i为选择FM中的第i个特征，-f_i为取消选择的第i个特征。若用二进制串表示配置c，则选择某特征，该特征位取值为1，否则取0。其中，满足所有约束的配置被称为有效配置，否则被称为无效配置。

定义3 配置空间Ψ是所有有效配置的集合，它的基数由|Ψ|表示。

为完成特定的任务目标，通常需要对配置空间中的有效配置进行探索。然而大型的软件产品线的特征数十分庞大，导致|Ψ|也随之增长。在枚举配置空间并不现实的情况下，需要选取配置空间的子集作为样本集，通过样本集对配置空间进行探索。

定义4 样本集是一个集合S=\left\{s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_n\right\}，其中s_i为一个配置空间中的第i个有效配置，它是样本集的样本之一。

1.2　行为空间

如前所述，配置的行为可以通过其所选的特征数量进行表述，所选特征数量的多样性将提高最终样本集的代表性。将配置空间Ψ映射到行为空间之后，算法会对均匀覆盖的配置抽样，使样本集多样性提高。

定义5 若以每个有效配置所选择的特征数量为基准表示配置的行为，则配置空间Ψ会被映射到由正整数组成的空间，即行为空间^{［19，25］}。行为空间用B表示，它的基数由|B|表示。

强制特征是指有效配置中一定选择的特征，而无效特征是有效配置中一定取消选择的特征。假设共有n个特征，则B集合中的最大值和最小值可以由强制特征的数量\left|\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\right|以及无效特征的数量\left|\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\right|确定。因为每个有效配置必须选择强制特征，但不能选择无效特征，所以B中的最小值\mathrm{m}\mathrm{i}\mathrm{n}(B)\ge \left|\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\right|，最大值\mathrm{m}\mathrm{a}\mathrm{x}(B)\len-\left|\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\right|。显然，B中最多有n-\left|\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\right|-\left|\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\right|+\mathrm{1}个整数，可以理解为配置空间Ψ被分为|B|个子空间，算法可以对这些子空间中不同分布的配置进行抽样。|B|远小于|Ψ|，因此行为空间更好理解。然而由于配置的数量繁多，很难准确地了解行为空间，可以通过集合B'近似表示行为空间B。B\mathrm{\text{'}}=\left\{\left|\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\right|,\left|\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\right|+\mathrm{1},...,n-\left|\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\right|\right\}，它包括\left|\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\right|至n-\left|\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\right|间的全部整数，考虑到B'中的整数可能无法与Ψ中有效配置选择的特征数量形成映射，因此B是B'的子集。B'还可以用来计算性能指标。

2 DDHNSbS算法及其优化策略

本节将介绍本文提出的DDHNSbS算法及其3种优化策略，分别是DMS、DD以及Halton-PaD。

2.1　DDHNSbS算法

DDHNSbS包括3个优化策略，它的算法流程如算法1所示。根据输入的由FM生成的命题公式以及用户所需的样本集大小，算法不断在配置空间中探索新的个体，从而提高最终样本集的多样性，在达到终止条件后将最终的样本集存储在档案A中并输出。

算法1 DDHNSbS算法

输入：命题公式\mathrm{\phi }，样本大小N；

输出：档案A。

① A←InitializeArchivewithHalton（N）；/* \mathrm{\phi }通过Halton-PaD生成初始种群{\mathrm{S}}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}并存储*/

② D←InitializeDistanceMatrix（N+1）；/* 初始化距离矩阵*/

③ calculate the novelty score \mathrm{\rho }\left(\mathrm{x}\right) for each \mathrm{x}\in \mathrm{A}；

④ while runtime\lemaxtime && gap\le10

⑤ \left\{{\mathrm{c}}_{\mathrm{1}},{\mathrm{c}}_{\mathrm{2}}\right\}←S_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}} after traditional genetic operators with DMS；/* 用DMS结合遗传算子生成新子代*/

⑥ for \mathrm{i}\in｛1， 2｝

⑦ if p<\mathrm{\theta }

⑧ DD；/* 进行多样性检测*/

⑨ end if

⑩ end for

⑪ apply ProbSAT solver to repair {\mathrm{c}}_{\mathrm{1}}\mathrm{\text{'}},{\mathrm{c}}_{\mathrm{2}}\mathrm{\text{'}}；/* ProbSAT求解器修复子代{\mathrm{c}}_{\mathrm{1}}\mathrm{\text{'}},{\mathrm{c}}_{\mathrm{2}}\mathrm{\text{'}}*/

⑫ updateArchive（A）；/* 新颖性搜索更新样本集*/

⑬ end while

⑭ return A

算法先通过随机抽样以及rSAT4J求解器生成初始种群，再进行后续操作。有效的样本集需要均匀而广泛地抽取，PaD-NSbS算法中使用PaD生成样本，目的是使特征数量尽可能在［0， n］之间分布；而Halton-PaD不仅可以满足该条件，还能保证取值更加均匀。因此，DDHNSbS算法中，首先按照所给样本数量以及所给命题公式\phi，通过Halton-PaD以及rSAT4J求解器随机生成N个配置，作为初始种群S_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}并将其存储在档案A中（第1行）。针对档案A中的各有效配置，算法运用距离公式计算任意2个不同配置之间的距离并存入距离矩阵（第2行）。其次，算法依次求出S_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}中各个体的新颖性分数，为新颖性搜索做准备（第3行）。进入探索过程后，PaD-NSbS以及NSbS算法直接使用传统遗传算子执行进化算法；在迭代期间，以新颖性分数为标准，算法保留分数高的个体并淘汰分数低的个体，然而这样会减弱PaD的效果，影响种群的多样性。为同时保留PaD和遗传算子的效果，DDHNSbS算法使用传统遗传算子与DMS相结合的方式产生新的子代（第5行）。产生新的子代后，为了在现有算法的基础上进一步提高样本的多样性，新的子代需要进行DD，而是否进行取决于概率\theta，若随机产生的概率p小于\theta，则需进行（第8行），并得到多样化后的子代；否则不对子代进行修改，用c_{\mathrm{1}}\mathrm{\text{'}}\mathrm{、}{c}_{\mathrm{2}}\mathrm{\text{'}}表示此时的子代。因为c_{\mathrm{1}}\mathrm{\text{'}}\mathrm{、}{c}_{\mathrm{2}}\mathrm{\text{'}}不能保证其有效性，所以算法使用ProbSAT求解器对无效解进行修复（第9行）。最后，根据新颖性分数更新档案（第10行），直到达到终止条件，返回档案A作为多样化的样本集输出。

算法中计算距离的公式分为2部分，分别在行为空间和配置空间衡量配置的相似性，从而保证所探索的个体不仅在行为空间具有独特性，在配置空间也能尽可能保持配置间的不同。新颖性分数的计算依赖于各配置间的距离，配置相距越远，说明配置分布越稀疏。处于稀疏区域的配置有助于提高样本集的多样性，因此该类型的个体会被赋予较高的新颖性分数，在新颖性搜索时就会更趋于探索分数高的个体^［25］。

算法DDHNSbS中的优化策略DMS、DD以及Halton-PaD将在后续介绍。

2.2　DMS方法

虽然原算法中交叉、变异等传统的遗传算子可以对样本集进行广泛搜索从而保证其多样性，但通过概率感知生成的初始解的随机效果会全部被遗传算子取代，因此初始种群的多样性受到一定影响。为了同时保留两者的效果并且扩大搜索范围，本文提出了DMS方法。

DMS的具体流程如下：当从父代选择出2个个体后，同时使用DMS以及传统的遗传算子生成新的子代。DMS首先以种群的新颖性分数平均值作为标准值，在搜索过程中，新颖性分数低于标准值的个体将被随机生成的新个体取代；相对地，新颖性分数高于标准值的个体会进行遗传操作并进入下一代。基于此，种群不仅能淘汰适应度低的个体，还能确保种群的多样性。

算法2 DMS方法

输入：被选择的父代{\mathrm{p}}_{\mathrm{1}},{\mathrm{p}}_{\mathrm{2}}；

输出：新生成的子代{\mathrm{c}}_{\mathrm{1}},{\mathrm{c}}_{\mathrm{2}}。

① {\mathrm{\rho }}_{\mathrm{b}\mathrm{e}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}\leftarrow \mathrm{m}\mathrm{a}\mathrm{x}\left({\mathrm{\rho }}_{\mathrm{1}},{\mathrm{\rho }}_{\mathrm{2}}\right)；/* 确定被选择父代中较高的新颖性分数*/

② avg_score←find the average novelty score of all samples；

③ if

④ \left\{{\mathrm{c}}_{\mathrm{1}},{\mathrm{c}}_{\mathrm{2}}\right\}←randomly generated solutions；

⑤ else

⑥ \left\{{\mathrm{c}}_{\mathrm{1}},{\mathrm{c}}_{\mathrm{2}}\right\}←{\mathrm{p}}_{\mathrm{1}},{\mathrm{p}}_{\mathrm{2}} after crossover；

⑦ for \mathrm{i}\in｛1， 2｝

⑧ {\mathrm{c}}_{\mathrm{i}}←{\mathrm{c}}_{\mathrm{i}} after mutation；

⑨ end for

⑩ end if

{\rho }_{\mathrm{1}}\mathrm{、}{\rho }_{\mathrm{2}}分别是被选择的2个父代p_{\mathrm{1}}\mathrm{、}{p}_{\mathrm{2}}的新颖性分数，DMS先比较2个个体的新颖性分数，选择较高的新颖性分数，即{\rho }_{\mathrm{b}\mathrm{e}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}（第1行）；再结合标准值avg_score进行判断（第3行），如果父代的新颖性分数{\rho }_{\mathrm{b}\mathrm{e}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}低于平均新颖性分数avg_score，即父代的新颖性分数均低于平均分数，则被选择的2个父代的适应度较低，因此放弃父代，调用Halton-PaD随机生成新的解，从而扩大搜索范围（第4行），并且跳过后续的遗传操作，以保证其多样化效果；否则，将继续进行交叉、变异等操作（第6~8行）生成子代，保留适应度较高的个体。最终算法返回新的解，继续新颖性搜索。

2.3　DD方法

原算法中每次只生成2个子代，然后以新颖性分数作为标准，筛去分数较差的配置。但这种方法存在一定缺陷，在局部搜索中可能存在搜索不足的情况，从而陷入局部最优，在规定的时间内难以对配置空间进行有效探索，导致样本集的多样性受到影响。为此，本文提出了DD方法，它根据概率选择性进行，进一步提高种群的多样性。

算法3 DD方法

输入：新生成的子代{\mathrm{c}}_{\mathrm{1}},{\mathrm{c}}_{\mathrm{2}}；

输出：新生成的多样化子代{\mathrm{c}}_{\mathrm{d}\mathrm{1}}^{\text{'}},{\mathrm{c}}_{\mathrm{d}\mathrm{2}}^{\text{'}}．

① for each features in SPL

② {\mathrm{f}}_{\mathrm{f}\mathrm{i}\mathrm{x}}\leftarrowfind the first feature with fixed value in all samples；

③ judge whether {\mathrm{f}}_{\mathrm{f}\mathrm{i}\mathrm{x}} is allowed to flip；

④ if {\mathrm{f}}_{\mathrm{f}\mathrm{i}\mathrm{x}} is allowed to flip；

⑤ \left\{{\mathrm{c}}_{\mathrm{d}\mathrm{1}}^{\mathrm{\text{'}}},{\mathrm{c}}_{\mathrm{d}\mathrm{2}}^{\mathrm{\text{'}}}\right\}←{\mathrm{c}}_{\mathrm{1}},{\mathrm{c}}_{\mathrm{2}} with flipped {\mathrm{f}}_{\mathrm{f}\mathrm{i}\mathrm{x}}；

⑥ break；

⑦ end if

⑧ end for

DD首先在档案的各配置中和经DMS后得到的2个子代中进行比较，若某个特征f_{\mathrm{f}\mathrm{i}\mathrm{x}}赋值始终相同，且其并非强制特征或无效特征，则将子代中该特征f_{\mathrm{f}\mathrm{i}\mathrm{x}}赋值反转（第5行）。DD是否进行取决于概率\theta，\theta的取值随着解决的SPL不同而变化。为了更直观地阐述，给出DD实例，见图1。

图1中的二进制串表示档案中的各个配置，对比发现第2个特征的取值在各配置中取值均为“0”；假设该特征不是强制特征或无效特征，则算法此时将子代的该位翻转并赋值为“1”。通过这种方法得到的样本集会更多样化。

2.4　Halton-PaD方法

抽样时需要样本集均匀地覆盖行为空间，而最终的样本集是在初始种群的基础上进行新颖性搜索得到，因此初始种群的选择尤为关键，即需要初始种群分布均匀，从而尽可能获取更多有关行为空间分布的信息^［30］。Halton序列是标准的低差异度序列^［27］，它可以生成无穷个样本，并保证这些样本分布均匀^［31］。Halton-PaD以Halton序列为基础实现，它根据作为概率的Halton序列值决定是否选择某特征，和PaD都能保证概率在［0， 1］间取值。

对于从Halton序列得到的概率p_{\mathrm{h}}，Halton-PaD生成的初始种群中，所选特征数量的数学期望为{\displaystyle \sum _{i=\mathrm{1}}^n}[p_{\mathrm{h}}\times \mathrm{1}+(\mathrm{1}-p_{\mathrm{h}})\times \mathrm{0}]，则所选特征数量的平均值为p_{\mathrm{h}}n，故而所选特征数量的范围是[\mathrm{0}\times n,\mathrm{1}\times n]，可以保证初始种群在行为空间均匀分布。

因此，HaltonPaD不仅能达到PaD的效果，还可以提高初始种群的均匀性。

3 实验设置

3.1　所用的FM

实验共选用39个FM作为数据集，FM的选取基于先前的研究^{［5，20，31-34］}，除了SPLOT-Generated-FM-5 000为人工生成^［20］，其余都可以代表真实世界的SPL或高度可配置系统。FM中特征数量、子句数量不等，可以根据特征数量将其分为3类：小型的FM，即特征数量<1 000；中型的FM，即特征数量在1 000~6 000；大型的FM，即特征数量>6 000。

表1具体给出了各FM的信息，其中|F|表示FM中的特征数量，|C|表示特征间约束数量，|core|和|dead|分别表示强制特征与无效特征的数量。将39个FM按表中顺序分别编号为1~39，其余表格使用编号分别对应相应的FM。

3.2　绩效指标

Xiang等^［25］提出了衡量样本集多样性的指标分散值（Spread），该值用于衡量样本集在行为空间的分布是否均匀，表示为：

\mathrm{S}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}\left(S,B\mathrm{\text{'}}\right)=\frac{\mathrm{1}}{\left|B\mathrm{\text{'}}\right|}{\displaystyle \sum _{i=\mathrm{1}}^{\left|B\mathrm{\text{'}}\right|}}{d}_{\mathrm{m}\mathrm{i}\mathrm{n}}\left(b_i\mathrm{\text{'}},S\right)（1）

式中：B\mathrm{\text{'}}=\left\{\left|\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\right|,\left|\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\right|+\mathrm{1},\cdots ,n-\left|\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\right|\right\}，如1.2节所述，它可以近似为行为空间；b_i\mathrm{\text{'}}为B\mathrm{\text{'}}中的第i个整数；S=\left\{s_{\mathrm{1}},s_{\mathrm{2}},\cdots ,s_N\right\}为样本集；d_{\mathrm{m}\mathrm{i}\mathrm{n}}\left(b_i\mathrm{\text{'}},S\right)为b_i\mathrm{\text{'}}和S的最小距离。

d_{\mathrm{m}\mathrm{i}\mathrm{n}}(b_i\mathrm{\text{'}},S)=\stackrel{N}{\underset{j=\mathrm{1}}{\mathrm{m}\mathrm{i}\mathrm{n}}}\left|b_i\mathrm{\text{'}}-T(s_j)\right|（2）

式中：T(s_j)为S中有效配置s_j所选择的特征数量。

通过式（2）可以得到结论：分散值越小的配置所在的区域就越稀疏，而新颖性搜索会更倾向于稀疏区域的配置，对该区域的探索会促进种群的多样性，因此分散值越小的样本集往往在行为空间具有更好的覆盖。

为了更好比较不同的采样器，Xiang等^［26］还提出了关于分散值的改善率（Improvement rate， IR）。假设采样器s_{\mathrm{1}}\mathrm{、}{s}_{\mathrm{2}}所选择的样本集分别是A_{\mathrm{1}}\mathrm{、}{A}_{\mathrm{2}}，则IR表达式为：

\mathrm{I}\mathrm{R}(s_{\mathrm{1}},s_{\mathrm{2}})=\frac{\mathrm{S}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}(A_{\mathrm{1}},B)-\mathrm{S}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}(A_{\mathrm{2}},B)}{\mathrm{S}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}(A_{\mathrm{1}},B)}\times \mathrm{100}\mathrm{\%}（3）

如果采样器s_{\mathrm{1}}的性能优于s_{\mathrm{2}}，则，即样本集A_{\mathrm{1}}比A_{\mathrm{2}}具有更好的行为空间覆盖，因此是更优的样本集。

3.3　实验细节

为了消除随机性的偏差，参考文献［25，26］的研究成果，所有采样器都将在各FM上独立运行30次；在每次独立运行中，若采样器迭代超过10次，且在此期间，其样本集的新颖性分数变化率不超过0.1%，则说明采样器已经相对稳定，此时停止运行，返回样本集。如果采样时间超过1h，算法也会终止；同时，所有采样器的种群大小设置为100，交叉概率设置为1.0，变异概率设置为0.1。本文后续将用性能指标衡量各样本集的优劣，以达到判定采样器性能的目的。DDHNSbS采样器与NSbS采样器相似，也同时运用2种求解器。其中，将ProbSAT求解器的参数max_flips赋值为30 000，采样器返回的样本集中有效配置数设置为100。

所有实验都在安装了ubuntuLtS的台式机上进行，硬件配置如下：Intel（R）Core（TM）i5-3470 CPU@3.20 GHz和7.7 GB RAM。实验涉及的所有算法都由java实现。

4 实验结果及分析

为了判断改进后是否显著提高采样器的性能，对每个FM都执行显著性水平为0.05的MannWhitney U测试^［35］，用“•”“‡”和“◦”分别表示显著优于、近似相同、显著差于。为评估DMS、DD以及Halton-PaD对算法性能的贡献，针对不同优化策略分别进行实验，通过各实验结果比较分析优化策略的效果。

4.1　DDHNSbS与NSbS、PaD-NSbS进行比较

在本小节中，将DDHNSbS采样器与NSbS采样器和PaD-NSbS采样器进行比较，以分散值作为判定标准，将最优结果用粗体表示，其余表格保持一致。实验结果如表2所示，表中用DDHN代表DDHNSbS，PaDN代表PaD-NSbS。

由表2可知，在所有FM中，DDHNSbS的性能要显著优于或近似于NSbS、PaD-NSbS。其中，在中型的FM中，DDHNSbS在85.7%的FM上对比NSbS有显著提高，而在小型和大型的FM中，DDHNSbS也能保证性能与NSbS相当；对比最新的算法PaD-NSbS，DDHNSbS在42.1%的小型FM中表现显著优于PaD-NSbS，在中型的FM中也有显著改进的例子，如freebsd-icse11。DDHNSbS在所有FM中，能保证显著优于或近似于PaD-NSbS。图2为算法分散值最佳的数量，可以直观地表示实验结果，其中横坐标表示3种算法，纵坐标表示针对每个FM，某算法计算得到的分散值最佳的数量，包括并列最佳的情况。从图2可得，在39个FM中，DDHNSbS计算得到的分散值为最佳的数量超过NSbS以及PaD-NSbS，它在32个FM中表现最佳，PaD-NSbS在14个FM中表现最佳。

为比较DDHNSbS与最新采样器PaD-NSbS的性能，图3根据MannWhitney U测试结果，总结了分散值显著提高的FM中，各规模FM所占的百分比。如图3所示，在分散值显著提高的FM中，有72.8%的FM为小型，27.2%为中型，DDHNSbS与PaD-NSbS在大型FM上的性能相当，这说明DDHNSbS在小型和中型FM中更具优势。根据实验结果可得，当FM的特征数量较少时，DDHNSbS通过Halton-PaD对比PaD生成的初始种群会更均匀地分布在行为空间，DMS在此基础上保留新颖性分数高的个体进行遗传操作生成子代，使最优解更为集中，同时淘汰新颖性分数低的个体，并随机生成新个体提高多样性；DD根据特定的概率检测并翻转特征值，避免局部最优，使生成的样本集均匀广泛地覆盖行为空间，从而保证其改进的显著性。然而随着FM中特征数量的增加，PaD-NSbS所选取配置的多样性也随之提高^［26］，这就导致DDHNSbS的优势不再明显，DDHNSbS和PaD-NSbS在大型FM中性能相当。

为了分析DDHNSbS性能好的原因，本文选择小型FM作为具体的例子生成配置。图4为各采样器在WebPortal上生成的配置所选择特征的数量。从选择特征的数量增加趋势可以看出，DDHNSbS的增加趋势更加规律，因此它所选取的配置在行为空间中分布更为均匀。

为进一步详细说明，需要观察各采样器在WebPortal上选取的连续配置增量，见图5。其中，只有DDHNSbS的增量始终保持为1，PaD-NSbS为1或2，NSbS的表现则相对较差，它的增量除了1和2还存在4。除了增量的稳定性，DDHNSbS和PaD-NSbS还能保证选取大小近似的子集；相比之下，NSbS选取平均分区的能力弱于前两者。

上述结果表明，DDHNSbS采样时能够在行为空间中选取分布均匀且广泛的配置集。

4.2　DMS的影响

将不采用DMS的DDHNSbS采样器称为M1，从而对比DDHNSbS采样器和M1，2种算法在所有FM上执行显著性水平为0.05的MannWhitney U测试，结果如下所示：DDHNSbS对比M1分别在24、15、0个FM上性能近似相同、显著更优、显著更差，可见对比M1，使用DMS策略的DDHNSbS在15个FM上有显著提高；而在近似相同的24个FM中，DDHNSbS有22个分散值小于或等于M1。从FM的特征数量分析，在71.4%的中型FM中，DDHNSbS比M1有显著改进，在小型的FM中也有显著改进的例子。总之，M1算法的性能明显差于或近似于DDHNSbS，因此DMS策略能提高算法的多样性，且如果FM为中型或小型，改进效果会更好。

为了进一步探究DMS策略对算法的影响，本文以数据集中的2个FM为例，并分别绘制了经过2种采样器抽样后得到的样本集在行为空间的分布，结果如图6所示。通过对比可知，DDHNSbS在边界处也能进行采样，因此在行为空间的分布很均匀；而M1没有DMS的辅助，在边界处生成的配置很少，因此在边界处分布较为稀疏。

这种结果可以预见，因为在M1算法进行局部搜索时，仅对某个子代进行处理，会局限搜索范围，导致算法陷入局部最优的状态。同时，当父代产生新的子代时可能不会产生有利于种群多样化的解，通过使用DMS可以避免该问题，该策略保护适应度高的个体进行遗传操作，淘汰适应度低的个体，并随机生成新个体，从而扩大算法的探索空间，进一步提高多样性。由此可见，DMS对于算法的改进有效。

4.3　DD的影响

用M2表示不采用DD的DDHNSbS采样器，并将其与DDHNSbS采样器进行对比。通过实验比较DDHNSbS与M2可得，DD在39个FM上对多样性的提高并不显著，但DDHNSbS仍能获得较好的结果，具体结果如下：DDHNSbS所得分散值大于、等于、小于M2的数量分别为8、7、24，可见在79.5%的FM中，DDHNSbS对比M2都能取得较好或相等的结果。这说明在执行进化算法时存在特征赋值不变的情况，DD会找到未被翻转的变量并重新赋值，从而在一定程度上促使种群多样化，但并不足以显著提高算法性能。

4.4　Halton-PaD的影响

将采用PaD的DDHNSbS求解器命名为DDHNSbS_P，并将其与DDHNSbS进行对比，MannWhitney U测试结果如下：DDHNSbS对比DDHNSbS_P分别在35、4、0个FM上性能近似相同、显著更优、显著更差。具体地说，DDHNSbS在18个FM上表现较好，其中在4个FM上显著优于DDHNSbS_P；在8个FM上与DDHNSbS_P的分散值相等，且均为小型或中型的FM，不存在显著差于DDHNSbS_P的情况。通过2种算法的对比，Halton-PaD对行为空间的覆盖比PaD更加完整；但在面对特征数量庞大的大型FM时，Halton-PaD与PaD对初始种群的采样都趋向于均匀覆盖整个行为空间。因此，在大型FM中，DDHNSbS与DDHNSbS_P性能相当。总体来看，使用Halton-PaD策略提高初始种群的平均性对算法性能的改进有效。

4.5　不同遗传算子的影响

通过比较不同交叉算子以及不同选择算子，以判断出最高效的遗传算子组合，并应用到DDHNSbS中。将采用统一交叉遗传算子的DDHNSbS采样器称为M3，采用随机选择遗传算子的DDHNSbS采样器称为M4，以便于后续的对比。

首先从不同的交叉算子开始实验，即UC与单点交叉（Singlepoint crossover，SPC）之间进行比较。UC是指子代按位交错选择2个父代的值生成新的子代；SPC则需要确定交叉点，再将第1个父代的首位至交叉点位置的值与第2个子代相应位置的值交换，从而获得新子代。交叉算子的比较结果见表6。

由表6可知，UC在39个FM上的表现要显著优于或近似于SPC。图7为DDHNSbS对比M3的改善率，可以直观发现，在抽样中型的FM时，UC的性能普遍显著优于SPC。经计算可得，IR的平均值为-3.43%，DDHNSbS采样器相比M3，多样性有所提高，因此选择UC作为算法的遗传算子。DDHNSbS对比M4的改善率见图8。

接下来比较不同的选择算子对算法的影响，本文采用二进制锦标赛选择（Binary tournament selection，BTS）和随机选择（Random selection， RS）。其中，BTS在种群中选取指定数量的个体进行竞争，并捕获最优个体；RS则在种群中随机选择2个个体作为父代。选择算子的比较结果见表7。

由表7可得，2种选择算子在小型和大型FM中的表现几乎一致，而BTS在中型FM中的表现要明显优于RS，该结论在IR数值中也有所体现。通过图8可得，在小型与大型的FM中，IR的数值基本接近于0；在中型FM中，IR的绝对值较大。IR的平均值为-2.98%，说明DDHNSbS采样器比M4性能更优，因此BTS的表现要优于或近似于RS，本文在算法中倾向于选择BTS作为选择算子。

从上述实验和分析可得，最高效的遗传算子组合为UC与BTS。

5 结束语

本文提出了一种自适应多样性采样算法，即DDHNSbS算法。该算法包括3个策略，分别是DMS、DD以及Halton-PaD。从实验结果可得，DDHNSbS在部分FM中的表现显著优于NSbS以及最新算法PaD-NSbS，在其他FM中则性能相当。结合实验数据，在85.7%的中型FM中，DDHNSbS的表现显著优于NSbS；在42.1%的小型FM中，DDHNSbS的表现显著优于PaD-NSbS。对于各优化策略，本文设置了消融实验，分别探究其对整体算法性能的影响。DMS使DDHNSbS的性能在71.4%的中型FM和部分小型FM中显著提高；在79.5%的FM中，运用DD的DDHNSbS表现较好或与M2相同；运用Halton-PaD的算法与运用PaD的算法对比时，有4个FM显著优于后者，不存在显著差于的情况。因此，从实验可得，各策略有效。此外，本文对不同遗传算子进行比较，运用UC的DDHNSbS比运用SPC的DDHNSbS性能更好，IR的平均值为-3.43%；运用BTS的DDHNSbS比运用RS的性能更好，IR的平均值为-2.98%。因此DDHNSbS算法选择UC以及BTS作为遗传算子。

在未来的工作中，除了将分散值作为实验指标，还可以考虑其他度量方式，从不同角度衡量样本集的多样性。此外，可以考虑将该抽样工具投入实际应用中，完成现实目标，如通过样本集中配置的性能预测其余配置的性能。同时，本文所提出的3个优化策略也适用于其他SPL的任务，如SPL测试等。由于DDHNSbS算法只在小型和中型FM中对比PaD-NSbS更有优势，后续将针对大型FM的多样化抽样进行改进，使DDHNSbS算法的优势得以保持。最后，可以尝试优化进化算法，从而更好地结合DDHNSbS进行抽样，如结合卡尔曼滤波预测模型的进化算法。

参考文献

[1] Clements P, Northrop L. Software Product Lines[M]. Boston: Addison-Wesley, 2002.

[2] Hou Y M, Ouyang D T, Tian X L, et al. Evolutionary many-objective satisfiability solver for configuring software product lines[J]. Applied Intelligence: The International Journal of Artificial Intelligence, Neural Networks, and Complex Problem-Solving Technologies, 2022, 52(9): 10650-10673.

[3] 孙宝凤, 任欣欣, 郑再思, 等. 考虑工人负荷的多目标流水车间优化调度[J]. 吉林大学学报: 工学版, 2021, 51(3): 900-909.

[4] Sun Bao-feng, Ren Xin-xin, Zheng Zai-si, et al. Multi⁃objective flow shop optimal scheduling considering worker's load[J]. Journal of Jilin University (Engineering and Technology Edition), 2021, 51(3): 900-909.

[5] 马永杰, 陈敏. 基于卡尔曼滤波预测策略的动态多目标优化算法[J]. 吉林大学学报: 工学版, 2022, 52(6): 1442-1458.

[6] Ma Yong-jie, Chen Min. Dynamic multi⁃objective optimization algorithm based on Kalman filter prediction strategy [J]. Journal of Jilin University (Engineering and Technology Edition), 2022, 52(6): 1442-1458.

[7] Pett T, Krieter S, Thüm T, et al. AutoSMP: an evaluation platform for sampling algorithms[C]∥Proceedings of the 25th ACM International Systems and Software Product Line Conference-Volume B, New York, NY, USA, 2021: 41-44.

[8] Devroey X, Perrouin G, Legay A, et al. Search-based similarity-driven behavioural SPL testing[C]∥Proceedings of the 10th International Workshop on Variability Modelling of Software-Intensive Systems, Salvador, Brazil, 2016: 89-96.

[9] Oh J, Gazzillo P, Batory D, et al. Scalable uniform sampling for real-world software product lines[R]. Austin: The Univ Texas at Austin, 2020.

[10] Dutra R, Laeufer K, Bachrach J, et al. Efficient sampling of SAT solutions for testing[C]∥Proceedings of the 40th International Conference on Software Engineering, Gothenburg, Sweden, 2018: 549-559.

[11] Plazar Q, Acher M, Perrouin G, et al. Uniform sampling of sat solutions for configurable systems: Are we there yet?[C]∥Proceedings of the 2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST), Xi'an, China, 2019: 240-251.

[12] Heradio R, Fernandez-Amoros D, Galindo J A, et al. Uniform and scalable SAT-sampling for configurable systems[C]∥Proceedings of the 24th ACM Conference on Systems and Software Product Line, Montreal, Quebec, Canada, 2020: 1-11.

[13] Liebig J, Von Rhein A, Kästner C, et al. Scalable analysis of variable software[C]∥Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, Saint Petersburg, Russia, 2013: 81-91.

[14] Medeiros F, Kästner C, Ribeiro M, et al. A comparison of 10 sampling algorithms for configurable systems[C]∥Proceedings of the 38th International Conference on Software Engineering, Austin, Texas, USA, 2016: 643-654.

[15] Melo J, Flesborg E, Brabrand C, et al. A quantitative analysis of variability warnings in linux[C]∥Proceedings of the 10th International Workshop on Variability Modelling of Software-intensive Systems, Salvador, Brazil, 2016: 3-8.

[16] Cohen M B, Dwyer M B, Shi J. Interaction testing of highly-configurable systems in the presence of constraints[C]∥Proceedings of the 2007 International Symposium on Software Testing and Analysis, London, England, United Kingdom, 2007: 129-139.

[17] Krieter S, Thüm T, Schulze S, et al. YASA: yet another sampling algorithm[C]∥Proceedings of the 14th International Working Conference on Variability Modelling of Software-Intensive Systems, Magdeburg, Germany, 2020: 1-10.

[18] Garvin B J, Cohen M B, Dwyer M B. Evaluating improvements to a meta-heuristic search for constrained interaction testing[J]. Empirical Software Engineering, 2011, 16(1): 61-102.

[19] Chakraborty S, Fremont D J, Meel K S, et al. On parallel scalable uniform SAT witness generation[C]∥Proceedings of the 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems, London, UK, 2015: 304-319.

[20] Ermon S, Gomes C P, Selman B. Uniform solution sampling using a constraint solver as an oracle[J/OL]. [2024-03-15].

[21] Kaltenecker C, Grebhahn A, Siegmund N, et al. Distance-based sampling of software configuration spaces[C]∥Proceedings of the 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), Montreal, Quebec, Canada, 2019: 1084-1094.

[22] Henard C, Papadakis M, Perrouin G, et al. Looking for novelty in search-based software combinatorial explosion: using similarity to generate and prioritize t-wise test configurations for software product lines[J]. IEEE Transactions on Software Engineering, 2014, 40(7): 650-670.

[23] Henard C, Papadakis M, Harman M, et al. Combining multi-objective search and constraint solving for configuring large software product lines[C]∥2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, Firenze, Italy, 2015: 517-528.

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

[25] Sayyad A S, Ingram J, Menzies T, et al. Scalable product line configuration: a straw to break the camel's back[C]∥2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE), Palo Alto, USA, 2013: 465-474.

[26] Xiang Y, Zhou Y R, Zheng Z B, et al. Configuring software product lines by combining many-objective optimization and SAT solvers[J]. ACM Transactions on Software Engineering and Methodology (TOSEM), 2018, 26(4): 1-46.

[27] Xiang Y, Huang H, Zhou Y R, et al. Search-based diverse sampling from real-world software product lines[C]∥Proc of the 44th International Conference on Software Engineering, Pittsburgh, USA, 2022: 1945-1957.

[28] Xiang Y, Yang X W, Huang H, et al. Sampling configurations from software product lines via probability-aware diversification and SAT solving[J]. Automated Software Engineering, 2022, 29(2): 1-45.

[29] 黄美发, 景晖, 钟艳如, 等. 基于拟随机序列的三维模型表面采样方法[J]. 计算机工程, 2008, 34(14): 263-265.

[30] Huang Mei-fa, Jing Hui, Zhong Yan-ru, et al. Sampling method on 3D model surface based on quasi random sequence[J]. Computer Engineering, 2008, 34(14): 263-265.

[31] 周慧思, 欧阳丹彤, 田新亮, 等. 基于模型诊断的一种新编码方法[J]. 计算机研究与发展, 2023, 60(1): 95-102.

[32] Zhou Hui-si, Ouyang Dan-tong, Tian Xin-liang, et al. A novel encoding for model-based diagnosis[J]. Journal of Computer Research and Development, 2023, 60(1): 95-102.

[33] Kang K C, Cohen S G, Hess J A, et al. Feature-oriented domain analysis (FODA) feasibility study[R]. Pittsburgh: Carnegie Mellon University, 1990.

[34] Maaranen H, Miettinen K, Mäkelä M M. Quasi-random initial population for genetic algorithms[J]. Computers & Mathematics with Applications, 2004, 47(12): 1885-1895.

[35] Keller A. Quasi-Monte Carlo image synthesis in a nutshell[C]∥Monte Carlo and Quasi-Monte Carlo Methods 2012, Sydney, Australia, 2013: 213-249.

[36] Luo C, Sun B Q, Qiao B, et al. LS-sampling: an effective local search based sampling approach for achieving high t-wise coverage[C]∥Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Athens, Greece, 2021: 1081-1092.

[37] Baranov E, Legay A, Meel K S. Baital: an adaptive weighted sampling approach for improved t-wise coverage[J/OL]. [2024-03-15].

[38] Xiang Y, Huang H, Li M Q, et al. Looking for novelty in search-based software product line testing[J]. IEEE Transactions on Software Engineering, 2021, 48(7): 2317-2338.

[39] Arcuri A, Briand L. A practical guide for using statistical tests to assess randomized algorithms in software engineering[C]∥Proceedings of the 33rd International Conference on Software Engineering, Honolulu, Hawaii, USA, 2011: 1-10.

基金资助

国家自然科学基金项目(62076108)

国家自然科学基金项目(61872159)

吉林省教育厅项目(JJKH20211106)

吉林省教育厅项目(JJKH20211103KJ)