=Paper=
{{Paper
|id=Vol-3007/2020-paper-1
|storemode=property
|title=A Germinal Centre Artificial Immune System for Software Test Suite Reduction
|pdfUrl=https://ceur-ws.org/Vol-3007/2020-paper-1.pdf
|volume=Vol-3007
|authors=Lukas Rosenbauer,Anthony Stein,Jörg Hähner
|dblpUrl=https://dblp.org/rec/conf/lifelike/RosenbauerSH21
}}
==A Germinal Centre Artificial Immune System for Software Test Suite Reduction==
https://ceur-ws.org/Vol-3007/2020-paper-1.pdf
A Germinal Centre Artificial Immune System for Software Test Suite Reduction
Lukas Rosenbauer1 , Anthony Stein2 and Jörg Hähner3
1 BSH Home Appliances, Im Gewerbepark B35, Regensburg, Germany
2 Artificial Intelligence in Agricultural Engineering, University of Hohenheim, Garbenstr. 9, Stuttgart, Germany
3 Organic Computing Group, University of Augsburg, Eichleitnerstr. 30, Augsburg, Germany
lukas.rosenbauer@bshg.com
Abstract optimal solution is hard to find within a reasonable amount
of time.
Testing is a crucial part in the development of a new product. During this work we also intend to reduce the size of the
If too little testing is done, customers might discover previ-
test suite during its specification, similar to Gotlieb and Mar-
ously undetected failures. A common approach to avoid this
is to define a test suite that contains at least one test for every ijan (2014). However, Gotlieb and Marijan (2014) used a
requirement. As the execution of manual tests and the imple- branch and bound approach that has worst case exponential
mentation of automated ones is timeintensive, it is a profitable runtime. On the other hand evolutionary algorithms tend
goal to reduce the amount of tests during the specification of to be computational lightweights that may not offer optimal
the test suite whilst still covering all requirements. In this
solutions but approximations with reasonable quality and es-
work we provide an artificial immune system to detect redun-
dant tests. Our new approach achieves optimal results for our pecially the MSCP has undergone heavy research from the
industrial data sets and further we are able to reduce its run- evolutionary computation community (Li et al., 2009; Yu
time and memory usage drastically compared to the existing et al., 2010; Yu et al., 2014; Balaji and Revathi, 2016).
germinal centre artificial immune system (GCAIS). The immune system has been used an inspiration for both
computational intelligence and rule based machine learning
(Azuaje, 2003). The latter is closely related to learning clas-
Introduction
sifier systems (LCS) which are frequently used in organic
Testing is a timeintensive but nevertheless important part of computing systems. Organic computing (OC) seeks to de-
product development. The verification of new products be- sign systems that have self-x properties (Müller-Schloer and
comes even more essential as the complexity of software is Tomforde, 2017) which can be found in LCS and in the im-
increasing rapidly. Several studies confirm that the size of mune system. The former has lead to a rather new evolution-
the specified test suite has a major impact on the total de- ary metaheuristic called germinal centre artificial immune
velopment cost (Fraser and Wotawa, 2007; Yu et al., 2008; system (GCAIS) (Joshi et al., 2014). The approach main-
Hsu and Orso, 2009). Thus it is a worthy goal to reduce the tains a population that takes an analogy to self-reacting cells
size of a test suite whilst maintaining its quality, such as its that create antibodies to eradicate pathogens. GCAIS has al-
coverage or its capability to find errors. ready been successfully applied to the MSCP on Beasley’s
Several approaches are already available to reduce the size OR library Joshi (2017) and often had optimal or close to
of the test suite for certain stages of testing. For example optimal results. However, it turns out that GCAIS has a few
Spieker et al. (2018) determine a test suite based on the his- downsides that we want to tackle in this paper.
tory of individual tests (e. g. how often did a test fail or how The main contributions of this paper are:
long does its execution take) using a reinforcement learning
agent. The agent selects tests that are more likely to fail and • GCAIS maintains a population of non-dominated ele-
its suite has bounded execution time. Gotlieb and Marijan ments which is updated every iteration. The correspond-
(2014) try to reduce the size of the test suite before any test is ing computation is also known as the calculation of the
executed or implemented. In contrast to Spieker et al. (2018) skyline (Börzsönyi et al., 2001). Several methods exist to
they maintain the coverage of the original test suite because calculate the skyline but they usually have higher than lin-
a testing history is not available yet. Each test covers a set of ear cost. We explicitly exploit the structure of GCAIS and
requirements and their goal is to determine the minimal set the MSCP and provide an approach that has linear cost in
of tests that covers all requirements. In mathematics and terms of the population size and the problem size.
computer science this problem is known as the minimum
set cover problem (MSCP) (Williamson and Shmoys, 2011). • The size of GCAIS’ population may explode. We intro-
The MSCP is a NP-hard optimization problem and thus an duce simple population boundaries and a deletion mech-
Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
anism similar to genetic algorithms (GA) to avoid this is- et al. (2010) developed an algorithm based on ant colony
sue (Holland, 1992). In our experiments we show that this optimization.
does not harm GCAIS’ capability to find close to optimal There are several pure mathematical approaches for solv-
solutions. In most cases our adapted version even is able ing the MSCP such as greedy algorithms, integer linear pro-
to find an optimal one. grams and rounding techniques which are guaranteed to con-
verge (Williamson and Shmoys, 2011). Gotlieb and Mari-
• We show on two industrial data sets that GCAIS can dras- jan (2014) designed an algorithm called FLOWER that com-
tical reduce the size of the specified test suite. Further we bines a branch and bound approach with flow networks.
can observe that the structure of test specifications differs FLOWER always delivers an optimal solution, but on the
from the more theoretical MSCP instances of Beasley’s other hand may have exponential runtime (depending on the
OR library. problem instance).
In Section 2 we introduce the MSCP in a formal way, dis- Germinal Center Artificial Immune System
cuss its approximability, and briefly introduce related work. In this section we introduce the base version of GCAIS. Fur-
Afterwards we present GCAIS and show how to reduce its ther, we identify its critical parts and show how the corre-
runtime and how we keep the population in bounds (Section sponding runtime and memory issues are avoided.
3). In Section 4 we perform experiments on two industrial
data sets as well as on Beasley’s OR library and examine Base algorithm
memory usage, runtime and approximation quality. Further GCAIS is a population-based, randomised search heuristic
future work is discussed in Section 5. We close the paper that is based on the immune system of vertebrates. The
with a conclusion (Section 6). heuristic has been influenced by recent insights about ger-
minal centre reaction (Joshi et al., 2014). Germinal centres
Minimum Set Cover Problem (GC) are regions where the invading antigen (Ag) is pre-
Here we first intend to describe the MSCP in a more formal sented to immune cells. If an invasion occurs, the cells pro-
way. Let n be the number of sets (the test cases) and m be the duce antibodies (Ab) that try to bind the pathogen and erad-
number of elements (the requirements) to cover. We denote icate it. The GCs start to grow and try to find the best Abs.
the sets as T1 , T2 ,...,Tn . Thus the problem to be solved can GCs communicate with each other in order to exchange their
be described as follows: Abs. The latter can be improved by proliferation, mutation
and selection of immune cells.
min |TS | We encode solutions as binary vectors of length m. If
[ [m the entry i is one then Ti belongs to the solution and a zero
s.t. Ti = Ti indicates that Ti is not a part of the cover. Furthermore let
i∈TS i=1 (1) |x| be the L1-norm of x (corresponds to the number of sets
TS ⊆ {1, 2, ..., m} used).
The metaheuristic maintains a population of non-dominated
Ti ⊆ {1, 2, ..., n}
solutions and also allows unfeasible solutions. A solution x
Thus we want to determine the minmal number of tests that is said to dominate another solution y if one of the following
still cover all requirements. A set of tests is called test suite two condition holds:
and thus the problem is coined test suite reduction if the
S S
i) |x| ≤ |y| ∧ | i∈x Ti | > | i∈y Ti |
undelying MSCP instance corresponds to tests (Gotlieb and S S
Marijan, 2014). If redundant tests can already be identified ii) |x| < |y| ∧ | i∈x Ti | ≥ | i∈y Ti |
during specification then their implementation as automated We denote this relation as x > p y. This relation is also
ones or their manual execution can be avoided. known as pareto dominance (Börzsönyi et al., 2001).
From a mathematical perspective the MSCP is one of the The initial population P consists out of the zero vector 0
more difficult NP-hard problems to solve as its worst case (no set at all is used). In every iteration the entire popula-
approximation ratio grows logarithmically in terms of the tion is mutated (flipping individual bits with a probability
problem size for algorithms with polynomial runtime (Dinur of m1 ) and merged with the original one. During the merge
and Steurer, 2014). However, as this result concerns the step every solution is eliminated that is either dominated by
worst case there is still research ongoing to find a method a mutated solution or a solution that is already in the popu-
that performs well on average. lation. This is repeated until a stopping criteria is met. We
Minotra (2008) gives an overview about genetic algo- summarized the method in Algorithm 1.
rithms and simulated annealing methods. Balaji and Revathi The for loop (line 4-7) costs O(|P|m) and can easily be
(2016) designed a particle swarm optimization method, Yu parallelized using for example OpenMP or other standard
et al. (2014) used chemical reaction optimization, and Ren parallelization libraries.
Algorithm 1: Germinal centre artificial immune
system (GCAIS).
input : T1 , T2 , ..., Tn , m
output: a solution
1 P = {0}
2 while stopping criterion is not met do
3 P’ = {}
4 for x in P do
5 y = mutate x
6 insert y to P’
7 end
8 Q = P ∪ P’
9 P = {x ∈ Q|∀y ∈ Q : ¬y > p x}
10 end
11 return best solution of P
Figure 1: Example of a skyline. The elements of the skyline
are marked black. The gray balls represent solutions found
throughout the search that have been dominated.
We decided to go for such a population based approach
as usually throughout a project the requirements (and thus • Sort filter skyline (SFS) sorts the considered solutions ac-
the tests) may change (Nurmuliani et al., 2004). With previ- cording to their entropy and exploits that subsequent solu-
ous approaches this would require a complete recalculation. tions cannot dominate preceeding ones. The method has
However, GCAIS allows infeasible solutions in its popula- a cost of O(|P|log(|P|)) (Chomicki et al., 2003).
tion and would enable us to translate the previous population
to the updated problem. We hope that this self-improving • Divide and conquer (D&Q) approaches split the solutions
approach might reduce the runtime in the future. into chunks and calculate skyline recursively. This also
GCAIS is similar to the global simple evolutionary multi- costs O(|P|log(|P|)) (Börzsönyi et al., 2001).
objective optimiser (GSEMO) (Giel and Wegener, 2003)
There are further approaches especially designed to handle
which is another population-based approach. It differs from
high-dimensional data or memory issues (Endres and We-
GCAIS as it has several populations and only mutates one
ichmann, 2017; Endres and Kießling, 2015; Endres et al.,
solution per iteration and population instead of all. Fur-
2015); however, as this is out of the scope of this paper, we
ther it sends a new solution with a probability p to all other
will not further discuss them.
populations. GSEMO’s populations also consist out of non-
The optimization problem that we try to solve is two-
dominated solutions.
dimensional (covered requirements, used tests), both dimen-
Skyline sions are discrete, and P is always a non-dominated set. We
The for loop of Algorithm 1 is not the only costly step of exploit these facts to provide a skyline calculation that costs
an iteration. The recalculation of P is also computationally O(n + |P|).
intense. In data engineering the calculation of the set of non- We maintain a look-up table which holds an entry for ev-
dominated solutions is also known as the computation of the ery i ∈ {0, 1, 2, .., n}. The i-th entry holds all solutions of
skyline (Börzsönyi et al., 2001). It is coined skyline as in the population that use i tests. It further holds how many
the two-dimensional case its solutions are ”above” the others requirements are covered by the solutions (they all cover the
(see Figure 1). A side effect of this visualization is that it can same number of requirements, otherwise a solution would
be used to track the search process of GCAIS or GSEMO be dominated). Whenever we consider to insert a mutated
during runtime. The advantage is that a series of these plots solution x for insertion we check the entry |x|. If the entry
displays the development of the population (in terms of its covers more elements then x is not inserted, if it covers the
diversity) and the convergence behaviour. Note, that in other same amount of elements then we append the solution to the
research areas the skyline is named pareto-frontier. entry. If it covers more elements then we overwrite the entry
Several algorithms exist in order to calculate the skyline with x and update the covered elements of the entry. Thus
(complexities adapted to this use case): an insertion costs O(1) and the insertion of the mutated pop-
ulation costs O(|P|).
• Block nested loop (BNL) is the straightforward approach After the insertion of a solution the table may contain
that compares each solution x with all other solutions in dominated solutions as only the entry of its cost is checked.
order to determine the skyline. It is trivial to see that this An inserted solution could also dominate entries of higher
costs O(|P|2 ) (Börzsönyi et al., 2001). cost. Thus we also need to introduce a repair method that is
called at the end of every iteration of GCAIS. We traverse introduce simple population boundaries for each entry of
the table exactly once. We start by saving the index 1 into the look-up table. Whenever the capacity of an entry is ex-
a variable i and check if the current entry to look at covers ceeded then we delete a random solution from the entry to
more entries. If so, we update i by its index and if not, we make space for a new one. Unlike the skyline computation,
delete the entry and proceed. Thus the repair method costs this may change the convergence behaviour of the algorithm
O(n) and the calculation of the skyline O(n + |P|). which we examine in our experimental evaluation.
We describe our skyline algorithm in Algorithm 2. The There is also another approach to keep GCAIS’ popu-
variable table denotes the look-up table and table[i].cov is lation from growing too fast. Joshi et al. (2015) used ε-
the number of requirements covered by the solutions using i dominance instead of pareto-dominance. For the former, the
tests. The number of requirements covered and the number space is separated in squares of side length ε (for spaces of
of tests used by a solution x can easily be retrieved during higher dimensions it is separated into hypercubes). For two
the creation of the mutated population and thus does not af- solutions from different squares the ε-dominace relation is
fect the cost of that method. The table should be initialized the same as the pareto-dominance relation. If two solutions
before the main loop is entered and should be kept through- x and y are in the same square then x ε-dominates y if and
out the search. only if: [ [
|y| − |x| + | Ti | − | Ti | > 0 (2)
Algorithm 2: Skyline procedure for GCAIS using i∈x i∈y
a look-up table. If this approach is used then GCAIS keeps a population of
input : mutated solutions P’ non-ε-dominated solutions instead of non-pareto-dominated
1 // insertion solutions. ε-dominance is more strict than pareto-dominance
2 for x in P’ do and thus it makes it harder for a solution to be inserted. How-
3 covered x = requirements covered by x ever, this no guarantee that the population does not grow un-
4 if table has no entry |x| then restricted.
5 table[|x|].cov = covered x Both approaches can easily be integrated into Algorithm
6 set the solutions of table[|x|] to x 2. The boundary check and deletion of a random solution
7 else if table[|x|].cov == covered x then can be incorporated into the insertion part. In order to use
8 append x to the solutions of table[|x|] ε-dominance we have to extend our repair method by incor-
9 else if table[|x|].cov < covered x then porating a check if the table entries are in the same square
10 table[|x|].cov = covered x and deleting ε-dominated entries. This updated version has
11 set the solutions of table[|x|] to x the same worst case complexity as Algorithm 2. We describe
12 end the new repair method in Algorithm 3.
13 // repair the table
14 i = 1 Algorithm 3: Updated repair method if epsilon
15 for k in {2, ...n} do dominance is used.
16 if table[k].cov ≤ table[i].cov then input : look-up table, ε
17 delete table[k] 1 i=1
18 else if table[k].cov > table[i].cov then 2 for k in {2, ...n} do
19 i=k 3 if b k−i
ε c == 0 then
20 end 4 // both entries are in the same square
5 d = k-i+table[i].cov - table[k].cov
6 if d > 0 then
7 // i dominates k
Avoiding huge populations 8 delete table[k]
A difference between GCAIS and for example genetic algo- 9 else if d < 0 then
rithms is that its population is unbounded. GCAIS keeps 10 // k dominates i
the non-dominated solutions it encounters throughout its 11 delete table[k]
search. The idea is that a mutated solution based on a non- 12 i=k
dominated solution has a higher likelihood to be an optimal 13 else if table[k].cov ≤ table[i].cov then
or close to optimal solution. However, this has the downside 14 delete table[k]
that the population may grow rapidly. For example if all tests 15 else if table[k].cov > table[i].cov then
cover the same amount of requirements and no requirement 16 i=k
is covered by more than one test, then the population even 17 end
grows exponentially.
In order to avoid an explosion of the population size, we
Evaluation o(alg)
approx rate(alg) = (5)
In our experiments we want to evaluate how much execu- OPT
tion time we save due to our look-up table. Further, we in- where alg denotes any considered algorithm (and its cor-
vestigate if the introduction of ε-dominance and population responding hyperparameters). GCAIS BASE is the standard
boundaries limits the capability of GCAIS to find close to variant of GCAIS described in Algorithm 1 and for the cal-
optimal or optimal solutions. To our knowledge the former culation of its non-dominated population we use the BNL
has yet only been applied to the multiobjective Knapsack method. P(alg) is the maximum size of an algorithm’s pop-
problem (Joshi et al., 2015). ulation during a run and r(alg) is its total runtime (until con-
In our experiments we first focus on the main goal of this vergence is reached). OPT is the optimal value and o(alg)
paper: the reduction of the amount of tests. For this we is the algorithm’s output. The optimal values for the consid-
acquired two data sets from BSH Home Appliances which ered data sets of Beasley’s OR library are known and for the
is a german company that develops and produces various industrial data sets we determined them via brute force.
home appliances such as ovens or dishwashers. Our data The mem save key performance indicator (Equation 3)
sets are for two different fridge projects. In our experiments measures the relative size of an algorithm’s population with
we use cleaned versions of the data sets. We removed tests regards to GCAIS BASE. We use the standard variant as all
that exclusively cover a single requirement (these tests must other GCAIS variants intend to either bound the population
be in a test suite that covers all requirements). We call these or to increase the likelihood of deleting solutions (e. g. ε-
data sets Fridge-1 and Fridge-2. dominance). Thus we have a common baseline for all meth-
As we deem two datasets as too little, we additionally per- ods. Further, the population size is the main factor for mem-
form evaluations on the scpe instances of Beasley’s OR li- ory usage of the considered algorithms.
brary which is frequently used for benchmarking MSCP al- Our speed up KPI (Equation 4) is an analogy to paral-
gorithms (Balaji and Revathi, 2016; Joshi et al., 2014). lel computing. There the speed up is the quotient of a par-
During our evaluation we consider the various variants of allel program’s runtime and the runtime of the sequential
GCAIS next to the GSEMO algorithm. We follow the vari- one (Kumar, 2002). Thus it measures how fast the paral-
ant of Joshi et al. (2014) which was adapted to the MSCP. lel method is compared to the sequential one. Instead we
We examined several parameterizations for GSEMO and evaluate how much faster an algorithm is compared to the
concluded that a population size of 30 and a send probabil- standard GCAIS version.
30
ity of nm are suitable choices. We also performed a fine tun- Our third KPI is the approximation rate (Equation 5)
ing of the hyperparameters of the artificial immune systems which indicates how close the produced solution is to be-
which we will not discuss here (due to space restrictions). ing optimal and a value of one corresponds to an optimal
We achieved reasonable results with a population boundary solution.
of 200. For ε we consider 0, 5, 10 and 15. The base variant All three KPIs should be seen in context to each other. For
of GCAIS (Algorithm 1) is parameterfree. example a brute force search always leads to an optimal so-
We repeat every experiment 100 times. Our implementa- lution but will have an exponential runtime and on the other
tion1 is in Python and we used a Dell Precision 3520 for our hand an algorithm that just takes all tests has the worst ap-
experiments (Intel i7-6820HQ processor with 4 Cores and proximation ratio but the best speed up and memory usage.
an individual clock rate of 2.7 Ghz, 32 GB RAM). Hence the goal is to find an approach that leads to reasonable
Every algorithm is given a time budget of ten minutes. values in all three categories.
Further, if there is no improvement in terms of the solutions
quality for 100 iterations then we interpret this as conver- Industrial Datasets
gence. The results of our experiments are displayed in Table 1. Our
first dataset (Fridge-1) is rather easy to solve for the con-
Quality Criteria sidered methods compared to our second one. The epsilon
During our experiments we intend to measure the approxi- dominance variants, the bounded variant and the base variant
mation quality, memory usage, and runtime. Thus we intro- of GCAIS always achieve optimal results. Also, GSEMO
duce the following key performance indicators (KPIs): has close to optimal results. However the combination of a
bounded population and epsilon dominance is rather detri-
P(GCAIS BASE)
mem save(alg) = (3) mental as these versions produce worse solutions than the
P(alg) version without it. We can see certain differences in the
r(GCAIS BASE) memory usage and the speed up. The bounded version of
speed up(alg) = (4) GCAIS only uses about a tenth of the memory of its base
r(alg)
variant and is about fourteen times faster. Yet GESMO is
1 Source code and data are available here: https://github. even faster but only achieves close to optimal results and re-
com/LagLukas/gcais_test_suite_reduction quires more memory.
(a) GCAIS base variant (b) GCAIS with epsilon dominance
(c) GCAIS with bounded population (d) GSEMO
Figure 2: Population sizes ±σ for the Fridge-1 dataset.
(a) GCAIS base variant (b) GCAIS with epsilon dominance
(c) GCAIS with bounded population (d) GSEMO
Figure 3: Population sizes ±σ for the Fridge-2 dataset.
Table 1: KPIs for the experimental results (averaged values ±σ). A - character indicates that the parameter was not used. We
marked the best values of algorithms that always found optimal solutions bold. The best values of individual KPIs are marked
in italics. The horizontal line separates our approaches to the ones we are comparing to.
Fridge-1 population boundary (per entry) ε mem save speed up approx rate
GCAIS 200 5 22.77 ± 0.0 1.28 ± 0.19 1.29 ± 0.2
GCAIS 200 10 22.77 ± 0.0 1.54 ± 0.19 1.34 ± 0.17
GCAIS 200 15 28.47 ± 0.0 2.11 ± 0.16 1.38 ± 0.16
GCAIS 200 - 10.35 ± 0.0 14.14 ± 0.02 1.0 ± 0.0
GCAIS - 5 0.03 ± 0.03 0.77 ± 0.16 1.0 ± 0.0
GCAIS - 10 0.03 ± 8.95 0.75 ± 0.16 1.0 ± 0.0
GCAIS - 15 0.03 ± 16.27 0.73 ± 0.15 1.0 ± 0.0
GCAIS BASE - - 1.0 1.0 1.0 ± 0.0
GSEMO - - 1.66 ± 0.78 16.81 ± 0.13 1.03 ± 0.05
Fridge-2 population boundary (per entry) ε mem save speed up approx rate
GCAIS 200 5 8.49 ± 0.0 0.32 ± 0.38 3.62 ± 0.46
GCAIS 200 10 10.9 ± 0.0 0.51 ± 0.48 3.82 ± 0.47
GCAIS 200 15 12.49 ± 0.0 0.84 ± 0.33 3.96 ± 0.3
GCAIS 200 - 5.11 ± 0.01 3.58 ± 0.08 1.0 ± 0.0
GCAIS - 5 0.14 ± 3.4 0.88 ± 0.14 2.7 ± 0.13
GCAIS - 10 0.18 ± 3.14 0.88 ± 0.14 2.66 ± 0.28
GCAIS - 15 0.23 ± 2.47 0.96 ± 0.23 2.8 ± 0.19
GCAIS BASE - - 1.0 1.0 1.0 ± 0.02
GSEMO - - 9.89 ± 0.01 47.33 ± 0.01 2.94 ± 0.15
Table 2: Experimental results for Beasley’s OR library. The best values are marked bold. Each KPI is displayed ±σ.
KPI algorithm scpe1 scpe2 scpe3 scpe 4 scpe5
mem save GSEMO 1.62 ± 0.15 1.62 ± 0.13 1.39 ± 0.2 1.1 ± 0.3 1.91 ± 0.15
mem save bounded GCAIS 4.23 ± 0.01 4.54 ± 0.01 4.68 ± 0.02 4.31 ± 0.02 4.54 ± 0.01
speed up GSEMO 2.56 ± 0.15 2.22 ± 0.15 1.69 ± 0.28 1.26 ± 0.41 3.37 ± 0.15
speed up bounded GCAIS 1.73 ± 0.18 1.36 ± 0.24 2.56 ± 0.14 2.04 ± 0.2 1.87 ± 0.21
approx rate GSEMO 1.46 ± 0.16 1.53 ± 0.1 1.49 ± 0.12 1.43 ± 0.14 1.53 ± 0.1
approx rate bounded GCAIS 1.06 ± 0.04 1.01 ± 0.03 1.09 ± 0.03 1.04 ± 0.05 1.08 ± 0.04
approx rate GCAIS BASE 1.11 ± 0.04 1.08 ± 0.06 1.11 ± 0.05 1.07 ± 0.05 1.14 ± 0.06
Our other dataset (Fridge-2) is tougher to solve for the is unable to find optimal solutions. Hence we could not ob-
considered metaheuristics as only the bounded GCAIS vari- serve the same positive effects of the usage of epsilon dom-
ant without epsilon dominance always achieves optimal re- inance as Joshi et al. (2015) did for the Knapsack problem.
sults. Once more the results show that this variant can The pure bounded version always achieved optimal results
drastically cut down memory usage and runtime. GSEMO and achieved high values in our other KPIs as well.
has an even shorter runtime and memory usage but on the Most of the observed differences can be explained by tak-
other hand only achieves approximation rates of about three. ing a look at the population growth and size which we visu-
These differences between GSEMO and our bounded ver- alized in Figures 2 and 3. The base variant and pure epsilon
sion of GCAIS are due to GSEMO’s convergence to an in- dominance variants of GCAIS show an exponential growth
ferior solution. GCAIS does not get stuck (as it always finds for Fridge-1 and on the other dataset we can observe a simi-
optimal solutions) and thus the population continues to grow lar observation for epsilon equal to 5. For the other two vari-
as does the runtime. ants the runtime ran out and thus we do not fully see an ex-
On both datasets we could observe that in our case the ponential growth. GSEMO’s population size grows linearly
epsilon dominance has a detrimental effect on the popula- for Fridge-1 and more or less logarithmically for Fridge-2.
tion size and therefore on the runtime. Combined with a Our bounded GCAIS version has, as expected, a constant
bounded population these effects disappear but the method population size (after several iterations). The jumps in the
graphs are due to newly found solutions that dominate other tions is that GCAIS detects dominating solutions more eas-
solutions in the population which get deleted. These differ- ily, which keep the population in bounds. Hence we think
ent growths are one of the causes for the differences in speed that the problem structure of test specifications differs from
up as all of the considered algorithms have a runtime which these more theoretical MSCP instances.
depends on this magnitude.
The growths in terms of population size can be explained Future Work
by taking a look at the structure of our datasets and the prob-
lem itself. Our test specifications consist out of test cases From an engineering perspective we intend to roll out our
that have similar sizes and only slightly overlap in terms version of GCAIS in the company. We further want to gather
of the requirements which they cover. Also, the two di- more datasets from different test levels to verify our ap-
mensions (covered requirements and used tests) are integers proach. We take special interest in the evolution of the re-
and there are only limited valid values. Thus there can be quirements and tests over the lifetime of a project. Thus we
many solutions that cover the same amount of requirements could examine if the reuse of past populations is an advan-
and use the same tests and it is hard to find solutions which tage.
dominate large portions of the population. If the tests would Our next scientific goal is to apply the GCAIS approach
highly differ in their size then it would be easier to find dom- to the adaptive test case selection problem (ATCS) (Spieker
inating solutions which would lead to smaller populations. et al., 2018). Its goal is to find a test suite that maximizes a
Next to our visual evaluation and the discussion of the test metric such as coverage whilst maintaining a test suite
raw values of Table 1, we perform additional statistical test- that has a bounded duration (for its execution). In the case
ing to confirm our observations. We test each KPI and each of coverage, the problem becomes a variant of the weighted
dataset individually. Our null hypothesis is that the algo- MSCP and GCAIS could be applied. In this case the prob-
rithms do not differ on one dataset regarding one KPI. This lem landscape varies even more over time as newly written
can be verified using a Friedman test. On all different null test cases are being added and their duration might change
hypotheses we observed p-values below 10−10 which we re- over time (as the software to be tested might be changed).
gard as significant. Thus we conclude that the algorithms A reuse of GCAIS’ population might lead in this case to a
differ in terms of the KPIs. self-improving system as it is continuously adapted and op-
Overall we are able to reduce the size of original test timised towards the new testing environment.
suites by over 30 percent.
Beasley’s OR Library
Conclusion
Due to the results on the industrial datasets and the spatial re- We introduced a test suite reduction problem which is a vari-
strictions we focus solely on the base variant of GCAIS, the ant of minimum set cover problem (MSCP). Its goal is to find
bounded variant without epsilon dominance, and GSEMO a test suite of minimal size that still covers all requirements.
during this experiment. We evaluate the scpe1 to scpe5 in- A state of the art approach for the MSCP is the germinal
stances of Beasley’s OR library. centre artificial immune systems (GCAIS) which has been
We displayed the experimental results in Table 2. Once heavily benchmarked on rather theoretical instances.
more the population boundaries for GCAIS lead to a cut GCAIS maintains a population of non-dominated solu-
down in terms of memory and runtime. Further, they reveal tions whose calculation cost is quadratic. We apply a sim-
that our adapted version of GCAIS did not lose its capability ple datastructure and an incremental update approach that
to find close to optimal or optimal solutions on these more allows us to reduce the cost to a linear one.
theoretical instances. In all cases our version was even su- Our experiments revealed that on our test specifications,
perior to the base variant. However, in three out of five cases the populations of the standard variant of GCAIS explode
GSEMO was once more faster than our bounded version as which leads to a high memory consumption and longer run-
it once more converged towards a suboptimal solution. times. Thus we adapted GCAIS by applying fixed popu-
We verified our observations about the bounded GCAIS’ lation capacities. Our improved variant could not only cut
superiority in terms of memory usage and approximation down runtime and memory usage compared to the standard
quality using one-sided Wilcoxon signed-rank tests. The p- variant, it was also able to find optimal or close to optimal
values were below 0.05 which we regard as significant. solutions on our industrial data as well as on the more theo-
Further, on these datasets the population of the base vari- retical instances of Beasley’s OR library.
ant of GCAIS does not grow as much as during our evalua-
tion of the industrial datasets. This explains why the mem- Acknowledgement
ory savings are lower. The smaller populations thus lead to
a smaller runtime which unfolds in smaller speed ups for We would like to thank Oliver Banf who helped us acquiring
the other algorithms. The reason for the smaller popula- the industrial data.
References Joshi, A., Rowe, J. E., and Zarges, C. (2015). Improving the per-
Azuaje, F. (2003). Review of “artificial immune systems: A formance of the germinal center artificial immune system us-
new computational intelligence approach” by l.n. de castro ing epsilon-dominance: A multi-objective knapsack problem
and j. timmis (eds) springer, london, 2002. Neural Netw., case study. In Ochoa, G. and Chicano, F., editors, Evolu-
16(8):1229. tionary Computation in Combinatorial Optimization, pages
114–125, Cham. Springer International Publishing.
Balaji, S. and Revathi, N. (2016). A new approach for solving set
covering problem using jumping particle swarm optimization Kumar, V. (2002). Introduction to Parallel Computing. Addison-
method. 15(3):503–517. Wesley Longman Publishing Co., Inc., USA, 2nd edition.
Börzsönyi, S., Kossmann, D., and Stocker, K. (2001). The skyline Li, Y., Hu, X., and Zhang, J. (2009). A new genetic algorithm
operator. In Proceedings of the 17th International Conference for the set k-cover problem in wireless sensor networks. In
on Data Engineering, page 421–430, USA. IEEE Computer 2009 IEEE International Conference on Systems, Man and
Society. Cybernetics, pages 1405–1410.
Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. (2003). Skyline Minotra, D. (2008). A study of heuristic-algorithms for set-
with presorting. pages 717– 719. covering problems.
Dinur, I. and Steurer, D. (2014). Analytical approach to parallel Müller-Schloer, C. and Tomforde, S. (2017). Organic computing –
repetition. In Proceedings of the Forty-sixth Annual ACM technical systems for survival in the real world. In Autonomic
Symposium on Theory of Computing, STOC ’14, pages 624– Systems.
633, New York, NY, USA. ACM.
Nurmuliani, N., Zowghi, D., and Powell, S. (2004). Analysis of
Endres, M. and Kießling, W. (2015). Parallel skyline computation requirements volatility during software development life cy-
exploiting the lattice structure. Journal of Database Manage- cle. In 2004 Australian Software Engineering Conference.
ment, 26:18–43. Proceedings., pages 28–37.
Endres, M., Roocks, P., and Kießling, W. (2015). Scalagon: An ef- Ren, Z.-G., Feng, Z.-R., Ke, L.-J., and Zhang, Z.-J. (2010). New
ficient skyline algorithm for all seasons. In Database Systems ideas for applying ant colony optimization to the set covering
for Advanced Applications, pages 292–308. problem. Computers & Industrial Engineering, 58(4):774 –
784.
Endres, M. and Weichmann, F. (2017). Index structures for prefer-
ence database queries. In Flexible Query Answering Systems, Spieker, H., Gotlieb, A., Marijan, D., and Mossige, M. (2018). Re-
pages 137–149. inforcement learning for automatic test case prioritization and
selection in continuous integration. CoRR, abs/1811.04122.
Fraser, G. and Wotawa, F. (2007). Redundancy based test-suite
reduction. In Dwyer, M. B. and Lopes, A., editors, Funda- Williamson, D. and Shmoys, D. (2011). The design of approxima-
mental Approaches to Software Engineering, pages 291–305, tion algorithms. The Design of Approximation Algorithms.
Berlin, Heidelberg. Springer Berlin Heidelberg.
Yu, J. J. Q., Lam, A. Y. S., and Li, V. O. K. (2014). Chemical
Giel, O. and Wegener, I. (2003). Evolutionary algorithms and the reaction optimization for the set covering problem. In 2014
maximum matching problem. In Proceedings of the 20th An- IEEE Congress on Evolutionary Computation (CEC), pages
nual Symposium on Theoretical Aspects of Computer Science, 512–519.
STACS ’03, page 415–426, Berlin, Heidelberg. Springer-
Verlag. Yu, Y., Jones, J. A., and Harrold, M. J. (2008). An empirical
study of the effects of test-suite reduction on fault localiza-
Gotlieb, A. and Marijan, D. (2014). Flower: Optimal test suite tion. In Proceedings of the 30th International Conference on
reduction as a network maximum flow. In Proceedings of Software Engineering, ICSE ’08, page 201–210, New York,
the 2014 International Symposium on Software Testing and NY, USA. Association for Computing Machinery.
Analysis, ISSTA 2014, pages 171–180, New York, NY, USA.
ACM. Yu, Y., Yao, X., and Zhou, Z.-H. (2010). On the approximation
ability of evolutionary optimization with application to mini-
Holland, J. H. (1992). Genetic algorithms. Scientific American, mum set cover. Artificial Intelligence, s 180–181.
267(1):66–73.
Hsu, H. and Orso, A. (2009). Mints: A general framework and tool
for supporting test-suite minimization. In 2009 IEEE 31st In-
ternational Conference on Software Engineering, pages 419–
429.
Joshi, A. (2017). The germinal centre artificial immune system.
University of Birmingham.
Joshi, A., Rowe, J. E., and Zarges, C. (2014). An immune-inspired
algorithm for the set cover problem. In Bartz-Beielstein, T.,
Branke, J., Filipič, B., and Smith, J., editors, Parallel Prob-
lem Solving from Nature – PPSN XIII, pages 243–251, Cham.
Springer International Publishing.