Information Technology Reference
In-Depth Information
why we did not model each ant as an independent actor for eciency reasons. We
rather modelled an ant to be a state of the nodes which are communicated and
transformed among the neighbors. Thus, an ant colony system may be regarded
a discrete state automaton. The handling of ants as passive states instead of
active actors is a software acceleration which we see crucial for reducing the
run time of a classical ant algorithm. Thus, an “ant” in our implementation is
nothing else than a unit adding the current cost measures of the edges used until
the target is reached.
3.5 Conceptual Improvements by AntScout
At initialization, the pheromone matrix has to start with some values. According
to the theory, all prepheromones should start with the same values, because no
ants have passed so far. If the segment lengths are added to that, this would
result in a greedy strategy at the beginning.
We decided not to start with such a crude strategy and then let the ant colonies
find suitable values statistically, but rather with initial values obtained from
deterministic methods. Since we had to solve the all pairs shortest path problem,
we did not apply Dijkstra's algorithm for each source, but rather applied the
algorithm of Floyd-Warshall (for a modern description cf. [3], ch. 25.2) which is
a little faster for that problem. This guarantees much faster convergence at the
beginning.
Since the statistical path finding does not guarantee that each ant reaches
its target at some time (e.g., the ant may get stuck in a loop), ants have to be
removedafterawhile.[9]suggeststoremoveanant,aftertheantrunintoaloop.
We first implemented this suggestion, but then found much better convergence
when instead an ant is removed after a certain time has elapsed. For different
networks, this time should depend on the size of the network.
Since the number of (source, target) pairs grows quadratic in the size of the
network, it is important to control the number of ants generated for a given
(source, target) pair. The trade-off is the following: The fewer ants are generated,
the less computation load to the system (which is a trivial observation), but
the more ants are generated in a certain time interval, the faster the expected
convergence.
We applied the following approach to solve this dilemma: At each source
s
,
ants are generated heading towards a predefined target
t
. Note that ants heading
to a further distant target
t
, also pass other targets
t
i
on their path from
s
to
t
.
The closer
t
i
from
s
, the higher the probability that an ant originally heading to
t
will also pass
t
i
. Catching up an original idea of Dorigo, Walther [10] already
mentioned that the pheromones referring to targets
t
i
should also be updated by
ants heading to
t
which would increase the accuracy of the pheromones referring
to the trip from
s
to
t
i
. Thus, if the generation frequency is the same for all
(source, target) pairs, the accuracy for closer relations is much better than for
further relations. This is exactly the opposite of what a user wants to see, because
in closer relations the absolute quality difference between different routes is much
less than for more distant relations. We compensate this by creating more ants
