META HEURISTICA BASADA EN COLONIA DE HORMIGAS EN N ETAPAS PARA PROBLEMAS DE ALTA DIMENSION

• Published in: Investigación operacional 2022-10, Vol.43 (4), p.484
• Main Authors: Hernández, Daniel, Hurtado, Steven, Pérez, Henry, Puris, Amilkar, Novoa-Hernández, Pavel
• Format: Article
• Language: Spanish
• ISSN: 0257-4306

Ant Colony Optimization is a population metaheuristic inspired by the behavior of natural ants, specifically their ability to find the shortest path between their nest and the food source. This search mechanism has been tested in discrete problems, establishing itself as a good option for this field of application. In previous works, it was shown that dividing the exploration process of these algorithms into 2 stages considerably improves their performance in terms of time and the quality of the results. In this context, we present, in this work, a generalization of the exploitation process by stages for instances of the Medium and High-Dimension of the Traveling Salesman Problem. For the tests, 5 instances of different sizes were selected and 4 variants of the algorithm were analyzed. The results corroborated that the process of division into stages is good for the performance of the algorithm, reaching the best results with 4 stages. KEYWORDS: Ant Colony System (ACS), Two-Stage Ant Colony Optimization (TS-ACO), Travel Salesman Problem (TSP). MSC: 91B32 La optimización basada en Colonia de Hormigas es una metaheurística poblacional inspirada en el comportamiento de las hormigas naturales, específicamente en su capacidad de encontrar el camino más corto entre su nido y la fuente de alimento. Este mecanismo de búsqueda ha sido probado en problemas discretos consolidándose como una buena opción para este campo de aplicación. En trabajos previos, se demostró que dividir en 2 etapas el proceso de exploración de estos algoritmos, mejora considerablemente su rendimiento en cuanto al tiempo y la calidad de los resultados. En este contexto, presentamos, en este trabajo una generalización del proceso de explotación por etapas para instancias del Viajante de Comercio de mediana y alta dimensión. Para las pruebas se seleccionaron 5 instancias de diferentes tamaños y se analizaron 4 variantes del algoritmo. Los resultados corroboraron que el proceso de división en etapas es beneficioso para el rendimiento del algoritmo alcanzando los mejores resultados con 4 etapas. PALABRAS CLAVES: Sistema de Colonia de Hormigas (ACS), Optimización de Colonia de Hormigas en N Etapas (NS-ACO), Problema del Viajante de Comercio (TSP)