Analysis of the Number of Ants in Ant Colony System Algorithm

Analysis of the Number of Ants in Ant Colony System Algorithm Mustafa Muwafak Alobaedy 1 , Ali A Khalaf 2 , and Ishola D. Muraina 3 1 Universiti Utara Malaysia, Malaysia, alobaedy@uum.edu.my 2 University of Baghdad, Iraq, alrahmanali@yahoo.com 3 Universiti Utara Malaysia, Malaysia, ishod@uum.edu.my Abstract— This study presents an analysis of the number of ants in ant colony system algorithm. The study focuses on the effect of changing the number of ants in the algorithm behavior rather than find the optimum number. The factors investigated in this study are algorithm execution time, best solution, pheromones accumulative, pheromone dispersion, and the number of new solutions found by the ants. The experiment was conducted using travelling salesman problem to investigate those factors. The results show that the number of ants changes the algorithm behavior dramatically. Therefore, tuning the parameter number of ants in ant colony system could be easier by applying the min and max number of ants recommended in this study. Keywords— : Ant Colony System; Ant Colony Optimization; Parameters Analysis; Metaheuristic Algorithm I. INTRODUCTION Swarm Intelligence (SI) is one of the prominent branches in artificial intelligence inspired by nature. SI includes several nature-inspired algorithms such as Particle Swarm Optimization (PSO), Artificial Bees Colony (ABC), and Ant Colony Optimization (ACO). ACO algorithm is a metaheuristic algorithm proposed by Colorni, Dorigo, and Maniezzo [1]. Since then, several variants of ACO algorithms have been proposed such as ant system, ant rank , elitist ant system, max-min ant system, and ant colony system algorithms [2]–[5]. One of the best variant of ACO has been argued to be is Ant Colony System (ACS) algorithm developed by Dorigo and Gambardella [6]. Study of Stutzle et al. [7] stresses that ACS algorithm has many parameters that needs to be tuned in order to get the best performance. One of those parameters is the number of ants to be used in a colony. According to ACS canonical, each ant constructs its own solution using the pheromone and heuristic information [8]. The pheromone information is shared between all the ants, while each ant applies local update on the pheromone. Therefore, more ants in the colony are suggested to cause more modification on the pheromone matrix. However, present studies have shown that little information is available about the effect of number of ants to the overall algorithm’s performance. Studies on variant ACO algorithm such as [8], [9] have emphasized important parameters values based on the performance of the algorithms. However, the obtained values from the experiment showed no concrete proof or methodology on how to find the optimum values. On the other hands, a recent study on ACO parameters addresses the problem of parameter evaluation [10], with investigated parameters of ߙ ( ݁݊݋݉݋ݎ݁ℎ݌ ) )݋݅ݐܽݎ݋݌ܽݒ݁( ߩ ݀݊ܽ,)ܿ݅ݐݏ݅ݎݑ݁ℎ(ߚ, but failed to consider number of ants. Thus, this study aims to analyze the influence of the number of ants in ACS algorithm especially on the algorithm execution time, finding the best solution, pheromone accumulation, pheromone dispersion, and the total number of solutions found by all ants. The outputs of those factors give a clear picture about ACS algorithm behavior and some guidance on tuning the parameter of the number of ants. II. ANT COLONY SYSTEM ALGORITHM The ACS algorithm was introduced by Dorigo and Gambardella [5], [6] to improve the performance of Ant System (AS) algorithm. ACS has been enhanced to differ in three main aspects from the AS. Firstly, ACS uses a more aggressive action choice rule than AS. Secondly, the pheromone is added only to move belonging to the global-best solution, and thirdly, each time an ant moves on a path, it removes some pheromone from that path. This implies that three main phases of the ACS algorithm constitute the ants’ solution construction, global pheromone trail update, and local pheromone trail update. Moreover, ACS algorithm starts solution construction when the ant moves from node to node. The ant will choose the node using one of the two rules; the pseudorandom proportional rule which is based on exploitation mechanism and exploration mechanism which is based on the probability distribution used in AS. Meanwhile, the tuning between exploitation and exploration is controlled by a parameter fixed by the user. In addition, ACS algorithm applies the global pheromone trail update. In global pheromone update, only one ant (the best-so-far ant) is allowed to add pheromone after all ants have finished constructing their tours. In addition, ACS algorithm applies the local pheromone trail update, where all the ants apply a local pheromone update rule immediately 2017 Fifth International Conference on Information and Communication Technology (ICoICT) ISBN: 978-1-5090-4911-0 (c) 2017 IEEE77 after moving on arcs during the tour construction using the evaporation concept. In ACS algorithm, when ant ݇ wants to move from node ݅to node݆ , it will choose the node using a rule called pseudorandom proportional rule, calculated as: ܲ ௜௝ ஺௡௧ ೖ ൌቊ ݔܽ݉݃ݎܽ ௟∈ே ೔ ೖ ݈݅߬൛ ሾ ݈݅ߟ ሿ ఉ ൟ, if ݍ ൑0ݍ; ܬ, otherwise (1) where ݍ is a random variable uniformly distributed in [0, 1], 0ݍ 0( ൑ 0ݍ ൑ 1) is a parameter, and ܬ is a random variable selected according to the probability distribution calculated as: ܬൌ ሿ݆݅߬ሾ ఈ ሿ݆݅ߟሾ ఉ ∑ ሿ݈݅߬ሾ ఈ ሿ݈݅ߟሾ ఉ ௟∈ே ೔ ೖ ܰ ∈ ݆݂݅, ௜ ௞ (2) with α = 1. Tuning between exploitation and exploration is controlled by the parameter0ݍ . In ACS only one ant (the best-so-far ant) is allowed to add pheromone after each cycle. The Update is implemented using the following equation: ← ݆݅߬ ( ߩ1െ ) ߬∆ߩ൅݆݅τ ௜௝ ௕௦ , ∀ ( ,݆݅ ) ܶ∈ ௕௦ , (3) Where ߩ is the pheromone evaporation rate, and ߬∆ ௜௝ ௕௦ = 1/Cbs. For local pheromone update, a rule immediately applied after moving on )݆,݅( ܿݎܽ during the solution construction using the following equation: ← ݆݅߬ ( 1െ ξ ) τ ୧୨ ൅ξτ ଴ , (4) Where ξ, 0 ൏ ߦ ൏ 1, and τ ଴ are two parameters. The value of τ ଴ is equal to the initial value for the pheromone trail. III. EXPERIMENT DESIGN A simulator for analyzing the number of ants in ACS algorithm was developed using C# language and executed under Windows 8 with 2.0 GHz and 2 GB memory. The experiments were conducted using TSP dataset from TSPLIB, specifically eil51 and kroa100 which consists of 51 cities and 100 cities respectively. The data sets with 50 and 100 cities are considered as small and medium scale problems respectively. The metrics used in this experiment are: i. Execution time ii. Best solution iii. Accumulative pheromone on all edges iv. Standard distribution of the pheromone v. The total number of new solutions found by the ants. Using these metrics help to understand the algorithm deeply and provides answers for the proposed questions. The algorithm runs one time for each change in the number of ants and the information related to the metrics are recorded. The stop condition is 1000 iterations. The other parameters values were selected from [8] as shown in Table 1. TABLE I. ACS PARAMETERS VALUE ࢼ ࣋ ૆ ࢗ ૙ 2 0.1 0.1 0.9 IV. EXPERIMENT AND RESULTS The experiment was conducted by starting with one ant and repeated by increasing ant by one in each runs. The total numbers of ants used in this experiment are 100 ants. Figure 1 shows that the algorithm execution time increased approximately with linear shape during the increase number of ants in eil51 dataset. The Figure shows that below 31 ants is reasonable time within 20 seconds. Figure 2 shows similar pattern for kroa100 dataset. However, the algorithm execution time increased double due to the complexity of the problem (100!). Never the less, below 16 ants is considered a reasonable execution time. Fig. 1. Execution Time with Different Number of Ants (50 Cities) 78 Fig. 2. Execution Time with Different Number of Ants (100 Cities) Figure 3 displays the tour length using different number of ants in eil51 dataset. The obtained result shows that using less than 6 ants produce the worst solution. On the other hands, using more than 6 ants enhance the results with some variance. Nevertheless, using more than 26 ants did not achieve better performance. Fig. 3. Tour Length with Different Number of Ants (50 Cities) Figure 4 presents the tour length using different number of ants in kroa100 dataset. The figure shows that the algorithm starts to find good tour after using 6 ants. However, the algorithm did not benefit after using 26-31 ants. Fig. 4. Tour Length with Different Number of Ants (100 Cities) The performance of pheromone accumulation based on the number of ants is depicted in Figure 5 and 6 for eil51 and kroa100 datasets respectively. More pheromone means the ants were able to find several best-so-far solutions. Both figures show that the accumulation of pheromone is reduced and stabilized using more than 16 ants. Therefore, this can be considered as a sign of stagnation. Fig. 5. Pheromone Accumulation with Different Number of Ants (50 Cities) Fig. 6. Pheromone Accumulation with Different Number of Ants (100 Cities) Due to the importance of pheromone in ants’ decision, the pheromone standard deviation were calculated and presented in Figures 7 and 8 for eil51 and kroa100 datasets respectively. The pheromone deviation shows the dispersion of pheromone on the edges. More dispersion means more information for the ants beside the heuristic information. Figures 7 and 8 show the pheromone deviation was reduced dramatically using 1-16 ants and stabilized with low dispersion after 16 ants. 79 Fig. 7. Pheromone Dispersion with Different Number of Ants (50 Cities) Fig. 8. Pheromone Dispersion with Different Number of Ants (100 Cities) One of the main attribute of ACS algorithm is the exploration of the search space. The algorithm needs to make some balance between exploitation and exploration mechanisms. Figure 9 depicts the number of solutions found by ACS using eil51 data set. The figure shows that increasing the number of ants more than 16 did not enhance the exploration with some exception around 31-36 ants. Fig. 9. Solution Number with Different Number of Ants (50 Cities) Figure 10 shows the number of solutions found by ACS algorithm using kroa100 data set. The experiment reveals that even one ant was able to find 22 solutions. This could be due to the size of kroa100 data set which is double than the size of eil51 dataset. However, the algorithm was able to find 43 solutions using 7 ants. To compare between Figure 9 and Figure 10 for both data sets, both figures shows that 6-16 ants were able to find a good number of new solutions. Note that the high number of new solutions does not mean it is necessary that the best solution will be one of them; it is just an indicator that the algorithm is able to explore bigger area of the search space. Fig. 10. Solution Number with Different Number of Ants (100 Cities) The experiment results show that the number of ants in ant colony systems is an important parameter which needs to be tuned carefully. The results revealed that increasing the number of ants does not necessarily mean better results. In fact, the experiment shows some contradiction when the number of ants is increased. Increasing the number of ants will increase the algorithms complexity which means longer execution time. In addition, more ants in the colony evaporate the pheromone faster due to the local pheromone update mechanism in ACS algorithm. Once the pheromone has evaporated, no more good solution will be found and this resulted into stagnation. Experiment also shows that increasing the number of ants did not help the exploration of search space effectively. Therefore, based on the experimental results, the recommended number of ants in the ACS algorithm is between 6 and 20 for the algorithm to reach optimum or near optimum solution within reasonable processing time. This recommendation is suitable for small and medium scale of travelling salesman problem. V. CONCLUSION The number of ants in the ant colony system algorithm has been proven to be an important parameter that contributed to the performance of the algorithm. Large number of ants did not help to enhance the algorithm performance. Observation on the execution time, best solution, pheromone accumulation, pheromone deviation, and the number of new solution founds by the ants in small and medium size problems indicates that small number of ants in ACS is recommended. As a future 80 work, a large scale of TSP could be investigated to find the range of suitable number of ants. In addition, other domains such as scheduling and graph coloring could be used to explore the influence of number of ants on ACS algorithm. A CKNOWLEDGMENT The authors wish to thank the College of Science, University of Baghdad. R EFERENCES [1] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed Optimization by Ant Colonies,” in Proceedings of the European Conference on Artificial Life, 1991, pp. 134–142. [2] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant System: Optimization by a Colony of Cooperating Agents,” J. IEEE Trans. Syst. Man, Cybern. B, Cybern., vol. 26, no. 1, pp. 29–41, Jan. 1996. [3] L. M. Gambardella and M. Dorigo, “Ant-Q : A Reinforcement Learning approach to the traveling salesman problem,” Update, vol. 5625, no. 1, pp. 252–260, 1995. [4] M. Dorigo, V. Maniezzo, and A. Colorni, “Positive Feedback as a Search Strategy (Report No 91- 016),” Milan, 1991. [5] M. Dorigo and L. M. Gambardella, “Ant Colonies for the Travelling Salesman Problem,” J. Biosyst., vol. 43, no. 2, pp. 73–81, 1997. [6] M. Dorigo and L. M. Gambardella, “Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem,” J. IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 53–66, 1997. [7] T. Stutzle, M. Lopez-Ibanez, P. Pellegrini, M. Maur, M. Montes de Oca, M. Birattari, and M. Dorigo, “Parameter Adaptation in Ant Colony Optimization,” in Autonomous Search SE - 8, Y. Hamadi, E. Monfroy, and F. Saubion, Eds. Springer Berlin Heidelberg, 2012, pp. 191–215. [8] M. Dorigo and T. Stutzle, Ant Colony Optimization. Cambridge, Mass: MIT Press, 2004. [9] T. Stutzle and H. Hoos, “MAX-MIN Ant System and Local Search for the Traveling Salesman Problem,” in Proceedings of the International Conference on Evolutionary Computation, 1997, pp. 309–314. [10] A. Siemiński, “Ant Colony Optimization Parameter Evaluation,” in Multimedia and Internet Systems: Theory and Practice, A. S. Aleksander Zgrzywa, Kazimierz Choroś, Ed. Berlin Heidelberg: Springer, 2013, pp. 143–153. 81