23-05-2012, 03:12 PM
Ant Colony Optimisation
Ant Colony Optimisation.pdf (Size: 100.34 KB / Downloads: 43)
Introduction
The Ant Colony Optimisation algorithm framework here-on referred to as ACO is a new algorithmic
framework which is inspired by the foraging patterns of biological ants. Any ACO algorithm (of
which there are many) serves to optimise some problem instance by generating a series of solutions
to the problem and using the utility (goodness) of these solutions to influence future solution
construction.
This report outlines the biological inspiration behind the development of the first ant-inspired
algorithms. The report then identifies two of these ant-inspired algorithms, their relation to the
biological models and offers a contrast and comparison between them. Finally the report describes
and analyses the ACO meta-heuristic framework to which a subset of ant-inspired algorithms belong.
The report is organised as follows. Section 2 describes the recruitment and foraging behaviour of
four species of ants. Section 3 identifies two ant-inspired algorithms: Ant Systems (AS) and ant
colony optimisation for continuous design spaces. Finally Sec. 4 defines the ACO meta-heuristic
framework and comments on the properties of the framework and it’s relation to ant-inspired
algorithms.
Biological Beginnings
This section outlines the biological inspirations underpinning the recent developments in ant inspired
search algorithms for optimisation. This section highlights specific characteristics of biological
models which have been used to develop optimisation algorithms as well as highlighting other
properties of the biological systems which may provide useful inspiration for the development of
new ant inspired algorithms.
The Cataglyphis and Ocymyrmex Species
It was mentioned briefly in the introduction that ACO is based on the foraging behaviour of
(biological) ants, i.e. how the ants locate and collect food. However so many species of ant exist, each
of which exhibits a distinctly different foraging behaviour, that it is more accurate to describe ACO
as being inspired by the recruitment strategy of ants which use chemical markers (pheromone
trails) to mark the location of a rich food source such as the Iridomyrmex humilus (Argentine ant)
species. Before elaborating on this point though let’s have a look at two different species of ant,
the cataglyphis and ocymyrmex ants of the Sahara and Namib deserts respectively.
The Sahara and Namib deserts are two of the most unforgiving environments on our planet, yet
two species of ants: the cataglyphis and ocymyrmex have evolved to fill this unique ecological niche
(For a further discussion of these species refer to [14]). Both of these species rely on the harsh
environment to provide them with food, since they search their local area for insects which have
succumbed to the extreme heat and stress of this harsh environment. What is interesting about
these ants is that they don’t use a chemical marker to recruit other ants to a food source rather
they use an internal memory to influence their own choice of a direction to travel from the nest.
The rules for movement of these species have been described as:
c Daniel Angus 2006
• Continue to forage in the direction of the preceding foraging trip whenever this trip has been
successful in finding food.
• If foraging trip is unsuccessful then abandon this direction and randomly select a new direction,
decreasing the probability of doing so as the number of previously successful runs
increases.
This individual behaviour leads to an efficient (for this specific environment) foraging pattern which
in the absence of food will result in the ants searching the environment at random, or in the case of
food being found will subtract foraging resources away from the global pool of resources to exploit
this discovered food source until it is eventually consumed, at which point the colony will revert to
its initial behaviour with a slight bias towards searching previously promising areas. It is important
to note that this bias will only exist for the life of the ant which found food in this sector, and that
if food is found again in this biased area then this ant will die out reverting the colony back to its
initial completely random state.
Interestingly enough if one were to hypothesise about placing two different abundant food resources
within close and far foraging range of the colony that the emergent effect would be that the members
of the colony would split randomly between the resources and stick to one even though one resource
is better (i.e. The closer the food to the nest the quicker it is to forage from hence this resource
may be considered better). This is because with the simple model described above there is no
intra-colony communication mechanism, which would allow the colony to converge on the better
resource. This is not of concern however since these species have evolved to exhibit a decentralised
control which augers well with their inherently unstable and dynamic environment.
The Tetramorium Caespitum Species
Tetramorium caespitum ants are quite distinct from the desert dwelling ants described above (This
species and its recruitment behaviour is fully described in [12]). These ants have evolved to suit a
different ecological niche where food sources are plentiful and the desired effect is to optimise the
distribution of resources to maximise the food collection activity. These ants also rely on randomness
to influence their decision making behaviour, however with the absence of a long term memory they
rely more on intra-colony communication mechanisms to influence their foraging decisions.