Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC. Authors must sign a non-exclusive distribution agreement after article acceptance.
A Many-objective Ant Colony Optimization applied to the Traveling Salesman Problem
Keywords:
ant colony optimization, traveling salesman problem, many-objective optimization, hypervolume, NSGA2Abstract
Evolutionary algorithms present performance drawbacks when applied to Many-objective Optimization Problems (MaOPs). In this work, a novel approach based on Ant Colony Optimization theory (ACO), denominated ACO λ base-p algorithm, is proposed in order to handle Manyobjective instances of the well-known Traveling Salesman Problem (TSP). The proposed algorithm was applied to several Many-objective TSP instances, verifying the quality of the experimental results using the Hypervolume metric. A comparison with other state-of-the-art Multi Objective ACO algorithms as MAS, M3AS and MOACS as well as NSGA2 evolutionary algorithm was made, verifying that the best experimental results were obtained when the proposed algorithm was used, proving a good applicability to MaOPs.
Downloads
Download data is not yet available.
References
[1] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The travelling salesman problem. Wiley, New York (1985)
[2] Barán, B., Schaerer, M.: A multiobjective Ant Colony System for Vehicle Routing Problems with Time Windows. Proc. Twenty first IAS-TED International Confe-rence on Applied Informatics, pp. 97–102. Insbruck, Austria (2003)
[3] Pinto, D., Barán, B.: Solving Multiobjective Multicast Routing Problem with a new Ant Colony Optimization approach. In Proceedings of the 3rd international IFIP/ACM Latin American conference on Networking, pp. 11-19, Cali, Colombia (2005)
[4] Paciello, J., Martı́nez, H., Lezcano, C., Barán, B.: Algoritmos de Optimización multi-objetivos basados en colonias de hormigas. XXXII Conferencia Latinoamericana de Informática - CLEI’2006. Santiago de Chile (2006).
[5] vön Lücken, C., Barán, B., Brizuela, C.: A survey on multy-objective evolucionay algorithms for many-objective problems. Computational Optimization and Applications 58, no. 3, pp. 707–756, (2014)
[6] Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: The Travelling Salesman Problem. Wiley, New York (1985)
[7] Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: A short review. In IEEE Congress on Evolutionary Computation CEC’2008, pp. 2419-2426 (2008)
[8] Barán, B., Gómez, O.: Reasons of ACO’s Success in TSP, ANTS’2004 - Fourth International Workshop on Colony Optimization and Swarm Intelligence. Bruselas, Bélgica. (2004)
[9] Martı́nez, H., Paciello, J., Barán, B.: Equipo distribuido de algoritmos ACO multiobjetivos. VIII Argentine Symposium on Artificial Intelligence - ASAI, 35 tz Jornadas Argentinas de Informática e Investigación Operativa- 35 JAIIO. Mendoza, Argentina (2006)
[10] Paciello, J., Martı́nez, H., Barán, B.: Aplicación de un equipo de algoritmos ACO al VRPTW bi-objetivo. XIII Conferencia Latino-IberoAmericana de Investigación Operativa -CLAIO’2006. Montevideo, Uruguay (2006)
[11] Zitzler, E.: Evolutionary algorithms for multiobjective optimization: Methods and applications. Vol. 63. Ithaca: Shaker, (1999)
[12] Riquelme, N., vön Lücken, C., Barán, B.: Perfomance metrics in multi-objective optimization. XLI Latinoamerican Conference on Informatics - CLEI’2015. Arequipa Peru 2015
[13] While, L., Hingston, P., Barone, L., Huband, S.: A faster algorithm for calculating hypervolume. Evolutionary Computation, IEEE Transactions on, 10 no. 1, pp. 29–38 (2006)
[14] Optymalizacji, H. M., Kot, K., Pietraszko, A.: Heurystyczne metody wielokryterialnej optymalizacji kombinatorycznej. Akademia Górniczo-Hutnicza Thesis (2009)
[2] Barán, B., Schaerer, M.: A multiobjective Ant Colony System for Vehicle Routing Problems with Time Windows. Proc. Twenty first IAS-TED International Confe-rence on Applied Informatics, pp. 97–102. Insbruck, Austria (2003)
[3] Pinto, D., Barán, B.: Solving Multiobjective Multicast Routing Problem with a new Ant Colony Optimization approach. In Proceedings of the 3rd international IFIP/ACM Latin American conference on Networking, pp. 11-19, Cali, Colombia (2005)
[4] Paciello, J., Martı́nez, H., Lezcano, C., Barán, B.: Algoritmos de Optimización multi-objetivos basados en colonias de hormigas. XXXII Conferencia Latinoamericana de Informática - CLEI’2006. Santiago de Chile (2006).
[5] vön Lücken, C., Barán, B., Brizuela, C.: A survey on multy-objective evolucionay algorithms for many-objective problems. Computational Optimization and Applications 58, no. 3, pp. 707–756, (2014)
[6] Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: The Travelling Salesman Problem. Wiley, New York (1985)
[7] Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: A short review. In IEEE Congress on Evolutionary Computation CEC’2008, pp. 2419-2426 (2008)
[8] Barán, B., Gómez, O.: Reasons of ACO’s Success in TSP, ANTS’2004 - Fourth International Workshop on Colony Optimization and Swarm Intelligence. Bruselas, Bélgica. (2004)
[9] Martı́nez, H., Paciello, J., Barán, B.: Equipo distribuido de algoritmos ACO multiobjetivos. VIII Argentine Symposium on Artificial Intelligence - ASAI, 35 tz Jornadas Argentinas de Informática e Investigación Operativa- 35 JAIIO. Mendoza, Argentina (2006)
[10] Paciello, J., Martı́nez, H., Barán, B.: Aplicación de un equipo de algoritmos ACO al VRPTW bi-objetivo. XIII Conferencia Latino-IberoAmericana de Investigación Operativa -CLAIO’2006. Montevideo, Uruguay (2006)
[11] Zitzler, E.: Evolutionary algorithms for multiobjective optimization: Methods and applications. Vol. 63. Ithaca: Shaker, (1999)
[12] Riquelme, N., vön Lücken, C., Barán, B.: Perfomance metrics in multi-objective optimization. XLI Latinoamerican Conference on Informatics - CLEI’2015. Arequipa Peru 2015
[13] While, L., Hingston, P., Barone, L., Huband, S.: A faster algorithm for calculating hypervolume. Evolutionary Computation, IEEE Transactions on, 10 no. 1, pp. 29–38 (2006)
[14] Optymalizacji, H. M., Kot, K., Pietraszko, A.: Heurystyczne metody wielokryterialnej optymalizacji kombinatorycznej. Akademia Górniczo-Hutnicza Thesis (2009)
Downloads
Published
2016-11-01
How to Cite
Riveros, F., Benítez, N., Paciello, J., & Barán, B. (2016). A Many-objective Ant Colony Optimization applied to the Traveling Salesman Problem. Journal of Computer Science and Technology, 16(02), p. 89–94. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/496
Issue
Section
Invited Articles
