Information Technology Reference
In-Depth Information
Price gives an algorithm that scales the effect of the permutation matrix as shown in
Fig 2.8.
2.3.2
Adjacency Matrix Approach
Storn developed the adjacency matrix approach outlined in this section [10]. There are
some rules that govern the adjacency matrix approach. When tours are encoded as city
vectors, the difference between rotated but otherwise identical tours is never zero. Ro-
tation, however, has no effect on a tour
s representation if it is encoded as an adjacency
matrix. Storn defined the notation
(
x
+
y
) mod 2 =
x
⊕
y
(2.10)
which is shorthand for modulo 2 addition, also known as the “exclusive or” logical
operation for the operation of the matrices. The difference matrix
Δ
ij
,
⊕
Δ
ij
=
A
i
A
j
(2.11)
is defined as the analog of DE
s traditional difference vector. Consider for example, the
valid TSP matrices
A
1
and
A
2
,
⎛
⎞
⎛
⎞
01001
10010
00011
01100
10100
01001
10100
01010
00101
10010
⎝
⎠
⎝
⎠
A
1
=
,
A
2
=
,
(2.12)
and their difference given as
⎛
⎝
⎞
⎠
00000
00110
01001
01001
00110
Δ
1
,
2
=
A
1
⊕
A
2
=
(2.13)
From the definition of
A
1
there are 1
s in column 1 in rows
{
2and5
}
, in column 2
there are 1
sinrows
, in column 3 there are 1
sinrows
{
1and4
}
{
4and5
}
, in column 4
there are 1
sinrows
, in column 5 there are 1
sinrows
{
2and3
}
{
1and3
}
respectively.
These pair
−
wise numbers define the adjacency relationships. Considering
{
2and5
}
it is shown that
5
is common and
and
{
4and5
}
{
2and4
}
are adjacent. Considering
it is shown that
1
is common and
{
are adjacent.
Continuing in this manner it could be observed that Fig 2.9 shows the graphical inter-
pretation of
A
1
,
A
2
and
1and4
}
and
{
1and3
}
{
1and3
}
Δ
ij
.
2.3.3
Relative Position Indexing
In the relative position indexing approach [4], permutations are obtained by determin-
ing the relative sizes of the different parameters defining an instance. Let there be an
Search WWH ::
Custom Search