Differential Evolution for Permutation-Based Combinatorial Problems - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 25

Mathematically the facility location problem can be formulated as

n
j =1 c j y j +

m
∑
i =1

n
j =1 d ij x ij min

n
j =1 x ij = K

s . t . ∀ i

(2.7)

x ij ≤ y j ∀ i , j

x ij , y j ∈{ 0 , i }∀ i , j

2.3 Permutation-Based Combinatorial Approaches

This section describes two permutation based combinatorial DE approaches which

were merely described in [10] and three other permutation

−

− based combinatorial DE

approaches which are detailed in this topic.

2.3.1 The Permutation Matrix Approach

The permutation matrix approach is the idea of Price, but Storn did the experiments that
document its performance [10]. The permutative matrix approach is based on the idea
of finding a permutative matrix that relates two vectors. For example, given two vectors
x r 1 and x r 1 defined in Equation 2.8:

⎛
⎝

⎞
⎠

⎛
⎝

⎞
⎠

1
3
4
5
2

1
4
3
5
2

x r 1 = , x r 2 = ; (2.8)

These two vectors encode tours, each of which is a permutation. The permutation
matrix, P ,that x r 1 and x r 1 is defined as:

⎛ ⎞

10000
00100
01000
00010
00001

⎝ ⎠

x r 2 = P . x r 1 , with P = (2.9)

for(i = 1; i < M; i ++) // search all columns of P
{ if(elementp(i , i) of P is 0) // 1 not on diagonal
{ if(rand() > δ

del) // if random number ex [0 , 1] exceeds δ del

{ j = 1; // find row where p(j , i)=1
while(p(j , i)! = 1)j ++;
}
}
}

Fig. 2.8. Algorithm to apply the factor δ to the difference permutation, P