Convergence and Running Time of Time-dependent Ant Colony Algorithms
Bodo Manthey, Jesse van Rhijn, Ashkan Safari, Tjark Vredeveld · 2025
Read Convergence and Running Time of Time-dependent Ant Colony Algorithms by Bodo Manthey, Jesse van Rhijn, Ashkan Safari, Tjark Vredeveld (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10810.txt.
Introduction
Manthey and three colleagues study ant colony methods in twenty twenty-five, a math approach based on how ants search for food. Computer ants build trial answers step by step and leave a scent trail on good paths. The scent fades over time, and the fade rate can change as the search runs.
The team proves that one graph based method still finds the best answer in the end. They then test two changed forms of a second method on a shortest path task. One form can take far too long to finish. The other form solves the same task in a fair span of time. The work helps users pick safe settings for such searches.
Catalog record
| CREATOR | Bodo Manthey, Jesse van Rhijn, Ashkan Safari, Tjark Vredeveld |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-10810
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence and Running Time of Time-dependent Ant Colony Algorithms Bodo Manthey, Jesse van Rhijn, Ashkan Safari, Tjark Vredeveld Abstract Ant Colony Optimization (ACO) is a well-known method inspired by the foraging behavior of ants and is extensively used to solve combinatorial optimization problems. In this paper, we first consider a general framework based on the concept of a construction graph – a graph associated with an instance of the optimization problem under study, where feasible solutions are represented by walks. We analyze the running time of this ACO variant, known as the Graph-based Ant System with time-dependent evaporation rate (GBAS/tdev), and prove that the algorithm’s solution converges to the optimal solution of the problem with probability 1 for a slightly stronger evaporation rate function than was previously known. We then consider two time-dependent adaptations of Attiratanasunthron and Fakcharoenphol’s n n -ANT algorithm: n n -ANT with time-dependent evaporation rate ( n n -ANT/tdev) and n n -ANT with time-dependent lower pheromone bound ( n n -ANT/tdlb). We analyze both variants on the single destination shortest path problem (SDSP). Our results show that n n -ANT/tdev has a super-polynomial time lower bound on the SDSP. In contrast, we show that n n -ANT/tdlb achieves a polynomial time upper bound on this problem. Faculty of Electrical Engineering, Mathematics, and Computer Science, University of Twente, The Netherlands and https://people.utwente.nl/b.manthey [email protected]://orcid.org/0000-0001-6278-5059 Faculty of Electrical Engineering, Mathematics, and Computer Science, University of Twente, The Netherlands and https://people.utwente.nl/j.vanrhijn [email protected]://orcid.org/0000-0002-3416-7672Supported by NWO grant OCENW.KLEIN.176. Department of Quantitative Economics, School of Business and Economics, Maastricht University, The Netherlands and https://ashkansafari.com/ [email protected]://orcid.org/0000-0002-0471-1884Supported by NWO grant OCENW.KLEIN.176. Department of Quantitative Economics, School of Business and Economics, Maastricht University, The Netherlands and https://www.maastrichtuniversity.nl/nl/t-vredeveld [email protected]://orcid.org/0000-0002-6357-8622 ccs Theory of computation Random search heuristics ccs Theory of computation Random walks and Markov chains ccs Theory of computation Shortest paths keywords metaheuristics, ant colony optimization, shortest path problem † † runningauthor: B. Manthey, J. van Rhijn, A. Safari and T. Vredeveld † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Ant Colony Optimization (ACO) is a nature-inspired metaheuristic first proposed by Dorigo, Maniezzo and Colorni [ 7 ] . The heuristic attempts to model the capacity of ants to find efficient paths between their nest and food sources, effectively solving shortest-path problems without intrinsic knowledge of the problem structure [ 10 ] . This property - zero or little knowledge of the problem - is a strongly desired property of general purpose optimization algorithms. In nature, ants communicate by depositing pheromones on the ground while searching their environment for food sources. These pheromone trails attract other ants, who are inclined to follow the paths established by their predecessors. When foraging ants discover multiple routes between the nest and a food source, shorter paths become infused with pheromones more rapidly than longer ones because ants can traverse them more quickly. Consequently, as more ants choose the shorter path, the pheromone concentration along it increases, eventually leading almost all ants to follow this most efficient route. Since its inception, different variants of ACO have been proposed and implemented, to different levels of success, and have been applied to different problems such as Shortest Paths [ 3 , 24 ] , Traveling Salesperson Problem [ 8 , 17 , 22 , 25 ] , Minimum Weight Vertex Cover [ 21 ] , Minimum Cut [ 16 ] , and Minimum Spanning Tree [ 20 ] . As is often the case with heuristics, theoretical guarantees of its performance came later. The first convergence results were obtained by Gutjahr [ 11 ] , analyzing a variant called the Graph-based Ant System (GBAS). In summary, GBAS sets up a graph \mathcal{C} (called the construction graph ) given an instance \Pi of a combinatorial optimization problem. One maps solutions of \Pi to walks in \mathcal{C} starting and ending at fixed nodes s and t . A run of GBAS is divided into cycles . In each cycle, a number of ants (chosen by the practitioner) are placed on a special starting node of \mathcal{C} and perform a random walk. When an ant finds a walk w from s to t , it computes the cost of the corresponding solution. Then some amount of pheromone is placed on the arcs of the construction graph, in such a way that good walks are reinforced in the next cycle. The specific rule according to which the pheromone is placed differs per GBAS variant. Simultaneously, some arcs lose some pheromone at a set rate, the evaporation rate \rho\in(0,1) . In a first paper [ 11 ] , Gutjahr showed that GBAS finds the optimal solution of any problem with a unique optimum with probability 1-\varepsilon , which he later generalized to problems with non-unique optima [ 13 ] . Here, \varepsilon\in(0,1) is a constant fixed by the number of ants, the size of the optimal solution, and the evaporation rate. Also with probability 1-\varepsilon , the pheromone values on the arcs of \mathcal{C} converge to zero everywhere except on the arcs corresponding to the optimal walk w^{*} . Crucially, \varepsilon does not depend on the number of cycles m for which the algorithm is run, and hence GBAS cannot be guaranteed to find the optimum even in the limit m\to\infty . Contrastingly, in a simple random walk where each ant chooses the next node in its walk uniformly at random, the time taken for any ant to find the optimal walk is finite with probability 1. Many variants of ACO have been described in the literature. A brief overview is given by Dorigo and Stützle [ 9 , Chapter 2] . These variants can be rather involved, providing functionality for more complicated pheromone update rules and centralized “daemon actions”. Although this makes ACO a very flexible heuristic, it complicates the analysis. We therefore restrict our attention to simpler variants for the purposes of this paper. One variant that received decent attention is the Max-Min Ant System (MMAS) [ 23 ] . This version of ACO mainly differs from GBAS in restricting the range of possible pheromone values on any arc to [\tau_{\min{}},\tau_{\max{}}] and in the pheromone update rule, where the best solution found thus far is reinforced in every cycle. The parameters \tau_{\min} and \tau_{\max} are chosen in advance, but may depend on the problem instance. The running time of this variant has been analyzed for classical shortest path problems [ 3 , 24 ] , achieving polynomial running time there, and on the Traveling Salesperson Problem [ 17 , 25 ] , yielding high-quality solutions in polynomial time. Extending both GBAS and MMAS, Gutjahr [ 12 ] proposed variants for both of these algorithms. First, he proposed GBAS/tdev, for time-dependent evaporation rate . This algorithm replaced the constant evaporation rate \rho by a decreasing function \rho:\mathbb{N}\to(0,1) . For a suitable function, this results in convergence to