Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures

Bernhard Werth; Johannes Karder; Andreas Beham; Erik Pitzer; Kaifeng Yang; Stefan Wagner

doi:10.1145/3583133.3596325

Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures

Bernhard Werth, Johannes Karder, Andreas Beham, Erik Pitzer, Kaifeng Yang, Stefan Wagner

Research output: Chapter in Book/Report/Conference proceedings › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
Publisher	Association for Computing Machinery, Inc
Pages	2108-2114
Number of pages	7
ISBN (Electronic)	9798400701207
DOIs	https://doi.org/10.1145/3583133.3596325
Publication status	Published - 15 Jul 2023
Event	2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion - Lisbon, Portugal Duration: 15 Jul 2023 → 19 Jul 2023

Publication series

Name	GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion

Conference

Conference	2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion
Country/Territory	Portugal
City	Lisbon
Period	15.07.2023 → 19.07.2023

Keywords

dynamic optimization
fitness landscape analysis
state space analysis

Access to Document

10.1145/3583133.3596325Licence: CC BY

Cite this

Werth, B., Karder, J., Beham, A., Pitzer, E., Yang, K., & Wagner, S. (2023). Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures. In GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion (pp. 2108-2114). (GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion). Association for Computing Machinery, Inc. https://doi.org/10.1145/3583133.3596325

Werth, Bernhard ; Karder, Johannes ; Beham, Andreas et al. / Walking through the Quadratic Assignment-Instance Space : Algorithm Performance and Landscape Measures. GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, Inc, 2023. pp. 2108-2114 (GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion).

@inproceedings{69569badf9ac4b7f8ceeb9e43c2bed86,

title = "Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures",

abstract = "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.",

keywords = "dynamic optimization, fitness landscape analysis, state space analysis",

author = "Bernhard Werth and Johannes Karder and Andreas Beham and Erik Pitzer and Kaifeng Yang and Stefan Wagner",

note = "Publisher Copyright: {\textcopyright} 2023 Copyright held by the owner/author(s).; 2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion ; Conference date: 15-07-2023 Through 19-07-2023",

year = "2023",

month = jul,

day = "15",

doi = "10.1145/3583133.3596325",

language = "English",

series = "GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion",

publisher = "Association for Computing Machinery, Inc",

pages = "2108--2114",

booktitle = "GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion",

}

Werth, B , Karder, J, Beham, A, Pitzer, E, Yang, K & Wagner, S 2023, Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures. in GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion. GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, Inc, pp. 2108-2114, 2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion, Lisbon, Portugal, 15.07.2023. https://doi.org/10.1145/3583133.3596325

Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures. / Werth, Bernhard ; Karder, Johannes; Beham, Andreas et al.
GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, Inc, 2023. p. 2108-2114 (GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion).

Research output: Chapter in Book/Report/Conference proceedings › Conference contribution › peer-review

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

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 - http://www.scopus.com/inward/record.url?scp=85169021810&partnerID=8YFLogxK

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 -

Werth B , Karder J, Beham A, Pitzer E, Yang K, Wagner S. Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures. In GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, Inc. 2023. p. 2108-2114. (GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion). doi: 10.1145/3583133.3596325

Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

JRZ adaptOp - Josef Ressel Center for Adaptive Optimization in Dynamic Environments

Cite this

Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Projects

JRZ adaptOp - Josef Ressel Center for Adaptive Optimization in Dynamic Environments

Cite this