Information Technology Reference
In-Depth Information
Ta b l e 2 . 4 .
SPV 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
V
3
, while the fourth node occupies the third position in
V
4
. Extracting these labels show
that the nodes are
;
finally, with respect to the random key values (
s
j
), the smallest position value (SPV)
rule is applied to the random key vector by arranging the values in a non-descending
order
{
4
,
8
,
11
,
18
}
The random key values are
{
0
.
23
,
−
0
.
07
,
0
.
80
,
0
.
76
}
{−
0
.
07
,
0
.
23
,
0
.
76
,
0
.
08
}
to determine the tour
π
{
8
,
4
,
18
,
11
}
. Using equation
2.17, the total tour length is then obtained as
1
j
=1
d
π
j
π
j
+1
+
d
π
m
π
1
=
d
8
,
4
+
d
4
,
18
+
d
18
,
11
+
d
11
,
8
In this approach, a problem may rise such that when the DE update equations are
applied, any parameter value might be outside of the initial search range, which is re-
stricted to the size of each cluster. Let
x
min
[
j
] and
x
max
[
j
] represent the minimum and
maximum value of each parameter value for dimension
j
. Then they stand for the mini-
mum and maximum cluster sizes of each dimension
j
. Regarding the initial population,
each parameter value for the set
V
j
is drawn uniformly from [
m
−
F
(
π
)=
V
j
+ 1
,
V
j
+ 1].Obvi-
ously,
x
max
[
j
] is restricted to [
V
j
+ 1], whereas
x
min
[
j
] is restricted to
−
x
max
[
j
].During
the reproduction of the DE, when any parameter value is outside of the cluster size, it
is randomly reassigned to the corresponding cluster size again.
−
2.3.6
Discrete/Binary Approach
Tasgetiren et al. present for the first time in this chapter, the application of the DDE
algorithm to the GTSP. They construct a unique solution representation including both
cluster and tour information is presented, which handles the GTSP properly when car-
rying out the DDE operations. The Population individuals can be constructed in such
a way that first a permutation of clusters is determined randomly, and then since each
cluster contains one or more nodes, a tour is established by randomly choosing a single
node from each corresponding cluster. For example,
n
j
stands for the cluster in the
j
th
dimension, whereas
j
represents the node to be visited from the cluster
n
j
.
Now, consider a GTSP instance with
N
=
π
{
1
,..,
25
}
where the clusters are
n
1
=
{
1
,..,
5
}
,
n
2
=
{
6
,..,
10
}
,
n
3
=
{
11
,..,
15
}
,
n
4
=
{
16
,..,
20
}
and
n
5
=
{
21
,..,
25
}
.
Table 2.5 shows the discrete/binary solution representation of the DDE for the GTSP.
A permutation of clusters is determined randomly as
.Thismeansthat
the first node is randomly chosen from the fourth cluster (here 16 is randomly chosen);
the second node is randomly chosen from the first cluster (here 5 is randomly chosen);
{
4
,
1
,
5
,
2
,
3
}
Search WWH ::
Custom Search