Information Technology Reference
In-Depth Information
new low 38
{
iteration, elapsed time, new value
}{
0
,
0
.
072004
,
3818
}
locally improved
{
3818
,
3812
}
new low 39
{
iteration, elapsed time, new value
}{
0
,
3
.
55622
,
3812
}
locally improved
{
3812
,
3786
}
{
}{
0
,
0
.
084006
,
3786
}
new low 40
iteration, elapsed time, new value
{
3786
,
3780
}
locally improved
{
}{
0
,
1
.
6361
,
3780
}
new low 41
iteration, elapsed time, new value
locally improved
{
3780
,
3768
}
new low 42
{
iteration, elapsed time, new value
}{
0
,
0
.
048003
,
3768
}
locally improved
{
3768
,
3758
}
new low 43
{
iteration, elapsed time, new value
}{
0
,
0
.
096006
,
3758
}
locally improved
{
3758
,
3756
}
new low 44
{
iteration, elapsed time, new value
}{
7
,
315
.
692
,
3756
}
locally improved
{
3756
,
3754
}
new low 45
{
iteration, elapsed time, new value
}{
10
,
108
.
415
,
3754
}
locally improved
{
3754
,
3752
}
new low 46
{
iteration, elapsed time, new value
}{
10
,
0
.
15601
,
3752
}
locally improved
{
3752
,
3748
}
new low 47
{
iteration, elapsed time, new value
}{
16
,
245
.
787
,
3748
}
locally improved
{
3748
,
3744
}
new low 48
{
iteration, elapsed time, new value
}{
16
,
0
.
076005
,
3744
}
{
872
.
687
,
{
3744
,
{
22
,
15
,
20
,
11
,
5
,
1
,
9
,
8
,
25
,
2
,
19
,
6
,
3
,
16
,
18
,
10
,
7
,
14
,
21
,
24
,
13
,
23
,
4
,
12
,
17
}}}
Notice that this permutation is not identical to the one we presented at the outset, which
in turn comes from benchmark suite results in the literature. Also note that we seem to
get good results from swaps early on (indeed, we almost get a global minimizer prior
to the main iterations). This raises the question of whether it might be useful to plug
in a different sort of heuristic, say larger swaps, or perhaps use of local (continuous)
quadratic programming. The interested reader may wish to explore such possibilities.
4.8
Future Directions
We have seen several examples of discrete optimization problems, and indicated ways
in which one might approach them using Differential Evolution. Problems investigated
include basic integer programming, set partitioning, set covering by subsets, and the
common permutation optimization problem of quadratic assignment. The main issues
have been to adapt Differential Evolution to enforce discrete or combinatorial structure,
e.g. that we obtain integrality, partitions, or permutations from chromosome vectors.
There are many open questions and considerable room for development. Here are a
few of them.
•
Figure out better ways to attack quadratic assignment problems so that we are less
likely to encounter difficulty in tuning parameter values, premature convergence,
and so on.
Search WWH ::
Custom Search