Contribuição do Instituto de Automação da Academia Chinesa de Ciências

Qubits | Conta pública QbitAI

Leva apenas 15 segundos para resolver o problema de planejamento estocástico, que é 1.440 vezes mais rápido que os métodos tradicionais!

Uma nova pesquisa do Instituto de Automação da Academia Chinesa de Ciências usou o GCN para alcançar novos avanços em tais problemas. O artigo foi selecionado para ICML 2024, a principal conferência de IA.

Isto significa que a tomada de decisões eficiente pode ser alcançada mesmo em condições incertas.

A tomada de decisão sob incerteza é um tipo importante de problema de tomada de decisão, que exige que os tomadores de decisão considerem plenamente todas as situações aleatórias e tomem a decisão mais razoável.

No campo da matemática, uma solução comumente utilizada é a programação estocástica, que inclui variáveis ​​aleatórias em modelos de programação matemática.

Entre eles, a Programação Estocástica em Dois Estágios (2SP) é um método eficaz para modelar tais problemas de tomada de decisão e é amplamente utilizado.

Esta conquista do Instituto de Automação da Academia Chinesa de Ciências, o modelo HGCN2SP (HGCN significa Hierarchical Graph Convolution Network), é exatamente a combinação do método 2SP efotoCombinado com redes convolucionais, o modelo pode ser utilizado para resolver tais problemas de forma mais eficiente.

O primeiro autor do artigo é Wu Yang, aluno de doutorado do instituto, e o pesquisador Zhang Yifan é o autor correspondente.

O que é programação estocástica em dois estágios?

A ideia básica do planejamento estocástico é converter as possíveis situações futuras do problema em vários cenários amostrais, depois otimizar cada cenário amostral e, finalmente, integrar os resultados da otimização de todos os cenários para orientar as decisões atuais.

Suas áreas de aplicação incluem gestão da cadeia de suprimentos, investimento financeiro, despacho de energia, gestão de emergências em desastres, etc.

O planejamento estocástico em duas etapas, como o nome sugere, divide o processo em duas etapas.

Especificamente, estas duas fases exigem que sejam tomadas decisões macro e micro, respectivamente, para minimizar os custos totais ou maximizar os benefícios totais.

As decisões na primeira fase são tomadas antes que a incerteza se manifeste, com o objetivo de otimizar a decisão inicial para se adaptar a uma variedade de cenários futuros possíveis.

As decisões na segunda fase são tomadas após o surgimento da incerteza e são ajustadas com base nas decisões da primeira fase e no que realmente aconteceu para otimizar o resultado global.

Através do modelo 2SP, os decisores precisam de considerar plenamente o impacto dos diferentes cenários que podem ocorrer durante o processo de tomada de decisão, melhorando assim a robustez e flexibilidade da tomada de decisão e tomando decisões mais científicas e eficientes.

Por exemplo, suponha que queiramos selecionar alguns dos 10 locais candidatos para construir armazéns para atender às necessidades de 20 áreas vizinhas.

O que precisa de ser decidido na primeira fase é qual destes 10 locais candidatos deve ser selecionado;

Na segunda etapa, a relação de distribuição entre o armazém e a região deve ser determinada. Neste momento, o número de variáveis ​​de decisão chega a 200 (ou seja, se o armazém i distribui para a região j).

△Imagem gerada por DALL·E

Matematicamente, o problema 2SP é geralmente expresso como:

Dentre eles, Q(x,ξ) representa o problema de otimização de segundo estágio dada a decisão de primeiro estágio x e o cenário ξ, e sua forma é:

Na solução real, N cenas são geralmente amostradas para calcular o valor Q correspondente para aproximar a expectativa.

Obviamente, quanto maior for N, mais credível será a aproximação. No entanto, à medida que o número de cenários aumenta, o tamanho do problema aumenta rapidamente, o que levará a um aumento significativo no tempo de solução.

Vamos usar o problema de seleção de localização de armazém para ilustrar. Para tomar melhores decisões de seleção de localização, precisamos levar em consideração fatores incertos, como demanda, clima, fluxo de pessoas, tráfego, etc., e as mudanças em cada fator correspondem a um. cenário.

Isto significa que N cenários diferentes precisam ser amplamente amostrados para simular a situação real o mais próximo possível. Neste momento, o número total de variáveis ​​de decisão no segundo estágio chegará a 200N, tornando o tempo de solução extremamente longo.

Na verdade, quando N é 500, mesmo usando o solucionador comercial mais avançado Gurobi, serão necessárias pelo menos 6 horas para tomar a decisão ideal.

Os métodos tradicionais geralmente usam amostragem aleatória ou técnicas de agrupamento para selecionar um pequeno número de cenários (como 10 ou 20) para uma solução aproximada. Embora o tempo seja reduzido, a qualidade das decisões resultantes muitas vezes não é ideal.

Com base nisso, deriva-se a ideia de design do modelo HGCN2SP - ao mesmo tempo em que reduz o número de cenas de amostragem, obtém resultados precisos o mais aproximadamente possível.

Usando redes convolucionais de grafos para resolver o problema 2SP

A equipe de pesquisa propôs o modelo HGCN2SP baseado em rede hierárquica de convolução de grafos para resolver o problema de programação estocástica em dois estágios.

Especificamente em termos de design de algoritmo, a equipe caracterizou o problema 2SP construindo um gráfico hierárquico, em que o gráfico inferior foi utilizado para representar as características de cada cena, enquanto o gráfico superior foi utilizado para representar a relação entre as cenas.

Em seguida, a rede convolucional de grafos hierárquicos (HGCN) é usada para extrair as informações de incorporação do subgráfico da cena subjacente e as informações estruturais do espaço da cena de nível superior para extrair a representação da cena.

O decodificador baseado no mecanismo de atenção é usado para selecionar cenas em ordem. Ele pode não apenas encontrar cenas representativas para simplificar o problema, mas também melhorar a seleção da base inicial ao resolver o problema pelo método simplex, otimizando a ordem do. cenas. Melhora significativamente o tempo de solução.

△ Estrutura do modelo HGCN2SP

A equipe também combinou o aprendizado por reforço (RL) para examinar de forma abrangente a qualidade da tomada de decisão e o tempo de solução para otimizar os parâmetros do modelo, melhorando significativamente a eficiência e a qualidade da resolução de problemas.

No problema de localização de armazém acima, embora o HGCN2SP tenha selecionado apenas 10 cenários, a diferença entre os resultados da sua decisão e a decisão tomada pelo solucionador Gurobi em 6 horas foi de apenas 1,7%, e o tempo de solução foi de apenas 15 segundos, o que equivale à velocidade A melhoria é de 1.440 vezes, o que reflete plenamente a eficácia deste método.

Além disso, no experimento Network Design Problem (NDP), o HGCN2SP obteve efeitos de tomada de decisão semelhantes em menos da metade do tempo dos métodos existentes.

Especialmente em instâncias de grande escala e em um grande número de cenários, o HGCN2SP ainda mantém fortes capacidades de generalização.

A proposta do HGCN2SP fornece uma nova ideia e ferramenta para resolver problemas complexos de 2SP e tem amplas perspectivas de aplicação.

A equipe de pesquisa planeja otimizar ainda mais o modelo, reduzir custos de treinamento e explorar sua aplicação em problemas mais práticos.

Endereço do papel:
https://openreview.net/forum?id=8onaVSFTEj