Engelbrecht Andries P. Computational Intelligence: An Introduction
Подождите немного. Документ загружается.
358 16. Particle Swarm Optimization
Table 16.1 Applications of Particle Swarm Optimization
Application References
Clustering [638, 639]
Design [7, 316, 700, 874, 875]
Scheduling [7, 470, 707, 754]
Planning [771, 775, 856, 886]
Controllers [143, 155, 297, 959]
Power systems [6, 296, 297, 299, 437, 444]
Bioinformatics [627, 705, 921]
Data mining [805]
4. Explain how PSO can be used to approximate functions using an n-th order
polynomial.
5. Show how PSO can be used to solve a system of equations.
6. If the basic PSO is used to solve a system of equations, what problem(s) do you
foresee? How can these be addressed?
7. How can PSO be used to solve problems with discrete-valued parameters?
8. For the predator-prey PSO, what will be the effect if more than one predator is
used?
9. Critically discuss the following strategy applied to a dynamic inertia weight:
Start with an inertia weight of 2.0, and linearly decrease it to 0.5 as a function
of the iteration number.
10. The GCPSO was developed to address a specific problem with the standard
PSO. What is this problem? If mutation is combined with the PSO, will this
problem be addressed?
11. Consider the following adaptation of the standard gbest PSO algorithm: all
particles, except for the gbest particle, use the standard PSO velocity update and
position update equations. The new position of the gbest particle is, however,
determined by using the LeapFrog algorithm. Comment on this strategy. What
advantages do you see, any disadvantages? Will it solve the problem of the
standard PSO in the question above?
12. Explain why the basic gbest PSO cannot be used to find niches (multiple solu-
tions), neither in parallel nor sequentially (assuming that the fitness function is
not allowed to be augmented).
13. Explain why velocities should be initialized to zero for the NichePSO.
14. Can it be said that PSO implements a form of
(a) competitive coevolution?
(b) cooperative coevolution?
Justify your answers.
15. Discuss the validity of the following statement: “PSO is an EA.”
Chapter 17
Ant Algorithms
Ants appeared on earth some 100 million years ago, and have a current total population
estimated at 10
16
individuals [378]. It is further estimated that the total weight of
ants is in the same order of magnitude as the total weight of human beings. Most of
these ants are social insects, living in colonies of 30 to millions of individuals. Ants
are not the only social insects living in colonies. The complex behaviors that emerge
from colonies of ants have intrigued humans, and there have been many studies of ant
colonies aimed at a better understanding of these collective behaviors. Collective ant
behaviors that have been studied include the foraging behavior, division of labour,
cemetery organization and brood care, and construction of nests. The South African,
Eug´ene Marais (1872-1936) was one of the first to study termite colonies. He published
his observations as early as 1927 in local magazines and newspapers. In his book, The
Soul of the Ant [558] (first published in 1937, after his death), he described in detail
his experimental procedures and observations of the workings of termite societies. The
Belgian, Maurice Maeterlinck (1862–1949), published TheLifeoftheWhiteAnt[547],
which was largely drawn from Marais’s articles (see the discussion in [558]).
Following on form this pioneering work, the French biologist Pierre-Paul Grass´e [333]
postulated on the mechanics of termite communication in his studies of their nest con-
struction behavior. Grass´e determined that a form of indirect communication exists
between individuals, which he termed stigmergy. It is through this local interaction
between individuals, and between individuals and the environment, that more complex
behaviors emerges. More recently, Deneubourg et al. [199] studied one example of stig-
mergy, namely pheromonal communication. From these studies, the first algorithmic
models of foraging behavior have been developed and implemented [208].
While most research efforts concentrated on developing algorithmic models of foraging
behavior, models have been developed for other behaviors, including division of labour,
cooperative support, self-assembly, and cemetery organization. These complex behav-
iors emerge from the collective behavior of very unsophisticated individuals. In the
context of collective behaviour, social insects are basically stimulus–response agents.
Based on information perceived from the local environment, an individual performs
a simple, basic action. These simple actions appear to have a large random com-
ponent. Despite this simplicity in individual behavior, social insects form a highly
structured social organism. To illustrate the complexity, and structured organization
of ant colonies, Marais [558] pointed out the resemblance between the human body
and a termite society.
Computational Intelligence: An Introduction, Second Edition A.P. Engelbrecht
c
2007 John Wiley & Sons, Ltd
359
360 17. Ant Algorithms
This chapter provides an introductory overview of ant algorithms. Section 17.1 con-
siders the foraging behavior of ants and discusses the first ant algorithms developed
on the basis of foraging models to solve discrete combinatorial optimization problems.
Models of the cemetery organization and brood care behaviors are discussed in Sec-
tion 17.2. The division of labor behavior is covered in Section 17.3. Some advanced
topics are presented in Section 17.4, including application of ACO in continuous en-
vironments, MOO, dynamic environments, and handling constraints. Applications of
ant algorithms (AA) are summarized in Section 17.5
17.1 Ant Colony Optimization Meta-Heuristic
One of the first behaviors studied by entomologists was the ability of ants to find
the shortest path between their nest and a food source. From these studies and
observations followed the first algorithmic models of the foraging behavior of ants, as
developed by Marco Dorigo [208]. Since then, research in the development of AAs
has gained momentum, resulting in a large number of algorithms and applications.
Collectively, algorithms that were developed as a result of studies of ant foraging
behavior are referred to as instances of the ant colony optimization meta-heuristic
(ACO-MH) [211, 215]. This section provides an overview of the ACO-MH, with a
focus on the basic principles of ACO algorithms, and the first algorithms that have
been developed. Section 17.1.1 gives an overview of the foraging behavior of real
ants, and introduces the concepts of stigmergy and artificial ants. A very simple ant
algorithm implementation is discussed in Section 17.1.3 to illustrate the basic principles
of AAs. Sections 17.1.4 to 17.1.11 respectively discuss the ant system (AS), ant colony
system (ACS), max-min ant system (MMAS), Ant-Q, fast ant system, Antabu, AS-
rank and ANTS instances of the ACO-MH. These algorithms were the first set of
ant algorithms implemented, mainly with reference to the traveling salesman problem
(TSP). Section 17.1.12 provides a discussion on the parameters of these algorithms.
17.1.1 Foraging Behavior of Ants
How do ants find the shortest path between their nest and food source, without any
visible, central, active coordination mechanisms? Studies of the foraging behavior
of several species of real ants revealed an initial random or chaotic activity pattern
in the search for food [216, 304, 628]. As soon as a food source is located, activity
patterns become more organized with more and more ants following the same path
to the food source. “Auto-magically”, soon all ants follow the same, shortest path.
This emergent behavior is a result of a recruitment mechanism whereby ants that have
located a food source influence other ants towards the food source. The recruitment
mechanism differs for different species, and can either be in the form of direct contact,
or indirect “communication.” Most ant species use the latter form of recruitment,
where communication is via pheromone trails. When an ant locates a food source,
it carries a food item to the nest and lays pheromone along the trail. Forager ants
decide which path to follow based on the pheromone concentrations on the different
17.1 Ant Colony Optimization Meta-Heuristic 361
Nest Food
Path B
Path A
Figure 17.1 Binary Bridge Experiment
paths. Paths with a larger pheromone concentration have a higher probability of
being selected. As more ants follow a specific trail, the desirability of that path is
reinforced by more pheromone being deposited by the foragers, which attracts more
ants to follow that path. The collective behavior that results is a form of autocatalytic
behavior,wherepositive feedback about a food path causes that path to be followed
by more and more ants [209, 216].
The indirect communication where ants modify their environment (by laying of
pheromones) to influence the behavior of other ants is referred to as stigmergy (refer
to Section 17.1.2.
The Bridge Experiments
Deneubourg et al. [199] studied the foraging behavior of the Argentine ant species
Iridomyrmex humilis in order to develop a formal model to describe its behavior. In
this laboratory experiment, as illustrated in Figure 17.1, the nest is separated from the
food source by a bridge with two equally long branches. Initially, both branches were
free of any pheromones. After a finite time period, one of the branches was selected,
with most of the ants following the path, even with both branches being of the same
length. The selection of one of the branches is due to random fluctuations in path
selection, causing higher concentrations on the one path.
From this experiment, referred to as the binary bridge experiment (and illustrated in
Figure 17.1), a simple formal model was developed to characterize the path selection
process [666]. For this purpose, it is assumed that ants deposit the same amount of
pheromone and that pheromone does not evaporate. Let n
A
(t)andn
B
(t)denotethe
number of ants on paths A and B respectively at time step t. Pasteels et al. [666]
found empirically that the probability of the next ant to choose path A at time step
t +1isgivenas,
P
A
(t +1)=
(c + n
A
(t))
α
(c + n
A
(t))
α
+(c + n
B
)
α
=1− P
B
(t + 1) (17.1)
where c quantifies the degree of attraction of an unexplored branch, and α is the bias
362 17. Ant Algorithms
FoodFood
NestNest
(b)(a)
Figure 17.2 Shortest Path Selection by Forager Ants
to using pheromone deposits in the decision process. The larger the value of α,the
higher the probability that the next ant will follow the path with a higher pheromone
concentration – even if that branch has only slightly more pheromone deposits. The
larger the value of c, the more pheromone deposits are required to make the choice of
path non-random. It was found empirically that α ≈ 2andc ≈ 20 provide a best fit
to the experimentally observed behavior.
Using the probability defined in equation (17.1), the decision rule of an ant that arrives
at the binary bridge is expressed as follows: if U(0, 1) ≤ P
A
(t + 1) then follow path A
otherwise follow path B.
Goss et al. [330] extended the binary bridge experiment, where one of the branches
of the bridge was longer than the other, as illustrated in Figure 17.2. Dots in this
figure indicate ants. Initially, paths are chosen randomly with approximately the
same number of ants following both paths (as illustrated in Figure 17.2(a)). Over
time, more and more ants follow the shorter path as illustrated in Figure 17.2(b).
Selection is biased towards the shortest path, since ants that follow the shortest path
return to the nest earlier than ants on the longer path. The pheromone on the shorter
path is therefore reinforced sooner than that on the longer path.
Goss et al. [330] found that the probability of selecting the shorter path increases with
the length ratio between the two paths. This has been referred to as the differential
path length effect by Dorigo et al. [210, 212].
To summarize the findings of the studies of real ants, the emergence of shortest path
selection behavior is explained by autocatalysis (positive feedback) and the differential
17.1 Ant Colony Optimization Meta-Heuristic 363
path length effect [210, 212].
Although an ant colony exhibits complex adaptive behavior, a single ant follows very
simple behaviors. An ant can be seen as a stimulus–response agent [629]: the ant
observes pheromone concentrations and produces an action based on the pheromone-
stimulus. An ant can therefore abstractly be considered as a simple computational
agent. An artificial ant algorithmically models this simple behavior of real ants. The
logic implemented is a simple production system with a set of production rules as
illustrated in Algorithm 17.1. This algorithm is executed at each point where the ant
needs to make a decision.
Algorithm 17.1 Artificial Ant Decision Process
Let r ∼ U(0, 1);
for each potential path A do
Calculate P
A
using, e.g., equation (17.1);
if r ≤ P
A
then
Follow path A;
Break;
end
end
While Algorithm 17.1 implements a simple random selection mechanism, any other
probabilistic selection mechanism (as overviewed in Section 8.5) can be used, for ex-
ample, roulette wheel selection.
17.1.2 Stigmergy and Artificial Pheromone
Generally stated, stigmergy is a class of mechanisms that mediate animal-to-animal
interactions [840]. The term stigmergy was formally defined by Grass´e [333] as a
form of indirect communication mediated by modifications of the environment. This
definition originated from observations of the nest-building behavior of the termite
species Bellicositermes natalensis and Cubitermes.Grass´e observed that coordination
and regulation of nest-building activities are not on an individual level, but achieved
by the current nest structure. The actions of individuals are triggered by the current
configuration of the nest structure. Similar observations have been made by Marais
[558], with respect to the Termes natalensis.
The word stigmergy is aptly constructed from the two Greek words [341],
• stigma, which means sign, and
• ergon, which means work.
Individuals observe signals, which trigger a specific response or action. The action
may reinforce or modify signals to influence the actions of other individuals.
Two forms of stigmergy have been defined [341, 871, 902]: sematectonic and sign-
based. Sematectonic stigmergy refers to communication via changes in the physical
364 17. Ant Algorithms
characteristics of the environment. Example activities that are accomplished through
sematectonic stigmergy include nest building, nest cleaning, and brood sorting (refer to
Section 17.2 considers algorithms based on sematectonic stigmergy). Sign-based stig-
mergy facilitates communication via a signaling mechanism, implemented via chemical
compounds deposited by ants. As an example, foraging behavior emerges from ants
following pheromone trails deposited by other ants.
Ant algorithms are population-based systems inspired by observations of real ant
colonies. Cooperation among individuals in an ant algorithm is achieved by exploiting
the stigmergic communication mechanisms observed in real ant colonies. Algorithmic
modeling of the behavior of ants is thus based on the concept of artificial stigmergy,
defined by Dorigo and Di Caro as the “indirect communication mediated by numeric
modifications of environmental states which are only locally accessible by the commu-
nicating agents” [211]. The essence of modeling ant behavior is to find a mathematical
that accurately describes the stigmergetic characteristics of the corresponding ant in-
dividuals. The main part of such a model is the definition of stigmergic variables which
encapsulate the information used by artificial ants to communicate indirectly. In the
contextof foraging behavior, artificial pheromone plays the role of stigmergic variable.
As discussed above, ants have the ability to always find the shortest path between their
nest and the food source. As ants move from a food source to the nest, an amount of
pheromone is dropped by each ant. Future ants choose paths probabilistically on on
the basis of the amount of pheromone. The higher the pheromone concentration, the
more the chance that the corresponding path will be selected. Some ant species have
the amount of pheromone deposited proportional to the quality of the food [210].
Over time, shorter paths will have stronger pheromone concentrations, since ants
return faster on those paths. Pheromone evaporates over time, with the consequence
that the pheromone concentrations on the longer paths decrease more quickly than on
the shorter paths.
Artificial pheromone mimics the characteristics of real pheromone, and indicates the
“popularity” of a solution to the optimization problem under consideration. In effect,
artificial pheromone encodes a long-term memory about the entire search process.
17.1.3 Simple Ant Colony Optimization
The first ant algorithm developed was the ant system (refer to Section 17.1.4)[208, 209],
and since then several improvements of the ant system have been devised [300, 301,
555, 743, 815]. These algorithms have somewhat more complex decision processes
than that illustrated in Algorithm 17.1. To provide a gentle, didactic introduction
to ant algorithms, this section breaks the chronological order in which ant algorithms
have been developed to first present the simple ACO (SACO) [212, 217]. The SACO
is an algorithmic implementation of the double bridge experiment of Deneubourg et
al. [199] (refer to Section 17.1.1), and is used in this section to illustrate the basic
components and behavior of the ACO-MH.
Consider the general problem of finding the shortest path between two nodes on a
17.1 Ant Colony Optimization Meta-Heuristic 365
1
23
4
5
67
DestinationSource
τ
45
τ
14
Figure 17.3 Graph for Shortest Path Problems
graph, G =(V,E), where V is the set of vertices (nodes) and E is a matrix representing
the connections between nodes. The graph has n
G
= |V | nodes. The length, L
k
,of
the path constructed by ant k is calculated as the number of hops in the path from the
origin to the destination node. An example graph and selected path are illustrated in
Figure 17.3. The length of the indicated route is 2. A pheromone concentration, τ
ij
,
is associated With each edge, (i, j), of the graph.
For the SACO, each edge is assigned a small random value to indicate the initial
pheromone, τ
ij
(0). Strictly speaking, edges do not have any pheromone concentrations
for the first step. An ant randomly selects which edge to follow next. Using the
simple decision logic summarized in Algorithm 17.1, implementation is made easier
by initializing the pheromone concentration on each link to a small random value. A
number of ants, k =1,...,n
k
, are placed on the source node. For each iteration of
SACO (refer to Algorithm 17.2), each ant incrementally constructs a path (solution) to
the destination node. At each node, each ant executes a decision policy to determine
the next link of the path. If ant k is currently located at node i, it selects the next
node j ∈N
k
i
, based on the transition probability [212, 217],
p
k
ij
(t)=
#
τ
α
ij
(t)
j∈N
k
i
τ
α
ij
(t)
if j ∈N
k
i
0ifj ∈N
k
i
(17.2)
where N
k
i
is the set of feasible nodes connected to node i, with respect to ant k.If,
for any node i and ant k, N
k
i
= ∅, then the predecessor to node i is included in N
k
i
.
Note that this may cause loops to occur within constructed paths. These loops are
removed once the destination node has been reached.
In the equation above, α is a positive constant used to amplify the influence of
pheromone concentrations. Large values of α give excessive importance to pheromone,
366 17. Ant Algorithms
especially the initial random pheromones, which may lead to rapid convergence to sub-
optimal paths.
Once all ants have constructed a complete path from the origin node to the destination
node, and all loops have been removed, each ant retraces its path to the source node
deterministically, and deposits a pheromone amount,
∆τ
k
ij
(t) ∝
1
L
k
(t)
(17.3)
to each link, (i, j), of the corresponding path; L
k
(t) is the length of the path con-
structed by ant k at time step t.
That is,
τ
ij
(t +1)=τ
ij
(t)+
n
k
k=1
∆τ
k
ij
(t) (17.4)
where n
k
is the number of ants.
Using equation (17.3), the total pheromone intensity of a link is proportional to the
desirability of the paths in which the link occurs, based on the length of the cor-
responding path. The deposited pheromone, ∆τ
k
ij
, calculated using equation (17.3),
expresses the quality of the corresponding solution. For SACO, the quality of a so-
lution (the constructed path) is simply expressed as the inverse of the length of the
path in terms of the number of hops in the path. Any other measure can be used, for
example the cost of traveling on the path, or the physical distance traveled. In general,
if x
k
(t) denotes a solution at time step t,thenf(x
k
(t)) expresses the quality of the
solution. If ∆τ
k
is not proportional to the quality of the solution and all ants deposit
the same amount of pheromone (i.e. ∆τ
1
ij
=∆τ
2
ij
= ... =∆τ
n
k
ij
), then it is only the
differential path length effect that biases path selection towards the shortest path –
very similar to the observations of Deneubourg et al. [199]. This discussion leads to
the two main forms of solution evaluation employed by ant algorithms, namely
• implicit evaluation, where ants exploit the differential path length effect to bias
the search of other agents, and
• explicit evaluation, where pheromone amounts are proportional to some quality
measure of constructed solutions.
If the amount of pheromone deposited is inversely proportional to the quality of the
solution (as is the case in equation (17.3)), then the larger f (x
k
(t)) (that is, the
worse the constructed solution), the smaller 1/f (x
k
(t)), hence the less the amount of
pheromone deposited on the link. Thus, a long path causes all the links of that path
to become less desirable as a component of the final solution. This is the case for any
quality measure, f , that needs to be minimized.
Any of a number of termination criteria can be used in Algorithm 17.2 (and for the
rest of the ant algorithms discussed later), for example,
• terminate when a maximum number of iterations, n
t
, has been exceeded;
• terminate when an acceptable solution has been found, with f(x
k
(t)) ≤ ;
17.1 Ant Colony Optimization Meta-Heuristic 367
Algorithm 17.2 Simple ACO Algorithm
Initialize τ
ij
(0) to small random values;
Let t =0;
Place n
k
ants on the origin node;
repeat
for each ant k =1,...,n
k
do
//Construct a path x
k
(t);
x
k
(t)=∅;
repeat
Select next node based on the probability defined in equation (17.2);
Add link (i, j)topathx
k
(t);
until destination node has been reached;
Remove all loops from x
k
(t);
Calculate the path length f(x
k
(t));
end
for each link (i, j) of the graph do
//pheromone evaporation;
Reduce the pheromone, τ
ij
(t), using equation (17.5);
end
for each ant k =1,...,n
k
do
for each link (i, j) of x
k
(t) do
∆τ
k
=
1
f(x
k
(t))
;
Update τ
ij
using equation (17.4);
end
end
t = t +1;
until stopping condition is true;
Return the path x
k
(t) with smallest f(x
k
(t)) as the solution;
• terminate when all ants (or most of the ants) follow the same path.
The initial experiments on the binary bridge problem [212] found that ants rapidly
converge to a solution, and that little time is spent exploring alternative paths. To force
ants to explore more, and to prevent premature convergence, pheromone intensities
on links are allowed to “evaporate” at each iteration of the algorithm before being
reinforced on the basis of the newly constructed paths. For each link, (i, j), let
τ
ij
(t) ← (1 − ρ)τ
ij
(t) (17.5)
with ρ ∈ [0, 1]. The constant, ρ, specifies the rate at which pheromones evaporate,
causing ants to “forget” previous decisions. In other words, ρ controls the influence of
search history. For large values of ρ, pheromone evaporates rapidly, while small values
of ρ result in slower evaporation rates. The more pheromones evaporate, the more
random the search becomes, facilitating better exploration. For ρ = 1, the search is
completely random.
At this point it is important to emphasize that solution construction is the result of