Results for de Carvalho et al. Problems
The
results reported here are based on the MRT algorithm described in Drezner (2008)
based on the hybrid genetic algorithm of Drezner (2003).
Recently de Carvalho and Rahmann (2006) introduced a new class of quadratic assignment problems that turn out to be extremely difficult to solve. There are 14 problems in this set. They were solved by GRASP (Olivera Pardalos and Resende, 2004 reported in de Carvalho and Rahmann, 2006), GATS (genetic algorithm and tabu search) solved by the method in Rodriguez et al., (2004), and EDA (estimation of distribution algorithms) reported in Pelikan et al. (2007). All these researchers report that these problems are extremely difficult to solve among the benchmark problems available on QAPLIB.
We experimented with many parameters for the MRT and found
that for these problems the number of generations needs to be relatively large
and the depth of the tabu search is less important
(especially for the border length minimization problems). Each problem was run
10 times for each variant of parameter setting of MRT. Run times range from
less than 2 minutes per single run for the n=36 problems to less than 9 hours
for the n=144 problems. The results and the solutions for different parameters
are reported here.
|
|
MRT |
GRASP |
GATS |
EDA |
|
Border Length Minimization |
||||
|
36 |
3,296 |
3,352 |
3,296 |
|
|
49 |
4,548 |
4,660 |
4,564 |
|
|
64 |
5,988 |
6,200 |
6,048 |
|
|
81 |
7,536 |
7,900 |
7,644 |
|
|
100 |
9,272 |
9,684 |
9,432 |
|
|
121 |
11,412 |
12,032 |
11,640 |
|
|
144 |
13,472 |
14,196 |
13,832 |
|
|
Conflict Index Minimization |
||||
|
36 |
168,611,971 |
169,925,219 |
169,016,907 |
168,705,477 |
|
49 |
236,355,034 |
238,859,844 |
237,077,377 |
236,355,034 |
|
64 |
325,671,035 |
327,770,071 |
326,696,412 |
326,251,579 |
|
81 |
427,447,820 |
434,317,170 |
428,682,120 |
427,852,554 |
|
100 |
523,146,366 |
532,573,788 |
525,401,670 |
|
|
121 |
653,416,978 |
664,137,090 |
658,317,466 |
|
|
144 |
795,009,899 |
813,127,758 |
803,379,686 |
|
de Carvalho
Jr., S.A. and S. Rahmann (2006) “Microarray Layout as
a Quadratic Assignment Problem," German Conference on Bioinformatics
(GCB), LNI, To appear.
Drezner, Z. (2003) “A New Genetic Algorithm for the
Quadratic Assignment Problem," INFORMS Journal on Computing, 15,
320-330.
Drezner, Z. (2008) “Extensive Experiments with Hybrid
Genetic Algorithms for the Solution of the Quadratic Assignment Problem," Computers
and Operations Research, 35, 717-736.
Oliveira, C.A.S., P.M. Pardalos
and M.G.C. Resende (2004) “GRASP with Path-relinking for the Quadratic Assignment Problem," In Ribeiro, C.C. and Martins, S.L. (eds.), Efficient and Experimental Algorithms, LNCS,
3059, 356-368, Springer-Verlag.
Pelikan M., S. Tsutsui,
and R. Kalapala (2007) “Dependency Trees, Permutations,
and Quadratic Assignment Problem," Missouiri
Estimation of Distribution Algorithms Laboratory (MEDAL) Report No. 2007003,
January, 2007.
Rodriguez, J.M., F.C. MacPhee,
D.J. Bonham, J.D. Horton, and V.C. Bhavsar (2004)
“Best Permutations for the Dynamic Plant Layout Problem," In Dasgupta, A.R., Iyengar, S.S.,
and Bhatt, H.S. (Eds.) Proceedings of the 12th International Conference on
Advances in Computing and Communications (ADCOM 2004)}, Allied Publishers
Pvt. Ltd., New Delhi Ahmedabad, India, 173-178.