A Hybrid Method Integrating an Elite Genetic Algorithm with Tabu Search for the Quadratic Assignment Problem

Abstract The Quadratic Assignment Problem (QAP) is one of the most studied classical combinatorial optimization problems. QAP has many practical applications. Designing enhanced meta-heuristic approaches for the QAP is an active research area. In this work, we propose a hybrid algorithm (EGATS) that combines an elite genetic algorithm and tabu search to solve the QAP. In the optimization process, EGATS employs two kinds of elite crossovers, repeated 2-exchange mutation, and tabu search to strike a balance between exploitation and exploration. We evaluated the performance of EGATS through computational experiments on 135 well-known benchmark instances from the quadratic assignment problem library, QAPLIB. EGATS obtained the best-known solution for 131 instances. Compared to other popular meta-heuristic algorithms in the literature, EGATS is a competitive method for the QAP.