| Abstract: |
Algorithm tuning, especially in the context of metaheuristic algo- rithms, 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 in- stances. There is much interest (but little research so far) on the relationship be- tween the training set and generalization performance. In general terms, we ex- pect that, if an algorithm is targeted at problems of a certain type, then the train- ing 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 re- search. In this paper we explore how certain structural aspects of the training set problem instances (in contrast, for example, to problem size) affect generali- zation performance. Specifically, we look at spaces of simple TSP instances where the number of cities are 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 tar- get 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 re- al-world optimizers for specific problem classes, such as, for example, vehicle routing problems with particular depot and customer distributions. |