Information Technology Reference
In-Depth Information
Table 6.13.
Two-Cut PTL Crossover Operator
j
1
2
3
4
5
P1
n
j
5
1
4
2
3
π
j
24
3
19
8
14
P2
n
j
5
1
4
2
3
π
j
24
3
19
8
14
O1
n
j
4
2
5
1
3
π
j
19
8
24
3
14
O2
n
j
5
1
3
4
2
π
j
24
3
14
19
8
Step 1.a.
Choose
d
= 2 nodes with corresponding clusters, randomly.
Step 1.b
. Establish
D
=
,
n
D
=
R
=
and
n
R
=
π
{
14
,
22
,
16
}
{
3
,
5
,
4
}
,
π
{
5
,
8
}
{
1
,
2
}
.
R
=
R
=
by randomly choosing
n
2
= 2intheset
Step 1.c.
Perturb
π
{
5
,
8
}
to
π
{
5
,
9
}
n
R
=
, and randomly replacing
n
2
= 8 with
n
2
= 9 from the same cluster
n
2
.
Step2.a
. After the best insertion of node
{
1
,
2
}
1
= 5 and the cluster
1
= 1.
π
π
Step2.b.
After the best insertion of node
n
2
= 9 and the cluster
R
1
= 2.
π
F
(
π
)=
d
5
,
22
+
d
22
,
16
+
d
16
,
14
+
d
14
,
8
+
d
8
,
5
6.2.6
PTL Crossover Operator
Two-cut PTL crossover operator developed by Pan et al. [21] is used in the DDE algo-
rithm. The two-cut PTL crossover operator is able to produce a pair of distinct offspring
even from two identical parents. An illustration of the two-cut PTL cross-over operator
is shown in Table 6.13.
In the PTL crossover, a block of nodes and clusters from the first parent is determined
by two cut points randomly. This block is either moved to the right or left corner of the
offspring. Then the offspring is filled out with the remaining nodes and corresponding
clusters from the second parent. This procedure will always produce two distinctive
offspring even from the same two parents as shown in Table 6.13. In this chapter, one
of these two unique offspring is chosen randomly with an equal probability of 0.5.
6.2.7
Insert Mutation Operator
Insert mutation operator is a modified insert mutation considering the clusters in the so-
lution representation. It is also used in the perturbation of the solution in the destruction
and construction procedure. It is basically related to removing a node from a tour of an
individual, and replacing that particular node with another one from the same cluster. It
is illustrated in Table 6.14.
As shown in Table 6.14, the cluster
n
2
= 5 is randomly selected and its corresponding
node
π
2
= 23 is replaced by node
π
2
= 22 from the same cluster
n
2
= 5.
Search WWH ::
Custom Search