Un organismo ameboide unicelular, un plasmodio del verdadero moho de lodo Physarum polycephalum. Crédito: Masashi Aono
Investigadores en Universidad de Hokkaido y Amoeba Energy en Japón, inspirados por el comportamiento de búsqueda eficiente de una ameba unicelular, desarrollaron una computadora analógica para encontrar una solución confiable y rápida al problema del viajante de comercio: un problema representativo de optimización combinatoria.
Muchas tareas de aplicaciones del mundo real, como la planificación y programación en logística y automatización, se formulan matemáticamente como problemas de optimización combinatoria. Las computadoras digitales convencionales, incluidas las supercomputadoras, son inadecuadas para resolver estos complejos problemas en un tiempo prácticamente permisible, ya que la cantidad de soluciones candidatas que necesitan evaluar aumenta exponencialmente con el tamaño del problema, también conocido como explosión combinatoria. Por lo tanto, en los últimos años se han desarrollado activamente nuevas computadoras llamadas “máquinas Ising”, que incluyen “atemperadores cuánticos”. Sin embargo, estas máquinas requieren un preprocesamiento complicado para convertir cada tarea a la forma que pueden manejar y tienen el riesgo de presentar soluciones ilegales que no cumplen con algunas limitaciones y solicitudes, lo que genera obstáculos importantes para las aplicaciones prácticas.
Diagrama de circuito de la ameba electrónica (izquierda: núcleo de ameba, derecha: barra transversal de resistencia). Crédito: Amoeba Energy
Estos obstáculos pueden evitarse utilizando la “ameba electrónica” de nuevo desarrollo, una computadora analógica inspirada en un organismo ameboide unicelular. Se sabe que la ameba maximiza la adquisición de nutrientes de manera eficiente al deformar su cuerpo. Se ha demostrado encontrar una solución aproximada al problema del viajante de comercio (TSP), es decir, dado un mapa de un cierto número de ciudades, el problema es encontrar la ruta más corta para visitar cada ciudad exactamente una vez y regresar a la ciudad de partida. Este hallazgo inspiró al profesor Seiya Kasai de la Universidad de Hokkaido a imitar la dinámica de la ameba electrónicamente utilizando un circuito analógico, como se describe en la revista. Informes científicos. “El núcleo de la ameba busca una solución en el entorno electrónico donde los valores de resistencia en las intersecciones de las barras transversales representan restricciones y solicitudes del TSP”, dice Kasai. Con las barras transversales, el diseño de la ciudad se puede modificar fácilmente actualizando los valores de resistencia sin un procesamiento previo complicado.
Rendimiento de búsqueda de solución TSP de la ameba electrónica en función del número de ciudades, N. (Izquierda) La longitud de ruta obtenida por la ameba electrónica (puntos rojos) se normalizó por la longitud promedio calculada por muestreo aleatorio. (Derecha) Tiempo de búsqueda de la solución de la ameba electrónica (puntos rojos) y el de 2-opt ejecutado en una computadora convencional (círculo blanco), donde el eje vertical representa el incremento de los resultados para el TSP de 10 ciudades. Crédito: Masashi Aono
Kenta Saito, un estudiante de doctorado en el laboratorio de Kasai, fabricó el circuito en una placa y logró encontrar la ruta más corta para el TSP de 4 ciudades. Evaluó el rendimiento para problemas de mayor tamaño utilizando un simulador de circuitos. Luego, el circuito encontró de manera confiable una solución legal de alta calidad con una longitud de ruta significativamente más corta que la longitud promedio obtenida por el muestreo aleatorio. Además, el tiempo necesario para encontrar una solución legal de alta calidad creció solo linealmente en función del número de ciudades. Al comparar el tiempo de búsqueda con un algoritmo TSP representativo “2-opt”, la ameba electrónica se vuelve más ventajosa a medida que aumenta el número de ciudades. “El circuito analógico reproduce bien la capacidad de optimización única y eficiente de la ameba, que el organismo ha adquirido a través de la selección natural”, dice Kasai.
“Dado que la computadora analógica consta de un circuito simple y compacto, puede abordar muchos problemas del mundo real en los que las entradas, las restricciones y las solicitudes cambian dinámicamente y pueden integrarse en dispositivos de IoT como un microchip de ahorro de energía”, dice Masashi Aono, quien lidera Amoeba Energy para promover el uso práctico de las computadoras inspiradas en amebas.
Referencia: “Sistema informático electrónico analógico inspirado en la ameba que integra una barra transversal de resistencia para resolver el problema del viajante de comercio” por Kenta Saito, Masashi Aono y Seiya Kasai, 27 de noviembre de 2020, Informes científicos.
DOI: 10.1038 / s41598-020-77617-7
