Contribution de l'Institut d'automatisation de l'Académie chinoise des sciences

Qubits | Compte public QbitAI

Il ne faut que 15 secondes pour résoudre le problème de planification stochastique, ce qui est 1440 fois plus rapide que les méthodes traditionnelles !

Une nouvelle recherche de l'Institut d'automatisation de l'Académie chinoise des sciences a utilisé GCN pour réaliser de nouvelles avancées dans ces problèmes. L'article a été sélectionné pour l'ICML 2024, la principale conférence sur l'IA.

Cela signifie qu’une prise de décision efficace peut être obtenue même dans des conditions incertaines.

La prise de décision dans l'incertitude est un type important de problème de prise de décision, qui oblige les décideurs à prendre pleinement en compte toutes les situations aléatoires et à prendre la décision la plus raisonnable.

Dans le domaine des mathématiques, une solution couramment utilisée est la programmation stochastique, qui inclut des variables aléatoires dans les modèles de programmation mathématique.

Parmi eux, la programmation stochastique en deux étapes (2SP) est une méthode efficace pour modéliser de tels problèmes de prise de décision et est largement utilisée.

Cette réalisation de l'Institut d'automatisation de l'Académie chinoise des sciences, le modèle HGCN2SP (HGCN signifie Hierarchical Graph Convolution Network), est exactement la combinaison de la méthode 2SP etimageCombiné avec des réseaux convolutifs, le modèle peut être utilisé pour résoudre ces problèmes plus efficacement.

Le premier auteur de l'article est Wu Yang, doctorant à l'institut, et le chercheur Zhang Yifan est l'auteur correspondant.

Qu’est-ce que la programmation stochastique en deux étapes ?

L'idée de base de la planification stochastique est de convertir les situations futures possibles du problème en plusieurs exemples de scénarios, puis d'optimiser chaque exemple de scénario et enfin d'intégrer les résultats d'optimisation de tous les scénarios pour guider les décisions actuelles.

Ses domaines d'application comprennent la gestion de la chaîne d'approvisionnement, les investissements financiers, la répartition de l'énergie, la gestion des urgences en cas de catastrophe, etc.

La planification stochastique en deux étapes, comme son nom l'indique, divise le processus en deux étapes.

Plus précisément, ces deux étapes nécessitent de prendre respectivement des décisions macro et micro pour minimiser les coûts totaux ou maximiser les bénéfices totaux.

Les décisions de la première étape sont prises avant que l’incertitude ne se manifeste, dans le but d’optimiser la décision initiale pour l’adapter à une variété de scénarios futurs possibles.

Les décisions de la deuxième étape sont prises après l'émergence de l'incertitude et sont ajustées en fonction des décisions de la première étape et de ce qui s'est réellement passé pour optimiser le résultat global.

Grâce au modèle 2SP, les décideurs doivent pleinement prendre en compte l'impact des différents scénarios pouvant se produire au cours du processus de prise de décision, améliorant ainsi la robustesse et la flexibilité de la prise de décision et prenant des décisions plus scientifiques et efficaces.

Par exemple, supposons que nous souhaitions sélectionner certains des 10 emplacements candidats pour construire des entrepôts afin de répondre aux besoins de 20 zones environnantes.

Ce qu'il faut décider dans un premier temps est lequel de ces 10 sites candidats doit être sélectionné ;

Dans la deuxième étape, la relation de distribution entre l'entrepôt et la région doit être déterminée. À ce stade, le nombre de variables de décision peut atteindre 200 (c'est-à-dire si l'entrepôt i distribue à la région j).

△Image générée par DALL·E

Mathématiquement, le problème 2SP est généralement exprimé comme suit :

Parmi eux, Q(x,ξ) représente le problème d'optimisation de deuxième étape étant donné la décision x de première étape et le scénario ξ, et sa forme est :

Dans la solution réelle, N scènes sont généralement échantillonnées pour calculer la valeur Q correspondante afin de se rapprocher de l'attente.

Évidemment, plus N est grand, plus l’approximation est crédible. Cependant, à mesure que le nombre de scénarios augmente, la taille du problème s’étend rapidement, ce qui entraînera une augmentation significative du temps de résolution.

Utilisons le problème de la sélection de l'emplacement de l'entrepôt pour illustrer. Afin de prendre de meilleures décisions de sélection de l'emplacement, nous devons prendre en compte des facteurs incertains tels que la demande, la météo, le flux de personnes, le trafic, etc., et les changements de chaque facteur correspondent à un scénario.

Cela signifie que N scénarios différents doivent être largement échantillonnés pour simuler le plus fidèlement possible la situation réelle. À ce stade, le nombre total de variables de décision dans la deuxième étape atteindra 200N, ce qui rendra le temps de solution extrêmement long.

En fait, lorsque N vaut 500, même en utilisant le solveur commercial le plus avancé Gurobi, il faudra au moins 6 heures pour prendre la décision optimale.

Les méthodes traditionnelles utilisent généralement des techniques d'échantillonnage aléatoire ou de regroupement pour sélectionner un petit nombre de scénarios (par exemple 10 ou 20) en vue d'une solution approximative. Bien que le temps soit réduit, la qualité des décisions qui en résultent n'est souvent pas idéale.

Sur cette base, l'idée de conception du modèle HGCN2SP est dérivée - tout en réduisant le nombre de scènes d'échantillonnage, obtenez des résultats aussi précis que possible.

Utiliser des réseaux convolutifs graphiques pour résoudre le problème 2SP

L'équipe de recherche a proposé le modèle HGCN2SP basé sur un réseau de convolution de graphes hiérarchiques pour résoudre le problème de programmation stochastique en deux étapes.

Plus précisément en termes de conception d'algorithmes, l'équipe a caractérisé le problème 2SP en construisant un graphique hiérarchique, dans lequel le graphique du bas était utilisé pour représenter les caractéristiques de chaque scène, tandis que le graphique du haut était utilisé pour représenter la relation entre les scènes.

Ensuite, un réseau convolutif de graphe hiérarchique (HGCN) est utilisé pour extraire les informations d'intégration du sous-graphe de scène sous-jacent et les informations structurelles de l'espace de scène de niveau supérieur afin d'extraire la représentation de la scène.

Le décodeur basé sur le mécanisme d'attention est utilisé pour sélectionner les scènes dans l'ordre. Il peut non seulement trouver des scènes représentatives pour simplifier le problème, mais également améliorer la sélection de la base initiale lors de la résolution du problème par la méthode simplex en optimisant l'ordre des scènes. Scènes. Améliore considérablement le temps de solution.

△Cadre de modèle HGCN2SP

L'équipe a également combiné l'apprentissage par renforcement (RL) pour examiner de manière approfondie la qualité de la prise de décision et le temps de résolution afin d'optimiser les paramètres du modèle, améliorant ainsi considérablement l'efficacité et la qualité de la résolution des problèmes.

Dans le problème de localisation de l'entrepôt ci-dessus, bien que HGCN2SP n'ait sélectionné que 10 scénarios, la différence entre ses résultats de décision et la décision prise par le solveur Gurobi en 6 heures n'était que de 1,7 % et le temps de solution n'était que de 15 secondes, ce qui équivaut à la vitesse. L'amélioration est de 1440 fois, ce qui reflète pleinement l'efficacité de cette méthode.

De plus, dans l’expérience du Network Design Problem (NDP), HGCN2SP a obtenu des effets décisionnels similaires en moins de la moitié du temps nécessaire aux méthodes existantes.

Surtout dans les instances à grande échelle et dans un grand nombre de scénarios, HGCN2SP conserve de fortes capacités de généralisation.

La proposition HGCN2SP fournit une nouvelle idée et un nouvel outil pour résoudre des problèmes 2SP complexes et offre de larges perspectives d'application.

L'équipe de recherche prévoit d'optimiser davantage le modèle, de réduire les coûts de formation et d'explorer son application dans des problèmes plus pratiques.

Adresse papier :
https://openreview.net/forum?id=8onaVSFTEj