Information Technology Reference
In-Depth Information
Outline of QAP2
QAP2
1. Input: square matrices
M
1
and
M
2
each of dimension
n
, along with parameter
settings to pass to NMinimize.
2. Form a vector of variables of length
n
−
1. For
j
in
{
1
,...,
n
−
1
}
constrain the
.
3. Form an objective function that sums the
n
2
products of elements of the first
matrix and elements of the row-and-column permuted second matrix. The vari-
ables vector, with entries rounded to nearest integers, may be viewed as a
shuffle on a set of
n
elements. The permutation is determined by invoking
getPerm
on the variables vector.
4. Call
NMinimize
on the objective function, using the above variables, con-
straints, and input option settings.
5. Return the minimal value found, along with the permutation that gives rise to
that value.
jth variable to lie in the range
{
j
−
.
499
...,
n
+ 1
.
499
}
QAP2[mat1
,
mat2
,
cp
,
it
,
sp ]:=Module[
QAP2[mat1
,
mat2
,
cp
,
it
,
sp ]:=Module[
{
{
{
len = Length[mat1]
−
−
−
1
,
obfunc
,
vars
,
x
,
nmin
,
vals
,
constraints
1
,
obfunc
,
vars
,
x
,
nmin
,
vals
,
constraints
1
,
obfunc
,
vars
,
x
,
nmin
,
vals
,
constraints
}
}
}
,
,
,
len = Length[mat1]
len = Length[mat1]
vars = Array[
x
,
len];
vars = Array[
x
,
len];
constraints = Map[(#[[1]]
constraints = Map[(#[[1]]
constraints = Map[(#[[1]]
−
−
−
.
499
.
499
.
499
≤
≤
≤
#
#
#
≤
≤
≤
len + 1
.
499)&
,
vars];
len + 1
.
499)&
,
vars];
len + 1
.
499)&
,
vars];
obfunc[vec :
obfunc[vec :
obfunc[vec :
{
{
{
Real
Real
Real
}
}
}
]:=
]:=
]:=
To tal[Flatten[mat1
To tal[Flatten[mat1
To tal[Flatten[mat1
∗
∗
∗
permuteMatrix[mat2
,
getPerm[Round[vec]]]]];
permuteMatrix[mat2
,
getPerm[Round[vec]]]]];
permuteMatrix[mat2
,
getPerm[Round[vec]]]]];
{
{
{
nmin
,
vals
nmin
,
vals
nmin
,
vals
}
}
}
= NMinimize[
= NMinimize[
= NMinimize[
{
{
{
obfunc[vars]
,
constraints
obfunc[vars]
,
constraints
obfunc[vars]
,
constraints
}
}
}
,
vars
,
,
vars
,
,
vars
,
Method
Method
Method
→{
→{
→{
DifferentialEvolution
,
SearchPoints
DifferentialEvolution
,
SearchPoints
DifferentialEvolution
,
SearchPoints
→
→
→
sp
,
CrossProbability
sp
,
CrossProbability
sp
,
CrossProbability
→
→
→
cp
,
cp
,
cp
,
PostProcess
PostProcess
PostProcess
→
→
→
False
False
False
}
}
}
,
MaxIterations
,
MaxIterations
,
MaxIterations
→
→
→
it
,
Compiled
it
,
Compiled
it
,
Compiled
→
→
→
False];
False];
False];
{
{
{
nmin
,
getPerm[Round[vars/.vals]]
nmin
,
getPerm[Round[vars/.vals]]
nmin
,
getPerm[Round[vars/.vals]]
}
}
}
]
]
]
We show a sample tuning run. We keep the number of iterations and number of chro-
mosomes modest, and try cross probabilities between 0.05 and 0.95, at increments of
.05.
Quiet[Tab le[
Quiet[Tab le[
Quiet[Tab le[
{
{
{
j
,
First[QAP2[mat1
,
mat2
,
j
/
100
,
50
,
20]]
j
,
First[QAP2[mat1
,
mat2
,
j
/
100
,
50
,
20]]
j
,
First[QAP2[mat1
,
mat2
,
j
/
100
,
50
,
20]]
}
}
}
,
,
,
{
{
{
j
,
5
,
95
,
5
j
,
5
,
95
,
5
j
,
5
,
95
,
5
}
}
}
]]
]]
]]
{{
5
,
4364
.
}
,
{
10
,
4436
.
}
,
{
15
,
4538
.
}
,
{
20
,
4428
.
}
,
{
25
,
4522
.
}
,
{
30
,
4506
.
}
,
{
35
,
4518
.
}
,
{
40
,
4550
.
}
,
{
45
,
4512
.
}
,
{
50
,
4456
.
}
,
{
55
,
4530
.
}
,
{
60
,
4474
.
}
,
{
65
,
4520
.
}
,
{
70
,
4412
.
}
,
{
75
,
4474
.
}
,
{
80
,
4454
.
}
,
{
85
,
4410
.
}
,
{
90
,
4314
.
}
,
{
95
,
4324
.
}}
From this we home in on the region of the larger values since they seem to be consis-
tently a bit better than other values (it is interesting that this is the opposite of what I
had found for the relative index positioning approach in the previous subsection). We
Search WWH ::
Custom Search