Algoritmo hormiga

De Wikipedia, la enciclopedia libre

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.

[editar] Descripción

En la naturaleza, las hormigas vagan aleatoriamente en su búsqueda de alimento, y a lo largo de su trayectoria de regreso a la colonia depositan una hormona denominada feromona. Si otras hormigas encuentran este rastro, lo más probable es que sigan esta trayectoria 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 refuerzan la intensidad de la feromona, con lo que logran que perdure por más tiempo.

Mientras más hormigas recorren una trayectoria, más intenso es el olor del rastro, 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 evitar la convergencia a una solución localmente óptima. Si no hubiera evaporación, todas las trayectorias serían igulamente atractivas para las hormigas. Esta situación haría que la exploración del espacio de la solución fuese demasiado amplia.

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 a solucionar.

[editar] Usos y ejemplos

Los algoritmos de la optimización de la colonia de la hormiga se han utilizado para producir soluciones cuasi-óptimas al problema del agente viajero. El algoritmo de la colonia de la hormiga puede funcionar continuamente y adaptarse a los cambios en tiempo real. Un ejemplo claro lo podemos observar en el problemas de ruteo 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.

[editar] Métodos relacionados

Este artículo tiene un estilo difícil de entender para los lectores interesados en el tema. Si tienes capacidad, por favor edítalo, 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.