Engelbrecht Andries P. Computational Intelligence: An Introduction

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

368 17. Ant Algorithms

cooperative behavior that emerges from the simple behaviors of individual ants: each

ant chooses the next link of its path based on information provided by other ants,

in the form of pheromone deposits. This again refers to the autocatalytic behavior

exhibited by forager ants. It is also important to note that the information used to

aid in the decision making process is limited to the local environment of the ant.

In their experiments, Dorigo and Di Caro found that [212, 217]

• SACO works well for very simple graphs, with the shortest path being selected

most often;

• for larger graphs, performance deteriorates with the algorithm becoming less

stable and more sensitive to parameter choices;

• convergence to the shortest path is good for a small number of ants, while too

many ants cause non-convergent behavior;

• evaporation becomes more important for more complex graphs. If ρ = 0, i.e.

no evaporation, the algorithm does not converge. If pheromone evaporates too

much (a large ρ is used), the algorithm often converged to sub-optimal solutions

for complex problems;

• for smaller α, the algorithm generally converges to the shortest path. For com-

plex problems, large values of α result in worse convergence behavior.

From these studies of the simple ACO algorithm, the importance of the exploration–

exploitation trade-oﬀ becomes evident. Care should be taken to employ mechanisms

to ensure that ants do not exploit pheromone concentrations such that the algorithm

prematurely stagnates on sub-optimal solutions, but that ants are forced to explore

alternative paths. In the sections (and chapters) that follow, diﬀerent mechanisms are

discussed to balance exploitation and exploration.

The simple ACO algorithm discussed in the previous section has shown some success

in ﬁnding the shortest paths in graphs. The performance of the algorithm can be im-

proved signiﬁcantly by very simple changes to Algorithm 17.2. These changes include

addition of heuristic information to determine the probability of selecting a link, mem-

ory to prevent cycles, and diﬀerent pheromone update rules using local and/or global

information about the environment. The next sections provide an overview of the

early ant algorithms which are based on such changes of the simple ACO algorithm.

17.1.4 Ant System

The ﬁrst ant algorithm was developed by Dorigo [208], referred to as ant system (AS)

[4, 77, 216]. AS improves on SACO by changing the transition probability, p

,to

include heuristic information, and by adding a memory capability by the inclusion of

a tabu list. In AS, the probability of moving from node i to node j is given as

(t)=







(t)η

(t)



u∈N

(t)

(t)η

(t)

if j ∈N

(t)

0ifj ∈N

(t)

(17.6)

17.1 Ant Colony Optimization Meta-Heuristic 369

where τ

represents the a posteriori eﬀectiveness of the move from node i to node j,as

expressed in the pheromone intensity of the corresponding link, (i, j); η

represents the

apriorieﬀectiveness of the move from i to j (i.e. the attractiveness, or desirability,

of the move), computed using some heuristic. The pheromone concentrations, τ

indicate how proﬁtable it has been in the past to make a move from i to j,servingas

a memory of previous best moves.

The transition probability in equation (17.6) diﬀers from that of SACO in equation

(17.2) on two aspects:

• The transition probability used by AS is a balance between pheromone intensity

(i.e. history of previous successful moves), τ

, and heuristic information (ex-

pressing desirability of the move), η

. This eﬀectively balances the exploration–

exploitation trade-oﬀ. The search process favors actions that it has found in the

past and which proved to be eﬀective, thereby exploiting knowledge obtained

about the search space. On the other hand, in order to discover such actions,

the search has to investigate previously unseen actions, thereby exploring the

search space. The best balance between exploration and exploitation is achieved

through proper selection of the parameters α and β.Ifα = 0, no pheromone

information is used, i.e. previous search experience is neglected. The search then

degrades to a stochastic greedy search. If β = 0, the attractiveness (or potential

beneﬁt) of moves is neglected and the search algorithm is similar to SACO with

its associated problems.

The heuristic information adds an explicit bias towards the most attractive solu-

tions, and is therefore a problem-dependent function. For example, for problems

where the distance (or cost) of a path needs to be minimized,

(17.7)

where d

is the distance (or cost) between the nodes i and j.

• The set, N

, deﬁnes the set of feasible nodes for ant k when located on node i.

The set of feasible nodes may include only the immediate neighbors of node i.

Alternatively, to prevent loops, N

may include all nodes not yet visited by ant

k. For this purpose, a tabu list is usually maintained for each ant. As an ant

visits a new node, that node is added to the ant’s tabu list. Nodes in the tabu

list are removed from N

, ensuring that no node is visited more than once.

Maniezzo and Colorni used a diﬀerent formulation of the probability used to determine

the next node [557]:

(t)=

ατ

(t)+(1−α)η



u∈N

(t)

(ατ

(t)+(1−α)η

(t))

if j ∈N

(t)

0otherwise

(17.8)

Parameter α deﬁnes a relative importance of the pheromone concentration τ

(t)with

respect to the desirability, η

(t), of link (i, j). The probability p

expresses a com-

promise between exploiting desirability (for small α), and pheromone intensity. This

formulation removes the need for the parameter β.

370 17. Ant Algorithms

Pheromone evaporation is implemented as given in equation (17.5). After completion

of a path by each ant, the pheromone on each link is updated as

(t +1)=τ

(t)+∆τ

(t) (17.9)

with

∆τ

(t)=



k=1

∆τ

(t) (17.10)

where ∆τ

(t) is the amount of pheromone deposited by ant k on link (i, j)andk at

time step t. Dorigo et al. [216] developed three variations of AS, each diﬀering in the

way that ∆τ

is calculated (assuming a minimization problem):

• Ant-cycle AS:

∆τ

(t)=



f(x

(t))

if link (i, j) occurs in path x

(t)

0otherwise

(17.11)

For the ant-cycle implementation, pheromone deposits are inversely proportional

to the quality, f(x

(t)), of the complete path constructed by the ant. Global in-

formation is therefore used to update pheromone concentrations. Q is a positive

constant.

For maximization tasks,

∆τ

(t)=



Qf(x

(t)) if link (i, j) occurs in path x

(t)

0otherwise

(17.12)

• Ant-density AS:

∆τ

(t)=



Q if link (i, j) occurs in path x

(t)

0otherwise

(17.13)

Each ant deposits the same amount of pheromone on each link of its constructed

path. This approach essentially counts the number of ants that followed link

(i, j). The higher the density of the traﬃc on the link, the more desirable that

link becomes as component of the ﬁnal solution.

• Ant-quantity AS:

∆τ

(t)=

if link (i, j) occurs in path x

(t)

0otherwise

(17.14)

In this case, only local information, d

, is used to update pheromone concentra-

tions. Lower cost links are made more desirable. If d

represents the distance

between links, then ant-quantity AS prefers selection of the shortest links.

The AS algorithm is summarized in Algorithm 17.3. During the initialization step,

placement of ants is dictated by the problem being solved. If the objective is to ﬁnd the

shortest path between a given source and destination node, then all n

ants are placed

17.1 Ant Colony Optimization Meta-Heuristic 371

Algorithm 17.3 Ant System Algorithm

t =0;

Initialize all parameters, i.e. α, β, ρ, Q, n

,τ

;

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

;

for each link (i, j) do

(t) ∼ U(0,τ

);

end

repeat

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

(t)=∅;

repeat

From current node i, select next node j with probability as deﬁned in

equation (17.6);

(t)=x

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

until full path has been constructed;

Compute f(x

(t));

end

for each link (i, j) do

Apply evaporation using equation (17.5);

Calculate ∆τ

(t) using equation (17.10);

Update pheromone using equation (17.4);

end

for each link (i, j) do

(t +1)=τ

(t);

end

t = t +1;

until stopping condition is true;

Return x

(t):f(x

(t)) = min



=1,...,n

{f(x



(t))};

at the source node. On the other hand, if the objective is to construct the shortest

Hamiltonian path (i.e. a path that connects all nodes, once only), then the n

ants

are randomly distributed over the entire graph. By placing ants on randomly selected

nodes, the exploration ability of the search algorithm is improved. Pheromones are

either initialized to a constant value, τ

, or to small random values in the range [0,τ

Using Algorithm 17.3 as a skeleton, Dorigo et al. [216] experimented with the three

versions of AS. From the experiments, which focused on solving the traveling salesman

problem (both the symmetric and asymmetric versions) and the quadratic assignment

problem, it was concluded that the ant-cycle AS performs best, since global informa-

tion about the quality of solutions is used to determine the amount of pheromones to

deposit. For the ant-density and ant-quantity models, the search is not directed by

any measure of quality of the solutions.

Dorigo et al. [216] also introduced an elitist strategy where, in addition to the re-

inforcement of pheromones based on equation (17.4), an amount proportional to the

length of the best path is added to the pheromones on all the links that form part of

372 17. Ant Algorithms

the best path [216]. The pheromone update equation changes to

(t +1)=τ

(t)+∆τ

(t)+n

∆τ

(t) (17.15)

where

∆τ

(t)=



f(˜x(t))

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

0otherwise

(17.16)

and e is the number of elite ants. In equation (17.16), ˜x(t) is the current best route,

with f(˜x(t)) = min

k=1,...,n

{f(x

(t))}. The elitist strategy has as its objective direct-

ing the search of all ants to construct a solution to contain links of the current best

route.

17.1.5 Ant Colony System

The ant colony system (ACS) was developed by Gambardella and Dorigo to improve

the performance of AS [77, 215, 301]. ACS diﬀers from AS in four aspects: (1) a

diﬀerent transition rule is used, (2) a diﬀerent pheromone update rule is deﬁned, (3)

local pheromone updates are introduced, and (4) candidate lists are used to favor

speciﬁc nodes. Each of these modiﬁcations is discussed next.

The ACS transition rule, also referred to as a pseudo-random-proportional action rule

[301], was developed to explicitly balance the exploration and exploitation abilities of

the algorithm. Ant k, currently located at node i, selects the next node j to move to

using the rule,

j =



arg max

u∈N

(t)

{τ

(t)η

(t)} if r ≤ r

J if r>r

(17.17)

where r ∼ U (0, 1), and r

∈ [0, 1] is a user-speciﬁed parameter; J ∈N

(t) is a node

randomly selected according to probability

(t)=

(t)η

(t)



u∈N

(t)η

(t)

(17.18)

(t) is a set of valid nodes to visit.

The transition rule in equation (17.17) creates a bias towards nodes connected by short

links and with a large amount of pheromone. The parameter r

is used to balance

exploration and exploitation: if r ≤ r

, the algorithm exploits by favoring the best

edge; if r>r

, the algorithm explores. Therefore, the smaller the value of r

,theless

best links are exploited, while exploration is emphasized more. It is important to note

that the transition rule is the same as that of AS when r>r

. Also note that the

ACS transition rule uses α = 1, and is therefore omitted from equation (17.18).

Unlike AS, only the globally best ant (e.g. the ant that constructed the shortest

path, x

(t)) is allowed to reinforce pheromone concentrations on the links of the

corresponding best path. Pheromone is updated using the global update rule,

(t +1)=(1− ρ

)τ

(t)+ρ

∆τ

(t) (17.19)

17.1 Ant Colony Optimization Meta-Heuristic 373

where

∆τ

(t)=



f(x

(t))

if (i, j) ∈ x

(t)

0otherwise

(17.20)

with f(x

)(t)=|x

(t)|, in the case of ﬁnding shortest paths.

The ACS global update rule causes the search to be more directed, by encouraging

ants to search in the vicinity of the best solution found thus far. This strategy favors

exploitation, and is applied after all ants have constructed a solution.

Gambardella and Dorigo [215, 301] implemented two methods of selecting the path,

(t), namely

• iteration-best,wherex

(t) represents the best path found during the current

iteration, t, denoted as ˜x(t), and

• global-best,wherex

(t) represents the best path found from the ﬁrst iteration

of the algorithm, denoted as ˆx(t).

For the global-best strategy, the search process exploits more by using more global

information.

Pheromone evaporation is also treated slightly diﬀerently to that of AS. Referring

to equation (17.19), for small values of ρ

, the existing pheromone concentrations on

links evaporate slowly, while the inﬂuence of the best route is dampened. On the

other hand, for large values of ρ

, previous pheromone deposits evaporate rapidly, but

the inﬂuence of the best path is emphasized. The eﬀect of large ρ

is that previous

experience is neglected in favor of more recent experiences. Exploration is emphasized.

While the value of ρ

is usually ﬁxed, a strategy where ρ

is adjusted dynamically from

large to small values will favor exploration in the initial iterations of the search, while

focusing on exploiting the best found paths in the later iterations.

In addition to the global updating rule, ACS uses the local updating rule,

(t)=(1− ρ

)τ

(t)+ρ

(17.21)

with ρ

also in (0, 1), and τ

is a small positive constant. Experimental results on

diﬀerent TSPs showed that τ

=(n

−1

provided good results [215]; n

is the

number of nodes in graph G,andL is the length of a tour produced by a nearest-

neighbor heuristic for TSPs [737] (L can be any rough approximation to the optimal

tour length [215]).

ACS also redeﬁnes the meaning of the neighborhood set from which next nodes are

selected. The set of nodes, N

(t), is organized to contain a list of candidate nodes.

These candidate nodes are preferred nodes, to be visited ﬁrst. Let n

< |N

(t)| denote

the number of nodes in the candidate list. The n

nodes closest (in distance or cost)

to node i are included in the candidate list and ordered by increasing distance. When

a next node is selected, the best node in the candidate list is selected. If the candidate

list is empty, then node j is selected from the remainder of N

(t). Selection of a

non-candidate node can be based on equation (17.18), or alternatively the closest

non-candidate j ∈N

(t) can be selected.

374 17. Ant Algorithms

Algorithm 17.4 Ant Colony System Algorithm

t = 0; Initialize parameters β,ρ

,ρ

,τ

;

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

;

for each link (i, j) do

(t) ∼ U(0,τ

);

end

ˆx(t)=∅;

f(ˆx(t)) = 0;

repeat

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

(t)=∅;

repeat

if ∃j ∈ candidate list then

Choose j ∈N

(t) from candidate list using equations (17.17) and

(17.18);

end

else

Choose non-candidate j ∈N

(t);

end

(t)=x

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

Apply local update using equation (17.21);

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

for each link (i, j) ∈ ˆx(t) do

Apply global update using equation (17.19);

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 375

ACS is summarized in Algorithm 17.4.

In order to apply ACS to large, complex problems, Dorigo and Gambardella added a

local search procedure to iteratively improve solutions [215].

17.1.6 Max-Min Ant System

AS was shown to prematurely stagnate for complex problems. Here, stagnation means

that all ants follow exactly the same path, and premature stagnation occurs when ants

explore little and too rapidly exploit the highest pheromone concentrations. St¨utzle

and Hoos have introduced the max-min ant system (MMAS) to address the premature

stagnation problem of AS [815, 816]. The main diﬀerence between MMAS and AS is

that pheromone intensities are restricted within given intervals. Additional diﬀerences

are that only the best ant may reinforce pheromones, initial pheromones are set to the

max allowed value, and a pheromone smoothing mechanism is used.

The pheromone global update is similar to that of ACS, in equation (17.19), where

∆τ

(t) is calculated on the basis either of the global-best path or of the iteration-

best path. The ﬁrst version of MMAS focused on the iteration-best path, where ˜x(t)

represents the best path found during the current iteration [815]. Later versions also

included the global-best path, ˆx(t), using diﬀerent strategies [816]:

• Using only the global-best path to determine ∆τ

(t), in which case ˆx(t)isthe

best overall path found from the ﬁrst iteration. Using only the global best path

may concentrate the search too quickly around the global best solution, thus

limiting exploration. This problem is reduced if the iteration-best path is used,

since best paths may diﬀer considerably from one iteration to the next, thereby

allowing more exploration.

• Use mixed strategies, where both the iteration-best and the global-best paths

are used to update pheromone concentrations. As default, the iteration-best

path is used to favor exploration with the global-best path used periodically.

Alternatively, the frequency at which the global-best path is used to update

pheromones is increased over time.

• At the point of stagnation, all pheromone concentrations, τ

, are reinitialized

to the maximum allowed value, after which only the iteration-best path is used

for a limited number of iterations.

The λ-branching factor, with λ =0.05, is used to determine the point of stagna-

tion. Gambardella and Dorigo deﬁned the mean λ-branching factor as an indica-

tion of the dimension of the search space [300]. Over time the mean λ-branching

factor decreases to a small value at point of stagnation. The λ

-branching fac-

tor is deﬁned as the number of links leaving node i with τ

-values greater than

λδ

+ τ

i,min

; δ

= τ

i,max

− τ

i,min

,where

i,min

=min

jN

{τ

} (17.22)

i,max

=max

jN

{τ

} (17.23)

376 17. Ant Algorithms

and N

is the set of all nodes connected to node i.If



i∈V

< (17.24)

where  is a small positive value, it is assumed that the search process stagnated.

Throughout execution of the MMAS algorithm, all τ

are restricted within predeﬁned

ranges. For the ﬁrst MMAS version, τ

∈ [τ

min

,τ

max

] for all links (i, j), where both

min

and τ

max

were problem-dependent static parameters [815]. If after application

of the global update rule τ

(t +1)>τ

max

, τ

(t + 1) is explicitly set equal to τ

max

On the other hand, if τ

(t +1) <τ

min

, τ

(t +1) is set to τ

min

. Using an upper

bound for pheromone concentrations helps to avoid stagnation behavior: pheromone

concentrations are prevented from growing excessively, which limits the probability of

rapidly converging to the best path. Having a lower limit, τ

min

> 0, has the advantage

that all links have a nonzero probability of being included in a solution. In fact, if

min

> 0andη

< ∞, the probability of choosing a speciﬁc link as part of a solution

is never zero. The positive lower bound therefore facilitates better exploration.

St¨utzle and Hoos [816] formally derived that the maximum pheromone concentration

is asymptotically bounded. That is, for any τ

it holds that

lim

t→∞

(t)=τ

≤

1 − ρ

∗

(17.25)

where f

∗

is the cost (e.g. length) of the theoretical optimum solution.

This provides a theoretical value for the upper bound, τ

max

. Since the optimal solution

is generally not known, and therefore f

∗

is an unknown value, MMAS initializes to an

estimate of f

∗

, by setting f

∗

= f(ˆx(t)), where f (ˆx(t)) is the cost of the global-best

path. This means that the maximum value for pheromone concentrations changes as

soon as a new global-best position is found. The pheromone upper bound,

max

(t)=



1 − ρ



f(ˆx(t))

(17.26)

is therefore time-dependent.

St¨utzle and Hoos [816] derive formally that sensible values for the lower bound on

pheromone concentrations can be calculated using

min

(t)=

max

(t)(1 −

√

ˆpn

)

/2 − 1)

√

ˆpn

(17.27)

where ˆp is the probability at which the best solution is constructed. Note that ˆp<1

to ensure that τ

min

(t) > 0. Also note that if ˆp is too small, then τ

min

(t) >τ

max

(t). In

such cases, MMAS sets τ

min

(t)=τ

max

(t), which has the eﬀect that only the heuristic

information, η

, is used. The value of ˆp is a user-deﬁned parameter that needs to be

optimized for each new application.

During the initialization step of the MMAS algorithm (refer to Algorithm 17.5), all

pheromone concentrations are initialized to the maximum allowed value, τ

max

(0) =

max

17.1 Ant Colony Optimization Meta-Heuristic 377

Algorithm 17.5 MMAS Algorithm with Periodic Use of the Global-Best Path

Initialize parameters α, β, ρ, n

, ˆp, τ

min

,τ

max

;

t =0,τ

max

(0) = τ

max

,τ

min

(0) = τ

min

;

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

;

(t)=τ

max

(0), for all links (i, j);

(t)=∅, f(x

(t)) = 0;

repeat

if stagnation point then

for each link (i, j) do

Calculate ∆τ

(t) using equation (17.28);

(t +1)=τ

(t)+∆τ

(t);

end

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

(t)=∅;

repeat

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

(t)=x

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

until full path has been constructed;

Compute f(x

(t));

end

(t mod f

= 0) ? (Iteration Best = false) : (Iteration Best = true);

if Iteration Best = true then

Find iteration-best: x

(t)=x

(t):f(x

(t)) = min



=1,...,n

{f(x



(t))};

Compute f(x

(t));

end

else

Find global-best: x = x

(t):f(x

(t)) = min



=1,...,n

{f(x



(t))};

Compute f(x);

if f(x) <f(x

(t)) then

(t)=x;

f(x

(t)) = f(x);

end

for each link (i, j) ∈ x

(t) do

Apply global update using equation (17.19);

end

Constrict τ

(t)tobein[τ

min

(t),τ

max

(t)] for all (i, j);

(t +1)=x

(t);

f(x

(t +1))=f(x

(t));

t = t +1;

Update τ

max

(t) using equation (17.26);

Update τ

min

(t) using equation (17.27);

until stopping condition is true;

Return x

(t) as the solution;