Algoritmo hormiga

El algoritmo hormiga o algoritmo de las hormigas es una técnica probabilística utilizada para solucionar problemas de cómputo; este algoritmo está inspirado en el comportamiento que presentan las hormigas para encontrar las trayectorias desde la colonia hasta el alimento.

Descripción

En la naturaleza, las hormigas vagan aleatoriamente en su búsqueda de alimento, y a lo largo de su camino de regreso a la colonia depositan una hormona denominada feromona. Si otras hormigas encuentran este rastro, lo más probable es que sigan este camino para depositar el alimento en la colonia.

Con el paso del tiempo el rastro de la feromona comienza a evaporarse y se reduce su fuerza atractiva. Las hormigas que siguen el rastro aumentan la cantidad de la feromona, con lo que el rastro es mas fuerte y dura más tiempo.

Cuantas más hormigas recorran ese camino, más intenso será el olor de la feromona, lo que estimula a más hormigas a seguir esa trayectoria.

Desde el punto de vista algorítmico, la evaporación de la feromona tiene la ventaja de provocar la convergencia a una solución localmente óptima. Si no hubiera evaporación, todas las trayectorias posibles serían igualmente atractivas para las hormigas. Esta situación haría que las trayectorias menos usadas por las hormigas, fueran igual de atractivas que las más utilizadas.

Así, cuando una hormiga encuentra una buena trayectoria de la colonia a una fuente de alimento, es más probable que otras hormigas sigan esa trayectoria, y la regeneración de la feromona provoca que finalmente todas las hormigas sigan una sola trayectoria.

Este comportamiento es la base para el diseño del algoritmo, donde las "hormigas simuladas" caminan alrededor del gráfico que representa el problema que solucionar.

Usos y ejemplos

Los algoritmos de optimización de Colonia de Hormigas se han utilizado para producir soluciones cuasi-óptimas al problema del viajante de comercio. El algoritmo de Colonia de Hormigas puede funcionar continuamente y adaptarse a los cambios en tiempo real. Un ejemplo claro lo podemos observar en el problemas de enrutamiento de redes y sistemas urbanos del transporte.

Los usos del algoritmo se utilizan para máquinas de aprendizaje y para problemas con una gran cantidad de datos. Por ejemplo, se ha estudiado crear un modelo del mantenimiento del cementerio donde las hormigas arraciman los cadáveres de sus semejantes.

Esto se ha adaptado a la tarea de supervisión de las máquinas de aprendizaje, encargadas de agrupar los grupos de objetos que son similares. De hecho se han demostrado que tales formas modificadas de algoritmos dan un funcionamiento y una exactitud mejores que los métodos clásicos tales como el bien conocido k-means.

Métodos relacionados

Este artículo o sección tiene un estilo difícil de entender para los lectores interesados en el tema. Si puedes, por favor edítalo y contribuye a hacerlo más accesible para el público general, sin eliminar los detalles técnicos que interesan a los especialistas.

Existen otros algoritmos de búsqueda muy conocidos como son el Simulated annealing (SA o Recocido simulado), y Tabu Search (TS o Búsqueda tabú):

• SA es una técnica global relacionada de la optimización que atraviesa el espacio de búsqueda generando soluciones cercanas a la solución actual.
• TS es similar SA, en que ambas atraviesan el espacio de la solución probando mutaciones de una solución individual. Mientras que SA genera solamente una solución transformada, la búsqueda del TS genera muchas soluciones transformadas y se mueve a la solución con la aptitud más baja de ésos generados. Para evitar el completar un ciclo y animar el mayor movimiento a través del espacio de la solución, TS se mantiene de soluciones parciales o completas. Se prohíbe para moverse a una solución que contenga los elementos de la lista del tabú, se pone al día mientras que la solución atraviesa el espacio de la solución.