Approaching the quadratic assignment problem with kernels of mallows models under the hamming distance
Approaching the quadratic assignment problem with kernels of mallows models under the hamming distance
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.
TIN2016-78365-R SVP-2014-068574 SEV-2013-0323
Combinatorial optimization, Evolutionary algorithms
Combinatorial optimization, Evolutionary algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).2 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!