Se sabe que las hormigas tienden a minimizar la longitud de la ruta entre su nido y los recursos alimenticios cercanos, incluso en presencia de obstáculos físicos y terreno accidentado.
Algunas especies de hormigas probablemente “implementen” el siguiente algoritmo: las hormigas comienzan a vagar al azar desde su nido. Después de encontrar un recurso alimenticio, las hormigas regresan a su nido, dejando un rastro de feromonas. Cuando otra hormiga encuentra un rastro de feromona, hay una mayor probabilidad de que siga esta dirección que otras direcciones, y esta probabilidad es proporcional a la concentración de la feromona. La observación clave es que en una unidad de tiempo dada, más hormigas irían de un lado a otro en los caminos más cortos que en los más largos, lo que resultaría en un refuerzo de la concentración de feromonas en estos caminos. A medida que la feromona se evapora con el tiempo, después de un tiempo, las altas concentraciones de feromona solo permanecerían en los caminos más cortos encontrados. Este es un buen ejemplo de inteligencia de enjambre: aunque las hormigas individuales siguen reglas muy simples de manera inconsciente, el resultado acumulativo de muchos agentes que siguen estas reglas es un comportamiento inteligente y óptimo desde la perspectiva de toda la colonia.
Esta descripción se puede traducir fácilmente en un algoritmo utilizado para problemas de optimización que implican encontrar rutas óptimas en un gráfico, como el problema del vendedor ambulante. Estos problemas tienden a ser prácticamente importantes y muy difíciles, ya que las soluciones ingenuas que implican la inspección de todas las soluciones posibles no son prácticas incluso para gráficos pequeños, porque el número de soluciones posibles crece exponencialmente (ver en el video adjunto). La técnica se conoce como el algoritmo de optimización de colonias de hormigas, y le permite encontrar soluciones aproximadas y bastante buenas rápidamente. El siguiente video muestra una implementación para el problema del vendedor ambulante:
- ¿Cómo podría encontrar la métrica correcta que se utilizará para los vecinos más cercanos u otros algoritmos basados en similitudes?
- El comportamiento emergente se encuentra en el núcleo de las ciencias físicas y de la vida: posiblemente por conveniencia computacional. ¿La teoría de la complejidad ofrece ideas aquí?
- ¿Qué es un problema de horario en la programación? ¿Cómo se convierte en un problema NP difícil?
- Si F2L se resuelve mejor de forma intuitiva, ¿por qué cada tutorial incluye algoritmos para todos los casos de F2L?
- Dado un gráfico dirigido, ¿podemos hacer DFS en cada nodo para encontrar el nodo de mayor valor?
Y el siguiente programa simula el comportamiento de búsqueda activa, mostrando las hormigas individuales y los niveles de feromona (en este caso, dos feromonas distintas). Observe cómo las hormigas adaptan su camino después de agregar obstáculos:
Por cierto, el comportamiento de búsqueda de hormigas no es perfecto, y el seguimiento automático de las reglas simples mencionado anteriormente podría en ocasiones especiales provocar un error fatal, un “error” llamado hormiguero:
