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