Engelbrecht Andries P. Computational Intelligence: An Introduction
Подождите немного. Документ загружается.
388 17. Ant Algorithms
Algorithm 17.7 Lumer–Faieta Ant Colony Clustering Algorithm
Place each data vector y
a
randomly on a grid;
Place n
k
ants on randomly selected sites;
Initialize values of γ
1
,γ
2
,γ and n
t
;
for t =1to n
t
do
for each ant, k =1, ···,n
k
do
if ant k is unladen and the site is occupied by item y
a
then
Compute λ(y
a
) using equation (17.45);
Compute P
p
(y
a
) using equation (17.46);
if U(0, 1) ≤ P
p
(y
a
) then
Pick up item y
a
;
end
end
else
if ant k carries item y
a
and site is empty then
Compute λ(y
a
) using equation (17.45);
Compute P
d
(y
a
) using equation (17.47);
if U(0, 1) ≤ P
d
(y
a
) then
Drop item y
a
;
end
end
end
Move to a randomly selected neighboring site not occupied by another ant;
end
end
• Patch size, n
N
: A larger patch size allows an ant to use more information
to make its decision. Better estimates of local densities are obtained, which
generally improve the quality of clusters. However, a larger patch size is com-
putationally more expensive and inhibits quick formation of clusters during the
early iterations. Smaller sizes reduce computational effort, and less information
is used. This may lead to many small clusters.
Modifications to Lumer--Faieta Algorithm
The algorithm developed by Lumer and Faieta [540] showed success in a number of
applications. The algorithm does, however, have the tendency to create more clusters
than necessary. A number of modifications have been made to address this problem,
and to speed up the search:
• Different Moving Speeds: Ants are allowed to move at different speeds [540].
Fast-moving ants form coarser clusters by being less selective in their estimation
of the average similarity of a data vector to its neighbors. Slower agents are
more accurate in refining the cluster boundaries. Different moving speeds are
17.2 Cemetery Organization and Brood Care 389
easily modeled using
λ(y
a
)=max
0,
1
n
2
N
y
b
∈N
n
N
×n
N
(i)
1 −
d(y
a
, y
b
)
γ(1 −
v−1
v
max
)
(17.48)
where v ∼ U(1,v
max
), and v
max
is the maximum moving speed.
• Short-Term Memory: Each ant may have a short-term memory, which
allows the ant to remember a limited number of previously carried items and
the position where these items have been dropped [540, 601]. If the ant picks
up another item, the position of the best matching memorized data item biases
the direction of the agent’s random walk. This approach helps to group together
similar data items.
Handl et al. [344] changed the short-term memory strategy based on the ob-
servation that items stored in the memory of one ant may have been moved by
some other ant, and is no longer located at the memorized position. For each
memorized position, y
a
, the ant calculates the local density, λ(y
a
). The ant
probabilistically moves to that memorized position with highest local density. If
the ant does not make the move, its memory is cleared and the dropping decision
is based on the standard unbiased dropping probabilities.
• Behavioral Switches: Ants are not allowed to start destroying clusters if they
have not performed an action for a number of time steps. This strategy allows
the algorithm to escape from local optima.
• Distance/Dissimilarity Measures:
For floating-point vectors, the Euclidean distance
d
E
(y
a
, y
b
)=
n
y
l=1
(y
al
− y
bl
)
2
(17.49)
is the most frequently used distance measure. As an alternative, Yang and Kamel
[931] uses the cosine similarity function,
d
C
(y
a
, y
b
)=1− sim(y
a
, y
b
) (17.50)
where
sim(y
a
, y
b
)=
n
y
l=1
y
al
y
bl
n
y
l=1
y
2
al
n
y
l=1
y
2
bl
(17.51)
The cosine function, sim(y
a
, y
b
), computes the angle between the two vectors,
y
a
and y
b
.Asy
a
and y
b
become more similar, sim(y
a
, y
b
) approaches 1.0, and
d
C
(y
a
, y
b
) becomes 0.
• Pick-up and Dropping Probabilities: Pick-up and dropping probabilities
different from equation (17.46) and (17.47) have been formulated specifically in
attempts to speed up the clustering process:
390 17. Ant Algorithms
– Yang and Kamel [931] use a continuous, bounded, monotic increasing func-
tion to calculate the pick-up probability as
P
p
=1−f
s
(λ(y
a
)) (17.52)
and the dropping probability as
P
d
= f
s
(λ(y
a
)) (17.53)
where f
s
is the sigmoid function.
– Wu and Shi [919] defines the pick-up probability as
P
p
=
1ifλ(y
a
) ≤ 0
1 − γ
1
λ(y
a
)if0<λ(y
a
) ≤ 1/γ
1
0ifλ(y
a
) > 1/γ
1
(17.54)
and the dropping probability as
P
d
=
1ifλ(y
a
) ≥ 1/γ
2
γ
2
λ(y
a
)if0<λ(y
a
) < 1/γ
2
0ifλ(y
a
) ≤ 0
(17.55)
with γ
1
,γ
2
> 0.
– Handl et al. [344] used the probabilities
P
p
=
1ifλ(y
a
) ≤ 1
1
λ(y
a
)
2
otherwise
(17.56)
P
d
=
1ifλ(y
a
) > 1
λ(y
a
)
4
otherwise
(17.57)
The above probabilities use a different local density calculation, where an addi-
tional constraint is added:
λ(y
a
)=
#
max{0,
1
n
2
N
y
b
∈N
n
N
×n
N
(i)
(1 −
d(y
a
y
b
)
γ
)} if ∀y
b
, (1 −
d(y
a
,y
b
)
γ
) > 0
0 otherwise
(17.58)
• Heterogeneous Ants: The Lumer–Faieta clustering algorithm uses homo-
geneous ants. That is, all ants have the same behavior as governed by static
control parameters, n
N
and γ. Using static control parameters introduces the
problem of finding optimal values for these parameters. Since the best values for
these parameters depend on the data set being clustered, the parameters should
be optimized for each new data set. Heterogeneous ants address this problem by
having different values for the control parameters for each ant. Monmarch´e et al.
[601] randomly selected a value for each control parameter for each ant within
defined ranges. New values can be selected for each iteration of the algorithm
or can remain static.
Handl et al. [344] used heterogeneous ants with dynamically changing values for
n
N
and γ. Ants start with small values of n
N
, which gradually increase over
time. This approach saves on computational effort during the first iterations
17.3 Division of Labor 391
and prevents difficulties with initial cluster formation. Over time n
N
increases to
prevent a large number of small clusters form forming. The similarity coefficient,
γ, is dynamically adjusted for each ant on the basis of the ant’s activity. Activity
is reflected by the frequency of successful pick-ups and drops of items. Initially,
γ
k
(0) ∼ U(0, 1) for each ant k. Then, after each iteration,
γ
k
(t +1)=
γ
k
(t)+0.01 if
n
k
f
(t)
n
f
> 0.99
γ
k
(t) − 0.01 if
n
k
f
(t)
n
f
≤ 0.99
(17.59)
where n
k
f
(t) is the number of failed dropping actions of ant k at time step t and
n
f
> 0.
17.2.3 Minimal Model for Ant Clustering
As mentioned in Section 17.2.1, real ants cluster corpses around heterogeneities. The
basic model proposed by Deneubourg et al. [199] (refer to Section 17.2.1) does not
exhibit the same behavior. Martin et al. [563] proposed a minimal model to simulate
cemetery formation where clusters are formed around heterogeneities. In this minimal
model, no pick-up or dropping probabilities are used. Also, ants do not have memories.
The dynamics of the minimal model consist of alternating two rules:
• The pick-up and dropping rule: Whenever an unladen ant observes a corpse
(data item) in one or more of its neighboring sites, a corpse is picked up with
probability one. If more than one corpse is found, one corpse is randomly se-
lected. After moving at least one step away, the corpse is dropped but only if the
ant is surrounded by at least one other corpse. The carried corpse is dropped in
a randomly selected empty site.
Ants do not walk over corpses, and can therefore potentially get trapped.
• Random walk rule: Ants move one site at a time, but always in the same
direction for a pre-assigned random number of steps. When all these steps have
been made, a new random direction is selected, as well as the number of steps.
If a corpse is encountered on the ant’s path, and that corpse is not picked up,
then a new direction is randomly selected.
Martin et al. [563] showed that this very simple model provides a more accurate
simulation of corpse clustering by real ants.
17.3 Division of Labor
The ecological success of social insects has been attributed to work efficiency achieved
by division of labor among the workers of a colony, whereby each worker specializes
in a subset of the required tasks [625]. Division of labor occurs in biological systems
when all the individuals of that system (colony) are co-adapted through divergent
392 17. Ant Algorithms
specialization, in such a way that there is a fitness gain as a consequence of such
specialization [774].
Division of labor has been observed in a number of eusocial insects [774, 850], including
ants [328, 348, 558, 693, 882], wasps [298, 624], and the honey bee [393, 625, 733]. Here
eusociality refers to the presence of [214]:
• cooperation in caring for the young,
• reproductive division of labor, with more or less sterile individuals working on
behalf of those individuals involved with reproduction, and
• overlap of generations.
Within these insect colonies, a number of tasks are done, including reproduction,
caring for the young, foraging, cemetery organization, waste disposal, and defense.
Task allocation and coordination occurs mostly without any central control, especially
for large colonies. Instead, individuals respond to simple local cues, for example
the pattern of interactions with other individuals [328], or chemical signals. Also
very interesting, is that task allocation is dynamic, based on external and internal
factors. Even though certain groups of individuals may specialize in certain tasks,
task switching occurs when environmental conditions demand such switches. This
section provides an overview of the division of labor in insect colonies. Section 17.3
gives a summary of different types of division of labor, and gives an overview of a
few mechanisms that facilitate task allocation and coordination. A simple model of
division of labor based on response thresholds is discussed in Section 17.3.2. This
model is generalized in Section 17.3.3 to dynamic task allocation and specialization.
17.3.1 Division of Labor in Insect Colonies
Social insects are characterized by one fundamental type of division of labor i.e. re-
productive division of labor [216, 882]. Reproduction is carried out by a very small
fraction of individuals, usually by one queen. In addition to this primary division of
labor into reproductive and worker castes, a further division of labor exists among the
workers. Worker division of labor can occur in the following forms [77]:
• Temporal polyethism, also referred to as the age subcaste [77, 216, 393, 625].
With temporal polyethism, individuals of the same age tend to perform the
same tasks, and form an age caste. Evidence suggests that social interaction is a
mechanism by which workers assess their relative ages [625]. As an example, in
honey bee colonies, younger bees tend to the hive while older bees forage [393].
Temporal polyethism is more prominent in honey bees and eusocial wasps [625].
• Worker polymorphism, where workers have different morphologies [77, 558,
882]. Workers of the same morphological structure belong to the same morpho-
logical caste, and tend to perform the same tasks. For example, minor ants care
for the brood, while major ants forage [77]. As another example, the termite
species Termes natalensis has soldier ants that differ significantly in morpho-
logical structure from the worker termites [558]. Morphological castes are more
prominent in ant and termite species [625].
17.3 Division of Labor 393
• Individual variability : Even for individuals in an age or morphological caste,
differences may occur among individuals in the frequency and sequence of task
performance. Groups of individuals in the same caste that perform the same set
of tasks in a given period are referred to as behavioral ants.
A very important aspect of division of labor is its plasticity. Ratios of workers that
perform different tasks that maintain the colony’s viability and reproductive success
may vary over time. That is, workers may switch tasks. It can even happen that
major ants switch over to perform tasks of minor ants. Variations in these ratios are
caused by internal perturbations or external environmental conditions, e.g. climatic
conditions, food availability, and predation. Eugene N. Marais reports in [558] one of
the earliest observations of task switching. Very important to the survival of certain
termite species is the maintenance of underground fungi gardens. During a drought,
termites are forced to transport water over very large distances to feed the gardens.
During such times, all worker termites, including the soldiers have been observed to
perform the task of water transportation. Not even in the case of intentional harm
to the nest structure do the ants deviate from the water transportation task. In
less disastrous conditions, soldiers will immediately appear on the periphery of any
“wounds” in the nest structure, while worker ants repair the structure.
Without a central coordinator, the question is: how are tasks allocated and coor-
dinated, and how is it determined which individuals should switch tasks? While it
is widely accepted that environmental conditions, or local cues, play this role, this
behavior is still not well understood. Observations of specific species have produced
some answers, for example:
• In honey bees, juvenile hormone is involved in the task coordination [393]. It
was found that young and older bees have different levels of juvenile hormone:
juvenile hormone blood titers typically increases with age. It is low in young
bees that work in the hive, and high for foragers. Huang and Robinson observed
drops in juvenile hormone when foragers switch to hive-related tasks [393].
• Gordon and Mehdiabadi [328] found for the red harvester ant, Pogonomyrmex
barbatus, that task switches are based on recent history of brief antennal con-
tacts between ants. They found that the time an ant spent performing midden
work was positively correlated with the number of midden workers that the ant
encountered while being away from the midden. It is also the case that ants busy
with a different task are more likely to begin midden work when their encounters
with midden workers exceed a threshold.
• Termite species maintain waste heaps, containing waste transported from fungi
gardens [348]. Here division of labor is enforced by aggressive behavior directed
towards workers contaminated with garbage. This behavior ensures that garbage
workers rarely leave the waste disposal areas.
17.3.2 Task Allocation Based on Response Thresholds
Th´eraulaz et al. [841] developed a simple task allocation model based on the notion
of response threshold [77, 216, 733]. Response thresholds refer to the likelihood of
394 17. Ant Algorithms
reacting to task-associated stimuli. Individuals with a low threshold perform a task
at a lower level of stimulus than individuals with high thresholds. Individuals be-
come engaged in a specific task when the level of task-associated stimuli exceeds their
thresholds. If a task is not performed by individuals, the intensity of the corresponding
stimulus increases. On the other hand, intensity decreases as more ants perform the
task. Here, the task-associated stimuli serve as stigmergic variable.
This section reviews a model of response thresholds observed in ants and bees.
Single Task Allocation
Let s
j
be the intensity of task-j-associated stimuli. The intensity can be a measure
of the number of encounters, or a chemical concentration. A response threshold, θ
kj
,
determines the tendency of individual k to respond to the stimulus, s
j
, associated with
task j. For a fixed threshold model, individual k engages in task j with probability
[77, 216, 841],
P
θ
kj
(s
j
)=
s
ω
j
s
ω
j
+ θ
ω
kj
(17.60)
where ω>1 determines the steepness of the threshold. Usually, ω =2. Fors
j
<< θ
kj
,
P
θ
kj
(s
j
) is close to zero, and the probability of performing task j is very small. For
s
j
>> θ
kj
, the probability of performing task j is close to one. An alternative threshold
response function is [77]
P
θ
kj
(s
j
)=1− e
−s
j
/θ
kj
(17.61)
Assume that there is only one task (the task subscript is therefore dropped in what
follows). Also assume only two castes. If ϑ
k
denotes the state of an individual, then
ϑ
k
= 0 indicates that ant k is inactive, while ϑ
k
= 1 indicates that the ant is performing
the task. Then,
P (ϑ
k
=0→ ϑ
k
=1)=
s
2
s
2
+ θ
2
k
(17.62)
is the probability that an inactive ant will become active.
An active ant, busy with the task, becomes inactive with probability P
k
= p per time
unit, i.e.
P (ϑ
k
=1→ ϑ
k
=0)=p (17.63)
Therefore, an active ant spends an average 1/p time performing the task. An individual
may become engaged in the task again, immediately after releasing the task. Stimulus
intensity changes over time due to increase in demand and task performance. If σ is
the increase in demand, γ is the decrease associated with one ant performing the task,
and n
act
is the number of active ants, then
s(t +1)=s(t)+σ − γn
act
(17.64)
The more ants engaged in the task, the smaller the intensity, s, becomes, and con-
sequently, the smaller the probability that an inactive ant will take up the task. On
17.3 Division of Labor 395
the other hand, if all ants are inactive, or if there are not enough ants busy with the
task (i.e. σ>γn
act
), the probability increases that inactive ants will participate in
the task.
Allocation of Multiple Tasks
Let there be n
j
tasks, and let n
kj
be the number of workers of caste k performing
task j. Each individual has a vector of thresholds, θ
k
,whereeachθ
kj
is the threshold
allocated to the stimulus of task j.After1/p time units of performing task j, the ant
stops with this task, and selects another task on the basis of the probability defined
in equation (17.60). It may be the case that the same task is again selected.
17.3.3 Adaptive Task Allocation and Specialization
The fixed response threshold model discussed in Section 17.3.2 has a number of limi-
tations [77, 216, 841]:
• It cannot account for temporal polyethism, since it assumes that individuals are
differentiated and are given pre-assigned roles.
• It cannot account for task specialization within castes.
• It is only valid over small time scales where thresholds can be considered con-
stant.
These limitations are addressed by allowing thresholds to vary over time [77, 841].
Thresholds are adapted using a simple reinforcement mechanism. A threshold de-
creases when the corresponding task is performed, and increases when the task is
not performed. Let ξ and φ respectively represent the learning coefficient and the
forgetting coefficient. Then, if ant k performs task j in the next time unit, then
θ
kj
(t +1)=θ
kj
(t) − ξ (17.65)
If ant k does not perform task j,then
θ
kj
(t +1)=θ
kj
(t)+φ (17.66)
If t
kj
is the fraction of time that ant k spent on task j,thenitspent1− t
kj
time on
other tasks. The change in threshold value is then given by
θ
kj
(t +1)=θ
kj
(t) − t
kj
ξ +(1− t
kj
)φ (17.67)
The decision to perform task j is based on the response threshold function (refer to
equation (17.60)).
The more ant k performs task j, the smaller θ
kj
becomes (obviously, θ
kj
is bounded in
the range [θ
min
,θ
max
]). If demand s
j
is high, and remains high, the probability P
θ
kj
is high. This means that ant k will have an increased probability of choosing task j.
396 17. Ant Algorithms
However, if too many ants perform task j, s
j
also decreases by the factor γn
act
.In
this case the probability increases that ants will switch tasks, and start to specialize
in a new task.
17.4 Advanced Topics
This section shows how AAs can be used to optimize functions defined over continuous
spaces, and to solve MOPs as well as dynamically changing problems.
17.4.1 Continuous Ant Colony Optimization
Ant colony optimization algorithms were originally developed to solve discrete op-
timization problems, where the values assigned to variables of the solution are con-
strained by a fixed finite set of discrete values. In order to apply ant colony algorithms
to solve continuous optimization problems, the main problem is to determine a way
to map the continuous space problem to a graph search problem. A simple solution to
this problem is to encode floating-point variables using binary string representations
[523]. If a floating-point variable is encoded using an n bit-string, the graph represen-
tation G =(V, E), contains 2n nodes – two nodes per bit (one for each possible value,
i.e. 0 and 1). A link exists between each pair of nodes. Based on this representation,
the discrete ACO algorithms can be used to solve the problem. It is, however, the
case that binary representation of floating-point values loses precision. This section
discusses an ACO algorithm for optimizing continuous spaces without discretizing the
solution variables.
The first ACO algorithm for continuous function optimization was developed by
Bilchev and Parmee [67, 68]. This approach focused on local optimization. Wodrich
and Bilchev [915] extended the local search algorithm to a global search algorithm,
which was further improved by Jayaraman et al. [414], Mathur et al. [564] and Rajesh
et al. [701]. This global search algorithm, referred to as continuous ACO (CACO), is
described next.
The CACO algorithm performs a bi-level search, with a local search component to
exploit good regions of the search space, and a global search component to explore
bad regions. With reference to Algorithm 17.8, the search is performed by n
k
ants, of
which n
l
ants perform local searches and n
g
ants perform global searches. The first
step of the algorithm is to create n
r
regions. Each region represents a point in the
continuous search space. If x
i
denotes the i-th region, then x
ij
∼ U(x
min,j
,x
max,j
)
for each dimension j =1,...,n
x
and each region i =1,...,n
r
; x
min,j
and x
max,j
are
respectively the minimum and maximum values of the domain in the j-th dimension.
After initialization of the n
r
regions, the fitness of each region is evaluated, where the
fitness function is simply the continuous function being optimized. Let f(x
i
) denote
the fitness of region x
i
. The pheromone, τ
i
, for each region is initialized to one.
The global search identifies the n
g
weakest regions, and uses these regions to find n
g
17.4 Advanced Topics 397
Algorithm 17.8 Continuous Ant Colony Optimization Algorithm
Create n
r
regions;
τ
i
(0) = 1,i=1,...,n
r
;
repeat
Evaluate fitness, f(x
i
), of each region;
Sort regions in descending order of fitness;
Send 90% of n
g
global ants for crossover and mutation;
Send 10% of n
g
global ants for trail diffusion;
Update pheromone and age of n
g
weak regions;
Send n
l
ants to probabilistically chosen good regions;
for each local ant do
if region with improved fitness is found then
Move ant to better region;
Update pheromone;
end
else
Increase age of region;
Choose new random direction;
end
Evaporate all pheromone;
end
until stopping condition is true;
Return region x
i
with best fitness as solution;
new regions to explore. Most of the global ants perform crossover to produce new
regions, with a few ants being involved in trail diffusion. For the crossover operation,
for each variable x
ij
of the offspring, choose a random weak region x
i
and let x
ij
= x
ij
,
with probability P
c
(referred to as the crossover probability). After the crossover step,
the offspring x
i
is mutated by adding Gaussian noise to each variable x
ij
:
x
ij
← x
ij
+ N(0,σ
2
) (17.68)
where the mutation step size, σ, is reduced at each time step:
σ ← σ
max
(1 − r
(1−t/n
t
)
γ
1
) (17.69)
where r ∼ U(0, 1), σ
max
is the maximum step size, t is the current time step, n
t
is
the maximum number of iterations, and γ
1
controls the degree of nonlinearity. The
nonlinear reduction in mutation steps limits exploration in later iterations to allow for
better exploitation.
Trail diffusion implements a form of arithmetic crossover. Two weak regions are ran-
domly selected as parents. For parents x
i
and x
l
, the offspring x
is calculated as
x
j
= γ
2
x
ij
+(1− γ
2
)x
lj
(17.70)
where γ
2
∼ U(0, 1).