Information Technology Reference
In-Depth Information
alter the objective function than would be the case in the ensemble ordering, as the cor-
responding permutation now depends far less on overall ordering in the chromosomes.
The advantage is that this method will thus be somewhat less in need of intricate tuning
for the crossover probability parameter (but we will do that anyway).
QAP3
Outline of QAP3
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
. Constrain each variable to lie in the
range
.
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 variables 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
getPerm2
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.
{
.
501
...,
n
+
.
499
}
QAP3[mat1
,
mat2
,
cp
,
it
,
sp ]:=Module[
QAP3[mat1
,
mat2
,
cp
,
it
,
sp ]:=Module[
{
{
{
len = Length[mat1]
,
obfunc
,
vars
,
x
,
nmin
,
vals
,
constraints
len = Length[mat1]
,
obfunc
,
vars
,
x
,
nmin
,
vals
,
constraints
len = Length[mat1]
,
obfunc
,
vars
,
x
,
nmin
,
vals
,
constraints
}
}
}
,
,
,
vars = Array[
x
,
len];
vars = Array[
x
,
len];
constraints = Map[(
.
501
constraints = Map[(
.
501
constraints = Map[(
.
501
≤
≤
≤
#
#
#
≤
≤
≤
len + 0
.
499)&
,
vars];
len + 0
.
499)&
,
vars];
len + 0
.
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
,
getPerm2[Round[vec]]]]];
permuteMatrix[mat2
,
getPerm2[Round[vec]]]]];
permuteMatrix[mat2
,
getPerm2[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
,
sp
,
sp
,
CrossProbability
CrossProbability
CrossProbability
→
→
→
cp
,
PostProcess
cp
,
PostProcess
cp
,
PostProcess
→
→
→
False
False
False
}
}
}
,
,
,
MaxIterations
MaxIterations
MaxIterations
→
→
→
it
,
Compiled
it
,
Compiled
it
,
Compiled
→
→
→
False];
False];
False];
{
{
{
nmin
,
getPerm2[Round[vars/.vals]]
nmin
,
getPerm2[Round[vars/.vals]]
nmin
,
getPerm2[Round[vars/.vals]]
}
}
}
]
]
]
We'll start with a tuning run.
Quiet[Tab le[
{
{
{
j
,
First[QAP3[mat1
,
mat2
,
j
/
100
,
50
,
20]]
j
,
First[QAP3[mat1
,
mat2
,
j
/
100
,
50
,
20]]
j
,
First[QAP3[mat1
,
mat2
,
j
/
100
,
50
,
20]]
}
}
}
,
,
,
{
{
{
j
,
5
,
95
,
5
j
,
5
,
95
,
5
j
,
5
,
95
,
5
}
}
}
]]
Quiet[Tab le[
Quiet[Tab le[
]]
]]
{{
5
,
4486
.
}
,
{
10
,
4498
.
}
,
{
15
,
4464
.
}
,
{
20
,
4492
.
}
,
{
25
,
4430
.
}
,
{
30
,
4516
.
}
,
{
35
,
4482
.
}
,
{
40
,
4396
.
}
,
{
45
,
4432
.
}
,
{
50
,
4472
.
}
,
{
55
,
4548
.
}
,
{
60
,
4370
.
}
,
{
65
,
4460
.
}
,
{
70
,
4562
.
}
,
{
75
,
4398
.
}
,
}}
I did a second run (not shown), in the upper range of crossover probabilities, and with
more iterations and larger numbers of search points. It homed in on .93 as a reasonably
good choice for a crossover probability setting.
{
80
,
4466
.
}
,
{
85
,
4378
.
}
,
{
90
,
4426
.
}
,
{
95
,
4354
.
Search WWH ::
Custom Search