英文文献蚁群算法.docx
《英文文献蚁群算法.docx》由会员分享,可在线阅读,更多相关《英文文献蚁群算法.docx(16页珍藏版)》请在三一文库上搜索。
1、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
2、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 al
3、gorithms 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
4、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 p
5、hase 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
6、. 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, G
7、ermany 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 m
8、any 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
9、 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 Yan
10、nakakis 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
11、 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
12、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 probl
13、ems 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
14、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 a
15、nd 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
16、 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
17、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 v
18、alue 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 improv
19、ement 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 :
20、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 suc
21、h 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 presente
22、d 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 t
23、he 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 an
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 英文 文献 算法
![提示](https://www.31doc.com/images/bang_tan.gif)
链接地址:https://www.31doc.com/p-6349432.html