英文文献蚁群算法.docx

Algorithmica (2009) 54: 243255DOI 10.1007/s00453-007-9134-2Runtime Analysis of a Simple Ant Colony Optimization AlgorithmFrank Neumann Carsten WittReceived: 22 January 2007 / Accepted: 20 November 2007 / Published online: 28 November 2007 Springer Science+Business Media, LLC 2007Abstract Ant Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this ran-domized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved show-ing that optimal solutions can be obtained in finite time. We present the first runtime analysis of an ACO algorithm, which transfers many rigorous results with respect to the runtime of a simple evolutionary algorithm to our algorithm. Moreover, we ex-amine the choice of the evaporation factor, a crucial parameter in ACO algorithms, in detail. By deriving new lower bounds on the tails of sums of independent Poisson trials, we determine the effect of the evaporation factor almost completely and prove a phase transition from exponential to polynomial runtime.Keywords Randomized search heuristics Ant colony optimization Runtime analysisA preliminary version of this paper appeared in the Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), volume 4288 of LNCS, pp. 618627, Springer.Financial support for C. Witt by the Deutsche Forschungsgemeinschaft (SFB) in terms of the Collaborative Research Center “Computational Intelligence” (SFB 531) is gratefully acknowledged.F. Neumann ()Algorithms and Complexity, Max-Planck-Institut fr Informatik, 66123 Saarbrcken, Germany e-mail: fnempi-inf.mpg.deC. WittFB Informatik, LS 2, Universitt Dortmund, 44221 Dortmund, Germany e-mail: carsten.wittcs.uni-dortmund.de244Algorithmica (2009) 54: 2432551 IntroductionThe analysis of randomized search heuristics with respect to their runtime is a grow-ing research area where many results have been obtained in recent years. This class of heuristics contains well-known approaches such as Randomized Local Search (RLS), the Metropolis Algorithm (MA), Simulated Annealing (SA), and Evolutionary Algo-rithms (EAs). Such heuristics are often applied to problems whose structure is not known or if there are not enough resources such as time, money, or knowledge to obtain good specific algorithms. It is widely acknowledged that a solid theoretical foundation for such heuristics is needed.Some general results on the runtime of RLS can be found in Papadimitriou, Schf-fer and Yannakakis 13. The graph bisection problem has been subject to analysis of MA 11, where MA can be seen as SA with a fixed temperature. For a long time, it was an open question whether there is a natural example where SA outperforms MA for all fixed temperatures. This question has recently been answered positively by Wegener 15 for instances of the minimum spanning tree problem.In this paper, we focus on another kind of randomized search heuristics, namely Ant Colony Optimization (ACO). Like EAs, these heuristics imitate optimization processes from nature, in this case the search of an ant colony for a common source of food. Solving problems by ACO techniques has become quite popular in recent years. Developed by Dorigo, Maniezzo and Colorni 3, they have shown to be a powerful heuristic approach to solve combinatorial optimization problems such as the TSP (see 2, for an overview on the problems that these heuristics have been applied to). From a theoretical point of view, there are no results that provide estimates of the runtime of ACO algorithms. Despite interesting theoretical investigations of models and dynamics of ACO algorithms 1, convergence results are so far the only results related to their runtimes. Dorigo and Blum 1 explicitly formulate the open problem to determine the runtime of ACO algorithms on simple problems in a similar fashion to what has been done for EAs.We solve this problem, starting the analysis of ACO algorithms with respect to their expected runtimes and success probability after a specific number of steps. RLS, SA, MA, and simple EAs search more or less locally, and runtime bounds are often obtained by considering the neighborhood structure of the considered problem. Con-sidering ACO algorithms, this is different as search points are obtained by random walks of ants on a so-called construction graph. The traversal of an ant on this graph is determined by values on the edges which are called pheromone values. Larger pheromone values correspond to a higher probability of traversing a certain edge, where the choice of an edge usually fixes a parameter in the current search space. The pheromone values are updated if a good solution has been constructed in this random walk. This update depends on the traversal of the ant and a so-called evapo-ration factor .The choice of seems to be a crucial parameter in an ACO algorithm. Using a large value of , the last accepted solution changes the pheromone values by a large amount such that there is a large probability of producing this solution in the next step. In contrast to this, the use of a small evaporation factor leads to a small effect of the last accepted solution such that an improvement may be hard to find in the next step.Algorithmica (2009) 54: 243255245We show that a simple ACO algorithm behaves for very large values of (namely 1/3) as the simplest EA called (1 + 1) EA. This algorithm has been studied extensively with respect to its runtime on pseudo-boolean functions f : 0, 1n R (see, e.g. 4) as well as on combinatorial optimization problems. The list of problems where runtime bounds have been obtained include some of the best-known polyno-mially solvable problems such as maximum matchings 7 and minimum spanning trees 12. It should be clear that we cannot expect such general heuristics to out-perform the best-known algorithms for these mentioned problems. The main aim of such analyses is to get an understanding how these heuristics work. In the case of NP-hard problems, one is usually interested in good approximations of optimal solutions. Witt 16 has presented a worst-case and average-case analysis of the (1 + 1) EA for the partition problem, which is one of the first results on NP-hard problems. All these results immediately transfer to our ACO algorithm with very large .After these general results, we consider the effect of the evaporation factor on the runtime of our ACO algorithm in detail. As proposed in the open problem stated by Dorigo and Blum 1, we examine the simplest non-trivial pseudo-boolean func-tion called ONEMAX and analyze for the first time for which choices of the runtime with high probability is upper bounded by a polynomial and for which choices it is exponential. We observe a phase transition from exponential to small polynomial runtime when crosses the threshold value 1/n. Larger values of imply that the expected function value of a new solution is determined by the function value of the best seen solution. Then an improvement will be achieved after an expected polyno-mial number of steps. In the case of smaller , an improvement does not increase the expected function value sufficiently. Here exponential lower bounds are obtained by showing that there is a large gap between the expected value and the best-so-far function value. Both the proof of the upper and the lower runtime bound contain new analytical tools to lower bound the tail of a sum of independent trials with different success probabilities. The new tools may be of independent interest in other proba-bilistic analyses.In Sect. 2, we introduce the simple ACO algorithm which we will consider. We investigate its relation to the (1 + 1) EA in Sect. 3 and transfer the results on this EA to our algorithm. In Sect. 4, we investigate the choice of the evaporation factor for the function ONEMAX in greater detail. We finish with some conclusions.2 The AlgorithmGutjahr 9 has considered a graph-based ant system and investigated under which conditions such an algorithm converges to an optimal solution. We consider a sim-ple graph-based ant system metaheuristic that has been inspired by this algorithm. Such a heuristic produces solutions by random walks on a construction graph (see, e.g., 2). Let C = (V , E) be the construction graph with a designated start vertex s and pheromone values on the edges. Starting at s, an ant traverses the construction graph depending on the pheromone value using Algorithm 1. Assuming that the ant is at vertex v, the ant moves to a successor w of v, where w is chosen proportionally to the pheromone values of all non-visited successors of v. The process is iterated until a situation is reached where all successors of the current vertex v have been visited.246Algorithmica (2009) 54: 243255Algorithm 1 (Construct(C, )1. v := s, mark v as visited.2. While there is a successor of v in C that has not been visited:(a) Let Nv be the set of non-visited successors of v and T :=(v,w)|wNv (v,w) .(b) Choose one successor w of v where the probability of selection of any fixedu Nv is (v,u)/ T .(c) Mark w as visited, set v := w and go to 2.3. Return the solution x and the path P (x) constructed by this procedure.Based on this construction procedure, solutions of our simple ACO algorithm (see Algorithm 2) called 1-ANT are constructed. In the initialization step, each edge gets a pheromone value of 1/|E| such that the pheromone values sum up to 1. After that, an initial solution x is produced by a random walk on the construction graph and the pheromone values are updated with respect to this walk. In each iteration, a new solution x is constructed and the pheromone values are updated if this solution is not inferior to the currently best solution x . We formulate our algorithm for maximiza-tion problems although it can be easily adapted to minimization.Algorithm 2 (1-ANT )1. Set (u,v) = 1/|E| for all (u, v) E.2. Compute x (and P (x) using Construct(C, ).3. Update(, P (x) and set x := x.4. Compute x (and P (x) using Construct(C, ).5. If f (x) f (x), Update(, P (x) and set x := x.6. Go to 4.For theoretical investigations, it is common to have no termination condition in such an algorithm. One is interested in the random optimization time which equals the number of constructed solutions until the algorithm has produced an optimal search point. Usually, we try to bound the expected value of this time.We take a general view and consider optimization for pseudo-boolean goal func-tions f : 0, 1n R for n 3 using the canonical construction graph in our set-ting, Cbool = (V , E) (see Fig. 1) with s = v0. In the literature, this graph is also known as Chain 10. Optimizing bitstrings of length n, the graph has 3n + 1 ver-tices and 4n edges. The decision whether a bit xi , 1 i n, is set to 1 is madeFig. 1Construction graph for pseudo-boolean optimizationAlgorithmica (2009) 54: 243255247at node v3(i1) . In case that the edge (v3(i1), v3(i1)+1) is chosen, xi is set to 1 in the constructed solution. Otherwise xi = 0 holds. After this decision has been made, there is only one single edge which can be traversed in the next step. In case that (v3(i1), v 3(i1)+1) has been chosen, the next edge is (v 3(i1)+1, v3i ), and other-wise the edge (v3(i1)+2, v3i ) will be traversed. Hence, these edges have no influenceon the constructed solution and we can assume (v3(i1) ,v3(i 1)+1) = (v3(i1)+1,v3i ) and (v3(i1) ,v3(i1)+2) = (v3(i1)+2,v3i ) for 1 i n. We call the edges (v3(i1) , v3(i1)+1) and (v3(i1)+1, v3i ) 1-edges and the other edges 0-edges. We define the 1-potentialas the sum of pheromone values on 1-edges and call the edges (v3(i1), v3(i1)+1) and (v3(i1), v3(i1)+2) as well as (v3(i 1)+1, v 3i ) and (v3(i 1)+2, v3i ) complementary to each other.The pheromone values are chosen such that at each time (u,v)E (u,v) = 1 holds. In addition, it seems to be useful to have bounds on the pheromone values (see,e.g., 1) to ensure that each search point has a positive probability of being cho-sen in the next step. We restrict each (u,v) to the interval1,n1and ensure2n22n2(u,)E (u,) =1for u = v3i , 0 i n 1, and(,v) (,v) =1for v = v3i ,12n2nin. This can be achieved by normalizing the pheromone values after an up-11n1n1date and replacing the current value byif (u,v) <and by2if (u,v) >22n22n22n2nholds. As a consequence, the probability that a certain bit is set to 1 by the con-struction procedure is the pheromone value on the corresponding 1-edges multiplied by 2n.Depending on whether edge (u, v) is contained in the path P (x) of the accepted solution x, the pheromone values are updated to in the procedure Update(, P (x)as follows:=min(1 ) (u,v) + ,n 1if (u, v)P (x),2n2(u,v)1+2nand=max(1 ) (u,v),1if (u, v) / P (x).2n2(u,v)1+2nDue to the bounds on the pheromone values, the probability of fixing xi as in an optimal solution is at least 1/n. Hence, the 1-ANT finds an optimum for each pseudo-boolean function f regardless of in expected time at most nn .3 1-ANT and (1 + 1) EAWe consider the relation between the 1-ANT and a simple evolutionary algorithm called (1 + 1) EA, which has extensively been studied with respect to its runtime distribution. The (1 + 1) EA starts with a solution x that is chosen uniformly at random and produces in each iteration a new solution x from a currently best so-lution x by flipping each bit of x with probability 1/n. Hence, the probabil-ity of producing a certain solution x with Hamming distance H (x, x) to x is(1/n)H (x,x ) (1 1/n)nH (x,x ) .248Algorithmica (2009) 54: 243255Algorithm 3 (1 + 1) EA)1. Choose x 0, 1n uniformly at random.2. Construct x by flipping each bit of x independently with probability 1/n.3. Replace