Chapter 5
Ant Colony–Based Simulation
We enter my study, candle in hand. One of the windows had
been left open, and what we see is unforgettable. With a soft
flick-flack the great Moths fly around the b el l-jar, alight, set
off again, come back, fly up to the ceiling and down. They
rush at the candle, putting it out with a stroke of their wings;
they descend on our shoulders, clinging to our clothes, grazing
our faces [37, pp. 168–169].
5.1 Collective behaviors of ants
Ants mar ch in a long line. There is fo od at one end, a nest at the other. This
is a familiar scene in gardens and on roads, but the sophisticated distributed
control by these small insects was recognized by humans only a few decades
ago.
Ants established their life in groups, or colonies, more than a hundred
million years before humans appe ared on Earth. They formed a society that
handles complex tasks such as food collection, nest building, and division of
labor through primitive methods of communication. As a result, ants have
a high level of fitness among species, and can adapt to harsh environments.
New ideas including routing, agents, and distributed control in robotics have
developed based on simple models of ant behavior. Applications of the ant
behavior model have been used in many papers, and are becomin g a field of
research rather than a fad.
Marching is a cooperative ant behavior that can be explained by the
pheromone trail model (Fig. 5.1 ). Cooperative behavior is frequently seen
in ant colo nies, and has attracted the interest of entomologists and behavioral
scientists. Pheromones ar e volatile chemicals synthesized within the insect,
and are used to communicate with o ther inse c ts of the same species. Exam-
ples are sex pheromones that attract the opposite sex, alarm pheromo nes that
alert group members, and trail pheromones that are used in ant marches.
Pheromones are discuss e d in a chapter of the well-known Souvenirs Ento-
mologiques by Je an-Henri Fabre (see the quote at the beginning of this chap-
ter).
However, recent research indicates that pheromones are effective within a
111
112 Agent-Based Modeling and Simulation with Swarm
FIGURE 5.1: Ant trail.
distance of only about 1 m from the female. Therefore, it is still not known if
males are attracted only because of the pheromones.
Many species of ants leave a trail of pheromo nes when carrying food to
the nest. Ants follow the trails left by other ants when searching for fo od.
Pheromones are volatile matter that is secreted while returning from the food
source to the nest. The experiments shown in Fig. 5.2 by Deneubourg and
Goss using Argentine ants linked this behavior to the search for the shortest
path [43]. They connected bridge-shaped paths (two connected paths) between
the nest and the food source, and counted the number of ants that used each
path. This seems like a simple problem, but because ants are almost blind
they have difficulty recognizing junctions, and cannot use c omplex methods
to communicate the position of the food. Furthermore, all the ants must take
the sho rter path to increase the efficiency of the group. Ants handle this task
by using pheromones to guide the other ants.
Figure 5.3 shows the ratio of ants that used the shorter path [43]. Almost
every ant used the sho rter path as time passed. Many of the ants return to
the shorter path, secreting additional pheromones; therefore, the ants that
followed als o take the shorter path. This model can be applied to the search
for the shortest path, and is used to solve the traveling salesman problem
(TSP) and routing of networks. There are many unknown factors about the
pheromones of actual ants; however, the volatility of pheromones can be uti-
lized to build a model that maintains the shortest path while adapting to
rapidly changing traffic. The path with a greater accumulation of pheromones
is chosen at junctions, but random fa c tors are inserted to avoid inflexible
solutions in a dynamic environment.
Ant Colony–Based Simulation 113
1
2
food
nest
12.5cm
nest
food
FIGURE 5.2: Bridge-shaped paths (adapted from Fig. 1a in [43], with per-
mission of Springer-Ve rlag GmbH).
㪇
㪈㪇
㪉㪇
㪊㪇
㪋㪇
㪌㪇
㪍㪇
㪎㪇
㪏㪇
㪐㪇
㪈㪇㪇
㪇㪄㪉㪇
㪉㪇㪄㪋㪇 㪋㪇㪄㪍㪇 㪍㪇㪄㪏㪇 㪏㪇㪄㪈㪇㪇
㪩㪸㫋㫀㫆㩷㫆㪽㩷㪸㫅㫋㫊㩷㫋㪿㪸㫋㩷㫌㫊㪼㪻㩷㫋㪿㪼㩷㫊㪿㫆㫉㫋㪼㫉㩷㫇㪸㫋㪿㩷㩿㩼㪀
㪫㫀㫄㪼㩷㫇㪸㫊㫊㪼㪻
FIGURE 5.3:
The ratio of ants that used the shorter path (adapted from
Fig. 1a in [43], with permission of Spr inger-Verlag GmbH).
114 Agent-Based Modeling and Simulation with Swarm
5.2 Swarm simulation of the pheromone trails of ants
An easy model can describe the actions of ants as follows:
• In the case of nothing, a random search is done.
• If the food is found, it takes it back to the hive. A homing ant knows
the positio n of the hive, and returns almost straig ht back.
• Ants that take the food back to the hive drop their pheromone.
Pheromones are volatile.
• Ants not having the food have the habit of being attracted to the
pheromone.
Figure 5.4 is the ex e c utio n sta te in Swarm. Here, the hives are placed in
the center, and there are three (lower right, upper left, lower left) food sources.
Figure 5.4(a) is the first random search pha se. In (b), the c loser lower right
and lower left food is found, and the pheromone trail is formed. The upper
left is in the middle of the formation. In (c), pheromone trails are formed
for all three sources, which makes the trans port more efficient. The lower
right source is almost exhaustively picked. In (d), the lower right food source
finishes, and the pheromone trail is already dissipated. As a result, a vigorous
transportatio n fo r the two sources on the left is being done. After this, all the
sources finish, and the ants return to random search again. The parameters
in the simulation are shown in Table 5.1.
In this program, at the time of stopping, food locations and various pa-
rameters can be changed dynamically. For this purpose, the probe method is
used, as described in Section 3.2.7. Specific ope rations are as follows:
• To change evapora tion and diffusion coefficients: Enter the variable and
press “enter.” Then click “initializeEvaporationAndDiffusionRate.”
• To change the bugs’ parameters or colony size: Enter the variable and
press “enter.” Then click “initializeBugAndColonySize.”
• To change foods’ positio ns: Enter x, y coordinates and press “enter.”
Then click “initializeFood.”
• To add a food source: Enter x, y coordinates and ra dius and press “enter.”
Then click “initializeFood.”
• To delete a food source: Enter the minus value in the food’s radius and
press “enter.” Then click “initializeFood.”
Let us try and check how the ants’ behavior changes when the food loca-
tion is changed. Especially, how robust is the search using pheromones under
disturbances?
Ant Colony–Based Simulation 115
(a) (b)
(c) (d)
FIGURE 5.4 (See Color Insert): Pheromone trails of a nts.
TABLE 5.1: Parameters of the pheromone trails of ants.
Parameter Meaning Range
amountOfReleasingPheromone Amount of pheromone dr opped. 0∼
evaporationRate Ratio of pheromone that evap o-
rates to the a mount dropped on
the ground.
0 1
diffusionRate Proportion of the evaporated
pheromone tha t diffuses.
0∼0.2
awayFromColonyRate The proportion of priority given
to the pheromone away from
the hive. Ignores the direction of
hive when 1.
1∼
turnRate The proportion of not go-
ing straight when searching for
fo od. Becomes a random walk
when 1.
0∼1
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.