🐜 Colonia de Hormigas

El Problema del Viajante de Comercio (TSP) plantea: dadas N ciudades, ¿cuál es el recorrido cerrado más corto que visita cada ciudad exactamente una vez y vuelve al inicio? Es NP-difícil, lo que significa que no existe un algoritmo exacto conocido de tiempo polinómico para N grande; el número de recorridos posibles crece como (N−1)!/2. Para 20 ciudades eso son más de 60 billones de recorridos. ACO normalmente encuentra soluciones casi óptimas mucho más rápido que la búsqueda exhaustiva, lo que lo hace práctico para problemas logísticos reales con cientos o miles de ciudades.

Una tasa de evaporación alta (ρ cercano a 1) significa que la feromona se disipa rápidamente, manteniendo todas las aristas casi igual de atractivas y favoreciendo una exploración amplia pero ralentizando la convergencia. Una tasa baja (ρ cercano a 0) permite que la feromona se acumule durante muchas iteraciones, reforzando las mejores rutas encontradas al principio pero arriesgándose al estancamiento. En la práctica, valores de 0,1–0,3 tienden a equilibrar bien la exploración y la explotación para instancias de TSP de tamaño moderado.

α es el exponente que controla cuánto favorecen las hormigas las aristas con alta feromona; β controla cuánto favorecen las aristas cortas (de bajo coste). Con β=5 y α=1 (valores típicos del artículo original de Dorigo), la distancia heurística domina al principio cuando la feromona es uniforme, dando recorridos iniciales sensatos, mientras que la feromona va desplazando gradualmente el equilibrio. Un α demasiado alto hace que el algoritmo dependa en exceso de depósitos de feromona tempranos, posiblemente deficientes.

Sí — ACO se ha adaptado a la coloración de grafos, la programación de talleres, la predicción de estructuras de proteínas e incluso la optimización continua (ACOR). En el enrutamiento de redes, el Enrutamiento Basado en Hormigas (ABR) envía «paquetes exploradores» que sondean rutas y depositan feromona digital, reencaminando dinámicamente el tráfico alrededor de la congestión. Cisco ha implementado variantes de esta idea en algoritmos de enrutamiento adaptativo para redes de telecomunicaciones.

La estigmergia es la coordinación indirecta mediante la modificación del entorno — los agentes se comunican cambiando el entorno compartido en lugar de mediante señales directas. Los rastros de feromona de las hormigas son el ejemplo canónico: cada hormiga responde a los rastros dejados por hormigas anteriores, y su propio rastro influye en las hormigas futuras, sin ningún controlador central. La estigmergia también se observa en la construcción de montículos de termitas, la construcción de nidos de avispas, y ha inspirado arquitecturas de computación distribuida.

ACO puede sufrir estancamiento, donde todas las hormigas convergen en un recorrido subóptimo y la diversidad de feromona colapsa. También requiere un ajuste cuidadoso de parámetros (α, β, ρ, número de hormigas), y su tasa de convergencia es generalmente más lenta que la de algoritmos especializados para problemas bien estudiados como el TSP. Los sistemas ACO híbridos que combinan la búsqueda basada en hormigas con heurísticas de mejora local (movimientos 2-opt o 3-opt) suelen rendir mucho mejor que el ACO puro en instancias grandes.

Una regla general habitual es usar una hormiga por ciudad. Más hormigas aumentan la diversidad de soluciones y reducen la posibilidad de convergencia prematura, pero también incrementan el cómputo por iteración. Las investigaciones han demostrado que, para el TSP, entre 10 y 50 hormigas suelen dar buenos resultados en instancias de hasta 200 ciudades, mientras que instancias muy grandes pueden beneficiarse de cientos de hormigas con computación paralela. El número ideal interactúa con ρ: una evaporación más rápida puede compensar tener menos hormigas manteniendo la diversidad.