Information Technology Reference
In-Depth Information
5.3 Genetic Algorithms
The genetic algorithm (GA) is one of the oldest and most popular evolutionary
algorithms. GAs have been used in a wide variety of applications. There are many
papers and topics about genetic algorithms. See for example, [
10
,
26
,
28
,
35
,
40
].
The basic idea is to simulate the process of natural selection.
Initially, we have a set of randomly generated candidates. The main part of a GA
is an iterative process. The population in each iteration is called a generation. It can
evolve through
inheritance, mutation, selection
and
crossover
.
When using GA to solve a practical optimization problem, we need to represent
each candidate solution as a
chromosome
, which is a sequence/string of values. We
also need a
fitness function
, telling us how good a candidate solution is. The goal is
to
maximize
the value of the fitness function.
Genetic algorithms have been used by various researchers to find covering arrays
and other combinatorial designs.
5.3.1 Applying GA to Obtain the Whole Covering Array
An early work in this area is outlined in Ghazi and Ahmed [
21
]. In the approach,
each chromosome consists of a number of test cases (called
configurations
in Ghazi
and Ahmed [
21
]). The fitness function for evaluating a chromosome is defined to
be the number of distinct pairwise interaction configurations covered by all of the
chromosome's configurations, divided by the total number of possible pairwise in-
teraction configurations
|
2
|
. Here,
2
is the set of all possible pairwise interaction
configurations.
For example, suppose the SUT has 3 parameters, each of which can only take the
value1or2.Then
2
is:
{{
1
,
1
,
−}
,
{
1
,
2
,
−}
,
{
2
,
1
,
−}
,
{
2
,
2
,
−}
,
{
1
,
−
,
1
}
,
{
1
,
−
,
2
}
,
{
2
,
−
,
1
}
,
{
2
,
−
,
2
}
,
{−
,
1
,
1
}
,
{−
,
1
,
2
}
,
{−
,
2
,
1
}
,
{−
,
2
,
2
}}
And its size is 12.
Given a chromosome
C
1
which has two configurations:
.The
set of pairwise interaction configurations covered by
C
1
can be calculated as follows.
For
i
{{
1
,
2
,
2
}
,
{
1
,
1
,
2
}}
2, let
N
i
denote the set of distinct pairwise interaction elements covered
by configuration
i
. Then
=
1
,
N
1
={{
1
,
2
,
−}
,
{
1
,
−
,
2
}
,
{−
,
2
,
2
}}
N
2
={{
1
,
1
,
−}
,
{
1
,
−
,
2
}
,
{−
,
1
,
2
}}
Search WWH ::
Custom Search