Zorizko instantzia uniformeak sortzen al dira optimizazio konbinatorioan?

Abstract

In evolutionary computation, it is common practice to use sets of instances as test-beds for evaluating and comparing the performance of new optimisation algorithms. In some cases, real-world instances are available, and, thus, they are used to constitute the experimental benchmark. Unfortunately, this is not the general case. Due to the diculties for obtaining real-world instances, or because the optimisation problems dened in the literature are not exactly as those dened in the industry, practitioners are forced to create articial instances.
In this paper, we study some aspects related to the random generation of articial instances. Particularly, we elaborate on the assumption that states that sampling uniformly at random in the space of parameters is equivalent to
sampling uniformly at random in the space of functions. Illustrated with some experiments, we prove that for some type of algorithms this assumption does not hold.