# Applying Data Clustering Feature to Speed Up Ant Colony Optimization

Authors: Chao-Yang Pang; Ben-Qiong Hu; Jie Zhang; Wei Hu; Zheng-Chao Shan
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Ant colony optimization (ACO) is often used to solve optimization problems, such as traveling salesman problem (TSP). When it is applied to TSP, its runtime is proportional to the squared size of problemN so as to look less efficient. The following statistical feature is observed during the authors’ long-term gene data analysis using ACO: when the data size N becomes big, local clustering appears frequently. That is, some data cluster tightly in a small area and form a class, and the correlation between different classes is weak. And this feature makes the idea of divide and rule feasible for the estimate of solution of TSP. In this paper an improved ACO algorithm is presented, which firstly divided all data into local clusters and calculated small TSP routes and then assembled a big TSP route with them. Simulation shows that the presented method improves the running speed of ACO by 200 factors under the condition that data set holds feature of local clustering.


---

## Body

## 1. Introduction

### 1.1. Introduction of Ant Colony Optimization (ACO)

In 1991, ant colony optimization (ACO) was presented firstly by Colorni et al. [1] and applied to solve TSP firstly by Dorigo et al. [1–3]. Dorigo et al. created a new research topic which is studied by many scholars now.ACO is essentially a system based on agents that simulate the natural behavior of ants, in which real ants are able to find the shortest route from a food source to their nest, without using visual cues by exploiting pheromone information [2]. Pheromone is deposited when ants are walking on a route. It provides heuristic information for other ants to choose their routes. The more dense the pheromone trail of a route is, the more possibly the route is selected by ants. At last, nearly all ants select the route that has the most dense pheromone trail, and it is the shortest route potentially.ACO has been applied to solve optimization problems widely and successfully, such as TSP [1–4], quadratic assignment problem [5], image processing [6], data mining [7], classification or clustering analysis [8], and biology [9]. The application of ACO leads the theoretic study of ACO. Gutijahr firstly analyzes the convergence property of ACO [10]. Stutzle and Dorigo prove the important conclusion that if the running time of ACO is long enough, ACO can find optimal solution possibly [11]. The other interesting property is revealed currently by Birattari et al. that the sequence of solutions of some algorithms does not depend on the scale of problem instance [12].ACO is especially well suited for solving difficult optimization problems, where traditional optimization methods are less efficient. However, ACO is not very efficient in solving large problems because running time is too long and the quality of solution is still low. To solve the two main problems, the configuration of the parameters is discussed [2, 3]. To further improve ACO, many approaches have been proposed. Among these approaches, parallel computation and other methods are used to accelerate ACO [13]. In this study, we design a novel clustering algorithm named special local clustering algorithm (SLC), which is applied to classify and find the solution for TSP problem. Moreover, a colony of ants acts on each class to get a local TSP path. And we use the convergence of route length as termination criterion of ACO. The experimental results indicated that the improved ACO speeds up and its quality becomes higher for testing problems. It is more robust than comparative approaches.


### 1.2. Clustering Correlates to the Running Time of ACO

One of study focuses of ACO is to cut down running time. The running time of ACO isO(tmax⁡MN2), and M=[N/1.5] in general, where tmax⁡, M, and N denote the iteration number, number of ants, and number of cities, respectively [4]. The running time is proportional to N2. Cutting down the number of cities N is the key to reduce running time. Therefore, classifying all cities into different classes and letting ACO act on each class will reduce running time heavily. Hu and Huang used this method to improve the running speed of ACO [14], which is named ACO-K-Means. It is faster than ACO by factors of 5–15 approximately. Simulations show that ACO-K-Means algorithm is valid only to the set of cities that has evident clustering feature and invalid to more general situation. ACO-K-Means implies that using clustering method to improve the running speed of ACO is possible.


### 1.3. Introduction of Local Clustering Algorithm

Clustering is classifying objects of a set (named training set) into different clusters (or groups), so that the data in each class (ideally) share some common traits. One of the most popular clustering algorithms is K-Means clustering algorithm [15, 16]. K-Means clustering algorithm assigns each point to the cluster whose center (i.e., centroid) is nearest to it and then updates the centroid. Repeat this process until termination criterion is satisfied [16].During thetth iteration of K-Means algorithm, the ith class has distortion that is defined as the average distance of each point and the class centroid, which is denoted by Di(t) (1≤i≤m), where m is the number of classes. Pang proves that for each i the distortion sequence {Di(t)} is convergent if the ith class is separated from other classes evidently [16]. That is, distortion sequence is convergent locally. According to this property, an algorithm named local clustering algorithm (LC) is presented [17], and its essential idea is introduced as below.Step 1.
K-Means is applied to a given training set to generate classes.Step 2.
The class whose distortionDi(t) is convergent first is deleted from training set. Then, update training set such that it is comprised of residual points. Go to Step 1.Repeat the process of Steps1 and 2 until all data is classified.LC algorithm is faster than K-Means algorithm by factors of 4–13 approximately.Suppose that theith class is Ri(t) during the tth iteration of K-Means algorithm. Set Ri(t) has entropy H(Ri(t)), where H(Ri(t))=-∑a∈Ri(t)p(a)log⁡2⁡p(a) and p(a) is the probability of data a. It is proved that entropy sequence {H(Ri(0)),H(Ri(1)),…,H(Ri(t)),…} is convergent [16]. That is, the convergent criterion of K-Means algorithm can be replaced by the convergence of entropy sequence [18]. The K-Means with convergent criterion of entropy convergence is fast by factors of 2 at least [18, 19].


## 1.1. Introduction of Ant Colony Optimization (ACO)

In 1991, ant colony optimization (ACO) was presented firstly by Colorni et al. [1] and applied to solve TSP firstly by Dorigo et al. [1–3]. Dorigo et al. created a new research topic which is studied by many scholars now.ACO is essentially a system based on agents that simulate the natural behavior of ants, in which real ants are able to find the shortest route from a food source to their nest, without using visual cues by exploiting pheromone information [2]. Pheromone is deposited when ants are walking on a route. It provides heuristic information for other ants to choose their routes. The more dense the pheromone trail of a route is, the more possibly the route is selected by ants. At last, nearly all ants select the route that has the most dense pheromone trail, and it is the shortest route potentially.ACO has been applied to solve optimization problems widely and successfully, such as TSP [1–4], quadratic assignment problem [5], image processing [6], data mining [7], classification or clustering analysis [8], and biology [9]. The application of ACO leads the theoretic study of ACO. Gutijahr firstly analyzes the convergence property of ACO [10]. Stutzle and Dorigo prove the important conclusion that if the running time of ACO is long enough, ACO can find optimal solution possibly [11]. The other interesting property is revealed currently by Birattari et al. that the sequence of solutions of some algorithms does not depend on the scale of problem instance [12].ACO is especially well suited for solving difficult optimization problems, where traditional optimization methods are less efficient. However, ACO is not very efficient in solving large problems because running time is too long and the quality of solution is still low. To solve the two main problems, the configuration of the parameters is discussed [2, 3]. To further improve ACO, many approaches have been proposed. Among these approaches, parallel computation and other methods are used to accelerate ACO [13]. In this study, we design a novel clustering algorithm named special local clustering algorithm (SLC), which is applied to classify and find the solution for TSP problem. Moreover, a colony of ants acts on each class to get a local TSP path. And we use the convergence of route length as termination criterion of ACO. The experimental results indicated that the improved ACO speeds up and its quality becomes higher for testing problems. It is more robust than comparative approaches.


## 1.2. Clustering Correlates to the Running Time of ACO

One of study focuses of ACO is to cut down running time. The running time of ACO isO(tmax⁡MN2), and M=[N/1.5] in general, where tmax⁡, M, and N denote the iteration number, number of ants, and number of cities, respectively [4]. The running time is proportional to N2. Cutting down the number of cities N is the key to reduce running time. Therefore, classifying all cities into different classes and letting ACO act on each class will reduce running time heavily. Hu and Huang used this method to improve the running speed of ACO [14], which is named ACO-K-Means. It is faster than ACO by factors of 5–15 approximately. Simulations show that ACO-K-Means algorithm is valid only to the set of cities that has evident clustering feature and invalid to more general situation. ACO-K-Means implies that using clustering method to improve the running speed of ACO is possible.


## 1.3. Introduction of Local Clustering Algorithm

Clustering is classifying objects of a set (named training set) into different clusters (or groups), so that the data in each class (ideally) share some common traits. One of the most popular clustering algorithms is K-Means clustering algorithm [15, 16]. K-Means clustering algorithm assigns each point to the cluster whose center (i.e., centroid) is nearest to it and then updates the centroid. Repeat this process until termination criterion is satisfied [16].During thetth iteration of K-Means algorithm, the ith class has distortion that is defined as the average distance of each point and the class centroid, which is denoted by Di(t) (1≤i≤m), where m is the number of classes. Pang proves that for each i the distortion sequence {Di(t)} is convergent if the ith class is separated from other classes evidently [16]. That is, distortion sequence is convergent locally. According to this property, an algorithm named local clustering algorithm (LC) is presented [17], and its essential idea is introduced as below.Step 1.
K-Means is applied to a given training set to generate classes.Step 2.
The class whose distortionDi(t) is convergent first is deleted from training set. Then, update training set such that it is comprised of residual points. Go to Step 1.Repeat the process of Steps1 and 2 until all data is classified.LC algorithm is faster than K-Means algorithm by factors of 4–13 approximately.Suppose that theith class is Ri(t) during the tth iteration of K-Means algorithm. Set Ri(t) has entropy H(Ri(t)), where H(Ri(t))=-∑a∈Ri(t)p(a)log⁡2⁡p(a) and p(a) is the probability of data a. It is proved that entropy sequence {H(Ri(0)),H(Ri(1)),…,H(Ri(t)),…} is convergent [16]. That is, the convergent criterion of K-Means algorithm can be replaced by the convergence of entropy sequence [18]. The K-Means with convergent criterion of entropy convergence is fast by factors of 2 at least [18, 19].


## 2. Improve Local Clustering Algorithm to Generate Compact Class

### 2.1. Compact Set and the Method of Generation

For any subset of Euclidean spaceRn, every sequence in this subset has a convergent subsequence, the limit point of which belongs to the set. This subset is calledcompact set. The conception of compact set (or compactness) is a topology conception. To understand it easily, compactness can be described visually as the phenomenon where many points cluster tightly in a small region, while noncompact set is the set of which most of points cluster loosely in a big region.K-Means clustering, LC, or other algorithms aim to partition a training set into classes. Some classes are compact and some are not. The most common situation is that a class contains a compact subset and some loose points, and points of the compact subset are around the center of the class. That is, the central part of class is compact possibly. To extract compact subset from a class, the following3δ-principle is introduced.For Gauss distribution, suppose thatδ denotes the deviation of random data. It is the 3δ-principle that there is more than 99% probability that a random point falls into the central region of data set whose radius is 3δ [16]. The central region contains more than 99% points. Thus, if radius 3δ is small enough and the number of points is big enough, the central region is compact. If the central region with radius 3δ is not compact, shortening the radius of central region to 3δ/4, 3δ/16, and so on will make it compact. For Gauss distribution which is comprised of enough points, the compact central region always exists. In general, for a class generated by clustering algorithm, all distances of points from class centroid comprise a similar gauss distribution. Therefore, the central region of a class is compact possibly.Suppose that theith class is Ri(t) at the tth iteration of K-Means or LC algorithm. With the increase of iteration, class sequence {Ri(0),Ri(1),…,Ri(t),Ri(t+1),…} (1≤i≤m) appears, where m denotes the number of classes. Let
(1)Di(t)=1|Ri(t)|∑x∈Ri(t)d(x,ci(t)),
where |Ri(t)| denotes the number of elements in Ri(t) and d(x,ci(t)) denotes distance.Consider(2)δi(t)=1|Ri(t)|∑x∈Ri(t)|d(x,ci(t))-Dit|.Clearly,Di(t) is the distortion of class Ri(t) and δi(t) is the approximation of deviation of Di(t).Consider(3)Ki(t)={x∣d(x,ci(t))≤14p(Di(t)+3δi(t)),gggx∈Ri(t)(p≥0)14p}.K
i
(
t
) is the central region of class Ri(t). Parameter p is used to shorten the radius of central region Ki(t) and makes it compact. Figure 1 illustrates the 3δ-principle and compact subset Ki(t).Figure 1
The illustration of compact central region of a class. In a classRi(t), most of points cluster around their centroid and few points are far away from the centroid. Subset Ki(t) (i.e., the shadow part) is the central region of class Ri(t). Compact set is the set where many points cluster in a small region tightly. Increasing parameter p will shorten radius and make Ki(t) compact.


### 2.2. Subroutine 1: Local Clustering Algorithm with3δ-Principle

The local clustering algorithm with3δ-principle is used to classify points into classes and to extract compact central region of classes. Its essential idea is described as below.Firstly, apply LC algorithm to cluster data. And apply the criterion of entropy convergence (i.e.,|H(Ri(t))-H(Ri+1(t+1))|/H(Ri(t))→0) to mark the stable class Ri(t).Secondly, extract compact central regionKi(t) from class Ri(t) and preserve it as a genuine class. Remove Ri(t) from training set and update it. Repeat the above two steps until all compact central regions are extracted. The details are described in Algorithm 1.Algorithm 1
Input parameters:
T: Training Set
m: The number of classes
ε: The stop threshold for clustering.
C
(
0
)
=
{
c
i
0
(
1
≤
i
≤
m
)
}: Initial centroids set.
p: A parameter to adjust the size of compact subs-ets Ki(t)(p≥0).
Output:
φ
(
T
)
=
{
K
1
(
t
)
,
K
2
(
t
)
,
…
,
K
i
(
t
)
,
…
,
K
m
(
t
)
} (i.e., the set of co-mpact subset, see Figure 1)
σ
(
T
)
=
{
B
1
(
t
)
,
B
2
(
t
)
,
…
,
B
i
(
t
)
,
…
,
B
m
(
t
)
}, where Bi(t)=Ri(t)-Ki(t), and it is comprised by dispersive points
(1≤i≤m, see Figure 1)
Void Subroutine  1  (T,m,ε,C(0),p,φ(T),σ(T))
{
Step  1. Initialization: Let iteration number t=0. Let Counter=m. Let φ(T)=ϕ and σ(T)=ϕ, where ϕ
denotes empty set. According to initial centroids setC(0), generate initial partition of training set
φ
0
=
{
R
i
0
∣
R
i
0
⊂
T
,
1
≤
i
≤
m
}.
Step  2. While (Counter>0){
Step  2.1. Generate new centroids set  C(t+1)={ci(t+1)∣1≤i≤m} and new partition φ(t+1)={Ri(t+1)∣1≤i≤m}
/* Note: Check whether entropy sequence {Hi(0),Hi(1),…,Hi(t),Hi(t+1),…} is convergent. If it is convergent,
let the convergent marker StableMarker(Ri(t+1))=True */
Step  2.2. For (i=1;i≤Counter;i++){
Estimate the entropy of class Ri(t+1), that is, H(Ri(t+1))=log2⁡|Ri(t+1)|.
If (|H(Ri(t))-H(Ri(t+1))|H(Ri(t))<ε){StableMarker(Ri(t+1))=True;}
Else {StableMarker(Ri(t+1))=False}
}
/* Note: Extract the data around the centroid of class as a genuine class */
Step  2.3. For (i=1;i≤Counter;i++){
If (StableMarker(Ri(t+1))=True){
Calculate compact central region Ki(t) according to formula (3)
Calculate Bi(t): Bi(t)=Ri(t+1)-Ki(t)
Let φ(T)=φ(T)∪Ki(t)
Let σ(T)=σ(T)∪Bi(t)
Update Training Set: T=T-Ri(t)
Update centroids set: C(t+1)=C(t+1)-{ci(t+1)}
Counter=Counter-1
}
}
t
=
t
+
1
}
}


### 2.3. Special LC Algorithm to Generate Compact Classes (SLC)

Note that above subroutine 1 is not a partition of training set. Subroutine 1 extracts only compact central regions of all classes and the residual points are unclassified. The residual points comprise a new training set. And it is possible that some of residual points cluster together tightly and comprise some small compact subsets again. These small compact subsets are new classes. To obtain these new classes and classify all points, SLC algorithm is described in Algorithm2.Algorithm 2
Input parameters:
T
0: Training Set
m
0: The initial number of classes.
ε: The stop threshold for clustering.
Output:
Num: The final number of classes.
CLS: The partition ofT0, in which each class is com-pact.
SLC Algorithm:
Step  1. Initialization: Let  T=T0,  m=m0,  CLS=ϕ, and  p=0.
Step  2. For (i=0;i<[log2⁡m];i++) /*Note:  [log2⁡m] denotes the integer */
{
Step  2.1. Generate initial centroids set  C0={ci(0)∣1≤i≤m}.
Step  2.2. Call Subroutine1 (T,m,C(0),ε,p,φ(T),σ(T))
Step  2.3.  CLS=CLS∪φ(T);
Step  2.4.T=σ(T);
/* Note: Increasep to get smaller compact class */
Step  2.5.  m=[m2];  p=p+1
}
Step  3. Every residual point x in the last set  σ(T)  is regarded as a class  {x}. And let  CLS=CLS∪{x}.
Let  Num  denote the number of classes contained in  CLS. The two outputs are  CLS  andNum.


### 2.4. The Clustering for Mixture Distribution (SLC-Mixture)

The clustering algorithm SLC presented above generates spherical classes only. However, for a general distribution, some classes are of spherical shape, some classes are of chain shape in which points cluster closely around a curve (or a line), and some classes contain isolated points. This common distribution is called mixture distribution. For a large-scale TSP, the distribution of cities is mixture distribution in general. The clustering method for mixture distribution is proposed as below.


#### 2.4.1. The Simple Maker to Distinguish Spherical Class from Chain-Shaped Class

The position of city on a map is two-dimensional point. A given class can be divided into 8 areas along the 4 directions of the north-south and west-east and two diagonal lines through the centroid of the class. If the class is spherical, the percentage of points in each area is close to 1/8 and is the same approximately. If the class is chain-shaped class (or part of chain-shaped class), it is impossible that the percentage of every area is close to 1/8 at the same time. Therefore, the percentage of points in each area is the maker of spherical class. Figure2 illustrates the marker.The illustration of distinguishing spherical class from chain-shaped class. A given class is divided into 8 parts along the 8 lines through the centroid of the class. If the class is spherical, the percentage of each part is close to thresholdε=1/8. If the class is chain-shaped class (or part of chain-shaped class), there are 2–4 parts whose percentage is far less than 1/8. Therefore, the percentage of each part is the marker of spherical class. ε=0.058 in this paper because some classes are elliptical.
(a)
(b)


#### 2.4.2. Applying SLC to Process Mixture Distribution (SLC-Mixture)

At first, apply SLC to classify all data of training set. Secondly, apply the marker presented above to distinguish spherical classes and extract them from the training set. Then all residual points comprise a new set named residual set. The residual set contains only chain-shaped classes and isolated points. Thirdly, apply the method presented in [20] to classify all residual points of residual set into different chain-shaped classes or marked as isolated points. The method presented in [20] is named chain-shaped clustering algorithm.The clustering method presented in this section is called SLC-Mixture algorithm, which processes the mixture distribution of spherical classes, chain-shaped classes, and isolated points.


## 2.1. Compact Set and the Method of Generation

For any subset of Euclidean spaceRn, every sequence in this subset has a convergent subsequence, the limit point of which belongs to the set. This subset is calledcompact set. The conception of compact set (or compactness) is a topology conception. To understand it easily, compactness can be described visually as the phenomenon where many points cluster tightly in a small region, while noncompact set is the set of which most of points cluster loosely in a big region.K-Means clustering, LC, or other algorithms aim to partition a training set into classes. Some classes are compact and some are not. The most common situation is that a class contains a compact subset and some loose points, and points of the compact subset are around the center of the class. That is, the central part of class is compact possibly. To extract compact subset from a class, the following3δ-principle is introduced.For Gauss distribution, suppose thatδ denotes the deviation of random data. It is the 3δ-principle that there is more than 99% probability that a random point falls into the central region of data set whose radius is 3δ [16]. The central region contains more than 99% points. Thus, if radius 3δ is small enough and the number of points is big enough, the central region is compact. If the central region with radius 3δ is not compact, shortening the radius of central region to 3δ/4, 3δ/16, and so on will make it compact. For Gauss distribution which is comprised of enough points, the compact central region always exists. In general, for a class generated by clustering algorithm, all distances of points from class centroid comprise a similar gauss distribution. Therefore, the central region of a class is compact possibly.Suppose that theith class is Ri(t) at the tth iteration of K-Means or LC algorithm. With the increase of iteration, class sequence {Ri(0),Ri(1),…,Ri(t),Ri(t+1),…} (1≤i≤m) appears, where m denotes the number of classes. Let
(1)Di(t)=1|Ri(t)|∑x∈Ri(t)d(x,ci(t)),
where |Ri(t)| denotes the number of elements in Ri(t) and d(x,ci(t)) denotes distance.Consider(2)δi(t)=1|Ri(t)|∑x∈Ri(t)|d(x,ci(t))-Dit|.Clearly,Di(t) is the distortion of class Ri(t) and δi(t) is the approximation of deviation of Di(t).Consider(3)Ki(t)={x∣d(x,ci(t))≤14p(Di(t)+3δi(t)),gggx∈Ri(t)(p≥0)14p}.K
i
(
t
) is the central region of class Ri(t). Parameter p is used to shorten the radius of central region Ki(t) and makes it compact. Figure 1 illustrates the 3δ-principle and compact subset Ki(t).Figure 1
The illustration of compact central region of a class. In a classRi(t), most of points cluster around their centroid and few points are far away from the centroid. Subset Ki(t) (i.e., the shadow part) is the central region of class Ri(t). Compact set is the set where many points cluster in a small region tightly. Increasing parameter p will shorten radius and make Ki(t) compact.


## 2.2. Subroutine 1: Local Clustering Algorithm with3δ-Principle

The local clustering algorithm with3δ-principle is used to classify points into classes and to extract compact central region of classes. Its essential idea is described as below.Firstly, apply LC algorithm to cluster data. And apply the criterion of entropy convergence (i.e.,|H(Ri(t))-H(Ri+1(t+1))|/H(Ri(t))→0) to mark the stable class Ri(t).Secondly, extract compact central regionKi(t) from class Ri(t) and preserve it as a genuine class. Remove Ri(t) from training set and update it. Repeat the above two steps until all compact central regions are extracted. The details are described in Algorithm 1.Algorithm 1
Input parameters:
T: Training Set
m: The number of classes
ε: The stop threshold for clustering.
C
(
0
)
=
{
c
i
0
(
1
≤
i
≤
m
)
}: Initial centroids set.
p: A parameter to adjust the size of compact subs-ets Ki(t)(p≥0).
Output:
φ
(
T
)
=
{
K
1
(
t
)
,
K
2
(
t
)
,
…
,
K
i
(
t
)
,
…
,
K
m
(
t
)
} (i.e., the set of co-mpact subset, see Figure 1)
σ
(
T
)
=
{
B
1
(
t
)
,
B
2
(
t
)
,
…
,
B
i
(
t
)
,
…
,
B
m
(
t
)
}, where Bi(t)=Ri(t)-Ki(t), and it is comprised by dispersive points
(1≤i≤m, see Figure 1)
Void Subroutine  1  (T,m,ε,C(0),p,φ(T),σ(T))
{
Step  1. Initialization: Let iteration number t=0. Let Counter=m. Let φ(T)=ϕ and σ(T)=ϕ, where ϕ
denotes empty set. According to initial centroids setC(0), generate initial partition of training set
φ
0
=
{
R
i
0
∣
R
i
0
⊂
T
,
1
≤
i
≤
m
}.
Step  2. While (Counter>0){
Step  2.1. Generate new centroids set  C(t+1)={ci(t+1)∣1≤i≤m} and new partition φ(t+1)={Ri(t+1)∣1≤i≤m}
/* Note: Check whether entropy sequence {Hi(0),Hi(1),…,Hi(t),Hi(t+1),…} is convergent. If it is convergent,
let the convergent marker StableMarker(Ri(t+1))=True */
Step  2.2. For (i=1;i≤Counter;i++){
Estimate the entropy of class Ri(t+1), that is, H(Ri(t+1))=log2⁡|Ri(t+1)|.
If (|H(Ri(t))-H(Ri(t+1))|H(Ri(t))<ε){StableMarker(Ri(t+1))=True;}
Else {StableMarker(Ri(t+1))=False}
}
/* Note: Extract the data around the centroid of class as a genuine class */
Step  2.3. For (i=1;i≤Counter;i++){
If (StableMarker(Ri(t+1))=True){
Calculate compact central region Ki(t) according to formula (3)
Calculate Bi(t): Bi(t)=Ri(t+1)-Ki(t)
Let φ(T)=φ(T)∪Ki(t)
Let σ(T)=σ(T)∪Bi(t)
Update Training Set: T=T-Ri(t)
Update centroids set: C(t+1)=C(t+1)-{ci(t+1)}
Counter=Counter-1
}
}
t
=
t
+
1
}
}


## 2.3. Special LC Algorithm to Generate Compact Classes (SLC)

Note that above subroutine 1 is not a partition of training set. Subroutine 1 extracts only compact central regions of all classes and the residual points are unclassified. The residual points comprise a new training set. And it is possible that some of residual points cluster together tightly and comprise some small compact subsets again. These small compact subsets are new classes. To obtain these new classes and classify all points, SLC algorithm is described in Algorithm2.Algorithm 2
Input parameters:
T
0: Training Set
m
0: The initial number of classes.
ε: The stop threshold for clustering.
Output:
Num: The final number of classes.
CLS: The partition ofT0, in which each class is com-pact.
SLC Algorithm:
Step  1. Initialization: Let  T=T0,  m=m0,  CLS=ϕ, and  p=0.
Step  2. For (i=0;i<[log2⁡m];i++) /*Note:  [log2⁡m] denotes the integer */
{
Step  2.1. Generate initial centroids set  C0={ci(0)∣1≤i≤m}.
Step  2.2. Call Subroutine1 (T,m,C(0),ε,p,φ(T),σ(T))
Step  2.3.  CLS=CLS∪φ(T);
Step  2.4.T=σ(T);
/* Note: Increasep to get smaller compact class */
Step  2.5.  m=[m2];  p=p+1
}
Step  3. Every residual point x in the last set  σ(T)  is regarded as a class  {x}. And let  CLS=CLS∪{x}.
Let  Num  denote the number of classes contained in  CLS. The two outputs are  CLS  andNum.


## 2.4. The Clustering for Mixture Distribution (SLC-Mixture)

The clustering algorithm SLC presented above generates spherical classes only. However, for a general distribution, some classes are of spherical shape, some classes are of chain shape in which points cluster closely around a curve (or a line), and some classes contain isolated points. This common distribution is called mixture distribution. For a large-scale TSP, the distribution of cities is mixture distribution in general. The clustering method for mixture distribution is proposed as below.


### 2.4.1. The Simple Maker to Distinguish Spherical Class from Chain-Shaped Class

The position of city on a map is two-dimensional point. A given class can be divided into 8 areas along the 4 directions of the north-south and west-east and two diagonal lines through the centroid of the class. If the class is spherical, the percentage of points in each area is close to 1/8 and is the same approximately. If the class is chain-shaped class (or part of chain-shaped class), it is impossible that the percentage of every area is close to 1/8 at the same time. Therefore, the percentage of points in each area is the maker of spherical class. Figure2 illustrates the marker.The illustration of distinguishing spherical class from chain-shaped class. A given class is divided into 8 parts along the 8 lines through the centroid of the class. If the class is spherical, the percentage of each part is close to thresholdε=1/8. If the class is chain-shaped class (or part of chain-shaped class), there are 2–4 parts whose percentage is far less than 1/8. Therefore, the percentage of each part is the marker of spherical class. ε=0.058 in this paper because some classes are elliptical.
(a)
(b)


### 2.4.2. Applying SLC to Process Mixture Distribution (SLC-Mixture)

At first, apply SLC to classify all data of training set. Secondly, apply the marker presented above to distinguish spherical classes and extract them from the training set. Then all residual points comprise a new set named residual set. The residual set contains only chain-shaped classes and isolated points. Thirdly, apply the method presented in [20] to classify all residual points of residual set into different chain-shaped classes or marked as isolated points. The method presented in [20] is named chain-shaped clustering algorithm.The clustering method presented in this section is called SLC-Mixture algorithm, which processes the mixture distribution of spherical classes, chain-shaped classes, and isolated points.


## 2.4.1. The Simple Maker to Distinguish Spherical Class from Chain-Shaped Class

The position of city on a map is two-dimensional point. A given class can be divided into 8 areas along the 4 directions of the north-south and west-east and two diagonal lines through the centroid of the class. If the class is spherical, the percentage of points in each area is close to 1/8 and is the same approximately. If the class is chain-shaped class (or part of chain-shaped class), it is impossible that the percentage of every area is close to 1/8 at the same time. Therefore, the percentage of points in each area is the maker of spherical class. Figure2 illustrates the marker.The illustration of distinguishing spherical class from chain-shaped class. A given class is divided into 8 parts along the 8 lines through the centroid of the class. If the class is spherical, the percentage of each part is close to thresholdε=1/8. If the class is chain-shaped class (or part of chain-shaped class), there are 2–4 parts whose percentage is far less than 1/8. Therefore, the percentage of each part is the marker of spherical class. ε=0.058 in this paper because some classes are elliptical.
(a)
(b)


## 2.4.2. Applying SLC to Process Mixture Distribution (SLC-Mixture)

At first, apply SLC to classify all data of training set. Secondly, apply the marker presented above to distinguish spherical classes and extract them from the training set. Then all residual points comprise a new set named residual set. The residual set contains only chain-shaped classes and isolated points. Thirdly, apply the method presented in [20] to classify all residual points of residual set into different chain-shaped classes or marked as isolated points. The method presented in [20] is named chain-shaped clustering algorithm.The clustering method presented in this section is called SLC-Mixture algorithm, which processes the mixture distribution of spherical classes, chain-shaped classes, and isolated points.


## 3. Apply SLC to ACO

### 3.1. The Termination Criterion of ACO

Suppose ACO acts on a compact class and letLt denote the minimum route length that is generated at the tth iteration of computation. There is sequence {L1,L2,…,Lt,Lt+1,…} and it is convergent under ideal condition. The convergent criterion |Lt-Lt+1|/Lt≤ε is proposed as the termination criterion of ACO in this paper.In the following discussion, ACO refers to the algorithm whose termination criterion is(|Lt-Lt+1|/Lt)≤ε.


### 3.2. Apply SLC to Improve the Running Speed of ACO (ACO-SLC)

In this section, the clustering algorithm SLC will be applied to improve the running speed of ACO. The method is named ACO-SLC and it is described as below.Input parameter:T: set of cities.Output: the shortest TSP route obtained by the algorithm.ACO-SLC Algorithm.Step 1.
Apply SLC algorithm to partition setT. The classes are B1,B2,…,Bi,…, and BNum, and their centroids are b1,b2,…,bi,…, and bNum, respectively.Step 2.
Construct graphG′: centroids b1,b2,…,bi,…, and bNum are regarded as virtual cities, respectively, and the virtual cities are regarded as the vertices of graph G′. For a pair of classes Bi and Bj, if there exist two cities that belong to Bi and Bj, respectively, and they join each other, use an edge to join the two corresponding vertices bi and bj. The weight of edge is the minimum distance between two classes; that is,
(4)d(Bi,Bj)=min⁡{d(xi,xj)∣xi∈Bi,xj∈Bj}.Step 3.
Calculate a TSP route of graphG′ to generate the traveling order of all classes: let ACO algorithm act on graph G′ to find a TSP route denoted by bj1,bj2,…bjNum, where j1,j2,…jNum, is a permutation of sequence 1,2,…Num. The pair of classes Bji and Bj(i+1) is called neighbor class.Step 4.
Choose an edge as the bridge to join a pair of neighbor classes, and this edge is named bridge edge. Assume that the two neighbor classes areBj1 and Bj2. If there exists an edge such that
(5)d(xu,xv)=min⁡{d(a,b)∣a∈Bj1,b∈Bj2},
edge (xu,xv) is the bridge edge, xu and xv are called border cities, where vertices a and b should be not used to join other neighbor classes.Step 5.
Calculate a local TSP route for every classBi (1≤i≤Num): add a new edge to join the two border cities in the class and mark the edge as necessary edge of the local TSP route. This edge is named pseudoedge. Let the ACO algorithm with convergence criterion (|Lt-Lt+1|/Lt)≤ε act on the class to generate a local TSP route.Step 6.
Construct a TSP route: walk along the traveling order obtained at Step3; for every pair of neighbor classes, delete the pseudoedge of each class such that the local route is not close. Then let the local route of each class and the bridge edge between these two classes be joined.Figure3 illustrates the processing of ACO-SLC algorithm.Figure 3
The schematic diagram of ACO-SLC. Firstly, classify all points into compact classes. Secondly, the centroid of each class is regarded as a virtual city; calculate a virtual TSP route. Then along the virtual route, join all classes. Thirdly, let ACO act on each class to get a local TSP route. Fourthly, join all local TSP routes along the virtual route to form the last route.


### 3.3. Using the Method of Little-Window and Removing Cross-Edge to Improve ACO-SLC (ACO-SLC-LWCR)

Clustering may cause the error of solution although it improves the running speed of ACO heavily. If all classes are compact and separated clearly, the quality of solution of ACO-SLC should be very good. However, in fact, the border between two neighbor classes is fuzzy. The fuzzy border will cause the inaccuracy of solution, and much longer route will appear. And recognizing the longer part and removing it will generate better solution possibly. It is well known that the shortest route is always at the surface of a convex hull. Thus, the longer part should be at the inner of a convex hull and two longer edges intersect. In other words, intersection of two edges is a marker of longer part of a route possibly. According to the marker, removing longer edges is calledremoving cross-edge orremoving intersection edges, which is similar to the method in [4]. (Notice: in [4], before executing ACO, the long and crossed edges are removed to improve the running speed of ACO, not to improve the solution quality.)Figure4 illustrates the method of removing cross-edge.Figure 4
The schematic diagram of ACO-SLC. Firstly, classify all points into compact classes. Secondly, the centroid of each class is regarded as a virtual city. And calculate a virtual TSP route. Then along the virtual route, join all classes. Thirdly, let ACO act on each class to get a local TSP route. Fourthly, join all local TSP routes along the virtual route to form the last route. The illustration of removing cross-edges from TSP route: at the left figure, AB and CD intersect each other. There is a principle that the shortest route is at the surface of a convex hull. Thus, edges AB and CD are the longer part of route and should be removed. Removing these two edges will generate shorter route (see right figure).In addition, a simple method namedlittle-window strategy is proposed to improve the running speed of ACO in [21]. Construct a set Si that is comprised by w accessible and short edges which join the ith city, where w is a preassigned constant. The ant which has arrived at ith city will select an edge from window set Si only to arrive at its next city and not select an edge from all neighbor edges of this vertex. So, this method improves the running speed of ACO.The ACO-SLC with little-window strategy and cross-edges removing is calledACO-SLC-LWCR.


### 3.4. The ACO-SLC for Mixture Distribution (ACO-SLC-Mixture)

ACO-SLC is suitable for the spherical shape distribution only, and the low quality of solution will appear possibly when ACO-SLC is applied to process mixture distribution. To process mixture distribution, the following method named ACO-SLC-Mixture is proposed in this paper.Firstly, apply SLC-Mixture at Section2.4.2 to partition the set of cities into spherical classes, chain-shaped classes, or isolated points. Secondly, apply ACO-SL-C-LWCR to each class and generate a TSP route.


## 3.1. The Termination Criterion of ACO

Suppose ACO acts on a compact class and letLt denote the minimum route length that is generated at the tth iteration of computation. There is sequence {L1,L2,…,Lt,Lt+1,…} and it is convergent under ideal condition. The convergent criterion |Lt-Lt+1|/Lt≤ε is proposed as the termination criterion of ACO in this paper.In the following discussion, ACO refers to the algorithm whose termination criterion is(|Lt-Lt+1|/Lt)≤ε.


## 3.2. Apply SLC to Improve the Running Speed of ACO (ACO-SLC)

In this section, the clustering algorithm SLC will be applied to improve the running speed of ACO. The method is named ACO-SLC and it is described as below.Input parameter:T: set of cities.Output: the shortest TSP route obtained by the algorithm.ACO-SLC Algorithm.Step 1.
Apply SLC algorithm to partition setT. The classes are B1,B2,…,Bi,…, and BNum, and their centroids are b1,b2,…,bi,…, and bNum, respectively.Step 2.
Construct graphG′: centroids b1,b2,…,bi,…, and bNum are regarded as virtual cities, respectively, and the virtual cities are regarded as the vertices of graph G′. For a pair of classes Bi and Bj, if there exist two cities that belong to Bi and Bj, respectively, and they join each other, use an edge to join the two corresponding vertices bi and bj. The weight of edge is the minimum distance between two classes; that is,
(4)d(Bi,Bj)=min⁡{d(xi,xj)∣xi∈Bi,xj∈Bj}.Step 3.
Calculate a TSP route of graphG′ to generate the traveling order of all classes: let ACO algorithm act on graph G′ to find a TSP route denoted by bj1,bj2,…bjNum, where j1,j2,…jNum, is a permutation of sequence 1,2,…Num. The pair of classes Bji and Bj(i+1) is called neighbor class.Step 4.
Choose an edge as the bridge to join a pair of neighbor classes, and this edge is named bridge edge. Assume that the two neighbor classes areBj1 and Bj2. If there exists an edge such that
(5)d(xu,xv)=min⁡{d(a,b)∣a∈Bj1,b∈Bj2},
edge (xu,xv) is the bridge edge, xu and xv are called border cities, where vertices a and b should be not used to join other neighbor classes.Step 5.
Calculate a local TSP route for every classBi (1≤i≤Num): add a new edge to join the two border cities in the class and mark the edge as necessary edge of the local TSP route. This edge is named pseudoedge. Let the ACO algorithm with convergence criterion (|Lt-Lt+1|/Lt)≤ε act on the class to generate a local TSP route.Step 6.
Construct a TSP route: walk along the traveling order obtained at Step3; for every pair of neighbor classes, delete the pseudoedge of each class such that the local route is not close. Then let the local route of each class and the bridge edge between these two classes be joined.Figure3 illustrates the processing of ACO-SLC algorithm.Figure 3
The schematic diagram of ACO-SLC. Firstly, classify all points into compact classes. Secondly, the centroid of each class is regarded as a virtual city; calculate a virtual TSP route. Then along the virtual route, join all classes. Thirdly, let ACO act on each class to get a local TSP route. Fourthly, join all local TSP routes along the virtual route to form the last route.


## 3.3. Using the Method of Little-Window and Removing Cross-Edge to Improve ACO-SLC (ACO-SLC-LWCR)

Clustering may cause the error of solution although it improves the running speed of ACO heavily. If all classes are compact and separated clearly, the quality of solution of ACO-SLC should be very good. However, in fact, the border between two neighbor classes is fuzzy. The fuzzy border will cause the inaccuracy of solution, and much longer route will appear. And recognizing the longer part and removing it will generate better solution possibly. It is well known that the shortest route is always at the surface of a convex hull. Thus, the longer part should be at the inner of a convex hull and two longer edges intersect. In other words, intersection of two edges is a marker of longer part of a route possibly. According to the marker, removing longer edges is calledremoving cross-edge orremoving intersection edges, which is similar to the method in [4]. (Notice: in [4], before executing ACO, the long and crossed edges are removed to improve the running speed of ACO, not to improve the solution quality.)Figure4 illustrates the method of removing cross-edge.Figure 4
The schematic diagram of ACO-SLC. Firstly, classify all points into compact classes. Secondly, the centroid of each class is regarded as a virtual city. And calculate a virtual TSP route. Then along the virtual route, join all classes. Thirdly, let ACO act on each class to get a local TSP route. Fourthly, join all local TSP routes along the virtual route to form the last route. The illustration of removing cross-edges from TSP route: at the left figure, AB and CD intersect each other. There is a principle that the shortest route is at the surface of a convex hull. Thus, edges AB and CD are the longer part of route and should be removed. Removing these two edges will generate shorter route (see right figure).In addition, a simple method namedlittle-window strategy is proposed to improve the running speed of ACO in [21]. Construct a set Si that is comprised by w accessible and short edges which join the ith city, where w is a preassigned constant. The ant which has arrived at ith city will select an edge from window set Si only to arrive at its next city and not select an edge from all neighbor edges of this vertex. So, this method improves the running speed of ACO.The ACO-SLC with little-window strategy and cross-edges removing is calledACO-SLC-LWCR.


## 3.4. The ACO-SLC for Mixture Distribution (ACO-SLC-Mixture)

ACO-SLC is suitable for the spherical shape distribution only, and the low quality of solution will appear possibly when ACO-SLC is applied to process mixture distribution. To process mixture distribution, the following method named ACO-SLC-Mixture is proposed in this paper.Firstly, apply SLC-Mixture at Section2.4.2 to partition the set of cities into spherical classes, chain-shaped classes, or isolated points. Secondly, apply ACO-SL-C-LWCR to each class and generate a TSP route.


## 4. Simulation

In this section, five related algorithms ACO, ACO-K-Means, ACO-SLC, ACO-SLC-LWCR, and ACO-SLC-Mixture are tested and compared. In the following simulation, ACO refers to ant-cycle presented by Colorni et al., which is very typical [1].All test data in this paper is downloaded fromhttp://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/. All algorithms in this paper run on personal computer (CPU: 1.80 GHz; memory: 480 M; software: Matlab). The parameters are listed as below. Initialize pheromone trails τij(0)=1, iteration number 1000, ε=0.001, α=1, β=10, ρ=0.4, Q=300, and m=[N/1.5]. Two performance items are tested. One item is the running time, which is defined asRatio =Time (ACO)/Time (Algorithm). The bigger the ratio is, the faster the algorithm is. In addition, the advantage of the ratio is that the subtle infection of other processes to runtime is evaded as possible, and it is more accurate than raw measured runtime because the value caused by other processes gives little contribution to the ratio. The other item is the quality of solution, which is defined as the percentage of errorError =(Solution-Optimum)/Optimum, whereOptimum denotes the best solution known currently. The smaller the error is, the better the quality of solution is.The performances of the five algorithms are listed in Figure5. It shows that ACO-SLC, ACO-SLC-LWCR, and ACO-SLC-Mixture are faster than ACO by 415~10736, 390~10192, and 257–9419 of factors, respectively! However, some solutions of ACO-K-Means and ACO-SLC have low quality. The inaccuracy ratio of ACO-SLC-Mixture is less than ACO in most cases and is bigger than ACO by 2% at most.Figure 5
The performance comparison with five algorithms. The figure shows that ACO-SLC algorithm, ACO-SLC, ACO-SLC-LWCR, and ACO-SLC-Mixture are faster than ACO by415~10736, 390~10192, and 257–9419 of factors, respectively! However, some solutions of ACO-K-Means and ACO-SLC have low quality. ACO-SLC-Mixture can process mixture distribution and its inaccuracy ratio is less than ACO in most cases and is bigger than ACO by 2% at most. It should be noted that under the condition where the data set holds feature of local clustering significantly, the quality of solution is good.The Defect of ACO-SLC.
(
1
) From Figure 5, it should be noted that only under the condition that the data set holds feature of local clustering significantly, the quality of solution is good. (2) The simulations of this paper show that the quality of ACO-SLC solution depends on the quality of clustering and clustering quality of SLC is sensitive to the initial centroids just like K-Mean algorithm. This is the main defect of ACO-SLC.


## 5. Conclusion

Time Complexity of ACO. ACO is the algorithm that is inspired by the foraging behavior of ant colonies and has been applied to solve many optimization problems. The typical application of ACO is the application at traveling salesman problem (TSP). The running time of ACO is O(tmax⁡MN2), where tmax⁡, M, and N denote the iteration number, number of ants, and number of cities, respectively. Parameter m is an experiential value and is set to [N/1.5] in general. Parameter N is the key factor of running time because running time is proportional to its square. Parameter tmax⁡ and N are available, and decreasing parameter tmax⁡ and N will cut down running time.Focus of ACO Study. ACO can generate solution with high quality in general. But its shortage is that running time is too long. Cutting down running time is one of study focuses of ACO, and one way is to decrease parameters tmax⁡ and N, especially N.Basic Idea for this Study Focus. For this study focus, the following basic idea is presented in this paper.Firstly, all cities are classified into compact classes, where compact class is the class where all cities in this class cluster tightly in a small region. Secondly, let ACO act on every class to get a local TSP route. Thirdly, all local TSP routes are joined to form solution. Fourthly, the inaccuracy of solution caused by clustering is eliminated.Realization of Basic Idea. The realization of above idea is based on a novel clustering algorithm presented in this paper, which is named special local clustering algorithm (SLC). The running time of SLC is far less than the time of ACO. SLC generates compact classes, while current popular clustering algorithm such as K-Means does not generate compact classes in general. The compactness of class makes the length of TSP route Lt at every iteration convergent; the convergence of Lt (i.e., (|Lt-Lt+1|/Lt)→0) is proposed as the termination criterion of ACO in this paper. Thus, parameter tmax⁡ is cut down to improve the running speed of ACO. In addition, every class has small size; ACO acting on small class makes parameter N cut down, and running speed is improved. According to this analysis, ACO-SLC algorithm is presented in this paper. Simulation shows that ACO-SLC is faster than ACO by 415~10736 of factors!Elimination of the Solution Inaccuracy Caused by Clustering. Although the running speed is improved in this paper, the inaccuracy of solution is heavy. Two factors causing the inaccuracy are found in this paper. One is the cross-edges (see Section 3.3) and the other factor is the unmatching between ACO-SLC and mixture distribution (see Section 3.4). According to these two factors, ACO-SLC-LWCR and ACO-SLC-Mixture are presented in this paper, which is the improvement of ACO-SLC. Simulation shows that ACO-SLC-LWCR and ACO-SLC-Mixture are faster than ACO by 390~101–92 and 257–9419 of factors, respectively! The inaccuracy ratio of ACO-SLC-Mixture is less than ACO in most cases and is bigger than ACO by 2% at most.



---

*Source: 545391-2014-05-05.xml*