Information Technology Reference
In-Depth Information
their own construction of a solution. This is how they resemble the behaviour of
real ants.
Ant systems found quite a few applications in logistics (for a real life appli-
cation, cf. [2]). In these applications, the ant systems solve different variants of
the vehicle routing problem.
In the following, we confine to the application of path finding in navigation
systems: In this application, ant systems use the normal road network as graph.
The nodes are the junctions and the edges are the individual road segments.
For each node, there is a routing matrix evaluating the quality of using a cer-
tain adjacent edge in order to reach a certain selected target. This corresponds
to the standard computer network protocols where ant systems have already
been successfully applied (cf. [4]). The quality measures of this matrix are the
pheromones. Note that the pheromones attached to an edge are not the same
as the current cost function for this edge, because the pheromones do not only
consider this edge but also all edges possibly behind on the way to the target.
For each (source, target) pair, ants are continuously produced at their source
node. The task of each ant is to find a path to the specified target node.
For each path finding, the probability that an ant selects a certain edge de-
pends not only on the quality of pheromones attached so far, but also on some
heuristic value, which may directly involve the graph's cost function. The trade-
off may be tuned by several parameters. In general, the mutual consideration
of task oriented pheromones and network oriented heuristic values ensures a
balance between the emergence of stable paths and the adaptivity to dynamic
changes.
In navigation, the path finding and updating functionalities of ants are tem-
porally interweaved. This enables a highly parallel process, but this requires
a suitable software environment to support that. In other applications of ant
algorithms like scheduling, the solution finding and updating phases are more
separated.
After an individual ant has found a path to the target, the update of the
pheromones works as follows: The pheromone values of the edges used are in-
creased, and the pheromones of the edges not used (but adjacent to the nodes
used) are decreased. The latter process resembles evaporation which has been
proven very practical in nature, because this gives more recent data a higher
influence than older data. However, the difference gap by which the pheromones
of the edges used are increased and the others are decreased depends on the
quality of the overall route: The longer the travel time, the smaller the differ-
ence gap. This technique results in a rather fast emerging of good routes used
by the majority of the ants.
For further information about ant systems and the details of the formulae
used, we refer to the standard literature such as [9], [7], [8], [13]. Also in the
master's thesis [1] which is the long version of this paper, the formulae are
elaborated explicitly.
