Contribuido por Instituto de Automatización, Academia de Ciencias de China

Qubits | Cuenta pública QbitAI

¡Solo toma 15 segundos resolver el problema de planificación estocástica, que es 1440 veces más rápido que los métodos tradicionales!

Una nueva investigación del Instituto de Automatización de la Academia de Ciencias de China ha utilizado GCN para lograr nuevos avances en tales problemas. El artículo ha sido seleccionado para ICML 2024, la principal conferencia de IA.

Esto significa que se puede lograr una toma de decisiones eficiente incluso en condiciones de incertidumbre.

La toma de decisiones en condiciones de incertidumbre es un tipo importante de problema de toma de decisiones, que requiere que quienes toman las decisiones consideren plenamente todas las situaciones aleatorias y tomen la decisión más razonable.

En el campo de las matemáticas, una solución comúnmente utilizada es la programación estocástica, que incluye variables aleatorias en los modelos de programación matemática.

Entre ellos, la programación estocástica de dos etapas (2SP) es un método eficaz para modelar este tipo de problemas de toma de decisiones y se utiliza ampliamente.

Este logro del Instituto de Automatización de la Academia de Ciencias de China, el modelo HGCN2SP (HGCN significa Hierarchical Graph Convolution Network), es exactamente la combinación del método 2SP yimagenCombinado con redes convolucionales, el modelo se puede utilizar para resolver este tipo de problemas de manera más eficiente.

El primer autor del artículo es Wu Yang, estudiante de doctorado del instituto, y el investigador Zhang Yifan es el autor correspondiente.

¿Qué es la programación estocástica de dos etapas?

La idea básica de la planificación estocástica es convertir las posibles situaciones futuras del problema en varios escenarios de muestra, luego optimizar cada escenario de muestra y finalmente integrar los resultados de optimización de todos los escenarios para guiar las decisiones actuales.

Sus áreas de aplicación incluyen gestión de la cadena de suministro, inversión financiera, despacho de energía, gestión de emergencias ante desastres, etc.

La planificación estocástica de dos etapas, como su nombre indica, divide el proceso en dos etapas.

Específicamente, estas dos etapas requieren que se tomen decisiones macro y micro respectivamente para minimizar los costos totales o maximizar los beneficios totales.

Las decisiones en la primera etapa se toman antes de que se manifieste la incertidumbre, con el objetivo de optimizar la decisión inicial para adaptarse a una variedad de posibles escenarios futuros.

Las decisiones en la segunda etapa se toman después de que surge la incertidumbre y se ajustan en función de las decisiones de la primera etapa y de lo que realmente sucedió para optimizar el resultado general.

A través del modelo 2SP, los tomadores de decisiones deben considerar plenamente el impacto de los diferentes escenarios que pueden ocurrir durante el proceso de toma de decisiones, mejorando así la solidez y flexibilidad de la toma de decisiones y tomando decisiones más científicas y eficientes.

Por ejemplo, supongamos que queremos seleccionar algunas de las 10 ubicaciones candidatas para construir almacenes que satisfagan las necesidades de 20 áreas circundantes.

Lo que hay que decidir en la primera etapa es cuál de estos 10 lugares candidatos debe seleccionarse;

En la segunda etapa, se debe determinar la relación de distribución entre el almacén y la región. En este momento, el número de variables de decisión es hasta 200 (es decir, si el almacén i se distribuye en la región j).

△Imagen generada por DALL·E

Matemáticamente, el problema 2SP suele expresarse como:

Entre ellos, Q (x, ξ) representa el problema de optimización de la segunda etapa dada la decisión x de la primera etapa y el escenario ξ, y su forma es:

En la solución real, generalmente se muestrean N escenas para calcular el valor Q correspondiente para aproximarse a la expectativa.

Obviamente, cuanto mayor es N, más creíble es la aproximación. Sin embargo, a medida que aumenta el número de escenarios, el tamaño del problema se expande rápidamente, lo que conducirá a un aumento significativo en el tiempo de solución.

Usemos el problema de la selección de la ubicación del almacén para ilustrar. Para tomar mejores decisiones de selección de ubicación, debemos tener en cuenta factores inciertos como la demanda, el clima, el flujo de personas, el tráfico, etc., y los cambios en cada factor corresponden a un. escenario.

Esto significa que es necesario muestrear ampliamente N escenarios diferentes para simular la situación real lo más fielmente posible. En este momento, el número total de variables de decisión en la segunda etapa llegará a 200N, lo que hará que el tiempo de solución sea extremadamente largo.

De hecho, cuando N es 500, incluso utilizando el solucionador comercial más avanzado, Gurobi, se necesitarán al menos 6 horas para tomar la decisión óptima.

Los métodos tradicionales suelen utilizar técnicas de muestreo aleatorio o de agrupamiento para seleccionar un pequeño número de escenarios (como 10 o 20) para una solución aproximada. Aunque el tiempo se reduce, la calidad de las decisiones resultantes a menudo no es la ideal.

A partir de esto, se deriva la idea de diseño del modelo HGCN2SP: mientras se reduce el número de escenas de muestreo, se obtienen resultados precisos de la forma más aproximada posible.

Uso de redes convolucionales gráficas para resolver el problema 2SP

El equipo de investigación propuso el modelo HGCN2SP basado en una red de convolución de gráficos jerárquicos para resolver el problema de programación estocástica de dos etapas.

Específicamente en términos de diseño de algoritmos, el equipo caracterizó el problema 2SP mediante la construcción de un gráfico jerárquico, en el que el gráfico inferior se usó para representar las características de cada escena, mientras que el gráfico superior se usó para representar la relación entre escenas.

Luego, se utiliza la red convolucional de gráficos jerárquicos (HGCN) para extraer la información de incrustación del subgrafo de escena subyacente y la información estructural del espacio de escena de nivel superior para extraer la representación de la escena.

El decodificador basado en el mecanismo de atención se utiliza para seleccionar escenas en orden. No solo puede encontrar escenas representativas para simplificar el problema, sino que también puede mejorar la selección de la base inicial al resolver el problema mediante el método simplex optimizando el orden. escenas. Mejora significativamente el tiempo de solución.

△Marco del modelo HGCN2SP

El equipo también combinó el aprendizaje por refuerzo (RL) para examinar exhaustivamente la calidad de la toma de decisiones y el tiempo de solución para optimizar los parámetros del modelo, mejorando significativamente la eficiencia y la calidad de la resolución de problemas.

En el problema de ubicación del almacén anterior, aunque HGCN2SP solo seleccionó 10 escenarios, la diferencia entre los resultados de su decisión y la decisión tomada por el solucionador Gurobi en 6 horas fue solo del 1,7% y el tiempo de solución fue de solo 15 segundos, lo que equivale a la velocidad. La mejora es de 1440 veces, lo que refleja plenamente la eficacia de este método.

Además, en el experimento del Problema de Diseño de Red (NDP), HGCN2SP logró efectos de toma de decisiones similares en menos de la mitad del tiempo que los métodos existentes.

Especialmente en instancias a gran escala y una gran cantidad de escenarios, HGCN2SP aún mantiene fuertes capacidades de generalización.

La propuesta de HGCN2SP proporciona una nueva idea y herramienta para resolver problemas complejos de 2SP y tiene amplias perspectivas de aplicación.

El equipo de investigación planea optimizar aún más el modelo, reducir los costos de capacitación y explorar su aplicación en problemas más prácticos.

Dirección del papel:
https://openreview.net/forum?id=8onaVSFTEj