SMART: Solution Methods with Ants Running by Types

Authors: Nicolas Zufferey

Abstract:

Ant algorithms are well-known metaheuristics which have been widely used since two decades. In most of the literature, an ant is a constructive heuristic able to build a solution from scratch. However, other types of ant algorithms have recently emerged: the discussion is thus not limited by the common framework of the constructive ant algorithms. Generally, at each generation of an ant algorithm, each ant builds a solution step by step by adding an element to it. Each choice is based on the greedy force (also called the visibility, the short term profit or the heuristic information) and the trail system (central memory which collects historical information of the search process). Usually, all the ants of the population have the same characteristics and behaviors. In contrast in this paper, a new type of ant metaheuristic is proposed, namely SMART (for Solution Methods with Ants Running by Types). It relies on the use of different population of ants, where each population has its own personality.

Keywords: Optimization, Metaheuristics, Ant Algorithms, Evolutionary Procedures, Population-Based Methods.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1338622

References:

[1] N. Zufferey, “Metaheuristics: some Principles for an Efficient Design,” Computer Technology and Applications, vol. 3 (6), pp. 446 – 462, 2012.
[2] M. Gendreau and J.-Y. Potvin, Handbook of Metaheuristics, ser. International Series in Operations Research & Management Science. Springer, 2010, vol. 146.
[3] M. Dorigo, “Optimization, learning and natural algorithms (in Italian),” Ph.D. dissertation, Politecnico di Milano, Dipartimento di Elettronica, Italy, 1992.
[4] C. Blum, “Ant colony optimization: Introduction and recent trends,” Physics of Life Reviews, vol. 2(4), pp. 353–373, 2005.
[5] M. Dorigo, M. Birattari, and T. Stuetzle, “Ant colony optimization – artificial ants as a computational intelligence technique,” IEEE Computational Intelligence Magazine, vol. 1 (4), pp. 28–39, 2006.
[6] M. Dorigo and T. Stuetzle, Handbook of Metaheuristics. In F. Glover and G. Kochenberger (Eds), 2003, vol. 57, ch. The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, pp. 251–285.
[7] N. Zufferey, “Optimization by ant algorithms: Possible roles for an individual ant,” Optimization Letters, vol. 6 (5), pp. 963 – 973, 2012.
[8] “Design and classification of ant metaheuristics,” in Proceedings of the 22nd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2014), Turin, Italy, February 12 – 14 2014.
[9] L. Luyet, S. Varone, and N. Zufferey, “An Ant Algorithm for the Steiner Tree Problem in Graphs,” Lecture Notes in Computer Science, vol. 4448, pp. 42 – 51, 2007.
[10] N. Zufferey, J. Farres, and R. Glardon, “Ant metaheuristics with adapted personalities for the vehicle routing problem,” in Proceedings of the 6th International Conference on Computational Logistics (ICCL 2015), Delft, Nederland, September 23 – 25 2015.
[11] M. Plumettaz, D. Schindl, and N. Zufferey, “Ant local search and its efficient adaptation to graph colouring,” Journal of the Operational Research Society, vol. 61, pp. 819 – 826, 2010.
[12] A. Hertz, D. Schindl, and N. Zufferey, “Lower bounding and tabu search procedures for the frequency assignment problem with polarization constraints,” 4OR, vol. 3 (2), pp. 139 – 161, 2005.
[13] J.-F. Cordeau, M. Gendreau, A. Hertz, G. Laporte, and J.-S. Sormany, Logistics Systems: Design and Optimization. Springer, 2005, ch. New Heuristics for the Vehicle Routing Problem, pp. 270–297.
[14] J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, and F. Semet, “A Guide to Vehicle Routing Heuristics,” Journal of the Operational Research Society, vol. 53 (5), pp. 512–522, 2002.
[15] J.-F. Cordeau and G. Laporte, Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search. Boston: Kluwer, 2004, ch. Tabu search heuristics for the vehicle routing problem, pp. 145–163.
[16] M. Gendreau, G. Laporte, and J.-Y. Potvin, The Vehicle Routing Problem. Philadelphia: SIAM Monographs on Discrete Mathematics and Applications, 2002, ch. Metaheuristics for the VRP, pp. 129–154.
[17] B. L. Golden, E. A. Wasil, J. P. Kelly, and I.-M. Chao, Fleet Management and Logistics. Boston: Kluwer, 1998, ch. Metaheuristics in vehicle routing, pp. 33–56.
[18] G. Laporte and F. Semet, The Vehicle Routing Problem. Philadelphia: SIAM Monographs on Discrete Mathematics and Applications, 2002, ch. Classical heuristics for the capacitated VRP, pp. 109–128.
[19] S. Lin, “Computer solutions of the traveling salesman problem,” Bell System Technical Journal, vol. 44, pp. 2245–2269, 1965.
[20] I. Or, “Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking,” Ph.D. dissertation, Nortwester University, USA, 1976.
[21] N. Christofides, A. Mingozzi, and P. Toth, Combinatorial Optimization, 1979, ch. The vehicle routing problem, pp. 315 – 338.
[22] D. Mester and O. Braysy, “Active-guided evolution strategies for large-scale capacitated vehicle routing problems,” Computers & Operations Research, vol. 34 (10), pp. 2964 – 2975, 2007.