非表示:
キーワード:
-
要旨:
Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has
become very popular for solving
problems from combinatorial optimization. Solutions for a given problem are
constructed by a random walk on a so-called construction graph. This random
walk can be influenced by heuristic information about the problem. In contrast
to many
successful applications, the
theoretical foundation of this kind of randomized search heuristic is rather
weak. Theoretical investigations with respect to the runtime behavior of ACO
algorithms have been started only recently for the optimization of
pseudo-boolean functions.
We present the first comprehensive rigorous analysis
of a simple ACO algorithms for a combinatorial optimization problem. In our
investigations we consider the minimum spanning tree problem and examine the
effect of two
construction graphs with respect to the runtime behavior.
The choice of the construction graph in an ACO algorithm seems to be crucial
for the success of such an algorithm.
First, we take the input graph itself as the construction graph and analyze
the use of a construction procedure that is similar to Broder's algorithm for
choosing a spanning tree uniformly at random. After that, a more incremental
construction procedure is analyzed. It turns out that this procedure is
superior to the Broder-based algorithm and produces additionally in a constant
number of iterations a minimum spanning tree if the influence of the heuristic
information is large enough.
