Artificial bee colony optimization for the quadratic assignment problem

Abstract

We propose hybrid Artificial Bee Colony (ABC) optimization algorithms for the well-known Quadratic Assignment Problem (QAP). Large problem instances of the QAP are still very challenging. Scientists have not discovered any method to obtain the exact solutions for these difficult problems yet. The ABC has been reported to be an efficient meta-heuristic for the solution of many intractable problems. It has promising results making it a good candidate to obtain (near)-optimal solutions for well-known NP-Hard problems. The proposed ABC algorithm (ABC-QAP) and its parallel version (PABC-QAP) are the first applications of the ABC meta-heuristic together with Tabu search to the optimization of the QAP. The behavior of employed, onlooker and scout bees are modeled by using the distributed memory parallel computation paradigm for large problem instances of the QAP. Scout bees search for food sources, employed bees go to food source and return to hive and share their information on the dance area, onlooker bees watch the dance of employed bees and choose food sources depending on the dance. Robust Tabu search method is used to simulate exploration and exploitation processes of the bees. 125 of 134 benchmark problem instances are solved optimally from the QAPLIB library and 0.27% deviation is reported for 9 large problem instances that could not be solved optimally. The performance of the ABC optimization algorithms is competitive with state-of-the-art meta-heuristic algorithms in literature. (C) 2019 Elsevier B.V. All rights reserved.