The Trade-off between Solution Quality and Computing Times of Intelligent Algorithms - A Computational Study on the Role of Parameters and Time Budgets

Many heuristic search methods have been derived by analogy from natural processes and applied to practical optimization problems recently. Considering the variety of methods available, the question arises how "good" or "bad" the methods are in relation to each other. To answer this question, a large series of test runs was performed. The underlying application problem is a sequencing problem. The methods under study are: simulated annealing, tabu search, threshold accepting, genetic algorithms, and parallel recombinative simulated annealing. It is shown that the performance of all methods - in terms of both solution quality and computing time - depends strongly on their parameters. Since the computing times needed vary considerably, a second test series was designed. All methods were allowed to use the same runtime budget. The obvious trade-off between the solution quality desired and the computing time allowed is discussed. 1 Purpose of the Study In this paper, several heuristic meth..