Running-time Analysis of Ant System Algorithms with Upper-bound Comparison
Running-time Analysis of Ant System Algorithms with Upper-bound Comparison
复制标题
具有上界比较的蚂蚁系统算法运行时间分析
DOI：
10.4018/ijsir.2017100101
复制
发表时间：
2017-10-01
影响因子：
1.1
通讯作者：
Hao, Zhifeng
中科院分区：
文献类型：
--
作者：
Huang, Han;Wu, Hongyue;Hao, Zhifeng
蚁群优化算法的运行时间分析对于理解算法的计算能力至关重要。对求解旅行商问题（TSP）的蚁群算法（AS）进行了运行时间分析。作者通过联合表示的最佳到目前为止的解决方案和信息素矩阵作为一个离散的随机状态，每次迭代的吸收马尔可夫链的AS算法模型。算法的运行时间可以用期望首次命中时间（FHT）来衡量，即平均达到全局最优解所需的最少迭代次数。作者推导了两种经典AS算法（即，蚂蚁数量系统和蚂蚁循环系统）。并以正多边形TSP（RTSP）为例，计算了6个RTSP实例，得到了数值结果。RTSP是一种特殊的但现实世界的TSP，其中严格施加了三角不等式的约束。两种AS算法的运行时间比较的数值结果验证了我们的理论研究结果。
Running- time analysis of ant colony optimization (ACO) is crucial for understanding the power of the algorithm in computation. This paper conducts a running-time analysis of ant system algorithms (AS) as a kind of ACO for traveling salesman problems (TSP). The authors model the AS algorithm as an absorbing Markov chain through jointly representing the best-so-far solutions and pheromone matrix as a discrete stochastic status per iteration. The running-time of AS can be evaluated by the expected first-hitting time (FHT), the least number of iterations needed to attain the global optimal solution on average. The authors derive upper bounds of the expected FHT of two classical AS algorithms (i.e., ant quantity system and ant-cycle system) for TSP. They further take regular-polygon TSP (RTSP) as a case study and obtain numerical results by calculating six RTSP instances. The RTSP is a special but real-world TSP where the constraint of triangle inequality is stringently imposed. The numerical results derived from the comparison of the running time of the two AS algorithms verify our theoretical findings.