Information Technology Reference
In-Depth Information
We tested this by a high variety of experiments to various (source, target) pairs
in several maps. In many cases, the system behaved as wanted. The response
time varied between instantly and less than 5 seconds. Only in some cases, we
realized that the system got stuck in a nonoptimal route.
Careful analysis revealed the following: AntNet tends to prefer routes with
fewer decision alternatives, i.e. paths with nodes of lower degree. This even holds
when the selected route is considerably longer than the optimal one (more than
20 %).
By the following techniques, this behaviour can be avoided: Ants passing
nodes with a higher degree get a higher relevance for updating the pheromones.
An alternative or supplementing strategy is to make the number of generated
ants dependent on the number of neighbors of the source: The more neighbors,
the more ants are generated.
4.3 Oscillation
Due to the nondeterministic behaviour, the preferred routes oscillate between
several candidates continuously.
We observed that such an oscillation only occurs when the routes do not differ
more than 7 % from the average among all routes ever suggested. This implies
that oscillating occurs only between routes that differ at most 14 %.
All experiments showed the following correlation: The more similar two routes
were concerning their quality, the more oscillation occurred between them.
This is a reasonable behaviour which is easy to explain for a probabilistic
algorithm. We suggest to utilize this for the following:
In real life, a driver who asked for a route should retain this route once he
is suggested one. But the oscillating behaviour results in different routes for
different drivers. Due to the observed correlation between frequency of oscillation
and similarity of route qualities, this results in a perfect distribution of trac
among almost equal routes. Since this distribution is organized at random, we
expect also a high social acceptance.
Thus, ant algorithms are very suitable for trac management as a side effect.
5Conluon
This paper described the construction and evaluation of the software AntScout
which applies ant colonies for routing in real road maps extracted from Open-
StreetMap. AntScout is prototypic, but it offers an interface comfort that makes
it testable by third parties.
AntScout proves that ant algorithms may be applied even without hierarchies
in real maps with up to 150 nodes on a modern laptop. The response to sudden
changes in the map (simulating trac jam and its resolution) is rather fast (less
than 5 seconds). The quality of the suggested routes is very reasonable: The
simulation switches between the best route and alternatives that were within 14
per cent off the optimum.
Conceptually, the improvements to the state-of-the-art are the following:
