Para poder votar este post tienes que identificarte o registrarte aquí.
Para votar este post conéctate con Facebook
Connect
Existe un rompecabezas clásico que ha intrigado durante años a los matemáticos de todo el mundo. Es el llamado “problema del viajante de comercio”. A grandes rasgos, trata de lo siguiente:
Imaginad que sois viajantes de comercio y que debéis visitar 15 ciudades durante un viaje de negocios. Ciudades que están diseminadas por el mapa de forma aleatoria. Vuestra pregunta, en aras de economizar recursos y tiempo, sería: ¿cuál es el camino que conduce a cada ciudad una sola vez recorriendo la menor distancia posible?
La pregunta parece sencilla. Sin embargo, la respuesta es casi imposible de determinar.
A pesar de que sólo hablamos de 15 ciudades, existen miles de millones de rutas posibles que podemos tomar. Por esa razón, históricamente, los matemáticos no han conseguido una ruta perfecta.
Esta clase de problemas son más importantes de lo que parecen para nuestra vida diaria, aunque nuestro trabajo nada tenga que ver con los viajantes de comercio. Por ejemplo, el funcionamiento de Internet, tal y como lo explica Steven Johnson en Sistemas emergentes:
Pensemos en esos viajantes de comercio como en bits de datos, y en las ciudades como en servidores de Red distribuidos por todo el planeta. Ser capaces de calcular la ruta más corta en la Red sería una bendición para un sistema de distribución masiva como Internet, donde puede haber miles de “ciudades” en cada ruta, en lugar de quince.
Afortunadamente, el problema fue resuelto hace poco. A finales de 1999, Marco Dorigo de la Universidad Libre de Bruselas, anunció que sus colegas y él habían dado con la clave. Y la clave era nada menos que observar a las hormigas.
¿Las hormigas? ¿Qué tienen que ver las hormigas con los viajantes de comercio o con el funcionamiento de Internet?
Al parecer, las colonias de hormigas tienen una habilidad extraordinaria a la hora de calcular el camino más corto hasta diferentes fuentes de alimento, usando su lenguaje simple de rastros de feromonas.
De modo que Dorigo hizo lo mismo que hacen las hormigas. Envió a un ejército de viajantes de comercio virtuales a explorar las posibles rutas en el mapa.
Cuando un viajante completa con éxito el trayecto a las quince ciudades, vuelve sobre sus pasos hasta la primera ciudad y deposita pequeñas cantidades de “feromonas” virtuales en el camino. Dado que la cantidad total de feromonas es finita, se distribuye en dosis más pequeñas en los caminos más largos y en dosis mayores en los más cortos. Con miles de hormigas recorriendo el mapa, algunos sectores de las rutas más cortas acumulan rápidamente gruesas capas de feromonas, mientras que las rutas menos convenientes prácticamente carecen de ellas.
Tras repetir varias sesiones de envíos de viajantes de comercio virtuales con tendencia a soltar feromonas a su paso, la inteligencia emergente del sistema da sus frutos: se alcanza una solución casi óptima para el problema del viajante de comercio sin usar nada que se parezca al cálculo tradicional o a un centro de resolución de problemas.
El problema se resuelve mediante una avalancha de pruebas y errores que interaccionan entre sí y se mejoran a sí mismos.
Ello ha originado que Telecom en Francia, British Telecommunications y MCI apliquen estrategias de routing de este tipo a sus redes de datos y telefonía. Otros estudios demuestran que la aproximación de Dorigo es mucho más eficaz que la rutina Open Shortest Path First que usa Internet para distribuir datos entre nodos de la Red.
En unos años, nuestras interacciones en línea se basarán en el poder ascendente de la inteligencia colectiva. Y todo gracias a las inspiradoras hormigas, que lo descubrieron antes que nosotros.
Vía | Sistemas emergentes de Steven Johnson
Preferimos ganar poco aunque lo podamos perder todo
El sistema para ganar dinero de Ponzi: los timos piramidales
¿Caminar borracho es más peligroso que conducir borracho?
reStart Internet Addiction Recovery Program: empaparse de realidad
Edificios con mucha ciencia (IV): Las urbanizaciones fractales de Dubai
Comentarios
Curiosidades de la vida...
El ser humano crea algo, y tarde o temprano, lo debe adaptar en base a lo que marca la naturaleza para un óptimo funcionamiento. Muchas respuestas están frente a nosotros y no las vemos, vaya, que no es (ni será) la primera vez que ocurre.
Oh, fascinante. Pero no entiendo el último párrafo. ¿Qué es eso de inteligencia colectiva? ¿El P2P?
Hasta los protozoos saben, cuando tienen hambre, encontrar las rutas más cortas a las fuentes de comida. Pongo un enlace a esta noticia aparecida a principios de año que es similar a la economía que practican las hormigas y que también se ha observado para comparar la eficiencia del trazado del metro de Tokio y que se plantea que puede servir para optimizar redes de comunicaciones.
http://www.bbc.co.uk/mundo/ciencia_tecnologia/2010/01/100125_lama_inalambrico_men.shtml
En mi época de estudiante en la Facultad de Informática hacíamos algoritmos para obtener la solución a este problema para n ciudades....Pero para dar con la solución haría falta computadoras con mucha potencia.
En el post dices lo siguiente:
"se alcanza una solución casi óptima para el problema del viajante de comercio sin usar nada que se parezca al cálculo tradicional o a un centro de resolución de problemas"
Yo lo veo más como un nuevo enfoque al problema, pero supongo que para simular lo de las hormigas también se habrá usado computadoras muy potentes....
Se reduce mucho la potencia de cálculo necesaria y se puede incorporar a la red; que se vuelve dinámica y se adapta a las nuevas situaciones en vivo.
Es fundamental para el internet del futuro, que ha de afrontar demandas masivas de información simultáneamente desde muchos focos (ejemplo, un partido de fútbol vía Imagenio u ONO Digital).
Mediante el uso de P2P y la optimización de rutas se reducen los costes. No puede depender semejante tarea de unos pocos servidores, si la demanda es masiva (millones de peticiones, que es sólo darle a un botón). Pues bien, se estudian las previsiones de demanda, y se emite en la red donde los mismos terminales de los usuarios dan servicio a otros terminales (P2P y sin estar pirateando!) y optimizan las rutas.
Cada vez se vuelve más complejo.
Muy interesante. Hay muchísimos casos en los que la tecnología humana se basa en la forma de actuar de los animales. Es impresionante la cantidad de inventos que se basan en "imitar" el comportamiento animal.
Sin duda, esta es una forma muy útil para mejorar internet, ya que se adapta a los problemas que surgan de forma inteligente y no se limita a aplicar una fórmula de modo mecánico.
6, Muy cierto, y es que al fin y al cabo también somos animales.
Interesante entrada por cierto.
bueno esto no lo veo yo tan novedoso. Mucho antes del 99 ya se resolvia el problema del viajante de comercio mediante algoritmos geneticos llegando a una solucion cuasi optima al igual que esto de las hormigas...solamente que con algoritmos geneticos os aseguro que hace falta muchisimo menso esfuerzo computacional ya que lo de las hormigas suena a prueba y error mezclado con reforzamiento psinaptico como en redes neuronales. Es tendencioso decir que por fin se ha resuelto el problema ya que soluciones si no mejores al menos similares de buenas ya se habian llevado a cabo anteriormente a esto de las hormigas
Estoy de acuerdo con el comentario de arriba. En su día en informática me enseñaron soluciones heurísticas al problema del viajante, como la de las hormigas o los algoritmos genéticos, pero que me acuerde dijeron que era un problema de tipo NP completo, para el cual no se puede encontrar en tiempo polinómico la solución óptima para cualquier instancia del problema.
Por eso pienso que no es muy correcto decir que el problema fue resuelto.
#7: con una ligera ventaja: que podemos estudiar el comportamiento de otros animales y plagiarles ;)
Vaya conclusion despues de ser ocioso y ver un rato como se mueven las hormigas XD
Ya en serio, esto de la forma en que se plantea el problema, no creen que generaria saturacion en los canales, las hormigas tienen canales "infinitos" por donde pasar, mientras que nuestras comunicaciones dependen de cierto ancho de banda, conforme el camino más corto se llene de "feromonas" los paquetes trataran de ir siempre por ahi, se que algoritmos similares a CSCD permitirian reenviarlos, pero no se, me da que no es la opcion más optima
Aunque, soy un inginiero más detras de una computadora dispuesto a aprender nuevas cosas !! :D !!
Hola, tengo una pregunta, si no lei mal, para buscar el camino optimo no solo tiene que recorrer todos los caminos, sino que muchas veces para saber cual es el que tiene mas capas de feromonas. Eso no tiene complejidad mayor que hacer un Dijkstra?? Saludos
osea, si queremos llegar más rápido, es mejor ir por una autopista por donde hay mas emisiones de escape, y por tanto más automóviles? :D
Felicitaciones, para demostrar que el cerebro y las ideas sirven para cosas fructíferas como ésta.
Yo he estudiado esto en mi facultad de informática, concretamente en la asignatura de MMCC (Métodos Matemáticos para las Ciencias de la Computación) y es muy interesante. Mi proyecto de fin de carrera iba a englobar los cálculos de este tipo (colonias de hormigas) con la minería de datos, todo ello de una forma aplicable a los datos recogidos durante las carreras de F1 con el fin de desarrollar estrategias con algoritmos genéticos para plantear las estrategias de siguientes carreras. Al final me decanté por otra cosa, pero esto quedará pendiente para mi tesis doctoral.
Saludos.
Escribir un comentario
Para hacer un comentario tienes que identíficarte: ENTRA o conéctate con FacebookConnect