Solución del problema del viajante utilizando un dispositivo combinatorio magnónico

Jul 27, 2023

Scientific Reports volumen 13, número de artículo: 11708 (2023) Citar este artículo

207 Accesos

Detalles de métricas

El problema del viajante de comercio (TSP) es un problema de toma de decisiones esencial para varias aplicaciones prácticas. Hoy en día, este problema se resuelve en los ordenadores digitales que explotan una arquitectura de tipo booleano comprobando una por una varias rutas posibles. En este trabajo, describimos un tipo especial de hardware para la solución TSP. Es un dispositivo combinatorio magnónico que comprende partes magnéticas y eléctricas conectadas en el circuito de anillo activo. Hay varias rutas de propagación posibles en la malla magnética formada por desfasadores, filtros de frecuencia y atenuadores. Los desfasadores imitan ciudades en TSP, mientras que la distancia entre las ciudades está codificada en la atenuación de la señal. El conjunto de filtros de frecuencia hace que las ondas en diferentes frecuencias se propaguen por las diferentes rutas. El principio de funcionamiento se basa en la superposición de ondas clásica. Hay una serie de ondas que llegan en todas las rutas posibles en paralelo, acumulando diferentes cambios de fase y amortiguación de amplitud. Sin embargo, sólo las ondas que acumulan un determinado cambio de fase serán amplificadas por la parte eléctrica. La amplificación llega primero a las ondas que poseen las mínimas pérdidas de propagación. Esto hace que este tipo de dispositivo sea adecuado para la solución TSP, donde las ondas son similares a las de los vendedores que viajan en todas las rutas posibles a la vez. Presentamos los resultados del modelado numérico que ilustra las soluciones TSP para cuatro y seis ciudades. Además, presentamos datos experimentales para la solución TSP con cuatro ciudades. El dispositivo prototipo está construido con componentes disponibles comercialmente, incluidos desfasadores/filtros magnéticos, cables coaxiales, divisores, atenuadores y un amplificador de banda ancha. Hay tres ejemplos de cómo encontrar la ruta más corta entre ciudades para tres conjuntos diferentes de distancias de ciudad a ciudad. El enfoque propuesto es escalable a TSP con un mayor número de ciudades. También se analizan los límites y desafíos físicos.

TSP es uno de los problemas de optimización combinatoria más conocidos1. Se puede expresar de la siguiente manera: "Dada una lista de ciudades y las distancias entre cada par de ciudades, encuentre la ruta más corta posible que visite cada ciudad exactamente una vez y regrese a la ciudad de origen". Es un problema de dureza de tiempo polinómico (NP-hard) no determinista, lo que significa que no hay garantía de obtener la ruta óptima ni un algoritmo exacto para resolverlo en tiempo polinómico. TSP es importante en una variedad de aplicaciones prácticas que incluyen transporte2, programación3 y genómica4. Matemáticamente, se puede definir como dado un conjunto de \(n\) ciudades, denominadas \(\left\{{c}_{1},{c}_{2},\dots ,{c}_{n }\right\}\), y permutaciones \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\} \). El objetivo es elegir \({\sigma }_{i}\) tal que se minimice la suma de todas las distancias euclidianas entre ciudades en un recorrido. TSP se puede modelar como un gráfico ponderado no dirigido como se muestra en la Fig. 1, donde las ciudades son los vértices del gráfico, las rutas son los bordes del gráfico y la distancia de una ruta es el peso del borde. TSP se puede resolver comprobando una por una todas las \(\left(n-1\right)!/2\) posibles rutas posibles. Es relativamente fácil comprobar todas las rutas posibles para un pequeño número de ciudades. Por ejemplo, hay \(\left(4-1\right)!/2=3\) rutas para el TSP con cuatro ciudades. El número de rutas posibles aumenta proporcionalmente a \(n\) factorial, lo que dificulta la resolución de un gran número de ciudades utilizando dispositivos informáticos clásicos.

Gráfico ponderado no dirigido para TSP con cuatro ciudades. Las ciudades son los vértices del gráfico, los caminos son los bordes del gráfico y la distancia de un camino es el peso del borde.

Hubo varios intentos de construir hardware especial para la solución TSP5,6. Por ejemplo, el TSP de 6 ciudades se resolvió utilizando una red óptica de tipo Kohonen6. Sin embargo, ninguno de estos enfoques dio como resultado un dispositivo prácticamente viable. Recientemente, se han aplicado a TSP7 una variedad de técnicas de optimización utilizadas en inteligencia artificial (IA). Puede acelerar significativamente la solución TSP, pero no puede proporcionar una ventaja fundamental si se implementa en hardware convencional.

Aquí, consideramos un tipo especial de dispositivo combinatorio en el que un acto de cálculo está asociado con encontrar una ruta de propagación de la onda a través de los nodos seleccionados en la malla. Este enfoque se describió por primera vez en la Ref.8. La idea principal es aprovechar la ventaja de la superposición de ondas clásica, donde varias ondas pueden propagarse a través de diferentes rutas al mismo tiempo. Quizás sea posible amplificar sólo aquellas señales que se propagan a través de los sitios seleccionados en la malla y acumulan un cierto cambio de fase. Los dispositivos de ondas de espín (magnónicos) son los más adecuados para este propósito debido a los importantes cambios de fase que se pueden lograr en guías de ondas de longitud micrométrica. El resto del trabajo se organiza de la siguiente manera. En la sección "Estructura del material y principio de funcionamiento", describimos el principio de funcionamiento del dispositivo de lógica combinatoria magnónica para TSP. Los resultados del modelado numérico que ilustran la solución TSP para cuatro y seis ciudades se presentan en la sección "Modelado numérico". Los datos experimentales de la solución TSP para cuatro ciudades se presentan en la sección "Datos experimentales". La Discusión y las Conclusiones se encuentran en las secciones “Discusión” y “Conclusiones”, respectivamente.

Los esquemas del dispositivo combinatorio para TSP con cuatro ciudades se muestran en la Fig. 2. El núcleo de la estructura es la malla que consta de desfasadores, atenuadores, filtros de frecuencia y sensores de potencia. Los círculos marcados con las letras A, B, C y D son desfasadores que representan las cuatro ciudades. Cada desfasador proporciona un cambio de fase único que es proporcional al logaritmo de un número primo. Por ejemplo, la ciudad A está representada por el desfasador que proporciona \(\pi \times \mathit{Log}\left(2\right)\) un cambio de fase a la señal que se propaga. La ciudad B está representada por el desfasador que proporciona \(\pi \times \mathit{Log}\left(3\right)\) cambio de fase, y así sucesivamente. Hay dos ciudades A, una a la izquierda y otra a la derecha de la malla. Esta es la ciudad desde la que parte el vendedor y a la que debe regresar después del viaje. Los desfasadores están conectados entre sí mediante guías de ondas. Hay un atenuador insertado en cada guía de ondas. La distancia entre las ciudades está codificada en la atenuación de la señal. Por ejemplo, se pueden tomar 10 millas equivalentes a 1 dB de atenuación. Hay un conjunto de filtros de paso de banda de frecuencia. Estos filtros tienen como objetivo garantizar diferentes frecuencias para diferentes rutas de propagación desde la ciudad A a la izquierda hasta la ciudad A a la derecha. Por ejemplo, sólo una señal con frecuencia \({f}_{1}\) puede propagarse a través de la ruta ABA; sólo una señal con frecuencia \({f}_{2}\) puede propagarse a través de la ruta ABCA, etc. También hay un conjunto de detectores de potencia insertados en cada guía de ondas. Estos detectores tienen como objetivo proporcionar la salida: la ruta de propagación de la señal. En la Fig. 2, los detectores están marcados como círculos de colores. El color verde representa el flujo de energía por encima de algún valor de referencia (por ejemplo, 1 dBm). El color rojo representa que no hay flujo de energía.

Esquemas del dispositivo combinatorio para TSP con cuatro ciudades. El núcleo de la estructura es la malla que consta de desfasadores, atenuadores, filtros de frecuencia y sensores de potencia. Los círculos marcados con las letras A, B, C y D son desfasadores que representan las cuatro ciudades. Cada desfasador proporciona un cambio de fase único que es proporcional al logaritmo de un número primo. Por ejemplo, la ciudad A está representada por el desfasador que proporciona \(\pi \times \mathit{Log}\left(2\right)\) un cambio de fase a la señal que se propaga. La ciudad B está representada por el desfasador que proporciona \(\pi \times \mathit{Log}\left(3\right)\) cambio de fase, y así sucesivamente. Hay dos ciudades A, una en el lado izquierdo y otro en el derecho de la malla. Esta es la ciudad desde la que parte el vendedor y a la que debe regresar después del viaje. Los desfasadores están conectados entre sí mediante guías de ondas. Hay un atenuador insertado entre cada par de ciudades. La distancia entre las ciudades está codificada en la atenuación de la señal. Por ejemplo, se pueden tomar 10 millas equivalentes a 1 dB de atenuación. Hay un conjunto de filtros de paso de banda de frecuencia. Estos filtros tienen como objetivo garantizar diferentes frecuencias para diferentes rutas de propagación desde la ciudad A a la izquierda hasta la ciudad A a la derecha.

Hay un amplificador de banda ancha \(G\), un desfasador sintonizable por voltaje \(\Psi\) y un atenuador sintonizable por voltaje \(R\) fuera de la malla. En adelante, nos referiremos a estos elementos como la parte “externa”. El amplificador de banda ancha debe proporcionar amplificación de señal para todas las frecuencias de señal. El desfasador sintonizable por voltaje y el atenuador sintonizable por voltaje controlan el cambio de fase y la atenuación de la parte externa. La combinación de la malla con la parte externa constituye un circuito en anillo activo multitrayecto8. Hay varias rutas posibles para que las señales se propaguen en la malla. Las diferentes rutas de propagación están asociadas con diferentes cambios de fase \(\Delta ({f}_{i})\) así como con diferentes atenuaciones de la señal \(L({f}_{i})\), donde \( {f}_{i}\) es la frecuencia de la señal que se propaga a través de la \(i\)-ésima ruta. Hay una superposición de ondas que se propagan por los diferentes caminos del circuito. Sin embargo, sólo algunas de las frecuencias se amplificarán para permitir oscilaciones automáticas estables. Hay dos condiciones para que se produzcan oscilaciones automáticas en un circuito en anillo activo9:

donde \(G\) es la ganancia proporcionada por el amplificador, \(R\) es la atenuación de la señal en la parte eléctrica, \(\Psi\) es el desfase de la parte eléctrica externa. La primera ecuación. (1) establece la condición de amplitud para las oscilaciones automáticas: la ganancia proporcionada por el amplificador de banda ancha debe ser suficiente para compensar las pérdidas en la malla y las pérdidas introducidas por el atenuador externo. La segunda ecuación establece la condición de fase para las autooscilaciones: el cambio de fase total para una señal que circula a través del anillo debe ser un múltiplo de \(2\pi .\). En este caso, las señales entran en fase en cada ronda de propagación. En la Ref.9 se puede encontrar una descripción más rigurosa de la propagación de señales en circuitos en anillo activo.

El procedimiento de cálculo para TSP es el siguiente. El desfasador externo \(\Psi\) está configurado al valor

donde el último término de la derecha es la suma de los retrasos de fase para las ciudades seleccionadas. En nuestro caso de cuatro ciudades,

Sólo las señales que se propagan a través de las ciudades seleccionadas (por ejemplo, A, B, C, D y A) se amplificarán ya que el desplazamiento de fase total a través del anillo es \(2\pi\). Las señales que se propagan a través de las ciudades seleccionadas pero de más de una (por ejemplo, ACBDCA) no se amplificarán porque el cambio de fase total no es un múltiplo de \(2\pi\). En la Ref.8 se puede encontrar una explicación más detallada de la amplificación selectiva de la señal en un circuito de anillo activo multitrayecto. Todas las demás señales que se propaguen por otras rutas (por ejemplo, ABA, ACDA, etc.) no se amplificarán porque no se cumple la condición de fase (2).

Entonces, es posible encontrar el camino más corto (es decir, el camino con pérdidas mínimas) usando el atenuador externo \(R\). Puede haber varias rutas para las cuales el cambio de fase total satisfaga la ecuación. (2). El número de rutas que satisfacen la condición de amplitud Ec. (1) disminuye con el aumento de la amortiguación externa \(R\). El camino más corto desaparecerá el último, ya que puede soportar la máxima amortiguación externa. Hay dos puntos importantes que queremos enfatizar con respecto al principio de funcionamiento. El sistema comienza con una superposición de todas las frecuencias posibles que se propagan por todos los caminos posibles. Podemos amplificar solo las señales que llegan a través de los nodos/ciudades seleccionados usando el desfasador externo para satisfacer la condición de fase (2). La ruta más corta se encuentra entonces introduciendo amortiguación adicional de modo que sólo la señal con pérdidas mínimas pueda satisfacer la condición de amplitud (1). En la siguiente sección, presentamos los resultados del modelado numérico que ilustra la solución TSP.

Para ilustrar el procedimiento de solución descrito anteriormente, presentamos los resultados del modelado numérico para el TSP de cuatro ciudades. En la Fig. 3A, se muestra un mapa de las 20 ciudades más divertidas de EE. UU. (fuente WalletHub). El viajante parte de Los Ángeles y tiene que visitar Miami, Washington, Chicago y regresar a Los Ángeles. Las distancias entre las ciudades se toman desde la aplicación Google Map. El problema se resuelve utilizando el dispositivo combinatorio que se muestra en la Fig. 2. Las distancias entre las ciudades se convierten en atenuación de la señal (por ejemplo, 1000 millas = 10 dB de atenuación).

(A) Mapa de Estados Unidos con las 20 ciudades más divertidas. El viajante parte de Los Ángeles y tiene que visitar Miami, Washington, Chicago y regresar a Los Ángeles. (B) Resultados del modelado numérico que muestra las distancias de todas las rutas posibles. Las rutas están marcadas con el #1, #2,… #27. Cada una de las rutas está asociada a una señal sinusoidal continua de alguna frecuencia \({f}_{1}\), \({f}_{2},\dots {f}_{27}\). (C) Resultados del modelado numérico que muestran cambios de fase para todas las rutas posibles. Sólo 6 rutas de 27 cumplen la condición de fase (2) y serán amplificadas. (D) Resultados del modelado numérico que representa la(s) ruta(s) más corta(s): Los Ángeles–Miami–Washington–Chicago–Los Ángeles y Los Ángeles–Chicago–Washington–Miami–Los Ángeles.

Hay 27 rutas posibles entre las cuatro ciudades (por ejemplo, Los Ángeles–Washington–Los Ángeles–Miami–Washington–Los Ángeles). En la Fig. 3B, se muestran las distancias de viaje para todas las rutas. Las rutas están marcadas con el #1, #2,… #27. Cada una de las rutas está asociada a una señal sinusoidal continua de alguna frecuencia \({f}_{1}\), \({f}_{2},\dots {f}_{27}\). Los valores de estas frecuencias no tienen importancia. Suponemos que los cambios de fase proporcionados por las ciudades no dependen de la frecuencia de la señal. El problema se resuelve en dos pasos. En el Paso 1, configuramos el desfasador externo de acuerdo con las Ecs. (3) y (4). Sólo las rutas que pasan por las cuatro ciudades y regresan a Los Ángeles se amplificarán en el circuito de anillo activo. En la Fig. 3C, se muestran cambios de fase para todas las rutas posibles. Sólo 6 rutas de 27 cumplen la condición de fase (2) y serán amplificadas. En el Paso 2, introducimos amortiguación adicional para el circuito eléctrico externo de modo que solo la ruta con pérdidas mínimas pueda satisfacer la condición (2). En la Fig. 3D, se muestran los resultados del modelado numérico que representa la(s) ruta(s) más corta(s) de seis posibles desde el Paso 1. En realidad, siempre hay dos rutas con la distancia más corta. En nuestro caso, son Los Ángeles–Miami–Washington–Chicago–Los Ángeles y Los Ángeles–Chicago –Washington–Miami–Los Ángeles.

El algoritmo descrito anteriormente se puede extender a un mayor número de ciudades. Por ejemplo, en la Fig. 4 se muestran los esquemas de un dispositivo para TSP con seis ciudades. Hay dos desfasadores más marcados como E y F agregados a la malla. Estos desplazadores proporcionan cambios de fase \(\pi \times \mathit{Log}\left(11\right)\) y \(\pi \times \mathit{Log}\left(13\right)\), respectivamente. Hay más interconexiones entre los sitios de la malla. Cada interconexión es una guía de ondas que incluye un atenuador, un filtro de frecuencia y un detector de potencia. Para simplificar, los atenuadores, filtros y detectores no se muestran en la Fig. 4. En este ejemplo, el vendedor ambulante que parte de Los Ángeles debe visitar Las Vegas, Chicago, Washington, Miami, San Francisco y regresar a Los Ángeles. El mapa con las ciudades se muestra en la Fig. 5A. La tabla con distancias de ciudad a ciudad se puede encontrar en los materiales complementarios. Hay más de 3000 rutas posibles como se muestra en la Fig. 5B. No todas estas rutas pasan por todas las ciudades seleccionadas. En el Paso 1, el desfasador externo se sintoniza para

Esquemas del dispositivo combinatorio para TSP con seis ciudades. Hay dos desfasadores más en comparación con la Fig. 2 marcados como E y F agregados a la malla. Estos desplazadores proporcionan cambios de fase \(\pi \times \mathit{Log}\left(11\right)\) y \(\pi \times \mathit{Log}\left(13\right)\), respectivamente.

(A) Mapa de Estados Unidos con las 20 ciudades más divertidas. El vendedor ambulante que parte de Los Ángeles debe visitar Las Vegas, Chicago, Washington, Miami, San Francisco y regresar a Los Ángeles. (B) Resultados del modelado numérico que muestra las distancias de todas las rutas posibles. (C) Resultados del modelado numérico que muestran cambios de fase para todas las rutas posibles. (D) Resultados del modelado numérico que representa la(s) ruta(s) más corta(s): Los Ángeles–Miami–Washington–Chicago–Las Vegas–San Francisco–Los Ángeles, y la ruta hacia atrás: Los Ángeles–San Francisco–Las Vegas–Chicago–Washington –Miami–Los Ángeles.

Sólo se amplificarán las rutas que pasan por todas las ciudades (es decir, las rutas que acumulan el cambio de fase requerido). Los resultados del modelado numérico en la Fig. 5C muestran las rutas que satisfacen la ecuación. (1). En el Paso 2, el atenuador externo introduce una amortiguación adicional. En la Fig. 5D, se muestran las rutas más cortas (es decir, #320 y #3062) que corresponden a Los Ángeles–Miami–Washington–Chicago–Las Vegas–San Francisco–Los Ángeles, y la ruta con el orden de ciudad inverso: Los Ángeles–San Francisco–Las Vegas–Chicago–Washington–Miami–Los Ángeles.

Cabe señalar que en los ejemplos presentados anteriormente, TSP se resolvió utilizando una computadora de tipo general. Todas las rutas posibles se calcularon una por una. Rutas con un cambio de fase que satisface la ecuación. (1) fueron seleccionados entonces. La ruta más corta de las rutas con la fase correcta se encontró verificando todas las rutas con la fase correcta. El uso de hardware convencional no aporta ninguna ventaja sobre los algoritmos existentes. Para acelerar la solución TSP, se necesita un dispositivo que utilice la superposición de ondas y verifique todas las rutas posibles en paralelo.

En esta parte, presentamos datos experimentales que muestran la solución TSP para cuatro ciudades. Existe una variedad de enfoques posibles para la implementación práctica del dispositivo que se muestra en la Fig. 2. Puede ser una superposición de ondas mecánicas, acústicas o electromagnéticas que se propagan a través de todas las rutas posibles en la malla. Nuestro enfoque tiene como objetivo explorar la combinación única de propiedades inherentes a las ondas de espín, donde las guías de ondas magnéticas pueden servir como desfasadores y filtros de frecuencia al mismo tiempo. La onda de espín es una oscilación colectiva de espines en una red de espín alrededor de la dirección de magnetización. Las ondas de espín aparecen en estructuras ordenadas magnéticamente y un cuanto de onda de espín se denomina “magnon”10. Los circuitos de anillo activo con líneas de retardo de onda de espín se utilizan ampliamente como fuentes de microondas sintonizables11. Las ondas de espín de radiofrecuencia se propagan en guías de ondas magnéticas mucho más lentamente que las ondas electromagnéticas en cables coaxiales. Por ejemplo, la velocidad de grupo de las ondas de espín magnetostáticas en una película monocristalina de granate de hierro ytrio Y3Fe2(FeO4)3 (YIG) de 7 µm de espesor es de aproximadamente 104 m/s12. Permite obtener grandes desplazamientos de fase (por ejemplo, hasta 2pi) para la señal que se propaga en guías de ondas de longitud milimétrica. Al mismo tiempo, la dispersión de las ondas de espín depende en gran medida de la magnetización de la guía de ondas. Las ondas de espín que se propagan a lo largo de la dirección de magnetización (las llamadas ondas de espín magnetostáticas de volumen hacia atrás (BVMSW) y las ondas de espín que se propagan perpendicularmente a la dirección de magnetización (las llamadas ondas de espín magnetostáticas de superficie MSSW) poseen una dispersión diferente13. y la ventana de frecuencia para la propagación de la onda de espín puede controlarse mediante el campo magnético aplicado localmente. Puede ser simplemente un imán de microescala colocado en la parte superior de la guía de ondas YIG. El primer experimento de prueba de concepto sobre retransmisión de señales La dirección en el dispositivo lógico combinatorio de dos caminos se logró utilizando un circuito de anillo activo basado en YIG con BVMSW y MSSW8.

En este trabajo, la malla se construye utilizando filtros de frecuencia basados ​​en YIG disponibles comercialmente producidos por Micro Lambda Wireless, Inc, modelo MLFD-40540. Los datos experimentales sobre la transmisión del filtro y el retardo de fase se pueden encontrar en los materiales complementarios. Los esquemas del dispositivo se muestran en la Fig. 6. En la Fig. 6A, se muestra una vista general del dispositivo similar a la de la Fig. 2. La principal diferencia está en el número de rutas que conectan la ciudad A en la izquierda y la ciudad A a la derecha. Se muestran nueve filtros de paso de banda. Las frecuencias centrales de los filtros están configuradas para transmitir tres frecuencias seleccionadas: \({f}_{1}=2.441\) GHz, \({f}_{2}=2.514\) GHz y \({f} _{3}=2,595\) GHz. Los filtros están ensamblados para proporcionar tres rutas de propagación: \({f}_{1}\) para ABCDA, \({f}_{2}\) para ACDBA y \({f}_{3}\) para ADBCA. El dispositivo tiene como objetivo encontrar la ruta más corta dependiendo del conjunto de atenuadores. En la Fig. 6B, se muestran los esquemas de conexión del dispositivo prototipo. Hay seis filtros de frecuencia de paso de banda de doble canal conectados mediante cables coaxiales. Las dos letras (por ejemplo, AB, CD, etc.) representan la ruta en la que se introduce el filtro. Por ejemplo, AB significa que el filtro se introduce en la ruta que conecta las ciudades A y B. Cada uno de los filtros introduce un cambio de fase en la señal que se propaga. Este hecho se aprovecha para minimizar el número de componentes en el circuito. Los filtros de frecuencia introducen el retardo de fase para cada ciudad. El sistema fue calibrado para que las señales que se propagan por las tres rutas acumulen los mismos cambios de fase. La amplificación en la parte eléctrica es proporcionada por tres amplificadores (Mini-Circuitos, modelo ZX60-83LN-S+) conectados en serie. La amplificación total es de unos 15 dB en todos los experimentos. Hay un desfasador externo (ARRA, modelo 9418A) que se ajustó para proporcionar un cambio de fase de \(\pi /6\). La condición de fase (2) se cumple para las tres rutas. Los datos experimentales sobre la propagación de señales se pueden encontrar en los materiales complementarios. Hay 12 atenuadores en el circuito, donde la atenuación en dB es proporcional a la distancia entre las ciudades. El flujo de energía se detecta mediante un acoplador unidireccional (KRYTAR, modelo 1850) que se conecta a los 12 lugares seleccionados como se muestra en la Fig. 6B. Estos lugares están marcados con los números 1,2,3 y 4. Las marcas tienen diferentes colores (es decir, rojo, verde y azul) para separar las señales que se propagan en las frecuencias \({f}_{1}\), \({ f}_{2},\) y \({f}_{3}\), respectivamente. La potencia detectada en el puerto 1 corresponde a la potencia de entrada. La potencia medida en los puertos 2, 3 y 4 corresponde a la señal después de recorrer la primera, segunda y tercera ciudades, respectivamente. Además, los espectros de frecuencia de la oscilación automática en el circuito de anillo activo se pueden medir utilizando el analizador de espectro y el PNA como se muestra en la Fig. 6B. Los espectros se pueden encontrar en los materiales complementarios.

(A) Vista general del dispositivo prototipo para TSP con cuatro ciudades. Hay 12 filtros de paso de banda de frecuencia única incluidos en el esquema. Las frecuencias centrales de los filtros están configuradas para transmitir tres frecuencias seleccionadas: \({f}_{1}=2.441\) GHz, \({f}_{2}=2.514\) GHz y \({f} _{3}=2,595\) GHz. Los filtros están ensamblados para proporcionar tres rutas de propagación: \({f}_{1}\) para ABCDA, \({f}_{2}\) para ACDBA y \({f}_{3}\) para ADBCA. (B) Esquemas de conexión del dispositivo prototipo. El retardo de fase para cada ciudad lo introducen los filtros de frecuencia. El sistema fue calibrado para que las señales que se propagan por las tres rutas acumulen los mismos cambios de fase. Hay 12 atenuadores en el circuito, donde la atenuación en dB es proporcional a la distancia entre las ciudades. El flujo de energía se detecta mediante un acoplador unidireccional (modelo) que está conectado a los 12 lugares seleccionados marcados con los números 1,2,3 y 4. Las marcas tienen diferentes colores (es decir, rojo, verde y azul) para separar las señales. propagándose en las frecuencias \({f}_{1}\), \({f}_{2},\) y \({f}_{3}\), respectivamente.

En los siguientes tres ejemplos, presentamos datos experimentales que demuestran la búsqueda de la ruta más corta dependiendo del conjunto de atenuadores para diferentes rutas. Cabe señalar que durante los experimentos no se cambian las frecuencias de paso de banda, ni la conectividad ni la posición del desfasador externo.

Experimento 1: En la Fig. 7A, se muestran los valores de los atenuadores para diferentes caminos. Estos valores se eligen aleatoriamente en función de los componentes disponibles. Tan pronto como se conectan las partes magnética y eléctrica, el dispositivo comienza a buscar el camino resonante. Se necesitan menos de 100 \(\mu s\) para llegar al régimen estable de autooscilaciones. En la Fig. 7B, se muestran datos experimentales sobre el flujo de potencia en el circuito. Existe aproximadamente la misma potencia de entrada para las tres rutas posibles. La mayor parte de la energía fluye por la ruta ACDBA. Hay más de 30 dBm de diferencia con las otras dos rutas (es decir, ABCDA y ADBCA), que no están en resonancia con la parte eléctrica. La ruta de propagación se ilustra en la Fig. 7C. Todas las mediciones se realizan a temperatura ambiente.

(A) Atenuación de nodo a nodo. (B) Datos experimentales sobre el flujo de potencia en la malla. (C) La ruta más corta ACDBA está representada por los sensores de potencia.

Experimento 2: A continuación, se cambió el conjunto de atenuadores. En la Fig. 8A se muestran los valores de los atenuadores para diferentes caminos. En la Fig. 8B, se muestran datos experimentales sobre el flujo de potencia en el circuito. Existe aproximadamente la misma potencia de entrada para las tres rutas posibles. La mayor parte de la energía fluye a través de la ruta ADBCA. Como en el ejemplo anterior, hay más de 30 dBm de diferencia con las otras dos rutas (es decir, ABCDA y ACDBA). La ruta de propagación se ilustra en la Fig. 8C.

(A) Atenuación de nodo a nodo para el ejemplo 2. (B) Datos experimentales sobre el flujo de potencia en la malla. (C) La ruta más corta ADBCA está representada por los sensores de potencia.

Experimento 3: En la Fig. 9A, se muestra un conjunto diferente de valores de atenuación para diferentes caminos. En la Fig. 9B, se muestran datos experimentales sobre el flujo de potencia en el circuito. La mayor parte de la energía fluye por la ruta ABCDA. Como en el ejemplo anterior, hay más de 30 dBm de diferencia con las otras dos rutas (es decir, ABCDA y ACDBA). La ruta de propagación se ilustra en la Fig. 9C. Hay un número infinito de conjuntos de atenuadores que imitan la distancia de viaje entre las cuatro ciudades. En todos los casos, el dispositivo encontrará la ruta más corta a través de todas las ciudades.

(A) Atenuación de nodo a nodo para el ejemplo 2. (B) Datos experimentales sobre el flujo de potencia en la malla. (C) La ruta más corta ABCDA está representada por los sensores de potencia.

Hay varias observaciones que nos gustaría hacer en base a los datos experimentales obtenidos. El prototipo de dispositivo combinatorio magnónico muestra la ruta más corta de propagación a través de los sitios seleccionados en la malla hecha de filtros de frecuencia, desfasadores y atenuadores. Es de vital importancia que el cambio en la ruta de propagación de la señal demostrado en los ejemplos se deba únicamente al cambio en la atenuación de la ruta. Por lo tanto, el dispositivo se puede utilizar para todas las combinaciones posibles de atenuación de trayectoria (distancias) entre los nodos (ciudades).

Existe una diferencia importante en el flujo de energía a través de las diferentes rutas que supera los 30 dBm a temperatura ambiente. El dispositivo de circuito en anillo activo amplifica selectivamente sólo las rutas que satisfacen las condiciones resonantes (1) y (2). La condición de fase (2) nos permite extraer las rutas con cambio de fase acumulado deseado. La condición de amplitud (1) permite seleccionar sólo la ruta más corta entre muchas con la misma fase acumulada. Se necesita un paso especial en el modelado numérico para extraer la ruta más corta aumentando la atenuación externa \(R\). La extracción de la ruta más corta ocurre naturalmente en el dispositivo prototipo debido a fenómenos no lineales. Este efecto se conoce como supresión de modo14,15 y se observa en resonadores mecánicos, acústicos y ópticos. Explica la redistribución de energía entre los modos, donde el modo con atenuación mínima recibe la mayor parte de la amplificación. Es un caso raro en el que el prototipo experimental funciona de manera más eficiente que el dispositivo teórico de modelado numérico.

Cabe señalar la diferencia entre el dispositivo de tipo general que se muestra en la Fig. 2 y el prototipo que se muestra en la Fig. 4. Se supone que todas las rutas que conectan la ciudad A de la izquierda y la ciudad A de la derecha están disponibles en el Dispositivo de tipo general. Como se mencionó anteriormente, existen rutas “parásitas” como ABA, ACBA que no pasan por todas las ciudades. Las rutas "correctas" se seleccionan utilizando el desfasador externo. El dispositivo que se muestra en la Fig. 2 se puede utilizar para encontrar cualquier ruta (por ejemplo, ABA, ACDA) ajustando el desfasador externo. Por el contrario, sólo hay tres rutas (es decir, ABCDA, ABDCA y ACBDA) en el dispositivo que se muestra en la Fig. 4. También es posible incluir rutas "parásitas" en el costo de los filtros de frecuencia adicionales. Por ejemplo, sería necesario incluir dos filtros de frecuencia adicionales sintonizados a la frecuencia central \({f}_{4}\) para tener la ruta ABA.

Existe una variedad de enfoques para la implementación práctica de dispositivos combinatorios. El enfoque magnónico tiene ciertas ventajas (por ejemplo, un cambio de fase prominente para la señal de RF en guías de onda de escala micrométrica) y desventajas (por ejemplo, una amortiguación de onda de espín prominente). Puede ser posible construir dispositivos combinatorios ópticos con baja amortiguación y rápida propagación de la señal si se puede lograr el destacado retraso de fase. La capacidad de explotar la superposición de ondas clásica proporciona una ventaja fundamental sobre las computadoras digitales convencionales en cuanto a rendimiento funcional. El rendimiento funcional es una métrica comúnmente aceptada para la evaluación de dispositivos lógicos16, que se puede definir de la siguiente manera:

Los dispositivos lógicos convencionales basados ​​en la tecnología de semiconductores complementarios de óxido metálico (CMOS) poseen un tamaño característico submicrométrico profundo (p. ej., longitud de canal de 7 nm) y realizan una operación en un tiempo muy corto (p. ej., una fracción de nanosegundo)17. Sin embargo, estos dispositivos de tipo booleano sólo pueden realizar una operación a la vez. Por el contrario, los dispositivos de lógica combinatoria son eficientes en la búsqueda paralela. Esta búsqueda a través de múltiples rutas equivale al número de operaciones posteriores del ordenador digital. El número de rutas posibles en TSP escala proporcionalmente a \(\left(n-1\right)!/2.\) El tiempo de cálculo escala proporcionalmente a \(n\cdot l/{v}_{g},\ ) donde \(l\) es la longitud de la guía de ondas que conecta los nodos en la malla, \({v}_{g}\) es la velocidad de grupo de la señal. El área de la malla escala proporcionalmente a \(\sqrt{n}\cdot {l}^{2}\). El rendimiento funcional de los dispositivos combinatorios para TSP se puede estimar de la siguiente manera:

Tomando la longitud de la guía de ondas como 10 mm y la velocidad del grupo como \({10}^{4}\) m/s, el rendimiento funcional se está disparando a \({10}^{35}\) Ops/ s∙m2 que está por encima de los límites de las supercomputadoras existentes combinadas.

Sorprendentemente, existe mucha similitud en la resolución de diferentes problemas, como los puentes de Königsberg, TSP y la factorización prima. El uso de números primos para marcar nodos de malla únicos (es decir, ciudades en TSP) parece muy eficiente y garantiza la unicidad de la fase acumulada a través de las diferentes rutas. A su vez, se puede utilizar el mismo dispositivo para la factorización prima. El desfasador externo se puede configurar en \(\Psi =2\pi -\pi Log(X)\), donde \(X\) es el número que se va a factorizar. El dispositivo encontrará una ruta en la que la fase acumulada coincida con la fase externa. Los ejemplos de factorización prima con el dispositivo de lógica combinatoria se presentan en el trabajo anterior8. En el futuro, puede ser posible construir un dispositivo combinatorio universal capaz de resolver una variedad de problemas NP-difíciles y NP.

La cuestión práctica clave está relacionada con la cantidad de piezas (es decir, guías de ondas, filtros de frecuencia, atenuadores, detectores de potencia) para construir un dispositivo para TSP con una gran cantidad de ciudades. En la Tabla 1, se muestran las estimaciones para el número de piezas para TSP con \(n\) ciudades. El número de desfasadores para las ciudades aumenta como \(n+1\). Se necesita un desfasador adicional para la segunda ciudad A. El número de guías de onda que conectan los desfasadores está dado por

donde el primer término de la derecha representa el número de rutas en el TSP clásico como se muestra en la Fig. 2. El segundo término de la derecha representa las guías de onda \(\left(n-1\right)\) adicionales para el segunda ciudad A. Hay la misma cantidad de atenuadores y detectores de potencia necesarios para TSP con \(n\) ciudades. Una situación más complicada es la de los filtros de frecuencia. Hay 12 filtros de paso de banda de frecuencia única (4 filtros para 3 rutas) que se muestran en la Fig. 6A. En el prototipo, utilizamos cables separados y filtros de frecuencia para crear dos rutas de propagación entre algunas ciudades (por ejemplo, BC y DC). Se necesitaría una cantidad enorme de \(\left(n-1\right)!\) de filtros de paso de banda de frecuencia única para TSP con \(n\) ciudades que siguieran este enfoque. En general, una ruta \(i-ésima\) en el dispositivo combinatorio debe estar asociada con alguna frecuencia \({f}_{i}\). Esto conduce al gran desafío del enfoque presentado, ya que el número de rutas posibles aumenta factorialmente con el número de ciudades. El número de frecuencias distintas puede ser bastante grande (por ejemplo, 1 M de frecuencias en el rango de frecuencias de 0,5 a 10 GHz con una separación entre frecuencias de 0,5 MHz). Sin embargo, es suficiente para resolver TSP con sólo 6 a 7 ciudades. En parte, este problema se puede resolver utilizando la misma frecuencia para las rutas que no se cruzan. El problema se puede resolver completamente utilizando filtros combinatorios que transmitan señales que comprenden ondas con una determinada combinación de frecuencias (por ejemplo, \({\{f}_{1}\), \({f}_{2},\) \ ({f}_{5}\), \({f}_{11}\}\) o \({\{f}_{2}\), \({f}_{4},\ ) \({f}_{7}\), \({f}_{19}\},\) etc.). En este escenario, la cantidad de filtros es la misma que la cantidad de guías de onda dada por la ecuación. (8), donde cada filtro tiene una combinación única de frecuencias de paso de banda. En todos los casos, sólo hay un amplificador de banda ancha externo, un desfasador externo sintonizable y un atenuador externo sintonizable.

Cabe señalar que cada nuevo problema requiere un ajuste o reconfiguración del circuito. Por ejemplo, el circuito para cuatro ciudades presentado en este trabajo se puede utilizar para cualquier otro TSP con cuatro ciudades. Es necesario ajustar la atenuación según las distancias entre las ciudades. Se puede hacer utilizando atenuadores sintonizables por voltaje. El aumento en el número de ciudades requiere un aumento en el número de desfasadores en el circuito. Sin embargo, los circuitos TSP se pueden utilizar para un número menor de ciudades sin quitar o agregar nuevos componentes. Por ejemplo, un TSP con ocho ciudades se puede utilizar para resolver problemas de ocho, siete, seis, cinco y cuatro ciudades.

Otro desafío práctico está asociado con la precisión de las piezas con respecto al número de ciudades. La diferencia en las distancias entre las ciudades puede disminuir significativamente para los TSP con un gran número de ciudades. Existen límites físicos para la precisión del control del atenuador. Además, el aumento de posibles rutas de propagación inevitablemente disminuye la diferencia en la fase acumulada para diferentes rutas. A su vez, esto conducirá al problema de encontrar la ruta más corta para un gran número de ciudades. El aumento de la precisión de las mediciones/cálculos es un problema común para TSP con un gran número de ciudades que puede abordarse con algoritmos heurísticos18. Se requiere menos precisión para los detectores de potencia. Se puede lograr una diferencia importante en el flujo de energía (por ejemplo, una diferencia de 20 dB entre las rutas activa y pasiva) independientemente del número de ciudades. Existen ciertas ventajas y desventajas de utilizar circuitos magnónicos para TSP. Por un lado, las ondas de espín producen cambios de fase prominentes en guías de ondas de longitud milimétrica. Por otro lado, la dispersión de las ondas de espín complica considerablemente la ingeniería de circuitos. Además, las ondas de espín poseen una interacción mucho más fuerte en comparación con las ondas ópticas. Por ejemplo, las ondas de espín que se propagan en direcciones ortogonales a través de la unión pueden reflejarse completamente entre sí19. Esto constituye un problema adicional para las interconexiones de ondas de espín. Ésta y muchas otras cuestiones merecen una consideración especial.

Describimos un enfoque para la solución TSP utilizando dispositivos combinatorios. El principio de funcionamiento se basa en la clásica superposición de ondas, donde cada onda corresponde a un viajante de comercio. Las ondas se propagan a través de una malla de guías de ondas, donde los desfasadores representan las ciudades en TSP y la distancia entre las ciudades está codificada en la atenuación de la señal. Sólo se amplifican las ondas que atraviesan las ciudades seleccionadas y acumulan el cambio de fase específico. La más amplificada es la onda que recorre el recorrido con mínima atenuación. La solución TSP se ilustra mediante modelos numéricos y se demuestra experimentalmente. El primer prototipo es un circuito de anillo activo magnónico de trayectorias múltiples que comprende desfasadores magnéticos, filtros de frecuencia y atenuadores. La ruta de propagación de la señal se detecta a través del detector de potencia. Te presentamos ejemplos para tres conjuntos diferentes de atenuadores/distancias de ciudad a ciudad. El dispositivo encuentra literalmente la ruta de propagación más corta a través de las ciudades. El funcionamiento es robusto ya que la diferencia de potencia entre las rutas activa y pasiva supera los 30 dBm. Todos los experimentos se realizan a temperatura ambiente. Este trabajo es un paso hacia dispositivos de lógica combinatoria para el procesamiento de datos de tareas especiales. Potencialmente, los dispositivos combinatorios pueden proporcionar una ventaja fundamental en el rendimiento funcional en comparación con los dispositivos digitales convencionales. La capacidad de utilizar la superposición clásica de ondas es la ventaja clave y la propiedad más atractiva del enfoque presentado.

Todos los datos generados o analizados durante este estudio se incluyen en este artículo publicado.

Biggs, N., Lloyd, EK y Wilson, RJ Teoría de grafos, 1736-1936. Isis 70, 164-165. https://doi.org/10.1086/352170 (1979).

Artículo MATEMÁTICAS Google Scholar

Ungureanu, V. Problema del vendedor ambulante con el transporte. Computadora. Ciencia. J. Molde. 14, 202–206 (2006).

MATEMÁTICAS Google Scholar

Fuentes, GEA, Gress, ESH, Mora, J. & Marin, JM Solución del problema de programación de talleres a través del problema del viajante. Rev. Iberoam. Automático. Informar. Indiana 13, 430–437. https://doi.org/10.1016/j.riai.2016.07.003 (2016).

Artículo de Google Scholar

Gusfield, D. y Gusfield, D. Problemas del vendedor ambulante en genómica (Cambridge Univ Press, 2019).

Libro MATEMÁTICAS Google Scholar

Aarts, EHL & Korst, JHM Máquinas Boltzmann para problemas de viajante de comercio. EUR. J. Ópera. Res. 39, 79–95. https://doi.org/10.1016/0377-2217(89)90355-x (1989).

Artículo MATEMÁTICAS Google Scholar

Collings, N., Sumi, R., Weible, KJ, Acklin, B. & Xue, W. En Reunión temática internacional sobre informática óptica (Oc 92). 637–641 (Ingeniería óptica Spie-Int Soc, 1993).

Saud, S., Kodaz, H. & Babaoglu, I. En 9ª Conferencia Internacional sobre Avances en Tecnología de la Información (IAIT). 17–32 (Conocimiento E, 2018).

Khitun, A. & Balinskiy, M. Dispositivos de lógica combinatoria basados ​​en un circuito de anillo activo de múltiples rutas. Ciencia. Representante https://doi.org/10.1038/s41598-022-13614-2 (2022).

Artículo PubMed PubMed Central Google Scholar

Tiberkevich, VS, Khymyn, RS, Tang, HX & Slavin, AN Sensibilidad a señales externas y propiedades de sincronización de un oscilador automático no isócrono con retroalimentación retardada. Ciencia. Representante https://doi.org/10.1038/srep03873 (2014).

Artículo PubMed PubMed Central Google Scholar

Kittel, C. Introducción a la Física del Estado Sólido 8ª ed. (Wiley, 2005).

MATEMÁTICAS Google Scholar

Chumak, AV, Serga, AA & Hillebrands, B. Cristales magnónicos para procesamiento de datos. J. Física. D-aplicación. Física. 50, 1–20. https://doi.org/10.1088/1361-6463/aa6a65 (2017).

Artículo CAS Google Scholar

Balinskiy, M. et al. Interferencia de ondas de espín en la unión cruzada YIG. Aip Adv. https://doi.org/10.1063/1.4974526 (2017).

Artículo de Google Scholar

Gurevich, AG y Melkov, GA Oscilaciones y ondas de magnetización 147–176 (CRC Press, 1996).

Google Académico

Okusaga, O. y col. En 2010 Simposio Internacional de Control de Frecuencia IEEE. 539–543 (IEEE, 2010).

Carroll, JM & Chang, K. Anillo-resonador de supresión del modo Microstrip. Electrón. Letón. 30, 1861–1862. https://doi.org/10.1049/el:19941291 (1994).

ADS del artículo Google Scholar

Nikonov, DE & Young, IA Metodología uniforme para realizar evaluaciones comparativas de dispositivos lógicos más allá de CMOS. En 2012 Reunión internacional de dispositivos electrónicos IEEE (IEDM 2012), vol. 25, https://doi.org/10.1109/iedm.2012.6479102 (2012).

Hoefflinger, B. En Chips 2020, vol. 2: Colección New Vistas in Nanoelectronics Frontiers (ed, Hoefflinger, B.) 143–148 (Springer, 2016).

Syambas, NR, Salsabila, S., Suranegara, GM e IEEE. En la XI Conferencia Internacional sobre Servicios y Aplicaciones de Sistemas de Telecomunicaciones (TSSA). (IEEE, 2017).

Balynskiy, M. et al. Puertas lógicas magnéticas reversibles basadas en interferencias de ondas de espín. J. Aplica. Física. https://doi.org/10.1063/1.5011772 (2018).

Artículo de Google Scholar

Descargar referencias

Este trabajo de M. Balinskiy y A. Khitun fue apoyado en parte por INTEL CORPORATION, con el premio n.º 008635, director del proyecto, Dr. DE Nikonov, y por la Fundación Nacional de Ciencias (NSF), con el premio n.º 2006290, oficial de programa, Dr. S. .Basu. Los autores desean agradecer al Dr. DE Nikonov por las valiosas discusiones.

Departamento de Ingeniería Eléctrica e Informática, Universidad de California-Riverside, Riverside, CA, 92521, EE. UU.

Mykhaylo Balinskyy y Aleksandr Khitun

También puedes buscar este autor en PubMed Google Scholar.

También puedes buscar este autor en PubMed Google Scholar.

AK tuvo la idea de los dispositivos magnónicos combinatorios para TSP y escribió el manuscrito, MB construyó el prototipo y llevó a cabo los experimentos. Todos los autores discutieron los datos y contribuyeron a la preparación del manuscrito.

Correspondencia a Aleksandr Khitun.

Los autores declaran no tener conflictos de intereses.

Springer Nature se mantiene neutral con respecto a reclamos jurisdiccionales en mapas publicados y afiliaciones institucionales.

Acceso Abierto Este artículo está bajo una Licencia Internacional Creative Commons Attribution 4.0, que permite el uso, compartir, adaptación, distribución y reproducción en cualquier medio o formato, siempre y cuando se dé el crédito apropiado al autor(es) original(es) y a la fuente. proporcione un enlace a la licencia Creative Commons e indique si se realizaron cambios. Las imágenes u otro material de terceros en este artículo están incluidos en la licencia Creative Commons del artículo, a menos que se indique lo contrario en una línea de crédito al material. Si el material no está incluido en la licencia Creative Commons del artículo y su uso previsto no está permitido por la normativa legal o excede el uso permitido, deberá obtener permiso directamente del titular de los derechos de autor. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by/4.0/.

Reimpresiones y permisos

Balinskyy, M., Khitun, A. Solución del problema del viajante de comercio utilizando un dispositivo combinatorio magnónico. Representante científico 13, 11708 (2023). https://doi.org/10.1038/s41598-023-38839-7

Descargar cita

Recibido: 17 de marzo de 2023

Aceptado: 16 de julio de 2023

Publicado: 20 de julio de 2023

DOI: https://doi.org/10.1038/s41598-023-38839-7

Cualquier persona con la que compartas el siguiente enlace podrá leer este contenido:

Lo sentimos, actualmente no hay un enlace para compartir disponible para este artículo.

Proporcionado por la iniciativa de intercambio de contenidos Springer Nature SharedIt

Al enviar un comentario, acepta cumplir con nuestros Términos y pautas de la comunidad. Si encuentra algo abusivo o que no cumple con nuestros términos o pautas, márquelo como inapropiado.