A Hybrid Metaheuristic for the Quadratic Assignment Problem

• Published in: Computational optimization and applications 2006-05, Vol.34 (1), p.85-113
• Main Authors: Tseng, Lin-Yu, Liang, Shyi-Ching
• Format: Article
• Language: English
• Subjects: Algorithms; Assignment problem; Genetic algorithms; Heuristic; Linear programming; Mathematical models; Methods; Neighborhoods; Optimization; Pheromones; Population; Studies
• ISSN: 0926-6003; 1573-2894
• DOI: 10.1007/s10589-005-3069-9

The quadratic assignment problem (QAP) is known to be NP-hard. We propose a hybrid metaheuristic called ANGEL to solve QAP. ANGEL combines the ant colony optimization (ACO), the genetic algorithm (GA) and a local search method (LS). There are two major phases in ANGEL, namely ACO phase and GA phase. Instead of starting from a population that consists of randomly generated chromosomes, GA has an initial population constructed by ACO in order to provide a good start. Pheromone acts as a feedback mechanism from GA phase to ACO phase. When GA phase reaches the termination criterion, control is transferred back to ACO phase. Then ACO utilizes pheromone updated by GA phase to explore solution space and produces a promising population for the next run of GA phase. The local search method is applied to improve the solutions obtained by ACO and GA. We also propose a new concept called the eugenic strategy intended to guide the genetic algorithm to evolve toward a better direction. We report the results of a comprehensive testing of ANGEL in solving QAP. Over a hundred instances of QAP benchmarks were tested and the results show that ANGEL is able to obtain the optimal solution with a high success rate of 90%. [PUBLICATION ABSTRACT]