A performance study of meta‐heuristic approaches for quadratic assignment problem. (28th April 2021)

• Record Type: Journal Article
• Authors: Achary, Thimershen; Pillay, Shivani; Pillai, Sarah M.; Mqadi, Malusi; Genders, Emma; Ezugwu, Absalom E.
• Is Part Of: Concurrency and computation. Volume 33:Number 17(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2021-04-28
• Subjects: genetic algorithm -- Meta‐heuristic -- particle swarm optimization -- quadratic assignment problem; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.6321
• Languages: English
• ISSNs: 1532-0626

Abstract

Abstract: The quadratic assignment problem (QAP) is a well‐known challenging combinatorial optimization problem that has received many researchers' attention with varied real‐world and industrial applications areas. It is noteworthy to mention that a plethora of nature‐inspired optimization algorithms have successfully been used to solve various optimization problems, including several variants of the QAPs. In this article, a comprehensive literature review is presented to show the most relevant nature‐inspired algorithms that have been used in solving the QAP. More so, extensive experiments are conducted and analyzed to show the performance of the well‐known state‐of‐the‐art nature‐inspired meta‐heuristic optimization algorithms in solving the QAP, including the ant colony optimization (ACO), bat algorithm, genetic algorithm (GA), particle swarm optimization (PSO), and tabu search algorithm. Besides, a modified variant of the discrete PSO algorithm is implemented and compared with existing approaches. The six selected algorithms' performances, including the modified PSO, are validated on eight commonly used QAP instances of varying complexity and size, considering the quality of solutions achieved and computational time consumed by the representative algorithms. The numerical results revealed that the most competitive algorithm was ACO, while the GA appeared to be the worst performed algorithm among the six compared meta‐heuristic algorithms. However, based on the extensive analysis conducted on the tested algorithms, further improvements are suggested, including implementing new modified versions of the tested algorithms to tackle the QAP and its variant instances.