Training Sets for Algorithm Tuning: Exploring the Impact of Structural Distribution

Mashal Alkhalifa, David Corne

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Algorithm tuning, especially in the context of metaheuristic algorithms, is a growing area of research and practice, which concerns configuring the parameters of an algorithm on the basis of a ‘training set’ of problem instances. There is much interest (but little research so far) on the relationship between the training set and generalization performance. In general terms, we expect that, if an algorithm is targeted at problems of a certain type, then the training set of problem instances should represent a diverse collection of problems of that type. However, many questions around this area are still the topic of research. In this paper, we explore how certain structural aspects of the training set problem instances (in contrast, for example, to problem size) affect generalization performance. Specifically, we look at spaces of simple TSP instances where the number of cities is constant, but with different spatial distributions. We find that, when the training problem sets are suitably difficult, an algorithm tuned for a specific spatial distribution tends towards being the best algorithm on test sets following that distribution. Conversely, and significantly, if the target problem set is not from a ‘particularly difficult’ spatial distribution, a better optimizer for that distribution may be produced by choosing a different spatial distribution for the training set. This has implications for the development of real-world optimizers for specific problem classes, such as, for example, vehicle routing problems with particular depot and customer distributions.

Original languageEnglish
Title of host publicationStudies in Fuzziness and Soft Computing
EditorsRadek Matoušek, Jakub Kůdela
PublisherSpringer
Pages183-195
Number of pages13
ISBN (Electronic)9783030616595
ISBN (Print)9783030616588
DOIs
Publication statusPublished - 2021

Publication series

NameStudies in Fuzziness and Soft Computing
Volume403
ISSN (Print)1434-9922
ISSN (Electronic)1860-0808

Keywords

  • Algorithm tuning
  • Combinatorial optimization
  • Parameter tuning

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Training Sets for Algorithm Tuning: Exploring the Impact of Structural Distribution'. Together they form a unique fingerprint.

Cite this