Information Technology Reference
In-Depth Information
The comparison is done with Tabu Search (TT) [36], Reative Tabu Search (RTS) [1],
Simulated Annealing (SA) [5], Genetic Hybrid (GH) [2] and Hybrid Ant Colony
(HAS) [13].
Two trends are fairly obvious. The first is that for bur instances, HAS obtains the
optimal, and is very closely followed by EDE by a margin of only 0.001 on average.
For the
tai
instances, EDE competes very well, obtaining the best values for the larger
problems and also obtains the best values for the
kra
problems. TT and RTS are shown
to be not well adapted to irregular problems, producing 10% worse solution at times.
GH which does not have memory retention capabilities does well, but does not produce
optimal results with any regularity.
3.7.3
Experimentation for Regular QAP
The second section of QAP problems is discussed in this section. This is the set of
regular problem as discussed in [13]. Regular problems are distinguished as having a
flow
dominance of less than 1.2.
Comparison was done with the same heuristics as in the previous section. The results
are presented in Table 3.40.
Three different set of instances are presented:
nug
,
sko
,
tai
and
wil
. Apart for the
nug20
instance, EDE finds the best solutions for all the reported instances. It can be
observed that TT, GH and SA perform best for
sko
problems and RTS performs best
for
tai
problems. On comparison with the optimal values, EDE obtains values with
tolerance of only 0.01 on average for all instances.
A sample generation for
Bur26a
problem is given in Fig 3.18.
−
Table 3.40.
EDE Regular QAP comparison
Instant
flow
dom
n
Optimal
TT
RTS
SA
GH
HAS-
QAP
EDE
nug20
0.99
20
2570
0
0.911
0.07
0
0
0.018
nug30
1.09
30
6124
0.032
0.872
0.121
0.007
0.098
0.005
sko42
1.06
42
15812
0.039
1.116
0.114
0.003
0.076
0.009
sko49
1.07
49
23386
0.062
0.978
0.133
0.04
0.141
0.009
sko56
1.09
56
34458
0.08
1.082
0.11
0.06
0.101
0.012
sko64
1.07
64
48498
0.064
0.861
0.095
0.092
0.129
0.013
sko72
1.06
72
66256
0.148
0.948
0.178
0.143
0.277
0.011
sko81
1.05
81
90998
0.098
0.88
0.206
0.136
0.144
0.011
tai20a
0.61
20
703482
0.211
0.246
0.716
0.628
0.675
0.037
tai25a
0.6
25
1167256
0.51
0.345
1.002
0.629
1.189
0.026
tai30a
0.59
30
1818146
0.34
0.286
0.907
0.439
1.311
0.018
tai35a
0.58
35
2422002
0.757
0.355
1.345
0.698
1.762
0.038
tai40a
0.6
40
3139370
1.006
0.623
1.307
0.884
1.989
0.032
tai50a
0.6
50
4941410
1.145
0.834
1.539
1.049
2.8
0.033
tai60a
0.6
60
7208572
1.27
0.831
1.395
1.159
3.07
0.037
tai80a
0.59
80
13557864
0.854
0.467
0.995
0.796
2.689
0.031
wil50
0.64
50
48816
0.041
0.504
0.061
0.032
0.061
0.004
Search WWH ::
Custom Search