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

Mashal Alkhalifa*, David Corne

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter


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
Number of pages13
ISBN (Electronic)9783030616595
ISBN (Print)9783030616588
Publication statusPublished - 2021

Publication series

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


  • Algorithm tuning
  • Combinatorial optimization
  • Parameter tuning

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computational Mathematics


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