Engelbrecht Andries P. Computational Intelligence: An Introduction

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

398 17. Ant Algorithms

For the local search process, each ant k of the n

local ants selects a region x

based

on the probability

(t)=

(t)η

(t)



j∈N

(t)η

(t)

(17.71)

which biases towards the good regions. The ant then moves a distance away from the

selected region, x

, to a new region, x



,using



= x

+∆x (17.72)

where

∆x

= c

− m

(17.73)

with c

and m

user-deﬁned parameters, and a

the age of region x

. The age of a

region indicates the “weakness” of the corresponding solution. If the new position,



, does not have a better ﬁtness than x

, the age of x

is incremented. On the other

hand, if the new region has a better ﬁtness, the position vector of the i-th region is

replaced with the new vector x



The direction in which an ant moves remains the same if a region of better ﬁtness is

found. However, if the new region is less ﬁt, a new direction is randomly chosen.

Pheromone is updated by adding an amount to each τ

proportional to the ﬁtness of

the corresponding region.

Other approaches to solving continuous optimization problems can be found in [439,

510, 511, 512, 887].

17.4.2 Multi-Objective Optimization

One of the ﬁrst applications of multiple colony ACO algorithms was to solve multi-

objective optimization problems (MOP). This section discusses such algorithms.

MOPs are solved by assigning to each colony the responsibility of optimizing one

of the objectives. If n

objectives need to be optimized, a total of n

colonies are

used. Colonies cooperate to ﬁnd a solution that optimizes all objectives by sharing

information about the solutions found by each colony.

Gambardella et al. [303] implemented a two-colony system to solve a variant of the

vehicle routing problem. A local search heuristic is ﬁrst used to obtain a feasible

solution, x(0), which is then improved by the two colonies, each with respect to a

diﬀerent objective. Each colony maintains its own pheromone matrix, initialized to

have a bias towards the initial solution, x(0). If at any time, t, one of the colonies,

, obtains a better solution, then x(t)=˜x

(t)where˜x

(t) is the iteration-best

solution of colony C

. At this point the colonies are reinitialized such that pheromone

concentrations are biased towards the new best solution.

Ippolito et al. [404] use non-dominated sorting to implement sharing between colonies

through local and global pheromone updates. Each colony implements an ACS algo-

rithm to optimize one of the objectives. Separate pheromone matrices are maintained

17.4 Advanced Topics 399

by the diﬀerent colonies. Both local and global updates are based on

(t +1)=τ

(t)+γτ

(t) (17.74)

where γ ∈ (0, 1), and τ

is the initial pheromone on link (i, j)(allτ

(0) = τ

); f

(t)is

referred to as a ﬁtness value, whose calculation depends on whether equation (17.74)

is used for local or global updates. The ﬁtness value is calculated on the basis of a

sharing mechanism, performed before applying the pheromone updates. The purpose

of the sharing mechanism is to exchange information between the diﬀerent colonies.

Two sharing mechanisms are employed, namely local sharing and global sharing:

• Local sharing: After each next move has been selected (i.e. the next node

is added to the current path to form a new partial solution), local sharing is

applied. For this purpose, non-dominated sorting (refer to Section 9.6.3 and

Algorithm 9.11) is used to rank all partial solutions in classes of non-dominance.

Each non-dominance class forms a Pareto front, PF

containing n

= |PF

non-dominated solutions. The sharing mechanism assigns a ﬁtness value f

each solution in Pareto front PF

, as summarized in Algorithm 17.9. For the

purposes of this algorithm, let x

denote the solution vector that corresponds

to the partial path constructed by ant k at the current time step. Then, d

represents the normalized Euclidean distance between solution vectors x

and

, calculated as









l=1



− x

max,l

− x

min,l



(17.75)

where L ≤ n

is the length of the current paths (assuming that all paths are

always of the same length), and x

max

and x

min

respectively are the maximum

and minimum values of the variables that make up a solution.

A sharing value σ

is calculated for each distance, d

, as follows:

1 −



if d

<σ

0otherwise

(17.76)

where

0.5



∗

(17.77)

∗

is the desired number of Pareto optimal solutions. Using the sharing values,

a niche count, ξ

, is calculated for each solution vector x

,as



b=1

(17.78)

The ﬁtness value of each solution x

is calculated on the basis of the niche count:

(17.79)

400 17. Ant Algorithms

With reference to the local update using equation (17.74), f

(t) is the ﬁtness

value of the Pareto front to which the corresponding solution belongs, calculated

p+1

= f

min,p

− 

(17.80)

where 

is a small positive number, and

min,p



min

a=1,...,n

} if p>1

if p =1

(17.81)

with f

an appropriate positive constant.

• Global sharing: After completion of all paths, the corresponding solutions

are again (as for local sharing) grouped into non-dominance classes. The ﬁtness

value, f

(t) for the global update is calculated for the global-best solution similar

to that of local sharing (as given in Algorithm 17.9), but this time with respect

to the complete solutions.

Algorithm 17.9 Multiple Colony ACO Local Sharing Mechanism

for each Pareto front PF

,p=1,...,n

∗

for each solution x

∈PF

for each solution x

∈PF

Calculate d

using equation (17.75);

Calculate sharing value σ

using equation (17.76);

end

Calculate niche count ξ

using equation (17.78);

Calculate ﬁtness value f

using equation (17.79);

end

Calculate f

using equation (17.80);

end

Mariano and Morales [561] adapt the Ant-Q algorithm (refer to Section 17.1.7) to

use multiple colonies, referred to as families, to solve MOPs. Each colony tries to

optimize one of the objectives considering the solutions found for the other objectives.

The reward received depends on how the actions of a family helped to ﬁnd trade-

oﬀ solutions between the rest of the colonies. Each colony, C

,forc =1,...,n

has the same number of ants, |C

|. During each iteration, colonies ﬁnd solutions

sequentially, with the |C

| solutions found by the one colony inﬂuencing the starting

points of the next colony, by initializing AQ-values to bias toward the solutions of

the preceding colony. When all colonies have constructed their solutions, the non-

dominated solutions are selected. A reward is given to all ants in each of the colonies

that helped in constructing a non-dominated solution. The search continues until

all solutions found are non-dominated solutions, or until a predetermined number of

iterations has been exceeded.

Multi-pheromone matrix methods use more than one pheromone matrix, one for each

of the sub-objectives. Assuming only two objectives, Iredi et al. [405], uses two

17.4 Advanced Topics 401

pheromone matrices, τ

and τ

, one for each of the objectives. A separate heuristic

information matrix is also used for each of the objectives. The AS transition rule is

changed to

(t)=







ψα

1,ij

(t)τ

(1−ψ)α

2,ij

(t)η

ψβ

(t)η

(1−ψ)β

(t)



u∈N

(t)

ψα

1,iu

(t)τ

(1−ψ)α

2,iu

(t)η

ψβ

(t)η

(1−ψ)β

(t)

if j ∈N

(t)

0ifj ∈N

(t)

(17.82)

where ψ is calculated for each ant as the ratio of the ant index to the total number of

ants.

Every ant that generated a non-dominated solution is allowed to update both

pheromone matrices, by depositing an amount of

,wheren

is the number of

ants that constructed a non-dominated solution. All non-dominated solutions are

maintained in an archive.

Doerner et al. [205] modiﬁed the ACS (refer to Section 17.1.5) by using multiple

pheromone matrices, one for each objective. For each ant, a weight is assigned to each

objective to weight the contribution of the corresponding pheromone to determining

the probability of selecting the next component in a solution. The ACS transition rule

is changed to

j =



arg max

u∈N

(t)

{(



c=1

c,iu

(t))

(t)} if r ≤ r

J if r>r

(17.83)

where n

is the number of objectives, w

is the weight assigned to the c-th objective,

and J is selected on the basis of the probability

(t)=

(



c=1

c,iJ

(t))

(t)



u∈N

(



c=1

c,iu

(t))

(t)

(17.84)

Local pheromone updates are as for the original ACS, but done separately for each

objective:

c,ij

=(1− ρ)τ

c,ij

+ ρτ

(17.85)

The global update changes to

c,ij

=(1− ρ)τ

c,ij

+ ρ∆τ

c,ij

(17.86)

where

∆τ

c,ij











15 if (i, j) ∈ best and second-best solution

10 if (i, j) ∈ best solution

5if(i, j) ∈ second-best solution

0otherwise

(17.87)

with the best solutions above referring to non-dominated solutions. An archive of

non-dominated solutions is maintained.

Cardoso et al. [105] extended the AS to solve MOPs in dynamically changing envi-

ronments. A pheromone matrix, τ

, and pheromone ampliﬁcation coeﬃcient, α

,is

402 17. Ant Algorithms

maintained for each objective function f

. The AS transition rule is changed to

(t)=

β(t)



c=1

(τ

c,ij

)



u∈N

(t)

β(t)



c=1

(τ

c,iu

)

if j ∈N

(t)

0ifj ∈N

(t)

(17.88)

All visited links are updated by each ant with an amount

(x)

The approach of Iredi et al. [405] discussed above makes use of a diﬀerent heuristic

matrix for each objective (refer to equation (17.82)). Bar´an and Schaerer [49] devel-

oped a diﬀerent approach based on ACS, as a variation of the approach developed by

Gambardella et al. [303]. A single colony is used, with a single pheromone matrix, but

one heuristic matrix for each objective. Assuming two objectives, the ACS transition

rule changes to

j =



arg max

u∈N

(t)

{τ

(t)η

ψβ

1,iu

(t)η

(1−ψ)β

2,iu

(t)} if r ≤ r

J if r>r

(17.89)

where ψ ∈ [0, 1] and J is selected on the basis of the probability,

(t)=

(t)η

ψβ

1,iJ

(t)η

(1−ψ)β

2,iJ

(t)



u∈N

(t)η

ψβ

1,iu

(t)η

(1−ψ)β

2,iu

(t)

(17.90)

For the local update rule, the constant τ

is initially calculated using

(17.91)

where

and f

are the average objective values over a set of heuristically obtained

solutions (prior to the execution of the ant algorithm) for the two objectives respec-

tively. The constant is, however, changed over time. At each iteration, τ



is calculated

using equation (17.91), but calculated over the current set of non-dominated solu-

tions. If τ



>τ

, then pheromone trails are initialized to τ

= τ



; otherwise, the global

pheromone update is applied with respect to each solution x ∈P,whereP is the set

on non-dominated solutions:

=(1− ρ)τ

(x)f

(x)

(17.92)

17.4.3 Dynamic Environments

For dynamic optimization problems (refer to Section A.9), the search space changes

over time. A current good solution may not be a good solution after a change in

the environment has occurred. Ant algorithms may not be able to track changing

environments due to pheromone concentrations that become too strong [77]. If most of

the ants have already settled on the same solution, the high pheromone concentrations

on the links representing that solution cause that solution to be constructed by all

future ants with very high probability even though a change has occurred. To enable

17.4 Advanced Topics 403

ACO algorithms to track changing environments, mechanisms have to be employed to

favor exploration.

For example, using the transition probability of ACS (refer to equation (17.18)), ex-

ploration is increased by selecting a small value for r

and increasing β. This will

force more random transition decisions, where the new, updated heuristic information

creates a bias towards the selection of links that are more desirable according to the

changed environment.

An alternative is to use an update rule where only those links that form part of a

solution have their pheromone updated, including an evaporation component similar

to the local update rule of ACS (refer to Section 17.1.5). Over time the pheromone

concentrations on the frequently used links decrease, and these links become less fa-

vorable. Less frequently used links will then be explored.

A very simple strategy is to reinitialize pheromone after change detection, but to keep a

reference to the previous best solution found. If the location of an environment change

can be identiﬁed, the pheromone of links in the neighborhood can be reinitialized to

a maximum value, forcing these links to be more desirable. If these links turn out

to represent bad solution components, reinforcement will be small (since it is usually

proportional to the quality of the solution), and over time desirability of the links

reduces due to evaporation.

Guntsch and Middendorf [340] proposed to repair solutions when a change occurred.

This can be done by applying a local search procedure to all solutions. Alternatively,

components aﬀected by change are deleted from the solution, connecting the prede-

cessor and successor of the deleted component. New components (not yet used in the

solution) are then inserted on the basis of a greedy algorithm. The position where a

new component is inserted is the position that causes the least cost increase, or highest

cost decrease (depending on the objective).

Sim and Sun [791] used a multiple colony system, where colonies are repelled by the

pheromone of other colonies to promote exploration in the case of changing environ-

ments.

Other approaches to cope with changing environments change the pheromone update

rules to favor exploration: Li and Gong [520] modify both the local and global update

rules. The local update rule is changed to

(t +1)=(1− ρ

(τ

(t)))τ

(t)+∆τ

(t) (17.93)

where ρ

(τ

) is a monotonically increasing function of τ

,e.g.

(τ

1+e

−(τ

+θ)

(17.94)

where θ>0.

The dynamic changing evaporation constant has the eﬀect that high pheromone values

are decreased more than low pheromone values. In the event of an environment change,

and if a solution is no longer the best solution, the pheromone concentrations on the

corresponding links decrease over time.

404 17. Ant Algorithms

The global update is done similarly, but only with respect to the global-best and

global-worst solutions, i.e.

(t +1)=(1− ρ

(τ

(t)))τ

(t)+γ

∆τ

(t) (17.95)

where







+1 if (i, j) is in the global-best solution

−1if(i, j) is in the global-worst solution

0otherwise

(17.96)

Guntsch and Middendorf [339] proposed three pheromone update rules for dynamic

environments. The objective of these update rules is to ﬁnd an optimal balance be-

tween resetting enough information to allow for exploration of new solutions, while

keeping enough information of the previous search process to speed up the process of

ﬁnding a solution. For each of the strategies, a reset value, γ

∈ [0, 1] is calculated,

and pheromone reinitialized using

(t +1)=(1− γ

)τ

+ γ

− 1

(17.97)

where n

is the number of nodes in the representation graph. The following strategies

were proposed:

• Restart strategy: For this strategy,

= λ

(17.98)

where λ

∈ [0, 1] is referred to as the strategy-speciﬁc parameter. This strategy

does not take the location of the environment change into account.

• η-strategy: Heuristic information is used to decide to what degree pheromone

values are equalized:

=max{0,d

} (17.99)

where

=1−

,λ

∈ [0, ∞) (17.100)

and

η =

− 1)



i=1



j=1,j=i

(17.101)

Here γ

is proportional to the distance from the changed component, and equal-

ization is done on all links incident to the changed component.

• τ-strategy: Pheromone values are used to equalize links closer to the changed

component more than further links:

=min{1,λ

},λ

∈ [0, ∞) (17.102)

where

=max









(x,y)∈N

max







(17.103)

and N

is the set of all paths from i to j.

17.5 Applications 405

Table 17.2 Ant Algorithm Applications

Problem Reference

Assignment problems [29, 230, 508, 555, 608, 704, 801]

Bioinformatics [573, 787]

Data clustering [540, 853]

Robotics [574, 912]

Routing [94, 99, 131, 161, 207, 516]

Scheduling [76, 282, 302, 334, 391, 572, 579, 927]

Sequential ordering problem [302]

Set covering [180]

Shortest common super-sequence [591]

Text mining [345, 370, 525, 703]

17.5 Applications

Ant algorithms have been applied to a large number of real-world problems. One of

the ﬁrst applications is that of the ACO to solve the TSP [142,150]. ACO algorithms

can, however, be applied to optimization problems for which the following problem-

dependent aspects can be deﬁned [77, 216]:

1. An appropriate graph representation to represent the discrete search space.

The graph should accurately represent all states and transitions between states.

A solution representation scheme also has to be deﬁned.

2. An autocatalytic (positive) feedback process; that is, a mechanism to up-

date pheromone concentrations such that current successes positively inﬂuence

future solution construction.

3. Heuristic desirability of links in the representation graph.

4. A constraint-satisfaction method to ensure that only feasible solutions are

constructed.

5. A solution construction method which deﬁnes the way in which solutions are

built, and a state transition probability.

In addition to the above requirements, the solution construction method may specify

a local search heuristic to reﬁne solutions.

This section provides a detailed explanation of how ACO can be applied to solve the

TSP and the QAP. Table 17.2 provides a list of other applications (this list is by no

means complete).

406 17. Ant Algorithms

17.5.1 Traveling Salesman Problem

The traveling salesman problem (TSP) is the ﬁrst application to which an ACO al-

gorithm was applied [208, 216]. It is an NP-hard combinatorial optimization problem

[310], and is the most frequently used problem in ACO literature [208, 213, 214, 216,

300, 301, 339, 340, 433, 592, 814, 815, 821, 852, 900, 939]. This section shows how

ACO algorithms can be used to solve the TSP.

Problem Deﬁnition

Given a set of n

cities, the objective is to ﬁnd a minimal length closed (Hamiltonian)

tour that visits each city once. Let π represent a solution as a permutation of the

cities {1,...,n

},whereπ(i) indicates the i-th city visited. Then, Π(n

)isthesetof

all permutations of {1,...,n

}, i.e. the search space. Formally, the TSP is deﬁned as

ﬁnding the optimal permutation π

∗

,where

∗

=arg min

π∈Π(n

)

f(π) (17.104)

where

f(π)=



i,j=1

(17.105)

is the objective function, with d

the distance between cities i and j.LetD =

]

×n

denote the distance matrix.

Two versions of the TSP are deﬁned based on the characteristics of the distance matrix.

If d

= d

for all i, j =1...,n

, then the problem is referred to as the symmetric TSP

(STSP). If d

= d

, the distance matrix is asymmetric resulting in the asymmetric

TSP (ATSP).

Problem Representation

The representation graph is the 3-tuple, G =(V,E,D), where V is the set of nodes,

each representing one city, E represents the links between cities, and D is the distance

matrix which assigns a weight to each link (i, j) ∈ E. A solution is represented as

an ordered sequence π =(1, 2,...,n

) which indicates the order in which cities are

visited.

Heuristic Desirability

The desirability of adding city j after city i is calculated as

(t)=

(t)

(17.106)

17.5 Applications 407

Reference to the time step t is included here to allow dynamic problems where distances

may change over time.

Constraint Satisfaction

The TSP deﬁnes two constraints:

1. All cities must be visited.

2. Each city is visited once only.

To ensure that cities are visited once only, a tabu list is maintained for each partial

solution to contain all cities already visited. Let Υ

denote the tabu list of the k-th

ant. Then, N

(t)=V \Υ

(t) is the set of cities not yet visited after reaching city i.

The ﬁrst constraint is satisﬁed by requiring each solution to contain n cities, and by

result of the tabu list.

Solution Construction

Ants are placed on random cities, and each ant incrementally constructs a solution,

by selecting the next city using the transition probability of any of the previously

discussed ACO algorithms.

Local Search

The most popular search heuristics applied to TSP are the 2-opt and 3-opt heuristics

[423]. Both heuristics involve exchanging links until a local minimum has been found.

The 2-opt heuristic [433, 815, 900] makes two breaks in the tour and recombines nodes

in the only other possible way. If the cost of the tour is improved, the modiﬁcation

is accepted. The 2-opt heuristic is illustrated in Figure 17.4(a). The 3-opt heuristic

[215, 814, 815, 900] breaks the tour at three links, and recombines the nodes to form

two alternative tours. The best of the original and two alternatives are kept. The

3-opt heuristic is illustrated in Figure 17.4(b). For the ATSP, a variation of the 3-opt

is implemented to allow only exchanges that do not change the order in which cities

are visited.

17.5.2 Quadratic Assignment Problem

The quadratic assignment problem (QAP) is possibly the second problem to which

an ACO algorithm was applied [216], and is, after the TSP, the most frequently used

problem for benchmarking ACO algorithms [216, 304, 340, 557, 743, 744, 835]. The

QAP, introduced by Koopmans and Beckman [477], is an NP-hard problem considered

as one of the hardest optimization problems. Even instances of relatively small size of