Ordenando cementerios y guarderías de hormigas

Algoritmos basados en animales (IV)

simpsonsportada

Al poco de nacer nuestro cerebro aprende a asignar clases a los objetos, de forma que reconocemos una silla, un coche o una nube. Previamente hemos adquirido la idea de esas clases y somos capaces de generar nuevas clases para etiquetar nuevos objetos. Pero en ocasiones la complejidad de los datos hace difícil la clasificación y es necesaria la intervención de ordenadores y algoritmos que dividen los elementos individuales en distintos grupos, bien conociendo previamente las clases posibles (lo que se conoce como clasificación supervisada), o bien sin saber a priori en qué grupos podrá finalmente dividirse el conjunto de datos (no supervisada, sin conjunto de entrenamiento). El agrupamiento de datos o clustering suele hacer referencia a esta última variante. Veamos un ejemplo.

Imaginemos que tenemos a este conjunto de personajes de los Simpson.

simpsons

¿Cómo los distribuirías en grupos, sin saber a priori en cuantas clases se han de dividir? Una primera opción podría consistir en separarlos por su sexo: hombres y niños en un grupo y mujeres y niñas en otro.

simpsons1

Pero según el cometido de la clasificación esta clasificación sería adecuada o no. También podríamos hacer un grupo con los miembros de la familia Simpson y otro con los personajes que trabajan en el colegio.

simpsons2

Pero, ¿quién nos dice que vaya a haber dos grupos? Según las características del problema que vayamos a resolver (por ejemplo, si buscamos un agrupamiento como posibles clientes de una tienda de ropa), puede que sea más adecuada una división entre hombres, mujeres y niños.

simpsons3

El agrupamiento más adecuado al problema concreto puede conseguirse con un algoritmo de agrupamiento no supervisado.  Estos algoritmos lo que persiguen es, a partir de las características de un conjunto de datos, decidir cuáles son las clases en que se pueden separar sin ningún conocimiento previo sobre estas. Ejemplos clásicos de clustering serían la generación de perfiles de clientes, la ordenación taxonómica de seres vivos en biología o la clasificación de documentos.

Existen algoritmos clásicos que permiten un agrupamiento no supervisado con diferente eficiencia, como el algoritmo de las k-medias, pero como en el resto de artículos de esta serie estamos interesados en si la naturaleza ha sabido resolver este problema. Y de nuevo vamos a buscar la solución en nuestras amigas las hormigas.

Cementerios de hormigas

Un primer caso de agrupación (aunque no de clasificación) lo constituye la formación de cementerios de hormigas. Muchas especies de hormigas se deshacen de los individuos muertos organizando una especie de camposantos, acumulando para ello en varios montones a las hormigas fallecidas. Este comportamiento fue descubierto por primera vez en la especie Lasius Niger.

1-figure1-1
Formación de cementerios de hormigas en laboratorio. Las fotografías reflejan la situación inicial y las agrupaciones al cabo de 3, 6 y 36 horas, respectivamente (fuente).

Al contrario que el comportamiento de las hormigas en la búsqueda de comida y envío de exploradores que ya se describió en el primer artículo de la serie, la formación de cementerios aún no se comprende completamente. No obstante se han desarrollado varios modelos matemáticos que tratan de explicar este fenómeno.

El primer algoritmo lo desarrollaron Deneubourg y colaboradores y se basa en unas reglas extremadamente simples. En él se asume que las hormigas trabajadoras recorren aleatoriamente el terreno y cada vez que encuentran un cadáver deciden si lo recogen o no según una probabilidad pR. Si llevan un cadáver a cuestas, en cada paso deciden si depositarlo o no según una probabilidad pD. Estas probabilidades se calculan según las siguientes ecuaciones.

formulas

En estas ecuaciones, k1 y k2 son los parámetros que definen el modelo y f es (simplificando) la densidad de cadáveres que tiene a su alrededor la hormiga “enterradora”. Tratemos de explicar estas ecuaciones. Si la densidad f es muy baja significa que apenas hay hormigas muertas cerca (se está lejos de un cluster) por lo que si se encuentra un cadáver la probabilidad de recogerlo es alta (pR tiende a 1) y la probabilidad de depositarlo baja (pD tiende a 0). En las proximidades de un cluster el valor de f es alto, por lo que nuestra hormiga no recogerá cadáveres (pR tiende a 0) y, en caso de llevar un cuerpo, lo depositará (pD tiende a 1). En la siguiente figura se muestra una simulación de estas ecuaciones.

simulacion
Simulación del modelo de agrupamiento de Deneubourg, con imágenes obtenidas a distintos tiempos que aumentan de izquierda a derecha y de arriba a abajo (fuente).

En este ejemplo no hay una clasificación de objetos ya que sólo existe una clase: los cadáveres de hormigas. No obstante, el modelo matemático anterior se puede modificar para incluir las probabilidades de recoger o depositar distintos tipos de objetos. Pero, ¿puede que ya hayan pensado en esto nuestras amigas las hormigas?

Guarderías de hormigas

La especie de hormiga Leptothorax unifasciatus se encarga del cuidado de sus crías de una forma muy peculiar. El desarrollo de esta especie (al igual que en otras especies de hormiga) desde que la hormiga reina pone los huevos pasa por distintas fases de larva y pupa antes de llegar al ejemplar adulto.

pseudomyrmex_gracilis_egg_to_ant
Desarrollo larvario de la hormiga Pseudomyrmex gracilis desde el huevo al adulto pasando por la larva y la pupa (Alex Wild).

Lo que hace peculiares a las colonias de Leptothorax unifasciatus es que distribuyen a sus crías ordenándolas en círculos concéntricos agrupándolas por etapas de desarrollo. La progenie de las hormigas no es capaz de desplazarse, por lo que son hormigas obreras quienes se encargan de distribuir las crías en grupos. En estos clusters las crías en las fases más tempranas (huevos y microlarvas) se concentran en el centro y las larvas se sitúan cada vez más alejadas de este centro según su tamaño. Las larvas requieren más cuidados ya que se alimentan por trofalaxis (las hormigas regurgitan la comida para darles de comer). Esta ordenación garantiza que las crías que necesitan más atención se encuentren en los anillos exteriores de la agrupación y puedan atenderse en primer lugar.

clustersgraph2
Distribución de crías en una colonia de Leptothorax unifasciatus tras la migración a un nuevo nido. Únicamente se muestran tres tipos de cría: huevos y microlarvas (círculos negros), larvas medianas (cuadrados) y larvas grandes (círculos blancos). Fuente.

Las crías más desarrolladas (prepupas y pupas) se distribuyen en círculos intermedios entre las larvas medianas y grandes, quizás porque no requieren alimentación. Además, esta ordenación permite una especialización de las hormigas obreras, que no necesitan desplazarse para realizar el mismo tipo de cuidado.

¿Cómo se consigue esta ordenación? Podríamos pensar que la reina pone los huevos en el centro y a medida que crecen las crías se van desplazando hacia afuera, pero esto no explicaría la situación intermedia de las pupas. Además, cuando las colonias emigran por situaciones de peligro o escasez de comida, en el nuevo nido se crean rápidamente estas ordenaciones en círculos concéntricos.

Un análisis detallado de este traslado de nidos ha desvelado que la formación de estos agrupamientos ordenados tiene lugar en dos fases: una primera de formación de clusters aleatorios (de forma semejante a como se crean las pilas de cementerios) y una segunda en la que se va reasignando cada tipo de cría a su posición correcta. De hecho, mientras la migración está en proceso las hormigas obreras ya empiezan a ordenar a las crías trasladadas al nido.

Technomyrmex difficilis. En esta foto se ve a hormigas obreras junto con distintas fases del desarrollo: huevos, larvas y pupas.
Technomyrmex difficilis. En esta foto se ve a hormigas obreras junto con distintas fases del desarrollo: huevos, larvas y pupas (Alex Wild).

Aún no se comprende cómo se consigue esta ordenación de las crías, aunque hay varias hipótesis. La más simple es que las hormigas obreras las agrupan según tamaños, comparando el tamaño de un cría determinada con los tamaños de las crías cercanas. También se ha especulado con que las obreras poseen receptores que detectan los desechos de las crías y pueden diferenciarlas según la intensidad del olor.

Teniendo en cuenta estas hipótesis se han desarrollado varios algoritmos basados en los agrupamientos de crías de hormigas, muchos de los cuales se han aplicado en robótica. La idea es que robots autónomos y sin comunicación entre ellos sean capaces de recoger objetos de una zona y clasificarlos según su tipo. Si los robots no disponen de un sistema de localización no pueden determinar la situación de los distintos grupos de objetos ya clasificados, por lo que se han de basar en su entorno local para lograr una clasificación. Puede encontrarse una revisión de algoritmos de agrupación (y otros) basados en inteligencia de enjambre en esta revisión reciente.

Experimento de clasificación con seis robots programados con reglas basadas en clustering de hormigas (fuente).
Experimento de clasificación con seis robots programados con reglas basadas en clustering de hormigas (fuente).

Más información

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>