Como se ha comentado anteriormente en este blog, es común que no sea de utilidad en el mundo real el uso de la programación lineal entera para obtener la solución óptima en el caso del problema del cálculo de rutas.
Una de las técnicas metaheurísticas más comunes para la resolución de este problema es conocida como Colonia de Hormigas (ACO por sus siglas en inglés). La técnica de colonia de hormigas fue introducida por Marco Dorigo en 1992, y se basa en el comportamiento de éstas cuando salen del hormiguero a buscar comida. Las hormigas depositan feromonas por aquellos lugares por donde pasan, de tal forma que cada hormiga cuando sale del hormiguero en busca de alimento, tiene mayor probabilidad de escoger caminos por los que hayan ido más hormigas anteriormente, es decir, caminos con mayor cantidad de feromonas.
En las imágenes podemos ver la evolución de los caminos que toman las hormigas, el camino más corto es mas frecuente al tener mayor cantidad de feromonas:
El algoritmo de colonia de hormigas, modifica ligeramente este comportamiento, esperando a que cada hormiga calcule una ruta completa para depositar feromonas. De esta forma, cada hormiga tendrá que escoger en cada iteración del algoritmo cuál de los nodos no visitados será el siguiente que visitará, basándose en su posición, y en la cantidad de feromonas depositadas en los arcos . De esta forma, la probabilidad de que una hormiga “k” elija el arco «xy» será:
Donde τ(xy) es la cantidad de feromona depositada en el arco xy , η(xy) representa la conveniencia de elegir el arco xy (generalmente definida como 1/distancia(xy)), α representa un parámetro por el cual se da peso a la cantidad de feromona depositada en cada arco y β representa el parámetro de influencia de η(xy) .
Como se puede observar en esta técnica metaheurística, la convergencia y la bondad de la solución obtenida es función de parámetros a elección del usuario que, por lo general, pueden ser distintos para cada problema. Una vez que cada hormiga ha completado una ruta, es decir, ha obtenido una solución factible, se actualiza la cantidad de feromonas que hay en cada arco:
Donde τ(xy) es la cantidad de feromona depositada en el arco xy, ρ es un parámetro que indica la evaporación de feromona de cada arco y Δτ(xy) representa el depósito de feromona de cada hormiga en los arcos por los que ha pasado. Típicamente, el depósito de feromona de cada hormiga en cada arco será Q/L(k) si ha pasado por el arco y 0 en caso contrario, donde Q es una constante y L(k) representa el espacio total recorrido por la hormiga en su circuito.
Existen diversas características del algoritmo que los diferencian entre sí, como pueden ser el número de hormigas o el número y posición de hormigueros. También son comunes las extensiones al caso presentado:
- Elitist Ant System (EAS): En cada depósito de feromonas, la mejor solución global obtenida hasta el momento también deposita feromonas en su recorrido.
- Max-Min Ant System (MMAS): Existe un rango de cantidad de feromona a depositar [τmin,τmax], y solamente la mejor solución obtenida en cada iteración deposita feromonas. Todos los arcos comienzan teniendo feromona inicializada a τmax, y cuando ésta se ha evaporado alcanzando el valor de τmin, se vuelven a inicializar a τmax.
- Rank-based Ant System (ASrank): Se clasifican las soluciones atendiendo a su bondad, y la cantidad de feromona depositada es proporcional a ese valor, de tal forma que las hormigas que han obtenido una mejor solución depositan mayor cantidad de feromona en sus arcos.
¿Quieres saber más sobre este tipo de problemas y los algoritmos para resolverlos?
Puedes seguirnos en las redes sociales (Linkedin, Twitter, Youtube) para no perderte nada y mantenerte al tanto de futuros eventos o acciones.