Hormigas y transferencia de datos en Internet

Por Guillermo Peris Ripollés, el 18 octubre, 2016. Categoría(s): Biología • Divulgación • Matemáticas

Algoritmos basados en animales (I)

SONY DSC

Durante los últimos años, el uso de herramientas informáticas para la resolución de problemas biológicos y médicos se ha extendido tanto que hoy en día resulta impensable no utilizar programas de ordenador para el análisis de datos biomédicos. Por ejemplo, resultan imprescindibles en el análisis de ADN y otros biomarcadores, simulación computacional de modelos de moléculas candidatas a fármacos, generación e interpretación de imágenes médicas… Pero, ¿ocurre la misma transferencia de información en sentido contrario? ¿Nos ayudan los sistemas biológicos a mejorar algunos de los programas que usamos a diario en nuestros ordenadores y móviles?

Los organismos vivos han encontrado a lo largo de millones de años de evolución algoritmos para optimizar diversas funciones. Algunas de estas estrategias para la resolución de problemas particulares de su entorno, una vez estudiadas y entendidas, pueden ser aplicadas a problemas tecnológicos concretos. Incluso existen áreas de investigación que estudian la transferencia de estrategias entre organismos vivos y tecnología, como la inteligencia de enjambre (swarm intelligence) que ya se utiliza en inteligencia artificial. Voy a intentar mostrar algunos ejemplos de esta informática basada en animales en una serie de artículos. Un primer ejemplo muy conocido y que no deja de sorprender es la gestión de recursos de las colonias de hormigas.


Las hormigas han perfeccionado un sistema que les permite minimizar los recursos que la colonia invierte en su conjunto para llevar comida al hormiguero. De este parten inicialmente, a modo de expedición, varias hormigas buscando comida que vagan al azar hasta encontrar una fuente de alimentación. En cuanto la encuentran inician su regreso al hormiguero por trayectos más o menos largos. Pero, a medida que pasa el tiempo, las nuevas exploradoras que parten del hormiguero acaban llegando hasta la comida y regresando con ella al hormiguero siguiendo la ruta más eficiente y, por tanto, consumiendo menos tiempo en ello y beneficiando la gestión global de la colonia. ¿Cómo lo consiguen?

camino1

La clave está en el uso de señales químicas. Cuando las hormigas encuentran una fuente de comida vuelven al hormiguero marcando el camino de regreso con feromonas, como se muestra en la siguiente figura. Ese camino puede ser más o menos largo en función de la trayectoria o los obstáculos que encuentren.

camino2

Las nuevas hormigas que salen en busca de comida siguen los rastros dejados por sus compañeras. Pero las feromonas tienden a evaporarse con el paso del tiempo y eso hace que los caminos más largos –al tardar más tiempo en ser recorridos– pierdan la señal con mayor rapidez. Por ello, a medida que pasa el tiempo se refuerza la señal de feromonas en el camino más corto.

camino3

Además, en cuanto una fuente de comida se termina las hormigas buscan alimento en otros lugares, por lo que la señal de ese supermercado se atenúa progresivamente. Otra ventaja es que ante cambios en el camino –por la presencia de un nuevo obstáculo, por ejemplo– esta estrategia permite una rápida adaptación.

En el siguiente vídeo puede verse una simulación de hormigas buscando alimento y llevándolo al hormiguero. En la imagen se muestra en color violeta el hormiguero, en azul las fuentes de comida y en verde el rastro de feromonas. Fíjense en cómo tiene más intensidad el rastro en los caminos más cortos hacia la comida y en cómo decrece cuando esta se termina.

[youtube]https://www.youtube.com/watch?v=kN0M49iqFRc[/youtube]

Transferencia de datos en internet

Internet es una red global formada por ordenadores, routers y otros dispositivos en la que cada uno de estos nodos está unido al resto por uno o varios caminos. Para acceder a la información que provee un servidor (por ejemplo, para abrir una página web externa en nuestro navegador) hay que seguir un camino que pasa por varios de estos nodos. Si queremos que el acceso sea rápido, es conveniente que los datos recorran la ruta que consuma menos tiempo y en la que haya menos congestión.

Mapa de conexiones de internet entre dos nodos vecinos obtenido en 2005 (más información).
Mapa de conexiones de internet entre dos nodos vecinos obtenido en 2005 (más información).

El cálculo del camino más corto entre dos nodos cualesquiera de internet no es tan sencillo como podría ser la estimación de la distancia más corta de dos ciudades en un GPS, porque el tráfico en internet varía muy rápidamente: hay servidores que se caen, aumento de la congestión en un determinado punto, nuevos ordenadores que se conectan a la red… Un camino muy rápido en un momento determinado puede saturarse de usuarios y congestionarse, y al mismo tiempo aparecer nuevos caminos con poco tráfico, por lo que es conveniente una buena distribución de los datos a través de toda la red. De tomar la decisión de qué camino es el más adecuado para acceder a un servidor se encargan los enrutadores, que mantienen un listado de «vías rápidas». Esta lista se actualiza con frecuencia utilizando algoritmos que tienen en cuenta la situación dinámica de la red.

Para conseguir este propósito, los enrutadores mantienen una tabla con los posibles destinos de la red (de la red en la que se encuentran, que no es todo internet) y cuál es el coste de llegar a cada uno de ellos, así como cuál es el siguiente nodo para continuar el camino de los datos. Esta tabla debe actualizarse para tener datos de tráfico de la red en tiempo real, para lo cual existen distintos algoritmos. Uno de ellos, AntNet, se basa en el envío de «hormigas» (realmente, paquetes de datos capaces de almacenar información) a recorrer toda la red, de una forma muy semejante a como hacen las hormigas reales. El procedimiento es el siguiente:

  1. Cada cierto tiempo, todos los nodos de la red envían «hormigas artificiales»  hacia otros nodos de la red elegidos aleatoriamente. En la siguiente imagen se muestra como ejemplo un nodo A  del que parten hormigas hasta otro nodo destino G. Los números en las aristas indican el tiempo de recorrido de cada arista en unidades arbitrarias. Obviamente, este tiempo no se conoce hasta que no se atraviesa la arista.
    grafo1
  2. En esta búsqueda del nodo destino, cada hormiga almacena los datos del camino: nodos atravesados, tiempo entre nodo y nodo, etc.
    grafo2
  3. Tras llegar (por distintos caminos) al nodo destino, las hormigas regresan al nodo de partida (el hormiguero) por el mismo camino dejando en cada nodo que atraviesan «feromonas», es decir, los datos de tiempo de acceso al nodo destino desde el nodo intermedio. Básicamente, actualizan las tablas de enrutamiento. Si muchas hormigas vuelven por el mismo nodo, sólo se almacena la información del camino más rápido.

grafo3

Este algoritmo basado en la búsqueda de alimento de las colonias de hormigas demostró ser superior a otros algoritmos para la actualización de las tablas de enrutamiento, utilizado en distintas condiciones de sobrecarga de red.

Congestión de red

Otro aspecto interesante (por su relación con algoritmos computacionales) es la gestión que hace el hormiguero de cuántos individuos envía a buscar comida y la frecuencia con que lo hace. Las hormigas recolectoras no regresan al hormiguero hasta que encuentran alimento, aunque ello suponga su muerte. Ello supone que, por ejemplo, enviar muchas hormigas a por comida en días de mucho sol puede suponer que mueran deshidratadas sin encontrar comida. Sin embargo, las colonias no envían muchas hormigas los días de mucho calor. Tampoco lo hacen si los focos de comida están relativamente lejos. ¿Cómo regulan esta situación?

De nuevo, la solución la toman las hormigas individuales y no la colonia en su conjunto. Inicialmente salen unas pocas exploradoras a buscar por los alrededores del hormiguero, y no salen más hormigas a por comida a menos que regresen las primeras que partieron y lo hagan con rapidez. Cada vez que una hormiga regresa con comida, toca con sus antenas a las compañeras que esperan en el hormiguero, pero estas no parten a por más provisiones a menos que haya una cierta frecuencia en la llegada de hormigas. Si no hay comida, esta está muy lejos o algún problema impide el regreso de las hormigas, disminuye la frecuencia del contacto y no salen más individuos recolectores. De nuevo, no existe una gestión global del hormiguero, ni órdenes a seguir, sino que todas las acciones se toman de forma individual por cada miembro de la colonia.

Fuente
Fuente

Los servidores de datos de internet utilizan una estrategia similar a esta para evitar los problemas de congestión de red. Hay que tener en cuenta que, aunque se conozca cuál es el mejor camino para enviar datos de un servidor a un cliente, a veces ocurren problemas de red, caídas de servidores, etc, que pueden hacer que los datos enviados no lleguen a su destino.

Cuando un servidor envía datos a nuestro dispositivo no lo hace de forma íntegra, sino que trocea la información y la envía en pequeños paquetes de datos que se reconstruyen en nuestro ordenador. Inicialmente se envían pocos paquetes de datos (slow start), del mismo modo que sólo parten inicialmente unas pocas hormigas recolectoras del hormiguero. Conforme van llegando a su destino esos paquetes de datos, se envían avisos al servidor (acks, de acknowledgements) de que la recepción ha sido correcta. Antes de enviar más paquetes de datos, el servidor espera a recibir esos acks, y al hacerlo envía una cantidad de datos aún mayor. Si deja de recibir «acuses de recibo» en un tiempo, corta la conexión e intenta reestablecerla posteriormente. Si los acks se reciben con rapidez es que hay una buena conexión así que pueden enviarse un mayor número de paquetes de datos. Sí, exactamente lo mismo que ocurre con la gestión de la colonia de hormigas de cuántas exploradoras se envían a por comida en función de la frecuencia con que llegan hormigas con comida.

En este caso, no fue la naturaleza la que inspiró el algoritmo informático, ya que esta semejanza se encontró a posteriori al estudiar el comportamiento de las hormigas recolectoras. Eso sí, a las hormigas se les ocurrió antes que a nosotros.

Para terminar, te animo a ver esta charla que da la experta mundial en hormigas Deborah Gordon, en la que explica otras utilidades algorítmicas de estos insectos.

[youtube]https://www.youtube.com/watch?v=aL00a3sfnYM[/youtube]

Más información



Por Guillermo Peris Ripollés, publicado el 18 octubre, 2016
Categoría(s): Biología • Divulgación • Matemáticas