Extensión de algoritmos ACO usando conceptos de Tabu Search

Abstract

En los algoritmos ACO (del inglés Ant Colony Optimization) las hormigas artificiales iterativamente construyen soluciones a un problema de optimización combinatorio. La construcción de dichas soluciones está guiada por rastros de feromona los cuales actúan como un mecanismo de adaptación que permite sesgar la muestra de nuevas soluciones hacia regiones prometedoras del espacio de búsqueda. Adicionalmente, el sesgo de la búsqueda está influenciado por información heurística dependiente del problema. En este trabajo, que describe parte de la línea de investigación relacionada al uso de memoria externa en algoritmos ACO, se propone la incorporación de conceptos de la metaheurística Tabu Search (TS) en el proceso de construcción de soluciones. Estos conceptos se refieren específicamente a la forma en la que TS utiliza la historia del proceso de búsqueda para evitar visitar soluciones ya analizadas.