A Hierarchical Data-Driven Parallel Memetic Algorithm for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is one of the most important combinatorial optimization problems in theory and practice. In this paper, we are proposing a hierarchical data-driven parallel memetic algorithm to solve the problem. A component-based hierarchical system architecture with a rich graphical user interface is proposed and implemented as a multi-threaded Windows application. The number of parallel memetic algorithms is set to equal the number of cores/node. Every memetic algorithm has its own local elite set. Collaboration among parallel memetic algorithms is allowed, and a shared elite set is created as a result. The main algorithm has multiple restarts, and a global elite set is maintained between those restarts. The global elite set acts as a tabu set for the shared elite set, and the shared elite set acts as a tabu set for the local elite sets. A set of crossover and mutation operators are proposed. We use visual data analytics to create more competent, data-driven versions of those operators. All the elite sets participate actively in the neighborhood search operations. The developed application has been deployed over four nodes, and the entire Quadratic Assignment Problem Library (QAPLIB) has been fully tested. The experimental results show that our algorithm acquires the optimal/best-known solutions for 127 out of 134 instances, leaving out just seven problems. To the best of our knowledge, the comparative results show that we have the best average compared to the state-of-the-art parallel algorithms to date, proving the efficiency and efficacy of the proposed algorithm