MAX--MIN Ant System Thomas St utzle

–Ant System

Thomas St¨u tzle

Universit′e Libre de Bruxelles

IRIDIA

Brussels,Belgium

Holger H.Hoos

University of British Columbia

Department of Computer Science

Vancouver,Canada

1Introduction

Ant Colony Optimization(ACO)[13,8,14,11]is a recently developed,population-based approach which has been successfully applied to several-hard combina-torial optimization problems[5,7,12,19,20,29,35,45](see[10,11]for an overview).

As the name suggests,ACO has been inspired by the behavior of real ant colonies,

in particular,by their foraging behavior.One of its main ideas is the indirect com-

munication among the inpiduals of a colony of agents,called(arti?cial)ants,

based on an analogy with trails of a chemical substance,called pheromone,which

real ants use for communication.The(arti?cial)pheromone trails are a kind of dis-

tributed numeric information(called stigmergic information in[9])which is mod-

i?ed by the ants to re?ect their experience accumulated while solving a particular

problem.Recently,the Ant Colony Optimization(ACO)meta-heuristic has been

proposed to provide a unifying framework for most applications of ant algorithm-

s[11,10]to combinatorial optimization problems.Algorithms which actually are

instantiations of the ACO metaheuristic will be called ACO algorithms in the fol-

lowing.

The?rst ACO algorithm,called Ant System(AS)[13,8,14],was applied to the

Traveling Salesman Problem(TSP).It gave encouraging results,yet its perfor-

mance was not competitive with state-of-the-art algorithms for the TSP.Therefore,

one important focus of research on ACO algorithms has been the introduction of

algorithmic improvements to achieve a much better performance.Typically,these

improved algorithms have been tested again on the TSP[12,47,6].While they dif-

fer mainly in speci?c aspects of the search control,all these ACO algorithms are

based on a stronger exploitation of the search history to direct the ants’search pro-

cess.Recent research on the search space characteristics of some combinatorial

optimization problems has shown that for many problems there exists a correlation

between the solution quality and the distance from very good or optimal solution-

s[4,3,24,34].Hence,it seems reasonable to assume that the concentration of the

search around the best solutions found during the search is the key aspect that led

to the improved performance shown by the modi?ed ACO algorithms.

The–Ant System(AS)algorithm discussed in this article

achieves a strong exploitation of the search history by allowing only the best so-

lutions to add pheromone during the pheromone trail update.Also,the use of a

rather simple mechanism for limiting the strengths of the pheromone trails effec-

tively avoids premature convergence of the search.Finally,AS can easily

be extended by adding local search algorithms.In fact,the best performing ACO

algorithms for many different combinatorial optimization problems improve the so-

lutions generated by the ants with local search algorithms[12,19,47,45,5].As our

empirical results show,AS is currently one of the the best performing ACO

algorithms for the TSP and the Quadratic Assignment Problem(QAP).

The remainder of this paper is structured as follows.In Section2,we introduce

ACO algorithms and discuss their application to the TSP,using Ant System as

a starting point.Next,we review some results from the search space analysis of

the TSP which show that solution quality and distance from a global optimum

are tightly correlated and we give new results for a similar analysis of the QAP

search space.In Section4we give details on the modi?cations of AS leading to AS and present an experimental investigation showing the effectiveness of these modi?cations.Section5gives results of our extensive experimental analysis

of AS with additional local search for the TSP.In Section6we show that

2

AS is one of the best available algorithms for the QAP.In the concluding Section7we brie?y summarize our main results and point out directions for further research.

2Ant colony optimization

2.1ACO algorithms

ACO algorithms make use of simple agents called ants which iteratively con-struct candidate solution to a combinatorial optimization problem.The ants’solu-tion construction is guided by(arti?cial)pheromone trails and problem-dependent heuristic information.In principle,ACO algorithms can be applied to any combina-torial optimization problem by de?ning solution components which the ants use to iteratively construct candidate solutions and on which they may deposit pheromone (see[10,11]for more details).An inpidual ant constructs candidate solutions by starting with an empty solution and then iteratively adding solution components until a complete candidate solution is generated.We will call each point at which an ant has to decide which solution component to add to its current partial solution a choice point.After the solution construction is completed,the ants give feed-back on the solutions they have constructed by depositing pheromone on solution components which they have used in their solution.Typically,solution components which are part of better solutions or are used by many ants will receive a higher amount of pheromone and,hence,will more likely be used by the ants in future iterations of the algorithm.To avoid the search getting stuck,typically before the pheromone trails get reinforced,all pheromone trails are decreased by a factor. The ants’solutions are not guaranteed to be optimal with respect to local changes and hence may be further improved using local search methods.Based on this ob-servation,the best performing ACO algorithms for many-hard static combi-natorial problems are in fact hybrid algorithms combining probabilistic solution construction by a colony of ants with local search algorithms[12,19,30,45,47,48]. In such hybrid algorithms,the ants can be seen as guiding the local search by con-structing promising initial solutions,because ants preferably use solution compo-nents which,earlier in the search,have been contained in good locally optimal solutions.

In general,all ACO algorithms for static combinatorial problems follow a specif-ic algorithmic scheme outlined in Figure1.After the initialization of the pheromone trails and some parameters,a main loop is repeated until a termination condition —which may be a certain number of solution constructions or a given CPU-time limit—is met.In the main loop,?rst,the ants construct feasible solutions,then the generated solutions are possibly improved by applying local search,and?nally

the pheromone trails are updated.It should be noted that the ACO meta-heuristic [10,11]is more general than the algorithmic scheme given here.

procedure ACO algorithm for static combinatorial problems

Set parameters,initialize pheromone trails

while(termination condition not met)do

ConstructSolutions

ApplyLocalSearch%optional

UpdateTrails

end

end

Fig.1.Algorithmic skeleton for ACO algorithms applied to static combinatorial prob-lems.

2.2Combinatorial optimization problems

Traditionally,almost all ACO algorithms have been tested on the TSP[13,14,12,47,6]. In this article we focus on the TSP and the QAP as application domains for AS. 2.2.1The Traveling Salesman Problem

The TSP can be represented by a complete graph with being

the set of nodes,also called cities,and being the set of arcs fully connecting

the nodes.Each arc is assigned a value which represents the dis-tance between cities and.The TSP then is the problem of?nding a shortest closed tour visiting each of the nodes of exactly once.For sym-metric TSPs,the distances between the cities are independent of the direction

of traversing the arcs,that is,for every pair of nodes.In the asym-metric TSP(ATSP)at least for one pair of nodes we have.All

the TSP instances used in the empirical studies presented in this article are tak-

en from the TSPLIB benchmark library accessible at iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.These instances have been used in many other studies and partly stem from practical ap-plications of the TSP.

2.2.2The Quadratic Assignment Problem

The QAP is the problem of assigning a set of facilities to a set of locations with given distances between the locations and given?ows between the facilities.The goal is to place the facilities on locations in such a way that the sum of the products between?ows and distances is minimal.Given facilities and locations,two matrices and,where is the distance between locations

and and is the?ow between facilities and,the QAP is the problem to minimize

(1)

where is an arbitrary permutation of the set of integers(corresponding to an assignment of facilities to locations),and gives the location of facility in.Intuitively,represents the cost contribution of simultaneously as-signing facility to location and facility to location.

The QAP is an-hard optimization problem[41]and it is considered one of the hardest optimization problems.To date,instances of size can generally not be solved to optimality and one has to apply heuristic algorithms which?nd very high quality solutions in a reltively short computation time.The instances on which we will test AS are taken from the QAPLIB benchmark library (accessible at serv1.imm.dtu.dk/?sk/qaplib/).

2.3Applying Ant System to the TSP

When applying Ant System(AS)to the TSP,arcs are used as solution compo-nents.A pheromone trail,where is the iteration counter,is associated with each arc;these pheromone trails are modi?ed during the run of the algorith-m through pheromone trail evaporation and pheromone trail reinforcement by the ants.When applied to symmetric TSP instances,pheromone trails are also sym-metric()while in applications to asymmetric TSPs(ATSPs)possibly .

2.3.1Tour Construction

Initially,ants are placed on randomly chosen cities.Then,in each construc-tion step,each ant moves,based on a probabilistic decision,to a city it has not yet visited.This probabilistic choice is biased by the pheromone trail and by a locally available heuristic information.The latter is a function of the arc length; AS and all other ACO algorithms for the TSP use.Ants prefer cities which are close and connected by arcs with a high pheromone trail and in AS an ant currently located at city chooses to go to city with a probability:

retrace its tour,once it is completed,so that it can deposit pheromone on the arcs it contains.

2.3.2Pheromone Update.

After all ants have completed the tour construction,the pheromone trails are updated.This is done?rst by lowering the pheromone trails by a constant factor (evaporation)and then by allowing the ants to deposit pheromone on the arcs they have visited.In particular,the update follows this rule:

(3) where the parameter(with)is the trail persistence(thus,models the evaporation)and is the amount of pheromone ant puts on the arcs it has used in its tour.The evaporation mechanism helps to avoid unlimited accumu-lation of the pheromone trails.While an arc is not chosen by the ants,its associated pheromone trail decreases exponentially;this enables the algorithm to“forget”bad choices over time.In AS,is de?ned as follows:

if arc is used by ant in iteration

(4)

otherwise

where is the tour length of the th ant.By Equation4,the better the ant’s tour is,the more pheromone is received by the arcs belonging to this tour.In general, arcs which are used by many ants and which are contained in shorter tours will receive more pheromone and therefore will more likely be chosen in future itera-tions of the algorithm.In this sense the amount of pheromone represents the learned desirability of choosing the city to move to when an ant is in city.

2.4Applying Ant System to the QAP

The AS application to the TSP can be extended to the QAP in a straightforward way.The main difference is in the de?nition of the solution components which for the QAP are given by the assignments of facilities to locations.Hence,the pheromone trails in the QAP application correspond to the desirability of assigning a facility to a location.

For the solution construction,it can be convenient to use a preordering of the fa-cilities(or,equivalently,the locations)and assign facilities in the given order.The decision points are related to the assignments:at each decision point an ant prob-abilistically decides on which location the next facility should be put.In AS for the QAP,these decisions are done according to Equation2using a QAP-speci?c heuristic information[30].In this case the feasible neighborhood of ant com-prises those locations which are still free.The single construction steps are repeated until a complete assignment is obtained.The pheromone update is done as in the TSP application.

6

2.5Improvements over Ant System

AS has been compared with other general purpose heuristics on some relative-

ly small TSP instances with up to75cities.Some initial results were encouraging

and have shown the viability of the approach;for example,AS could be shown

to achieve better tour qualities than other nature-inspired algorithms,such as Sim-

ulated Annealing or Genetic Algorithms[14].However,for larger TSP instances

AS gives a very poor solution quality compared to state-of-the-art algorithms.A

?rst improvement over AS,called the elitist strategy for Ant System(AS e)[8,14],

gives a strong additional reinforcement to the solution components belonging to

the best solution found since the start of the algorithm;this solution is denoted as

(global-best solution)in the following.This is realized by adding a quantity ,where is the number of elitist ants and is the solution cost of, to the arcs used in after each iteration.Some limited results presented in[8,14]

suggest that the use of the elitist strategy with an appropriate number of elitist ants

allows AS to?nd better tours and to?nd them earlier in the run.Yet,if too many

elitist ants are used,the search concentrates early around suboptimal solutions lead-

ing to a premature stagnation of the search.Search stagnation is de?ned in[14]as

the situation where all ants follow the same path and construct the same solution

over and over again,such that better solutions cannot be found anymore.

Other improvements over AS include Ant Colony System(ACS)[18,12]and

the rank-based version of Ant System(AS rank)[5].In ACS and AS,the best

solutions found during the search are exploited by allowing only one ant to update

the trails after each iteration,while in AS rank a?xed number of ants of the current

iteration–the better the ants are ranked in the current iteration,the more weight

they are given for the trail update–and the global-best ant are allowed to update

the pheromone trails.

3Search space characteristics

All improved ACO algorithms have one important feature in common:they ex-

ploit the best solutions found during the search much more than what is done by

Ant System.Also,they use local search to improve the solutions constructed by the

ants.The fact that additional exploitation of the best found solutions provides the

key for an improved performance,is certainly related to the shape of the search s-

pace of many combinatorial optimization problems.In this section,we report some

results on the topology of search spaces of TSP and QAP instances which partly

explain the observed performance differences and motivates important aspects of

the algorithmic design of AS.

3.1Analysis of Fitness Landscapes

Central to the search space analysis of combinatorial optimization problems is

the notion of?tness landscape[42,53].Intuitively,the?tness landscape can be

7

imagined as a mountainous region with hills,craters,and valleys.A local search

algorithm can be pictured as a wanderer that performs a biased walk in this land-

scape.In a minimization problem such as the TSP or the QAP,the goal is to?nd

the lowest point in this landscape.The effectiveness of a given search strategy for

the wanderer strongly depends on the ruggedness of the landscape,the distribution

of the valleys and craters in the landscape,and the overall number of valleys and

craters.Formally,the?tness landscape is de?ned by

(1)the set of all possible solutions;

(2)an objective function that assigns a?tness value to every;

(3)a neighborhood structure.

The?tness landscape determines the shape of the search space as encountered by

a local search algorithm.The neighborhood structure induces a distance metric on

the set of solutions;the distance between two solutions and can be de?ned as the minimum number of moves that have to be performed to transform

into.

The distribution of local minima and their relative location with respect to global

optima is an important criterion for the effectiveness of adaptive multi-start algo-

rithms like ACO algorithms.For analyzing this aspect of the?tness landscape,the

correlation between solution?tness and the distance to optimal solutions has been

studied[3,24,34];in the literature on genetic algorithms this correlation is also

called the?tness-distance correlation(FDC)[24].This correlation can be captured

by the correlation coef?cient,which is de?ned as:

Cov

Var

2.53

3.5

44.555.566.5

7

140160180200220

240260p e r c e n t a g e d e v i a t i o n f r o m o p t i m u m distance to closest global optimum "rat783"024681012141618180200220240260280300320340360

p e r c e n t a g e d e v i a t i o n f r o m o p t i m u m distance to closest global optimum fl1577Fig.2.Fitness-distance plots for symmetric TSP instances.Each of the plots is based on 2500local optima.The plots are for the instances rat783(left)and fl1577(right).The -axis gives the distance to the closest global optimum,the -axis represents the percentage deviation from the minimal tour length.

3.2FDC Analysis for the TSP

The symmetric TSP is one of the most widely studied problems in terms of search space analysis [25,37,3,4].A good distance measure between two tours and is given by the number of different arcs,that is,

(where is the number of cities).A ?rst study of the correlation between the solution quality and the distance to the global optimum has been done

in [3].Additionally,plots of the solution cost versus the distance to the closest glob-al optimum have shown to be a very illustrative tool for the graphical presentation of the cost-distance relationship [3,24,34].Here,we exemplify results on the FDC analysis using some instances which are larger than previously studied ones.

For our investigation we use a 3-opt local search algorithm [27].This local search algorithm proceeds by systematically testing whether the current tour can be improved by replacing at most three arcs.Straightforward 3-opt implementa-tions require exchanges to be examined.Since this is too time-consuming in practice,we use a number of standard speed-up techniques [1,32,23]which achieve a sub-quadratical growth of the local search time with instance size.In particular,we restrict the set of examined moves to a candidate list of a ?xed number of near-est neighbors;here,as a default we set this number to 40.Additionally,we apply a ?xed radius nearest neighbor search [1,23].

For some instances several globally optimal solution exist.To partially address this issue,for each of these problems we generated a number of globally optimal solutions,then eliminated doubles and in our FDC analysis we use the distance to the closest of these global optima.(Note that the number in the instance name gives the number of cities.)Figure 2gives plots of the percentage deviation from the optimum versus the distance to the closest global optimum.All plots show a strong positive correlation between solution cost and the distance from the closest optimal solution —better local minima tend to be closer to the global optimum.Some summary results for the FDC analysis are given in Table 1,in particular,the average

9

Table1

Results of the FDC analysis on symmetric TSP instances based on25003-opt local optima.We report the instance name,the average percentage deviation from the optimum (Average(%)),the number of optimal solutions which are used in the FDC analysis(), the average distance between local optima(),the ratio between and the instance size,the average distance to the closest global optimum(),the ratio and the?tness-distance correlation coef?cient().

lin318.tsp 3.56175.830.22867.250.2110.469 rat783.tsp 4.85119249.320.318204.240.2610.624 pcb1173.tsp 5.917328.930.280274.340.2340.585 d1291.tsp 6.9627206.270.160159.190.1230.631 fl1577.tsp8.1627330.750.210267.250.1690.450 pr2392.tsp 5.7112660.910.276552.490.2310.538

Table2

Results of the FDC analysis for QAP instances from the4classes de?ned in this section. Given are the instance identi?er(the number in the instance name is the number of facili-ties),the?ow dominance fd,the distance dominance dd and the sparsity(sp).The remaining entries give summary results of the FDC analysis of the QAP search space.In particular,Average(%)is the average percentage deviation from the best known solution, is the number of optimal solutions used in the FDC analysis,is the average distance to the closest optimum,is the ratio between this average instance and the instance dimension,and is the correlation coef?cient.

unstructured,randomly generated(i)

Instances with grid-distances(ii)

real-life instances(iii)

real-life like instances(iv)

Real-life-like instances.Since the real-life instances in QAPLIB are of a rather small size,a particular type of randomly generated problems has been proposed in[50].These instances are generated in such a way that the matrix entries re-semble the distributions found for real-life problems.

To differentiate between the classes of QAP instances,the?ow dominance statistic fd can be used.It is de?ned as:

fd

and

A high?ow dominance indicates that a large part of the overall?ow is exchanged among relatively few items.Randomly generated problems from class(i)have a rather low?ow dominance,whereas real-life problems,in general,have a rather high?ow dominance.To capture the structure of the distance matrix,a distance dominance(dd)can be de?ned analogously.Additionally,real life problems of-ten have sparse?ow matrices,hence the sparsity of the?ow matrix,de?ned as

11

,where is the number of zero matrix entries,can give additional information on the instance type.

Our FDC analysis of the QAP search space uses a2-opt algorithm which ex-amines all possible exchanges of pairs of facilities.The distance between solutions and is measured as the number of items placed on different locations,that is,

.We measure the distance to the optimal solutions if they are available,otherwise we use the best known solutions.Note that for instances of class,,and with up to80items the currently best known solutions are conjectured to be optimal.

For the FDC analysis of the QAP search space one has to take into considera-tion the fact that many instances have multiple optimal solutions which may,due to symmetries in the distance matrix like in instances of class,be at maximal possible distance.Hence,on such instances one has to measure the distance to the closest global optimum to get meaningful results.As the exact number of glob-al optima for the QAP instances is not known,we determined a(possibly large) number of optimal(or best known)solutions.The?tness-distance analysis for the QAP is based on50002-opt local optima(identical solutions have been elim-inated).Some summary results are given in Table2,where additionally the?ow dominance,the distance dominance,and the sparsity of each instance are indicat-ed.Figure3shows scatter plots of the?tness-distance correlation for one instance of each problem class.

The?tness-distance analysis shows clear differences between the different prob-lem classes.For class,the correlation coef?cients are almost zero for all in-stances.Hence,the solution quality gives only very little guidance and on these instances ACO algorithms can be expected to perform rather poorly.For the other three classes,signi?cant correlations between the solution cost and the distance to an optimal solution exist.The only exception is instance bur26a for which the correlation coef?cient is not signi?cantly different from zero at the0.01level.Note that for instances with a high?ow or distance dominance and high sparsity,also a signi?cant FDC can be observed which suggests that these simpler measures may be used as indicators for a high FDC.

In summary,we can conclude that—on average—the better the solution quality the closer a solution is to an optimal solution in real-life QAP instances and also in those of classes and.These instances show a structure in the following sense:The optimal solutions determine the preferred locations of items.Hence,the more locations for items a solution has in common with an optimal solution,the better will be that solution,on average.As we have argued before,such a signi?cant correlation also indicates the potential usefulness of an ACO approach to the QAP. Comparing the results of the FDC analysis for the TSP and the QAP one may observe two main differences.First,the ratio between the average distance of the local minima from the closest optimal solution and the instance dimension,for both problems given by,is much smaller for the TSP than for the QAP.Second,the correlation coef?cients for the TSP instances are somewhat larger than for the QAP. Based on these observations we can conclude that local minima in the QAP appear to be spread over large parts of the QAP search space,while for the TSP they are

12

2.53

3.5

44.555.566.5

7

50525456

5860p e r c e n t a g e d e v i a t i o n f r o m o p t i m u m distance to closest optimum "tai60a"0.511.522.533.544.555.54045505560

p e r c e n t a g e d e v i a t i o n f r o m o p t i m u m distance to closest optimum "sko64"02

4

6810121416

18

05101520

2530p e r c e n t a g e d e v i a t i o n f r o m o p t i m u m distance to closest optimum "kra30a"02468101214161820354045505560

p e r c e n t a g e d e v i a t i o n f r o m o p t i m u m distance to closest optimum "tai60b"Fig.3.Fitness-distance plots for four QAP instances,one from each instance class.From top left to bottom right:tai60a (class ),sko64(class ),kra30a (class ),and

tai60b (class

).The number in the instance name is the number of facilities.The plots show 50002-opt solutions for each instance;the -axes gives the distance to the closest global optimum,while the -axes indicates the absolute solution cost.

concentrated on a relatively small subspace;also,the solution quality of QAP local minima tends to give somewhat less guidance than for the TSP.Hence,the QAP should be relatively more dif?cult to solve than the TSP,which is in accordance with the observed hardness of these problems in practice.Additionally,the fact that local minima in the QAP search space are more scattered suggests that in the QAP case effective algorithms need to do a stronger search space exploration than in the TSP case.

4–Ant System

Research on ACO has shown that improved performance may be obtained by a stronger exploitation of the best solutions found during the search and the search space analysis in the previous section gives an explanation of this fact.Yet,using a greedier search potentially aggravates the problem of premature stagnation of the search.Therefore,the key to achieve best performance of ACO algorithms is to combine an improved exploitation of the best solutions found during the search with an effective mechanism for avoiding early search stagnation.–

Ant System,which has been speci?cally developed to meet these requirements,differs in three key aspects from AS.

13

To exploit the best solutions found during an iteration or during the run of the algorithm,after each iteration only one single ant adds pheromone.This ant may be the one which found the best solution in the current iteration(iteration-best ant)or the one which found the best solution from the beginning of the trial (global-best ant).

To avoid stagnation of the search the range of possible pheromone trails on each solution component is limited to an interval min max.

Additionally,we deliberately initialize the pheromone trails to max,achieving in this way a higher exploration of solutions at the start of the algorithm.

In the next sections we discuss the differences between AS and AS in more detail and report computational results which demonstrate the effectiveness of the introduced modi?cations in improving the performance of the algorithm.

4.1Pheromone trail updating

In AS only one single ant is used to update the pheromone trails after each iteration.Consequently,the modi?ed pheromone trail update rule is given by

best(6)

where best best and best denotes the solution cost of either the iteration-best()or the global-best solution().Using one single ant for the pheromone trail update was also proposed in ACS[12].While in ACS typically only is used(although some limited experiments have also been performed us-ing),AS focuses on the use of the iteration-best solutions.

The use of only one solution,either or,for the pheromone update is the most important means of search exploitation in AS.By this choice,solution elements which frequently occur in the best found solutions get a large reinforce-ment.Still,a judicious choice between the iteration-best and global-best ant for updating the pheromone trails controls the way the history of the search is exploit-ed.When using only,the search may concentrate too fast around this solution and the exploration of possibly better ones is limited,with the consequent danger of getting trapped in poor quality solutions.This danger is reduced when is chosen for the pheromone trail update since the iteration-best solutions may differ considerably from iteration to iteration and a larger number of solution components may receive occasional reinforcement.Of course,one can also use mixed strategies like choosing as a default for updating the pheromones and using only every ?xed number of iterations.In fact,as we will show later,when using AS with local search for solving some of the larger TSP or QAP benchmark instances,the best strategy seems to be the use of a dynamical mixed strategy which increases the frequency of using for the pheromone update during the search(see Section5 for details).

14

4.2Pheromone trail limits

Independent of the choice between the iteration-best and the global-best ant for

the pheromone trail update,search stagnation may occur.This can happen if at each

choice point,the pheromone trail is signi?cantly higher for one choice than for all

the others.In the TSP case,this means that for each city,one of the exiting arcs

has a much higher pheromone level than the others.In this situation,due to the

probabilistic choice governed by Equation2,an ant will prefer this solution com-

ponent over all alternatives and further reinforcement will be given to the solution

component in the pheromone trail update.In such a situation the ants construct the

same solution over and over again and the exploration of the search space stops.

Obviously,such a stagnation situation should be avoided.One way for achiev-

ing this is to in?uence the probabilities for choosing the next solution component,

which depend directly on the pheromone trails and the heuristic information.The

heuristic information is typically problem-dependent and static throughout the al-

gorithm run.But by limiting the in?uence of the pheromone trails one can easi-

ly avoid the relative differences between the pheromone trails from becoming too

extreme during the run of the algorithm.To achieve this goal,AS imposes

explicit limits min and max on the minimum and maximum pheromone trails such

that for all pheromone trails,min max.After each iteration one has to ensure that the pheromone trail respects the limits.If we have max,we

set max;analogously,if min,we set min.Also note that

by enforcing min and if for all solution components,the probability of choosing a speci?c solution component is never0.

Still,appropriate values for the pheromone trail limits have to be chosen.In the

following we will propose a principled way of determining these values.Yet,?rst

we introduce the notion of convergence for–Ant System which is

needed in the following.We say that AS has converged if for each choice

point,one of the solution components has max as associated pheromone trail,while

all alternative solution components have a pheromone trail min.If AS has

converged,the solution constructed by always choosing the solution componen-

t with maximum pheromone trail will typically correspond to the best solution

found by the algorithm.The concept of convergence of AS differs in one

slight but important aspect from the concept of stagnation[14].While stagnation

describes the situation where all ants follow the same path,in convergence situa-

tions of AS this is not the case due to the use of the pheromone trail limits.

We now re?ne our concept of convergence by showing that the maximum possi-

ble pheromone trail is asymptotically bounded.

Proposition4.1For any it holds:

(7)

max

Proof:The maximum possible amount of pheromone added after any iteration

is,where is the optimal solution value for a speci?c problem.

15

Hence,by Equation6the discounted pheromone trail up to iteration corre-sponds to

max

Intuitively,we require best to be relatively large and later give numeric examples of reasonable values for best for the the AS application to the TSP.

16

construct the best solution with a probability of dec.By setting

dec best

(8) we can determine dec as

dec

max avg min

(10) Solving this equation for min yields

min max dec best

best

(11)

Note that if best,then min.If best is too small,it may happen that by Equation11min max.In this case we set min max which corresponds to using only the heuristic information in the solution construction.Based on Equation11, we can determine min,given a value for best.Choosing values for best is directly related to the amount of exploration done by–Ant System when it has converged.Thus,best provides a good way of investigating the effect of the lower trail limits on the performance of–Ant System.

In Section4.4.2we will investigate the proposed settings of min and we experi-mentally show the usefulness of the lower trail limits.

4.3Pheromone trail initialization

In AS we initialize the pheromone trails in such a way that after the?rst iteration all pheromone trails correspond to max.This can easily be achieved by setting to some arbitrarily high value.After the?rst iteration of AS,the trails will be forced to take values within the imposed bounds,in particular,they will be set to max.This type of trail initialization is chosen to increase the explo-ration of solutions during the?rst iterations of the algorithm.To illustrate this fact, consider the following example:Due to the trail evaporation(determined by param-eter),after the?rst iteration the relative difference between the pheromone trails on solution components will differ by a ratio of at most,after the second by, etc.If,on the contrary,the pheromone trails would be initialized to their lower lim-its min,the relative differences between the pheromone trails would increase much

more strongly;in particular,in this latter case,the ratio between min and the amount of pheromone deposited on a solution element is). With the empirically chosen parameter settings,this ratio is signi?cantly higher than the relative difference among the pheromone trail when initializing the phero-mone trails to max.For example,with the parameter settings chosen for the exper-imental investigation in the next section,in the?rst case this factor would amount to6.44,while when initializing the pheromone trails to max it corresponds to1.02. Thus,the selection probabilities of Equation2evolve more slowly when initializing the pheromone trails to max and,hence,the exploration of solutions is favored.The experimental results presented in Section4.4.3con?rm the conjecture that the larg-er exploration of the search space due to setting max improves AS’performance.

4.4Experiments with–Ant System

In this section we experimentally study the effectiveness of the three main mod-i?cations of AS compared to AS and the in?uence of speci?c parameter set-tings on AS performance.The experimental study uses the TSP as example application and here we use AS without local search;for a detailed overview of the results obtained with AS with local search for the TSP we refer to Section5.All the experiments were performed with a ceteris paribus assumption, that is,in each experiment only one single factor is varied and,hence,performance differences can only be attributed to the variation of this single factor.

Unless explicitly indicated otherwise,the following default parameter settings are used.We choose(where is the number of ants) and,an evaporation rate which results in a rather slow convergence for AS.The pheromone update is done using only the iteration-best ant.The phe-romone trail limits were chosen as proposed in Section4.2with best.The

ants start their solution construction from a randomly chosen city and they use can-didate lists of length20which contain the nearest neighbors ordered according to nondecreasing distances[1,28,40].When constructing a tour,an ant chooses prob-abilistically according to Equation2the next city among those in the candidate list, if possible.Only if all the members of the candidate list of a city have already been visited,one of the remaining cities is chosen.In this latter case we deterministically choose the city for which is maximum.

The TSP benchmark instances are all taken from TSPLIB;for all instances the optimal solution value is known.We will refer to the benchmark instances by the identi?er used in TSPLIB which indicates the number of cities(instance eil51 has51cities,etc.).

4.4.1Parameter values for

To examine the in?uence of different values of the pheromone trail evaporation rate,which determines the convergence speed of AS towards good solution-s,we present curves for the tradeoff between the average solution quality versus the number of tour constructions for the two TSP instances kroA100and d198using

18

00.5

1

1.52

2.5320000400006000080000100000120000140000

p e r c e n t a g e d e v i a t i o n No. tour constructions

"rho=0.98""rho=0.95""rho=0.90""rho=0.80""rho=0.70"02

4

6

81012

1410000100000

p e r c e n t a g e d e v i a t i o n No. tour constructions

"rho=0.98""rho=0.95""rho=0.90""rho=0.80""rho=0.70"Fig.4.In?uence of the parameter on the tradeoff between the number of tour con-structions (given on -axis)and the solution quality (given on -axis)on TSP instances kroA100(left)and d198(right).Note the log-scale on the x-axis;the upper and leftmost parts of the curves were cut off to focus on the important details.

different settings of averaged over 25and 10independent executions of the algo-rithms,respectively.The maximum number of tour constructions is and is varied between 0.7and 0.99.

In Figure 4,it can be observed that for a low number of tour constructions,better tours are found when using lower values of .This is due to the fact that for lower

the pheromone trails on arcs which are not reinforced decrease faster and,hence,the search concentrates earlier around the best tours seen so far.If is high,too few iterations are performed to reach marked differences between the pheromone trails on arcs contained in high quality tours and those which are not part of the best tours.For a larger number of tour constructions,however,using higher values pays off,because the algorithm is able to explore longer the search space.Additionally,it is interesting to note that with more tour constructions the average performance increases generally for all values of .This is mainly due to the effect of the lower trail limits (see also next section).

4.4.2Lower pheromone trail limits

To investigate the effectiveness of the lower trail limits,we compare experimen-tal results obtained by systematically varying best (as proposed in Section 4.2)and without using lower pheromone trail limits (min ).As before,we allow a max-imum tour constructions,which is suf?cient to achieve convergence of

19

AS on every instance.

Table3

Computational results for systematically varying best and without lower pheromone trail limits(min).Given are the average tour length,averaged over25runs,and in paren-thesis the percentage deviation from the optimal tour length.Note that the smaller best the tighter are the trail limits.The best results are indicated in bold-face.

eil51428.5(0.59%)428.0(0.46%)427.8(0.43%)427.7(0.39%)427.8(0.43%) kroA10021344.8(0.29%)21352.8(0.33%)21336.9(0.26%)21353.9(0.34%)21373.2(0.43%) d1*******.9(1.55%)15973.2(1.22%)15952.3(1.09%)16002.3(1.41%)16047.6(1.70%) lin31842363.4(0.80%)42295.7(0.64%)42346.6(0.75%)42423.0(0.94%)42631.8(1.43%)

instance max min

20

4.4.4Global versus iteration-best update

As mentioned before,updating the pheromone trails with may give advan-tages over using.We compare these two choices by running the same experi-ments as before,but always using for the pheromone trail update.Additionally, we investigate the in?uence of the lower pheromone trail limits by running each of the experiments with and without imposing lower pheromone trail limits.

The results are given in Table5.The average performance when using the iteration-best ants for pheromone update is signi?cantly better than using only the global-best ant.For example,a closer examination of the results(not reported here)showed that the worst solution obtained with the standard settings for AS was better than the average solution quality when using with pheromone trail limits for all instances.In general,using exclusively for the pheromone trail update seems not to be a very good idea for AS.Yet,the lower pheromone trail limits help to signi?cantly improve the performance when using.Nevertheless,mixed s-trategies which sometimes use may be helpful for achieving better exploitation of the search results.Experiments on larger instances have shown that using such mixed strategies with a frequency of increasing over time may yield a faster convergence of the algorithm and produce improved results.

Table5

Computational results for comparison of global-best update()versus iteration-best up-date()with and without using lower pheromone trail limits(indicated by either limits or no-limits).Given are the average tour length,averaged over25runs,and in parenthe-sis the percentage deviation from the optimal tour length.The best results are indicated in bold-face.

eil51427.8(0.43%)429.2(0.75%)427.8(0.43%)434.1(1.89%)

kroA10021336.9(0.26%)21417.1(0.64%)21373.2(0.43%)21814.7(2.50%)

d1*******.3(1.09%)16136.1(2.26%)16047.6(1.70%)16473.7(4.40%)

lin31842346.6(0.75%)42901.0(2.08%)42631.8(1.43%)44558.5(6.02%)

本文来源：https://www.bwwdw.com/article/3uwq.html