Introducción a la optimización de colonias de hormigas

El mundo algorítmico es hermoso con múltiples estrategias y herramientas que se desarrollan las 24 horas del día para satisfacer la necesidad de computación de alto rendimiento. De hecho, cuando los algoritmos se inspiran en las leyes naturales, se observan resultados interesantes. Los algoritmos evolutivos pertenecen a esta clase de algoritmos. Estos algoritmos están diseñados para imitar ciertos comportamientos, así como rasgos evolutivos del genoma humano. Además, dicho diseño algorítmico no solo está limitado a los humanos, sino que también puede inspirarse en el comportamiento natural de ciertos animales. El objetivo básico de fabricar tales metodologías es proporcionar soluciones realistas, relevantes y, sin embargo, de bajo costo a problemas que hasta ahora no se pueden resolver por medios convencionales.

Así, han evolucionado diferentes técnicas de optimización basadas en dichos algoritmos evolutivos y, por lo tanto, han abierto el dominio de las metaheurísticas. Metaheurística se ha derivado de dos palabras griegas, a saber, Meta que significa un nivel por encima y heuriskein que significa encontrar . Algoritmos como Particle Swarm Optimization (PSO) y Ant Colony Optimization (ACO) son ejemplos de inteligencia de enjambre y metaheurísticas. El objetivo de la inteligencia de enjambre es diseñar sistemas inteligentes de múltiples agentes inspirándose en el comportamiento colectivo de insectos sociales como hormigas, termitas, abejas, avispas y otras sociedades animales como bandadas de pájaros o bancos de peces.

Fondo:

La técnica Ant Colony Optimization está puramente inspirada en el comportamiento de búsqueda de alimento de las colonias de hormigas, introducida por primera vez por Marco Dorigo en la década de 1990. Las hormigas son insectos eusociales que prefieren la supervivencia y el mantenimiento de la comunidad en lugar de como especies individuales. Se comunican entre sí mediante el sonido, el tacto y las feromonas. Las feromonas son compuestos químicos orgánicos secretados por las hormigas que desenstringn una respuesta social en los miembros de la misma especie. Estos son químicos capaces de actuar como hormonas fuera del cuerpo del individuo secretor, para impactar el comportamiento de los individuos receptores. Dado que la mayoría de las hormigas viven en el suelo, utilizan la superficie del suelo para dejar rastros de feromonas que pueden ser seguidos (olidos) por otras hormigas.
Las hormigas viven en nidos comunitarios y el principio subyacente de ACO es observar el movimiento de las hormigas desde sus nidos para buscar comida en el camino más corto posible. Inicialmente, las hormigas comienzan a moverse al azar en busca de comida alrededor de sus nidos. Esta búsqueda aleatoria abre múltiples rutas desde el nido hasta la fuente de alimento. Ahora, en función de la calidad y cantidad de la comida, las hormigas llevan una porción de la comida con la concentración de feromonas necesaria en su camino de regreso. Dependiendo de estas pruebas de feromonas, la probabilidad de selección de un camino específico por parte de las siguientes hormigas sería un factor de orientación hacia la fuente de alimento. Evidentemente, esta probabilidad se basa tanto en la concentración como en la tasa de evaporación de la feromona. También se puede observar que dado que la tasa de evaporación de la feromona también es un factor decisivo,

En la figura anterior, por simplicidad, solo se han considerado dos caminos posibles entre la fuente de alimento y el hormiguero. Las etapas se pueden analizar de la siguiente manera:

1. Etapa 1: Todas las hormigas están en su nido. No hay contenido de feromonas en el ambiente. (Para el diseño algorítmico, se puede considerar la cantidad de feromona residual sin interferir con la probabilidad)
2. Etapa 2: Las hormigas comienzan su búsqueda con la misma probabilidad (0,5 cada una) a lo largo de cada ruta. Claramente, el camino curvo es el más largo y, por lo tanto, el tiempo que tardan las hormigas en llegar a la fuente de alimento es mayor que el otro.
3. Etapa 3: Las hormigas a través del camino más corto llegan antes a la fuente de alimento. Ahora, evidentemente se enfrentan a un dilema de selección similar, pero esta vez debido al rastro de feromonas a lo largo del camino más corto ya disponible, la probabilidad de selección es mayor.
4. Etapa 4: Más hormigas regresan por el camino más corto y posteriormente las concentraciones de feromonas también aumentan. Además, debido a la evaporación, la concentración de feromonas en el camino más largo se reduce, disminuyendo la probabilidad de selección de este camino en etapas posteriores. Por lo tanto, toda la colonia usa gradualmente el camino más corto en mayores probabilidades. Por lo tanto, se logra la optimización de la ruta.

Diseño algorítmico:

En relación con el comportamiento anterior de las hormigas, ahora se puede desarrollar un diseño algorítmico. Para simplificar, se ha considerado una sola fuente de alimento y una sola colonia de hormigas con solo dos caminos de recorrido posible. Todo el escenario se puede realizar a través de gráficos ponderados donde la colonia de hormigas y la fuente de alimento actúan como vértices (o Nodes); los caminos sirven como bordes y los valores de feromonas son los pesos asociados con los bordes.
Sea el gráfico G = (V, E) donde V, E son las aristas y los vértices del gráfico. Los vértices según nuestra consideración son V _s (Vértice de origen – colonia de hormigas) y V _d (Vértice de destino – Fuente de alimento), Los dos bordes son E ₁ y E₂ con longitudes L ₁ y L ₂ asignadas a cada uno. Ahora, se puede suponer que los valores de feromona asociados (indicativos de su fuerza) son R ₁ y R ₂ para los vértices E ₁ y E ₂ respectivamente. Así, para cada hormiga, la probabilidad inicial de selección de camino (entre E ₁ y E ₂ ) se puede expresar de la siguiente manera:

Evidentemente, si R ₁ >R ₂ , la probabilidad de elegir E ₁ es mayor y viceversa. Ahora, mientras regresa por este camino más corto, digamos E _i , el valor de la feromona se actualiza para el camino correspondiente. La actualización se realiza en función de la longitud de los caminos, así como de la tasa de evaporación de la feromona. Por lo tanto, la actualización se puede realizar paso a paso de la siguiente manera:

1. De acuerdo con la longitud de la ruta :
   
   en la actualización anterior, i = 1, 2 y ‘K’ sirve como parámetro del modelo. Además, la actualización depende de la longitud de la ruta. Cuanto más corto sea el camino, mayor será la feromona añadida.
2. De acuerdo con la tasa de evaporación de la feromona :
   
   el parámetro ‘v’ pertenece al intervalo (0, 1] que regula la evaporación de la feromona. Además, i = 1, 2.

En cada iteración, todas las hormigas se colocan en el vértice de origen V _s (colonia de hormigas). Posteriormente, las hormigas se mueven de V _s a V _d (fuente de alimento) siguiendo el paso 1. Luego, todas las hormigas realizan su viaje de regreso y refuerzan su camino elegido en base al paso 2.

Pseudocódigo:

Procedure AntColonyOptimization:
    Initialize necessary parameters and pheromone trials;
    while not termination do:
        Generate ant population;
        Calculate fitness values associated with each ant;
        Find best solution through selection methods;
        Update pheromone trial;
    end while
end procedure

La actualización de feromonas y los cálculos de aptitud en el pseudocódigo anterior se pueden encontrar a través de las implementaciones paso a paso mencionadas anteriormente.
Así, se ha establecido la introducción de la técnica de optimización ACO. La aplicación del ACO puede extenderse a diversos problemas como el famoso TSP (Travelling Salesman Problem) .

Referencias:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf