• 2 min de lectura
Nuevo solucionador aborda problemas de optimización con 10,000 variables
Cristian Cassella, de Northeastern, dice que su Analog Floquet Solver evitó trampas comunes de optimización, manejando problemas QUBO con hasta 10,000 variables.
Imagen: TechXplore
Los problemas de optimización a menudo se reducen a una enorme cantidad de decisiones simples de sí o no. En computación, a esa clase de problema se le conoce como optimización binaria cuadrática sin restricciones, o QUBO: un marco usado para buscar la mejor combinación de decisiones binarias mientras se minimiza el costo o el uso de energía.
Como dijo Cristian Cassella, profesor de ingeniería eléctrica y de computación en la Northeastern University, los problemas QUBO “son de importancia fundamental en muchas disciplinas, desde el descubrimiento de fármacos hasta la logística, así como las comunicaciones inalámbricas.”
Un aumento de la demanda de viajes compartidos durante la temporada del Mundial es un ejemplo. Con aproximadamente 10,000 conductores activos en una ciudad, cerca de la mitad disponibles, el sistema tiene que ponderar emparejamientos conductor-pasajero, rutas, tráfico, retrasos y ausencias. Formulaciones QUBO similares también aparecen en el plegamiento de proteínas, donde los investigadores modelan muchas decisiones estructurales para predecir formas tridimensionales estables.
Recomendado
Los ratones de 8.000 Hz suenan rápidos — la mayoría de jugadores aún no los necesita
El desafío es la escala. Alejandro Montanez, del Centro de Supercomputación Jülich en Jülich, Alemania, dijo que el número de combinaciones posibles crece tan rápido que muchos problemas del mundo real con 10 o más opciones se vuelven extremadamente difíciles de resolver directamente.
Un enfoque común utiliza máquinas de Ising, que convierten problemas QUBO en modelos basados en estados de espín electrónico en materiales como el hierro. Pero estos sistemas pueden quedar atrapados en un mínimo local: una respuesta aceptable que no es la mejor disponible.
Cassella y su equipo dicen que construyeron una alternativa, el Analog Floquet Solver, para ayudar a los sistemas a escapar de esas trampas. Basándose en la teoría de Floquet, que describe sistemas bajo forzamiento periódico, el método añade energía de una manera que permite al solucionador seguir “saltando” en lugar de asentarse demasiado pronto.
«Hemos encontrado una forma de proporcionar cierto grado de energía al sistema que permite que la máquina, a medida que desciende, siga 'saltando'.»
Según Cassella, el enfoque resolvió algunos problemas que antes no se habían resuelto a velocidad récord, produjo respuestas precisas para ecuaciones con hasta 10,000 variables y ofreció una mejora de nueve órdenes de magnitud en términos de consumo de energía.
El trabajo, republicado por Northeastern Global News, apunta a aplicaciones en economía, finanzas, descubrimiento de fármacos, biología, ingeniería y comunicaciones inalámbricas.
«En todas y cada una de las áreas hay problemas que actualmente son irresolubles.»
Computing Editor
Tomas lives in the terminal. He covers chips, laptops, and operating systems with a focus on performance and efficiency. He reads kernel changelogs the way other people read fiction, and he's always on the hunt for the perfect mechanical keyboard switch. If it processes data, Tomas has an opinion on it.
vía TechXplore
