A comparison of different metaheuristics for the quadratic assignment problem in accelerated systems

Although metaheuristics are used for solving complex and real-world problems, they do not provide an exact solution, but only an approximate solution in feasible time. However, for very large instances, a metaheuristic may take a considerable amount of time. Therefore, we utilize a highly parallel metaheuristic to run on a modern massively parallel graphics processing unit (GPU) to further reduce the execution time. Additionally, because metaheuristics are not problem-specific, it is interesting to determine which metaheuristic is best for each problem type. In this study, using a massive parallel machine such as a GPU, we evaluate the performance of different metaheuristics such as the iterated local search, simulated annealing, genetic algorithm, tabu search, particle swarm optimization, and crow search algorithm with respect to the quadratic assignment problem. (c) 2020 Elsevier B.V. All rights reserved.

Automated summary

Although metaheuristics provide only approximate solutions in feasible time and may take considerable time for very large instances, utilizing highly parallel metaheuristics on modern GPUs can further reduce execution time. It is interesting to determine the best metaheuristic for each problem type since they are not problem-specific. This study evaluates the performance of different metaheuristics for the quadratic assignment problem using a massively parallel machine like a GPU.