离散粒子群优化在覆盖阵列生成中的应用
86 浏览量
更新于2024-07-15
收藏 2.01MB PDF 举报
"这篇研究论文探讨了使用离散粒子群优化(Discrete Particle Swarm Optimization, DPSO)技术来解决覆盖阵列生成问题。"
在软件工程领域，软件的行为往往受到多种因素的影响，组合测试(Combinatorial Testing, CT)旨在通过生成少量测试用例来发现这些因素及其交互作用可能导致的缺陷。覆盖阵列生成是CT中的一个核心问题，它是一个离散优化问题，目标是找出最小规模的测试用例集，以确保所有可能的因子组合至少出现一次。这有助于提高测试覆盖率，减少潜在的软件缺陷。
粒子群优化(PSO)是一种基于演化搜索的启发式算法，已被证明在生成具有竞争力规模的覆盖阵列方面非常有效。然而，当前的PSO方法在处理离散搜索空间时，通常直接将粒子的位置四舍五入到整数，这种方法可能无法充分利用PSO的潜力。此外，对于覆盖阵列生成问题，如何有效地设置PSO的参数也缺乏明确的指导原则。
论文中，作者扩展了一种现有的离散PSO方法——集合基PSO(Set-based PSO)，将其应用于覆盖阵列生成。为了改进这种方法，他们引入了两种辅助策略：粒子重新初始化和邻域探索。粒子重新初始化策略旨在避免算法陷入局部最优，通过在搜索过程中适时重置粒子的位置来保持种群多样性。邻域探索策略则利用了局部搜索能力，帮助粒子在搜索空间中更有效地移动，寻找更好的解决方案。
实验结果表明，提出的DPSO扩展方法在覆盖阵列生成任务上优于标准的离散PSO和其他比较算法，尤其是在处理大尺寸和高维度的覆盖阵列问题时。此外，论文还提供了关于如何为覆盖阵列生成问题设置PSO参数的见解，这对于实际应用和未来的研究具有重要的参考价值。
这篇论文为软件测试领域的组合测试提供了一个新的优化工具，通过改进的离散粒子群优化算法提高了覆盖阵列的生成效率，有助于更有效地揭露软件中的潜在缺陷。
578 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 19, NO. 4, AUGUST 2015
Algorithm 1 One-Test-at-a-Time Strategy
1: Input: SUT(n,
1
, ...,
n
) and covering strength t
2: Output: covering array TS
3: TS =∅
4: Construct S (all the t-way schemas to be covered) based
on n,
1
, ...,
n
and t
5: while S =∅ do
6: Generate a test case p with the highest fitness value
according to some heuristics
7: Add p to the test suite TS
8: Remove the t-way schemas covered by p from S
9: end while
10: return TS
Definition 4 (Fitness Function): Let TS be the generated
test set, and p be a test case. Then fitness(p) is the number of
uncovered t-way schemas in TS that are covered by p.
The fitness function can be formulated as
fitness(p) =|schema
t
({p}) − schema
t
(TS)| (1)
where schema
t
(TS) represents the set of all t-way schemas
covered by test set TS, and |·| stands for cardinality. When
all C
t
n
t-way schemas covered by p are not covered by TS,
the fitness function reaches the maximum value fitness(p) =
|schema
t
({p})|=C
t
n
.
For example, consider the 2-way covering array generation
of the e-commerce system shown in Table II. Suppose that
TS consists of test cases (0, 0, 0, 0, 0) and (0, 0, 1, 1, 1).
The fitness function computes the fitness value for a candi-
date test case p = (1, 0, 1, 2, 2) as follows: because p covers
ten 2-way schemas, namely schema
2
({p}) ={(1,0,–,–,–),
(1, –, 1, –, –,), (1, –, –, 2, –), (1, –, –, –, 2), (–, 0, 1, –, –),
(–,0,–,2,–),(–,0,–,–,2),(–,–,1,2,–),(–,–,1,–,2),
(–,–,–,2,2)}andTS onlycovers(–,0,1,–,–)inp,the
function returns fitness(p) =9.
C. PSO
PSO is a swarm-based evolutionary computation technique.
It was developed by Kennedy et al.[30], inspired by the social
behavior of bird flocking and fish schooling. PSO utilizes a
population of particles as a set of candidate solutions. Each
of the particles represents a certain position in the problem
hyperspace with a given velocity. A fitness function is used
to evaluate the quality of each particle. Initially, particles are
distributed in the hyperspace uniformly. Then each particle
repeatedly updates its state according to the individual best
position in its history (pbest) and the current global best posi-
tion (gbest). Eventually, each particle possibly moves toward
the direction of the individual optimum and global optimum,
and finds an optimal or near optimal solution.
Suppose that the problem domain is a D−dimensional
hyperspace. Then the position and velocity of particle i can
be represented by x
i
∈ R
D
and v
i
∈ R
D
respectively. CPSO
uses the following equations to update a particle’s velocity
and position, where v
i,j
(k) represents the jth component of the
velocity of particle i at the kth iteration, and x
i,j
(k) represents
its corresponding position:
v
i,j
(k + 1) = ω × v
i,j
(k) + c
1
× r
1,j
× (pbest
i,j
− x
i,j
(k))
+ c
2
× r
2,j
× (gbest
j
− x
i,j
(k)) (2)
x
i,j
(k + 1) = x
i,j
(k) + v
i,j
(k + 1). (3)
The best position of particle i in its history is pbest
i
, and
gbest is the best position among all particles. The velocity-
update equation (2) captures the three basic concepts of PSO.
The first is inertia, the tendency of the particle to continue in
the direction it has been moving. The second is memory of
the best position ever found by itself. The third is cooperation
using the best position found by other particles.
The parameter ω is inertia weight. It controls the bal-
ance between exploration (global search state) and exploitation
(local search state). Two positive real numbers c
1
and c
2
are acceleration constants that control the movement ten-
dency toward the individual and global best position. Most
studies set ω = 0.9, and c
1
= c
2
= 2 to get the best
balance [17], [31], [32]. In addition, r
1,j
and r
2,j
are two uni-
formly distributed random numbers in the range of [0.0, 1.0],
used to ensure the diversity of the population.
If the problem domain (the search space of particles) has
bounds, a bound handling strategy is adopted to keep the par-
ticles inside the search space. Many different strategies have
been proposed [33]. In the reflecting strategy, when a particle
exceeds the bound of the search space in any dimension, the
particle direction is reversed in this dimension to get back to
the search space. For example, in case of a dimension with
a range of values from 0 to 2, if a particle moves to 3, its
position is reversed to 1.
In addition, as the velocity can increase over time, a limit
is set on velocity to prevent an infinite velocity or invalid
position for the particle. Setting a maximum velocity, which
determines the distance of movement from the current position
to the possible target position, can reduce the likelihood of
explosion of the swarm traveling distance [31]. Generally, the
value of the maximum velocity is selected as
i
/2, where
i
is the range of dimension i.
The pseudocode in Algorithm 2 presents the process of gen-
erating a test case by PSO. This algorithm can be invoked
by line 6 of Algorithm 1 to generate a test case for t-way
schemas. The n factors of the test case can be treated as an
n-dimensional hyperspace. A particle p
i
=(x
1
, x
2
, ..., x
n
) can
be regarded as a candidate test case. The fitness function is
that of Definition 4, the number of uncovered t-way schemas
in the generated test suite that are covered by particle p
i
. PSO
employs real numbers but the valid values are integers for cov-
ering array generation, so each dimension of particle’s position
can be rounded to an integer while maintaining the velocity
as a real number. This method is used in all prior research
applying PSO to covering array generation [13]–[16].
III. R
ELATED WORK
In this section, three different but related aspects are dis-
cussed. We first summarize search-based CT, especially the
current applications of PSO for covering array generation.
Then, we introduce prior research on discrete versions of PSO,
剩余16页未读，继续阅读
2022-06-20 上传
2019-04-21 上传
点击了解资源详情
点击了解资源详情
点击了解资源详情
点击了解资源详情
点击了解资源详情
2023-09-05 上传
2024-11-03 上传
weixin_38746574
- 粉丝: 10
- 资源: 937
我的内容管理
展开
最新资源
- StarModAPI: StarMade 模组开发的Java API工具包
- PHP疫情上报管理系统开发与数据库实现详解
- 中秋节特献：明月祝福Flash动画素材
- Java GUI界面RPi-kee_Pilot：RPi-kee专用控制工具
- 电脑端APK信息提取工具APK Messenger功能介绍
- 探索矩阵连乘算法在C++中的应用
- Airflow教程：入门到工作流程创建
- MIP在Matlab中实现黑白图像处理的开源解决方案
- 图像切割感知分组框架：Matlab中的PG-framework实现
- 计算机科学中的经典算法与应用场景解析
- MiniZinc 编译器：高效解决离散优化问题
- MATLAB工具用于测量静态接触角的开源代码解析
- Python网络服务器项目合作指南
- 使用Matlab实现基础水族馆鱼类跟踪的代码解析
- vagga：基于Rust的用户空间容器化开发工具
- PPAP: 多语言支持的PHP邮政地址解析器项目
