Análisis del Ómicron ACO con optimización local

Abstract

La optimización por Colonia de Hormigas (Ant Colony Optimization o ACO) es una metaheurística inspirada por el comportamiento de búsqueda de alimentos de las hormigas. Esta metaheurística ha sido exitosamente empleada en la resolución de difíciles problemas de optimización combinatoria como el problema del cajero viajante (Traveling Salesman Problem o TSP). El presente artículo analiza el desempeño del Ómicron ACO (OA), una nueva alternativa de algoritmo ACO, comparándolo con el MAX-MIN Ant System (MMAS), uno de los ACO más reconocidos, en la resolución de dos instancias del TSP de 100 y 442 ciudades respectivamente. Con el objeto de realizar una comparación completa, se incluye un optimizador local (Local Search) como acelerador de convergencia, verificándose experimentalmente ciertas ventajas del OA sobre el más tradicional MMAS.