A new pheromone update strategy for ant colony optimization

Abstract

Ant system (AS), the first Ant Colony Optimization algorithm (ACO), was proposed by mimicking the foraging behavior of real ants. The inspiring source of ACO is the pheromone laying and following behavior of real ants. The pheromone serves as numerical information to reflect ants’ experience accumulated. However, tests on AS indicate that its pheromone update method can’t always retain the ants’ useful search experiences which mainly refer to the better solutions found. In this study we propose a new pheromone update strategy that uses the Traveling Salesman Problem (TSP) as the instance problem. The idea is to update the pheromone on each edge in TSP by a variable termed component best solution (CBS) matrix, which stores the length of the best tour found for each edge. Simultaneously, the importance of pheromone is strengthened gradually by augmenting the value of its exponent. To investigate its effectiveness, comparisons of experiments are conducted among AS, Elitist ACO and the new algorithm (CBSACO) on five TSP instances. Results show that the performance of CBSACO outperforms that of AS and Elitist ACO. Because this modification to AS is based on the pheromone update method, it can be easily transferred to other combinatorial optimization problems.

Keywords

Ant colony optimization (ACO)pheromone component best solution Elitist AC

1 Introduction

The behavior of a single ant is very simple, but a complete ant colony is capable of finding the shortest path from a food source to their nest via a medium called pheromone [1, 2]. This behavior of ant colony has motivated the design of the Ant Colony Optimization algorithm, called basic ACO in this paper. Basic ACO was applied to the TSP since its proposal and encouraging results were obtained [3]. It has also been applied to solve a wide range of other computationally hard problems [4] because of its desirable characteristics like versatile, robust and distributed computing [5, 6].

However, similar to other metaheuristics, the basic ACO can computationally be inefficient and easily get trapped in the local optima, especially for complex combinatorial optimization problems [7, 8]. Despite the encouraging initial results, the basic ACO is not competitive with state-of-the-art algorithms for the TSP [4, 9]. Therefore, one important development of ACO focuses on the algorithmic variants to achieve much better performance. An elitist strategy [5] was introduced by Dorigo into basic ACO soon after its establishment. In the elitist strategy, a strong additional reinforcement is given to the edges belonging to the best solution found. As an extension of the elitist strategy the rank-based ACO [10] sorts the tours found according to their lengths after each iteration, and only edges of a fixed number of better tours as well as the global-best tour are allowed to be laid with pheromone. Other improvements have also been proposed, for instance Max-Min ACO, Ant Colony System, Best-Worst ACO and population-based ACO. Among them, Max-Min ACO [9] introduces an upper and lower bounds to prevent the values of the pheromone strength from being too large or small and a firm elitist strategy is performed. In ACS [7] two mechanisms are instituted in the procedure which consist of a strong elitist strategy and a so-called pseudo-random proportional rule. In Best-Worst ACO [11], only the pheromone on the edges of the global-best tour and worst tour found in each iteration is updated, and a pheromone re-initialization strategy is performed while getting trapped in the local optima. In population-based ACO [12], only the edges belonging to an elitist solution population are laid with pheromone, and no pheromone evaporation is done for all edges. At the same time, the elitist population is constantly updated during the run of the algorithm.

Meanwhile, there are growing studies focusing on other computationally hard problems using ACO, which is another development of basic ACO. For example, the ACO was modified to solve vehicle routing problems [13 –15]. Models for Course timetabling problem using ACO were proposed by Socha [16, 17]. There are also examples of Flow shop problem using ACO [18]. Other examples are applications of ACO to problems such as classification rules obtention [19 –21], set covering [22] and quadratic assignment [23] et al. recently; we proposed two potential models in which basic ACO was modified to solve P-Median problem [24] and path-covering problem [25] on raster data.

Although, numerous promising results have been obtained with its modified models presented above, there still exist some problems for these two developments of ACO. Firstly, for the development of applications of ACO algorithms to various computationally hard problems, the modified ACO models are devised according to the characteristics of corresponding concrete problems. Their modifications to ACO are probably only suitable for the specific problems to be solved, and are difficult in being transferred to other problems. Secondly, for the development that aims to get high-performing algorithmic variants, the improved models are mostly based on a stronger exploitation of the best found solution, but not the other better solutions which also play a great role in finding even better solutions. In the meantime, although some of these ACO models have introduced some local search strategies to improve their performance on TSP, these local search strategies are again probably only suitable for TSP and also have difficulty in being transferred to other problems.

Therefore a new pheromone update strategy is formulated in this study. A component best solution matrix which stores the length of the best tour found so far for each edge is introduced into basic ACO, and then the pheromone on each edge is updated according to this matrix. The importance of pheromone is strengthened by gradually augmenting the value of its exponent, in order not only to magnify the difference of different tours but also to accelerate the convergence speed. This new pheromone update strategy can make full use of the better solutions found as far as they are stored in the matrix, and can also be easily transferred to other combinatorial optimization problems.

The rest of this paper is organized as follows. Section 2 briefly introduces the basic ACO and analyzes the weaknesses of the pheromone update method of basic ACO. Section 3 looks at the new pheromone update strategy as well as its parameters setting. Section 4 deals with the comparison of CBSACO with both the basic ACO and Elitist ACO on five TSP instances. Finally, Section 5 concludes with further steps

2 Principle of basic ACO and analysis of its pheromone update method

2.1 Principle of basic ACO

Basic ACO is devised by simulating ants’ behaviors of finding the best tour from a food source to their nest. One of the main ideas of ACO algorithm is the indirect communication among artificial ant based on a chemical substance, called pheromone, which real ants use for communication. The pheromone is adapted to reflect ants’ search experience. Ants select tours for exploring randomly at the initial of the food search stage. After all the tours in the current iteration are established, pheromone is accordingly laid by ants on the edges of tours. Typically, edges which are part of better tours or are used by many ants will receive a higher amount of pheromone. In the next stage, ants have a high probability to move along the edges on which pheromone is plentiful, and hence, a more amount of pheromone is laid on these edges. At the final stage, all the ants will be attracted to the shortest tour due to this positive feedback mechanism. The mechanism of basic ACO can be explained through the solution to the TSP which is to find a closed tour with minimal length connecting N given cities [6]. In the algorithm, the process of solution establishment which iteratively adding cities until a complete solution is guided by two components: (1) the amount of pheromone on the edges, and (2) the visibility (travel distance) η_ij (t). In addition, a tabu list, Tabu_k, is used to save the cities already visited and to prevent an ant from visiting them again. The state transition rule used by ACO is given by Equation (1), which gives the probability with which the kth ant moves from city i to city j [6]. $p_{ij}^{k} (t) = {\begin{matrix} \frac{{[τ_{ij} (t)]}^{α} \cdot {[η_{ij} (t)]}^{β}}{\sum_{s \in {allowed}_{k}} {[τ_{ij} (t)]}^{α} \cdot {[η_{ij} (t)]}^{β}}, & if j \in {allowed}_{k} \\ 0 & otherwise \end{matrix}$ (1) where $p_{ij}^{k} (t)$ is the state transition probability from city i to city j for the kth ant at iteration t. τ_ij (t) is the amount of pheromone on edge (i, j), and τ_ij (t) is a heuristic function related to visibility (distance). The set allowed_k, represents cities that can be visited next time without repetition.

The parameters α and β control the relative importance of pheromone versus visibility. A larger value α indicates that more influences of pheromone strength on the probability. In contrast, a larger value of β indicates greater contribution of the visibility (distance) to the probability. α is called pheromone exponent while β is called heuristic exponent in the following. The heuristic function τ_ij (t) is defined as the inverse of the distance or the visibility between cities i and j [6]. $η_{ij} (t) = \frac{1}{d_{ij}}$ (2)

Where d_ij is the distance between city i and city j.

After all ants completed the tour construction at iteration t, the pheromone is updated first by evaporation and then by depositing pheromone on the visited edges. The amount of pheromone is updated according to the following equations [6]: $τ_{ij} (t + 1) = (1 - ρ) * τ_{ij} (t) + Δ τ_{ij} (t)$ (3) $Δ τ_{ij} (t) = \sum_{k = 1}^{m} Δ τ_{ij}^{k} (t)$ (4) where ρ is a coefficient determining the evaporation rate, and Δτ_ij (t) is the amount of pheromone per length unit laid on edge (i, j) by all the ants between time t and t + 1. $Δ τ_{ij}^{k} (t)$ is calculated according to the following equation [6]: $Δ τ_{ij}^{k} (t) = {\begin{matrix} \frac{Q}{L_{k}}, & if the k th ant visites edge (i, j) \\ 0, & otherwise \end{matrix}$ (5) where Q is a constant, and L_k is the tour length or the total travel cost of the kth ant.

2.2 Analysis of the pheromone update method of basic ACO

In basic ACO, pheromone is critical for ants to communicate with each other and cooperate to find the shortest tour from a food source to their nest. The process of pheromone update is done by evaporating and being laid accordingly. Generally, edges which belong to better tours and are traversed by many ants will gain more pheromone. In this process, for edges traversed by more than one ant, the number of times the pheromone laid is equal to the number of ants traversed; for edges traversed by one ant only, the pheromone is laid just one time; for edges not traversed by any ants, the pheromone on them just evaporates without being laid. In the next iteration those edges with a high amount of pheromone will become more desirable for ants to choose. Over time, the modified pheromone and the heuristic information will guide the algorithm to find shorter tours.

However, this pheromone update method has at least two limitations. First, the best tours found are not preserved in the pheromone update process, which usually plays a great role in finding an even better solution. Other metaheuristics, such as genetic algorithm (GA) and particle swarm optimization, generally make full exploitation of the best solution. However, the best solution in ACO may only augment its tour’s pheromone strength at the iteration when it is found, and then disappears. Second, after one iteration, although the pheromone on some edges is laid several times by ants, all the corresponding tours may not be good enough. In contrast, the corresponding tour might be better for those the pheromone on some edges is laid once, however, this tour may be submerged soon due to its less amount of pheromone on these edges. In other words, the times that the pheromone laid dominates the amount of pheromone on edges rather than tours’ quality, which means the current pheromone update method of basic ACO lays a lot emphasis on the tour quantity instead of tour quality.

To verify the limitations of current pheromone update method stated above, the relationship between edge’s best tour (the length of best tour found since the start of algorithm belonging to each edge) and the amount of pheromone on them is tested using the data CH130 from TSPLIB [26], the size of which will be donated as num_of_cities. The Pearson’s correlation coefficient r is used as the index. The formula for calculating coefficient r is: $r = \frac{\sum_{i = 1}^{n} (L_{i} - \bar{L}) (τ_{i} - \bar{τ})}{\sqrt{\sum_{i = 1}^{n} (L_{i} - \bar{L})^{2} \sum_{i = 1}^{n} (τ_{i} - \bar{τ})^{2}}}$ (6) where L is the length of edge’s best tour and $\bar{L}$ is the average length of L. τ is the amount of pheromone on the edge, and similarly $\bar{τ}$ is the average value of τ.

In the tests, the basic ACO algorithm is implemented using VB 6.0 coding on an Intel Core i5-2400 3.1 GHz processor. Parameters of the algorithm are set to the following values: num_of_ants = 20, ρ = 0.5, α = 2, β = 4, τ₀ = 1, num_of_iterations = 5000. Additionally the range of possible amount of pheromone on edge is restricted to an interval [τ_min, τ_max] according to Max-Min ACO [9] with τ_max = 10 and τ_min = 0.1. Since it is a common practice to use a data structure known as a candidate list to solve TSP problem [27, 28], which contains the nearest neighbor cities ordered according to nondecreasing distance. Ant chooses those cities in the candidate list first when establishing a tour. Only after all the cities in the candidate list have been visited will the ant consider visiting the remaining cities. A candidate list with a length of 20 is used in this study for all data. Several modifications given in Equation (7) are made to Equation (5) which is the amount of pheromone laid by one ant. $Δ τ_{ij}^{k} (t) = {\begin{matrix} (\frac{Q}{L_{k}} - 1) * 100 * ρ / num_of_ants, & if the k th ant visites edge (i, j) and \frac{Q}{L_{k}} > 1 \\ 0, & otherwise \end{matrix}$ (7) where Q is set to the average length of all tours found since the start of the algorithm in order to make sure that the value of Δτ can retain relatively stable for different TSP problems. The reason to multiply ρ to the right side of the equation is also to ensure the relatively stable Δτ value with different ρ values. The num_of_ants is divided on the right side of the equation for the same reason. Normally Q is supposed to be 1.1 times greater than L_k, so $\frac{Q}{L_{k}} - 1$ is close to 0.1. The utilization of ‘100’ at the right side of the equation can make sure the value of τ reaches to τ_max(τ_max = 10) at an ideal situation.

Following the above steps, the moment (iteration) when to calculate r and the objects (edges) which will be chosen need to be fixed on at this stage. In this process, not all iterations but ones which are multiple of ten are chosen, i.e., the 10th, 20th, 30th, …, 4900th, and 5000th iteration are used as moments for calculation. Again not all edges but ones whose own best solution is better are used to calculate r, because the amount of many edges’ pheromone will be reduced to τ_min due to the evaporation. Thus, the r value of edges with better best solution is more representative than that of all edges. In practice, all the edges in TSP are ordered according to the length of their own best tours, and then the top two time num_of_cities edges and four time num_of_cities edges are chosen for calculation respectively. Five independent trials are carried out for the test data. The results are shown in Fig. 1.

Fig.1

The value of r changes with the iterations of the five trials (Ch130, ρ = 0.5).

During the five repetitive trials showed in Fig. 1, r decreases to 0 in the first, second, fourth and fifth trial soon after the run of the algorithm while it does so at the second half of the algorithm execution in the third trial. The pheromone strength on all most edges has been found close to τ_min when the r value approaches to 0. Additionally in the last iteration of all five trials, the pheromone strength of the top two times num_of_cities edges is recorded and some edges’ pheromone strength have been found to be equal to τ_min. The frequency of the τ_min appearing in the recorded edges is listed in Table 1.

As showed in Table 1, for the top one time num_of_cities edges, the proportion of them with pheromone amount equal to τ_min ranges from 3.08% to 100% in the last iteration while it ranges from 45% to 100% for the top two time num_of_cities ones. Since the evaporation coefficient ρ has a great impact on the amount of pheromone on edges, the other two values 0.1 and 0.01 for ρ are also examined in the same way. The results are shown in the following figures (i.e. Figs. 2 to 3) and tables (i.e. Tables 2 to 3). r decreases to 0 at a certain period of the algorithm execution in the first and fifth trial for ρ valuing 0.1 and it does not fall close to zero level any longer in the five trials for ρ valuing 0.01 (Figs. 2 and 3). However, the edges with pheromone amount equal to τ_min still keep a moderate share for both two ρ values (Tables 2 and 3).

Fig.2

The value of r changes with the iterations of the five trials (Ch130, ρ = 0.1).

Fig.3

The value of r changes with the iterations of the five trials (Ch130, ρ = 0.01).

Table 1

Frequency of τ_min appearing in the recorded edges of the five trials (in the last iteration, CH130, ρ = 0.5)

	1st trial	2nd trial	3rd trial	4th trial	5th trial	Average
Frequency in the top one time	25 (19.23%)	5 (3.85%)	130 (100%)	4 (3.08%)	8 (6.15%)	34.4 (26.46%)
num_of_cities edges
Frequency in the top two time	117 (45.00%)	119 (45.77%)	260 (100%)	127 (48.85%)	125 (48.08%)	149.6 (57.54%)
num_of_cities edges
r in the last iteration	–0.6767	–0.8625	0	–0.8457	–0.8753

Table 2

Frequency of τ_min appearing in the recorded edges of the five trials (in the last iteration, ch130, ρ = 0.1)

	1st trial	2nd trial	3rd trial	4th trial	5th trial	Average
Frequency in the top one time	16 (12.31%)	5 (3.85%)	0 (0%)	2 (1.54%)	130 (100%)	30.6 (23.54%)
num_of_cities edges
Frequency in the top two time	103 (39.62%)	105 (40.38%)	114 (43.85%)	117 (45%)	260 (100%)	139.8 (53.77)
num_of_cities edges
r in the last iteration	–0.7415	–0.8568	–0.8886	–0.7878	0

Table 3

Frequency of τ_min appearing in the recorded edges of the five trials (in the last iteration, ch130, ρ = 0.01)

	1st trial	2nd trial	3rd trial	4th trial	5th trial	Average
Frequency in the top one time	2 (1.54%)	18 (13.85%)	7 (5.38%)	2 (1.54%)	14 (10.77%)	8.6 (6.62%)
num_of_cities edges
Frequency in the top two time	99 (38.08%)	119 (45.77%)	109 (41.92%)	111 (42.69%)	110 (42.31%)	109.6 (42.15%)
num_of_cities edges
r in the last iteration	–0.8026	–0.7774	–0.8159	–0.8816	–0.7495

In summary, the following results can be disclosed based on the above three sets of experiments: i) When the evaporation coefficient is large, the tours found are not good enough and they do not concentrate on certain edges in one iteration, the evaporation effect will dominates the variation of pheromone and consequently causes all edges’ pheromone to decrease quickly and probably approach τ_min. As a result, the search experience accumulated will be lost and can no longer be exploited in the succeeding search process. ii) Although the absolute r value is close to 0.8 or even greater most of the time, the statistical results from Tables 1–3 indicate that an average of 6% of the top one time num_of_cities edges has pheromone strength equal to τ_min. Thus the algorithms cannot make full use of such edges. For conditions of top two time num_of_cities edges, the proportion increases to greater than 40%, and these edges will make no sense in finding even better solutions.

3 A new pheromone update strategy

Section 2 have pointed out and validated that the current pheromone update method of basic ACO cannot make sure to preserve the better tours and will result in the disproportion between edges’ own best solution and their pheromone strength sometimes. Against the weaknesses of basic ACO and to make full use of the search experience of the ACO algorithm especially the better solutions found, a new pheromone update strategy is proposed as follows.

3.1 The new pheromone update strategy

For new pheromone update strategy, a component best solution matrix, donated as BESTTOUR_ij, which stores the length of the best tour found so far for each edge is introduced into basic ACO, and is used as the basis for pheromone update on each edge. In practice, the BESTTOUR_ij value of all edges is set to an arbitrarily high value which significantly exceeds the normal tour length and is denoted as BESTTOUR_max at the initialization phase. When one iteration finishes, the BESTTOUR_ij of each edge will be updated according to Equation (8).

$\begin{matrix} if {BESTTOUR}_{ij} \\ > L_{k} then {BESTTOUR}_{ij} = L_{k} \end{matrix}$ (8)

Then, the pheromone on each edge in CBSACO is updated according to BESTTOUR_ij, given by Equations (9) and (10). ${\begin{matrix} τ_{ij} (t + 1) = (1 - ρ) * τ_{ij} (t) + Δ τ_{ij} (t), & if {BESTTOUR}_{ij} < > {BESTTOUR}_{max} \\ τ_{ij} (t + 1) = τ_{ij} (t), & othewise \end{matrix}$ (9) ${\begin{matrix} Δ τ_{ij} (t) = (Q / {BESTTOUR}_{ij} - 1) * 10 * ρ, & if Q / {BESTTOUR}_{ij} > 1 \\ Δ τ_{ij} (t) = 0, & otherwise \end{matrix}$ 10)

Similar to parameter settings in basic ACO, Q is set equal to the average length of all tours. Normally Q is supposed to be 1.1 times greater than BESTTOUR_ij. Thus, Q/BESTTOUR_ij - 1 is close to 0.1 and the value of (Q/BESTTOUR_ij - 1) *10 approaches 1. Therefore, the amount of pheromone on the edges can be maintained near 1 through Equations (9) and (10). Same to basic ACO, the bound of possible pheromone strength in CBSACO is restricted to the interval [τ_min, τ_max] according to Max-Min Ant System (Thomas and Holger 2000, Stutzle and Hoos 1997) (τ_max = 10, τ_min = 0.1).

The new pheromone update strategy differs from that of basic ACO because of two main aspects. i) All edges in CBSACO are laid with pheromone according to the best solutions themselves, whereas only part of the edges in basic ACO. ii) The pheromone exponent α augments gradually in CBSACO, whereas it keeps unchanged in basic ACO. Since in CBSACO, the new pheromone update strategy evens out pheromone strength on all edges, which is not favorable for finding even better solutions and slow the algorithm convergence, the value of pheromone exponent α is set from an initialization value, generally zero, to α_max given by Equation (11). $α (k + 1) = α (k) + Δ α, if α < α_{max}$ (11) where α_max is the maximum pheromone exponent fixed in advance and Δα is the increment of the pheromone exponent during each iteration.

Obviously, this new pheromone update strategy can make the edges’ pheromone strength proportional to the length of their own best solution. Thus, the better solution founded can be completely utilized in the next stage.

3.2 Toning of the new parameters

In this process, parameters α_max and Δα are introduced into the new pheromone update strategy, and the impacts of them on the performance of CBSACO were tested.

During the tests, α_max is kept as a constant of 200. Δα and its corresponding total iteration number is shown in Table 4. The value of Δα is inversely proportional to its total iteration number in the table in order to make the pheromone exponent reach the maximum value at the later stage of computation. Five group data from TSPLIB [26] given in Table 5 is used as the test instances.

Table 4
Δα and corresponding total iteration number for 9 tests

Serial Δα Total Serial Δα Total

number number of number number of

iterations iterations

1 1 20000 6 0.01 30000

2 0.3 20000 7 0.0075 30000

3 0.1 20000 8 0.005 50000

4 0.05 20000 9 0.002 110000

5 0.03 20000

Serial	Δα	Total	Serial	Δα	Total
1	1	20000	6	0.01	30000
2	0.3	20000	7	0.0075	30000
3	0.1	20000	8	0.005	50000
4	0.05	20000	9	0.002	110000
5	0.03	20000

Table 5

Five group test instances

Name of problem	num_of_cities
Pr76	76
Kroa100	100
Ch130	130
Kroa200	200
Pr439	439

Because each ant establishes a tour during one iteration, the total number of tours generated is equal to the iteration number multiplied by the number of ants. The shortest one of all the tours is used as the result of each trial. For each group instance, five repetitive trials are carried out for each Δα. The comparison among different Δα values is performed on the average, maximum and minimum tour lengths of the five trials. The results are presented in the Fig. 4.

Fig.4

The average, maximum, minimum tour length of five trials for five group instances with respect to different Δα.

Figure 4 shows the following results. i) The tour length (average-, maximum- and minimum-) of four group instances, except pr76, becomes shorter with decreasing Δα values while it tends to be stable with Δα smaller than 0.01. ii) When the size of the instance is small, the result of the large Δα value is as good as that of the small Δα value. However, the result worsens significantly with increasing instance size (num_of_cities) when the Δα value is large. Besides, a large number of iteration times are needed for α to reach to α_max based on a small Δα value and it is a little time-consuming. In a sum, considering the tour length performance and time consuming impacts, the parameter Δα is better to be configured inversely related to the instance size, such that Δα with the value of 0.05 is suitable for problems with size less than 100, Δα with the value of 0.01 is suitable for problems with size less than 200, and so on.

On the other side, in order to investigate the impact of α_max on the performance of the CBSACO algorithm, the moment (number of generation) when the best solution is found is recorded for each trial, as well as the pheromone exponent value at such moment. This value which is regarded as the most suitable value for α_max is averaged over five repetitive trials, and the result is listed in Table 6. When Δα values 1, 0.3, 0.1, 0.05 and 0.03, the pheromone exponent reaches α_max at a very early stage. Thus, it is useless to record the pheromone exponent value at such moment because most of them are equal to α_max.

Table 6

Pheromone exponent value for finding the best solution on five group instances

Instance	Pr76	Kroa100	Ch130	Kroa200	Pr439
0.01	128.1	85.7	112.6	175.6	169.4
0.0075	67.4	81.2	89.4	161.8	162. 1
0.005	84.5	59.5	92.7	188.6	117.7
0.002	53.0	66.3	89.3	111.7	111. 8
Ave	83.3	73.2	96.0	159.4	140. 3

It can be seen from the Table 6 that when the instance size becomes larger, the corresponding pheromone exponent at the moment when best solution is found tend to become larger too. The suitable range of α_max generally could be 50 to 200 and it can be augmented bigger with the larger the instance size.

4 Experimental results and comparison

In order to validate the effectiveness of the new pheromone update strategy proposed in this study, comparative experiments are carried out among basic ACO, Elitist ACO and CBSACO. Two main ACO algorithms, Max-Min ACO and ACS, are excluded from comparison here because they are incorporated with local search strategies.

As previously stated, in Elitist ACO the edges belonging to the best tour are additionally laid with pheromone even if they are not traversed by any ants in the current iteration. Different from Elitist ACO proposed by Dorigo [5], the elitist strategy here is slightly modified for simplification. The maximum pheromone value on all edges is recorded while it is updated, and then is assigned to the edges belonging to the best tour. In this way, the edges of the best tour have the maximum amount of pheromone all the time.

Parameters of the basic ACO, Elitist ACO and CBSACO are set according to the aforementioned experimental results. The setting of parameters in basic ACO is same as that in the Section 2. The evaporation coefficient ρ values 0.5 at which better testing result was obtained in Section 2. Similarly, the setting of parameters in Elitist ACO and CBSACO is the same as that in basic ACO except the evaporation coefficient ρ value is 0.01. The total number of iterations is set to 20000 for all three algorithms. The new parameter Δα is set to 0.01, and the settings of α_max are listed in Table 7 depending on the instance used.

Table 7
Value of α_max with different instance

Instance α _max

Pr76 80

Kroa100 100

Ch130 120

Kroa200 150

Pr439 180

Instance	α _max
Pr76	80
Kroa100	100
Ch130	120
Kroa200	150
Pr439	180

In this comparison experiment, ten trials are run for each group instance and the best tour found is selected as the result of each trial. The comparison among the three algorithms is performed on the maximum, minimum and average lengths of the best tour of the ten trials as before. The results are shown in Table 8.

Table 8

Comparison of CBSACO with basic ACO and elitist ACO on the maximum, minimum and average tour lengths

Algorithms	Maximum			Minimum			Ave			Best Known
	Basic	Elitist	CBSACO	Basic	Elitist	CBSACO	Basic	Elitist	CBSACO	Solution
pr76	117458.4	109870.6	109504.0	111253.2	108159.4	108159.0	114287.4	108715.9	108394.0	108159.0
kroa100	23269.4	21385.8	21383.6	21725.0	21285.4	21285.4	22258.1	21330.1	21301.8	21285.4
ch130	6478.4	6235.1	6184.84	6280.2	6110.7	6110.7	6340.0	6175.7	6137.24	6110.7
kroa200	32009.3	29875.5	29777.1	30760.3	29464.7	29405.7	31276.8	29675.1	29542.2	29369.4
pr439	119758.8	115821.0	112788.0	114131.0	109300.5	109816.0	116649.0	112184.1	110605.0	107217.0

It can be seen from the Table 8 that during the ten repetitive trials, the average, maximum, minimum values of CBSACO exhibit a significant improvement over those of basic ACO. Meanwhile, the performance of CBSACO surpasses that of Elitist ACO and the only exception is the instance Pr439 in which Elitist ACO has a slightly better performance on the minimum value. In detail, CBSACO obtains the best known solution several times during ten trials for instance Pr76, Kroa100 and Ch130 while it also finds a solution which is highly similar to the best known solution for instance kroa200. A gap exists between the best solution found and the best known solution only for instance pr439. In general, CBSACO seems to more probably able to find better solutions than basic ACO and Elitist ACO.

Although the experimental results in Table 8 show that CBSACO performs best among the three algorithms, however, shortages still are there for CBSACO. i) For large size instance, the pheromone exponent needs to augment slowly and this will cause a large number of iteration times and more computing time. ii) At the late stage of the CBSACO run, the pheromone exponent α value usually becomes very large or even equal to α_max, and this will dominate the algorithm search and possibly leads it to be trapped in the local optima.

5 Conclusion and further work

In this study, tests on basic ACO indicate that the pheromone update method cannot always retain the ants’ useful search experience which mainly refers to the best solution and better solutions found, and this would lead to the incomplete exploitation of such solutions. Moreover, pheromone on edges decreases quickly and may achieve to a minimum value preset with large value of evaporation coefficient. When this occurs, all the search experience will be lost and cannot be exploited again in the following search process.

Going against such weaknesses of basic ACO, a new pheromone update strategy which can preserve the better solutions found and cause the edges’ pheromone strength proportional to the length of their own best found solutions was proposed in this study. The new pheromone update strategy differs from that of basic ACO in two main aspects. While the first is that all edges are laid with pheromone, the other is the pheromone exponent augments gradually. Since different from some modifications to ACO implemented by incorporation with local search strategies or devised for some concrete problems, which have difficulty in being transferred to other combinatorial optimization problems, CBSACO proposed in this paper makes a substantial modification to the pheromone update method, and it can be transferred easily to other problems. Comparison experiments results show that the new pheromone update strategy based CBSACO greatly outperforms that of basic ACO and surpasses that of Elitist ACO as well. Meanwhile, tests for CBSACO also imply its strong and global search ability relative to basic ACO and elitist ACO. Additionally, for the configuration of two new parameters α_max and Δα introduced, experimental results imply that a large α_max value and a small Δα value are needed with increasing instance size in order to obtain a better solution.

As stated above, however, CBSACO proposed in this study still exhibits several drawbacks, such as being time-consuming and getting trapped in local optima at the late stage of the algorithm run. So further work includes local search prevention of CBSACO such that “mutation” operation in GA, “tabu” strategy in Tabu Search and among others can be brought into CBSACO to avoid search stagnation.

Footnotes

Acknowledgments

We appreciate the valuable comments from the anonymous reviewers. We are indebted to the National Youth Natural Foundation of China (Grant No. 41201383), Jiangxi Province Key Lab for Digital Land (Grant No. DLLJ201313) and Open research fund program of key laboratory of earth observation, state bureau of surveying and mapping (Grant No. K201504).

References

Beckers

, et al., Trails and U-turns in the selection of a path by the ant Lasius niger, Journal of Theoretical Biology159(4) (1992), 397–415.

Goss

, et al., Self-organized shortcuts in the Argentine ant, Naturwissenschaften76(12) (1989), 579–581.

Colorni

, et al., Distributed optimization by ant colonies, Proceedings of the 1st European Conference on Artificial Life, 1991, pp. 134–142.

Dorigo

and Stützle

, Ant colony optimization: Overview and recent advances, Handbook of Metaheuristics146(05) (2010), 227–263.

Dorigo

, Optimization, learning and natural algorithms, Thesis Politecnico di MilanoItaly, 1992.

Dorigo

, et al., Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics26(1) (1996), 29–41.

Dorigo

and Gambardella

L.M.

, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation1(1) (1997), 53–66.

Dorigo

, et al., Ant algorithms for discrete optimization, Artificial Life5(2) (1999), 137–172.

Stutzle

and Hoos

H.H.

, Max-Min ant system, Future Generation Computer Systems16(9) (2000), 889–914.

10.

Bullnheimer

, et al., A new rank based version of the Ant System: A computational study, Technical report, Institute of Management Science, University of Viena, 1997.

11.

Cordón García

, et al., Analysis of the best-worst Ant System and its variants on the TSP, Mathware & Soft Computing9(2-3) (2002), 177–192.

12.

Guntsch

and Middendorf

, A population based approach for ACO, Applications of Evolutionary Computing, Proceedings2279 (2002), 72–81.

13.

Bell

J.E.

and McMullen

P.R.

, Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics18(1) (2004), 41–48.

14.

Fuellerer

, et al., Ant colony optimization for the two-dimensional loading vehicle routing problem, Computers & Operations Research36(3) (2009), 655–673.

15.

Reimann

, et al., D-Ants: Savings based ants divide and conquer the vehicle routing problem, Computers & Operations Research31(4) (2004), 563–591.

16.

Socha

, et al., A max-min ant system for the university course timetabling problem, in Proc 3rd Int Workshop Ant Algorithms, 2002, pp. 1–13.

17.

Socha

, et al., Ant algorithms for the university course timetabling problem with regard to the state-of-the-art, in Applications of Evolutionary Computing: Proceedings of the 2003 EvoWorkshops, 2003, pp. 334–345.

18.

Rajendran

and Ziegler

, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research155(2) (2004), 426–438.

19.

Martens

, et al., Classification with ant colony optimization, IEEE Transactions on Evolutionary Computation11(5) (2007), 651–665.

20.

Otero

, et al., c Ant-Miner: An ant colony classification algorithm to cope with continuous attributes, Ant Colony Optimization and Swarm Intelligence (2008), 48–59.

21.

Parpinelli

R.S.

, et al., Data mining with an ant colony optimization algorithm, IEEE Transactions on Evolutionary Computation6(4) (2002), 321–332.

22.

Lessing

, et al., A comparison between ACO algorithms for the set covering problem, Ant Colony Optimization and Swarm Intelligence (2004), 105–122.

23.

Maniezzo

, Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem, Informs Journal on Computing11(4) (1999), 358–369.

24.

, et al., Intelligent GIS for solving high-dimensional site selection problems using ant colony optimization techniques, International Journal of Geographical Information Science23(4) (2009), 399–416.

25.

, et al., Ant intelligence for solving optimal path-covering problems with multi-objectives, International Journal of Geographical Information Science23(7) (2009), 839–857.

26.

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

27.

Bentley

J.J.

, Fast algorithms for geometric traveling salesman problems, ORSA Journal on Computing4(4) (1992), 387–411.

28.

Reinelt

, The traveling salesman: Computational solutions for TSP applications. New York: Springer-Verlag, 1994.

A new pheromone update strategy for ant colony optimization

Abstract

Keywords

1 Introduction

2 Principle of basic ACO and analysis of its pheromone update method

2.1 Principle of basic ACO

3.1 The new pheromone update strategy

Table 4 Δα and corresponding total iteration number for 9 tests Serial Δα Total Serial Δα Total number number of number number of iterations iterations 1 1 20000 6 0.01 30000 2 0.3 20000 7 0.0075 30000 3 0.1 20000 8 0.005 50000 4 0.05 20000 9 0.002 110000 5 0.03 20000

Table 7 Value of αmax with different instance Instance α max Pr76 80 Kroa100 100 Ch130 120 Kroa200 150 Pr439 180

Footnotes

Acknowledgments

References

Table 4
Δα and corresponding total iteration number for 9 tests

Serial Δα Total Serial Δα Total

number number of number number of

iterations iterations

1 1 20000 6 0.01 30000

2 0.3 20000 7 0.0075 30000

3 0.1 20000 8 0.005 50000

4 0.05 20000 9 0.002 110000

5 0.03 20000

Table 7
Value of α_max with different instance

Instance α _max

Pr76 80

Kroa100 100

Ch130 120

Kroa200 150

Pr439 180