Information and Software Technology

A multi-objective test case prioritization method based on UML Activity Diagram

--Manuscript Draft--

Manuscript Number: INFSOF-D-24-00429

Article Type: Research paper

Keywords: Test case prioritization; multi-objective; UML; sparrow search algorithm

Abstract: Context: Test case prioritization enhances regression testing efficiency. Yet, focusing
on a single optimization objective in sequencing leads to inadequate fault detection
performance in the test case execution sequence. Additionally, limited research
explores UML activity diagram-based prioritization.
Objectives: This study approaches the prioritization of test scenarios and the
generation of test data. The aim is to enhance the fault detection capability and overall
efficiency of the test suite through a multi-objective prioritization method.
Methods: Regarding test scenario prioritization, this research proposes a Permutation-
based Two Stage Sparrow Search Algorithm. PTS-SSA initiates a sequencing-based
decoding approach that translates sparrows from a continuous space to a sequenced
space. Subsequently, three enhanced sorted crossover operators are proposed to
enhance population search capabilities within the sorted space. Four objective
functions are formulated to comprehensively evaluate the sequences of test scenarios.
To generate test data, a decision backpropagation method based on test scenarios is
proposed, which backpropagates input data constraints through decision edge
conditions to generate test data based on the constraints.
Results: In test scenario prioritization experiments, PTS-SSA notably enhances test
suite fault detection capability, with APFDc metrics improving by an average of 42.41%
post-prioritization. Performance comparisons indicate that multi-objective prioritization
outperforms single-objective methods, with PTS-SSA showing superior performance
compared to the other two multi-objective techniques.
Conclusion: The proposed approach enhances fault detection capabilities and
optimizes the efficiency of regression testing by utilizing a multi-objective prioritization
method. The results demonstrate that PTS-SSA offers superior performance in
comparison to other single and multi-objective methods, thus providing a robust
solution for test case prioritization and test data generation.

Powered by Editorial Manager® and ProduXion Manager® from Aries Systems Corporation
Structured Abstract

Context: Test case prioritization enhances regression testing efficiency. Yet, focusing on a single
optimization objective in sequencing leads to inadequate fault detection performance in the test case
execution sequence. Additionally, limited research explores UML activity diagram-based prioritization.
Objectives: This study approaches the prioritization of test scenarios and the generation of test data. The
aim is to enhance the fault detection capability and overall efficiency of the test suite through a multi-
objective prioritization method.
Methods: Regarding test scenario prioritization, this research proposes a Permutation-based Two Stage
Sparrow Search Algorithm. PTS-SSA initiates a sequencing-based decoding approach that translates
sparrows from a continuous space to a sequenced space. Subsequently, three enhanced sorted crossover
operators are proposed to enhance population search capabilities within the sorted space. Four objective
functions are formulated to comprehensively evaluate the sequences of test scenarios. To generate test
data, a decision backpropagation method based on test scenarios is proposed, which backpropagates input
data constraints through decision edge conditions to generate test data based on the constraints.
Results: In test scenario prioritization experiments, PTS-SSA notably enhances test suite fault detection
capability, with APFDC metrics improving by an average of 42.41% post-prioritization. Performance
comparisons indicate that multi-objective prioritization outperforms single-objective methods, with PTS-
SSA showing superior performance compared to the other two multi-objective techniques.
Conclusion: The proposed approach enhances fault detection capabilities and optimizes the efficiency
of regression testing by utilizing a multi-objective prioritization method. The results demonstrate that
PTS-SSA offers superior performance in comparison to other single and multi-objective methods, thus
providing a robust solution for test case prioritization and test data generation.
Manuscript Click here to view linked References

A multi-objective test case prioritization method based on UML Activity Diagram

Xiaozhi Du a, *, Kai Chen a, Zongbin Qiao a
a
School of Software Engineering, Xi’an Jiaotong University, Shaanxi, China
Email: xzdu@[Link] (X.Z. Du), 1171319431@[Link] (K. Chen), qiaozob@[Link] (Z.B. Qiao)

Abstract

Context: Test case prioritization enhances regression testing efficiency. Yet, focusing on a single
optimization objective in sequencing leads to inadequate fault detection performance in the test case
execution sequence. Additionally, limited research explores UML activity diagram-based prioritization.
Objectives: This study approaches the prioritization of test scenarios and the generation of test data. The
aim is to enhance the fault detection capability and overall efficiency of the test suite through a multi-
objective prioritization method.
Methods: Regarding test scenario prioritization, this research proposes a Permutation-based Two Stage
Sparrow Search Algorithm. PTS-SSA initiates a sequencing-based decoding approach that translates
sparrows from a continuous space to a sequenced space. Subsequently, three enhanced sorted crossover
operators are proposed to enhance population search capabilities within the sorted space. Four objective
functions are formulated to comprehensively evaluate the sequences of test scenarios. To generate test
data, a decision backpropagation method based on test scenarios is proposed, which backpropagates input
data constraints through decision edge conditions to generate test data based on the constraints.
Results: In test scenario prioritization experiments, PTS-SSA notably enhances test suite fault detection
capability, with APFDC metrics improving by an average of 42.41% post-prioritization. Performance
comparisons indicate that multi-objective prioritization outperforms single-objective methods, with PTS-
SSA showing superior performance compared to the other two multi-objective techniques.
Conclusion: The proposed approach enhances fault detection capabilities and optimizes the efficiency
of regression testing by utilizing a multi-objective prioritization method. The results demonstrate that
PTS-SSA offers superior performance in comparison to other single and multi-objective methods, thus
providing a robust solution for test case prioritization and test data generation.
Keywords: Test case prioritization; multi-objective; UML; sparrow search algorithm

1. Introduction

Model-Based Testing (MBT) has received more and more attention from researchers. MBT can be
carried out in the early requirements analysis phase of software development so that errors can be
detected and avoided as early as possible, which in turn improves the testing efficiency and reduces the
testing cost. There are many models that can model the behavior of software from different perspectives,
such as Petri nets [1], finite state machines [2], extended finite state machines [3], UML [4], etc. The
scale and complexity of the Petri net model will increase with the complexity of the system under test,
and it is not applicable to the modeling of complex systems. The finite state machine model is highly
coupled and inflexible in structure. Extended finite state machine optimizes the finite state machine, but
it is still too complex when dealing with complex systems. In contrast, UML models are widely
applicable and simple to model, especially UML activity diagrams can effectively model complex
dynamic workflows and express the complex interactive behaviors among various activities of the system
in a visual form [5].
 Test case prioritization (TCP) is a crucial element in model-based testing. To ensure software
accuracy and reliability, numerous test cases are typically required, making test case execution a time-
intensive and resource-consuming task. Due to constraints in time and resources, executing all test cases
in full is often infeasible. In traditional sequential testing, test cases follow a predetermined order,
potentially delaying the discovery of critical errors until later stages, wasting resources. Time limitations
may prevent the execution of defect-detecting test cases, leading to undetected defects with serious
repercussions [6]. Through TCP, prioritizing essential test cases for execution enables swift defect
identification, reducing time and resource costs and the risk of releasing flawed software. Prioritizing
critical functionalities for testing early in the software development cycle via TCP facilitates prompt
issue resolution and problem prevention. When dealing with a large number of test cases, TCP ensures
optimal resource allocation to enhance testing efficiency and focus scarce resources on vital test cases.
In post-maintenance and software upgrades, TCP boosts regression testing efficiency, correcting the
model to improve fault detection. TCP tackles multiple factors simultaneously, including time and
resource constraints, making it a multi-objective optimization dilemma that necessitates a holistic
approach. Test cases stem from a blend of test scenarios and data, with TCP generating numerous test
cases from lower-priority scenarios, affecting optimization efficiency to some degree [7].
To solve the above problems, this paper firstly proposes a UML activity diagram-based test
scenario prioritization algorithm called Permutation-based Two Stage Sparrow Search Algorithm. And
an objective function with stronger evaluation capability is proposed to improve the performance of test
scenario optimization sequence. Then the decision backpropagation method is proposed to generate the
corresponding test data from the test scenarios, which is finally combined to obtain the test cases. The
main contributions of this paper are as follows:：
(1) In this paper, we propose a Permutation-based Two Stage Sparrow Search Algorithm (PTS-
SSA) that manages the convergence and diversity of populations, respectively, and performs sequence
discretization of SSA through a sequencing-based decoding method, as well as three improved crossover
operators based on the sequencing, which can efficiently accomplish the prioritization of test scenarios
from a multi-objective perspective.
(2) This paper proposes four objective functions based on UML activity diagrams, namely
APDC,APCC, APLC, and APNC, which are able to evaluate the test scenario sequences more
comprehensively and improve the comprehensive fault detection capability of the test scenario
optimization sequences.
(3) This paper proposes the decision backpropagation method, which parses the decision
conditions on the edges of the test scenarios, backpropagates the constraints on the input data, and then
automatically generates the test data corresponding to the test scenarios based on the constraints.
The rest of this paper is organized as follows. Section 2 reviews related work and discusses the
unresolved issues. In Section 3, the proposed PTS-SSA method is described in detail. In Section 4, some
experiments are conducted to evaluate the feasibility and effectiveness of our method. Section 5
concludes this paper and discusses some future work.
2. Related Work

2.1. Test case prioritization

Model-Based Test Case Prioritization can enhance early-stage failure detection in software
development. In recent years, a growing number of researchers have directed their attention to UML-
based test case prioritization techniques. Bhuyan et al. [8] modeled the system under test using UML
activity and use case diagrams, assigning node weights based on node coverage and complexity,
determining path weights from included nodes, and prioritizing test cases accordingly. The method's
computational complexity is elevated, with significant resource consumption, especially in complex
system scenarios. Meiliana et al. [9] introduced an enhanced genetic algorithm for optimizing test cases
based on UML activity diagrams, albeit leading to redundant node generation. Panthi et al. [10] proposed
a two-stage test case generation and optimization approach using UML activity diagrams. The initial
phase involves transforming UML activity diagrams into activity interaction diagrams, while the
subsequent phase generates and sequences test scenarios from activity interaction diagrams based on
decision and concurrency criteria employing an enhanced ant colony algorithm. This method enhances
the efficacy of generated test scenarios. However, converting activity diagrams into interaction diagrams
presents limitations and challenges, particularly in complex activity diagram applications.
Heuristic algorithms are frequently utilized in TCP. Khatibsyarbini et al [11] implemented the
firefly algorithm in addressing the TCP problem. This method employs an objective function based on
similarity distance to prioritize test cases. Bajaj et al [12] introduced a discrete cuckoo search algorithm,
enhancing the cuckoo search algorithm with an adaptive strategy of asexual genetic reproduction for
sorting test cases. Additionally, they hybridized the cuckoo search algorithm with the genetic algorithm
to boost search capabilities and prevent local optima. While this approach enhances sorting quality, it
suffers from high computational complexity and inefficiency. On the other hand, Xing et al [13]
revamped the coding method of the artificial fish schooling algorithm, optimizing clustering, foraging,
and tail chasing behaviors based on test-point coverage and execution time. This optimization enhances
the algorithm's efficiency in prioritizing test cases. However, the experimental validation was limited to
simpler programs, lacking validation on complex programs.
In real-world test scenarios, TCP often involves multiple optimization objectives such as branch
coverage, statement coverage, and execution time of use cases. Consequently, there is a growing body of
research tackling the TCP conundrum from a multi-objective perspective. Tulasiraman et al [14]
introduced an enhanced Pareto optimal clone selection method that prioritizes test cases based on three
objectives—execution time, severe fault identification, and detection cost—thus bolstering the fault
detection rate of the test case set. Arrieta et al [15] improved the test case set's fault detection rate in the
Nondominated Sorting Genetic Algorithm based on Elite Strategies (NSGA-II) by introducing novel
crossover and mutation operators and designing four objective functions for Cyber-Physical Systems
(CPSs). This enhancement effectively boosts optimization outcomes for TCP issues. Nazir et al. [16]
leveraged the Multi-objective Particle Swarm Algorithm (MOPSO) to enhance TCP optimization by
incorporating a new crossover operator and four objective functions. Their approach advances the fault
coverage of the test case set, albeit in a relatively simple experimental environment without tests on
complex systems. Birchler et al [17] extracted static road features from an autopilot simulation
environment to develop diversity metrics integrated into NSGA-II, guiding autopilot test case
prioritization and significantly reducing overall test execution time. Vedpal et al [18] proposed a multi-
objective hybrid chaotic Drosophila optimization algorithm, initiating the Drosophila population through
chaotic mapping to enhance population distribution breadth. By blending foraging behavior and
reproductive characteristics, this method improves search capabilities in TCP, facilitating rapid
exploration of solution spaces and preventing convergence to local optima.

2.2. Motivation

Many excellent TCP algorithms have been proposed and have achieved good results. However,
there are still many problems: firstly, most of the methods are based on code design and cannot be tested
starting from the requirement analysis stage in the early stage of software development. Secondly, the
number of test cases is huge and contains a large number of low-priority test cases, which leads to a long
optimization sequence and greater difficulty in optimization; finally, the optimization objective is not
fully considered, which leads to a poor performance of the optimization sequence in terms of
comprehensive fault detection.
In order to solve the above problems, this paper accomplishes the prioritization of test cases from
two aspects: prioritization of test scenarios and generation of test data based on test scenarios. First, for
prioritizing test scenarios, this paper proposes a two-stage sparrow search algorithm based on ranking.
The method improves the optimization efficiency in long sequences by managing convergence and
diversity separately. Then four objective functions based on UML activity diagrams are designed to
improve the comprehensive fault detection capability of the optimized sequences. Secondly, for test data
generation, this paper proposes a decision backpropagation method. The method backpropagates the
constraints of the input data by parsing the decision conditions on the decision edges of the test scenarios,
and then automatically generates the corresponding test data. Test scenarios with high priority will
generate more test cases, and test scenarios with low priority will generate fewer test cases, thus ensuring
higher fault detection capability of the test sequence.

3. The proposed method

In this section, the details of the PTS-SSA and decision backpropagation methods proposed in this
paper, as well as the process of converting the TCP problem into a multi-objective optimization problem,
are presented. The overall flow of the method is shown in Figure 1 and each step is described in detail
below.

Fig.1 Multi-objective TCP process based on UML activity diagrams

3.1. Pre-process UML activity diagrams

UML is a unified, standard and visual modeling language for object-oriented software design [9],
which is suitable for architecture-focused and use-case-driven software design process. UML enables
designers to achieve a consistent understanding of the semantic description, thus eliminating the impact
of different methods of expression. Therefore, in this paper, activity diagrams are used as the object of
study.
Specifically, activity diagrams have the following two properties:
(1) Describing test cases from a system functional perspective. Compared with other visualization
models, UML activity diagrams can clearly demonstrate business processes in a complex model in a
simple and intuitive form. Therefore, test cases can be described through the process information
generated by users interacting with system functions [19].
(2) Describing test cases from the control dependency perspective. UML activity diagrams
abstract and conceptualize the system under test. In addition to the basic elements such as activities and
actions, there are also control dependency elements such as branching and merging, bifurcation and
confluence. These control dependency elements can describe the test cases more clearly, and they are the
necessary conditions for TCP based on the model [19].
UML is characterized by unstructuredness, abstraction, etc., so a formal definition of activity
diagrams is needed to obtain information about activity nodes and decision edges that are necessary for
generating test cases. In this paper, the activity diagram is standardized and defined as follows:
Definition 2-1 Define an activity graph as a set of elements 𝐺 = {𝐴, 𝑂, 𝑇, 𝐵, 𝑀, 𝐹, 𝐽}。where 𝐴 =
{𝑎0 , 𝑎1 , 𝑎2 , … } is the set of activities. 𝑂 = {𝑜0 , 𝑜1 , 𝑜2 , … }is the set of objects. 𝑇 = {𝑡0 , 𝑡1 , 𝑡2 , … } is the
set of transfer flows. 𝐵 = {𝑏0 , 𝑏1 , 𝑏2 , … }is the set of branch nodes. 𝑀 = {𝑚0 , 𝑚1 , 𝑚2 , … } is the set of
merge nodes. 𝐹 = {𝑓0 , 𝑓1 , 𝑓2 , … }is the set of bifurcation nodes. 𝐽 = {𝑗0 , 𝑗1 , 𝑗2 , … } is the convergence
node set.
Definition 2-2 In an activity graph 𝐺 = {𝐴, 𝑂, 𝑇, 𝐵, 𝑀, 𝐹, 𝐽}, assume that 𝐴′ ⊆ 𝐴、𝑏 ′ ∈ 𝐵、𝑚′ ∈
𝑀，∃𝑇 ′ ⊆ 𝑇，𝑆. 𝑇. ∀𝑎 ∈ 𝐴′ , 𝑎 → 𝑏 ′ → 𝑚′ → 𝑎，then define 𝐶 = {𝐴′ , 𝑇 ′ , 𝑏 ′ , 𝑚′ } to be the cyclic
structure of the activity graph.
Definition 2-3 In an activity graph 𝐺 = {𝐴, 𝑂, 𝑇, 𝐵, 𝑀, 𝐹, 𝐽}, assume that 𝐴′ ⊆ 𝐴、𝑓 ′ ∈ 𝐹、𝑗 ′ ∈ 𝐽，
∃𝑇 ′ ⊆ 𝑇，𝑆. 𝑇. ∀𝑎 ∈ 𝐴′ , 𝑓 ′ → 𝑎 → 𝑗 ′ ，then define 𝐶 = {𝐴′ , 𝑇 ′ , 𝑓 ′ , 𝑗 ′ } to be the concurrency structure
of the activity graph.

Figure 2 shows an example of a UML activity diagram for the ATM model [20], which contains
branching, looping and concurrency structures. Based on the ATM model, the preprocessing of UML
activity diagrams is as follows: firstly, the activity diagrams are converted into parsable XML files. When
parsing the XML file, this paper extracts the valid information in the XML file according to the
transformation rule table [21] and generates CFGs, which are stored in the form of adjacency tables. The
activities in the activity graph are mapped to the nodes in the CFG and the transfer flows in the activity
graph are mapped to the edges in the CFG through the transformation rules. The table of transformation
rules is shown in Table 1. After applying the transformation rule table on the ATM activity graph shown
in Fig. 2, the generated CFG is shown in Fig. 3. Table 2 shows some of the test scenarios for ATM activity
graph generation. In this paper, only the prioritization of the test scenarios is considered, without
considering how the test scenarios are generated.
 Fig.2 ATM Activity Diagram

Table 1 Activity diagram to CFG conversion rule

UML Activity Diagram Node CFG node
Start Node S: node with indegree 0
End Node E: node with outdegree 0
Branch Node B: node with indegree 1 and outdegree 2
Merge Node M: node with at least 2 indegree and 1 outdegree
Fork Node F: node with indegree 1 and outdegree at least 2
Join Node J: node with indegree of at least 2 and outdegree of 1
Active node A: node with in-degree 1 and out-degree 1
Transfer Edge D: An edge connecting two nodes
 Fig.3 CFG of ATM Activity Diagram
Table 2 some test scenario of the ATM activity diagram
number Test Scenario
TS1 0-1-2-3-4-5-9-10-11
TS2 0-1-2-3-4-2-3-4-5-9-10-11
TS3 0-1-2-3-4-5-6-12-13-14-16-22-23-7-8-9-10-11
TS4 0-1-2-3-4-5-6-12-13-14-17-19-22-23-7-8-9-10-11
TS5 0-1-2-3-4-5-6-12-13-14-17-19-21-22-23-7-8-9-10-11
TS6 0-1-2-3-4-5-6-12-13-15-18-20-22-23-7-8-9-10-11
TS7 0-1-2-3-4-5-6-12-13-15-18-20-24-25-26-27-28-29-22-23-7-8-9-10-11
TS8 0-1-2-3-4-5-6-12-13-14-16-22-23-7-6-12-13-14-16-22-23-8-9-10-11

3.2. Objective function design

A multi-objective optimization problem contains multiple conflicting optimization objectives,

which can be defined by Eq. (1) (without loss of generality, take minimization optimization as an
example):
 min 𝐹(𝑥) = (𝑓1 (𝑥), 𝑓2 (𝑥), … , 𝑓𝑀 (𝑥)) ∈ 𝛷
(1)
𝑠. 𝑡. 𝑥 ∈ 𝛺

where 𝑥 = (𝑥1 , 𝑥2 , … 𝑥𝐷 )𝜖𝛺 is a D−dimensional decision vector. 𝛷 ϵ ℝ𝑀 is the M−dimensional

objective space. 𝛺 ∈ ℝ𝐷 is the D-dimensional decision space. M is the number of objectives, D is
the number of decision variables, and F is a mapping from the D-dimensional decision space to the M-
dimensional objective space. When 𝐷 > 100, it is a large-scale multi-objective optimization problem.
In complex systems, the number of decision nodes may exceed 100, and the set of test cases to be sorted
at the same time may include thousands of test cases, so the test case prioritization problem for complex
systems is a large-scale multi-objective optimization problem.
In this paper, we will address the TCP problem from a multi-objective perspective, starting with
the design of multiple objective functions capable of comprehensively evaluating test case execution
sequences. In code-based TCP research, because the fault detection information of the sequence cannot
be obtained until the test case sequence is run. Based on the assumption that the stronger the sequence
coverage capability is the stronger the fault detection capability is, related studies tend to model the fault
detection capability by calculating the coverage of the test case sequence over the program through
multiple coverage matrices. Therefore, this paper will adopt a similar strategy to design the objective
function from the perspective of coverage. Because UML activity diagrams are characterized by
describing the interactive behaviors and concurrent behaviors that exist between systems, in this paper
we design the Average of the Percentage of Decision Coverage (APDC), Average of the Percentage of
Concurrent Coverage (APCC),Average of Percentage of Loop Coverage, APLC) three minimum
optimization objective functions. The calculation of APDC is shown in equation (2):
𝑚
∑ 𝑑𝑒 𝑇𝑆𝑖 1
𝐴𝑃𝐷𝐶 = 𝑖=1 − (2)
𝑛 ∙ 𝑚𝑑𝑒 2𝑛

where 𝑛 is the number of test scenarios. 𝑚𝑑𝑒 is the number of decision nodes in the model. 𝑇𝑆𝑖 is the
test scenario execution number covering the i_th decision node. the calculation of APCC is shown in
equation (3):

∑𝑚 𝑐
𝑖=1 𝑇𝑆𝑖 1
𝐴𝑃𝐶𝐶 = − (3)
𝑛 ∙ 𝑚𝑐 2𝑛

where 𝑚𝑐 is the number of concurrent modules in the model. 𝑇𝑆𝑖 is the execution number of the test
scenario covering the i-th concurrent module. the calculation of APLC is shown in Equation (4):
𝑚𝑙
∑𝑖=1 𝑇𝑆𝑖 1
𝐴𝑃𝐿𝐶 = − (4)
𝑛 ∙ 𝑚𝑙 2𝑛

where 𝑚𝑙 is the number of loop modules in the model. 𝑇𝑆𝑖 is the test scenario execution sequence
number that covers the i-th loop module. PTS-SSA is the minimum value optimization strategy, so the
smaller the values of APDC, APCC, and APLC are, the better the coverage ability of the test case
execution sequence. Meanwhile, the three objective functions are optional, and the appropriate objective
function can be selected according to the existence of corresponding conditions in the model.
Execution time is one of the important optimization objectives in TCP, but this paper is based on
model prioritization of test scenarios, and the execution time of test scenarios is not available. According
to the theoretical analysis, the activity nodes will be written as related codes, and the more and more
difficult the executed codes are, the longer the corresponding execution time will be. In the actual testing
process, different execution times can be represented by giving weights to the activity nodes. This paper
is based on the assumption that the amount of code and the execution difficulty of each activity node are
the same, then the more activity nodes are covered, the longer the theoretical execution time. Therefore,
this paper proposes the fourth objective function Average of the Percentage of Node Coverage (APNC),
and the calculation of APNC is shown in Equation (5):
𝑚 𝑛𝑑
∑𝑖=1 𝑇𝑆𝑖 1
𝐴𝑃𝑁𝐶 = − (5)
𝑛 ∙ 𝑚𝑛𝑑 2𝑛

where 𝑚𝑛𝑑 is the number of nodes in the model. 𝑇𝑆𝑖 is the test scenario execution number that covers
the i-th node.
To compute the above proposed 4 objective functions, then the activity graph is first preprocessed
to obtain the corresponding coverage matrices. According to the design of this paper, 4 coverage matrices
need to be obtained from the activity graph, which are decision node coverage matrix, concurrent module
coverage matrix, cyclic module coverage matrix and node coverage matrix. Taking the ATM activity
graph in Fig. 2 and the sequence of 8 test scenarios shown in Table 2 as an example, Tables 3 to 6 are the
corresponding decision node (D1~D10) coverage matrices, concurrent module coverage matrices, cyclic
module (L1~L4) coverage matrices and node (N1~N30) coverage matrices generated. In the decision
node coverage matrix, only branching decision nodes are considered and decision nodes with cyclic paths
are not considered. And each branch of a decision node is considered separately for coverage or not.
Concurrent Module Coverage Matrix only considers whether to cover concurrent modules or not, and
the branch structure and loop structure inside concurrent modules will be included in Decision Node
Coverage Matrix and Circular Module Coverage Matrix.

Table 3 Decision Node Coverage Matrix of ATM Activity Diagram

TS1 TS2 TS3 TS4 TS5 TS6 TS7 TS8

D1 * *
D2 * * * * * *
D3 * *
D4 * * * *
D5 * *
D6 * *
D7 *
D8 *
D9 *
D10 *

Table 4 Concurrency Module Coverage Matrix of ATM Activity Diagram

TS1 TS2 TS3 TS4 TS5 TS6 TS7 TS8

C1 *
 Table 5 Cyclic Module Coverage Matrix of ATM Activity Diagram

TS1 TS2 TS3 TS4 TS5 TS6 TS7 TS8

L1 * * * * * * * *
L2 *
L3 * * * * * *
L4 *

3.3. Permutation-based two stage sparrow search algorithm

The purpose of TCP is to organize test cases to achieve specific goals, such as meeting coverage
criteria faster or speeding up fault detection, etc. The mathematical definition of TCP is as follows:
Definition 3-1 Define a test case set 𝑇 = {𝑡1 , 𝑡2 , … , 𝑡𝑛 }， the set of full permutations 𝑃𝑇 of the
test case set 𝑇 , and the mapping 𝑓: 𝑃𝑇 → 𝑅′′ 。 Find a 𝑇 ′ ∈ 𝑃𝑇, 𝑆. 𝑇. ∀𝑇 ′′ , 𝑓(𝑇′) ≥ 𝑓(𝑇′′)(𝑇 ′′ ∈
𝑃𝑇, 𝑇 ′′ ≠ 𝑇 ′ )。
From the above definition, it is clear that TCP is to find a sequence of test cases such that the
function mapping value of that sequence of test cases is optimal. Thus, TCP is essentially a discrete
combinatorial optimization problem. For the TSP problem, a two-stage sort based sparrow algorithm is
proposed, and its overall flow is shown in Fig. 4. The PTS-SSA is divided into two phases to perform the
search, one is the convergence search phase and the other is the diversity search phase, and the PTS-SSA
selects the search phases adaptively based on the distribution of individuals on the PF.
The convergent search phase mainly manages the convergence of the population and ensures the
fast convergence of the population to the [Link] [22] is a single-objective optimization heuristic
algorithm that simulates sparrow predation and antipredation, and has strong convergence. To enable
SSA to be applied to multi-objective optimization problems, this paper proposes an adaptive population
partitioning strategy and a randomly guided search strategy. In the adaptive population partitioning
strategy, the individuals on PF are partitioned into the discoverer subpopulation and the rest into the
follower subpopulation according to the non-dominated sorting result of the population, and the vigilant
subpopulation is adaptively adjusted according to an adaptive function. In the randomly guided search
strategy, the followers randomly select a discoverer as the next search target, thus realizing the fast
convergence of the population to the Pareto frontier. Second, the solution space of SSA is continuous,
while the solution space of TSP is a discrete permutation space, so this paper introduces a sort-based
decoding method to discretize the solution of SSA.
The diversity search phase mainly manages the diversity of the populations and ensures that the
populations are widely distributed and diversely represented on the PF. In order to fully explore the large-
scale decision space, this paper proposes a dynamic population division strategy and a multi-
subpopulation search strategy. First, the sparrow population is divided into three subpopulations by the
dynamic population division strategy, and each subpopulation will adopt a search strategy with different
search directions to complete the full exploration of the large-scale decision space. Among them, the
discoverer subpopulation adopts the improved positional crossover operator to fully explore the local
space; the vigilant subpopulation adopts the sorted and improved inverse learning operator to detect the
potential global optimal position to prevent the algorithm from falling into the local optimum; and the
follower subpopulation adopts the dynamic k-opt operator to perform the comprehensive search.
 Table 6 Node Coverage Matrix of ATM Activity Diagram

TS1 TS2 TS3 TS4 TS5 TS6 TS7 TS8

N1 * * * * * * * *
N2 * * * * * * * *
N3 * * * * * * * *
N4 * * * * * * * *

N5 * * * * * * * *
N6 * * * * * * * *
N7 * * * * * *

N8 * * * * * *
N9 * * * * * *
N10 * * * * * * * *
N11 * * * * * * * *

N12 * * * * * * * *
N13 * * * * * *
N14 * * * * * *
N15 * * * *
N16 * *

N17 * *
N18 * *
N19 * *

N20 * *
N21 * *
N22 *
N23 * * * * * *

N24 * * * * * *
N25 *
N26 *

N27 *
N28 *

N29 *
N30 *
PTS-SSA will choose the appropriate search phase according to the distribution of the population
on PF, so as to better balance the convergence and diversity of the population in the whole search process.
Meanwhile, to ensure the search efficiency of the algorithm in the early stage, this paper proposes a
chaotic population initialization strategy, which ensures that the initial solutions of the population are
widely and randomly distributed, so as to reduce the computational cost of the early ineffective search.
The two stages are described in detail below.

Fig.4 PTS-SSA Algorithm Framework

3.3.1. Population chaotic initialization

Initializing the population by obeying uniformly distributed random numbers leads to insufficiently
wide distribution of the population in the early stage, which reduces the search efficiency of the
population in the early stage. Especially under the huge search space of LSMaOPs, a population that is
not widely distributed tends to perform a large number of blind searches in the early stage, which affects
the convergence of the population. Chaos theory describes the complex behavior of a nonlinear
deterministic system with stochastic and ergodic properties [23]. The population generated by chaotic
mapping can have a more uniform distribution in the space [24]. It has been proven on single-objective
optimization problems that initializing the population by chaotic sequences can effectively improve the
search efficiency of the algorithm in the early stage [25]. Therefore, in this paper, Singer mapping is
chosen to generate chaotic sequences to initialize the population to improve the early search capability
of the algorithm in the large-scale decision space. the Singer mapping is shown in Eq. 6:
𝑧𝑘+1 = 𝜇(7,86𝑧𝑘 − 23.31𝑧𝑘2 + 28.75𝑧𝑘3 − 13.302875𝑧𝑘4 ) (6)

where the singer mapping has chaotic properties for 𝜇 ∈ [0.9,1.08]. Singer mappings have a larger value
domain than other chaotic mappings, which can accommodate more types of problems. In this paper, 𝜇
is set to 1.

3.3.2. Sorting-based decoding method

TCP problems are discrete combinatorial optimization problems where the solutions are encoded as a set
of discrete sequences, each corresponding to a test case execution order for a set of test cases. Therefore,
it is important to design the mapping function to map the solutions in the continuous space to the discrete
permutation space in such a way that there is no overlap or omission. Based on the above considerations,
this paper introduces a sort-based decoding method [26] to accomplish the mapping. The flow of the
sort-based decoding method is shown in Fig. 5. First, the algorithm performs the normal position update
operation on the sorted solution to generate a set of continuous variable solutions; then the continuous
variables within the solution are sorted to obtain the sequential number of each continuous variable after
sorting, in this paper, we choose the non-descending sorting, if the values of the continuous variables are
the same, their original relative positions are maintained; and then the continuous variables with the
sequential number are restored to the original position, and the final sorting of the sequential number is
the decoded solution. The order-based decoding method can map the solutions in the continuous space
to the discrete arrangement space without any weighting or omission, and better retain the original
information of the continuous variables, which ensures the effectiveness of the algorithm's search results.
In this paper, after the initialization of the population and the convergence search phase are completed,
the order-based decoding method is used to map the solutions.

Fig. 5 Flow of Sorting-based decoding method

3.3.3. Convergent search stage

The convergence search phase mainly manages the convergence of the population and ensures the
fast convergence of the population to the PF. To enable SSA to be applied to large-scale multi-objective
optimization problems, this paper proposes an adaptive population partitioning strategy and a stochastic
guided search strategy. In the adaptive population partitioning strategy, the individuals on the PF are
divided into the discoverer subpopulation and the rest into the follower subpopulation according to the
non-dominated sorting result of the population, and the vigilant subpopulation is adaptively adjusted
according to an adaptive function. In the randomly guided search strategy, the followers will randomly
select a discoverer as the next search target, thus realizing the fast convergence of the population to the
Pareto frontier. The detailed steps of the adaptive population partitioning strategy and the randomized
bootstrap search strategy are described below.

(1) Adaptive population dividing strategy

The size of the subpopulation in the original sparrow algorithm is generally set subjectively, with
20 to 40 percent of the population being finders and the rest being followers. Vigilantes make up 10% to
20% of the population. However, in large-scale multi-objective optimization problems, a fixed division
strategy may result in dividing the non-dominated individuals into followers, which makes the non-
dominated individuals converge and gather among themselves, incurring additional computational costs;
or dividing the dominated individuals into discoverers, which makes the dominated individuals not
converge to the PF, thus reducing the convergence efficiency. Both of these cases reduce the optimization
efficiency of the algorithm. Therefore, this paper proposes an adaptive population partitioning strategy:
firstly, a fast non-dominated sorting of the population is performed, and then all non-dominated
individuals at the current PF are partitioned into the discoverer subpopulation, and the rest of the
dominated individuals are partitioned into the follower subpopulation. All the non-dominated individuals
will be randomly wandering in the PF, which can improve the diversity of the population to some extent,
while avoiding falling into the local optimum. Individuals in the follower subpopulation will converge
quickly to the current PF through the randomized bootstrap search strategy. It does not make much sense
for the individuals in the follower subpopulation to perform local exploitation or global exploration,
because none of the individuals in this subpopulation is at the PF, so the explored positions may not be
as good as the current PF in most cases, which will only lead to a large number of meaningless blind
searches and increase the computational cost in vain. Therefore, in this paper, we let the follower
subpopulation converge to the PF quickly, so that more individuals can search on the PF, thus reducing
the cost of blind search and improving the search efficiency. In the original SSA, the subpopulation of
vigilantes is randomly selected in the whole population, and both discoverers and followers have the
chance to become vigilantes. However, in a multi-objective optimization problem, followers become
vigilant because they are not on the current PF, so becoming vigilant only increases the cost of blind
search. Therefore, in the adaptive population segmentation strategy, the vigilant will not be selected from
the followers, but only randomly selected from the discoverers. Meanwhile, because the vigilantes are
selected only from the discoverers, this paper also expands the selection ratio of the vigilantes and
adaptively adjusts the percentage of vigilantes according to Equation.7:

𝑖𝑡𝑒𝑟
𝑟𝑜𝑣 = 𝛼 + 𝛽 ∗ tanh (𝛾 + 𝜎 ∗ ) (7)
𝑖𝑡𝑒𝑟𝑚𝑎𝑥

where 𝑟𝑜𝑣 is the percentage of vigilantes. 𝑖𝑡𝑒𝑟 is the current iteration number. 𝑖𝑡𝑒𝑟𝑚𝑎𝑥 is the
maximum iteration number. 𝛼、𝛽、𝛾、𝜎are the hyperparameters. In this paper, we fit the rov curve by
experiment, the hyperparameters are chosen as 𝛼 = 0.3, 𝛽 = −0.2, 𝛾 = −5, 𝜎 = 10，and Fig.6 is the
rov curve when 𝑖𝑡𝑒𝑟𝑚𝑎𝑥 = 1000.
 Fig. 6 changes in the percentage of vigilantes

(2) Random bootstrap search strategy

In the original SSA, the follower will move towards the finder individual with the optimal objective
function value. Thus, most of the studies on multi-objective improvement of SSA will determine the
optimal non-dominant individual by calculating the crowding degree distance. By analyzing these studies,
the reason is because these studies need SSA to manage both convergence and diversity at the same time,
so the optimal nondominant individual is selected to guide the search by the crowding degree distance.
SSA itself has excellent convergence, but the diversity of SSA performs poorly due to its search
mechanism and guidance mechanism. MOPs need to consider both convergence and diversity, so these
studies need to select the optimal nondominant individuals by the crowding degree distance to improve
the diversity performance of SSA as much as possible. However, in TS-SSA, convergence and diversity
are managed separately, and SSA only needs to mainly manage convergence to ensure that the population
converges to PF quickly, and then improve the population diversity as much as possible. Therefore, this
paper proposes a randomized bootstrap search strategy that focuses on the convergence of the population
and allows the successors to converge to the PF quickly, and also ensures that the extensive distribution
of the original individuals on the PF is not destroyed. In the randomized bootstrap search strategy, the
discoverer searches through Eq.8:

−𝛾
𝑋𝑖𝑡 ∙ 𝑒𝑥𝑝 ( ) 𝑖𝑓 𝑅 < 𝑆𝑇
𝑋𝑖𝑡+1 ={ 𝛼 ∙ 𝐼𝑡𝑒𝑟𝑚𝑎𝑥 (8)
𝑋𝑖𝑡 + 𝑄 ∙ 𝐿 𝑖𝑓 𝑅 ≥ 𝑆𝑇

where 𝑡 is the current iteration number. 𝛾 ∈ (0, 𝑆𝑢𝑏𝑃𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 ] is a random number obeying a
uniform distribution. 𝑆𝑢𝑏𝑃𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 is the number of individuals in the subpopulation of
discoverers.𝛼 ∈ (0,1] is a random number.𝐼𝑡𝑒𝑟𝑚𝑎𝑥 is the maximum number of iterations.𝑅 ∈ [0,1] is
an alarm value.𝑆𝑇 ∈ [0.5,1] is the safety threshold.𝑄~𝑁(0,1) is the random number obeying a normal
distribution.𝐿 is a1 × 𝑑 vector with each dimension being 1. The individuals in the discoverer subgroup
are all non-dominant to each other, so there is no ordering relationship of superiority or inferiority, so the
random number γ is used in Eq.8.
In random bootstrap search strategy，The follower searches through Eq.9:
 𝑋𝑖𝑡+1
𝑡
𝑋𝑟𝑓 − 𝑋𝑖𝑡 𝑃𝑜𝑝 𝑃𝑜𝑝 (9
𝑄 ∙ 𝑒𝑥𝑝 ( ) 𝑖𝑓 𝑖 > 𝑎𝑛𝑑 𝑆𝑢𝑏𝑃𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 <
={ 𝑖2 2 2 )
𝑡
𝑋𝑟𝑑 + |𝑋𝑖𝑡 − 𝑋𝑟𝑑
𝑡
| ∙ 𝐴+ ∙ 𝐿 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
𝑡 𝑡+1
where 𝑋𝑟𝑓 is randomly selected individual in the follower subpopulation other than individual 𝑖. 𝑋𝑟𝑑
is randomly selected individual in the discoverer subpopulation. 𝐿 is a 1 × 𝑑 vector, 𝐴+ =
𝐴𝑇 (𝐴𝐴𝑇 )−1 , and 𝐴 is a vector of 1 × 𝑑 randomized to 1 or -1 in each dimension, 𝑛 is the population
size, 𝑆𝑢𝑏𝑝𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 is discoverer subpopulation size. In TS-SSA, convergence and diversity are
managed separately, and SSA only needs to mainly manage convergence primarily to ensure that the
population converges quickly to the Pareto front, and then increase the population diversity as much as
possible. Therefore, randomly selecting any individuals on the Pareto front can ensure fast convergence
of the dominant individuals. It also avoids the high computational cost of selecting the optimal
nondominant individual by computing the crowded distance. When the followers are at the back of the
population and the number of individuals in the discoverer subpopulation does not exceed half of the
𝑛 𝑛
total number of the population, i.e., 𝑖 > 𝑎𝑛𝑑 𝑆𝑢𝑏𝑝𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 < , it is better to stay away from
2 2

other followers. Because there are a few discoverers at this time, guiding the followers at this time will
lead to the aggregation of the population and reduce the diversity of the population.
The random bootstrap search strategy for the vigilante subpopulation is shown in Eq.10:

𝑋𝑖𝑡+1

𝑡
𝑃𝑜𝑝
𝑋𝑟𝑑 + 𝛽 ∙ |𝑋𝑖𝑡 − 𝑋𝑟𝑑
𝑡
| 𝑖𝑓 𝑆𝑢𝑏𝑃𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 < (1
2
= |𝑋𝑖𝑡 − 𝑋𝑟𝑓
𝑡
| 𝑃𝑜𝑝 0)
𝑋𝑖𝑡 + 𝐾 ∙ ( ) 𝑖𝑓𝑆𝑢𝑏𝑃𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 >
1 𝑀 2
{ ∑ (𝑓 − 𝑓𝑟𝑓,𝑗 ) + 𝜀
𝑀 𝑗=1 𝑖,𝑗

where 𝛽~𝑁(0,1) is a step control parameter obeying a normally distributed random number. 𝑀 is the
number of targets. 𝐾 ∈ [−1,1] is a random number. 𝜀 is a minima avoiding 0 in the denominator.
𝑡
𝑋𝑟𝑓 is any individual in the follower subpopulation except for individual 𝑖.𝑓𝑖,𝑗 is the jth objective function
value of the vigilant 𝑋𝑖𝑡 ’s jth objective function value. 𝑓𝑟𝑓,𝑗 is the jth objective function value of the
𝑡
follower 𝑋𝑟𝑓 . Because all the vigilantes are selected from the discoverer subpopulation, each alarm is
issued from the current Pareto optimal position, when the discoverer subpopulation has fewer individuals,
the population is not widely distributed on the current PF, and there may be other safe positions in the
vicinity of the current position, so at this time, the vigilantes exchange information with the discoverers
and perform local search to find potential safe positions on the current PF location. When there are more
individuals in the subpopulation of the discoverer, the population has already carried out a certain degree
of extensive search on the current PF, and there may be no potential safe location on the current PF, so
at this time, the vigilante will randomly select followers to exchange information and carry out a global
exploration to find a new potential PF.

3.3.4. Diversity search stage

When the populations all converge to the PF, the original population partitioning strategy of SSA
needs to calculate the congestion distance of individuals, which has a high computational complexity. At
the same time, when the populations are all on the PF, it is more necessary for the populations to have a
wide distribution on the PF to construct the shape of the PF, and a strong global search ability, so as to
be as close as possible to the real PF, but the original search strategy of SSA has a poor performance of
the diversity and the ability of global search, which is difficult to satisfy the demand. The adaptive
population partitioning strategy and the randomized bootstrap search strategy also face the same dilemma,
with a general global search ability that easily falls into the local optimal situation. However, the multi-
population search concept of SSA shows excellent search performance. Therefore, this paper proposes a
dynamic population delineation strategy and a multi-population search strategy based on the multi-
population concept of SSA and the large-scale exploration technique, and the details of these two
strategies are described below.

(1) Dynamic multi-population search strategy

In the original SSA, the risk value 𝑅 represents the population's risk assessment of the environment,
and the risk threshold 𝑆𝑇 represents the population's risk tolerance. The dynamic change of 𝑅 can
constantly adjust the search direction of population, thus avoiding the algorithm falling into a local
optimal.
The dynamic population dividing strategy is shown in Eq.11:
𝑆𝑢𝑏𝑃𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 = 𝑃𝑜𝑝/2
{ 𝑆𝑢𝑏𝑃𝑜𝑝𝑓𝑜𝑙𝑙𝑜𝑤𝑒𝑟 = 𝑃𝑜𝑝/4 𝑖𝑓 𝑅 < 𝑆𝑇
𝑆𝑢𝑏𝑃𝑜𝑝𝑣𝑖𝑔𝑖𝑙𝑎𝑛𝑡𝑒 = 𝑃𝑜𝑝/4

(11)
𝑆𝑢𝑏𝑃𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 = 𝑃𝑜𝑝/4
{ 𝑆𝑢𝑏𝑃𝑜𝑝𝑓𝑜𝑙𝑙𝑜𝑤𝑒𝑟 = 𝑃𝑜𝑝/4 𝑖𝑓 𝑅 ≥ 𝑆𝑇
𝑆𝑢𝑏𝑃𝑜𝑝𝑣𝑖𝑔𝑖𝑙𝑎𝑛𝑡𝑒 = 𝑃𝑜𝑝/2

where 𝑆𝑢𝑏𝑃𝑜𝑝𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟𝑒𝑟 is the discoverer subpopulation size, 𝑆𝑢𝑏𝑃𝑜𝑝𝑓𝑜𝑙𝑙𝑜𝑤𝑒𝑟 is the follower

subpopulation size, 𝑆𝑢𝑏𝑃𝑜𝑝𝑣𝑖𝑔𝑖𝑙𝑎𝑛𝑡𝑒 is the vigilante subpopulation size, n is the population size. The
discoverer subpopulation performs a local exploitation, the vigilant subpopulation performs a global
exploration, and the follower subpopulation learns the search information of the other two subpopulations.
Therefore, when 𝑅 < 𝑆𝑇, i.e., when the population is currently in a more secure position, the discoverer
subpopulation expands and the population performs a local exploitation to increase the diversity of the
population at the local level. When 𝑅 ≥ 𝑆𝑇, i.e., the current position of the population is no longer safe,
the vigilante subpopulation expands and the population mainly performs a global exploration for
potentially optimal positions to avoid falling into a local optimal and to improve the global diversity of
the population. Dynamic changes in subpopulation size change the dominant search direction of the
population, leading to multi-directional search that allows full exploration of large-scale decision spaces.
However, 𝑅 in the original SSA obeys a uniform distribution, which is difficult to satisfy the
randomness of dynamic changes. Therefore, this paper also applies Singer mapping on 𝑅 to generate a
set of chaotic sequences to ensure the randomness and traversal of 𝑅, so as to ensure the randomness of
the dynamic dividing of the population. Second, the 𝑆𝑇 in the original SSA is a fixed preset value, which
does not fully take into account the different needs of the algorithm's early and late search stages. In the
early search stage, there is still a large amount of potential space unexplored, so global exploration should
be the main focus at this time; while in the late optimization stage, most of the space has been explored,
and local exploitation should be the main focus at this time.
 Therefore, the 𝑆𝑇 in this paper is adaptively adjusted according to Eq. 12:

𝑆𝑇𝑚𝑎𝑥 + 2𝑆𝑇𝑚𝑖𝑛 𝑆𝑇𝑚𝑎𝑥 − 𝑆𝑇𝑚𝑖𝑛 𝑖𝑡𝑒𝑟

𝑆𝑇 = + ∗ tanh (−5 + 10 ∗ ) (12)
3 3 𝑖𝑡𝑒𝑟𝑚𝑎𝑥

where 𝑆𝑇𝑚𝑎𝑥 is the maximum value of 𝑆𝑇, 𝑆𝑇𝑚𝑖𝑛 is the minimum value of 𝑆𝑇, 𝑖𝑡𝑒𝑟 is the current
iteration number. Error! Reference source not found. shows the change of 𝑆𝑇 when 𝑆𝑇𝑚𝑎𝑥 = 1 ,
𝑆𝑇𝑚𝑖𝑛 = 0.5, 𝑖𝑡𝑒𝑟𝑚𝑎𝑥 = 1000. In the early search stage, we keep 𝑆𝑇 at a low value to increase the
frequency of dynamic dividing of the population, so that the main search direction of the population is
constantly changing to full local exploit and global explore. As the search continues, 𝑆𝑇 will gradually
increase to allow the discoverer subpopulation to gradually become dominant. In the later search stage,
𝑆𝑇 is kept at a high level so that the discoverer subpopulation becomes the dominant subpopulation of
the population, which results in the entire population being dominated by local exploitation in the later
search stage.

Fig.7 ST Change

(3) Multi-population search strategy

In order to fully explore the large-scale decision space, avoid falling into the local optimum, and
find potential PFs, this paper proposes a multi-subgroup search strategy based on the multi-population
concept of SSA and large-scale exploration technique, in which the search direction is dominated by
multiple searches and dynamically changes to fully explore the local space and the global space. The
discoverer subgroup adopts the improved sequential intersection (IPX) operator to dominate the local
exploration; the vigilant subgroup adopts the permutation-based reverse learning (PRL) operator to
dominate the global exploration; and the follower subgroup adopts the dynamic k-opt operator for
comprehensive exploration.
The PBX operator is a commonly used permutation crossover operator, and the specific execution
process is shown in Figure 8. First, two parents𝑥 1 = (𝑥11 , 𝑥21 , ⋯ , 𝑥𝐷1 )，𝑥 2 = (𝑥12 , 𝑥22 , ⋯ , 𝑥𝐷2 ) are randomly
selected, and several genes at different positions in 𝑥 1 are randomly selected and copied to the same
position in the child 𝑐1 , and then the genes missing in 𝑐1 are filled sequentially from 𝑥 2 in the original
order; the process of generating the child 𝑐 2 is The process of generating the offspring 𝑐 2 is similar,
first the genes not copied to 𝑐1 in 𝑥 2 are copied to the same position in, and then the missing genes in
𝑐 2 are filled in from 𝑥 1 in the original order; the number and position of crossover points of the PBX
operator are very flexible, and thus it has a strong ability of local search in sorting optimization. However,
the number of selection of cross-points of the PBX operator is fixed, which affects the search ability of
the PBX operator in different periods of the search stage. So, in this paper, an improvement is made to
address this point by dynamically varying the number of cross sites to make the PBX operator better able
to search in a large decision space. The number of cross sites in the PBX operator is adaptively varied
according to Equation 13:

𝑖𝑡𝑒𝑟
𝑛𝐼𝑃𝑋 = ⌊𝐷 ∙ (tanh (5 − 10 ∗ ) + 3)/8⌋ (13)
𝑖𝑡𝑒𝑟𝑚𝑎𝑥

where 𝑛𝐼𝑃𝑋 is the number of intersections, 𝐷 is the decision vector dimension, 𝑖𝑡𝑒𝑟 is the current
iteration number, 〖𝑖𝑡𝑒𝑟𝑚𝑎𝑥 is the maximum iteration number, and the final value is rounded down. The
number of intersections is maintained at 1/2 of the decision vector dimension in the early stage, and
gradually decreases to 1/4 of the decision vector dimension as the population continues to iterate.

Fig.8 process of positional crossover

The PRL used by the vigilant is shown in Eq. 14:

𝑐 =𝐷+1−𝑥 (14)

where 𝑥 = (𝑥1 , 𝑥2 , ⋯ , 𝑥𝐷 ) is the parent, 𝑐 is the child, and 𝐷 is the dimension of the decision vector.
The sorting-based reverse learning operator has a strong global search capability that changes the
positions of elements throughout the sequence, facilitating exploration of potentially optimal positions.
The RL operator is computationally simple, but changes rapidly, allowing fast search over a large area.
In single-objective optimization problems, convergence of the PRL operator to the population is
destructive and can easily produce invalid searches, and constraints are usually imposed to reduce the
destruction of convergence of the RL operator to the population. The usual method of constraint is to
reduce the number of individuals that perform backward learning according to the relevant conditions.
However, in this paper, the information acquired by the vigilant is referentially learned by the follower
for searching, so the PRL operator is only constrained by the dynamic population partitioning strategy in
this paper. Compared with other search operators, the PRL operator performs better in diversity and is
more computationally efficient, allowing for broader and faster search. And PRL only needs to deal with
diversity in this paper, which reduces its impact on convergence.
In this paper, a k-opt operator for dynamic selection is proposed based on the opt algorithm. opt
algorithm [27] is a kind of crossover operator commonly used in sequence optimization, which can be
divided into 2-opt, 3-opt, 4-opt algorithms and so on, and these opt algorithms are collectively known as
k-opt algorithms. k stands for the number of edges that need to be exchanged, and it can be taken as an
arbitrary integer greater than 2, but the larger k is, the more complicated the calculation is. k represents
the number of edges to be exchanged, which can be any integer greater than 2. Based on the
comprehensive consideration of efficiency and optimization effect, this paper chooses 2-opt and 3-opt
crossover operators for sequence optimization. 2-opt algorithm is shown in Fig. 9(a). First select two
non-adjacent edges, delete these two edges, and then reconnect the nodes, and reconnect to ensure that
there exists a pathway, so there is only one connection for 2-opt. Fig. 9 (b) shows the coded move process
of the 2-opt algorithm, which first selects two intersections and then reverses the order of the nodes
within the intersection sites. The process of the 3-opt algorithm is shown in Fig. 9 (c). Three non-adjacent
edges are first selected and then the same de-connection process as in 2-opt is performed, also ensuring
the existence of pathways. However, there are 7 different connection methods in 3-opt, and in the
consideration of computational efficiency, only one of the connection methods is selected in this paper
to complete the moving process. The encoded moving process of the connection method chosen in this
paper is shown in Fig. 9 (d). Firstly, three crossing loci are selected, and then the node order between two
neighboring loci is reversed. Based on the 2-opt operator and 3-opt operator as well as the movement
characteristics of SSA described in the previous section, a dynamic k-opt operator is proposed in this
paper as shown in Eq.15:

𝑓2−𝑜𝑝𝑡 (𝑥𝑖𝑡 ) 𝑖𝑓 𝑅 < 𝑆𝑇

𝑥𝑖𝑡+1 = { (15)
𝑓3−𝑜𝑝𝑡 (𝑥𝑖𝑡 ) 𝑖𝑓 𝑅 ≥ 𝑆𝑇

When 𝑅 < 𝑆𝑇, the cross-generated offspring are moved by the 2-opt operator; when 𝑅 ≥ 𝑆𝑇, the cross-
generated offspring are moved by the 3-opt operator. 2-opt operator is a kind of small-step jumping,
which is suitable for local search; 3-opt is a kind of large-step jumping, which is able to avoid falling
into the local optimal case and is suitable for global exploration.

Fig. 9 2-opt and 3-opt cross movements

3.3.5. Environmental selection strategy

In this paper, we use a reference point environmental selection strategy similar to NSGA-III[29]. In
many-objective space, this method has lower computational complexity and stronger selection pressure
compared to the environment selection strategy by the degree of crowding. First, we perform a fast non-
dominated sorting of the mixed population of parents and children into different Pareto layers 𝐹𝑖 (𝑖 =
1,2 … , 𝑛). If |𝐹1 | = 𝑛, the individuals in 𝐹1 are placed in 𝑆𝑛𝑒𝑥𝑡 and go directly to the next iteration. If
|𝐹1 | > 𝑛, the reference point selection strategy is applied in𝐹1 and NP individuals are selected to be put
into 𝑆𝑛𝑒𝑥𝑡 . if |𝐹1 | < 𝑛, the individuals in each layer are put into 𝑆𝑛𝑒𝑥𝑡 in order, until ⋃𝑙𝑖=1 𝐹𝑖 ≥ 𝑁𝑃.
And then |𝐹𝑙 | − |⋃𝑙𝑖=1 𝐹𝑖 | + 𝑛 individuals are selected from 𝐹𝑙 into 𝑆𝑛𝑒𝑥𝑡 .
Since TS-SSA produces population with good convergence and diversity, it is not necessary to give too
much selection pressure in the environmental selection strategy to select the better offspring to ensure
the overall performance of the population.
The pseudo-code for TS-SSA is shown in Algorithm 1:
Algorithm 1 PTS-SSA
1: R=rand ();
2: while termination criterion not fulfilled do
3: R=chaosMapping(R);
4: ST= adaptionST ();
5: Subpopdiscoverer, Subpopfollower=NDSort (Pop);
6: if | Subpopdiscoverer | !=N then
7: Offspringdiscoverer =MOSSAdiscoverer (Subpopdiscoverer);
8: Offspringfollower =MOSSAfollower (Subpopfollower);
9: Subpopvigilante =randomSelection (Subpopdiscoverer);
10: Offspringvigilante =MOSSAvigilante (Subpopvigilante);
11: Offspring= Offspringdiscoverer + Offspringfollower + Offspringvigilante;
12: Offspring=decode (Offspring);
13: else
14: if R<ST then
15: Subpopdiscoverer=randomSelection (Pop, N/2);
16: Subpopfollower =randomSelection (Pop- Subpopdiscoverer, N/4);
17: Subpopvigilante =Pop- Subpopdiscoverer - Subpopfollower;
18: else
19: Subpopvigilante=randomSelection (Pop, N/2);
20: Subpopfollower =randomSelection (Pop- Subpopvigilante, N/4);
21: Subpopdiscoverer =Pop- Subpopvigilante - Subpopfollower;
22: end if
23: Offspringdiscoverer =IPX(Subpopdiscoverer);
24: Offspringvigilante =PRL(Subpopvigilante);
25: Offspringfollower =Dkopt(Subpopfollower);
26: Offspring= Offspringdiscoverer + Offspringfollower + Offspringvigilante;
27: end if
28: OffspringObj=calculateObj (Offspring);
29: Pop=EnvironmentalSelection (Pop, Offspring);
30: end while

3.3.6. Time complexity analysis

The time complexity of PTS-SSA is determined by the sort-based decoding method, the adaptive
population dividing strategy and the random bootstrap search strategy in the first stage, the dynamic
population dividing strategy and the multi-population search strategy in the second stage, and the
reference point environment selection strategy. In the following analysis, 𝑀 represents the number of
objectives and 𝑁 represents the population size. The time complexity of the sort-based decoding method
is 𝑂(𝑁).In the first stage, the adaptive population dividing strategy has to perform the nondominated
sorting on the population. The nondominated sorting algorithm used in this paper is Efficient
Nondominated Sorting Algorithm (ENS)[28], the best time complexity of ENS is 𝑂(𝑀𝑁 log 𝑁), the
worst time complexity is 𝑂(𝑀𝑁 2 ). Thus, the best time complexity of the adaptive population dividing
strategy is 𝑂(𝑀𝑁 log 𝑁), and the worst time complexity is 𝑂(𝑀𝑁 2 ). The random bootstrap search
strategy randomly selects individuals for position update, so the time complexity is 𝑂(𝑁). The best time
complexity of the first stage is 𝑂(𝑀𝑁 log 𝑁) and the worst time complexity is 𝑂(𝑀𝑁 2 ). In the second
stage, the dynamic population dividing strategy involves randomly assigning individuals, so the time
complexity is 𝑂(𝑁) . The multi-population search strategy involves updating the positions of all
individuals, and the time complexity is 𝑂(𝑁). Therefore, the time complexity of the second stage is
𝑂(𝑁) . ENS is used in the reference point environment selection strategy to achieve non-dominated
sorting, so the best time complexity is 𝑂(𝑀𝑁 log 𝑁) and the worst time complexity is 𝑂(𝑀𝑁 2 ). In
summary, the overall best time complexity of TS-SSA is 𝑂(𝑀𝑁 log 𝑁) and the worst time complexity
is 𝑂(𝑀𝑁 2 ).

3.4. Automatic generation of test data

Test cases are generated by combining test scenarios and test data. This section describes the test
data generation process in detail, and finally the test cases are generated by combining the generated test
data and test scenarios. It is difficult to generate test data directly from the model, because the model is
complex, varied, and not generalized. However, the decision nodes of the test scenarios generated based
on the model have decision conditions attached to their decision edges, according to which the decision
conditions can be inverted to introduce the constraints of the input data corresponding to the current test
scenario, and then the test data are automatically generated based on the constraints, and finally the test
data are combined with the test scenarios to generate the test cases.

3.4.1. Test data design

Test data includes input data and expected outputs. The generation of input data must be determined
based on the input data constraints of the test scenario. In a model, there are base domains of input data,
and all input data are generated from these base domains. Therefore, in this paper, constraints are first
generated for all base domains by the equivalence class partitioning method, and then the input data are
automatically generated by combining with the boundary value analysis method. The expected output is
usually given by the tester by analyzing the documentation or code.

3.4.2. Model-Based decision backpropagation of test scenarios for test data generation

Due to the need to extract test data from the model, this paper proposes a model-based decision
backpropagation method for test scenarios. The flow of the decision backpropagation method is as
follows: first, the constraints of all basic domains of the model are generated by the equivalence class
division method; then, the decision conditions attached to the decision edges of all decision nodes are
extracted from the corresponding test scenarios; then, the constraints of the basic domains corresponding
to the test scenarios are backpropagated according to these decision conditions; then, the test data are
automatically generated by the constraints; finally, the test data and the test scenarios are combined to
generate test cases. Consider the activity diagram of the ATM model in Figure 2 as an example. The basic
domains present in the model and their constraints are shown in Table 7. It consists of seven base domains
with multiple constraints and two base domains with only one constraint. In the following, the process
of generating test data using the Test Scenario Decision Backpropagation method will be specifically
described using the test scenarios listed in Table 2. Taking TS4 as an example, Table 8 describes the base
domains, decision conditions, and constraints for backpropagation, as well as the generation of input data
and a test case to satisfy TS4 that TS4 has gone through.

Table 7 Constraints on the division of base domains by equivalence classes

Cash
Segmentation Account Business Cash Out
Card PIN Business
Type Verification Type Amount
Type
Cash out not
Password
Valid type Valid user Cash business Cash out greater than
match
balance
The number
of digits of
the password
is correct but
does not
match Transfer Cash out greater
Invalid type Invalid user Cash in
Too many business than balance
password
digits
Too few
password
digits
Amount of Amount of
Segmentation Transaction Amount of transfer to current
transfer cash
type selection account
Transaction deposited
Transfer
amount is not Continue
Valid type Cash amount Amount credited
greater than transaction
balance
Amount
transferred is Exit
Invalid type \ \
greater than transaction
the balance

Table 8 TS4's base domain, decision conditions, constraints, and input data
Account Business Cash Out Transaction
Card PIN
Verification Type Amount selection
Insufficient
Decision Password
Valid user Cash business balance Exit Exit transaction
condition correct
transaction
Cash out
Password
Constraints Valid user Cash business greater than Exit transaction
match
balance
Input data 123456 Valid user Cash business 101 Exit transaction
Test Case TC4: Password: 123456, Verify User: Valid User, Select Business: Cash Business, Cash
Out: 200, Transaction Selection: Exit Transaction. Expected Result: Account Balance 100
[Link] results and discussions

In this section, the performance of PTS-SSA will be evaluated through experiments. The
experiments are divided into two parts: the first part is the effectiveness experiment of PTS-SSA to
evaluate the performance of PTS-SSA priority ranking; the second part is the comparison experiment of
PTS-SSA with other TCP algorithms.

4.1. Experimental design

4.1.1．Experimental environment configuration

The experimental environment configuration is shown in Table 9.

Table 9 Experimental environment configuration
Configuration Name Configuration Content

Processor Intel(R) Core (TM) i7-11800 CPU @ 2.30GHz

RAM 32 GB
Operating System 64-bit Windows 10
Programming Language Matlab

Programming tools MATLAB_R2023a, PlatEMO 4.2[30]

Table 10 Fault coverage matrix for some test scenarios of ATM activity diagrams

TS1 TS2 TS3 TS4 TS5 TS6 TS7 TS8

F1 * * * * * * * *
F2 *
F3 * * * * * *
F4 * *

F5 * * * *
F6 * *

F7 * *
F8 * *
F9 *
F10 *
F11 *

F12 *
F13 * * * * * *

F14 *
F15 *
4.1.2. Experimental UML activity diagram models

The main goal of TCP is to improve the fault detection capability of the test suite in the shortest
execution time, so the first step is to obtain the fault coverage matrix of the model. In this paper, we
follow the model-based mutation operator proposed by Shin [33] to seed the model with faults, generate
mutants, and thus obtain the fault coverage matrix. Based on the characteristics of UML activity diagrams,
the decision mutation operator and the concurrent mutation operator are selected in this paper to perform
fault seeding. The decision mutation operator mainly performs fault seeding for missing decision
conditions, and the concurrent mutation operator mainly performs fault seeding for changing the
execution order of activities on concurrent threads. Taking the ATM activity graph in Figure 2 as an
example, a total of 15 mutants were generated, and the fault coverage matrices generated with some of
the test scenarios of the ATM activity graph shown in Table 2 are shown in Table 10. The models used
for the experiments include ID registration model [32], ATM model [20], make call model [33], logistics
management system model [34], and smart wrench system model [35]. The specific information of the
experimental models is shown in Table 11.
Table 11 Experimental model specific information
Number Number of Number of Number of Number Number of
Model Name of Decision Concurrent loop of Test
Nodes Nodes Modules Modules Faults Scenarios
ID Registration 37 11 1 1 23 32
ATM 30 7 1 2 15 31

Make Call 39 8 1 2 17 21
Logistics
Management 65 7 4 2 18 29
System
Smart Wrench
51 8 2 3 18 48
System

4.1.3. Evaluation indicators

(1) Cost-aware mean failure detection rate based on model improvement

Cost cognizant Average of the Percentage of Faults Detection (𝐴𝑃𝐹𝐷𝐶 ) is a commonly used metric
to evaluate the fault coverage performance of a method in TCP research. The calculation of 𝐴𝑃𝐹𝐷𝐶 is
shown in Eq.15:

1
∑𝑚 𝐹 𝑛
𝑖=1 (𝑠𝑖 ∙ (∑𝑗=𝑇𝑆𝑖 𝑡𝑗 − 2 𝑡 𝑇𝑆𝑖 ))
(15)
𝐴𝑃𝐹𝐷𝐶 =
∑𝑛𝑗=1 𝑡𝑗 ∙ ∑𝑚 𝐹
𝑖=1 𝑠𝑖

where 𝑛 denotes the number of test scenarios, 𝑚𝐹 denotes the number of faults, 𝑇𝑆𝑖 denotes the
sequence number of test scenarios covering the ith fault, 𝑠𝑖 denotes the importance of the ith fault, and
𝑡𝑗 denotes the execution time of the jth test case. The higher the value of 𝐴𝑃𝐹𝐷𝐶 , the stronger the fault
detection ability of the sequence. When measuring the fault detection ability of a sequence, 𝐴𝑃𝐹𝐷𝐶 not
only considers the fast coverage of faults, but also the overall execution time and fault priority, so 𝐴𝑃𝐹𝐷𝐶
can evaluate the comprehensive performance of TCP algorithm's prioritization in a more comprehensive
way. In this paper, we prioritize the test scenarios, so the execution time is replaced by the number of
nodes in the test scenarios, and at the same time, we set the same degree of importance of each fault, and
the calculation of the adjusted 𝐴𝑃𝐹𝐷𝐶 is shown in Eq.16:

1
∑𝑚 𝐹 𝑛
𝑖=1 (∑𝑗=𝑇𝑆𝑖 𝑛𝑜𝑑𝑒𝑗 − 2 𝑛𝑜𝑑𝑒𝑇𝑆𝑖 )
𝐴𝑃𝐹𝐷𝐶 = (16)
∑𝑛𝑗=1 𝑛𝑜𝑑𝑒𝑗 ∙ 𝑚𝐹

where 𝑛𝑜𝑑𝑒𝑗 is the number of nodes included in the jth test scenario.
(2) Hypervolume
Hypervolume (HV) measures the performance of the multi-objective optimization algorithm by
calculating the volume of the region enclosed by the PS and the reference point as in Eq.17:

|𝑃𝑆|

𝐻𝑉 = 𝛿 ⋃ 𝑣𝑖 (17)
𝑖=1

where 𝛿 is the Lebesgue measure, 𝑃𝑆 is the Pareto solution set, and 𝑣𝑖 is the hypervolume enclosed
by the ith solution and the reference point in PS. The higher the HV, the better the performance of the
[Link] calculation of HV does not require the real PF, so it is more suitable to measure the
performance of the multi-objective optimization algorithm in solving the real multi-objective problem,
and has better practicality. The prioritization problem in the test scenario of this paper is a multi-objective
problem with unknown real PF, which is better measured by the HV metric.

4.1.4. Comparison methods

To evaluate the prioritization capability of PTS-SSA, four TCP methods are selected for
comparative experiments in this paper. The methods are as follows:
(1) μCSA [12]: μCSA (Discrete Cuckoo Search Algorithm) discretizes the cuckoo search
algorithm by introducing an asexual genetic reproduction strategy to achieve the sorting operation on test
cases. It also enhances the search capability of the algorithm by mixing the cuckoo search algorithm with
the genetic algorithm to avoid falling into local optimality.
(2) TSPACO [10]: TSPACO (Test Scenarios Prioritization Ant Colony Optimization) Prioritizes
test scenarios by means of an improved Ant Colony algorithm.
(3) MOPSO [16]: MOPSO (Multi-objective Particle Swarm Algorithm) prioritizes test cases from
a multi-objective perspective of coverage and execution time.
(4) MO-SDC [17]: MO-SDC (Multi-objective Self-driving Cars) is based on NSGA-II and
prioritizes test scenarios from a multi-objective perspective of inter-sequence distance and cumulative
execution cost.
4.1.5. Parameter setting

The experimental parameters of the type are set as shown in Table 12. Since the heuristic algorithm
has randomness, for the sake of fairness, all methods using the heuristic algorithm are run independently
for 10 times and the average value is taken as the final result. The algorithm-related parameters are listed
in Table 13. The algorithm parameters are all in accordance with the recommended parameters given in
the relevant literature in order to obtain the comparative results with the optimal performance.

Table 12 Parameter settings for model experiments

Number of
Maximum number of evaluations of
Model name individuals in the
the objective function
population
ID Registration 100 100000
ATM 100 100000
Make Call 100 100000
Logistics Management
100 100000
System
Smart Wrench System 100 100000

Table 13 Experimental parameters of the algorithm

Parameter Applicable
Parameter Parameter Description
Value Algorithm
𝑝𝑐 Probability of crossover 0.9 ALL
𝑝𝑚 Probability of variation 1/D ALL
𝜂𝑐 Crossover Distribution Index 20 ALL
𝜂𝑚 Variational Distribution Index 20 ALL
𝑝𝑠 Exchange probability 0.4 μCSA
𝜏 Pheromone concentration 1.0 TSPACO
𝜌 Evaporation rate 0.1 TSPACO
𝜂 Edge heuristic factor 2.0 TSPACO
Pheromone concentration control
𝛼 1.0 TSPACO
parameter
𝛽 Edge-inspired factor control parameter 1.0 TSPACO
𝜇 Singer chaotic mapping hyperparameters 1 PTS-SSA

4.2. Experimental results and analysis

4.2.1. PTS-SSA validity experiment

Fig.10 show the comparison results of 𝐴𝑃𝐹𝐷𝐶 before and after the five experimental models are
sorted by PTS-SSA, and the 𝐴𝑃𝐹𝐷𝐶 values of PTS-SSA are obtained by averaging 10 independent runs.
The results show that PTS-SSA can significantly improve the 𝐴𝑃𝐹𝐷𝐶 value of the test suite. Before
prioritization, the 𝐴𝑃𝐹𝐷𝐶 values of all five test suites are low because the test sequences are obtained
by random arrangement, so the fault detection ability is poor. After prioritizing the test suites of the
models by PTS-SSA, the 𝐴𝑃𝐹𝐷𝐶 values are significantly improved, 1.15 times in ID registration model,
0.69 times in ATM model, 0.84 times in Make Call model, 0.49 times in logistics management system
model, and 0.84 times in smart wrench system model. 0.84 times. Unordered test suites have poor fault
detection capabilities and important test scenarios are often not prioritized for execution, which reduces
the efficiency of testing. The prioritization technique enables the important test scenarios to be executed
first. At the same time, in this paper, we prioritize test scenarios from a multi-objective perspective, so
we can take into account multiple optimization objectives in the optimization process, such as execution
time and coverage, etc., so that we can generate test scenarios with higher comprehensive fault detection
performance, and further improve the testing efficiency. Especially in the case of a large number of test
scenarios, the prioritization can filter out the test scenarios with stronger fault detection capability, and
allow the test scenarios with stronger fault detection capability to be executed first, so as to avoid wasting
limited test resources on the test scenarios with weaker fault detection capability, thus reducing the test
cost, improving the utilization rate of the test resources, and thus improving the test efficiency.
Table 14 shows the 𝐴𝑃𝐹𝐷𝐶 values for different combinations of objectives. From the results, it
can be seen that the presence of APNC optimization goals improves the 𝐴𝑃𝐹𝐷𝐶 value of the test suite
to some extent. Only in the make-call model with fewer test scenarios, the 𝐴𝑃𝐹𝐷𝐶 value of the 3-
objective combination is the same as the 𝐴𝑃𝐹𝐷𝐶 value of the 4-objective combination. In the intelligent
wrench system with more test scenarios, the 𝐴𝑃𝐹𝐷𝐶 values of the two combinations have a certain gap.
This indicates that when the decision space is large and the test cost is considered, the execution time is
a more important optimization objective, which affects the comprehensive fault detection capability of
the prioritized test suite to a certain extent.

Table 14 𝐴𝑃𝐹𝐷𝐶 values for different combinations of objective functions

Objective functions
Model name 𝑨𝑷𝑭𝑫𝑪 (%)
combination
APDC+APCC+APLC+APNC 95.12
ID Registration
APDC+APCC+APLC 94.18
APDC+APCC+APLC+APNC 98.89
ATM
APDC+APCC+APLC 97.56
APDC+APCC+APLC+APNC 95.83
Make Call
APDC+APCC+APLC 95.83
APDC+APCC+APLC+APNC 97.85
Logistics Management System
APDC+APCC+APLC 97.21
Smart Wrench System APDC+APCC+APLC+APNC 96.17
APDC+APCC+APLC 94.08
In summary, PTS-SSA can significantly improve the comprehensive fault detection capability of
the test suite and maintain good optimization performance when the test scenarios are large in size. The
APNC metric in this paper can improve the 𝐴𝑃𝐹𝐷𝐶 value of test scenario prioritization to a certain
extent, while the APNC metric is a substitute for the actual test case execution time, which proves that
taking the test case execution time as an optimization goal is necessary to improve the comprehensive
fault detection capability of the test suite after TCP.
 Fig. 10 Comparison between before and after prioritization of 𝐴𝑃𝐹𝐷𝐶

4.2.2. PTS-SSA performance comparison experiment

This section evaluates the performance difference between PTS-SSA and other TCP algorithms
through performance comparison experiments between PTS-SSA and μCSA, TSPACO, MOPSO and
MO-SDC on five models. Tables 15 show the results of each method through 10 independent runs, taking
the average of the optimal values in the final population of each run. The results show that PTS-SSA
outperforms the other four algorithms in terms of the value of 𝐴𝑃𝐹𝐷𝐶 .
In order to observe more intuitively the ability of each algorithm to prioritize the test scenarios,
this paper calculates the 𝐴𝑃𝐹𝐷𝐶 value of the final population of each algorithm in each run, and
summarizes the results of 10 times together and draws its box line diagram. The specific results are
shown in Fig. 11.
In summary, PTS-SSA has a significant performance advantage over μCSA algorithm, TSPACO,
MOPSO algorithm, and MO-SDC algorithm in prioritizing test scenarios, and also maintains strong
convergence in complex models. As the model complexity increases, the multi-objective optimization
algorithm significantly outperforms the single-objective optimization algorithm, and the multi-objective
optimization algorithm is able to maintain better optimization performance and convergence in the
complex search space. The single-objective optimization algorithm, on the other hand, leads to a decrease
in convergence and a decrease in optimization performance as the complexity of the search space
increases.

Table 15 The 𝐴𝑃𝐹𝐷𝐶 value of the method on 5 models

Model name μCSA TSPACO MOPSO MO-SDC PTS-SSA

ID Registration 90.18 84.65 91.06 90.37 95.12

ATM 91.67 84.19 97.59 94.13 98.89
Make Call 90.27 87.56 90.67 91.58 95.83
Logistics
Management 91.46 85.47 93.82 94.57 97.85
System
Smart Wrench
85.53 80.17 92.77 89.74 96.17
System

(a) (b)

(c) (d)

(e)
Fig. 11 Boxplot of 𝐴𝑃𝐹𝐷𝐶 values for the comparison algorithm on 5 models
5. Conclusions and future works

In this paper, prioritization of test cases is accomplished from two aspects: prioritization of test
scenarios and generation of test data based on test scenarios. Firstly, in terms of prioritization of test
scenarios, this paper proposes a PTS-SSA. The PTS-SSA is divided into two phases of optimization,
which manages the convergence and diversity of populations respectively. The convergence search phase
is carried out by an adaptive population partitioning strategy and a randomized bootstrap search strategy;
the diversity search phase is carried out by a dynamic population partitioning strategy and a multi-
subpopulation search strategy. Both phases are adaptively selected by the distribution characteristics of
the populations on the PF. PTS-SSA also introduces chaotic population initialization to improve the
search efficiency of the algorithm at the early stage. An ordering-based decoding method is also
introduced to map sequential solutions to ranked solutions. In the multisubpopulation search strategy,
three improved sorted crossover operators are proposed. The first one is an improved position-based
crossover operator, which balances the search ability of the PBX operator at early and late stages by
dynamically changing the number of crossover points. A sorting improvement is made to the reverse
learning operator so that it can handle the sorting problem. Dynamic k-opt operators are proposed to
dynamically select 2-opt and 3-opt operators for searching based on sparrow population characteristics.
Then based on the UML activity diagram, four objective functions for prioritizing test scenarios, namely,
average decision coverage, average concurrency coverage, average loop coverage and average node
coverage, are designed to comprehensively evaluate the fault detection capability of the test scenario
sequence. Finally, this paper proposes a decision backpropagation method to generate test data from test
scenarios, and test data and test scenarios are combined to obtain test cases, so as to complete the
prioritization of test cases.
In order to validate the performance of the proposed method, five different models with four
comparative algorithms are selected for experiments. The experiments are divided into two parts: the
first part is the effectiveness experiment of PTS-SSA. The experimental results show that PTS-SSA has
a better prioritization ability, compared with the sequence of unsorted test scenarios, after sorting by
PTS-SSA, the value of 𝐴𝑃𝐹𝐷𝐶 improves by 1.15 times in the ID registration model, 0.69 times in the
ATM model, 0.84 times in the Make Call model, 0.49 times in the logistics management system model,
and 0.49 times in the smart wrench system model. 0.49 times, and 0.84 times on the Smart Wrench
System model. The second part is the performance comparison experiment between PTS-SSA and the
other four algorithms. The experimental results show that the multi-objective TCP method is better than
the single-objective TCP method as a whole, which proves the necessity of solving the TCP problem
from a multi-objective perspective. Meanwhile, PTS-SSA is significantly better than the other two multi-
objective TCP methods, especially on complex models, and is better able to search in large-scale decision
spaces and avoid falling into local optimal.
Although the method proposed in this paper achieves good results on TCP, there are still some
aspects that can be improved: first, the sorting-based decoding method still loses some information.
Therefore, in future work, we will make further improvements to the sparrow alignment discretization
mapping to further reduce the information loss. First, the high-dimensional multi-objective improvement
method proposed in this paper for biological population intelligence algorithms has only been applied to
the sparrow search algorithm for the time being. Similar improvements to other biological population
intelligence algorithms will be considered in future work to design a generalized improvement method.
CRediT authorship contribution statement
Xiaozhi Du: Conceptualization, Methodology, Writing – original draft, Editing, Supervision. Kai
Chen: Investigation, Methodology, Writing – original draft, Validation. Zongbin Qiao: Methodology,
Software, Writing – review & editing, Validation.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships
that could have appeared to influence the work reported in this paper.
Data Availability
Data will be made available on request.
Acknowledgments
The work described in this paper is partially supported by the Chinese National Natural Science
Foundation (grant number 12275208).
References

[1] GONçALVES E M N, MACHADO R A, RODRIGUES B C, et al. CPN4M: Testing Multi-

Agent Systems under Organizational Model Moise+ Using Colored Petri Nets [J]. Applied
Sciences, 2022, 12(12):
[2] shu Z, Yan G. IoTInfer: Automated Blackbox Fuzz Testing of IoT Network Protocols Guided by
Finite State Machine Inference [J]. IEEE Internet of Things Journal, 2022, 9(22): 22737-51.
[3] Rocha M, Simao A, Sousa T. Model-based test case generation from UML sequence diagrams
using extended finite state machines [J]. Software Quality Journal, 2021, 29(3): 597-627.
[4] Ahmad. T, Iqbal. J, Ashraf. D, et al. Model-based testing using UML activity diagrams: A
systematic mapping study [J]. Computer Science Review, 2019, 33(98-112.
[5] Sypsas A, Kalles D. Using UML Activity Diagram for Adapting Experiments under a Virtual
Laboratory Environment[C]//In 24th Pan-Hellenic Conference on Informatics (PCI 2020).
Association for Computing Machinery, 2020:27–30.
[6] Vedpal, Tanwar H, Chauhan N, et al. Test case prioritization using a Hybrid Chaotic Flower-fruit
fly optimization algorithm with multiple objectives [J]. Multimedia Tools and Applications, 2023.
[7] Mohd-Shafie M L, Wan-Kadir W M N, Khatibsyarbini M. Model-based test case prioritization
using selective and even-spread count-based methods with scrutinized ordering criterion [J]. PLoS
One, 2020, 15(2): e0229312.
[8] Bhuyan P, Ray A, Das M. Test Scenario Prioritization Using UML Use Case and Activity Diagram
[C]// 2017 Computational Intelligence in Data Mining, 2017, 556:492-512.
[9] Meiliana, Dewi L C, Chandra A. Generation from UML activity diagram and sequence diagram by
using genetic algorithm[J]. ICIC Express Letters. 2019, 13(7):585-591.
[10] Panthi V, Tripathi A, Mohapatra D P. Software validation based on prioritization using concurrent
activity diagram [J]. International Journal of System Assurance Engineering and Management,
2022, 13(4): 1801-16.
[11] Khatibsyarbini, Muhammad, Isa, Mohd Adham, Jawawi, Dayang N. A., Hamed, Haza Nuzly
Abdull, Mohamed Suffian, Muhammad Dhiauddin, et al. Test Case Prioritization Using Firefly
Algorithm for Software Testing [J]. IEEE Access, 2019, 7:132360-132373.
[12] Bajaj A, Sangwan O P. Discrete cuckoo search algorithms for test case prioritization [J]. Applied
Soft Computing, 2021, 110.
[13] Xing Y, Wang X, Shen Q. Test case prioritization based on Artificial Fish School Algorithm [J].
Computer Communications, 2021, 180:295-302.
[14] Tulasiraman M, Vivekanandan N, Kalimuthu V. Multi-objective Test Case Prioritization Using
Improved Pareto-Optimal Clonal Selection Algorithm [J]. 3D Research, 2018, 9(3).
[15] Arrieta A, Wang S, Markiegi U, Sagardui G, Etxeberria L. Employing Multi-Objective Search to
 Enhance Reactive Test Case Generation and Prioritization for Testing Industrial Cyber-Physical
Systems [J]. IEEE Transactions on Industrial Informatics, 2018, 14(3): 1055-66.
[16] Nazir M, Mehmood A, Aslam W, Park Y.W., Choi G. S., Ashraf I. A Multi-Goal Particle Swarm
Optimizer for Test Case Prioritization [J]. IEEE Access, 2023, 11:90683-97.
[17] Birchler C, Khatiri S, Derakhshanfar P, Panichella S, Panichella A. Single and Multi-objective Test
Cases Prioritization for Self-driving Cars in Virtual Environments [J]. ACM Transactions on
Software Engineering and Methodology, 2023, 32(2): 1-30.
[18] Vedpal, Tanwar H, Chauhan N, Khanna M. Test case prioritization using a Hybrid Chaotic Flower-
fruit fly optimization algorithm with multiple objectives [J]. Multimedia Tools and Applications,
2023.
[19] Al-Fedaghi S. Validation: Conceptual versus Activity Diagram Approaches[J]. International
Journal of Advanced Computer Science and Applications, 2021,12(6):287-297.
[20] Shirole M, Kumar R. Constrained permutation-based test scenario generation from concurrent
activity diagrams[J]. Innovations in Systems and Software Engineering, 2021, 17:345–353.
[21] Kundu D, Samanta D. A Novel Approach to Generate Test Cases from UML Activity Diagrams[J].
Journal of Object Technology, 2009, 8(3):65-83.
[22] Xue J, Shen B. A novel swarm intelligence optimization approach: sparrow search algorithm [J].
Systems Science & Control Engineering, 2020, 8(1): 22-34.
[23] Gao S, Wu R, Wang X, Liu JF, Li Q, Tang XL. EFR-CSTP: Encryption for face recognition based
on the chaos and semi-tensor product theory [J]. Information Sciences, 2023, 621: 766-81.
[24] Geng J, Sun X, Wang H, Bu XH, Liu DH, Li F, Zhao ZW. A modified adaptive sparrow search
algorithm based on chaotic reverse learning and spiral search for global optimization [J]. Neural
Computing and Applications, 2023.
[25] Tang A, Zhou H, Han T Xie L. A Chaos Sparrow Search Algorithm with Logarithmic Spiral and
Adaptive Step for Engineering Problems [J]. Computer Modeling in Engineering & Sciences, 2022,
130(1): 331-64.
[26] Zhang Z, Han Y. Discrete sparrow search algorithm for symmetric traveling salesman problem [J].
Applied Soft Computing, 2022, 118.
[27] Saji Y, Barkatou M. A discrete bat algorithm based on Lévy flights for Euclidean traveling
salesman problem [J]. Expert Systems with Applications, 2021, 172.
[28] XINGYI Z, YE T, RAN C, et al. An Efficient Approach to Nondominated Sorting for
Evolutionary Multiobjective Optimization [J]. IEEE Transactions on Evolutionary Computation,
2015, 19(2): 201-13.
[29] Deb K, Jain H. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-
Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints [J]. IEEE
Transactions on Evolutionary Computation, 2014, 18(4): 577-601.
[30] Tian Y, Cheng R, Zhang X, Jin, Y. PlatEMO: A MATLAB Platform for Evolutionary Multi-
 Objective Optimization [Educational Forum] [J]. IEEE Computational Intelligence Magazine,
2017, 12(4): 73-87.
[31] Shin KW, Lim DJ. Model-Based Test Case Prioritization Using an Alternating Variable Method
for Regression Testing of a UML-Based Model [J]. Applied Sciences, 2020, 10(21).
[32] Kundu D, Samanta D. A Novel Approach to Generate Test Cases from UML Activity Diagrams[J].
Journal of Object Technology, 2009, 8(3):65-83.
[33] Arora V, Singh M, Bhatia R. Orientation-based Ant colony algorithm for synthesizing the test
scenarios in UML activity diagram[J]. Information and Software Technology, 2020, 123:106292.
[34] Chen H, Jiang JM, Hong Z, Lin L. Decomposition of UML activity diagrams [J]. Software: Practice
and Experience, 2018, 48(1): 105-22.
[35] DU X Z, ZHANG J J, CHEN K, et al. DFS-KeyLevel: A Two-Layer Test Scenario Generation
Approach for UML Activity Diagram [J]. Journal of Electronic Testing-Theory and Applications,
2023, 39(1): 71-88.
Declaration of Interest Statement

Declaration of interests

☒The authors declare that they have no known competing financial interests or personal relationships
that could have appeared to influence the work reported in this paper.

☐The authors declare the following financial interests/personal relationships which may be considered
as potential competing interests: