Reducing the Experiments Required to Assess the Performance of Metaheuristic Algorithms

Abstract

Abstract. When assessing experimentally the performance of metaheuristic algorithms on a set of hard instances of an NP-complete problem, the required time to carry out the experimentation can be very large. A means to reduce the needed effort is to incorporate variance reduction techniques in the computational experiments. For the incorporartion of these techniques, the traditional approaches propose methods which depend on the technique, the problem and the metaheuristic algorithm used. In this work we develop general-purpose methods, which allow incorporating techniques of variance reduction, independently of the problem and of the metaheuristic algorithm used. To validate the feasibility of the approach, a general-purpose method is described which allows incorporating the antithetic variables technique in computational experiments with randomized metaheuristic algorithms. Experimental evidence shows that the proposed method yields a variance reduction of the random outputs in 78% and that the method has the capacity of simultaneously reducing the variance of several random outputs of the algorithms tested. The overall reduction levels reached on the instances used in the test cases lie in the range from 14% to 55%.