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.