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

doi:10.13229/j.cnki.jdxbgxb.20240344

Abstract

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

CLC Number:

TP311

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.

Figures/Tables 12

Fig.1

Table 1

Table 2

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 6

Fig.7

Fig.8

Table 7

References 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.

Related Articles 12

[1]	Pei-ming SUN,Zhe WANG. Optimization method of party affairs activity scheduling based on directional differential evolution algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(8): 2761-2770.
[2]	Yong-jie MA,Min CHEN. 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.
[3]	Zhou-zhou LIU,Qian-yun ZHANG,Xin-hua MA,Han PENG. Compressed sensing signal reconstruction based on optimized discrete differential evolution algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2246-2252.
[4]	Bing-hai ZHOU,Qiong WU. Balancing and bi⁃objective optimization of robotic assemble lines [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 720-727.
[5]	Lei JIANG,Ren-chu GUAN. Design of fuzzy comprehensive evaluation system for talent quality based on multi⁃objective evolutionary algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1856-1861.
[6]	Lei CHEN,Jiang⁃feng WANG,Yuan⁃li GU,Xue⁃dong YAN. Multi⁃source traffic data fusion algorithm based onmind evolutionary algorithm optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 705-713.
[7]	HU Guan-yu, QIAO Pei-li. High dimensional differential evolutionary algorithm based on cloud population for network security prediction [J]. 吉林大学学报(工学版), 2016, 46(2): 568-577.
[8]	LI Gen,LI Wen-hui. Facial feature tracking based on mind evolutionary algorithm [J]. 吉林大学学报(工学版), 2015, 45(2): 606-612.
[9]	LI Gen,LI Wen-hui. Face occlusion recognition based on MEBML [J]. 吉林大学学报(工学版), 2014, 44(5): 1410-1416.
[10]	YOU Xiao-ming, LIU Sheng, WANG Yu-ming. Quantum-behaved network resource parallel allocation optimization model and application [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 341-345.
[11]	DING Hui, LI Hong-guang. Agent-based evolutionary approach towards solving constrained multi-objective optimization problems [J]. 吉林大学学报(工学版), 2011, 41(增刊1): 173-178.
[12]	ZHAO Wen-hong1, WANG Wei1,2, WANG Yu-ping2, HAO Ming-qiang3 . ZHAO Wen-hong1, WANG Wei1,2, WANG Yu-ping2, HAO Ming-qiang3 [J]. 吉林大学学报(工学版), 2008, 38(04): 865-870.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

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

Sampling method of software product line based on adaptive evolutionary algorithm

RICH HTML

PDF (PC)