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

Tate, David M.; Smith, Alice E.

Comput. Oper. Res. 22, No. 1, 73-83 (1995).

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

Keywords:

quadratic assignment; combinatorial optimization; randomized parallel search heuristics

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)
[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
[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
[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)