The Ant Heuristic “Reloaded”
Abstract
As a swarm-based optimization heuristic, the Ant System (AS) was proposed to deal with the Traveling Salesman Problem (TSP). Classifified as a constructive approach, AS was inspired by the ants’ social behavior.In Practice, its implementation reveals three basic variants that exploit two operating models: a fifirst “natural” model, where ants move and update pheromones, with consideration of distances between towns, to defifine the Ant-Quantity variant, and without considering distances for the Ant-Density variant. Or an “abnormal” second model, where ants move and delay updates until all ants have completed a full cycle, then consider the tour length which defifines the Ant-Cycle that was claimed to be the best variant. We reload the AS and reconsider these three basic ant algorithms and their respective two models. We propose to explore an “overlooked” third model, which consists of further expanding the “abnormal” ants’ attitude, forcing them to move and update pheromones, simultaneously, after every single move, thus conceiving the Ant-Step model. Keeping the option whether or not to consider distances, we propose two new AS basic algorithms: the Ant-Step-Quantity and the Ant-Step-Density. The aim of this paper is to present and assess these two new basic AS variants in respect to the three existing ones, specially the one considered the best, through an experimental study on various symmetric TSP benchmarks.References
E. Bonomi, and J. L. Lutton, The N-city travelling salesman problem: Statistical mechanics and the metropolis algorithm, SIAM review, vol. 26, no. 4, pp. 551–568, 1984.
M. R. Bonyadi, M. R. Azghadi, and H. S. Hosseini, Population-Based Optimization Algorithms for Solving the Travelling Salesman Problem, Travelling Salesman Problem, BoD–Books on Demand, pp. 1–34, 2008.
B. Bullnheimer, R. F. Hartl, and C. Strauss, A new rank based version of the Ant System. A computational study, SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 1997.
B. Bullnheimer, R. F. Hartl, and C. Strauss, An improved ant System algorithm for thevehicle Routing Problem, Annals of operations research, Springer, vol. 89, pp. 319–328, 1999.
S. S. Chen, and C. W. Shih, Solving TSP by Transiently Chaotic Neural Networks, Travelling Salesman Problem, BoD–Books on Demand, pp. 117–134, 2008.
S. S. Choong, L. Wong, and C. P. Lim, An artificial bee colony algorithm with a modified choice function for the Traveling Salesman Problem, Swarm and evolutionary computation, Elsevier, vol. 44, pp. 622–635, 2019.
A. Colorni, M. Dorigo, and V. Maniezzo, Distributed optimization by ant colonies, Proceedings of the first European conference on artificial life, vol. 142, pp. 134–142, 1991.
D. Costa, and A. Hertz, Ants can colour graphs, Journal of the operational Research Society, Palgrave Macmillan, vol. 48. no. 3, pp. 295–305, 1997.
M. Dorigo, V. Maniezzo, and A. Colorni, The ant system: An autocatalytic optimizing process, Italy: Dipartimento di Elettronica, Politecnico di Milano, pp. 91–116, 1991.
M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: optimization by a colony of cooperating agents, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, IEEE, vol. 26, no. 1, pp. 29–41, 1996.
M. Dorigo, and L.M. Gambardella, Ant colonies for the travelling salesman problem, BioSystems, Elsevier, vol. 43, no. 2, pp. 73–81, 1997.
M. Dorigo, and G. Di Caro, Ant colony optimization: a new meta-heuristic, Evolutionary Computation, CEC 99. Proceedings of the 1999 Congress on, IEEE, vol. 2, pp. 1470–1477, 1999.
J. Dr´eo, A. P´etrowski, P. Siarry and E. Taillard, Metaheuristics for hard optimization: methods and case studies, Springer Science & Business Media, 2006.
C. N. Fiechter, A parallel tabu search algorithm for large scale traveling salesman problems, Working Paper 90/1, D´epartement de math´ematiques, ´Ecole Polytechnique F´ed´erale de Lausanne, 1990.
E. FG. Goldbarg, M. C. Goldbarg, and G. R. de Souza, Particle swarm optimization algorithm for the traveling salesman problem, Travelling Salesman Problem, BoD–Books on Demand, pp. 75–96, 2008.
B. L. Golden, and C. Skiscim, Using simulated annealing to solve routing and location problems, Naval Research Logistics Quarterly, Wiley Online Library, vol. 33, no. 2, pp. 261–279, 1986.
F. Greco, Traveling salesman problem, BoD–Books on Demand, 2008.
H. Joshi, and S. Arora, Enhanced grey wolf optimization algorithm for global optimization, Fundamenta Informaticae, IOS Press, vol. 153, no. 3, pp. 235–264, 2017.
J. E. Knox, The application of tabu search to the symmetric traveling salesman problem, University of Colorado at Boulder, 1989.
N. Kumbharana, and G. M. Pandey, A comparative study of ACO, GA and SA for solving travelling salesman problem, International Journal of Societal Applications of Computer Science, vol. 2, no. 2, pp. 224–228, 2013.
G. Laporte, The traveling salesman problem: An overview of exact and approximate algorithms, European Journal of Operational Research, vol. 59. n. 2. North-Holland, pp. 231–247, 1992.
W.H. Li, W.J. Li, Y. Yang, H.Q. Liao, J.L. Li, and X.P. Zheng, Artificial bee colony algorithm for traveling salesman problem, Advanced materials research, Trans Tech Publ, vol. 314, pp. 2191–2196, 2011.
Y. H. Liu, Solving the probabilistic travelling salesman problem based on genetic algorithm with queen selection scheme, Traveling Salesman Problem, Federico Greco. Vienna, Austria, pp. 157–172, 2008.
M. Malek, Search methods for traveling salesman problems, Department of Electrical Engineering, The University of Texas, Austin, 1988.
V. Maniezzo, and A. Colorni, The ant system applied to the quadratic assignment problem, Knowledge and Data Engineering, IEEE Transactions on, IEEE, vol. 11, no. 5, 769–778, 1999.
S. Nahar, S. Sahni, and E. Shragowitz, Simulated annealing and combinatorial optimization, 23rd ACM/IEEE Design Automation Conference, pp. 293–299, 1986.
H.V.D. Parunak, “Go to the ant”: Engineering principles from natural multi-agent systems, Annals of Operations Research Journal, JC BALTZER AG, vol. 75, pp. 69–102, 1997.
Y. Rossier, M. Troyon, and Th. M. Liebling, Probabilistic exchange algorithms and Euclidean traveling salesman problems, Operations-Research-Spektrum, Springer, vol. 8, no. 3, pp. 151–164, 1986.
D. S. Sopto, S. I. Ayon, M. Akhand, and N. Siddique, Modified Grey Wolf Optimization to Solve Traveling Salesman Problem, International Conference on Innovation in Engineering and Technology (ICIET), IEEE, pp. 1–4, 2018.
T. St¨utzle, and H. Hoos, Improvements on the ant-system: Introducing the MAX-MIN ant system, Artificial Neural Nets and Genetic Algorithms, Springer, pp. 245–249, 1998.
T. St¨utzle, and H. Hoos, The max-min ant system and local search for combinatorial optimization problems, Meta-heuristics, Springer, pp. 313–329, 1999.
M. F. Tasgetiren, Y. C. Liang, Q. K. Pan, and PN. Suganthan, A Modified Discrete Particle Swarm Optimization Algorithm for the Generalized Traveling Salesman Problem, Travelling Salesman Problem, BoD–Books on Demand, pp. 97–116, 2008.
J. Wei, Approaches to the travelling salesman problem using evolutionary computing algorithms, Travelling Salesman Problem, BoD–Books on Demand, pp. 63–74, 2008.
D. Zeghida, F. Michel, and D. Meslati, An agent-based model for biomorphic software systems, Complex Systems, ICCS’2012, IEEE International Conference on, IEEE, pp. 1–6, 2012.
D. Zeghida, D. Meslati, N. Bounour, and Y. Allat, Agent Influence/Reaction Ant System Variants: An Experimental Comparison, International Journal of Artificial Intelligence, Ceser Publications, vol. 16, no. 2, pp. 60–77, 2018.
D. Zeghida, N. Bounour, and D. Meslati. The Ant-Step Algorithms: Reloading the Ant System Heuristic and the Overlooked Basic Variants , 2020 IEEE 2nd International Conference on Electronics, Control, Optimization and Computer Science (ICECOCS), IEEE, pp. 1–6, 2020.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
