The Quadratic Assignment Problem (QAP) is a well-known NP-hard combinatorial optimization problem that has received a lot of attention from the research community since it has many practical applications, such as allocation of facilities, design of electronic devices, etc. In this paper, we propose a hybrid approximate approach for the QAP based upon the framework of the Biased Random Key Genetic Algorithm. This hybrid approach includes an improvement method to be applied over the best individuals of the population in order to exploit the promising regions found in the search space. In the computational experiments, we evaluate the performance of our approach on widely known instances from the literature. In these experiments, we compare our approach against the best proposals from the related literature and we conclude that our approach is able to report high-quality solutions by means of short computational times.
- Quadratic Assignment Problem
- Biased Random Key Genetic Algorithm
- Approximation algorithms
Lalla-Ruiz, E., Exposito-Izquierdo, C., Melian-Batista, B., & Marcos Moreno-Vega, J. (2016). A Hybrid Biased Random Key Genetic Algorithm for the Quadratic Assignment Problem. Information processing letters, 116(8), 513-520. https://doi.org/10.1016/j.ipl.2016.03.002