Information Technology Reference
In-Depth Information
Mutant population:
V
t
is the set of
NP
individuals in the mutant population at gener-
ation
t
,i.e.,
V
t
=[
V
1
,
V
2
,...,
V
t
NP
].
Trial population:
U
t
is the set of
NP
individuals in the trial population at generation
t
,
i.e.,
U
t
=[
U
1
,
U
2
,...,
U
t
NP
].
To u r :
a newly introduced variable
i
, denoted a tour of the GTSP solution implied by
π
i
=
π
in
,where
the individual
X
i
, is represented as
i
1
,
i
2
,...,
ij
is the assignment
π
π
π
π
of node
j
of the individual
i
in the tour at generation
t
.
Mutant constant:
F
(0
,
2) is a real number constant which affects the differential
variation between two individuals.
∈
Crossover constant:
CR
(0
,
1) is a real number constant which affects the diversity
of population for the next generation.
∈
t
i
X
i
),
Fitness function:
In a minimization problem, the objective function is
f
i
(
π
←
i
denotes the corresponding tour of individual
X
i
.
t
where
π
5.2.1
Solution Representation
In this section, we present a solution representation which enables
DEs
to solve the
GTSP
. Bean [2] suggested an encoding for the
GA
to solve the
GTSP
, where each
set
V
j
has a gene consisting of an integer part between
1
,
V
j
and a fractional part
between [0
,
1]. The integer part indicates which node from the cluster is included in the
tour, and the nodes are sorted by their fractional part to indicate the order. Similarly,
a continuous
DE
can be used to solve the
GTSP
. First, we say each parameter value
represents a cluster for the
GTSP
and is restricted to each cluster size of the GTSP
instances.
From the following example, consider a GTSP instance with
V
=
{
1
,..,
20
}
and
V
1
=
. The parameter values
(
x
j
) can be positive or negative, e.g. for dimension
j
equal to 4.23 and for dimension
j
2 is -3.07, etc. This feature indicates the difference between the random key encoding
and the one in this chapter. Table 5.1 shows the solution representation of the DE for the
GTSP. Then the integer parts of these parameter values (
x
j
) are respectively decoded as
node 4 (the fourth node in
V
1
), node 8 (the third node in
V
2
), node 11 (the first node in
V
3
), and node 18 (the third node in
V
1
).
{
1
,..,
5
}
,
V
2
=
{
6
,,..,
10
}
,
V
3
=
{
11
,..,
15
}
and
V
4
=
{
16
,..,
20
}
Ta b l e 5 . 1 .
Solution Representation
j
1
2
3
4
x
j
4.23
-3.07
1.80
3.76
v
j
4
8
11
18
s
j
0.23
-0.07
0.80
0.76
π
j
8
4
18
11
F
(π)
d
8
,
4
d
4
,
18
d
18
,
11
d
11
,
8
Search WWH ::
Custom Search