Paralelismo aplicado a Ant Colony Optimization

Abstract

La utilización de metaheurísticas para la resolución de problemas de optimización combinatoria del tipo NP-difícil ha permitido afrontar instancias grandes obteniendo soluciones cercanas al óptimo en tiempos razonables. En los últimos años la aplicación de paralelismo a las metaheurísticas ha demostrado su utilidad no solamente porque ha permitido disminuir considerablemente los tiempos de ejecución, sino también porque ha permitido obtener mejoras en la calidad de las soluciones encontradas. Ant Colony Optimization (ACO) es una metaheurística de las más recientes que ha sido aplicada con éxito sobre varios de los problemas estándares de optimización demostrando su potencial. Las primeras propuestas de paralelismo aplicado a ACO se remontan a los orígenes de la propia metaheurística. Sin embargo, la investigación en esta temática ha crecido notablemente en los últimos cinco años. El presente reporte es un relevamiento sobre la aplicación de técnicas de alto desempeño sobre ACO. El objetivo de este relevamiento es brindar un resumen de las principales propuestas existentes en la literatura sobre esta temática. Solamente se consideran las implementaciones paralelas aplicadas sobre problemas estáticos monobjetivos de optimización combinatoria.