Solving the Quadratic Assignment Problems by a Genetic Algorithm with a New Replacement Strategy

This paper proposes a genetic algorithm based on a new replacement strategy to solve the quadratic assignment problems, which are NP-hard. The new replacement strategy aims to improve the performance of the genetic algorithm through well balancing the convergence of the searching process and the diversity of the population. In order to test the performance of the algorithm, the instances in QAPLIB, a quadratic assignment problem library, are tried and the results are compared with those reported in the literature. The performance of the genetic algorithm is promising. The significance is that this genetic algorithm is generic. It does not rely on problem-specific genetic operators, and may be easily applied to various types of combinatorial problems.

Authors:

• Yongzhong Wu
• Ping Ji

Keywords:

• Quadratic assignment problem
• Genetic algorithm
• Replacement strategy
• QAPLIB.

References:

[1] T. C. Koopmans, M. J. Beckmann, Assignment problems and the location
of economic activities, Econometrica, 25(1957), pp.53-76.
[2] R. E. Burkard, E. Cela, P. M. Pardalos, L. S. Pitsoulis, The quadratic
assignment problem, in: Anonymous Handbook of Combinatorial
Optimization, Volume 3, Kluwer, 1998, pp.241-337.
[3] S. Sahni, T. Gonzalez, NP-complete approximation problems, Journal of
the Association for Computing Machinery, 23(1976), pp.555-565.
[4] R. E. Burkard, E. Cela, G. Rote, G. J. Woeginger, The quadratic
assignment problem with a monotone anti-Monge and a symmetric
Toeplitz matrix: easy and hard cases, Mathematical Programming,
82(1998), pp.125-158.
[5] R. E. Burkard, S. E. Karisch, F. Rendl, QAPLIB: A quadratic assignment
problem library, Journal of Global Optimization, 10(1997), pp.391-403.
[6] L. Steinberg, The backboard wiring problem: A placement algorithm,
SIAM Review, 3(1961), pp.37-50.
[7] C. E. Nugent, T. E. Vollman, J. Ruml, An experimental comparison of
techniques for the assignment of facilities to locations, Operations
Research, 16(1968), pp.150-173.
[8] D. T. Conolly, An improved annealing mechanism for the QAP, European
Journal of Operational Research, 46(1990), pp.93-100.
[9] J. Skorin-Kapov, Tabu search applied to the quadratic assignment
problem, ORSA Journal on Computing, 2(1990), pp.33-45.
[10] E. D. Taillard, Robust tabu search for the quadratic assignment problem,
Parallel Computing, 17(1991), pp.443-455.
[11] C. Fleurent, J. Ferland, Genetic hybrids for the quadratic assignment
problem, in: Anonymous DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, 1994, pp.173-187.
[12] D. D. Tate, A. E. Smith, A genetic approach to the quadratic assignment
problem, Computers and Operations Research, 1(1995), pp.855-865.
[13] R. K. Ahuja, J. B. Orlin, A. Tiwari, A greedy genetic algorithm for the
quadratic assignment problem, Computers and Operations Research,
27(2000), pp.917-934.
[14] Z. Drezner, A new genetic algorithm for the quadratic assignment
problem, INFORMS Journal on Computing, 15(2002), pp.320-330.
[15] Y. Li, P. M. Pardalos, Resende, M. G. C., A greedy randomized adaptive
search procedure for the quadratic assignment problem. DIMACS Series
in Discrete Mathematics and Theoretical Computer Science, 16(1994),
pp.237-261.
[16] L. M. Gambardella, E. D. Taillard, M. Dorigo, Ant colonies for the
quadratic assignment problem, Journal of the Operational Research
Society, 50(1999), pp.167-176.
[17] E. D. Taillard, Comparison of iterative searches for the quadratic
assignment problem, Location Science, 3(1995), pp.87-105.