Los investigadores han demostrado que una ameba, un organismo unicelular que consiste principalmente en protoplasma gelatinoso, tiene capacidades informáticas únicas que algún día pueden ofrecer una alternativa competitiva a los métodos utilizados por las computadoras convencionales.

Los investigadores, dirigido por Masashi Aono en la Universidad de Keio, asignó una ameba para resolver el problema del vendedor ambulante (TSP). El TSP es un problema de optimización en el que el objetivo es encontrar la ruta más corta entre varias ciudades, para que cada ciudad se visite exactamente una vez, y los puntos de inicio y final son los mismos.

El problema es NP-hard, lo que significa que a medida que aumenta el número de ciudades, el tiempo necesario para que una computadora lo resuelva crece exponencialmente. La complejidad se debe a la gran cantidad de posibles soluciones. Por ejemplo, para cuatro ciudades, solo hay tres rutas posibles. Pero para ocho ciudades, el número de rutas posibles aumenta a 2520.

En el nuevo estudio, Los investigadores encontraron que una ameba puede encontrar soluciones razonables (casi óptimas) para el TSP en un período de tiempo que crece solo de forma lineal a medida que el número de ciudades aumenta de cuatro a ocho. Aunque las computadoras convencionales también pueden encontrar soluciones aproximadas en tiempo lineal, El enfoque de la ameba es completamente diferente al de los algoritmos tradicionales. Como explican los científicos, la ameba explora el espacio de la solución redistribuyendo continuamente el gel en su cuerpo amorfo a una velocidad constante, así como procesando la retroalimentación óptica en paralelo en lugar de en serie.

Aunque una computadora convencional todavía puede resolver el TSP mucho más rápido que una ameba, especialmente para problemas de tamaño pequeño, los nuevos resultados son intrigantes y pueden conducir al desarrollo de nuevas computadoras analógicas que deriven soluciones aproximadas de problemas computacionalmente complejos de tamaños mucho mayores en tiempo lineal.

Cómo funciona

El tipo particular de ameba que usaron los científicos fue un plasmodio o "verdadero moho de limo, "que pesa alrededor de 12 mg y consume copos de avena. Esta ameba deforma continuamente su cuerpo amorfo al suministrar y retirar gel repetidamente a una velocidad de aproximadamente 1 mm / segundo para crear apéndices similares a pseudópodos.

En sus experimentos, los investigadores colocaron la ameba en el centro de un chip estrellado, que es una placa redonda con 64 canales estrechos que se proyectan hacia afuera, y luego colocó el chip encima de una placa de agar. La ameba está confinada dentro del chip, pero aún puede moverse a los 64 canales.

Para maximizar su absorción de nutrientes, la ameba intenta expandirse dentro del chip para entrar en contacto con la mayor cantidad de agar posible. Sin embargo, a la ameba no le gusta la luz. Dado que cada canal se puede iluminar de forma selectiva con luz, es posible obligar a la ameba a retirarse de los canales iluminados.

Para modelar el TSP, cada canal en el chip estrellado representa una ciudad ordenada en la ruta del vendedor. Por ejemplo, en el caso de cuatro ciudades etiquetadas como A-D, si la ameba ocupa los canales A4, B2, C1, y D3, entonces la solución correspondiente al TSP es C, B, D, A, C.

Para guiar a la ameba hacia una solución óptima o casi óptima, la clave está en controlar la luz. Para hacer esto, los investigadores utilizan un modelo de red neuronal en el que cada seis segundos el sistema actualiza qué canales están iluminados. El modelo incorpora información sobre la distancia entre cada par de ciudades, así como la retroalimentación de la posición actual de la ameba en los canales.

El modelo asegura que la ameba encuentre una solución válida al TSP de varias maneras. Por ejemplo, una vez que la ameba ha ocupado una cierta fracción de un canal en particular, di A3, luego los canales A1, A2, y todos los demás canales "A" están iluminados para evitar que la ciudad A sea visitada dos veces. También, B3, C3, D3, y todos los otros "3" canales están iluminados para prohibir visitas simultáneas a múltiples ciudades.

El modelo tiene en cuenta las distancias entre ciudades al facilitar la iluminación de canales que representan ciudades con distancias más largas que con distancias más cortas. Por ejemplo, digamos que la ameba ocupa el canal B2, y ha comenzado a invadir los canales C3 y D3 en cantidades iguales, y la distancia entre las ciudades B y C es 100 mientras que la distancia entre las ciudades B y D es 50. La distancia más larga entre B y C eventualmente hace que el sistema ilumine el canal C3, provocando que la ameba se retire de ese canal pero permitiendo que continúe moviéndose hacia D3.

En general, modelar el TSP con una ameba aprovecha la tendencia natural de la ameba a buscar un equilibrio estable. Como es menos probable que los canales que representan rutas más cortas estén iluminados, la ameba puede extenderse en esos canales y continuar explorando otros canales no iluminados para maximizar su área de superficie en la placa de agar.

Los investigadores también desarrollaron una simulación por computadora llamada AmoebaTSP que imita algunas de las características principales de cómo la ameba aborda el problema. incluido el movimiento continuo del gel a medida que se suministra a un ritmo constante y se extrae de varios canales.

"En nuestro chip estrellado para resolver el norte -Ciudad TSP, el área total del cuerpo de la ameba se convierte en norte cuando la ameba finalmente encuentra una solución aproximada, "Aono dijo Phys.org . “Parece haber una 'ley' de que la ameba suministra su recurso gelatinoso para expandirse en los canales no iluminados a un ritmo constante, decir, X . Esta ley se mantendrá incluso cuando algunos recursos se recuperen de los canales iluminados. Luego, el tiempo necesario para expandir el área del cuerpo. norte representar la solución se convierte en norte / X . Este mecanismo sería el origen del tiempo lineal, y fue reproducido por nuestro modelo de simulación por computadora.

"Pero aún, el mecanismo por el cual la ameba mantiene la calidad de la solución aproximada, es decir, la corta longitud de la ruta, sigue siendo un misterio. Parece que los movimientos correlacionados espacial y temporalmente de las partes ramificadas de la ameba ubicadas en canales distantes son la clave. Cada una de estas ramas está oscilando su volumen con alguna "memoria" temporal sobre experiencias iluminadas. Los grupos de las ramas realizan la sincronización y desincronización para compartir información aunque estén espacialmente distantes ".

En el futuro, los investigadores planean mejorar aún más las habilidades informáticas de la ameba.

"Investigaremos más a fondo cómo estas complejas dinámicas oscilatorias espacio-temporales mejoran el rendimiento computacional para encontrar soluciones de mayor calidad en menos tiempo, ", dijo el coautor Song-Ju Kim de la Universidad de Keio". Si pudiera aclararse, el conocimiento contribuirá a crear novedosas computadoras analógicas que exploten la dinámica espacio-temporal de la corriente eléctrica en su circuito.

"Por supuesto, ejecutar algunos otros algoritmos en computadoras digitales tradicionales para tiempo lineal, podemos derivar soluciones aproximadas a TSP. Por otra parte, al ejecutar nuestros modelos de simulación (AmoebaTSP o sus versiones desarrolladas) en las computadoras tradicionales como hicimos en este estudio, las dinámicas espacio-temporales analógicas y paralelas requieren un tiempo no lineal para simularlas como procesos digitales y seriales. Por lo tanto, estamos tratando de obtener soluciones de mucha mayor calidad que las derivadas de las tradicionales ejecutando nuestros modelos en las computadoras analógicas durante un tiempo lineal o más corto ".

Los investigadores también esperan que, fabricando un chip más grande, la ameba podrá resolver problemas de TSP con cientos de ciudades, aunque esto requeriría decenas de miles de canales.

© 2018 Science X Network