Ant colonies for the quadratic assignment problem

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...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of the Operational Research Society 1999-02, Vol.50 (2), p.167-176
Main Authors: Gambardella, L M, Taillard, É D, Dorigo, M
Format: Article
Language:English
Subjects:
Animal behavior
ant colony optimisation
ant systems
Ants
Applied sciences
Business and Management
Combinatorial optimization
Exact sciences and technology
Flows in networks. Combinatorial problems
Heuristic
Heuristic methods
Hybridity
Insect behavior
Insect colonies
Iterative solutions
Management
Mathematical models
meta-heuristics
Operational research and scientific management
Operational research. Management science
Operations research
Operations Research/Decision Theory
Optimization
Pheromones
quadratic assignment problem
Studies
Tabu search
Theoretical Paper
Theoretical Papers
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0160-5682
1476-9360
DOI:10.1057/palgrave.jors.2600676