A Memetic Algorithm for the Quadratic Assignment Problem with Parallel Local Search

The Quadratic Assignment Problem (QAP) is a well-studied, NP-Hard combinatorial optimization problem with practical applications in timetabling, scheduling, logistics, circuit design and data visualisation, to name a few. In this paper a Memetic Algorithm is described, which utilises a ternary tree structure for its population and uses a Tabu Search as its local improvement strategy. The Tabu Search is also run in parallel, significantly reducing the running time of the algorithm. The ternary tree not only stores the individuals within the population, but the inherent structure within this tree also determines parent selection for crossover. A small number of rules, which include fitness and diversity-based rules, govern whether a newly produced solution remains within the population, or whether it is discarded. These key features are tested against a basic Memetic Algorithm using the instances from the QAP library, QAPLIB, and have shown to significantly improve the performance in terms of both time and solution quality. The best version of the Memetic Algorithm is shown to perform competitively with some of the state-of-the-art algorithms for the QAP from the literature, with grid-based and real-life instances shown to be solved very efficiently and effectively by the presented algorithms. © 2015 IEEE.