Sent to you by Cassisi via Google Reader: Las abejas resuelven problemas que los ordenadores no (tan fácil) via ALT1040 by Alan Lazalde on 10/26/10 El problema del agente viajero es un clásico dentro de las ciencias de la computación. Imaginen un pobre hombre con un mapa y un puñado de ciudades por visitar, sin excepción. Por supuesto, puede visitar una a una de las ciudades al azar hasta terminar, pero esto puede ser muy ineficiente. Lo mejor será que busque la ruta más corta para recorrer todas las ciudades sin repetir visitas. Ahora bien, asuman que tal agente también es un programador —vaya fortuna—. Entonces tendría a bien diseñar un algoritmo apropiado para resolver el problema. Luego lo implementaría en un programa capaz de dibujar esa óptima ruta, oculta a primera vista, que le ahorrará muchos costos. Genial, ¿no? La triste realidad es que el algoritmo no tiene una solución general conocida —el agente ganaría un premio Turing si lo hallase de veras—. Entonces, ¿cómo se resuelve el problema del agente viajero? Con aproximaciones o heurísticas. Las hay de todo tipo y, desde hace unos años, inspiradas en la naturaleza. Una de las más recientes fue reportada por The Guardian y está relacionada con las abejas. El Dr. Nigel Raine, del área de ciencias biológicas del Royal Holloway en Londres, menciona al respecto: Las abejas resuelven el problema del agente viajero todos los días. Ellas visitan flores en múltiples ubicaciones y, debido a que utilizan mucha energía para volar, encuentran una ruta que les mantiene volando el menor tiempo posible […] A pesar de sus pequeños cerebros las abejas son capaces de realizar extraordinarias hazañas de conducta. Por supuesto, las abejas no son el único caso conocido en la naturaleza. Desde hace años, con Marco Dorigo a la cabeza, las colonias de hormigas han sido estudiadas por sus habilidades de optimización de rutas. Básicamente, las hormigas crean caminos gracias a las moléculas de feromona que dejan a su paso. Con el tiempo, las mejores rutas son las que mayor feromona poseen. Quise conocer cómo le hacen las abejas para conseguir sus propias rutas óptimas. Pero el artículo científico del Dr. Nigel y otros con todos los detalles de sus investigaciones aún no ha sido publicado. Sólo sé, y les cuento, que usaron flores artificiales controladas por ordenadores para probar la conducta de las abejas. Los investigadores querían saber si los insectos seguirían una ruta simple definida por el orden en el que encontraron las flores. Para su sorpresa, pronto las abejas “aprendieron” a volar por la ruta más corta para ahorrarse tiempo y energía. El Dr. Nigel comenta: Necesitamos entender cómo pueden resolver el problema del agente viajero sin necesidad de una computadora. Los algoritmos bioinspirados son fascinantes por donde se les vea. Nadie es mejor que la naturaleza para proveer soluciones óptimas probadas con millones de años de evolución. Por otro lado, las aplicaciones son muchas y bien interesantes. ¿Se imaginan algoritmos y software bioinspirados para encontrar rutas óptimas en Internet? Ya los hay, y muy pronto escribiremos algo al respecto. Las abejas resuelven problemas que los ordenadores no (tan fácil) escrita en ALT1040 el 26 October, 2010 por alan.lazalde Enviar a Twitter | Compartir en Facebook Things you can do from here: - Subscribe to ALT1040 using Google Reader - Get started using Google Reader to easily keep up with all your favorite sites