Balancing Between Exploration and Exploitation in ACO
Keywords:
ACO, TSP, B, Elitist Ant System (EAS), Beta-Elitist Ant System (BEAS), transition ruleAbstract
In order to balance the preference of the artificial entities towards exploration or exploitation (in their transition rule), a novel technique is proposed for replacing the random function used by the classical Ant Colony Optimization (ACO) algorithms for solving the Traveling Salesman Problem (TSP). The proposed Beta Distribution function (B), or random:betavariate(a; b) has the proven capability (depicted through test-runs) of influencing the algorithm’s solution quality and convergence speed. Consequently, this paper will introduce in the related work section the classical ACO algorithm, with a focus on the transition rule used for choosing the next node in the problem’s associated graph, followed by the related work on this topic, and it will continue with the introduction of the B function which will be presented both from a theoretical and practical perspective in relation with the scope: balancing between exploration and exploitation in order to improve the performance of the ACO algorithm for the TSP. The paper concludes that the B-EAS has the ability to find better solution than EAS for a set of benchmarks from the TSPLib library.References
Afshar, M.H. (2005); A new transition rule for ant colony optimization algorithms: application to pipe network optimization problems, Engineering Optimization, 37 (5): 525-540. https://doi.org/10.1080/03052150500100312
Blum, C.; Roli, A.; Dorigo, M. (2001); HC-ACO: The Hyper-Cube Framework for Ant Colony Optimization, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 399- 403.
Bullnheimer, B.; Hartl, R.F.; Strauss, C. (1999); A New Rank Based Version of the Ant System: A Computational Study, Central European Journal for Operations Research and Economics, 25-38.
Cordón, O.; de Viana, I.F.; Herrera, F.; Moreno, L. (2000); A new ACO model integrating evolutionary computation concepts: The best-worst Ant System. In M. Dorigo, M. Middendorf, & T. Stuützle (Eds.), Abstract Proceedings of ANTS 2000-From Ant Colonies to Artificial Ants: Second International Workshop on Ant Algorithms, Brussels, IRIDIA, Université Libre de Bruxelles, 22-29.
Dorigo, M.; Maniezo, V.; Colorni, A. (1996); Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26 (1): 29-41. https://doi.org/10.1109/3477.484436
Dorigo, M.; Gambardella, L. (1997); Ant Colony System: A Cooperative Learning. IEEE Transactions of Evolutionary Computation, 1 (1): 53-66. https://doi.org/10.1109/4235.585892
Google (2016). Google Trends, Retrieved from https://www.google.com/trends/explore? q=AntColonyOptimization.
Goss, S.; Aron, S.; Deneubourg, J.L.; Pasteels, J.M. (1989); Self-organized shortcuts in the Argentine ant, Naturwissenschaften, 76, 579-581, Springer-Verlag. https://doi.org/10.1007/BF00462870
Gutjahr, W.J. (2000). A Graph-based Ant System and its convergence, Future Generation Computer Systems, 873-888. https://doi.org/10.1016/S0167-739X(00)00044-3
Kerns, G. (2011); Introduction to Probability and Statistics Using R, IPSUR, ISBN: 978-0- 557-24979-4.
Negulescu, S.; Dzitac, I.; Lascu, A. (2010); Synthetic Genes for Artificial Ants. Diversity in Ant Colony Optimization Algorithms, International Journal of Computers Communication & Control, 5 (2): 216-223. https://doi.org/10.15837/ijccc.2010.2.2476
Reinelt, G. (1991); TSPLIB - A Traveling Salesman Problem Library. ORSA Journal on Computing, 376-384. https://doi.org/10.1287/ijoc.3.4.376
Susnea, I.; Axenie, C. (2015); Cognitive maps for indirect coordination of intelligent agents, Studies in Informatics and Control, 24(1): 111-118.
Tuba, M.; Jovanovic, R.(2013); Improved ACO Algorithm with Pheromone Correction Strategy for the Traveling Salesman Problem, International Journal of Computers Communications & Control, 8(3): 477-485. https://doi.org/10.15837/ijccc.2013.3.7
Wei, X.; Han, L.; Hong, L. (2014); A modified ant colony algorithm for traveling salesman problem, International Journal of Computers Communications & Control, 9(5): 633-643. https://doi.org/10.15837/ijccc.2014.5.1280
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
