Information Technology Reference
In-Depth Information
Since the values of parameter
x
j
can be positive or negative, to determine which node
(
v
j
) should be taken, the absolute value of the parameter
x
j
needs to be considered. Then
the random key values (
s
j
) are determined by simply subtracting the integer part of the
parameter
x
j
from its current value considering the negative signs, i.e.,
s
j
=
x
j
int (
x
j
).
So for dimension 1, its parameter
x
1
is equal to 4.23 and the random key value
s
1
is
0.23 (
S
1
= 4
.
23
−
−
4). Finally, with respect to the random key values (
s
j
), the smallest
position value (SPV) rule of Tasgetiren et. al. [29] is applied to the random key vector
to determine the tour
. As illustrated in Table 5.1, the objective function value implied
by a solution
x
with
m
nodes is the total tour length, which is given by
π
m
−
1
j
=1
d
π
j
π
j
+1
+
d
π
m
π
1
F
(
π
)=
(5.1)
However, with this proposed representation scheme, 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 restricted 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 minimum and maximum cluster sizes of each dimension
j
.
Regarding the initial population, each parameter value for the set
V
j
is drawn uniformly
from [
−
V
j
+ 1
,
V
j
+ 1]. Obviously,
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 re-assigned to the corresponding cluster size
again.
−
5.2.2
An Example Instance of the GTSP
In this section, we summarize the solution representation by using a GTSP instance of
11EIL51 from TSPLIB Library [23] with
V
=
{
1
,..,
51
}
, where the clusters are
V
1
=
{
19
,
40
,
41
}
,
V
2
=
{
3
,
20
,
35
,
36
}
,
V
3
=
{
24
,
43
}
,
V
4
=
{
33
,
39
}
,
V
5
=
{
11,12,27,32,46,
47,51
}
,
V
6
=
{
2
,
16
,
21
,
29
,
34
,
50
}
,
V
7
=
{
8
,
22
,
26
,
28
,
31
}
,
V
8
=
{
13
,
14
,
18
,
25
}
,
Ta b l e 5 . 2 .
Clusters for the Instance 11EIL51
Cluster
Node
V
1
19
40
41
V
2
3
20
35
36
V
3
24
43
V
4
33
39
V
5
11
12
27
32
46
47
51
V
6
2
16
21
29
34
50
V
7
8
22
26
28
31
V
8
13
14
18
25
V
9
4
15
17
37
42
44
45
V
10
1
6
7
23
48
V
11
5
9
10
30
38
49
Search WWH ::
Custom Search