标题： 时间依赖型蚁群算法的收敛性与运行时间 显示英文标题

标题： Convergence and Running Time of Time-dependent Ant Colony Algorithms

摘要： 蚁群优化（ACO）是一种受蚂蚁觅食行为启发的知名方法，广泛用于解决组合优化问题。 在本文中，我们首先考虑一个基于构造图概念的一般框架——与正在研究的优化问题实例相关联的图，其中可行解由行走表示。 我们分析了这种ACO变体的运行时间，称为基于图的蚁群系统，具有时间依赖的蒸发率（GBAS/tdev），并证明当蒸发率函数比之前已知的稍强时，该算法的解以概率1收敛到问题的最优解。 然后，我们考虑Attiratanasunthron和Fakcharoenphol的$n$-ANT算法的两种时间依赖适应：具有时间依赖蒸发率的$n$-ANT（$n$-ANT/tdev）和具有时间依赖信息素下限的$n$-ANT（$n$-ANT/tdlb）。 我们在单点最短路径问题（SDSP）上分析了这两种变体。 我们的结果表明，$n$-ANT/tdev在SDSP上具有超多项式时间下界。 相反，我们证明$n$-ANT/tdlb在此问题上实现了多项式时间上界。 显示英文摘要

摘要： 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$-ANT algorithm: $n$-ANT with time-dependent evaporation rate ($n$-ANT/tdev) and $n$-ANT with time-dependent lower pheromone bound ($n$-ANT/tdlb). We analyze both variants on the single destination shortest path problem (SDSP). Our results show that $n$-ANT/tdev has a super-polynomial time lower bound on the SDSP. In contrast, we show that $n$-ANT/tdlb achieves a polynomial time upper bound on this problem.