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

doi:10.13229/j.cnki.jdxbgxb.20240344

摘要/Abstract

摘要：

为了进一步提高样本集的多样性，提出了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.

Key words: software product lines, diverse sampling, novelty search, probability-aware diversification, evolutionary algorithm

中图分类号:

TP311

欧阳丹彤,袁哲,张立明. 基于自适应进化算法的软件产品线抽样方法[J]. 吉林大学学报(工学版), 2025, 55(9): 3007-3019.

Dan-tong OUYANG,Zhe YUAN,Li-ming ZHANG. Sampling method of software product line based on adaptive evolutionary algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(9): 3007-3019.

图/表 12

图1

表1

表2

图2

图3

图4

图5

图6

表6

图7

图8

表7

参考文献 35

[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.
	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.
[4]	马永杰, 陈敏. 基于卡尔曼滤波预测策略的动态多目标优化算法[J]. 吉林大学学报: 工学版, 2022, 52(6): 1442-1458.
	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	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.
[18]	Ermon S, Gomes C P, Selman B. Uniform solution sampling using a constraint solver as an oracle[J/OL]. [2024-03-15].
[19]	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.
[20]	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.
[21]	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.
[22]	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.
[23]	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.
[24]	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.
[25]	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.
[26]	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.
[27]	黄美发, 景晖, 钟艳如, 等. 基于拟随机序列的三维模型表面采样方法[J]. 计算机工程, 2008, 34(14): 263-265.
	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.
[28]	周慧思, 欧阳丹彤, 田新亮, 等. 基于模型诊断的一种新编码方法[J]. 计算机研究与发展, 2023, 60(1): 95-102.
	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.
[29]	Kang K C, Cohen S G, Hess J A, et al. Feature-oriented domain analysis (FODA) feasibility study[R]. Pittsburgh: Carnegie Mellon University, 1990.
[30]	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.
[31]	Keller A. Quasi-Monte Carlo image synthesis in a nutshell[C]∥Monte Carlo and Quasi-Monte Carlo Methods 2012, Sydney, Australia, 2013: 213-249.
[32]	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.
[33]	Baranov E, Legay A, Meel K S. Baital: an adaptive weighted sampling approach for improved t-wise coverage[J/OL]. [2024-03-15].
[34]	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.
[35]	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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

FM	\|F\|	\|C\|	\|core\|	\|dead\|
fiasco_17_10	234	1 178	7	6
lrzip	20	63	2	0
BerkeleyDBC	18	19	2	0
HiPAcc	31	104	1	0
Jhipster	45	104	7	0
E-shop	290	426	30	0
Printers	172	310	50	0
SmartHomev2.2	60	82	7	0
WebPortal	43	68	4	0
busybox_1_28_0	998	962	12	0
Polly	40	100	9	0
7z	44	210	5	0
JavaGC	39	105	7	0
VP9	42	104	9	0
axtls_2_1_4	94	190	4	0
uClibc-ng_1_0_29	269	1 403	14	0
toybox_0_7_5	316	106	8	15
toybox	544	1 020	4	365
axTLS	684	2 155	3	381
fiasco	1 638	5 228	49	964
SPLOT-FM-5000	5 000	9 419	75	0
uClinux	1 850	2 468	7	1 237
ref4955	1 218	3 099	0	50
adderII	1 276	3 206	0	37
ecos-icse11	1 244	3 146	0	35
m5272c3	1 323	3 297	0	43
pati	1 248	3 266	0	47
olpce2294	1 274	3 881	0	42
integrator_arm9	1 267	50 606	0	44
at91sam7sek	1 319	3 963	0	74
se77x9	1 319	49 937	0	58
phycore229x	1 360	4 026	0	89
freebsd-icse11	1 396	62 163	3	38
busybox-1.18.0	6 796	17 836	12	3 939
uClinux-config	11 254	31 637	15	6 012
buildroot	14 910	45 603	100	6 895
freetz	31 012	102 705	117	14 445
2.6.28.6-icse11	6 888	343 944	58	102
embtoolkit	23 516	180 511	839	6 561

FM编号	DDHN	NSbS		PaDN		FM编号	DDHN	NSbS		PaDN
1	63.006	63.148	?	65.220	?	21	357.001	362.475	?	376.201	?
2	2.053	2.053	?	2.053	?	22	2.125	18.621	?	9.992	?
3	1.824	1.824	?	1.824	?	23	5.635	7.794	?	5.466	?
4	4.002	4.045	?	4.355	?	24	5.932	8.152	?	5.868	?
5	4.179	4.179	?	4.195	?	25	5.893	7.643	?	5.893	?
6	1.128	4.175	?	1.202	?	26	6.624	8.902	?	6.581	?
7	5.841	5.888	?	5.891	?	27	5.682	7.480	?	5.606	?
8	0.051	0.331	?	0.064	?	28	5.962	7.542	?	5.964	?
9	0.268	0.399	?	0.289	?	29	6.142	7.468	?	6.099	?
10	4.098	6.743	?	4.623	?	30	6.093	8.701	?	6.044	?
11	6.813	6.813	?	6.813	?	31	6.225	9.028	?	6.098	?
12	12.650	12.650	?	12.650	?	32	6.143	8.877	?	6.144	?
13	7.636	7.636	?	7.636	?	33	18.858	20.218	?	21.663	?
14	8.500	8.500	?	8.500	?	34	279.247	284.050	?	284.028	?
15	3.691	3.703	?	4.007	?	35	399.488	401.478	?	401.233	?
16	21.432	21.724	?	23.859	?	36	312.876	322.055	?	321.407	?
17	1.078	3.150	?	1.299	?	37	1 349.705	1 366.916	?	1 370.377	?
18	8.267	8.355	?	8.448	?	38	45.597	47.574	?	47.405	?
19	28.318	28.332	?	28.591	?	39	2 169.514	2 175.095	?	2 175.915	?
20	92.307	93.106	?	94.124	?

FM编号	DDHNSbS	M3		IR/%
1	63.006	63.177	?	-0.27
2	2.053	2.053	?	0.00
3	1.824	1.824	?	0.00
4	4.002	4.025	?	-0.57
5	4.179	4.179	?	0.00
6	1.128	1.142	?	-1.24
7	5.841	5.854	?	-0.22
8	0.051	0.053	?	-3.92
9	0.268	0.264	?	1.49
10	4.098	4.212	?	-2.78
11	6.813	6.813	?	0.00
12	12.650	12.650	?	0.00
13	7.636	7.636	?	0.00
14	8.500	8.500	?	0.00
15	3.691	3.693	?	-0.05
16	21.432	21.568	?	-0.63
17	1.078	1.116	?	-3.53
18	8.267	8.394	?	-1.54
19	28.318	28.311	?	0.02
20	92.307	92.300	?	0.01
21	357.001	357.762	?	-0.21
22	2.125	2.380	?	-12.00
23	5.635	6.236	?	-10.67
24	5.932	6.660	?	-12.27
25	5.893	6.558	?	-11.28
26	6.624	7.165	?	-8.17
27	5.682	6.261	?	-10.19
28	5.962	6.728	?	-12.85
29	6.142	6.762	?	-10.09
30	6.093	6.689	?	-9.78
31	6.225	6.933	?	-11.37
32	6.143	6.809	?	-10.82
33	18.858	18.697	?	0.85
34	279.247	276.312	?	1.05
35	399.488	399.740	?	-0.06
36	312.876	317.214	?	-1.39
37	1 349.705	1 351.619	?	-0.14
38	45.597	46.134	?	-1.18
39	2 169.514	2 172.433	?	-0.13

FM编号	DDHNSbS	M4		IR/%
1	63.006	62.968	?	0.06
2	2.053	2.053	?	0.00
3	1.824	1.824	?	0.00
4	4.002	4.031	?	-0.72
5	4.179	4.179	?	0.00
6	1.128	1.165	?	-3.28
7	5.841	5.847	?	-0.10
8	0.051	0.052	?	-1.96
9	0.268	0.271	?	-1.12
10	4.098	4.383	?	-6.95
11	6.813	6.813	?	0.00
12	12.650	12.650	?	0.00
13	7.636	7.636	?	0.00
14	8.500	8.500	?	0.00
15	3.691	3.700	?	-0.24
16	21.432	21.492	?	-0.28
17	1.078	1.123	?	-4.17
18	8.267	8.332	?	-0.79
19	28.318	28.421	?	-0.36
20	92.307	92.305	?	0.00
21	357.001	354.963	?	0.57
22	2.125	2.281	?	-7.34
23	5.635	6.156	?	-9.25
24	5.932	6.468	?	-9.04
25	5.893	6.429	?	-9.10
26	6.624	7.118	?	-7.46
27	5.682	6.197	?	-9.06
28	5.962	6.498	?	-8.99
29	6.142	6.599	?	-7.44
30	6.093	6.667	?	-9.42
31	6.225	6.802	?	-9.27
32	6.143	6.667	?	-8.51
33	18.858	19.021	?	-0.86
34	279.247	274.058	?	1.86
35	399.488	401.03	?	-0.39
36	312.876	311.247	?	0.52
37	1 349.705	1 349.448	?	0.02
38	45.597	46.994	?	-3.06
39	2 169.514	2 168.406	?	0.05