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

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.