Information Technology Reference
In-Depth Information
continuously changing current status of the road segments is integrated into the
optimization process.
2.2 How Ant Systems Perform Routing Tasks
Ant algorithms are explicitly designed to perform dynamic routing tasks. They
resemble the behaviour of ant colonies in nature. The difference to classical
routing algorithms is the following:
Eager computing:
Ant systems compute routing information continuously be-
tween any potential query points. This is called the eager computing strategy:
The result is already computed for the current situation before the query is
asked.
Off-board middleware:
Ant systems are performed on an off-board middle-
ware which is the necessary prerequisite for passing current information gath-
ered by thousands of individuals to thousands of applying users.
Statistical compression of individual information:
The dynamic infor-
mation obtained by individuals is not stored individually but collected in
pheromones
which are information chunks containing quality information
for links with respect to a certain target. For each target, each link has got its
own pheromone value. This considerably condenses the information individ-
ually obtained. Since the pheromones are target-oriented, the pheromones
do not just evaluate single road segments, but the total route from the place
they are stored to the desired target.
Local information first:
The local use of pheromones enables the system to
give the answer in which direction to proceed within fractions of a second
even if the total route has not been computed yet. This even applies to
dynamic changes that just occurred.
First, we describe general properties all artificial ant systems share. Ant sys-
tems operate on an underlying graph and solve dedicated constraint problems.
These problems may be scheduling or path finding tasks or combinations thereof.
In principle, any constraint problem may be solved with ant systems as long as
the underlying graph is properly defined.
An (artificial) ant is a software unit. Such units are continuously generated
over time by the ant system. Each ant uses the current state of data of the
underlying graph, considers the current constraints to be solved at the time of
its generation, and tries to find a single solution for this problem. Each ant is
influenced by the pheromones of the graph links lying directly ahead. It will not
automatically use the link with the best pheromone values, but rather decide
that probabilistically: The better a pheromone value, the more likely an ant will
use it. After having found a solution, each ant gives feedback modifying the
pheromones attached to the links this ant has used for its solution. The amount
of modification depends on the quality of the result discovered by the ant. Thus,
the pheromones represent the collected memory of previous ants having used the
respective edge. Subsequently generated ants are biased by these pheromones for
