Resulta que las hormigas son extremadamente buenas para estimar la concentración de otras hormigas en su vecindad. Esta habilidad parece jugar un papel en varias actividades comunales, particularmente en el procedimiento de votación mediante el cual una colonia de hormigas selecciona un nuevo nido.
Los biólogos han sospechado durante mucho tiempo que las hormigas basan sus estimaciones de densidad de población en la frecuencia con la que, literalmente, se topan con otras hormigas mientras exploran aleatoriamente sus entornos.
Esa teoría recibe un nuevo respaldo de un artículo teórico que los investigadores del Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT presentarán en la conferencia del Simposio de la Asociación para la Maquinaria de Computación sobre los Principios de la Computación Distribuida a finales de este mes. El documento muestra que las observaciones de la exploración aleatoria delel entorno converge muy rápidamente en una estimación precisa de la densidad de población. De hecho, convergen casi tan rápido como es teóricamente posible.
Más allá de ofrecer soporte para las suposiciones de los biólogos, este marco teórico también se aplica al análisis de redes sociales, a la toma de decisiones colectivas entre enjambres de robots y a la comunicación en redes ad hoc, como redes de sensores de bajo costo dispersos en entornos prohibidos.
"Es intuitivo que si un grupo de personas camina al azar por un área, la cantidad de veces que se topan será un sustituto de la densidad de población", dice Cameron Musco, un estudiante graduado del MIT en ingeniería eléctrica y computaciónciencia y un coautor del nuevo artículo. "Lo que estamos haciendo es dar un análisis riguroso detrás de esa intuición, y también decir que la estimación es una muy buena estimación, en lugar de una estimación aproximada. En función del tiempo,se vuelve cada vez más preciso y va casi tan rápido como cabría esperar que pudieras hacer "
caminatas aleatorias
Musco y sus coautores, su asesor, la profesora NEC de Ciencia e Ingeniería de Software, Nancy Lynch, y Hsin-Hao Su, un postdoc en el grupo de Lynch, caracterizan el entorno de una hormiga como una grilla, con algunas otras hormigas dispersas al azara través de él. La hormiga de interés, llámelo explorador, comienza en alguna celda de la cuadrícula y, con igual probabilidad, se mueve a una de las celdas adyacentes. Luego, con igual probabilidad, se mueve a una de las celdas adyacentesa esa, y así sucesivamente. En estadística, esto se conoce como una "caminata aleatoria". El explorador cuenta la cantidad de otras hormigas que habitan en cada celda que visita.
En su artículo, los investigadores comparan la caminata aleatoria con el muestreo aleatorio, en el que las celdas se seleccionan de la cuadrícula al azar y se cuenta el número de hormigas. La precisión de ambos enfoques mejora con cada muestra adicional, pero notablemente, la caminata aleatoriaconverge en la densidad de población real prácticamente tan rápido como el muestreo aleatorio.
Eso es importante porque en muchos casos prácticos, el muestreo aleatorio no es una opción. Supongamos, por ejemplo, que desea escribir un algoritmo para analizar una red social en línea; por ejemplo, para estimar qué fracción de la red se describe a sí mismacomo republicano. No hay una lista disponible públicamente de los miembros de la red; la única forma de explorarla es elegir un miembro individual y comenzar a buscar conexiones.
Del mismo modo, en redes ad hoc, un dispositivo dado solo conoce las ubicaciones de los dispositivos en sus inmediaciones; no conoce el diseño de la red en su conjunto. Un algoritmo que utiliza recorridos aleatorios para agregar información de múltiples dispositivossería mucho más fácil de implementar que uno que tenga que caracterizar la red como un todo.
Repetir encuentros
El resultado de los investigadores es sorprendente porque, en cada paso de una caminata aleatoria, el explorador tiene una probabilidad significativa de regresar a una celda que ya ha visitado. Por lo tanto, una estimación derivada de caminatas aleatorias tiene una probabilidad mucho mayor de sobremuestreo particularceldas que una basada en muestreo aleatorio.
Inicialmente, dice Musco, él y sus colegas asumieron que esto era una responsabilidad que un algoritmo para estimar la densidad de población tendría que superar. Pero sus intentos de filtrar datos sobremuestreados parecían empeorar el rendimiento de su algoritmo en lugar de mejorarlo.fueron capaces de explicar por qué, teóricamente.
"Si caminas aleatoriamente alrededor de una cuadrícula, no vas a toparte con todos, porque no vas a cruzar toda la cuadrícula", dice Musco. "Así que hay alguien en el otro extremo de la cuadrículaque tengo casi un cero por ciento de posibilidades de toparme. Pero aunque me toparé con esos tipos menos, tropezaré más con los tipos locales. Necesito contar todas mis interacciones con los tipos locales para compensar el hechoque existen estos tipos lejanos con los que nunca me voy a encontrar. Se equilibra perfectamente. Es realmente fácil demostrar eso, pero no es muy intuitivo, por lo que nos llevó un tiempo darnos cuenta de esto ".
Generalizaciones
La cuadrícula que los investigadores usaron para modelar el entorno de las hormigas es solo una instancia especial de una estructura de datos llamada gráfica. Una gráfica consta de nodos, típicamente representados por círculos y bordes, típicamente representados como segmentos de línea que conectan nodos.la cuadrícula, cada celda es un nodo, y comparte bordes solo con esas celdas inmediatamente adyacentes a ella.
Sin embargo, las técnicas analíticas de los investigadores se aplican a cualquier gráfico, como uno que describa qué miembros de una red social están conectados, o qué dispositivos en una red ad hoc están dentro del rango de comunicación entre ellos.
Si el gráfico no está muy bien conectado, si, por ejemplo, es solo una cadena de nodos, cada uno conectado solo a los dos nodos adyacentes, el sobremuestreo puede convertirse en un problema. En una cadena de, por ejemplo,100 nodos, un explorador que realiza una caminata aleatoria podría atascarse atravesando los mismos cinco o seis nodos una y otra vez.
Pero siempre que dos caminatas aleatorias que comiencen desde el mismo nodo puedan ramificarse en diferentes direcciones, como suele ser el caso en los gráficos que describen redes de comunicación, las caminatas aleatorias siguen siendo prácticamente tan buenas como el muestreo aleatorio.
Además, en el nuevo artículo, los investigadores analizan caminatas aleatorias ejecutadas por un solo explorador. Las observaciones agrupadas de muchos exploradores convergerían en una estimación precisa más rápidamente ". Si fueran robots en lugar de hormigas, podrían obtener ganancias hablando conel uno al otro y diciendo: 'Oh, esta es mi estimación' ", dice Musco.
Fuente de la historia :
Materiales proporcionado por Instituto de Tecnología de Massachusetts . Nota: El contenido puede ser editado por estilo y longitud.
Cite esta página :