Contact Information:

Myllymäki, Petri J
University of Helsinki
B430, P.O.Box 26
Helsinki, Finland FIN-00014
Phone: +358 9 708 44212
EMail: Petri.Myllymaki@cs.Helsinki.FI

Abstract ID: A517

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

Lahtinen, Jussi
Myllymäki, Petri
Silander, Tomi
Tirri, Henry
Wettig, Hannes
University of Helsinki

Abstract

In the literature there exist several stochastic methods for solving NP-hard 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.

Content Areas: search, applications, genetic algorithms

Statement of sole submission: "The author(s) certifies that this paper has not been accepted by and is not currently under review for another conference or journal. Nor will it be submitted for such during AAAI-98's review period.