Algoritmo de Colonia de Hormigas

El algoritmo de colonia de hormigas (ACO, por sus siglas en inglés) es una metaheurística de optimización inspirada en el comportamiento de las hormigas reales, útil para resolver problemas que se pueden reducir a encontrar buenos caminos a través de un grafo. Pertenece a la llamada inteligencia de enjambre: individuos simples que, en conjunto, resuelven problemas complejos.

La idea biológica

El truco está en las feromonas. Cuando las hormigas buscan comida, dejan un rastro químico al desplazarse. Los caminos más cortos se recorren más veces en el mismo tiempo, así que acumulan más feromona, lo que atrae a más hormigas, en un refuerzo positivo que hace que la colonia converja hacia la ruta óptima sin que ninguna hormiga la calcule. La feromona, además, se evapora con el tiempo, lo que evita que la colonia se quede atrapada demasiado pronto en una solución mediocre.

Del hormiguero al algoritmo

ACO traslada esa idea al ordenador. «Hormigas» artificiales construyen soluciones paso a paso, de forma probabilística, guiadas por dos cosas: el rastro de feromona —una memoria colectiva de qué caminos han funcionado— y una información heurística del problema. Las mejores soluciones refuerzan su feromona, y esta se evapora poco a poco. Repitiendo el ciclo, la colonia va afinando la respuesta.

De dónde viene

Lo propuso Marco Dorigo en su tesis doctoral de 1992, en el Politécnico de Milán; su primer algoritmo, el Ant System, se aplicó al problema del viajante. Después llegaron variantes más refinadas, como el Ant Colony System o el MAX-MIN Ant System.

Para qué sirve

Es una herramienta de optimización combinatoria. Su ejemplo canónico es el problema del viajante (hallar la ruta más corta que visita una serie de ciudades), y se aplica al enrutamiento en redes, la logística y el reparto, la planificación y la asignación. Comparte familia con otras metaheurísticas, como los algoritmos genéticos o el recocido simulado, pero se distingue por su enfoque constructivo: no retoca soluciones completas, sino que las va edificando.