用于覆盖阵列生成的离散粒子群优化资源-CSDN文库

125 浏览量 2021-03-03 12:17:49 上传评论收藏 2.01MB PDF 举报

标题《用于覆盖阵列生成的离散粒子群优化》指出本文将重点探讨一种基于离散粒子群优化（DPSO）算法的覆盖阵列生成方法。该方法在软件测试领域中属于组合测试（Combinatorial Testing，CT）研究的一个重要分支，旨在通过生成尽可能小的测试用例集合来发现由不同因素及其相互作用引起的缺陷。覆盖阵列生成是一个离散优化问题，在CT领域中受到广泛关注。描述中提到，粒子群优化（Particle Swarm Optimization，PSO）是一种基于群体智能的演化搜索启发式技术，已经成功地生成了在大小上具有竞争力的覆盖阵列。但目前现有的PSO方法在处理离散搜索空间时，仅简单地将粒子位置四舍五入到整数。此外，对于参数设置这一问题，目前尚无有效的指导方针。本文提出了两种辅助策略，即粒子重初始化和对全局最优解gbest进行额外评估，以改善性能。通过这些策略发展出一种新颖的DPSO算法，专门用于覆盖阵列生成，并系统性地开发了针对传统PSO（CPSO）和DPSO的参数设置指导方针。同时，本文还开发了四种现有PSO变体的离散扩展，以进一步研究DPSO在覆盖阵列生成中的有效性。实验表明，采用参数设置指导方针的CPSO可以产生更好的结果，而DPSO能够生成比CPSO和其他现有演化算法更小的覆盖阵列。从内容部分摘录的信息来看，文章被发表在了IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION期刊上，是一篇关于进化计算领域的研究论文。研究者们包括华耀武（Huayao Wu）、聂长海（Changhai Nie）、费青（Fei-Ching Kuo）、李扬亨（Hareton Leung）和查尔斯·J·科尔本（Charles J. Colbourn）。文章的发表时间表明，这项研究的提交和修正经历了相对漫长的过程，最终于2015年发表。文章进一步指出，随着软件功能和运行环境变得更加复杂，现代软件系统的测试变得越来越昂贵。文章开篇即提出组合测试（CT）的目标，即通过一组较小的测试用例集合来发现这些因素及其相互作用所引起的缺陷。离散粒子群优化（Discrete Particle Swarm Optimization，DPSO）是一种对连续空间PSO算法的离散扩展。DPSO方法在处理覆盖阵列生成这类离散优化问题时，相较于现有的其他演化算法，展示了更高的效率。PSO算法通过模拟鸟群的觅食行为，在问题空间中搜寻最优解。DPSO中通过离散化方法，粒子的移动不再是连续的，而是符合离散问题空间的限制。在传统PSO（CPSO）中，粒子的位置更新是通过简单的数学公式完成，但在离散空间中，位置需要四舍五入到最近的离散点。论文提出的改进措施包括粒子重初始化和对全局最优解的额外评估，意在提高算法的收敛速度和解的质量。粒子重初始化意味着在算法陷入局部最优解时，将粒子随机重新放置到搜索空间中，有助于跳出局部最优。额外评估全局最优解gbest的策略则是为了确保算法在迭代过程中能够更加有效地利用已发现的最优解。文章中也提到了实验结果，显示了DPSO算法在生成覆盖阵列方面的优势，并指出这在PSO算法中是一个有希望的改进方向。DPSO算法被证实能够生成更小的覆盖阵列，也就是说，它在保持测试用例组合数量的同时，能够更有效地检测到缺陷。文章提到的索引项包括组合测试（Combinatorial Testing，CT）、覆盖阵列生成（covering array generation）、粒子群优化（Particle Swarm Optimization，PSO）。这些索引项指明了文章主题和研究方向，强调了该研究在相关领域的应用价值和重要性。

资源推荐

资源详情

资源评论

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 19, NO. 4, AUGUST 2015 575

A Discrete Particle Swarm Optimization for

Covering Array Generation

Huayao Wu, Changhai Nie, Member, IEEE, Fei-Ching Kuo, Member, IEEE,

Hareton Leung, Member, IEEE, and Charles J. Colbourn

Abstract—Software behavior depends on many factors.

Combinatorial testing (CT) aims to generate small sets of test

cases to uncover defects caused by those factors and their

interactions. Covering array generation, a discrete optimization

problem, is the most popular research area in the ﬁeld of CT.

Particle swarm optimization (PSO), an evolutionary search-based

heuristic technique, has succeeded in generating covering arrays

that are competitive in size. However, current PSO methods for

covering array generation simply round the particle’s position

to an integer to handle the discrete search space. Moreover, no

guidelines are available to effectively set PSOs parameters for

this problem. In this paper, we extend the set-based PSO, an

existing discrete PSO (DPSO) method, to covering array gen-

eration. Two auxiliary strategies (particle reinitialization and

additional evaluation of gbest) are proposed to improve perfor-

mance, and thus a novel DPSO for covering array generation

is developed. Guidelines for parameter settings both for conven-

tional PSO (CPSO) and for DPSO are developed systematically

here. Discrete extensions of four existing PSO variants are devel-

oped, in order to further investigate the effectiveness of DPSO

for covering array generation. Experiments show that CPSO can

produce better results using the guidelines for parameter settings,

and that DPSO can generate smaller covering arrays than CPSO

and other existing evolutionary algorithms. DPSO is a promising

improvement on PSO for covering array generation.

Index Terms—Combinatorial testing (CT), covering array

generation, particle swarm optimization (PSO).

I. INTRODUCTION

S SOFTWARE functions and run-time environments

become more complex, testing of modern software sys-

tems is becoming more expensive. Effective detection of

Manuscript received May 12, 2013; revised December 29, 2013 and

May 18, 2014; accepted September 28, 2014. Date of publication October 9,

2014; date of current version July 28, 2015. This work was supported in part

by the National Natural Science Foundation of China under Grant 61272079,

in part by the Research Fund for the Doctoral Program of Higher Education

of China under Grant 20130091110032, in part by the Science Fund for

Creative Research Groups of the National Natural Science Foundation of

China under Grant 61321491, in part by the Major Program of National

Natural Science Foundation of China under Grant 91318301, and in part

by the Australian Research Council Linkage under Grant LP100200208.

(Corresponding author: Changhai Nie.)

H. Wu and C. Nie are with the State Key Laboratory for Novel

Software Technology, Nanjing University, Nanjing 210023, China (e-mail:

hywu@outlook.com; changhainie@nju.edu.cn).

F.-C. Kuo is with the Faculty of Information and Communication

Technologies, Swinburne University of Technology, Hawthorn, VIC 3122,

Australia (e-mail: dkuo@swin.edu.au).

H. Leung is with the Department of Computing, Hong Kong Polytechnic

University, Hong Kong (e-mail: hareton.leung@polyu.edu.hk).

C. J. Colbourn is with Arizona State University, Tempe, AZ 85287-8809,

USA (e-mail: colbourn@asu.edu).

Digital Object Identiﬁer 10.1109/TEVC.2014.2362532

failures at a low cost is a key issue for test case genera-

tion. Combinatorial testing (CT) is a popular testing method

to detect failures triggered by various factors and their interac-

tions [1]. By employing covering arrays as test suites, the CT

method aims to sample the large combination space with few

test cases to cover different interactions among a ﬁxed num-

ber of factors. Kuhn and Reilly [2] shows that more than 70%

of the failures in certain software were caused by the interac-

tions of one or two factors, and almost all the failures could

be detected by checking the interactions among six factors.

Therefore, CT can be an effective method in practice.

Generating a covering array with fewest tests (minimum

size) is a major challenge in CT. In general, the minimum

size of a covering array is unknown; hence, methods have

focused on ﬁnding covering arrays that have as few tests as

possible at reasonable search cost. The many methods that

have been proposed can be classiﬁed into two main groups:

1) mathematical methods and 2) computational methods [1].

Mathematical (algebraic or combinatorial) methods typically

exploit some known combinatorial structure. Computational

methods primarily use greedy strategies or heuristic-search

techniques to generate covering arrays, due to the size of the

search space.

Mathematical methods yield the best possible covering

arrays in certain cases. For example, orthogonal arrays used

in the design of experiments provide covering arrays with a

number of tests that is provably minimum. However, all known

mathematical methods can be applied only for restrictive sets

of factors. This limitation has led to an emphasis on compu-

tational methods. Greedy algorithms have been quite effective

in generating covering arrays, but their accuracy suffers from

becoming trapped in local optima.

In recent years, search-based software engineering (SBSE)

has focused on using search-based optimization algorithms

to ﬁnd high-quality solutions for software engineering prob-

lems. Inspired by SBSE, many artiﬁcial intelligence-based

heuristic-search techniques have been applied to software

testing. For example, simulated annealing (SA) [3]–[7],

genetic algorithm (GA) [8]–[10], and ant colony

optimization (ACO) [9], [11], [12] have all been applied

to covering array generation. These techniques can generate

any types of covering arrays, and the constraint solving

and prioritization techniques can be easily integrated. Their

applications have been shown to be effective, producing

relatively small covering arrays in many cases. Particle swarm

optimization (PSO), a relatively new evolutionary algorithm,

1089-778X

 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.

See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

576 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 19, NO. 4, AUGUST 2015

has also been used in this area [13]–[16]. It is easy to

implement and has fast initial progress.

The conventional PSO (CPSO) algorithm was originally

designed to ﬁnd optimal or near optimal solutions in a

continuous space. Nevertheless, many discrete PSO (DPSO)

algorithms and frameworks have been developed to solve

discrete problems [17]–[22]. For covering array generation,

current discrete methods [13]–[16] simply round the particle’s

position to an integer while keeping the velocity as a real

number. They suffer from two main shortcomings. First, the

performance of PSO is signiﬁcantly impacted by its parameter

settings. In [23], effects of the general parameter selection and

initial population of PSO have been analyzed, but no guide-

lines on parameter settings have been reported for covering

array generation. Hence, a clear understanding of how to set

these execution parameters is needed. Second, simple rounding

fractional positions to integers introduces a substantial source

of errors in the search. Instead, a specialized DPSO version is

needed. Because current PSO methods show promise for gen-

erating covering arrays, these two main shortcomings should

be addressed.

In this paper, we adapt set-based PSO (S-PSO) [18]to

generate covering arrays. S-PSO utilizes set and probability

theories to develop a new representation scheme for combina-

torial optimization problems as well as reﬁning the related

evolution operators. In our adaptation of S-PSO, two aux-

iliary strategies are proposed to enhance performance, and

a novel DPSO algorithm is thus proposed. DPSO has the

same conceptual basis and exhibits similar search behavior to

CPSO, with parameters playing similar roles. Then, we explore

the optimal parameter settings for both CPSO and DPSO to

improve their performance, and identify recommended set-

tings. Furthermore, because many CPSO variants [24]–[27]

can be easily extended to discrete versions based on our DPSO,

the performance of these discrete versions is also compared

with their original ones. Finally, we compare CPSO and DPSO

with existing GA and ACO [9], [11] algorithms to generate

covering arrays.

The main contributions of this paper are as follows.

1) Based on the set-based representation, we design a

version of S-PSO [18] for covering array generation.

2) We propose two auxiliary strategies, particle reinitializa-

tion, and additional evaluation of gbest, to enhance the

performance of PSO. A novel DPSO for covering array

generation is proposed.

3) We design experiments to explore the optimal param-

eter settings for CPSO and DPSO for covering array

generation.

4) We implement original and discrete versions of four

representative PSO variants (TVAC [24], CLPSO [25],

APSO [26], and DMS-PSO [27]) to compare their

efﬁcacy for covering array generation.

The rest of this paper is organized as follows. Section II

gives background on CT, covering array generation, and

the CPSO algorithm. Section III summarizes related work.

Section IV presents our DPSO algorithm, including the

representation scheme, related operators, and two auxiliary

strategies. Section V evaluates the performance of CPSO and

TABLE I

E-C

OMMERCE SOFTWARE SYSTEM

DPSO, and explores optimal parameter settings. Section VI

gives a comparison among CPSO, DPSO, and original and

discrete variants. Section VII compares CPSO and DPSO

with GA and ACO. Section VIII concludes this paper and

outlines future work.

II. B

ACKGROUND

A. CT

Suppose that the behavior of the software under test (SUT)

is controlled by n independent factors, which may repre-

sent conﬁguration parameters, internal or external events, user

inputs, and the like. The ith factor has 

discrete levels, cho-

sen from the ﬁnite set V

of size 

.Ann-tuple (x

, x

,...,x

)

forms a test case, where x

∈ V

for 1 ≤ i ≤ n.

Consider a simple e-commerce software system [15]. This

system consists of ﬁve different components. Each of these ﬁve

components can be regarded as a factor, and its conﬁgurations

can be regarded as different levels. Table I shows these ﬁve

factors and their corresponding levels. In this example, n = 5,



= 

= 2, 

= 

= 3.

System failures are often triggered by interactions among

some factors, which can be represented by the combinations

of factor levels. In order to detect these failures, their com-

binations should be covered at least once by the test suite. A

t-way schema can be used to represent them.

Deﬁnition 1 (t-way schema): The n-tuple (−, y

, ...,

, ...) is a t-way schema (t > 0) when some t factors

have ﬁxed levels and the others can take any valid levels,

represented as “−.”

For example, suppose that when factor Payment Server

takes the level Master and factor Web Server takes the level

Apache, a system failure occurs. To detect this failure, the

2-way schema (Master, –, Apache, –, –) must be covered

at least once by the test suite. To simplify later discussion,

we use the index in the level set of each factor to present

a schema. For example, (0, –, 1, –, –) is used to represent

(Master, –, Apache, –, –).

Exhaustive testing covers all n-way schemas of the sys-

tem; in our example, it uses 2 × 2 × 2 × 3 × 3 = 72 test

cases. Testing cost becomes prohibitive as the numbers of fac-

tors and levels increase. Moreover, because only interactions

among few factors are likely to trigger failures [2], testing

high-way schemas can lead to many uninformative test cases.

At the other extreme, if we only guarantee to cover each 1-way

schema once, only three test cases are needed (a single test

case can cover ﬁve 1-way schemas at most). But we may

fail to detect some interaction triggered failures involving two

factors.

WU et al.: A DISCRETE PARTICLE SWARM OPTIMIZATION FOR COVERING ARRAY GENERATION 577

TABLE II

OVERING ARRAY CA(9; 2, 2

)

Instead, CT covers all t-way schemas. Such a test suite is a

t-way covering array, with t being the covering strength. The

value of t determines the depth of coverage. It is a key setting

of CT, and should be decided by the testers. We give a precise

deﬁnition.

Deﬁnition 2 (Covering Array): If an N×n array, where N is

the number of test cases, has the following properties: 1) each

column i (1 ≤ i ≤ n) contains only elements from the set V

with 

=|V

| and 2) the rows of each N × t sub array cover

all |V

|×|V

|×...×|V

| combinations of the t columns at

least once, where t ≤ n and 1 ≤ k

<...<k

≤ n, then it is a

t-way covering array, denoted by CA(N; t, n,(

,

,...,

)).

When 

= 

= ... = 

= , it is denoted by CA(N; t, n,).

Reference [2] demonstrated that more than 70% failures can

be detected by a 2-way covering array, and almost all failures

can be detected by a 6-way covering array. Hence, using CT,

we can detect many failures of the system by applying rela-

tively low strength covering arrays. In other words, CT can

greatly reduce the size of test suite while maintaining high

fault detection ability.

In the example of Table I, if we only consider the inter-

actions between any two factors, only nine test cases are

required to construct a 2-way covering array instead of 72

for exhaustive testing. Table II shows a covering array, where

each row represents one test case. This table covers all possi-

ble 2-way schemas for any two factors corresponding to the

columns. For example, consider factor Payment Server and

User Browser, all 2×3 = 6 schemas, (Master, –, –, Firefox, –)

(Master, –, –, Explorer, –), (Master, –, –, Chrome, –),

(VISA, –, –, Firefox, –), (VISA, –, –, Explorer, –),

(VISA, –, –, Chrome, –), can be found in the table.

For convenience, if several groups of g

factors (g

< n)have

the same number of levels a

, a

can be used to represent

these factors and their levels. Thus, the covering array can

be denoted by CA(N; t, a

, a

,...,a

) where



= n,

or CA(N; t, a

) when g

= n and a

= a. For example, the

covering array in Table II is a CA(9; 2, 2

In many software systems, the impacts of the interactions

among factors are not uniform. Some interactions may be more

prone to trigger system failures, while other may have lit-

tle or no impact on the system. To effectively detect these

different interactions, variable strength (VS) covering arrays

can be applied. This can offer different covering strengths

TABLE III

DDING THREE TEST CASES TO CONSTRUCT

VCA(12; 2, 2

, CA(3, 2

))

to different groups of factors, and can therefore provide a

practical approach to test real applications.

Deﬁnition 3 (VS Covering Array): A VS covering array,

denoted by VCA(N; t, a



...a



, CA

, b

...b

),...,

, c

...c

)),isanN × n covering array of covering

strength t containing one or more sub covering arrays, namely

, ..., CA

, each of which has covering strength t

, ..., t

all larger than t.

Consider the e-commerce system shown in Table I.Ifthe

interactions of three factors, Payment Server, Web Server, and

Business Database, have a higher probability to trigger sys-

tem failures, then a VS covering array can be constructed.

As in Table II, only three more test cases (Table III)are

needed to construct the VCA(12; 2, 2

, CA(3, 2

)). With

these 12 test cases, not only are all 2-way schemas of all ﬁve

factors covered, but also all 3-way schemas of these three fac-

tors (Payment Server, Web Server, and Business Database) are

covered.

B. Covering Array Generation

Covering arrays are used as test suites in CT. Covering array

generation is the process of test suite construction. It is the

most active area in CT with more than 50% of research papers

focusing on this ﬁeld [1]. Due to limited testing resources, all

aim to construct a minimal covering array while still main-

taining full coverage of combinations. Computational methods

have been used widely for covering array generation because

they can be applied to any systems. In general, these methods

generate all possible combinations ﬁrst. Then they generate

test cases to cover these combinations one-by-one. One-test-

at-a-time is the most widely used strategy among evolutionary

algorithms to generate a covering array.

The one-test-at-a-time strategy was popularized by

AETG [28] and was further used by Bryce and Colbourn [29].

This strategy takes the model of SUT(n, 

, ..., 

) where

n is the number of factors and 

is the number of valid

levels of factor i, and the covering strength t as input. At

ﬁrst, an empty test suite TS and a set S of t-way schemas

to be covered are initialized. In each iteration, a test case is

generated with the highest ﬁtness value according to some

heuristic techniques. Then it is added to TS and the t-way

schemas covered by it are removed. When all the t-way

schemas have been covered, the ﬁnal test suite TS is returned.

This process is shown in Algorithm 1.

In this strategy, a ﬁtness function must be used to evaluate

the quality of a candidate test case (line 6 in Algorithm 1). It is

an important part of all heuristic techniques. In covering array

generation, the ﬁtness function takes the test case as the input

and then outputs a ﬁtness value representing its “goodness.”

It is deﬁned as follows.

剩余16页未读，继续阅读

评论收藏

内容反馈

weixin_38746574

粉丝: 10
资源: 936

用于覆盖阵列生成的离散粒子群优化

用于覆盖阵列生成 的离散粒子 群优化_C++_代码_下载

潮流能涡轮机阵列优化离散量子粒子群算法.docx

基于模糊离散粒子群算法的非均匀阵列优化(英文) (2012年)

基于模糊离散粒子群算法的非均匀阵列优化(英文).pdf

粒子群优化算法用于阵列天线方向图综合设计.pdf

粒子群优化算法综合阵列的副瓣

PSO粒子群优化MPPT,并应用在PV光伏阵列发电系统simulink仿真,其中PSO在simulink实现进行实时优化控制

雷达通信基于matlab粒子群算法优化综合微带天线阵列方向图【含Matlab源码 1967期】.zip

【雷达】基于粒子群算法优化综合微带天线阵列方向图附matlab代码，可以自适应调节副瓣电平和波瓣宽度.zip

改进的粒子群优化算法用于方向图阵列综合.pdf

一种改进的离散粒子群算法用于分布式电源容量优化.pdf

粒子群优化算法在阵列天线方向图中的应用

基于粒子群优化算法的共形阵列天线图综合.pdf

粒子群算法综合线阵低副瓣方向图.zip_低副瓣_算法 方向图_粒子群_粒子群 线阵_阵列 优化

粒子群优化算法PSO介绍中英文翻译word版.pdf

基于粒子群优化的MPPT跟踪.zip

基于粒子群优化算法的功率倒置阵列.pdf

粒子群算法综合线阵低副瓣方向图_粒子群_粒子群算法_阵列天线_天线综合_方向图综合

基于改进粒子群优化算法光伏阵列多峰值MPPT的研究.pdf

matlabfuxing.rar_matlab阵列综合_天线方向图_泰勒方向图_粒子群方向图_阵列优化

基于粒子群算法的阵列波束宽零陷优化设计.pdf

基于自适应权重粒子群优化BP神经网络的光伏阵列故障诊断与定位.pdf

粒子群优化RBF神经网络的光伏阵列故障诊断.pdf

改进小波变异粒子群优化算法用于直线阵综合.pdf

基于粒子群优化小波神经网络的光伏阵列故障检测.docx

基于粒子群优化算法的天线方向图综合研究.pdf

基于免疫粒子群算法的交叉天线阵列优化方法.pdf

最新资源

用于覆盖阵列生成的离散粒子群优化_C++_代码_下载

粒子群算法综合线阵低副瓣方向图.zip_低副瓣_算法方向图_粒子群_粒子群线阵_阵列优化