116 Agent-Based Modeling and Simulation with Swarm
5.3 Ant colony optimization (ACO)
Optimization a lgorithms based on the collective behavior of ants are called
ant colony optimization (ACO) [31].
ACO using a pheromone trail model for the TSP uses the following algo-
rithm to optimize the travel path.
1. Ants are placed randomly in each city.
2. Ants move to the next city. The destinatio n is probabilistically deter-
mined based on the information on pheromones and given conditions.
3. Repeat until all cities are visited.
4. Ants that make one full cy c le secrete pheromones on the route according
to the length of the route.
5. Return to 1 if a satisfactory solution has not been obtained.
The ant colony optimization (ACO) algorithm can be outlined as follows.
Take η
ij
as the distance between cities i and j. The probability p
k
ij
(t) that
an ant k in city i will move to city j is determined by the reciprocal of the
distance 1/η
ij
and the amount of pheromone τ
ij
(t) (eq. (5.1)):
p
k
ij
(t) =
τ
ij
(t) × η
α
ij
P
h∈J
k
i
τ
ih
(t) × η
α
ih
. (5.1)
Here, J
k
i
is the set of all cities that the ant k in city i can move to (has
not visited). The condition that ants are more likely to select a route with
more pheromone r e flec ts the p ositive feedback from past searches as well as
j
1
j
2
j
3
i
t
ij
ij
1
amount of pheromone
distance
FIGURE 5.5:
Path selection rules of ants.
Ant Colony–Based Simulation 117
TABLE 5.2: Comparison between ACO and metaheuristics.
TSP ACO GA EP SA Optimal
Oliver 30 420 421 420 424 420
[830] [3200] [40,000] [24,617]
Eil 50 425 428 426 443 425
[1,830] [25,000] [1 00,000] [68,512]
Eil 75 535 545 542 580 535
[3,480] [80,000] [3 25,000] [173,250]
KroA 100 21,282 21,761 N/A N/A 21,2 82
[4,820] [103,00] [N/A] [N/A]
a heuristic for searching for a s horter path. The ACO can thereby include an
appropria te amount of knowledge unique to the problem.
The pheromone table is updated by the following equations:
Q(k) = the reciprocal of the path tha t ant k found (5.2)
∆τ
ij
(t) =
X
k∈A
ij
Q(k) (5.3)
τ
ij
(t + 1) = (1 − ρ) · τ
ij
(t) + ∆τ
ij
(t) (5.4)
The amount of pheromone added to each path after one iteration is inversely
proportional to the length of the paths that the ants found (eq. (5.2)). The re-
sults for all ants that moved through a path are reflected in the path (eq. (5.3)).
Here, A
ij
is the s e t of all ants that moved on a path from city i to city j. Neg-
ative feedback to avoid local solutions is given as an evaporation coefficient
(eq. (5 .4)), where the amount of pheromone in the paths, or informa tion from
the past, is reduced by a fixed factor (ρ).
The ACO is an effective method to solve the traveling salesman problem
(TSP) compared to other search strategies. Table 5.2 shows the optimized
values for four benchmark problems and various minima found using other
methods (smaller is better, obviously) [31]. T he number s in brackets indica te
the number of candidates investigated. The ACO is more suitable for this
problem compared to methods such as a genetic algorithm (GA, Section 2.2),
simulated annealing (SA), and evolutionary programming (EP). However, it
is inferior to the Lee–Kernighan method (the current TSP champion code).
The characteris tic that specialized methods per form better in static problems
is shared by many metaheuristics (high-level strategies which guide a n under-
lying heuristic to increas e its performance). Complicated problems, such as
TSPs where the distances between cities are asymmetric o r where the cities
change dynamically, do not have established programs and the ACO is con-
sidered to be one of the most promising methods.
The length and pheromone accumulation of paths betwee n cities are stored
118 Agent-Based Modeling and Simulation with Swarm
FIGURE 5.6: TSP simulator by ACO.
in a table (Fig. 5.5). Ants can recognize infor mation on their surroundings,
and probabilistically decide the next city to visit. The amount of pheromones
added to each path after every cycle is inversely proportional to the length of
the cycle path.
An a pplet to solve the T SP using ants is provided for self-study (Fig. 5.6).
Operation procedures and displayed contests are almost the same as tho se
with the TSP by a GA (see Section 2.2.7 and Appendix A.3). The pa ths
between cities are color-coded based on the phero mone amount (a darker color
means more pheromones). The position of cities can be changed using the GUI;
therefore, the effects of pheromones and convergence are easy to understand.
Cities can be dynamically changed, yet ants can search with certain accuracy.
5.4 Ant-clustering algorithms
ACO is used in clustering and sorting. The following is a description of
ant-clustering.
Ants farm aphids and rear larvae in nests. Livestock a nd larvae are spa-
tially categorized and placed by size in “farms” and “nurseries” in ant nests.
It is considered that this ecology was developed to make feeding work more
efficient.
Ant Colony–Based Simulation 119
The ab ove behavior can be described by a distributed control model for
the probability that an agent picks up (P
pick
) or drops (P
drop
) an object.
P
pick
= (1 − χ) ·
k
pick
k
pick
+ f(i)
!
2
(5.5)
P
drop
= χ ·
f(i)
k
drop
+ f(i)
!
2
(5.6)
Here, f(i) is the density of nearby objects similar to i. To be more precise, this
is defined as a function that decreases with an increasing number of similar
objects nearby.
f(i) =
(
P
j∈N (i)
d(i,j)
|N (i)|
if N(i) 6= φ
1 if N(i) = φ
(5.7)
d(i, j) is the similarity (distance in feature space) between objects i and j,
and N (i) is a set of neighbors of object i. d(i, j) is normalized such that
0 ≤ d(i, j) ≤ 1. d(i, j) = 0 means that two objects are identical. Values k
pick
and k
drop
are par ameters that indicate thresholds in picking up and dropping
behavior, respe c tively. χ is a reactio n coefficient determined by the number of
objects n in the Moore neighborhood (neighbors in eight directions: top and
bottom, right and left, four diagona ls).
χ =
n
2
n
2
+ k
2
crowd
(5.8)
k
crowd
is the threshold, and χ = 1/2 when n = k
crowd
. χ approaches 1
when there are more objects in the neighborhood, and the behavior is biased
towards dropping. On the co ntrary, fewer objects mean a higher likelihood of
picking up behavior.
Equations (5.5) and (5.6) represent a model where agents (ants) randomly
acting on a plane move objects based on environmenta l par ameters. In other
words, the probability that an agent picks up or drops an object is deter-
mined by the density of similar objects in the neighborhood. Agents pick up
objects in low-density neighborhoods and drop objects in high-density neigh-
borhoods while moving randomly, and as a result, clusters of similar features
are segregated.
The result o f ant-clustering, where ants pick up or drop an object based on
the above rules and move one step in a randomly chosen dir e c ti on, is shown
in Fig. 5.7. Here, objects of a different color belong to a different class. This
two-dimensional space has a torus topology (the right edge is connected to
the left edge , and the top edge is connected to the bottom edge). Ants move
randomly at first, and then start to form s mall pre-clusters. These pre-clusters
gradually attract similar objects to form larger clusters. Transport by ants
120 Agent-Based Modeling and Simulation with Swarm
(a) (b) (c)
FIGURE 5.7: Ant-clustering.
and accumulation of objects form a positive feedback loop that increases the
cluster size, r e sulting in a clusterization process.
Details on ant-clustering are given in references [28, 45].
5.5 Swarm-based simulation of ant-clustering
The state of execution of a nt-clustering by ACO is shown in Fig. 5.8. In
this simulation, variables k
pick
, k
drop
, k
crowd
, e tc., in Equations (5 .5), (5.6),
(5.8), number of ants, and number of objects (number of red and blue objects)
can be se t during execution. Since the “seed” of a random number can be set,
re-execution with a different random number is also possible.
Feature values of an object are defined by the buildObjects method in
the ModelSwarm.java file as follows:
// Feature vector of red object
v = new double[] { 0.1 + rGen.nextDouble()*0.15,
0.1 + rGen.nextDouble()*0.15,
0.1 + rGen.nextDouble()*0.15};
// Feature vector of blue object
v = new double[] { 0.7 + rGen.nextDouble()*0.15,
0.7 + rGen.nextDouble()*0.15,
0.7 + rGen.nextDouble()*0.15};
Features in this case are a three-dimensional vector. For generating those
objects, a uniform random number vector (each element in the range of 0.0–
0.15) is added to (0.1, 0.1, 0.1) or (0.7, 0.7, 0.7). Similarity between two objects
is calculated by using the norm of the difference of those feature vectors (the
calcDistance method inside DataUnit.java).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.