Discrete/Binary Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 143

trial individual is chosen as U i = V i . By doing so, the trial individual is made up either
from the outcome of perturbation operator or from the crossover operator. Equation 6.2
will be denoted as U i := P c

CR V i , X k − 1

⊕ .

i

i :=1 , 2 ,.., NP

Finally, the selection operator is carried out based on the survival of the fitness among
the trial and target individuals such that:
X i = U i

if f π U i < f π

k − 1

X k − 1
i

i

← ←

i

(6.3)

X k − 1
i

ot herwise

Equation 6.3 will be denoted as X i = arg min f π U i , f π

k
i

k − 1
i

X k − 1
i

← ← .

i :=1 , 2 ,.., NP

6.2.1 Solution Representation

We employ a path representation for the GTSP in this chapter. In the path representa-
tion, each consecutive node is listed in order. A disadvantage of this representation is
due to the fact that there is no guarantee that a randomly selected solution will be a
valid GTSP tour because there is no guarantee that each cluster is represented exactly
once in the path without some repair procedures. To handle the GTSP, we include both
cluster and tour information in the solution representation. The solution representation
is illustrated in Table 6.1 where d π j π j +1

j +1 .
Population individuals can be constructed in such a way that first a permutation of clus-
ters is determined randomly, and then since each cluster contains one or more nodes, a
tour is established by randomly choosing a single node from each corresponding clus-
ter. For example, n j stands for the cluster in the j th

shows the distance from node π

j to node

π

dimension, whereas π j represents

the node to be visited from the cluster n j .

Ta b l e 6 . 1 . Solution Representation

j 1 ... m − 1 m

n j n 1 ... n m − 1 n m

π j π 1 ... π m − 1 π m

X d π j π j +1 d π 1 π 2 ... d π m − 1 π m d π m π 1

m
j =1 d π j π j +1 + d π m π 1

d π 1 π 2 ... d π m − 1 π m d π m π 1

As illustrated in Table 6.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 ( π )= (6.4)