Information Technology Reference
In-Depth Information
c
3
c
3
c
3
c
2
c
2
c
2
c
4
c
4
c
4
c
5
c
5
c
5
c
1
c
1
c
1
A
1
A
2
1, 2
=
A
1
A
2
Fig. 2.9.
Graphical interpretations of
A
1
,
A
2
and the difference matrix Δ
ij
instance of four cities that define a tour such that these are initially generated by DE as
x
1
,
f
=
{
0
.
50
.
80
.
20
.
6
}
. Another instance of such four cities could simple be simply
defined as
x
2
,
f
=
{
0
.
60
.
10
.
30
.
4
}
. In relative indexing, these instances encode per-
mutations given as
x
1
=
respectively. In the first case
for example the lowest value which is 0.2 is in the third position so it is allocated a label
of 1; the next higher value is 0.5 which occupies the first position and it is allocated the
label 2 and so on. Let there be a third instance denoted as
x
3
,
f
=
{
24 1 3
}
and
x
2
=
{
4123
}
{
0
.
60
.
80
.
30
.
5
}
.
Then we have
x
3
=
{
341 2
}
. The concept is fairly simple. The subscript
f
indicates
floating point.
The basic idea behind DE is that two vectors define a difference that can then be
added to another vector as a mutation. The same idea transfers directly to the realm
of permutations, or the permutation group. Just as two vectors in real space define a
difference vector that is also a vector, two permutations define a mapping that is also
a permutation. Therefore, when mutation is applied to with F = 0.5, the floating-point
mutant vector,
v
f
,is
v
f
=
x
r
3
,
f
+
F
x
r
1
,
f
−
x
r
2
,
f
=
{
0
.
60
.
80
.
30
.
5
}
+ 0
.
5
{−
0
.
10
.
7
−
0
.
10
.
2
}
(2.14)
=
{
0
.
55 1
.
15 0
.
25 0
.
6
}
The floating-point mutant vector,
v
f
, is then transformed back into the integer do-
main by assigning the smallest floating value (0.25) to the smallest integer (1), the
next highest floating value (0.55) to the next highest integer (2), and so on to ob-
tain
v
=
. [10] noted that this backward transformation, or “relative position
indexing”, always yields a valid tour except in the unlikely event that two or more
floating
{
24 1 3
}
point values are the same. When such an event occurs, the trial vector must be
either discarded or repaired.
−
2.3.4
Forward/Backward Transformation Approach
The forward/backward transformation approach is the idea of [6], and is generally re-
ferred to as Onwubolu
s approach [10]. There are two steps involved:
Search WWH ::
Custom Search