Information Technology Reference
In-Depth Information
Ta b l e 6 . 2 .
Solution Representation
j
1
2
3
4
5
n
j
3
1
5
2
4
X
π
j
14
5
22
8
16
d
π
j
π
j
+1
d
14
,
5
d
5
,
22
d
22
,
8
d
8
,
16
d
16
,
14
Now, consider a GTSP instance with
N
=
{
1
,..,
25
}
where the clusters are
n
1
=
{
1
,..,
5
}
,
n
2
=
{
6
,..,
10
}
,
n
3
=
{
11
,..,
15
}
,
n
4
=
{
16
,..,
20
}
and
n
5
=
{
21
,..,
25
}
.
Table 6.2 illustrates the example solution in detail.
So, the fitness function of the individual is given by
F
(
π
)=
d
14
,
5
+
d
5
,
22
+
d
22
,
8
+
d
8
,
16
+
d
16
,
14
.
6.2.2
Complete Computational Procedure of DDE
The complete computational procedure of the DDE algorithm for the GTSP problem
can be summarized as follows:
•
Step 1: Initialization
-S t
t
=0,
NP
=100
-
Generate
NP
individuals randomly as in Table 6.2,
X
i
,
i
= 1
,
2
,...,
NP
where
X
i
=
x
i
1
,
x
i
2
,...,
x
im
.
-
Evaluate each individual
i
in the population using the objective function
f
i
π
X
i
for
i
= 1
,
2
,...,
NP
.
o
i
←
•
Step 2: Update generation counter
-
k
=
k
+ 1
•
Step 3: Generate mutant population
-
For each target individual,
X
i
,
i
= 1
,
2
,...,
NP
, at generation
k
, a mutant individ-
ual,
V
i
=
v
i
1
,
v
i
2
,...,
v
im
, is determined such that:
+
F
X
k
−
1
b
i
V
i
=
X
k
−
1
X
k
−
1
c
i
−
(6.5)
a
i
where
a
i
,
b
i
and
c
i
are three randomly chosen individuals from the population
such that (
a
i
=
b
i
=
c
i
).
•
Step 4: Generate trial population
-
Following the mutation phase, the crossover (re-combination) operator is ap-
plied
individual,
V
i
to
obtain
the
trial
population.
For
each
mutant
=
v
i
1
,
v
i
2
,...,
v
im
, an integer random number between 1 and
n
, i.e.,
D
i
∈
=
u
i
1
,
u
i
2
,...,
u
im
is generated
(1
,
2
,...,
m
), is chosen, and a trial individual,
U
i
such that:
u
ij
=
v
ij
,
if r
ij
≤
CR or j
=
D
i
(6.6)
x
k
−
1
ij
,
Ot herwise
where the index
D
refers to a randomly chosen dimension (
j
= 1
,
2
,...,
m
), which
is used to ensure that at least one parameter of each trial individual
U
i
differs
Search WWH ::
Custom Search