Computational Intelligence - May 2017 - 49
value with a cost function. Similarly, Lin [10]
For ATCG-PC, the solving difficulty mainly arises from
used Hamming distance to redesign the fitness function. All of the mentioned fitness
the search space landscape (i.e., the cardinality of X)
functions use the same strategy in that the fitand the unknown mapping from X to P. An optimal
ness function is calculated based on a ranset of test cases can be found if the mapping from
domly generated path. The random path helps
to search in a large space, but it produces little
X to P is known. In this sense, we argue that some
heuristic information to reveal the mapping
information of the mapping, if available, is helpful to
from X to P because of its randomness.
solve ATCG-PC efficiently.
In this study, rather than using the strategy
of random paths, we designed a self-adaptive
fitness function to prompt the meta-heuristic
algorithm to use more information from the found paths. The
IV. Modified Differential Evolution for ATCG-PC
problem of ATCG-PC requires as small a number of test cases
With the proposed fitness function, many meta-heuristic algoas possible for complete path coverage. One of the most effirithms, such as GA, PSO, and ACO can be used to solve the
cient approaches to saving the test cases is to generate test cases
problem of ATCG-PC. We plan to choose the one to impleby using the heuristic information of the found paths. Therement the proposed fitness function. The performance of
fore, the proposed fitness function is designed to be adaptively
fitness(x) focuses on using the heuristic information generated
calculated according to the found paths. Specifically, we define
from the found paths to produce new solutions. Hence, we
the fitness value of test case x (i.e., fitness(x)) by Exp. (4).
chose the meta-heuristic algorithm that makes the most use of
the found solutions to produce new solutions. DE [4], [19],
h (p x)
[23], [24] is an algorithm of this kind.
(4)
fitness (x) = / j = 1 f (p x, j)
In each iteration of DE, every individual of the population
is used as a basis for producing a candidate solution with other
where h ( p x) is the vertex number of the path p x, and f (p x, j)
randomly selected solutions found by DE [25], [26]. This propis the evaluation value of the j-th vertex of p x . The proposed
erty results from the mutation and crossover operators of DE
f ( p x, j ) has two strategies to make use of the heuristic infor[19], [24].
mation from the found paths.
Exp. (6) is the formula of DE mutation.
The first strategy is to reduce the fitness value of the vertex
that is the initial vertex of the edges of the found paths. The
value of f (p x, j) will be zero if all of the edges whose initial
v i = y i + F $ (y j - y k)
(6)
vertex is the j-th vertex of p x are in the covered paths. In this
where v i is the new solution, y i is the mutated solution, y j and
case, the j-th vertex is considered to be non-contributing for
uncovered paths.
y k are randomly selected solutions, and F is a factor parameter
The second strategy is to evaluate the vertex that is the iniin [0,1]. y i, y j, y k and v i are candidate test cases for ATCG-PC.
tial vertex of the uncovered edge. If there exist some uncovered
Exp. (7) is the formula of DE crossover.
branches from the j-th vertex of p x, f (p x, j) will be calculated
by Exp. (5).
v ij, rand ij # Pc and j = j rand
(7)
y ij = )
y ij, rand ij 2 Pc or j ! j rand
f (p x, j ) = 1/(cost (v xj) + f)
(5)
where v xj is the j-th branch vertex of p x, f is a small constant
to avoid a zero denominator, and cost (v xj) is the cost function
[13] described by Table 1.
Following the advice [6], [13] about evaluating predicates of
software test, the vertex with uncovered branches will get a fitness value to contribute to the fitness value of the generated
path according to Exp. (4). The corresponding solution (test
case) will have more chances to produce its offspring (test case)
due to a higher fitness value. A new path will be covered if one
uncovered branch can be covered by the generated test case.
The proposed fitness function aims to lead the meta-heuristic algorithm to produce more uncovered paths based on
the found paths. The fitness value of the test case is in direct
proportion to the number of uncovered branches of its
found path.
TABLE 1 Calculation of Function cost(v)
PREDICATE OF v
cost(v ) FUNCTION
BOOLEAN
IF TRUE THEN 0 ELSE K
A2B
IF (B - A) 1 0 THEN 0 ELSE (B - A) + K
A$B
IF (B - A) # 0 THEN 0 ELSE (B - A) + K
A1B
IF (A - B) 1 0 THEN 0 ELSE (A - B) + K
A#B
IF (A - B) # 0 THEN 0 ELSE (A - B) + K
A =B
IF A - B = 0 THEN 0 ELSE A - B + K
A!B
IF A - B ! 0 THEN 0 ELSE K
A/B
cost (A) + cost (B)
A0B
MIN(cost(A), cost(B))
may 2017 | IEEE ComputatIonal IntEllIgEnCE magazInE
49
Table of Contents for the Digital Edition of Computational Intelligence - May 2017
Computational Intelligence - May 2017 - Cover1
Computational Intelligence - May 2017 - Cover2
Computational Intelligence - May 2017 - 1
Computational Intelligence - May 2017 - 2
Computational Intelligence - May 2017 - 3
Computational Intelligence - May 2017 - 4
Computational Intelligence - May 2017 - 5
Computational Intelligence - May 2017 - 6
Computational Intelligence - May 2017 - 7
Computational Intelligence - May 2017 - 8
Computational Intelligence - May 2017 - 9
Computational Intelligence - May 2017 - 10
Computational Intelligence - May 2017 - 11
Computational Intelligence - May 2017 - 12
Computational Intelligence - May 2017 - 13
Computational Intelligence - May 2017 - 14
Computational Intelligence - May 2017 - 15
Computational Intelligence - May 2017 - 16
Computational Intelligence - May 2017 - 17
Computational Intelligence - May 2017 - 18
Computational Intelligence - May 2017 - 19
Computational Intelligence - May 2017 - 20
Computational Intelligence - May 2017 - 21
Computational Intelligence - May 2017 - 22
Computational Intelligence - May 2017 - 23
Computational Intelligence - May 2017 - 24
Computational Intelligence - May 2017 - 25
Computational Intelligence - May 2017 - 26
Computational Intelligence - May 2017 - 27
Computational Intelligence - May 2017 - 28
Computational Intelligence - May 2017 - 29
Computational Intelligence - May 2017 - 30
Computational Intelligence - May 2017 - 31
Computational Intelligence - May 2017 - 32
Computational Intelligence - May 2017 - 33
Computational Intelligence - May 2017 - 34
Computational Intelligence - May 2017 - 35
Computational Intelligence - May 2017 - 36
Computational Intelligence - May 2017 - 37
Computational Intelligence - May 2017 - 38
Computational Intelligence - May 2017 - 39
Computational Intelligence - May 2017 - 40
Computational Intelligence - May 2017 - 41
Computational Intelligence - May 2017 - 42
Computational Intelligence - May 2017 - 43
Computational Intelligence - May 2017 - 44
Computational Intelligence - May 2017 - 45
Computational Intelligence - May 2017 - 46
Computational Intelligence - May 2017 - 47
Computational Intelligence - May 2017 - 48
Computational Intelligence - May 2017 - 49
Computational Intelligence - May 2017 - 50
Computational Intelligence - May 2017 - 51
Computational Intelligence - May 2017 - 52
Computational Intelligence - May 2017 - 53
Computational Intelligence - May 2017 - 54
Computational Intelligence - May 2017 - 55
Computational Intelligence - May 2017 - 56
Computational Intelligence - May 2017 - 57
Computational Intelligence - May 2017 - 58
Computational Intelligence - May 2017 - 59
Computational Intelligence - May 2017 - 60
Computational Intelligence - May 2017 - 61
Computational Intelligence - May 2017 - 62
Computational Intelligence - May 2017 - 63
Computational Intelligence - May 2017 - 64
Computational Intelligence - May 2017 - 65
Computational Intelligence - May 2017 - 66
Computational Intelligence - May 2017 - 67
Computational Intelligence - May 2017 - 68
Computational Intelligence - May 2017 - 69
Computational Intelligence - May 2017 - 70
Computational Intelligence - May 2017 - 71
Computational Intelligence - May 2017 - 72
Computational Intelligence - May 2017 - Cover3
Computational Intelligence - May 2017 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com