Information Technology Reference
In-Depth Information
SeedRandom[11111];
SeedRandom[11111];
Timing[
Timing[
{
min
,
perm
}
= QAP[mat1
,
mat2
,.
06
,
200
,
40
,.
6]]
Timing[
{
{
min
,
perm
min
,
perm
}
}
= QAP[mat1
,
mat2
,.
06
,
200
,
40
,.
6]]
= QAP[mat1
,
mat2
,.
06
,
200
,
40
,.
6]]
{
13
.
5048
,
{
3864
.,
{
22
,
20
,
17
,
12
,
5
,
13
,
15
,
23
,
25
,
2
,
19
,
10
,
9
,
8
,
4
,
1
,
7
,
6
,
16
,
18
,
24
,
21
,
14
,
3
,
11
}}}
We now try a longer run.
SeedRandom[11111];
SeedRandom[11111];
Timing[
Timing[
{
min
,
perm
}
= QAP[mat1
,
mat2
,.
06
,
4000
,
100
,.
6]]
Timing[
{
{
min
,
perm
min
,
perm
}
}
= QAP[mat1
,
mat2
,.
06
,
4000
,
100
,.
6]]
= QAP[mat1
,
mat2
,.
06
,
4000
,
100
,.
6]]
{
394
.
881
,
{
3884
.,
{
15
,
20
,
19
,
10
,
13
,
22
,
1
,
16
,
7
,
4
,
9
,
25
,
6
,
23
,
12
,
8
,
11
,
21
,
14
,
17
,
5
,
2
,
18
,
3
,
24
}}}
We learn a lesson here. Sometimes a short run is lucky, and a longer one does not fare
as well. We will retry with a different crossover, more iterations, and a larger set of
chromosomes.
Timing[
{
min
,
perm
}
= QAP[mat1
,
mat2
,.
11
,
10000
,
200
,.
6]]
Timing[
Timing[
{
{
min
,
perm
min
,
perm
}
}
= QAP[mat1
,
mat2
,.
11
,
10000
,
200
,.
6]]
= QAP[mat1
,
mat2
,.
11
,
10000
,
200
,.
6]]
{
2186
.
43
,{
3826
.,
{
5
,
2
,
18
,
11
,
4
,
12
,
25
,
8
,
14
,
24
,
17
,
3
,
16
,
6
,
21
,
20
,
23
,
9
,
7
,
10
,
22
,
15
,
19
,
1
,
13
}}}
This result is not bad.
4.6.2
Representing and Using Permutations as Shuffles
The method we now show will generate a permutation as a
shuffle
of a set of integers.
We first describe a standard way to shuffle, with uniform probability, a set of
n
elements.
First we randomly pick a number
j
1
in the range
= 1, we swap the
first and
j
1
th elements. We then select at random an element
j
2
in the range
{
1
,...,
n
}
and, if
j
1
{
2
,...,
n
}
.
If
j
2
= 2 we swap the second and
j
2
th elements. The interested reader can convince
him or herself that this indeed gives a uniform random shuffle (in contrast, selecting all
elements in the range
{
1
,...,
n
}
fails to be uniform).
Our goal, actually, is not directly to generate shuffles, but rather to use them. Each
chromosome will represent a shuffle, encoded as above by a set of swaps to perform. So
the effective constraint on the first variable is that it be an integer in the range
{
1
,...,
n
}
,
while the second must be an integer in the range
, and so on (small point: we
do not actually require an
n
th variable, since its value must always be
n
). We require a
utility routine to convert quickly from a shuffle encoding to a simple permutation vector.
The code below will do this. We use the
Compile
function of
Mathematica
to get a
speed boost.
{
2
,...,
n
}
Search WWH ::
Custom Search