An Empirical Evaluation of Stochastic Search Methods in Real-World Telecommunication Domains

摘要

In the literature there exist several stochastic methods for solving NP-haid optimization problems approximatively. Examples of such algorithms include (in the order of increasing computational complexity) stochastic greedy search methods, simulated annealing, and genetic algorithms. In this paper we are interested in the problem, which one of these methods is likely to give best performance in practice, with respect to the computational effort required in applying the method. We study this problem empirically by selecting a set of stochastic algorithms with varying computational complexity, and by experimentally evaluating for each method how the goodness of the results achieved improves with increasing computational time. For the evaluation, we use two practical optimization problems closely related to real-world problems in telecommunications. To get a wider perspective of the quality of the results, the stochastic methods are also compared against special-case greedy heuristics. Our investigation indicates that although good results can be achieved by genetic algorithms, simpler stochastic algorithms can achieve similar performance with less computational resources. However, of the methods studied, genetic algorithms appear to be the most consistent in the sense that the variance in the quality of the results obtained is smallest with this approach.