Memetic search for the quadratic assignment problem

•We present a memetic algorithm (called BMA) for the well-known QAP.•BMA integrates BLS within the population-based evolutionary computing framework.•BMA is able to attain the best-known results for 133 out of 135 QAP benchmark instances.•We provide insights on search landscapes and crossover operators for QAP.

The quadratic assignment problem (QAP) is one of the most studied NP-hard problems with various practical applications. In this work, we propose a powerful population-based memetic algorithm (called BMA) for QAP. BMA integrates an effective local optimization algorithm called Breakout Local Search (BLS) within the evolutionary computing framework which itself is based on a uniform crossover, a fitness-based pool updating strategy and an adaptive mutation procedure. Extensive computational studies on the set of 135 well-known benchmark instances from the QAPLIB revealed that the proposed algorithm is able to attain the best-known results for 133 instances and thus competes very favorably with the current most effective QAP approaches. A study of the search landscape and crossover operators is also proposed to shed light on the behavior of the algorithm.