|
The ant colony optimization
algorithm (ACO),
introduced by Marco
Dorigo in his doctoral thesis in 1992, is a probabilistic
technique for solving computational problems which can be reduced to
finding good paths through graphs.
They are inspired by the behavior of ants in finding paths from the
colony to food.
In the real world, ants (initially) wander randomly, and upon
finding food return to their colony while laying down pheromone
trails. If other ants find such a path, they are likely not to keep
travelling at random, but to instead follow the trail, returning and
reinforcing it if they eventually find food.
Over time, however, the pheromone trail starts to evaporate, thus
reducing its attractive strength. The more time it takes for an ant
to travel down the path and back again, the more time the pheromones
have to evaporate. A short path, by comparison, gets marched over
faster, and thus the pheromone density remains high as it is laid on
the path as fast as it can evaporate.
Thus, when one ant finds a good (short, in other words) path from
the colony to a food source, other ants are more likely to follow
that path, and positive feedback eventually leaves all the ants
following a single path. The idea of the ant colony algorithm is to
mimic this behavior with "simulated ants" walking around
the graph representing the problem to solve.
Ant colony optimization algorithms have been used to produce
near-optimal solutions to the travelling salesman problem. They have
an advantage over simulated annealing and genetic algorithm
approaches when the graph may change dynamically; the ant colony
algorithm can be run continuously and adapt to changes in real time.
This is of interest in network routing and urban transportation
systems.
PDF
Following is the proof for the convergence in value and convergence in
solution of ACO algorithms, with the descriptions of limitations needed for this
convergence to occur. The work is derived and guided by Dorigo's book Ant Colony
Optimization (2004). PDF
Data Organization in Unstructured Distributed Environments
We are trying to apply this approach to the problem of data
organization in unstructured distributed environments, such as Grid or
unstructured P2P, in order to organize data by any kind of relation.
Such organizaiton would allow to produce not only keyword based queries
but also to retrieve any other kind of correlation between data.
The known algorithms in the unstructured peer-to-peer
environment use flooding or k-random walkers in order to find some
information stored in the network. We believe, that ACO with its
reinforcement of pheromone trails could provide a basis for more
effective and efficient organization and access of data.
The picture below represents the outcome of applying the ACO
approach to data organization. The large pile, containing a lot of
correlated data, has numerous long pheromone marked trails pointing to
it. The paths are built duiring the aggregation phase, where the ants
follow the pheromone trails and also reinforce them. The more data
comes into the pile the more the paths are reinforced and also the more
paths point to the pile. On the other hand, a small pile, containing
only few data, has very short pheromone paths pointing to it. The
reason for this comes from the fact, that only few ants used this
trails to drop the data in this pile.
Upgrading the Ant Model
Additional work is being done in the upgrading of the ant
model. In its basic sense, ants are simple processing units that
retrieve the information from the environment, perform an action based
on read information and store the result of the action (in the form of
the pheromone) back to the environment (such process is called
stigmergy). Ant model also predicts (LINK TO THE ACO.PDF) that ants
possess some internal values (thresholds) that determine their
behaviour and are used in order to adapt to changes in the environments
(when the lack of working ants forces the soldiers to take over the
jobs done by the working ants).
Therefore, the current ants can be seen as simple processing
units reacting to environmental changes, but with a fixed
functionality.
Our extended model upgrades the simple ant and gives it a
„mind“ composed of states. The ant reacts to the environment according
to the state it is in and the environment determines if it can proceede
to another state. Having only static „states of mind“ is equivalent to
the original ant model.
However, using techniques from reinforcement learning or from
classical machine learning, the states are no longer static and the ant
„learns“ how to process and react to the environment and how to
reinforce the pheromone trails. Such approach may provide level of
adaption to the generic ants to solve problems (in terms of efficiency)
for which they were not initially designed.
A picture below represents a state of a static „state of mind“
of an ant that aggregates correlated data into piles (used in
application for sorting data in a grid environment).
|
Selected Publications 