Algorithm selection on generalized quadratic assignment problem landscapes

Andreas Beham; Stefan Wagner; Michael Affenzeller

doi:10.1145/3205455.3205585

Algorithm selection on generalized quadratic assignment problem landscapes

Andreas Beham, Stefan Wagner, Michael Affenzeller

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

9 Citations (Scopus)

Abstract

Algorithm selection is useful in decision situations where among many alternative algorithm instances one has to be chosen. This is often the case in heuristic optimization and is detailed by the well-known no-free-lunch (NFL) theorem. A consequence of the NFL is that a heuristic algorithm may only gain a performance improvement in a subset of the problems. With the present study we aim to identify correlations between observed differences in performance and problem characteristics obtained from statistical analysis of the problem instance and from fitness landscape analysis (FLA). Finally, we evaluate the performance of a recommendation algorithm that uses this information to make an informed choice for a certain algorithm instance.

Original language	English
Title of host publication	GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
Publisher	Association for Computing Machinery, Inc
Pages	253-260
Number of pages	8
ISBN (Electronic)	9781450356183
DOIs	https://doi.org/10.1145/3205455.3205585
Publication status	Published - 2 Jul 2018
Event	2018 Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan Duration: 15 Jul 2018 → 19 Jul 2018

Publication series

Name	GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

Conference

Conference	2018 Genetic and Evolutionary Computation Conference, GECCO 2018
Country/Territory	Japan
City	Kyoto
Period	15.07.2018 → 19.07.2018

Keywords

Algorithm selection
Assignment problems
Fitness landscapes

Access to Document

10.1145/3205455.3205585

Cite this

Beham, A., Wagner, S., & Affenzeller, M. (2018). Algorithm selection on generalized quadratic assignment problem landscapes. In GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference (pp. 253-260). (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/3205455.3205585

@inproceedings{a54708eb781c44268c2085afc25d63a7,

title = "Algorithm selection on generalized quadratic assignment problem landscapes",

abstract = "Algorithm selection is useful in decision situations where among many alternative algorithm instances one has to be chosen. This is often the case in heuristic optimization and is detailed by the well-known no-free-lunch (NFL) theorem. A consequence of the NFL is that a heuristic algorithm may only gain a performance improvement in a subset of the problems. With the present study we aim to identify correlations between observed differences in performance and problem characteristics obtained from statistical analysis of the problem instance and from fitness landscape analysis (FLA). Finally, we evaluate the performance of a recommendation algorithm that uses this information to make an informed choice for a certain algorithm instance.",

keywords = "Algorithm selection, Assignment problems, Fitness landscapes",

author = "Andreas Beham and Stefan Wagner and Michael Affenzeller",

note = "Publisher Copyright: {\textcopyright} 2018 Copyright held by the owner/author(s). Copyright: Copyright 2018 Elsevier B.V., All rights reserved.; 2018 Genetic and Evolutionary Computation Conference, GECCO 2018 ; Conference date: 15-07-2018 Through 19-07-2018",

year = "2018",

month = jul,

day = "2",

doi = "10.1145/3205455.3205585",

language = "English",

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

publisher = "Association for Computing Machinery, Inc",

pages = "253--260",

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

}

Beham, A, Wagner, S & Affenzeller, M 2018, Algorithm selection on generalized quadratic assignment problem landscapes. in GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, Inc, pp. 253-260, 2018 Genetic and Evolutionary Computation Conference, GECCO 2018, Kyoto, Japan, 15.07.2018. https://doi.org/10.1145/3205455.3205585

Algorithm selection on generalized quadratic assignment problem landscapes. / Beham, Andreas; Wagner, Stefan ; Affenzeller, Michael.
GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc, 2018. p. 253-260 (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference).

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

TY - GEN

T1 - Algorithm selection on generalized quadratic assignment problem landscapes

AU - Beham, Andreas

AU - Wagner, Stefan

AU - Affenzeller, Michael

PY - 2018/7/2

Y1 - 2018/7/2

N2 - Algorithm selection is useful in decision situations where among many alternative algorithm instances one has to be chosen. This is often the case in heuristic optimization and is detailed by the well-known no-free-lunch (NFL) theorem. A consequence of the NFL is that a heuristic algorithm may only gain a performance improvement in a subset of the problems. With the present study we aim to identify correlations between observed differences in performance and problem characteristics obtained from statistical analysis of the problem instance and from fitness landscape analysis (FLA). Finally, we evaluate the performance of a recommendation algorithm that uses this information to make an informed choice for a certain algorithm instance.

AB - Algorithm selection is useful in decision situations where among many alternative algorithm instances one has to be chosen. This is often the case in heuristic optimization and is detailed by the well-known no-free-lunch (NFL) theorem. A consequence of the NFL is that a heuristic algorithm may only gain a performance improvement in a subset of the problems. With the present study we aim to identify correlations between observed differences in performance and problem characteristics obtained from statistical analysis of the problem instance and from fitness landscape analysis (FLA). Finally, we evaluate the performance of a recommendation algorithm that uses this information to make an informed choice for a certain algorithm instance.

KW - Algorithm selection

KW - Assignment problems

KW - Fitness landscapes

UR - http://www.scopus.com/inward/record.url?scp=85050606379&partnerID=8YFLogxK

U2 - 10.1145/3205455.3205585

DO - 10.1145/3205455.3205585

M3 - Conference contribution

T3 - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

SP - 253

EP - 260

BT - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery, Inc

T2 - 2018 Genetic and Evolutionary Computation Conference, GECCO 2018

Y2 - 15 July 2018 through 19 July 2018

ER -

Beham A, Wagner S , Affenzeller M. Algorithm selection on generalized quadratic assignment problem landscapes. In GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc. 2018. p. 253-260. (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference). doi: 10.1145/3205455.3205585

Algorithm selection on generalized quadratic assignment problem landscapes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this