Los problemas NP-complejos de los abejorros.

Los humanos tenemos tendencia a buscarnos problemas. Y a un conjunto de éstos lo llamamos problemas NP-complejos. Pero en la naturaleza los humanos no somos los únicos en enfrentarnos a las situaciones que los generan. Un ejemplo típico de este tipo de problemas es el denominado del viajante de comercio, o quizás deberíamos decir, para no ser tan antropocéntricos, el problema del abejorro recolector. Los abejorros revelan que su inteligencia y memoria van más allá de lo que sospechábamos encontrando soluciones óptimas a problemas con 120 opciones y dos variables empleando un cerebro del tamaño de una cabeza de alfiler.

El problema del viajante de comercio (PVC) se puede expresar en términos matemáticos más formales (así, por ejemplo) pero a nosotros nos bastará con una descripción sencilla para después entender rápidamente el problema del abejorro recolector.

Un viajante de comercio debe viajar entre N ciudades, la suya incluida. El orden en el que las visite no importa siempre que visite cada una durante su viaje y finalice éste en el lugar donde empezó, la sede de su empresa. Cada una de las ciudades, o nodos, está conectada con los otros nodos por distintos medios de transporte (aviones, trenes o carreteras). Cada una de estas conexiones tiene unos costes asociados. En términos más matemáticos diríamos que la dificultad de atravesar esta arista del grafo vendría expresada por el coste, que es monetario (el precio del billete o el combustible) y temporal (tiempo invertido en el traslado). El objetivo del viajante es conseguir que los costes del viaje, en dinero desembolsado y tiempo, sean mínimos.

No parece demasiado difícil si pensamos en 4 ó 5 ciudades. Lo podemos resolver a lo bruto. La dificultad está en que conforme aumenta N la complejidad se dispara, ya que el número de permutaciones es (N-1)!, leído ene-menos-uno-factorial, si no consideramos la sede de la empresa. Un ejemplo numérico nos dará idea de la magnitud del problema: si hay que visitar 12 ciudades el número de opciones a considerar es superior a ¡479 millones! El PVC es un ejemplo típico de un conjunto de problemas de optimización considerados “difíciles” o “complejos” a los que los matemáticos e informáticos llevan dándole vueltas desde hace decenios por sus implicaciones en ciencia e ingeniería (piensa en la fabricación de un circuito integrado y el orden en el que un láser tiene que realizar miles de perforaciones). El uso de la fuerza bruta para resolver uno de estos problemas implica el uso de superordenadores.

Otra característica interesante del PVC es que se considera particularmente difícil de resolver. Si se encuentra una forma de descomponerlo en problemas menores, estos problemas son al menos tan complejos como el original; esto es lo que se llama un problema NP-complejo.

Pero a poco que nos fijemos nos daremos cuenta de que el PVC es idéntico en planteamiento a la situación a la que se enfrentan las abejas, los pájaros y los primates que recolectan su alimento de lugares que están fijos en el espacio y que se recuperan con el tiempo (flores, granos, frutas). Estos animales tienden a visitar estos lugares en secuencias repetitivas. La cuestión es, ¿están optimizadas estas secuencias para conseguir la máxima cantidad de alimento con el menor gasto energético posible? O dicho de otra forma, resuelven estos animales el ¿problema del abejorro recolector?

Para encontrar un indicio de lo que puede ser una respuesta a estas preguntas un grupo de investigadores de la Universidad Queen Mary (Reino Unido) encabezados por Mathie Lihoreau ha estudiado los movimientos de los abejorros (Bombus terrestris) al recolectar néctar de 5 flores artificiales de distinta rentabilidad alimenticia. En un artículo publicado en diciembre de 2010 en The American Naturalist [1], este equipo de investigadores demostró que los abejorros saben encontrar la distancia mínima (óptima) cuando se trata de visitar flores de igual rentabilidad alimenticia. Ahora, han encontrado que resuelven el problema de encontrar la ruta óptima entre 120 posibles y considerando las dos variables. Publican sus resultados en Functional Ecology [2].

El equipo marcó numéricamente los abejorros que se alojaban en un nido artificial para poder diferenciarlos cuando visitaban cinco flores también artificiales dispuestas en los vértices de un pentágono regular. En primer lugar confirmaron sus estudios anteriores con flores de igual rentabilidad alimenticia (definida como la cantidad de néctar que se puede recolectar en una visita). Pero al hacer a una flor mucho más rentable que las demás forzaron en una segunda fase a los abejorros a decidir entre seguir la ruta más corta o visitar la flor más rentable primero, o cualquier combinación intermedia.

Los abejorros después de explorar la nueva disposición unas cuantas veces terminaron ajustándose a distintos patrones en función de la posición de la flor más rentable. Si visitarla primero suponía un incremento en la distancia sobre el óptimo del 18% o menos, los abejorros ponían la flor más rica la primera de la lista. Si la desviación sobre la distancia óptima era superior al 42% los abejorros se ceñían al recorrido más corto. Entre ambas cifras, soluciones intermedias que tendían a maximizar la rentabilidad alimenticia del recorrido.

Esto quiere decir que los abejorros intentaban optimizar tanto la distancia recorrida como la recogida de néctar conforme ganaban experiencia con las flores. Pero démonos cuenta de lo que significa cognitivamente además de matemáticamente resolver el problema del abejorro recolector: imagina que quieres recoger lo máximo con el mínimo esfuerzo; para ello necesitas recordar tanto la localización como la rentabilidad de cada flor así como las rutas conocidas en tu intento de resolver un problema NP-complejo. Ahora añade que eres un abejorro con cerebro de abejorro y que no puedes usar un ordenador...

Esta entrada es una participación de Experientia docet en la Edición 2.5 del Carnaval de Matemáticas que acoge Juegos topológicos, y en la V Edición del Carnaval de Biología que organiza Feelsynapsis.

Referencias:

[1] Lihoreau, M., Chittka, L., & Raine, N. (2010). Travel Optimization by Foraging Bumblebees through Readjustments of Traplines after Discovery of New Feeding Locations The American Naturalist, 176 (6), 744-757 DOI: 10.1086/657042

[2] Lihoreau, M., Chittka, L., & Raine, N. (2011) Trade-off between travel distance and prioritization of high-reward sites in traplining bumblebees Functional Ecology DOI: 10.1111/j.1365-2435.2011.01881.x