Clicky

Innovador algoritmo de Toshiba ofrece la optimización combinatoria más rápida y de mayor escala del mundo

algoritmo Toshiba

El algoritmo de bifurcación simulada puede acelerar fácilmente la resolución de problemas

Toshiba Corporation ha logrado un gran avance en la optimización combinatoria, la selección de las mejores soluciones de entre una enorme cantidad de patrones combinatorios, con el desarrollo de un algoritmo que ofrece el rendimiento más rápido y de mayor escala del mundo, y una mejora de aproximadamente 10 veces sobre los métodos actuales.

El nuevo método de Toshiba se puede aplicar a tareas tan difíciles pero esenciales como la identificación de rutas de reparto eficientes, la determinación de las estructuras moleculares más efectivas para investigar el desarrollo de nuevos fármacos y la creación de carteras rentables de productos financieros.

 

La técnica recientemente desarrollada, el algoritmo de bifurcación simulada, obtiene rápidamente soluciones aproximadas altamente precisas (buenas soluciones) para problemas complejos de optimización combinatoria a gran escala, problemas que han resistido la solución durante mucho tiempo y que son muy difíciles de resolver utilizando técnicas convencionales.

Potencialmente aún más importante, el algoritmo también ofrece una excelente escalabilidad a bajo costo al usar las computadoras existentes, lo que podría revolucionar los actuales procesos de optimización.

Toshiba utilizará el algoritmo de bifurcación simulada para construir una plataforma de servicio capaz de resolver rápidamente diversos problemas sociales y empresariales, con el objetivo de su comercialización en 2019.

Muchos problemas solo pueden resolverse seleccionando una gran cantidad de opciones para encontrar las mejores combinaciones. Estos incluyen realizar una logística eficiente (el problema del vendedor ambulante en matemáticas), dirigir el tráfico para aliviar la congestión, aplicar el diseño molecular al desarrollo de medicamentos y optimizar las carteras financieras. Hoy en día, realizar tal optimización combinatoria requiere una enorme cantidad de cómputo, y sigue siendo difícil usar las computadoras actuales para encontrar soluciones.

El movimiento de 2.000 partículas como la Máquina de Bifurcación Simulada resuelve un problema de optimización con 2.000 variables completamente conectadas

1: Cambio temporal de la posición de la partícula x


2: Movimiento de partículas en el espacio de fase.(superficie plana xy)

Hay crecientes expectativas de que los dispositivos de computación de la próxima generación, como las computadoras cuánticas, liderarán el camino hacia mejores soluciones, y la investigación actual apunta a desarrollar computadoras especialmente diseñadas para la optimización combinatoria mediante el uso de circuitos superconductores, láseres y computadores digitales basados en semiconductores. A pesar de estos esfuerzos, sigue siendo un desafío aumentar el tamaño del problema solucionable y reducir el tiempo de cálculo.

Por ejemplo, todavía es difícil para las computadoras cuánticas con circuitos superconductores resolver problemas complejos a gran escala. Y mientras que las computadoras digitales basadas en semiconductores de hoy en día facilitan el aumento del tamaño del problema solucionable, los algoritmos actuales para la optimización combinatoria son difíciles de paralelizar, lo que dificulta el uso de la computación en paralelo para acelerar la resolución de problemas.

Toshiba ha resuelto estos problemas al desarrollar un nuevo algoritmo de optimización combinatoria, el algoritmo de bifurcación simulada. Es altamente paralelizable y, por lo tanto, puede acelerar fácilmente la resolución de problemas en una computadora digital estándar a través de cómputo paralelo. Como los sistemas de cómputo a gran escala actuales se pueden usar como están, no hay necesidad de instalar nuevos equipos, lo que facilita la ampliación a un bajo costo.

Por ejemplo, al usar arreglos de puertas programables en campo (FPGA), se puede obtener una buena solución a un problema de optimización con 2.000 variables totalmente conectadas (aproximadamente 2 millones de conexiones) en solo 0.5 milisegundos. Esto es aproximadamente 10 veces más rápido que la computadora cuántica basada en láser reconocida como la más rápida del mundo puede resolver el mismo problema.

algoritmo de bifurcación simulada, gráfico 1

Además, al usar un grupo de ocho GPU, Toshiba obtuvo una buena solución para un problema a gran escala que involucra 100.000 variables totalmente conectadas (aproximadamente 5 mil millones de conexiones) en solo unos segundos. Estos resultados abren nuevas formas de resolver problemas de optimización combinatoria a gran escala en diferentes áreas de aplicación.

algoritmo de bifurcación simulada, gráfico 2

El algoritmo de bifurcación simulada aprovecha los fenómenos de bifurcación, los procesos adiabáticos y los procesos ergódicos en la mecánica clásica para encontrar rápidamente soluciones altamente precisas.

Toshiba derivó el principio de una teoría de una computadora cuántica propuesta por la propia compañía. Este descubrimiento en la mecánica clásica inspirada en la mecánica cuántica es un resultado académicamente interesante y altamente novedoso que sugiere la existencia de teoremas matemáticos desconocidos.

Durante este año Toshiba pretende utilizar este avance tecnológico clave para realizar y comercializar una plataforma de servicios que satisfaga todas las necesidades de optimización en logística, finanzas y otras áreas de la sociedad moderna.

Los detalles de la nueva tecnología se publican en la revista académica en línea Science Advances: Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems

Jesus_Caceres