Information Technology Reference
In-Depth Information
Ta b l e 5 . 3 .
Clusters for the Instance 11EIL51
Cluster
Node
j
1
2
3
4
5
6
7
8
9
10
11
x
j
3.45
-2.66
1.86
1.11
-3.99
-6.24
-2.81
4.52
6.23
-1.89
3.02
v
j
41
20
24
33
27
50
22
25
44
1
10
s
j
0.45
-0.66
0.86
0.11
-0.99
-0.24
-0.81
0.52
0.23
-0.89
0.02
π
j
27
1
22
20
50
10
33
44
41
25
24
d
π
j
π
j
+1
d
27
,
1
d
1
,
22
d
22
,
20
d
20
,
50
d
50
,
10
d
10
,
33
d
33
,
44
d
44
,
41
d
41
,
25
d
25
,
24
d
24
,
27
F
(π) 8
7
15
21
17
12
17
20
21
14
22
V
9
=
{
4
,
15
,
17
,
37
,
42
,
44
,
45
}
,
V
10
=
{
1
,
6
,
7
,
23
,
48
}
,and
V
11
=
{
5
,
9
,
10
,
30
,
38
,
49
}
.
To make clearer, we show the 11EIL51 instance in Table 5.2 below:
In order to establish the GTSP solution, each parameter value for the dimension j
is restricted to each cluster size such that
−
4
<
x
1
<
4,
−
5
<
x
2
<
5,
−
3
<
x
3
<
3,
−
3
<
x
4
<
3,
−
8
<
x
5
<
8,
−
7
<
x
6
<
7,
−
6
<
x
7
<
6,
−
5
<
x
8
<
5,
−
8
<
x
9
<
8,
7
<
x
11
<
7. This provides the feasibility of the GTSP solution
generated by the DE algorithm. Suppose that a DE solution is obtained by the traditional
update equations and the parameter values
x
j
s
of the individual are given as in Table
5.3.
Similar to what we have explained via Table 5.1 example, the integer parts of the
individual parameter values (
x
j
) are respectively decoded as node 41 (the third node
in
V
1
), node 20 (the second node in
V
2
), node 24 (the first node in
V
3
), node 33 (the
first node in
V
4
), node 27 (the third node in
V
5
), node 50 (the sixth node in
V
6
), node
22 (the second node in
V
7
), node 25 (the fourth node in
V
8
), node 44 (the sixth node in
V
9
), node 1 (the first node in
V
10
) and node 10 (the third node in
V
11
). Unlike the case
in the RKGA, where the random key is defined as another vector, the fractional part of
the individual parameter values (
x
j
) can be directly obtained as a random key to obtain
the tour. As shown in Table 5.3, while applying the SPV rule to the random key vector
(
s
j
), the tour (
−
6
<
x
10
<
6and
−
π
j
) can be obtained very easily. As well, the objective function value of
the individual
X
is given by
10
j
=1
d
π
j
π
j
+1
+
d
π
10
π
1
=
d
27
,
1
+
d
1
,
22
+
d
22
,
20
+
d
20
,
50
+
d
50
,
10
+
d
10
,
33
+
d
33
,
44
+
d
44
,
41
+
d
41
,
25
+
d
25
,
24
+
d
24
,
27
F
(
π
)=
10
j
=1
d
π
j
π
j
+1
+
d
π
11
π
1
= 8 + 7 + 15 + 21 + 17 + 12+ 17 + 20+ 21 + 14+ 22 = 174
F
(
π
)=
5.2.3
Complete Computational Procedure of DE
The complete computational procedure of the DE algorithm for the GTSP problem can
be summarized as follows:
Search WWH ::
Custom Search