×

A genetic approach to the quadratic assignment problem. (English) Zbl 0812.90099

Summary: The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem with a wide variety of practical applications. Although many heuristics and semi-enumerative procedures for QAP have been proposed, no dominant algorithm has emerged. We describe a genetic algorithm (GA) approach to QAP. Genetic algorithms are a class of randomized parallel search heuristics which emulate biological natural selection on a population of feasible solutions. We present computational results which show that this GA approach finds solutions competitive with those of the best previously-known heuristics, and argue that genetic algorithms provide a particularly robust method for QAP and its more complex extensions.

MSC:

90B80 Discrete location and assignment
90C20 Quadratic programming
90C27 Combinatorial optimization
68T05 Learning and adaptive systems in artificial intelligence
90-08 Computational methods for problems pertaining to operations research and mathematical programming
92D10 Genetics and epigenetics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bazaraa, M. S.; Kirca, O., A branch-and-bound heuristic for solving the QAP, Naval Res. Logist. Q., 30, 287-304 (1983) · Zbl 0575.90041
[2] Beghin-Picavet, M.; Hansen, P., Deux problèmes d’affectation non linéaires, RAIRO Recherche Opérationelle, 16, 263-276 (1982) · Zbl 0491.90082
[3] Bukard, R. E.; Bonniger, T., A heuristic for quadratic boolean program with applications to quadratic assignment problems, Eur. J. Opns Res., 13, 374-386 (1983) · Zbl 0509.90058
[4] Cohoon, J. P.; Hegde, S. U.; Martin, W. N.; Richards, D. S., Distributed genetic algorithms for the floorplan design problem, IEEE Trans. Computer-Aided Design, 10, 483-492 (1991)
[5] Cohoon, J. P.; Paris, W. D., Genetic placement, IEEE Trans. Computer-Aided Design, 6, 956-964 (1987)
[6] Davis, L., Job shop scheduling with genetic algorithms, (Proc. Int. Conf. Genetic Algorithms and Their Applications (1985)), 136-140 · Zbl 0681.68043
[7] Davis, L.; Coombs, S., Genetic algorithms and communications link speed design: theoretical considerations, (Proc. Second Int. Conf. Genetic Algorithms (1987)), 252-256
[8] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[9] Hanan, M.; Kurtzberg, J. M., A review of the placement and quadratic assignment problems, SIAM Rev., 14, 324-342 (1972) · Zbl 0241.90048
[10] Heragu, S. S.; Kusiak, A., Machine layout problem in flexible manufacturing systems, Opns Res., 36, 258-268 (1988)
[11] Hillier, F. S.; Connors, M. M., Quadratic assignment problem algorithms and the location of indivisible facilities, Mgmt Sci., 13, 42-57 (1966)
[12] Hitchings, G. G.; Cottam, M., An efficient heuristic procedure for solving the layout design problem, Omega, 4, 205-214 (1976)
[13] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor · Zbl 0317.68006
[14] Hou, E. S.H.; Hong, R.; Ansari, N., Efficient multiprocessor scheduling based on genetic algorithms, (Proc. IECON ’90, Vol 2 (1990)), 1239-1243
[15] Hou, E. S.H.; Li, H.-Y., Task scheduling for flexible manufacturing systems based on genetic algorithms, (Proc. 1991 IEEE Int. Conf. Systems, Man, and Cybernetics (1991)), 397-402
[16] Hundal, T. S., The facility layout problem: a myopic priority heuristic, (Ph.D. dissertation (1991), University of Pittsburgh)
[17] Kaku, B. K.; Thompson, G. L.; Morton, T. E., A hybrid heuristic for the facilities layout problem, Comput. Opns Res., 18, 241-253 (1991) · Zbl 0723.90043
[18] Koopmans, T. C.; Beckmann, M., Assignment problems and the location of economic activities, Econometrica, 25, 53-76 (1957) · Zbl 0098.12203
[19] Nugent, C. E.; Vollmann, T. E.; Ruml, J., An experimental comparison of techniques for the assignment of facilities to locations, Opns Res., 16, 150-173 (1968)
[20] Picone, C. J.; Wilhelm, W. E., A perturbation scheme to improve Hillier’s solution to the facilities location problem, Mgmt Sci., 30, 1238-1249 (1984) · Zbl 0555.90038
[21] Sieglemann, H. T.; Frieder, O., The allocation of documents in multiprocessor information retrieval systems: an application of genetic algorithms, (Proc. 1991 IEEE Int. Conf. Systems, Man, and Cybernetics (1991)), 645-650
[22] Steinberg, L., The backboard wiring problem: a placement algorithm, SIAM Rev., 3, 37-50 (1961) · Zbl 0097.14703
[23] Wilhelm, M. R.; Ward, T. L., Solving quadratic assignment problems by ‘simulated annealing’, IIE Trans., 19, 107-119 (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.