Information Technology Reference
In-Depth Information
another mixed 0-1 formulation for the long chain design problem. This formula-
tion contains the quadratic assignment problem as a special case. The equivalent
reformulation is given as follows:
(
EP
)
minD
◦
(
XLY
)
x
i,j
=1
j
∈
J
(5)
i∈I
x
i,j
=1
i
∈
I
(6)
j∈J
y
i,j
=1
j
∈
J
(7)
i
∈
I
y
i,j
=1
i
∈
I
(8)
j∈J
x
i,j
,y
i,j
∈{
0
,
1
}
i
∈
I,j
∈
J
(9)
B
=
i,j
=1
,··· ,n
A
i,j
B
i,j
=
Trace
(
A
T
B
),
D
is the constant distance matrix, i.e., [
D
]
i,j
=
d
i,j
,and
L
can
be chosen as any feasible solution in formulation (P).
Note that decision matrix variables
X
=[
x
i,j
]
n×n
and
Y
=[
x
i,j
]
n×n
are called
permutation matrix variables because multiplying a matrix A from the left by a
permutation matrix X results in a permutation of rows of A, and multiplying a
matrix A from the right by
X
T
has the same effect on the columns of A. Thus
for any solution of (P), i.e., any long chain, encoded by matrix
L
, we can still
obtain a long chain by permutation operations
XLY
.Thusitisclearthat(EP)
is equivalent to (P).
where matrix inner product
◦
is defined as
A
◦
4.2 Hybrid Genetic Algorithm
n×n
, we can encode it into
Note that for each permutation matrix
X
∈{
0
,
1
}
a vector
x
=(
i
1
i
2
···
i
n
), which is a permutation of the integers from 1 to
n
.
Based on the reformulation (EP), we present a hybrid genetic algorithm which
contains initialization, selection, crossover, mutation and 2-opt exchange local
search.
The main body of HGA is given as follows:
1. Initialization.
Run 2-approximation algorithm and let its solution be
L
∗
=
[
x
i,j
]
n×n
.Set
L
=
L
∗
and randomly generate
x,y
from the natural order.
2. Selection.
Calculate objective value function for each individual, evaluate each
individual by inverse of its objective value and select new generation by Roulette
wheel selection method.
3. Crossover.
According to the crossover probability, select certain individuals
and exchange their permutation vector
x
.
Search WWH ::
Custom Search