Université Libre de Bruxelles
Institut de Recherches Interdisciplinaires
et de Développements en Intelligence Artificielle Ant Colony Optimization:Overview and
Recent Advances
Marco Dorigo and Thomas St¨u tzle
IRIDIA–Technical Report Series
Technical Report No.
TR/IRIDIA/2009-013
May2009
IRIDIA–Technical Report Series
ISSN1781-3794
Published by:
套路人的绕口令IRIDIA,Institut de Recherches Interdisciplinaires
西游记绘本
et de D´e veloppements en Intelligence Artificielle
Universit´e Libre de Bruxelles
Av F.D.Roovelt50,CP194/6
1050Bruxelles,Belgium
Technical report number TR/IRIDIA/2009-013
The information provided is the sole responsibility of the authors and does not necessarily reflect the opinion of the members of IRIDIA.The authors take full responsability for any copyright breaches that may result from publication of this paper in the IRIDIA–Technical Report Series.IRIDIA is not responsible for any u that might be made of data appearing in this publication.
Ant Colony Optimization:Overview and Recent Advances
左河水
Marco Dorigo and Thomas St¨u tzle
May2009
1Introduction
Ant Colony Optimization(ACO)[57,59,66]is a metaheuristic for solving hard combinatorial optimization problems.The inspiring source of ACO is the pheromone trail laying and following behavior of real ants,which u pheromones as a communication medium.In analogy to the biological example,ACO is bad on indirect communication within a colony of simple agents, called(artificial)ants,mediated by(artificial)pheromone trails.The pheromone trails in ACO rve as a distributed,numerical information,which the ants u to probabilistically construct solutions to the problem being solved and which the ants adapt during the algorithm’s execution to reflect their arch experience.
Thefirst example of such an algorithm is Ant System(AS)[55,63,64,65],which was pro-pod using as example application the well known traveling salesman problem(TSP)[6,99,128]. Despite encouraging initial results,AS could not compete with state-of-the-art algorithms for the TSP.Nevertheless,it had the important role of stimulating further rearch both on algorithmic variant
s,which obtain much better computational performance,and on applications to a large va-riety of different problems.In fact,there exist now a considerable number of applications of such algorithms where world class performance is obtained.Examples are applications of ACO algo-rithms to problems such as quential ordering[76],scheduling[18],asmbly line balancing[19], probabilistic TSP[7],2D-HP protein folding[132],DNA quencing[25],protein–ligand docking [98],packet-switched routing in Internet-like networks[47],and so on.The ACO metaheuris-tic provides a common framework for the existing applications and algorithmic variants[57,59]. Algorithms which follow the ACO metaheuristic are called ACO algorithms.
The(artificial)ants in ACO implement a randomized construction heuristic which makes prob-abilistic decisions as a function of artificial pheromone trails and possibly available heuristic in-formation bad on the input data of the problem to be solved.As such,ACO can be interpreted as an extension of traditional construction heuristics,which are readily available for many com-binatorial optimization problems.Yet,an important difference with construction heuristics is the adaptation of the pheromone trails during algorithm execution to take into account the cumulated arch experience.
The rest of this chapter is organized as follows.In Section2,we briefly overview construction heuristics and local arch algorithms.In Section3,we prent a specific version of the ACO metaheu
ristic that focus on applications to N P-hard problems.Section4outlines the inspiring biological analogy and describes the historical developments leading to ACO.In Section5,we illustrate how the ACO metaheuristic can be applied to different types of problems and we give an overview of its successful applications.Section6gives an overview of recent developments in ACO and Section7concludes the chapter.
2Approximate approaches
Many important combinatorial optimization problems are hard to solve.The notion of problem hardness is captured by the theory of computational complexity[79,123]and for many important problems it is well known that they are N P-hard,that is,the time needed to solve an instance
1
procedure Greedy Construction Heuristic
s p=empty solution
while s p not complete
1Other approximate methods are also conceivable.For example,when stopping exact methods,like Branch &Bound,before completion[10,95](for example,after some given time bound,or when some guarantee on the solution quality is obtained through the u of lower and upper bounds),we can convert exact algorithms into approximate ones.
procedure IterativeImprovement(s∈S)
s′=Improve(s)
乳牙几岁开始脱落while s′=s do
s=s′
s′=Improve(s)
end
return s
end IterativeImprovement
Figure2:Algorithmic skeleton of iterative improvement.
大提琴谱
此时无声胜有声作文
Figure3:Schematic illustration of a2-exchange move.The propod move reduces the total tour length if we consider the Euclidean distance between the points.
小米查真伪2.2Local arch algorithms
Local arch algorithms start from a complete initial solution and try tofind a better solution in an appropriately defined neighborhood of the current solution.In its most basic version,known as iterative improvement,the algorithm arches the neighborhood for an improving solution.If such a solution is found,it replaces the current solution and the local arch continues.The steps are repeated until no improving neighbor solution can be found and the algorithm ends in a local optimum.An outline of an iterative improvement algorithm is given in Figure2.The procedure Improve returns a better neighbor solution if one exists,otherwi it returns the current solution, in which ca the algorithm stops.
The choice of an appropriate neighborhood structure is crucial for the performance of local arch algorithms and has to be done in a problem specific way.The neighborhood structure defines the t of solutions that can be reached from s in one single step of the algorithm.An example neighborhood for the TSP is the k-exchange neighborhood in which neighbor solutions differ by at most k edges.Figure3shows an example of a2-exchange neighborhood.The2-exchange algorithm systematically tests whether the current tour can be improved by replacing two edges.To fully specify a local arch algorithm,it is necessary to designate a particular neighborhood examination scheme that defines how the neighborhood is arched and which neighbor solution replaces the current one.
In the ca of iterative improvement algorithms,this rule is called the pivoting rule [157]and examples are the best-improvement rule,which choos the neighbor solution giving the largest improvement of the objective function,and thefirst-improvement rule,which us thefirst improved solution found when scanning the neighborhood to replace the current one.A common problem with local arch algorithms is that they easily get trapped in local minima and that the result strongly depends on the initial solution.
3The ACO metaheuristic
如何烧红烧肉好吃Artificial ants ud in ACO are stochastic solution construction procedures that probabilistically build a solution by iteratively adding solution components to partial solutions by taking into account(i)heuristic information about the problem instance being solved,if available,and(ii)
(artificial)pheromone trails which change dynamically at run-time to reflect the agents’acquired arch experience.
A stochastic component in ACO allows the ants to build a wide variety of different solutions and hence to explore a much larger number of solutions than greedy heuristics.At the same time, the u of heuristic information,which is readily available for many problems,can guide the ants towards the
most promising solutions.More important,the ants’arch experience can be ud to influence,in a way reminiscent of reinforcement learning[149],the solution construction in future iterations of the algorithm.Additionally,the u of a colony of ants can give the algorithm incread robustness and in many ACO applications the collective interaction of a population of agents is needed to efficiently solve a problem.
The domain of application of ACO algorithms is vast.In principle,ACO can be applied to any discrete optimization problem for which some solution construction mechanism can be conceived. In the following of this ction,wefirst define a generic problem reprentation that the ants in ACO may exploit to construct solutions,and then we define the ACO metaheuristic.
3.1Problem reprentation
Let us consider minimization problems2and define a general model of a combinatorial optimization problem.
Definition3.1A model P=(S,Ω,f)of a combinatorial optimization problem consists of •a arch space S that is defined by afinite t of decision variables,each with afinite domain, and a tΩof constraints among the variables;
•an objective function f:S→I R+0that is to be minimized.
The arch space is defined by afinite t of variables X i,i=1,...,n,each having an associated domain D i of values that can be assigned to it.An instantiation of a variable consists in an assignment of a value v j i∈D i to variable X i and it is denoted by X i=v j i.A feasible solution s∈S is an assignment to each variable of a value in its domain such that all the problem constraints inΩare satisfied.IfΩis empty,then the problem is unconstrained and each decision variable can take any value from its domain,independent of the other variables.In this ca,P is an unconstrained problem model;otherwi it is called constrained.A feasible solution s∗∈S is called a global minimum of P if and only if we have that f(s∗)≤f(s)∀s∈S.We denote by S∗⊆S the t of all global minima.
This model of a combinatorial optimization problem can be directly ud to derive a generic pheromone model that is exploited by ACO algorithms.To e how,let us call the instantiation of a variable X i with a particular value v j i of its domain a solution component,which is denoted by c j i.Ants then need to appropriately combine solution components to form high-quality,feasible solutions.To do so,each solution component c j i will have an associated pheromone variable T ij. We denote the t of all solution components by C and the t of all pheromone variables by T. Each pheromone variable T ij has a pheromone valueτij;this value indicates the desirability of choosing sol
ution component c j i.Note that,as said before,the pheromone values are time-varying and therefore they are a function of the algorithm iteration t.In what follows we will,however, omit the reference to the iteration counter and write simplyτij instead ofτij(t).
As an example of this formalization,consider the TSP.In this ca,the solution components are the moves from one city to another one.This can be formalized by associating one variable to each city.Each variable X i has then associated n−1values,j=1,...,n,j=i.As a result,with each edge between a pair of cities is associated one pheromone valueτij.An instantiation of the decision variables corresponds to a feasible solution,if and only if the t of edges corresponding to the values of the decision variables forms a Hamiltonian cycle.(Note that for the TSP it is easily possible to guarantee that ants generate feasible solutions.)The objective function f(·)computes for each feasible solution the sum of the edge lengths,that is,the length of the Hamiltonian cycle.
