A GA-ACO-local search hybrid algorithm for solving quadratic assignment problem

Abstract

In recent decades, many meta-heuristics, including genetic algorithm (GA), ant colony optimization (ACO) and various local search (LS) procedures have been developed for solving a variety of NP-hard combinatorial optimization problems. Depending on the complexity of the optimization problem, a meta-heuristic method that may have proven to be successful in the past might not work as well. Hence it is becoming a common practice to hybridize meta-heuristics and local heuristics with the aim of improving the overall performance. In this paper, we propose a novel adaptive GA-ACO-LS hybrid algorithm for solving quadratic assignment problem (QAP). Empirical study on a diverse set of QAP benchmark problems shows that the proposed adaptive GA-ACO-LS converges to good solutions efficiently. The results obtained were compared to the recent state-of-the-art algorithm for QAP, and our algorithm showed obvious improvement.