A Hybrid Biased Random Key Genetic Algorithm for the Quadratic Assignment Problem

Eduardo Lalla-Ruiz, Christopher Exposito-Izquierdo, Belen Melian-Batista, J. Marcos Moreno-Vega

    Research output: Contribution to journalArticleAcademicpeer-review

    10 Citations (Scopus)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)513-520
    Number of pages8
    JournalInformation processing letters
    Volume116
    Issue number8
    DOIs
    Publication statusPublished - Aug 2016

    Keywords

    • Quadratic Assignment Problem
    • Biased Random Key Genetic Algorithm
    • Metaheuristic
    • Approximation algorithms

    Cite this