Engelbrecht Andries P. Computational Intelligence: An Introduction

Подождите немного. Документ загружается.

378 17. Ant Algorithms

The max-min approach was also applied to ACS, referred to as MMACS. In this

case, the larger the value of r

(refer to equation (17.17)), the tighter the pheromone

concentration limits have to be chosen. A lower τ

max

/τ

min

ratio has to be used

for larger r

to prevent ants from too often preferring links with high pheromone

concentrations.

Even though pheromone concentrations are clamped within a deﬁned range, stagna-

tion still occurred, although less than for AS. To address this problem, a pheromone

smoothing strategy is used to reduce the diﬀerences between high and low pheromone

concentrations. At the point of stagnation, all pheromone concentrations are increased

proportional to the diﬀerence with the maximum bound, i.e.

∆τ

(t) ∝ (τ

max

(t) − τ

(t)) (17.28)

Using this smoothing strategy, stronger pheromone concentrations are proportionally

less reinforced than weaker concentrations. This increases the chances of links with

low pheromone intensity to be selected as part of a path, and thereby increases the

exploration abilities of the algorithm.

Algorithm 17.5 summarizes MMAS, where the iteration-best path is used as default

to update pheromones and the global-best is used periodically at frequency f

17.1.7 Ant-Q

Gambardella and Dorigo [213, 300] developed a variant of ACS in which the local

update rule was inspired by Q-learning [891] (also refer to Chapter 6). In Ant-Q, the

pheromone notion is dropped to be replaced by Ant-Q value (or AQ-value). The goal

of Ant-Q is to learn AQ-values such that the discovery of good solutions is favored in

probability.

Let µ

(t) denote the AQ-value on the link between nodes i and j at time step t.Then

the transition rule (action choice rule) is given by (similarly to equation (17.17))

j =



arg max

u∈N

(t)

{µ

(t)η

(t)} if r ≤ r

J otherwise

(17.29)

The parameters α and β weigh the importance of the learned AQ-values, µ

,and

the heuristic information, η

. The AQ-values express how useful it is to move to

node j from the current node i. In equation (17.29), J is a random variable selected

according to a probability distribution given by a function of the AQ-values, µ

,and

the heuristic values η

Three diﬀerent rules have been proposed to select a value for the random variable, J:

• For the pseudo-random action choice rule, J is a node randomly selected from

the set N

(t) according to the uniform distribution.

17.1 Ant Colony Optimization Meta-Heuristic 379

• For the pseudo-random-proportional action choice rule, J ∈ V is selected accord-

ing to the distribution,

(t)=







(t)η

(t)



u∈N

(t)

(t)η

(t)

if j ∈N

(t)

0otherwise

(17.30)

• For the random-proportional action choice rule, r

= 0 in equation (17.29). The

next node is therefore always selected randomly based on the distribution given

by equation (17.30).

Gambardella and Dorigo show that the pseudo-random-proportional action choice rule

is best for Ant-Q (considering the traveling salesman problem (TSP)).

AQ-values are learned using the updating rule (very similar to that of Q-learning),

(t +1)=(1− ρ)µ

(t)+ρ



∆µ

(t)+γ max

u∈N

(t)

{µ

(t)}



(17.31)

where ρ is referred to as the discount factor (by analogy with pheromone evaporation)

and γ is the learning step size. Note that if γ = 0, then equation (17.31) reduces to

the global update equation of ACS (refer to equation (17.19)).

In Ant-Q, update equation (17.31) is applied for each ant k after each new node j has

been selected, but with ∆µ

(t) = 0. The eﬀect is that the AQ-value associated with

link (i, j) is reduced by a factor of (1 − ρ) each time that the link is selected to form

part of a candidate solution. At the same time the AQ-value is reinforced with an

amount proportional to the AQ-value of the best link, (j, u), leaving node j such that

the future desirability of link (j, u) is increased. The update according to equation

(17.31) can be seen as the local update rule, similar to equation (17.21) of ACS.

In addition to the above local update, a delayed reinforcement is used, similar to

the global update rule of ACS (refer to equation (17.19)). After all paths have been

constructed, one for each ant, AQ-values are updated using equation (17.31), where

∆µ

(t) is calculated using equation (17.20) with x

(t) either the global-best or the

iteration-best path. Gambardella and Dorigo found from their experimental results

(with respect to the TSP), that the iteration-best approach is less sensitive to changes

in parameter γ, and is faster in locating solutions of the same quality as the global-best

approach.

17.1.8 Fast Ant System

Taillard and Gambardella [831, 832] developed the fast ant system (FANT), speciﬁ-

cally to solve the quadratic assignment problem (QAP). The main diﬀerences between

FANT and the other ACO algorithms discussed so far are that (1) FANT uses only

one ant, and (2) a diﬀerent pheromone update rule is applied which does not make

use of any evaporation.

380 17. Ant Algorithms

The use of only one ant signiﬁcantly reduces the computational complexity. FANT

uses as transition rule equation (17.6), but with β = 0. No heuristic information is

used. The pheromone update rule is deﬁned as

(t +1)=τ

(t)+w

∆˜τ

(t)+w

∆ˆτ

(t) (17.32)

where w

and w

are parameters to determine the relative reinforcement provided

by the current solution at iteration t and the best solution found so far. The added

pheromones are calculated as

∆˜τ

(t)=



1if(i, j) ∈ ˜x(t)

0otherwise

(17.33)

and

∆ˆτ

(t)=



1if(i, j) ∈ ˆx(t)

0otherwise

(17.34)

where ˜x(t)andˆx(t) are respectively the best paths found in iteration t and the global-

best path found from the start of the search.

Pheromones are initialized to τ

(0) = 1. As soon as a new ˆx(t) is obtained, all

pheromones are reinitialized to τ

(0) = 1. This step exploits the search area around

the global best path, ˆx(t). If, at time step t, the same solution is found as the

current global best solution, the value of w

is increased by one. This step facilitates

exploration by decreasing the contribution, ∆ˆτ

(t), associated with the global best

path.

17.1.9 Antabu

Roux et al. [743, 744] and Kaji [433] adapted AS to include a local search using tabu

search (refer to Section A.5.2) to reﬁne solutions constructed by each iteration of AS.

In addition to using tabu search as local search procedure, the global update rule is

changed such that each ant’s pheromone deposit on each link of its constructed path

is proportional to the quality of the path. Each ant, k, updates pheromones using

(t +1)=(1− ρ)τ

(t)+



f(x

(t))



f(x

−

(t)) − f(x

(t))

f(ˆx(t))



(17.35)

where f(x

−

(t)) is the cost of the worst path found so far, f (ˆx(t)) is the cost of the

best path found so far, and f(x

(t)) is the cost of the path found by ant k. Equation

(17.35) is applied for each ant k for each link (i, j) ∈ x

(t).

17.1.10 AS-rank

Bullnheimer et al. [94] proposed a modiﬁcation of AS to: (1) allow only the best ant

to update pheromone concentrations on the links of the global-best path, (2) to use

17.1 Ant Colony Optimization Meta-Heuristic 381

elitist ants, and (3) to let ants update pheromone on the basis of a ranking of the ants.

For AS-rank, the global update rule changes to

(t +1)=(1− ρ)τ

(t)+n

∆ˆτ

(t)+∆τ

(t) (17.36)

where

∆ˆτ

(t)=

f(ˆx(t))

(17.37)

with ˆx(t) the best path constructed so far. If n

elite ants are used, and the n

ants

are sorted such that f(x

(t)) ≤ f(x

(t)) ≤ ...≤ f(x

(t)), then

∆τ

(t)=



σ=1

∆τ

(t) (17.38)

where

∆τ

(t)=

−σ)Q

f(x

(t))

if (i, j) ∈ x

(t)

0otherwise

(17.39)

with σ indicating the rank of the corresponding ant. This elitist strategy diﬀers from

that implemented in AS (refer to Section 17.1.4) in that the contribution of an elite

ant to pheromone concentrations is directly proportional to its performance ranking:

the better the ranking (i.e. small σ) the more the contribution.

17.1.11 ANTS

Approximated non-deterministic tree search (ANTS) was developed by Maniezzo and

Carbonaro [555, 556] as an extension of AS. ANTS diﬀers from AS in: (1) the transition

probability calculation, (2) the global update rule, and (3) the approach to avoid

stagnation.

ANTS uses the transition probability as deﬁned in equation (17.8). The set N

con-

tains all feasible moves from the current node i. Pheromone intensities are updated

after all ants have completed construction of their paths. Pheromones are updated

using equations (17.5) and (17.10), but with

∆τ

(t)=τ



1 −

f(x

(t)) − 

f(t) − 



(17.40)

where f(x

(t)) represents the cost of the corresponding path, x

(t), of ant k at iteration

t,and

f(t) is a moving average on the cost of the last ˆn

global-best solutions found

by the algorithm. If f(ˆx(t)) denotes the cost of the global-best solution at iteration t,

then

f(t)=





=t−ˆn

f(ˆx(t



))

ˆn

(17.41)

If t<ˆn

, the moving average is calculated over the available t best solutions. In

equation (17.40),  is a lower bound to the cost of the optimal solution.

382 17. Ant Algorithms

Algorithm 17.6 ANTS Algorithm

t =0;

Initialize parameters α, β, ρ, Q, n

,τ

, ˆn

,;

Place all ants, k =1,...,n

;

for each link (i, j) do

(t)=τ

;

end

ˆx(t)=∅;

f(ˆx(t)=0;

repeat

for each ant k =1,...,n

(t)=∅;

repeat

Select next node j with probability deﬁned in equation (17.8);

(t)=x

(t) ∪{(i, j)};

until full path has been constructed;

Compute f(x

(t));

end

x = x

(t):f(x

(t)) = min



=1,...,n

{f(x



(t))};

Compute f(x);

if f(x) <f(ˆx(t)) then

ˆx(t)=x;

f(ˆx(t)) = f(x);

end

ˆn

=min{t, ˆn

};

Calculate moving average,

f(t), using equation (17.41);

for each link (i, j) do

Apply global update using equations (17.5), (17.10) and (17.40);

end

for each link (i, j) do

(t +1)=τ

(t);

end

ˆx(t +1)=ˆx(t);

f(ˆx(t +1))=f (ˆx(t));

t = t +1;

until stopping condition is true;

Return ˆx(t) as the solution;

17.1 Ant Colony Optimization Meta-Heuristic 383

Table 17.1 General ACO Algorithm Parameters

Parameter Meaning Comment

Number of ants

Maximum number of iterations

Initial pheromone amount not for MMAS

ρ Pheromone persistence ρ

,ρ

for ACS

α Pheromone intensiﬁcation α =1forACS

β Heuristic intensiﬁcation not for SACO, ANTS

The calculation of the amount of pheromone, ∆τ

, deposited by each ant eﬀectively

avoids premature stagnation: pheromone concentrations are reduced if the cost of an

ant’s solution is lower than the moving average; otherwise, pheromone concentrations

are increased. The update mechanism makes it possible to discriminate small achieve-

ments in the ﬁnal iterations of the search algorithm, and avoids exploitation in the

early iterations.

ANTS is summarized in Algorithm 17.6.

17.1.12 Parameter Settings

Each of the algorithms discussed thus far uses a number of control parameters that

inﬂuence the performance of the algorithms (refer to Table 17.1). Here performance

refers to the quality of solutions found (if any is found) and the time to reach these

solutions.

The following parameters are common to most ACO algorithms:

• n

, the number of ants: From the ﬁrst studies of ACO algorithms, the inﬂuence

of the number of ants on performance has been studied [215, 216]. An obvious

inﬂuence of the number of ants relates to computational complexity. The more

ants used, the more paths have to be constructed, and the more pheromone

deposits calculated. As an example, the computational complexity of AS is

O(n

), where n

= n

is the total number of cycles, n

is the total

number of iterations, and n

is the number of nodes in the solutions (assuming

that all solutions have the same number of nodes).

The success of ACO algorithms is in the cooperative behavior of multiple ants.

Through the deposited pheromones, ants communicate their experience and

knowledge about the search space to other ants. The fewer ants used, the less

the exploration ability of the algorithm, and consequently the less information

about the search space is available to all ants. Small values of n

may then cause

sub-optimal solutions to be found, or early stagnation. Too many ants are not

necessarily beneﬁcial (as has been shown, for example, with SACO). With large

values of n

, it may take signiﬁcantly longer for pheromone intensities on good

links to increase to higher levels than they do on bad links.

384 17. Ant Algorithms

For solving the TSP, Dorigo et al. [216] found that n

≈ n

worked well. For

ACS, Dorigo and Gambardella [215] formally derived that the optimal number

of ants can be calculated using

log(φ

− 1) − log(φ

− 2)

log(1 − ρ

)

(17.42)

where φ

is the average pheromone concentration on the edges of the last best

path before the global update, and φ

after the global update. Unfortunately,

the optimal values of φ

and φ

are not known. Again for the TSP, empirical

analyses showed that ACS worked best when (φ

−1)/(φ

−1) ≈ 0.4, which gives

= 10 [215].

It is important to note that the above is for a speciﬁc algorithm, used to solve a

speciﬁc class of problems. The value of n

should rather be optimized for each

diﬀerent algorithm and problem.

• n

, maximum number of iterations: It is easy to see that n

plays an important

role in ensuring quality solutions. If n

is too small, ants may not have enough

time to explore and to settle on a single path. If n

is too large, unnecessary

computations may be done.

• τ

, initial pheromone: During the initialization step, all pheromones are either

initialized to a constant value, τ

(for MMAS, τ

= τ

max

), or to random values in

the range [0,τ

]. In the case of random values, τ

is selected to be a small positive

value. If a large value is selected for τ

, and random values are selected from

the uniform distribution, then pheromone concentrations may diﬀer signiﬁcantly.

This may cause a bias towards the links with large initial concentrations, with

links that have small pheromone values being neglected as components of the

ﬁnal solution.

There is no easy answer to the very important question of how to select the best values

for the control parameters. While many empirical studies have investigated these

parameters, suggested values and heuristics to calculate values should be considered

with care. These are given for speciﬁc algorithms and speciﬁc problems, and should

not be accepted in general. To maximize the eﬃciency of any of the algorithms, the

values of the relevant control parameters have to be optimized for the speciﬁc problem

being solved. This can be done through elaborate empirical analyses. Alternatively,

an additional algorithm can be used to “learn” the best values of the parameters for

the given algorithm and problem [4, 80].

17.2 Cemetery Organization and Brood Care

Many ant species, for example Lasius niger and Pheidole pallidula, exhibit the behavior

of clustering corpses to form cemeteries [127] (cited in [77]). Each ant seems to behave

individually, moving randomly in space while picking up or depositing (dropping)

corpses. The decision to pick up or drop a corpse is based on local information of

the ant’s current position. This very simple behavior of individual ants results in the

17.2 Cemetery Organization and Brood Care 385

emergence of a more complex behavior of cluster formation. It was further observed

that cemeteries are sited around spatial heterogeneities [77, 563].

A similar behavior is observed in many ant species, such as Leptothorax unifasciatus,

in the way that the colony cares for the brood [77, 912, 913]. Larvae are sorted in such

a way that diﬀerent brood stages are arranged in concentric rings. Smaller larvae are

located in the center, with larger larvae on the periphery. The concentric clusters are

organized in such a way that small larvae receive little individual space, while large

larvae receive more space.

While these behaviors are still not fully understood, a number of studies have resulted

in mathematical models to simulate the clustering and sorting behaviors. Based on

these simulations, algorithms have been implemented to cluster data, to draw graphs,

and to develop robot swarms with the ability to sort objects. This section discusses

these mathematical models and algorithms. Section 17.2.1 discusses the basic ant

colony clustering (ACC) model, and a generalization of this model is given in Sec-

tion 17.2.2. A minimal ACC approach is summarized in Section 17.2.3.

17.2.1 Basic Ant Colony Clustering Model

The ﬁrst algorithmic implementations that simulate cemetery formation were inspired

by the studies of Chr´etien of the ants Lasius niger [127]. Based on physical experi-

ments, Chr´etien derived the probability of an ant dropping a corpse next to an n-cluster

as being proportional to 1 − (1 − p)

for n ≤ 30, where p is a ﬁtting parameter [78].

Ants cannot, however, precisely determine the size of clusters. Instead, the size of

clusters is determined by the eﬀort to transport the corpse (the corpse may catch on

other items, making the walk more diﬃcult). It is likely that the corpse is deposited

when the eﬀort becomes too great.

On the basis of of Chr´etien’s observations, Deneubourg et al. [200] developed a model

to describe the simple behavior of ants. The main idea is that items in less dense areas

should be picked up and dropped at a diﬀerent location where more of the same type

exist. The resulting model is referred to as the basic model.

Assuming only one type of item, all items are randomly distributed on a two-

dimensional grid, or lattice. Each grid-point contains only one item. Ants are placed

randomly on the lattice, and move in random directions one cell at a time. After each

move, an unladen ant decides to pick up an item (if the corresponding cell has an

item) based on the probability



+ λ



(17.43)

where λ is the fraction of items the ant perceives in its neighborhood, and γ

> 0.

When there are only a few items in the ant’s neighborhood, that is λ<<γ

,thenP

approaches 1; hence, objects have a high probability of being picked up. On the other

hand, if the ant observes many objects, that is λ>>γ

, P

approaches 0, and the

probability that the ant will pick up an object is small.

386 17. Ant Algorithms

Each loaded ant has a probability of dropping the carried object, given by



+ λ



(17.44)

provided that the corresponding cell is empty; γ

> 0. If a large number of items is

observed in the neighborhood, i.e. λ>>γ

,thenP

approaches 1, and the probability

of dropping the item is high. If λ<<γ

,thenP

approaches 0.

The fraction of items, λ, is calculated by making use of a short-term memory for each

ant. Each ant keeps track of the last T time steps, and λ is simply the number of

items observed during these T time steps, divided by the largest number of items that

can be observed during the last T time steps. If only one item can be observed during

each time step, λ = n

/T ,wheren

is the number of encountered items.

The basic model is easily expanded to more than one type of item. Let A and B

denote two types of items. Then equations (17.43) and (17.44) are used as is, but with

λ replaced by λ

or λ

depending on the type of item encountered.

17.2.2 Generalized Ant Colony Clustering Model

Lumer and Faieta [540] generalized the basic model of Deneubourg et al. (refer to

Section 17.2.1) to cluster data vectors with real-valued elements for exploratory data

analysis applications. This section presents the original Lumer–Faieta algorithm and

discusses extensions and modiﬁcations to improve the quality of solutions and to speed

up the clustering process.

Lumer--Faieta Algorithm

The ﬁrst problem to solve, in applying the basic model to real-valued vectors, is to

deﬁne a distance, or dissimilarity, d(y

, y

), between data vectors y

and y

,using

any applicable norm. For real-valued vectors, the Euclidean distance between the two

vectors has been used most frequently to quantify dissimilarity. The next problem

is to determine how these dissimilarity measures should be used to group together

similar data vectors, in such a way that

• intra-cluster distances are minimized; that is, the distances between data vectors

within a cluster should be small to form a compact, condensed cluster.

• inter-cluster distances are maximized; that is, the diﬀerent clusters should be

well separated.

As for the basic model, data vectors are placed randomly on a two-dimensional grid.

Ants move randomly around on the grid, while observing the surrounding area of n

sites, referred to as the n

-patch. The surrounding area is simply a square neighbor-

hood, N

×n

(i), of the n

× n

sites surrounding the current position, i,ofthe

ant. Assume that an ant is on site i at time t, and ﬁnds data vector y

. The “local”

17.2 Cemetery Organization and Brood Care 387

density, λ(y

), of data vector y

within the ant’s neighborhood is then given as

λ(y

)=max









∈N

×n

(i)



1 −

d(y

, y

)









(17.45)

where γ>0 deﬁnes the scale of dissimilarity between items y

and y

. The constant

γ determines when two items should, or should not be located next to each other. If

γ is too large, it results in the fusion of individual clusters, clustering items together

that do not belong together. If γ is too small, many small clusters are formed. Items

that belong together are not clustered together. It is thus clear that γ has a direct

inﬂuence on the number of clusters formed. The dissimilarity constant also has an

inﬂuence on the speed of the clustering process. The larger γ, the faster the process

is.

Using the measure of similarity, λ(y

), the picking up and dropping probabilities are

deﬁned as [540]



+ λ(y

)



(17.46)



2λ(y

)ifλ(y

) <γ

1ifλ(y

) ≥ γ

(17.47)

A summary of the Lumer–Faieta ant colony clustering algorithm is given in Algo-

rithm 17.7.

The following aspects of Algorithm 17.7 need clariﬁcation:

• n

is the maximum number of iterations.

• The grid size: There should be more sites than data vectors, since items are

not stacked. Each site may contain only one item. If the number of sites is

approximately the same as the number of items, there are not enough free cells

available for ants to move to. Large clusters are formed with a high classiﬁcation

error. On the other hand, if there are many more sites than items, many small

clusters may be formed. Also, clustering takes long due to the large distances

that items need to be transported.

• The number of ants: There should be fewer ants than data vectors. If there

are too many ants, it may happen that most of the items are carried by ants.

Consequently, density calculation results in close to zero values of λ(y

). Drop-

ping probabilities are then small, and most ants keep carrying their load without

depositing it. Clusters may never be formed. On the other hand, if there are

too few ants, it takes longer to form clusters.

• Local density: Consider that an ant carries item y

.Ifthen

neighboring

sites have items similar to y

, λ(y

) ≈ 1. Item y

is then dropped with high

probability (assuming that the site is empty). On the other hand, if the items

are very dissimilar from y

, λ(y

) ≈ 0, and the item has a very low probability

of being dropped. In the case of an unladen ant, the pick-up probability is large.