Soluciones del problema del vendedor ambulante obtenido por un sistema informático basado en amebas. Ejemplos de recorridos de vendedores en cuatro, cinco, seis, siete y ocho ciudades, obtenidos en experimentos, donde cada recorrido se pinta de rojo en los canales correspondientes de la figura correcta. Los paneles de la izquierda muestran las imágenes de luz transmitidas de los estados iniciales (Un grupo de investigadores japoneses de la Universidad de Keio en Tokio
demostró que la ameba es capaz de generar soluciones aproximadas a un problema matemático sorprendentemente complejo conocido como
el problema del vendedor ambulante .
La tarea del vendedor es una de las tareas de optimización combinatoria más conocidas, que consiste en encontrar la ruta más rentable que pase por estas ciudades al menos una vez y luego regresar a la ciudad original.
Sin embargo, la declaración de optimización del problema pertenece a la clase de problemas NP-hard, como la mayoría de sus casos especiales. La versión del "problema de decisión" (es decir, aquella en la que se plantea la cuestión de si la ruta existe más allá del valor dado de k) pertenece a la clase de problemas NP-completos.
La dificultad de calcular la solución correcta aumenta exponencialmente a medida que se agregan más ciudades a la tarea. Por ejemplo, para cuatro ciudades hay tres soluciones, y para seis ciudades: 360. En el futuro, el crecimiento exponencial continúa.
A pesar de la gran complejidad computacional, hay una gran cantidad de algoritmos heurísticos y precisos que pueden resolver completamente algunos casos con decenas de miles de ciudades, e incluso los problemas con millones de ciudades
pueden aproximarse en un 0.05% . El enlace indicado contiene intentos de resolver para una instancia de 1,904,711 ciudades de la Tierra desde la base de la Sociedad Geográfica Nacional.
Base de la Sociedad Geográfica Nacional de 1.904.711 ciudades.Por el momento, el récord de la distancia mínima para las ciudades de la Tierra es de 7 515 772 107 km, se estableció el 13 de marzo de 2018 utilizando el algoritmo heurístico
LKH .
El clásico problema del vendedor en informática se utiliza como punto de referencia para los algoritmos de optimización.
Las amebas son organismos unicelulares que no tienen idea de la complejidad de la optimización combinatoria. No tienen nada ni remotamente parecido al sistema nervioso central, lo que los hace candidatos menos adecuados para resolver problemas de tal complejidad. Sin embargo, los investigadores japoneses han descubierto que se puede usar un cierto tipo de ameba para calcular soluciones casi óptimas al problema del vendedor ambulante en ocho ciudades.
Según un
artículo científico , una ameba llamada
Physarum polycephalum , que anteriormente se había utilizado como computadora biológica en varios otros experimentos, participó en los experimentos. Esta criatura se considera especialmente útil en computación biológica porque puede expandir varias áreas de su cuerpo en busca de una forma más eficiente de obtener alimentos, y odia la luz.
Para convertir este mecanismo natural de nutrición en una computadora, los investigadores japoneses colocaron la ameba en un plato especial con 64 canales, en la dirección en la cual el animal podía estirar el cuerpo. La ameba intenta constantemente expandir el cuerpo para cubrir el área más grande posible de la placa de nutrientes. Sin embargo, cada canal en la placa puede iluminarse, lo que hace que la ameba salga de este canal por un sentimiento de aversión a la luz.
Para simular el problema del vendedor ambulante, a cada uno de los 64 canales en la placa se le asignó un código de ciudad entre A y H, además de un número del 1 al 8, que indica el orden de las ciudades (el orden de las ciudades corresponde al orden en que fueron visitadas por el vendedor).
Para programar la ameba, los investigadores utilizaron una red neuronal que incluía datos sobre la posición actual de la ameba y la distancia entre ciudades para iluminar canales específicos. La red neuronal tenía más probabilidades de iluminar ciudades (canales) con mayores distancias entre ellas.
Cuando el algoritmo y la ameba interactúan, este último toma una forma que representa soluciones aproximadas al problema del vendedor ambulante. Lo más interesante es que la cantidad de tiempo que le lleva a la ameba obtener estas soluciones casi óptimas crece
linealmente , aunque el número de opciones de solución aumenta
exponencialmente . En un futuro cercano, los investigadores fabricarán chips con decenas de miles de canales para que la ameba pueda intentar resolver el problema del vendedor ambulante en cientos de ciudades.
El artículo científico fue
publicado el 19 de diciembre de 2018 en la revista
Royal Society Open Science (doi: 10.1098 / rsos.180396).