Article ID: | iaor2000987 |
Country: | United Kingdom |
Volume: | 50 |
Issue: | 2 |
Start Page Number: | 167 |
End Page Number: | 176 |
Publication Date: | Feb 1999 |
Journal: | Journal of the Operational Research Society |
Authors: | Dorigo M., Gambardella L.M., Taillard E.D. |
Keywords: | ant system, quadratic assignment |
This paper presents HAS–QAP, a hybrid ant colony system coupled with a local search, applied to the quadratic assignment problem. HAS–QAP uses pheromone trail information to perform modifications on QAP solutions, unlike more traditional ant systems that use pheromone trail information to construct complete solutions. HAS–QAP is analysed and compared with some of the best heuristics available for the QAP: two versions of tabu search, namely, robust and reactive tabu search, hybrid genetic algorithm, and a simulated annealing method. Experimental results show that HAS–QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS–QAP performance is less competitive on random, regular and unstructured problems.