Kernels of Mallows Models under the Hamming Distance for solving the Quadratic Assignment Problem

The Quadratic Assignment Problem (QAP) is a well-known permutation-based combinatorial optimization problem with real applications in industrial and logistics environments. Motivated by the challenge that this NPhard problem represents, it has captured the attention of the evolutionary computation community for decades. As a result, a large number of algorithms have been proposed to optimize this algorithm. Among these, exact methods are only able to solve instances of size n 40, and thus, many heuristic and metaheuristic methods have been applied to the QAP. In this work, we follow this direction by approaching the QAP through Estimation of Distribution Algorithms (EDAs). Particularly, a nonparametric distance-based exponential probabilistic model is used. Based on the analysis of the characteristics of the QAP, and previous work in the area, we introduce Kernels of Mallows Model under the Hamming distance to the context of EDAs. Conducted experiments point out that the performance of the proposed algorithm in the QAP is superior to (i) the classical EDAs adapted to deal with the QAP, and also (ii) to the specific EDAs proposed in the literature to deal with permutation problems.1. Introduction The Quadratic Assignment Problem (QAP) [30] is a well known combinatorial optimization problem. Along with other problems, such as the traveling salesman problem, the linear ordering problem and the flowshop scheduling problem, it belongs to the family of permutation-based (a permutation is a bijection of the set {1,...,n } onto itself) problems [10]. The QAP has been applied in many different environments over the years, to name but a few notable examples, selecting optimal hospital layouts [24], optimally placing components on circuit boards [44], assigning gates at airports [23] or optimizing data transmission [38]. Sahni and Gonzalez [45] proved that the QAP is an NPhard optimization problem, and as such, no polynomial-time exact algorithm can solve this problem unless P NP. M: The size of the set of selected solutions. S: The number of new solutions generated at each iteration.