Observa cómo una metaheurística real de Optimización por Colonia de Hormigas evoluciona en vivo las rutas de drones de reparto, con un refuerzo genuino de rastros de feromonas que converge hacia rutas multi-parada más cortas a lo largo de colonias sucesivas.
Esta simulación pone en práctica un algoritmo real de Optimización por Colonia de Hormigas (ACO) en un problema de enrutamiento de reparto por drones multi-parada: un dron debe visitar cada punto de entrega exactamente una vez y regresar a la base, el clásico Problema del Viajante. En lugar de guionizar una ruta, la página mantiene una matriz de feromonas τ genuina sobre cada par de puntos de entrega. En cada colonia, cada hormiga simulada construye un recorrido completo eligiendo repetidamente su siguiente parada no visitada con probabilidad proporcional a τ(i,j)α · η(i,j)β, donde η(i,j) = 1/distancia(i,j) es la deseabilidad heurística de un salto corto. Una vez que cada hormiga de la colonia ha terminado su recorrido, la feromona se evapora por un factor (1 − ρ) y cada hormiga deposita nueva feromona proporcional a Q / L en los tramos de la ruta que construyó, así que las rutas más cortas refuerzan sus tramos mucho más fuertemente que las largas.
Ejecuta esto durante suficientes colonias y el mapa de rastros se afila visiblemente: los tramos débiles y poco usados se desvanecen mientras un puñado de tramos —los que siguen apareciendo en los recorridos más cortos— se vuelven más brillantes, y la longitud de la mejor ruta conocida (rastreada en el gráfico en vivo) sigue disminuyendo. Puedes ajustar en vivo el número de puntos de entrega, el número de hormigas por colonia y la tasa de evaporación ρ, junto con los exponentes de peso de feromona α y peso de distancia β que controlan cuán fuertemente confían las hormigas en la experiencia de la colonia frente a la distancia bruta. Nada aquí está guionizado o precocinado: cada colonia realmente vuelve a derivar sus rutas a partir del estado actual de feromonas y las decisiones aleatorias de las hormigas, así que reiniciar con un mapa nuevo o parámetros diferentes produce una curva de convergencia distinta cada vez.
¿Qué es la Optimización por Colonia de Hormigas y qué problema resuelve aquí?
La Optimización por Colonia de Hormigas (ACO) es una metaheurística inspirada en cómo las hormigas reales encuentran caminos cortos entre su nido y la comida usando rastros de feromonas. En esta simulación resuelve un problema de enrutamiento de reparto multi-parada: un dron debe visitar cada punto de entrega exactamente una vez y regresar a la base, que es el clásico Problema del Viajante (TSP). El TSP es NP-difícil, así que más allá de un puñado de paradas resulta impráctico comprobar cada ordenamiento posible. ACO ejecuta muchas hormigas simuladas que construyen rutas candidatas de forma probabilística, reforzando los tramos que tienden a aparecer en rutas cortas, así la población de rutas mejora a lo largo de colonias sucesivas sin llegar nunca a demostrar la optimalidad.
¿Cómo decide la regla de probabilidad de transición de ACO a dónde va cada hormiga?
En cada paso, una hormiga situada en el punto de entrega i elige su siguiente parada no visitada j con probabilidad proporcional a [τ(i,j)]^α × [η(i,j)]^β, donde τ(i,j) es el nivel de feromona en el tramo (i,j) y η(i,j) = 1/distancia(i,j) es la deseabilidad heurística: los puntos más cercanos parecen más atractivos. α controla cuán fuertemente la hormiga sigue la experiencia acumulada de la colonia (feromona), mientras que β controla cuán fuertemente sigue la distancia puramente codiciosa. Luego la hormiga hace un sorteo aleatorio ponderado (tipo ruleta) entre todos los candidatos no visitados usando estas puntuaciones combinadas, así que generalmente —aunque no siempre— elige un tramo prometedor, lo que mantiene a la colonia explorando.
¿Por qué se evapora la feromona y qué controla la tasa de evaporación ρ?
Después de que cada colonia termina sus recorridos, todos los valores de feromona se multiplican por (1 − ρ) antes de agregar nuevos depósitos. Sin evaporación, la feromona solo se acumularía, y los tramos que tuvieron suerte temprano dominarían para siempre, atrapando la búsqueda en una solución mediocre. La evaporación permite que los rastros débiles o antiguos se desvanezcan para que la colonia pueda seguir explorando rutas alternativas. Una ρ alta olvida la historia rápidamente y explora más, pero converge más lenta y ruidosamente; una ρ baja recuerda más tiempo y converge más rápido, pero arriesga fijarse en una ruta temprana y subóptima (convergencia prematura).
Después de la evaporación, cada hormiga de la colonia deposita feromona de magnitud Q / L en cada tramo de la ruta que construyó, donde L es la longitud total de la ruta de esa hormiga y Q es una constante fija. Como el depósito es inversamente proporcional a la longitud, una hormiga que encontró una ruta corta refuerza sus tramos mucho más fuertemente que una que encontró una ruta larga e ineficiente. A lo largo de muchas colonias, este refuerzo diferencial es lo que convierte una búsqueda puramente aleatoria en una que concentra la feromona —y por lo tanto el tráfico futuro de hormigas— en los tramos que aparecen repetidamente en rutas cortas.
Establecer α = 0 hace que las hormigas ignoren la feromona por completo y se comporten como una heurística codiciosa tipo vecino más cercano impulsada solo por η (distancia), así que no se forma memoria de colonia y hay poca mejora con el tiempo. Establecer β = 0 hace que las hormigas ignoren la distancia por completo y sigan solo la feromona, lo que puede causar que toda la colonia refuerce una ruta temprana, posiblemente mala, muy rápidamente (estancamiento). El equilibrio clásico usa una α moderada (alrededor de 1) con una β más fuerte (alrededor de 2–5) para que la exploración temprana sea consciente de la distancia, mientras la feromona sigue permitiendo que la buena estructura se acumule a lo largo de las colonias.
El gráfico rastrea la longitud de la mejor ruta encontrada hasta ahora, que por definición nunca puede empeorar: es un mínimo continuo. Se estanca cuando ninguna hormiga de las colonias más recientes ha logrado superar la ruta campeona actual, lo cual es esperado: a medida que la feromona se concentra en buenos tramos, la mayoría de las hormigas convergen hacia recorridos similares y las mejoras genuinamente nuevas se vuelven más raras. Las mesetas largas usualmente significan que la colonia se ha asentado cerca de un óptimo local para los parámetros actuales; aumentar la tasa de evaporación, el número de hormigas o el exponente de exploración β a veces puede desatascarla para encontrar una ruta más corta.
Un solucionador exacto (ramificación y acotamiento, programación dinámica o programación entera) puede garantizar la ruta más corta verdadera posible, pero su tiempo de ejecución crece explosivamente con el número de paradas: la programación dinámica ya necesita aproximadamente n²·2ⁿ operaciones, lo cual se vuelve inviable mucho antes de n = 30. ACO renuncia a la garantía de optimalidad a cambio de escalabilidad: produce rutas buenas, a menudo casi óptimas, para instancias mucho más grandes en una cantidad fija de cómputo, exactamente el compromiso que hacen los sistemas reales de reparto y logística al enrutar docenas o cientos de paradas.