具有上限比较的蚂蚁系统算法的运行时分析资源-CSDN文库

50 浏览量 2021-03-12 03:47:34 上传评论收藏 679KB PDF 举报

资源推荐

资源详情

资源评论

DOI: 10.4018/IJSIR.2017100101



Volume 8 • Issue 4 • October-December 2017





Han Huang, School of Software Engineering, South China University of Technology, Guangzhou, China

Hongyue Wu, School of Software Engineering, South China University of Technology, Guangzhou, China

Yushan Zhang, School of Statistics and Mathematics, Guangdong University of Finance and Economics, Guangzhou, China

Zhiyong Lin, Department of Computer Science, Guangdong Polytechnic Normal University, Guangzhou, China

Zhifeng Hao, School of Applied Mathematics, Guangdong University of Technology, Guangzhou, China



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.



Ant System Algorithm, First‐Hitting Time, Pheromone Rate, Running‐Time Analysis, Swarm Intelligence



Ant colony optimization (ACO) is a nature-inspired computational method. It was first proposed by

Dorigo et al. (1996) who were inspired by the seeking food behavior of ants in a colony. Although

it was originally used to solve the shortest path problem, ACO has been applied to a wide range of

problems, which include the traveling salesman problem (TSP) (Dorigo et al.,1996; Dorigo et al.,

2006) and other combinatorial optimization problems (Oliveto, 2007; Venkatraman & Ritchie, 2012;

Vaisakh & Srinivas, 2010). Numerous experimental results have been reported in the literature to

show the capacity of ACO in optimization. In fact, this approach has become one of the best-known

metaheuristic techniques, along with Tabu search, genetic and evolutionary algorithms, simulated

annealing, and other prominent general-purpose search methods (Dorigo & Stützle, 1999).

With the progress of work on ACO, the research community, as Dorigo and Blum pointed

out in their survey (Dorigo & Blum, 2005), has come to the conclusion that it would deepen the



Volume 8 • Issue 4 • October-December 2017

understanding of ACO through increased efforts to extend its theoretical foundations. Overall, the

current research related to the theoretical foundations of ACO can be divided into two important

branches: convergence proof and running-time analysis. Actually, in the survey conducted by Dorigo

et al. (2005), the running-time analysis is taken as the first open problem in the ACO research field.

Gutjahr and Sebastiani have pointed out in their recent study (Gutjahr, 2007; Gutjahr & Sebastiani,

2008) that the most urgent goal of ACO running-time research in the immediate future is to extend

the existing results of time complexity to the NP-complete problems such as TSP.

Along the line advocated by Gutjahr et al. (2007), we focus on the running-time analysis of

ACO for TSP in this paper. Specifically, we investigated a special ACO, i.e., ant system algorithm

(AS) (Dorigo et al., 1996). We modeled AS as an absorbing Markov chain by taking the ant-catching

solutions and pheromone matrix per iteration as a discrete status. Based on our prior work (Huang et

al., 2009), we establish a general framework for the running-time analysis of AS, where the concept

of first-hitting time (Neumann et al., 2009; Chen et al., 2010), i.e., the time that the optimal solution

is first found, plays a crucial role. In this study, we show how the proposed framework work well

for the running-time analysis of AS by investigating a special TSP, i.e., regular-polygon (RTSP). We

believe that the contribution of this work is threefold. Firstly, because AS is one of the earliest ACO

approaches proposed for TSP, the running-time analysis of AS is more significant than that of other

specially constructed ACO algorithms. Secondly, the considered RTSP is a real-world TSP which

has the constraint of triangle inequality, and thus the conducted running-time analysis of its solution

seems more meaningful than other works (Zhou, 2009; Kötzing et al., 2010; Nallaperuma, 2013)

which focus on a constructed unreal TSP instances (i.e., without considering the constraint of triangle

inequality). Finally, we derive a running-time upper bound which is determined by the pheromone

rate (defined in Subsection 3.1). Furthermore, we verify the results by calculating six RTSP instances.

The remaining parts of the paper are organized as follows. Section 2 provides a brief review of

relevant works on running-time analysis of ACO algorithms. Section 3 presents the overall framework

of the AS algorithm for TSP and the theoretical preparation for running-time analysis of AS. Section

4 introduces the derived running-time upper bounds of two AS variants (ant system and ant-cycle

system) for TSP. It also presents experimental results to verify the obtained theoretical results. Finally,

Section 5 draws conclusions.



The representative studies of theoretical foundation of ACO are briefly reviewed in two branches

(i.e., convergence proof and running-time analysis) as follows.

In the branch of convergence proof, researchers aim to reveal whether an ACO algorithm can

converge with the optimal solutions. Gutjahr (Gutjahr, 2000; Gutjahr, 2002; Gutjahr, 2003) proposed

the convergence judgment for a special ACO algorithm named graph-based ant-quantity system. Stüzle

and Dorigo (Stüzle & Dorigo, 2002) presented a convergence proof for a class of ACO algorithms,

which is similar to the analysis of non-heuristic algorithms. For the convergence analysis, some

researchers worked on basic probability models; others based their work on stochastic process models.

Badr and Fahmy (Badr & Rahmy, 2004) used the random branching model to study the convergence

of ant-density, ant-quantity and ant-cycle algorithms (Dorigo et al., 2006).

While these studies of convergence proof have indicated whether an ACO algorithm can find the

optimal solution with infinite iteration times, they have not yet revealed how fast the ACO algorithm

can converge. Therefore, in recent years, more and more research efforts have been devoted to the

other branch of ACO study, i.e., running-time analysis, which focuses on the analysis of convergence

speeds of ACO algorithms.

The other branch of research shows that much work has been done on the running-time analysis

of ACO algorithms for a variety of problems that have various levels of difficulty. The early work

mainly conducted the analysis with relatively easy problems such as pseudo-Boolean (Kötzing et al.,



Volume 8 • Issue 4 • October-December 2017

2012) and polynomial solvable problems (Witt, 2013; Sudholt & Thyssen, 2012). Neumann and Witt

(Neumann & Witt, 2009) conducted a running-time analysis of a simple ACO algorithm and inspected

the effect of evaporation factor. Hao (Hao et al., 2006) studied the complexity of a single-ant algorithm

that converges in a polynomial time. Later, Gutjahr (Gutjahr et al., 2008) presented running-time

analysis results of ant-quantity system (Dorigo, 1996) and graph-based ant-quantity system (Gutjahr,

2000). He (Gutjahr, 2007) also showed the competitiveness of a special ACO algorithm with (1+1)

EA in terms of running time on One-Max problem. Doerr et al. (Doerr & Johannsen, 2007; Doerr

et al., 2011) further investigated the pheromone update mechanism in the simple ACO algorithm

1-ANT, and showed how the exponential running-time bound rapidly decreases to a polynomial bound

for pseudo-Boolean functions. Gutjahr and Sebastiani (Gutjahr & Sebastiani, 2008) analyzed the

running-time of an ACO variant with the best-so-far reinforcement. Neumann et al. (2009) extended

the running-time analysis of ACO algorithms to unimodal functions and estimated first-hitting times

for pheromone borders by using non-homogeneous processes. The results above, however, cannot

be directly extended to other ACO algorithms for application because the algorithms analyzed were

designed for only toy problems (e.g. pseudo-Boolean problem) but not real-word problems.

Besides the running-time analysis of ACO algorithms, which are for the optimization of pseudo-

Boolean functions, some running-time results of ACO algorithms on polynomial solvable problems

have also been obtained. Neumann and Witt (2008) presented the running-time analysis of 1-Ant

ACO algorithm for the minimum spanning tree problem. Attiratanasunthron and Fakcharoenphol

(2008) obtained the polynomial running-time bounds of a multiple-ant ACO algorithm for the

single-destination shortest path problem on a directed acyclic graph. Peng et al. (2015) presented an

approximation ability of ACO algorithms on the TSP (1, 2) problem.

The main application of ACO algorithms lies in solving NP-complete combinatorial optimization

problems, for which very few running-time analysis results seem to be available in the ACO literature

(Kötzing et al., 2012; Sudholt & Thyssen, 2012). Huang and Hao (Huang et al., 2009) have found

that ant colony system algorithm (Dorigo, 1997) cannot converge in polynomial time (iteration) when

solving TSPs without the help of local searching. After that, Neumann et al. (Neumann & Sudholt,

1978; Neumann & Sudholt, 2009) studied the impact of local searching on the running-time of ACO

algorithms. Huang et al. (2009) proposed results on the relation between the running time of ACO and

pheromone trail variant by four case studies of the simplified ant-quantity system algorithms. Zhou

(2009) identified an upper bound of expected running-time of the 1-Ant ACO algorithm for complete

and incomplete construction TSPs. Kötzing et al. (Kötzing and Neumann et al., 2010; Kötzing and

Lehre et al., 2010; Kötzing et al., 2012) proposed several theoretical properties for the running time of

ACO for TSPs and minimum cut problems. Furthermore, the result of estimating distribution algorithm

(Chen et al., 2010) is also useful for the analysis of ACO. Later, Kötzing et al. (2012) improved Zhou

(2009)’s work on the running time of ACO for construction TSPs. For Euclidean TSP, Samadhi et

al. (2008) presented an enhanced ant colony optimization approach based on parameterized results

taking into account the number of inner points. Their work (Oliveto & Witt, 2008) indicates the

importance of the running-time analysis for practical problems like Euclidean TSP. Samadhi (2015)

presents new insights into bio-inspired algorithms and the TSP based on parameterized analysis. In

brief, most of the abovementioned results are applicable to only some constructed problems (the

special cases of non-Euclidean TSP (Zhou, 2009; Kötzing et al., 2010; Nallaperuma, 2013) and the

minimum cut problem (Kötzing et al., 2010)). In view of this, further work on running-time analysis

for more practical problems has been suggested (Oliveto & Witt, 2008; Paduch & Sapiecha, 2011).

The TSPs considered in (Zhou, 2009) are constructed cases of non-Euclidean geometries. In

the constructed TSP, the length of the edge between a vertex and its nearest vertex is 1 and others

are n (n>1). As a result, the TSP instances do not meet the constraint of triangle inequality and are

hard to find in reality. Different from the related work (Zhou, 2009; Kötzing et al., 2012) above, the

present study focuses on the RTSP which is a Euclidean TSP and more practical than that studied in

(Zhou, 2009). Moreover, we introduce the ant system algorithm (Dorigo et al. 1996) without the help

剩余16页未读，继续阅读

评论收藏

内容反馈

weixin_38702945

粉丝: 9
资源: 964

具有上限比较的蚂蚁系统算法的运行时分析

具有多个任务的蚂蚁系统的建模分析及其在空间邻近细胞状态估计中的应用

可运行的蚂蚁算法

数学建模MATLAB蚂蚁算法

用蚂蚁算法解决多旅行商问题

TSP -蚁群算法

C++蚁群算法的机器人路径规划

基于蚁群算法的路径规划.pdf

antc.rar_蚁群算法c++

旅行商问题的三种解法-神经网络、遗传算法和蚁群算法.pdf

蚁群算法-旅行商问题-人工智能-java-代码+报告+注释.docx

旅行销售员（算法 代码）

蚁群算法的代码

蚁群算法求解TSP问题matlab代码.zip

【蚁狮算法】基于柯西变异的蚁狮优化算法求解单目标优化问题matlab代码.zip

MATLAB实现智能优化算法.pdf

基于Agent和蚁群算法的分布式服务发现.pdf

基于改进蚁群算法的CVRP问题1

蚁群算法(C++版).doc

【路径规划】基于蚁群算法求解带举例约束的车辆路径问题（DVRP）matlab代码.zip

基本蚁群算法的c源程序.pdf

用蚁群算法求解类TSP问题的研究1

蚁群优化算法的理论研究进展

初学者蚁群Matlab程序.pdf

TSP.zip_TSP matlab_tsp

Ant-Based Routing Algorithm to Achieve the Lifetime Bound for Target Tracking Sensor Networks

混合启发式算法在汽车调度中的应用

数学建模中的旅行商问题

最新资源

旅行销售员（算法　代码）