Ant Colony–Based Simulation 121
FIGURE 5.8: Ant-clustering with Swarm.
Ant-clustering can be applied to mor e practical problems by extending this
part.
5.6 Ant colony–based approach to the network routing
problem
The Internet is one of the most extensively engineered objects today.
Packet switching, a method to transfer data developed in the 1960s, breaks
down data into small packets, sends these packets to the destination along
totally different paths, and recovers the data at the destination. The power of
packet s w itching changed the Internet from an academic and military tool to
a mass medium. However, the traffic on the Internet cannot be predicted, and
the utilization efficiency is not necessarily high. The routing on the Internet is
large-sc ale and dynamic, so it is not easy to understand the entire structure.
Furthermore, throughput and quality of service (QoS) must be increased de-
spite the difficulty of centralized control. The objective in the routing problem
is to optimize the routing table (a table specifying the node to which a pa cket
for a predetermined destination should be forwarded) for each node such that
the throughput of the entire system is increased (Fig. 5.9).
Each node can only recog nize nearby traffic; therefore there is a table
for every node. The SPF (shortest path first) routing cur rently used in the
Internet compiles routing tables from information that can be recognized by
the respective node. In contrast, Dorigo et al. proposed AntNet routing based
122 Agent-Based Modeling and Simulation with Swarm
K
B
C
A
Y
Z
X
ࡁ࠼
K
࡞࠹ࠖࡦࠣ࠹ࡉ࡞
⋡⊛
X
Y
Z
ᰴࡁ࠼
A
B
C
crowded
unknown
Routing table for node K
destination
next node
FIGURE 5.9:
Routing table.
out-bound: table reference
in-bound: table update
FIGURE 5.10: Agent-based routing.
Ant Colony–Based Simulation 123
on ACO. This method deploys software agents on the network that collect
routing data by moving back and forth be tween the source and the destination
and upda ting routing tables in intermediate nodes (Fig. 5.10).
Agent-based routing results in a n overhead that is not necessary in static
routing; therefore the total traffic and cost performance are important factors.
The steps in AntNet are as follows:
1. Ants are regularly released from each node to random destinations.
2. Ants select paths using pheromo nes and heuristics and reach their re-
sp e c tive destinations. Ants remember the time that they took and the
nodes that they visited.
3. Ants that reach their respective destinations return to the origin by
moving along the path in reverse order while updating the table in each
node.
4. Return to 1.
Similar to the example in the T SP (see eq. (5.5)), the probability that a node
is selected as the next node is determined using a weight ω by the following
equation:
p
k
ij
(t) =
ω · τ
ij
(t) + (1 − ω) · η
ij
(t)
P
h∈J
k
i
ω · τ
ih
(t) + (1 − ω) · η
ih
(t)
, (5.9)
where J
k
i
is the set of all cities that ant k in city i can move to (but has not yet
visited). The pher omone table in each node is updated through the following
equations:
τ
ij
(t + 1) ⇐ (1 − ρ) · τ
ij
(t) + ∆τ
ij
(t) (update) (5.10)
∆τ
ij
(t) =
n
X
k=1
Q(k) (addition) (5.11)
τ
ij
(t + 1) ⇐
τ
ij
(t)
1 + ∆τ
ij
(t)
(evap oration) (5.12)
The status o f the network is not constant in AntNet unlike in ACOs.
Therefore, ants move along the paths that packets move to evaluate the status
of the network, and return along the same path to reflect the evaluation. As
a consequence, the upda ting of the pheromone tables is not synchronic.
Dorigo et al. tested the AntNet system on a simulator of network file sys-
tem (NSF), a co re network in the USA, and compar e d it with routing methods
such as Bellman– Ford, SPF, and OSPF (open shor tes t path first) [15]. Fig-
ure 5.1 1 shows the results of tests when there are hot spots. A constant bit
rate (CBR) with constant traffic patterns and a variable bit rate (VBR) were
124 Agent-Based Modeling and Simulation with Swarm
㪇
㪉
㪋
㪍
㪏
㪈㪇
㪈㪉
㪭㪙㪩
㪚㪙㪩
㪭㪙㪩
㪚㪙㪩
㪭㪙㪩
㪚㪙㪩
㪭㪙㪩
㪚㪙㪩
㪭㪙㪩
㪚㪙㪩
㪭㪙㪩
㪚㪙㪩
㪘㫅㫋㩷㪥㪼㫋 㪦㪪㪧㪝 㪪㪧㪝 㪪㪧㪝㩷㪈㪝 㪛㪸㪼㫄㫆㫅 㪙㪝
㪸㫍㪾㪅㩷㪻㪼㫃㪸㫐㩷㫋㫀㫄㪼㩿㫊㪼㪺㪅㪀 㫋㪿㫉㫆㫌㫇㫌㫋㫊㩿㪈㪇㪵㪎㪆㫊㪼㪺㪅㪀
FIGURE 5.11:
Comparison of AntNet and other routing metho ds
(from [15]).
tested. The performance under low network load was high with all algorithms,
and the thro ughput when the lo ad was high became similar. In both condi-
tions, AntNet achieved shorter delays with high throughput. In particular,
AntNet showed superior performance when the load s uddenly changed (hot
sp ots had formed). The overhead of ant agents was negligible in the tests.
There are many examples of research on routing using ACOs; for instance,
Telecom Bretagne is working on smoothing of QoS. Applications to ATM
networks and w ireless environments are a lso being investigated.
5.7 Ant-based job separation
Another well-known ecology of ants is social division of labor. Ant colonies
consist of ants with various roles such as q uee n ants, soldier ants, and worker
ants. These roles are called “ c astes,” and some of these (e.g., queen ants) have
physically specialized functions. However, gener al work including collecting
and looking after larvae is c arried out by worker ants in turn, and no individual
is designated to perform a given task. It is also known that for a species
where soldier ants divide labor with o ther worker ants, soldier ants do the
work of worker ants if worker ants are removed from the nest. Distributing an
Ant Colony–Based Simulation 125
appropria te number of ants to each task is necessary to increa se the fitness of
the colony as a whole. Ants can divide labor without any centralized control;
such autonomous distribution of tasks would be useful in the field of rob otics or
scheduling in factories. The next equation is proposed as a model for assigning
workers to multiple ta sks through distributed control.
T
θ
(s) =
s
n
s
n
+ θ
n
(5.13)
For instance, T is defined as tasks such as feeding larvae. The probability that
a given ant does this task T
θ
is determined by the amount of pheromone s
that the larvae emit and the thre shold for each individual θ.
In reality, larvae secrete more pheromone when they are hungry, and reduce
the amount of pheromone secretion when caretakers p e rform their tasks. In-
dividual ants go out to collect food when the amount of detected pheromone
becomes lower than a threshold value, and conversely, when the amount of
pheromone from larvae exceeds a threshold, ants that returned from collect-
ing food become caretakers. There is a distribution of the threshold in each
individual; therefore appropriate numbers of individuals can be distributed to
multiple tasks.
Such a behavior model can be applied to the problem of task distribution
in robots capable of multiple tasks or fault-tolerant systems. For example, a
solution that uses agents called routing wasps has been proposed for scheduling
tasks in a factory [16]. In this system, pseudo-pheromones ar e emitted from
tasks in a queue based on priority and wait time. Agents are assigned to each
assembly machine, and thresholds to perform specific tasks are determined
based on the status of each machine. Agents a ssign tasks to each machine
with probabilities determined by threshold values and amounts of pheromone.
Such a system was shown to increase throughput of a factory.
Ant methods are being implemented in various ways in industry. For ex-
ample, Bios Group
1
based in New Mexico is a consulting firm which builds
systems based on s warm intelligence, and has provided methods to make
scheduling efficient to Southwest Airlines and P&G, for example. P&G uses
distributed scheduling where collaborative decisions such as transport of raw
materials and management of factories are made by agents on a network. The
swarm approach is used to build a system where the transport path is deter-
mined by taking into account the utilization of overcrowded warehouses in the
candidate paths.
1
http://www.biosgroup.com/
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.