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

Authors: Yongzhong Wu, Ping Ji

Abstract:

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.

Keywords: Quadratic assignment problem, Genetic algorithm, Replacement strategy, QAPLIB.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070713

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.