TY - GEN
T1 - Walking through the Quadratic Assignment-Instance Space
T2 - 2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion
AU - Werth, Bernhard
AU - Karder, Johannes
AU - Beham, Andreas
AU - Pitzer, Erik
AU - Yang, Kaifeng
AU - Wagner, Stefan
N1 - Publisher Copyright:
© 2023 Copyright held by the owner/author(s).
PY - 2023/7/15
Y1 - 2023/7/15
N2 - This paper presents an analysis of the trends and behavior of Fitness Landscape Analysis (FLA) and corresponding algorithm performance features for instances of the Quadratic Assignment Problem (QAP) and the instance space between them. Given two QAPLIB instances, a transformation generates 30 intermediary instances, i.e. problem versions for further experimentation. For each problem version, we track algorithm performance of robust tabu search (RTS) and variable neighborhood search (VNS), as well as FLA measures obtained by various types of walks. Thus, we are able to analyze how these performances and measures change during the transformation. We observe that RTS dominates VNS in earlier problem versions, while VNS outperforms RTS in later problem versions. Overall, the transformation leads to a smooth traversal of the instance space, and both algorithm performance and FLA measures correlate with problem versions.
AB - This paper presents an analysis of the trends and behavior of Fitness Landscape Analysis (FLA) and corresponding algorithm performance features for instances of the Quadratic Assignment Problem (QAP) and the instance space between them. Given two QAPLIB instances, a transformation generates 30 intermediary instances, i.e. problem versions for further experimentation. For each problem version, we track algorithm performance of robust tabu search (RTS) and variable neighborhood search (VNS), as well as FLA measures obtained by various types of walks. Thus, we are able to analyze how these performances and measures change during the transformation. We observe that RTS dominates VNS in earlier problem versions, while VNS outperforms RTS in later problem versions. Overall, the transformation leads to a smooth traversal of the instance space, and both algorithm performance and FLA measures correlate with problem versions.
KW - dynamic optimization
KW - fitness landscape analysis
KW - state space analysis
UR - https://www.scopus.com/pages/publications/85169021810
U2 - 10.1145/3583133.3596325
DO - 10.1145/3583133.3596325
M3 - Conference contribution
AN - SCOPUS:85169021810
T3 - GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
SP - 2108
EP - 2114
BT - GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
PB - Association for Computing Machinery, Inc
Y2 - 15 July 2023 through 19 July 2023
ER -