Abejorros y el problema del viajante
Al parecer los abejorros saben resolver el problema del viajante. Una tarea difícil que en computación se cataloga como problema NP.
|
|
|
El problema del viajante consiste en salir de la sede de la empresa y volver a la misma visitando todas las ciudades una sola vez por el camino más corto posible. Matemáticamente se trata de encontrar un ciclo hamiltoniano sobre un grafo en el que los vértices del grafo representan ciudades unidas por aristas (las carreteras) con un peso dado (los kilómetros o el gasto en combustible del tramo en cuestión). Básicamente, para este problema no hay un algoritmo que lo resuelva de manera eficiente y se cree que no existe. Aquí se entiende por “eficiente” el que sea resoluble en un tiempo polinómico. Es decir, que el tiempo de resolución en relación al tamaño del problema (en nuestro caso al número de vértices del grafo que representa las ciudades unidas por carreteras) crezca polinómicamente y no exponencialmente.
Aunque hay muchos algoritmos que encuentran una buena aproximación al problema del viajante, no existe ninguno que sea eficiente y que a la vez dé la mejor solución posible. La única manera de encontrar la mejor solución consiste básicamente en enumerar todas las posibilidades y escoger la mejor (la ruta más corta), algo sumamente ineficiente. Se sospecha que algunos de estos problemas, como el del viajante, nunca tendrán una solución eficiente, al ser problemas de tipo NP o NP completos.
Obviamente para unas pocas ciudades unidas por unas pocas carreteras es relativamente sencillo resolverlo a la fuerza bruta, incluso con sólo un lápiz y un papel. Pero si son muchas le lleva a un ordenador mucho tiempo resolver el problema.
Lo que buscamos con la resolución del problema del viajante es encontrar la ruta que cumple con nuestros objetivos con el menor gasto de energía y tiempo. Pero esto es precisamente lo que tienen que hacer algunos animales. Un abejorro, por ejemplo, necesita recolectar polen y néctar en diversas flores y de cómo lo haga dependerá su eficacia y, por tanto, su supervivencia. Esto debe de crear una presión de selección que haya hecho que los abejorros hayan evolucionado con el tiempo para que ser más eficientes y que inconscientemente recorran el menor camino posible.
Esto es lo debieron pensar científicos de varias instituciones británicas cuando se pusieron a investigar la optimización de los vuelos del abejorro en su tarea de recolectar néctar. Descubrieron que los abejorros resuelven el problema del viajante, siendo el primer ejemplo de este tipo en el reino animal. Y todo con un cerebro diminuto.
El equipo de investigadores usó flores artificiales controladas computacionalmente para ver si estos animalillos seguían una ruta marcada con anterioridad o si descubrían con la nueva disposición la ruta más corta. Después de explorar la nueva localización de las flores, los abejorros rápidamente aprendieron a encontrar el camino más corto, es decir, la solución del problema del viajante para esa configuración. Es de suponer que hagan lo mismo en el campo.
Según Nigel Raine, las “abejas” resuelven el problema del viajante todos los días. Visitan flores en múltiples lugares y como usan mucha energía en el vuelo necesitan optimizar la ruta para mantener el camino que vuelan al mínimo.
Comprender cómo los abejorros efectúan este tipo de cálculo puede que nos ayude a diseñar sistemas o algoritmos (quizás basados en redes neuronales), más eficientes y que necesiten escasos recursos, pues el cerebro de los abejorros es muy pequeño. Podrían usarse, por ejemplo, en el control del tráfico y en la regulación de semáforos.
Raine dice que “a pesar de sus pequeños cerebros las abejas son capaces de proezas extraordinarias. Necesitamos comprender cómo resuelven el problema del viajante sin la ayuda de un ordenador. ¿Qué tipo de atajos usan? ”
En el mundo de la computación ya se habían utilizado algoritmos inspirados en animales (en concreto en las hormigas) para resolver el problema del viajante, pero este caso constituye el primer caso real en la Naturaleza.
Copyleft: atribuir con enlace a http://neofronteras.com/?p=3281
Fuentes y referencias:
Nota de prensa I.
Nota de prensa II.
Artículo original.
Computador bacteriano resuelve problema.
¿Es P no igual a NP?
Otras maneras de contar.
19 Comentarios
RSS feed for comments on this post.
Lo sentimos, esta noticia está ya cerrada a comentarios.
martes 26 octubre, 2010 @ 7:44 am
Para mí la parte interesante no es cómo resuelven el problema los abejorros, sino saber si esa solución es hereditaria o aprendida. Y si es hereditaria entender qué genes y cómo codifican esa solución. A fin de cuentas no entiendo cómo la naturaleza podría resolver este problema si no es mediante prueba y error.
Saludos
martes 26 octubre, 2010 @ 6:02 pm
Asombrosamente simple: los abejorros se comunican socialmente entre si, a través de un lenguaje (un código) quimico, por el cual informan con pasmosa precisión los mas simples itinerarios, tanto como los posibles errores de elección. Hipótesis verificable, por cierto.
martes 26 octubre, 2010 @ 8:30 pm
Ya lo dijo Feynman: «Creo que la imaginación de la naturaleza es mucho más grande que la del hombre.Nunca va a dejar que descansemos». Lo cierto es que la naturaleza nunca deja de sorprendernos.
saludos.
miércoles 27 octubre, 2010 @ 3:27 am
joabbl: puedo asegurarte que la solucion de los abejorros es hereditaria, me cuesta mas imaginar a los abejorros aprendiendo de sus padres el algoritmo. Y la naturaleza resolvio por ensayo y error el diseño del «dispositivo» que resuelve el problema (el cerebro cableado de nacimiento), pero una vez nacido el abejorro el dispositivo debe resolver el problema de «una» sin ensayo y error, sino NO SERIA SOLUCION AL PROBLEMA
miércoles 27 octubre, 2010 @ 8:16 pm
Son muchos abejorros, basta que uno de éstos dé con el camino mas expedito, sea por adn o ensayo y error, para que todos lo sepan, por transmisión química del «pensamiento».
Saludos.
jueves 28 octubre, 2010 @ 8:13 am
No debería ser difícil descubrir si es un comportamiento aprendido o hereditario. Bastaría con «criar» abejorros en solitario y ver si son capaces de resolver el problema. Y si es así (cosa que yo apenas dudo), mediante «ingeniería inversa» acabar descubriendo cuales son los genes que consiguen ese comportamiento. Me resulta difícil creer que sea un comportamiento aprendido porque si así fuese, en cada generación debería haber algunos abejorros más listos o con más suerte que los demás y siempre habría abejorros más «duros de mollera» que lo tendrían difícil para sobrevivir, lo cual es claramente antidemocrático e incluso fascista (al menos entre los abejorros que se dediquen a la demagogia «abejorril»), porque en el fondo todos los abejorros han de ser iguales ante la naturaleza y ante su dios. Y si además la «Educación» entre lo abejorros se deteriora por la razón que sea como está pasando entre los humanos su supervivencia estaría comprometida (como la nuestra).
Saludos igualitarios.
jueves 28 octubre, 2010 @ 11:59 am
Apreciado Joabbl, el comportamiento «abejorril» supongo que ha de ser innato por una razón: el abejorro ha de poseer un sistema que mida la eficiencia en la selección de rutas, para poder seleccionar la mejor de ellas. Podria ser un sistema que mida el consumo energético en determinado tiempo de vuelo. O bien estimar directamente la distancia, aprovechando su perfecta visión en 3D. O ambas cosas. En cualquier caso, el «software» de este sistema de medición no puede ser aprendido.
Saludos
jueves 28 octubre, 2010 @ 12:34 pm
Sería interesante destripar a fondo los genes responsables de este comportamiento (y de muchos otros que se producen en la naturaleza). En animales relativamente simples como los insectos quizá algún día, partiendo de su ADN, se puedan predecir algunas de sus características y modificarlas a voluntad utilizando modelos informáticos. Pero entiendo que ese día aún está lejos.
Saludos
jueves 28 octubre, 2010 @ 1:51 pm
Tal vez. Es posible que exista uno o mas componentes quimicos en el tipo de flores, que actuen como señales de tránsito. Sabemos por la nanotecnologia que las moleculas, en este caso de los holores, SI codifican mensajes o pueden hacerlo. Tal vez el abejorro sólo «lee» la respuesta correcta. Es sólo una hipótesis, por cierto.
jueves 28 octubre, 2010 @ 5:52 pm
Voy a escuchar «la danza de la libélula», lo prometo.
Belleza. Bell e zz ell b ll zz …
sábado 30 octubre, 2010 @ 7:46 pm
Estoy de acuerdo con Gerardo 4, joabbl 6 y RicardM 7: creo que la solución está inscrita en los genes y que merecería la pena averiguarlo, tratándose de una experiencia tan sencilla y barata.
Enhorabuena a Juan Díaz por su acertado humor, cosa que, aunque a Neo le parezca banal, no es tan sencilla cuando es tan apropiada y original. Tiene tanto mérito como el pensar sesudamente. De todas formas, adelante con ese esfuerzo que nos pide; su empeño en alimentar nuestras mentes lo merece.
Saludos.
sábado 30 octubre, 2010 @ 8:57 pm
La respuesta de las abejas es obviamente innata y por tanto genética. Entre otras cosas porque las abejas no tienen cultura ni un sistema nervioso sofisticado que les permita el aprendizaje de sus semejantes de algo así en vida.
Se han descubierto comportamientos sofisticados en aves que también son innatos, incluidos el uso de herramientas:
http://www.sciencefriday.com/videos/watch/10327
Sin embargo, lo importante es que se aprendan gracias a otros semejantes como pasa en primates (o cetáceos).
Lo importante en humanos es que la cultura se basa en una evolución lamarckista que es muchísimo más rápida que la darwinista y de ahí nuestro «éxito» como especie.
domingo 31 octubre, 2010 @ 8:25 pm
Parece tener prioridad la investigación en los genes de la inmunidad en las abejas. Universidad de Utha.
Como sea, el propoleo ya se usa por sus efectos como antibiótico natural.
lunes 1 noviembre, 2010 @ 9:33 pm
Muy estimado Neo: Tienes toda la razón. He visto al cuervo. Ese tipo de comportamiento en aves ya lo demostró Rodríguez de la Fuente, hace más de 30 años -creo recordar- con un alimoche llamado Gaspar que, sin enseñanza previa, rompía un huevo -creo artificial- similar al de un avestruz.
Un saludo.
martes 2 noviembre, 2010 @ 12:49 am
Estimado Tomás:
Recuerdo que de niño vi el episodio del alimoche y me vino a la mente al escribir el comentario, pero no quise mencionarlo porque quizás no todo el mundo haya visto tal episodio.
Lo curioso es que F. R. de la Fuente vendía esa capacidad innata como algo maravilloso (el alimoche del episodio había sido criado fuera de África), cuando lo maravilloso hubiera sido que fuera una conducta aprendida.
martes 2 noviembre, 2010 @ 4:00 am
Sin embargo, es aprendido para las urracas huir del espantajo, pero a través de los años le faltaron el respeto, e hicieron su morada en el solitario fantasma de alhué.
martes 2 noviembre, 2010 @ 7:15 pm
Al 15 de Neo: Pues sí, tienes razón. Pero entonces parece que en algún momento ha tenido que haber para esas aves un «efecto Baldwin».
Ya veo que descartas -parece lógico- toda cultura para las abejas, pero entonces ¿como comenzaron a hacer cualquier tarea compleja, tal como el comunicarse o resolver el problema del viajante?. Si fuera el caso de que su especie ya comenzó sabiendo, es que su especie antecesora ya sabía. Pero tampoco podemos así retroceder hasta el infinito. En algún momento en una especie o en su transición exitosa hubo de darse la adquisición. Creo que es una cuestión irresuelta.
Un cordial saludo.
martes 2 noviembre, 2010 @ 9:33 pm
Estimado Tomás:
Pues la selección natural puede explicarlo. Aquellas abejas que hacían un recorrido más alejado del aleatorio tenían una ventaja competitiva frente al resto al gastar menos energía para conseguir la misma comida. En el transcurso de millones de años el proceso se fue optimizando al irse seleccionando el «hardware neurológico» más adecuado. Así hasta que se alcanzó la solución óptima.
Sin embargo, si se ponen miles de flores las abejas probablemente no conseguirán la solución óptima, sino una aproximación.
miércoles 3 noviembre, 2010 @ 9:43 am
Sí, Neo, me parece convincente.