Article ID: | iaor19951089 |
Country: | United Kingdom |
Volume: | 22 |
Issue: | 1 |
Start Page Number: | 73 |
End Page Number: | 83 |
Publication Date: | Jan 1995 |
Journal: | Computers and Operations Research |
Authors: | Tate David M., Smith Alice E. |
Keywords: | programming: quadratic |
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. In this paper, the authors 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. The authors 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.