TY - GEN
T1 - Approaching the quadratic assignment problem with kernels of Mallows models under the hamming distance
AU - Arza, Etor
AU - Pérez, Aritz
AU - Ceberio, Josu
AU - Irurozki, Ekhiñe
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.
PY - 2019/7/13
Y1 - 2019/7/13
N2 - The Quadratic Assignment Problem (QAP) is a specially challenging permutation-based np-hard combinatorial optimization problem, since instances of size n > 40 are seldom solved using exact methods. In this sense, many approximate methods have been published to tackle this problem, including Estimation of Distribution Algorithms (EDAs). In particular, EDAs have been used to solve permutation problems by introducing distance based exponential models, such as the Mallows Models. In this paper we approximate the QAP with a Hamming distance based kernels of Mallows Models. Based on the benchmark instances, we have observed that our approach is competitive, reaching the best-known solution in 71% of the tested instances, especially on large instances (n > 125), where it is able to outperform state of the art results in 43 out of 288 instances.
AB - The Quadratic Assignment Problem (QAP) is a specially challenging permutation-based np-hard combinatorial optimization problem, since instances of size n > 40 are seldom solved using exact methods. In this sense, many approximate methods have been published to tackle this problem, including Estimation of Distribution Algorithms (EDAs). In particular, EDAs have been used to solve permutation problems by introducing distance based exponential models, such as the Mallows Models. In this paper we approximate the QAP with a Hamming distance based kernels of Mallows Models. Based on the benchmark instances, we have observed that our approach is competitive, reaching the best-known solution in 71% of the tested instances, especially on large instances (n > 125), where it is able to outperform state of the art results in 43 out of 288 instances.
KW - Estimation of Distribution Algorithm
KW - Evolutionary Algorithm
KW - Hamming distance
KW - Quadratic Assignment Problem
U2 - 10.1145/3319619.3321976
DO - 10.1145/3319619.3321976
M3 - Conference contribution
AN - SCOPUS:85070577377
T3 - GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion
SP - 141
EP - 142
BT - GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion
PB - Association for Computing Machinery, Inc
T2 - 2019 Genetic and Evolutionary Computation Conference, GECCO 2019
Y2 - 13 July 2019 through 17 July 2019
ER -